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:
This snippet was given as equivalent to the Lisp function shown below.
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:
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:
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 counterreturns 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.
Here we define a generic xplus function constructor. It takes an argument ywhich 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.
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.
Let’s skip straight to the curried form of invoking this construct…
This worked rather nicely. How about making it generic ? We want to curry an arbitrary binary function.