Lambda-Over-Lambda in C++14

The Convergence of Modern C++ on the Lisp Programming Style – Part II

In The Convergence of Modern C++ on the Lisp Programming Style  we looked at how C++11 standard has evolved to become  an algorithmic language that increasingly incorporates features of the language Lisp. In this post we will look at what C++14 brings to the table in this regard.  As implied by the title, we will be looking at lambdas. There is one key feature in the C++14 standard that is relevant here N3649: Generic Lambdas.

Lets us revisit a trusted example from  The Convergence of Modern C++ on the Lisp Programming Style:

Generic Function xplusone in C++11

This snippet was given as equivalent to the Lisp function shown below.

xplusone in Lisp

In both cases the return type is inferred from the result of the addition of 1 and x. And in both cases, x is a generic variable.

I did, however, gloss over one key difference: The Lisp version is actually a named lambda. This is because “defun” is itself a macro. As a consequence, xplusone  is really a symbol bound to a lambda expression. This is the default under Lisp. By contrast, in C++ functions are “static” by default unless they are, for instance, declared as variables of type std::function and a lambda is assigned.

We can observe this in the macro expansion shown below:

Defun macro expansion to NAMED-LAMBDA

It will become apparent shortly why this is interesting. Firstly, let us return to our C++ function xplusone. It employs a generic type, hence it is templated. Let us see how that simplifies under C++14 and generic lambdas.

Three observations are striking immediately:

1) The use case for a template has disappeared entirely. We simply have a generic function argument x. This matches Lisp.

2) The code is now entirely as brief as Lisp. Where Lisp has a lot of parenthesis,  this style of coding develops a lot of “autos.”

3) The mechanics are identical also. Both functions are actually named lambdas.

To be fair, the C++ version of the code was implemented as a functor,  giving it a little extra bulk. But there was a reason for this. In pre-C++11 days, a functor provided the means to construct a function bundled with state, a pre-cursor to the closure. This brings us to the next subject…

Let-over-Lambda and Lambda-over-Lambda

One way to construct closures in Lisp is the  let-over-lambda idiom discussed in detail in Dough Hoyte’s book by the same title “Let over Lambda.” The key take-away is that a closure is a function with state “bound in” by a let binding. The closure is “closed over a free variable” – hence the term closure. The closure is constructed by returning it from another function which creates the let binding. A simple example will illustrate:

 

Simple Let over Lambda Idiom

In the above example we create a constructor function counter which first performs a let binding of the value zero to the symbol x. Then it defines a function f  that has x as a free variable ( it will be captured  from the lexical scope of f ). The function f increments x, then returns its value. Finally counter returns f as the value of its expression. Now we can construct a variable n as an instance of counter and  call n repeatedly. This does what is expected. Subsequent invocations increment x. Closures are simple and elegant building blocks. In a sense, they are simply the inverse of objects. Objects are types or state with function(s). Closures are functions with state.  The latter are the basic building blocks of functional programming. The key difference: functions compose algebraically and can be reasoned about using the Lambda calculus. Incidentally, the lambda calculus also requires functions to be monadic. More about that later.

We have already established that a defun is but a named lambda. Thus a let-over-lambda idiom is an instance of a more general lambda-over-lambda. The let binding is used to bind state information into the closure – yet we can achieve this in other ways. Let us make our xplusone more generic and restate the problem as just xplus. This will make for an interesting exercise.

Lambda-Over-Lambda in Lisp

Here we define a generic xplus function constructor. It takes an argument y which is a free variable in the lambda expression (+ x  y) which is to say y is not an input parameter to our lambda function. The resulting lambda (with y captured) is returned as the value of the expression xplus. We may now create instances of xplus as closures and  invoke them as shown above. Conversely, we might elide defining dedicated closures and make function invocation more direct as shown below.

Schönfinkel’ing

In the above example we rendered what used to be a binary function (plus) into two monadic functions. This is also referred to as Schönfinkel’ing after its author Moses Schönfinkel or Currying after Haskell Curry who elaborated the technique. (xplus 2) is also an instance of partial function application as it applies part of the expression (+ 2 3), namely + 2.

Armed with the above knowledge, we might infer C++ is now at last equipped with the syntax for true functional programming. Let us translate what we have written above into the equivalent C++.  Given that defun is another notation for lambda, we expect our C++ expression for plus to be an instance of the lambda-over-lambda idiom.

Lambda-over-Lambda in C++

Let’s skip straight to the curried form of invoking this construct…

C++14 Currying

C++ Currying Build & Run

This worked rather nicely. How about making it generic ? We want to curry an arbitrary binary function.

C++ Generic Currying

All appearance to the contrary, the above is actually C++…

C++ Generic Currying Invocation

C++ Generic Currying Evaluation

Not only can we leverage currying and partial function application, we can also make this generic thanks to N3649. Single argument functions are a corner stone of the Lambda Calculus.

Summary

1) C++14 generic lambdas enable a degree of functional programming that has, until now, been impossible in C++.

2) They make C++ constructs more concise.

3) They eliminate many use cases of template syntax that has been a hallmark of C++ since the introduction of the STL.

4) The mechanics underpinning C++ and Lisp lambda closures is identical: the lambda-over-lambda idiom.

5) Lisp tends toward lambda as the default for functions. The same is bound to happen to C++ in that using auto parameters with standard functions is not possible — but in lambdas it is. This makes lambdas a far more powerful means of abstraction than regular functions.

When the C++ standard introduced template, an entire coding style of generic programming unfolded on this which made “<>” as ubiquitous as the pointer symbol “*” had been in C land. With the introduction of generic lambdas to the C++ standard, a genuine functional coding style is about to unfold and perhaps  make the keyword auto just as ubiquitous.

Epilogue – Monads

Now that we have acquainted ourselves with the lambda-over-lambda idiom, we can tackle another: monads.  I tend to think of monads as “chainable state containers.” There are many analogies, but just like the lambda-over-lambda idiom, one has to see it in action to appreciate what it does.  So rather than purvey extravagant terminology, let’s get cooking. As one might guess, we start with lambda-over-lambda.

Monad 1st Attempt

So what do we have? We have a lambda terminal that accepts term as input, then constructs another lambda ( a closure ) which closes over the free variable term. The second lambda in turn accepts func as input where func operates on term as stored by the closure.  We then define another lambda hello which accepts a stream s ( or file descriptor in this case ) and calls fprintf on this with the string “hello.” Ultimately, it returns s. The latter is highly significant. It’s akin to a const reference return type from a class member returning *this. It’s also what std:cout does to effect chaining <<  <<  <<.  And it’s chaining that we are after.  Let’s build and evaluate:

Terminal Hello

Nifty – looks a lot like currying and partial function evaluation that we saw earlier. Can we extend this? Let’s amend our example to see what happens.  Let’s try something like this :

Hello World ?

Ok, but this runs into trouble.

Build Error

Why might that be ?  Let’s do the mental code walk. terminal is a constructor which returns a closure. The closure is a wrapper that holds our state: stdout.   The hello lambda returns that state. So after terminal(stdout) we have a closure that accepts a function. After (hello) – what do we have ? Just stdout. Can we modify hello to return something else ? No, hello only knows about s. And its returns s. This is known as an endofunctor in category theory.  So we need to map in something else that returns a closure once again which expects a function that we can pass (world) to. We will call this fmap.

Here is our completed solution.

Monad Final

Now instead of chaining our functions hello and world directly, we chain the  respective fmap wrappers. Let’s see if this works.

Monad Evaluation

Nifty – this does what we expect.  We now have a way of priming this mechanism with some state and then successively composing functions by chaining our wrappers. We can even use these wrappers as decorators adding rules and modifiers as we go. Some axioms must hold. Each inner function ( hello, world, newline ) must map its input to an output of a compatible type. So a number can become a price and a price can become an interest rate. These are said to be in the same type “category.” And each mapping operation must accept a “wrapper” and yield a compatible “wrapper” that can become the input into the next mapping operation. You might visualise this as two strands that run along side each other. One successively yielding a modified variable – the other successively yielding possibly modified wrappers. Each invocation has one argument and is thus said to be monadic. Each operation is composable with its successor. This wrapper construct is the essence of a monad. And with C++14 and thanks to N3649 it has become as succinct as in Lisp or Haskell…

Haskell has a formalism for this. All other languages condemn us to repeat this formalism.

Applicative

What does this say? Pure says take an ‘a’ and wrap it in an ‘f a’. Note that this is not a an ‘f’ of ‘a’, as in a function of ‘a’ that will yield a ‘b.’ It’s still an ‘a’, unmodified, just wrapped in ‘f.’ The type formalism tells us a lot. The apply operator <*>, called “spaceship,” then takes a function (a -> b) and an “f a” wrapper and yields a “f b” wrapper. We did just that above. “fmap” is our wrapper. It does not modify what it wraps. “terminal” applies the function a -> b. But we don’t return our ‘b.’ Rather we return a wrapped ‘b.’ In Haskell this idiom is referred to as a Type Class which is to say a data type that is constrained in some way. The closest C++ comes to this is “concepts,” but it utterly lacks the ability to reason about these.