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 xplusine in C++11

Generic Function xplusone in C++11

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

xplusone in Lisp

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

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.

xplusone as generic lambda

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

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

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

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++

Lambda-over-Lambda in C++

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

C++14 Currying

C++14 Currying

C++ Currying Build & Run

C++ Currying Build & Run

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

C++ Generic Currying

C++ Generic Currying

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

C++ Generic Currying Invocation

C++ Generic Currying Invocation

C++ Generic Currying Evaluation

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

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

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 ?

Hello World ?

Ok, but this runs into trouble.

Build Error

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

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

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

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.

 

 

 

 

 

 

 

 

 

 

 

 

11 responses to “Lambda-Over-Lambda in C++14

  1. s/Dough/Doug/g – Although that did make me chortle.

    Really enjoying this little series of posts. Thanks!

  2. I think you might be interested in the implementation of flatmap/bind and an overall collection pipeline over here: http://cpptruths.blogspot.com/2014/08/fun-with-lambdas-c14-style-part-3.html

    • Thank you for this Sumant. I realise that what I have is technically a monad but that I still lack some utility functions to make it ultimately useful. Will have a read of the link you provided. Thanks again.

      Chris

  3. Mirko

    There could be a typo in your monad section:

    “We have a lambda terminal that accepts term as input then constructs another lambda which closes over the free variable term and calls a function func on it which in turn accepts *func* as input.”

    Should it be *term* instead of *func*? (I’m just guessing here – still trying to digest it).

    • Thanks for that Mirko – not so much a typo as badly worded. I updated the blog with a “fix.” To elaborate: there are two lambdas here. The purpose of the outer lambda is to act as a constructor for the second lambda. It does this by priming the second lambda with its state: term. Term is captured by that second lambda as it is a free variable in its lexical scope – this lexical scope being furnished by the outer lambda. In a sense, the second lambda now has a member variable called term if you were to think of it in object oriented terms. After evaluating terminal, all you have in your hands is the second lambda. But what is that? It’s a function that accepts a formal parameter func. Func is also a function. What does it do ? It operates on term.

      All this is very similar to the double indirection provided by the visitor pattern in object orientation land. It’s also the reason that functional programming has no use for this design pattern, because what that design pattern furnishes comes for free in functional programming at the language level through higher order functions. What is solved by the visitor pattern is the Expression Problem: http://en.wikipedia.org/wiki/Expression_problem. Understanding why solving the expression problem is a big deal is one key to understanding the significantly superior expressiveness of the functional paradigm over imperative programming.

      Best Regards

      Chris

  4. swmckay

    LOL, the funny thing now is that if you count *all* the brackets in the C++ code, it adds up to about the same as the number of open- and close-parentheses in the Lisp code. If C++16 simply fixes the syntax to use C-expressions (pronounced “ess-expressions”) and replaces all statements with expressions that return values, then it’ll really be getting somewhere.

  5. I have created huge systems in C++ using a combination of Generic Programming and Functional Programming meta models. I am nowadays more of Clojure + Scala + Elixir developer, but welcome the C++14 (proposed) changes, to enable polymorphism even in the anonymous realm of functoids. C++ actually has a lot of expressivity — no, I didn’t even mention performance — that most FP languages lack, from its (admittely ad hoc) notion of templates. So, there are other reasons but performance and even ABI compatibility to use C++ before other (FP) languages.

    C++ is indeed re-converging. From a hairy mishmash to a more streamlined FP+GP experience. Perhaps a bit too late? Well, I welcome the changes, and the quite quick uptake of the new standard features in the compilers (MSVC, GCC and CLang, specifically…)

    Am at loss when people claim that using functional techniques — such as HOFs and functional combinators — is simply an exercise and cannot be used for “real programming.” One should not eject that style of programming in C++ merely due to one’s own shortcomings. I can assure you that functional programming in C++ is used in highly real systems. Or perhaps I have just been dreaming the two million lines of C++ code I have written since 1989, with heavy use of functional combinations and streams (such as using Boost’s iterator transformers, yielding streams or Haskell/Clojure-like lazy sequences.)

    Yes, you can create crappy, procedural monsters with C++. But you can write quite succinct FP+GP programs as well. And even more so with C++11, and with C++14.

    I will now go back to my Scala hacking…

  6. nitpicker

    One suggestion I would like to make is to use the term ‘function object’ instead of ‘functor’, so as not to mix those with functors from category theory.

  7. Pingback: Lambda-Over-Lambda in C++14 | thoughts...

  8. James Anastasiou

    This was absolutely brilliant.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s