Link between lambda calculus and lambda expressions in C++

Question

I'm trying to undesrtand what is the link between lambda calculus and lambda expressions in C++.

First of all in untyped lambda calculus we don't have "base values" like booleans or ints or whatevr, so everything must be encoded as a function and then we can apply any term to any other term, which isn't quite the case in C++ once it has a type system.

Moreover, I've seen that lambda expressions are either converted in function pointers (when they don't capture anything) or functors (classes with the sole purpose of wrapping functions).

So I wonder, is "lambda expression" just a fancy name for anonymous functions and thus that would resemble lambda calculus (in the sense that terms in lambda expressions can be seen as unnamed functions), or there is more to it?

Thanks in advance.

Answer 1

Alonzo Church did more than just invent the lambda calculus - he came up with a useful notation for functions, lambda notation, which he describes on pp. 5-7 of his 1941 book on the lambda calculus [1]:

To take an example from the theory of functions of natural numbers, consider the expression . If we say, " is greater than 1,000," we make a statement which depends on x and actually has no meaning unless x is determined as some particular natural number. On the other hand, if we say, " is a primitive recursive function," we make a definite statement whose meaning in no way depends on a determination of the variable x (so that in this case x plays the role of an apparent, or bound, variable). … We shall hereafter distinguish by using … as the denotation of the corresponding function ….

In the 1950s, when John McCarthy was developing Lisp, he adopted Church's notation. His 1960 paper describing Lisp explains:

Functions and Forms. It is usual in mathematics—outside of mathematical logic—to use the word "function" imprecisely and to apply it to forms such as y^2 + x. Because we shall later compute with expressions for functions, we need a distinction between functions and forms and a notation for expressing this distinction. This distinction and a notation for describing it, from which we deviate trivially, is given by Church [citing Church [2]].

(He later said "To use functions as arguments, one needs a notation for functions, and it seems natural to use the lambda-notation of Church. I didn’t understand the rest of the book, so I wasn’t tempted to try to implement his more general mechanism for defining functions." [3] Nevertheless, Lisp comes surprisingly close to implementing a form of the lambda calculus.)

Proposals for incorporating anonymous functions into C++ date back to at least 1988 [4], only 9 years after the invention of C++, and the authors appear to have been well aware of the Lisp usage and adopted the name. The proposal which made it into the C++11 standard [5], and work leading up to it (e.g. [6], [7]) simply say (for example) "The term originates from functional programming and lambda calculus, where a lambda abstraction defines an unnamed function." [6]

So to answer your question: lambda expressions are related not so much to the full lambda calculus developed by Church, but to the lambda notation he invented to denote anonymous functions.

References

[1] Church, Alonzo. The calculi of lambda-conversion. Princeton University Press, 1941.

[2] McCarthy, John. "Recursive functions of symbolic expressions and their computation by machine, Part I." Communications of the ACM 3.4 (1960): 184-195.

[3] McCarthy, John. "History of LISP." History of programming languages I. ACM, 1978. url: http://jmc.stanford.edu/articles/lisp.html

[4] Breuel, Thomas M. "Lexical closures for C++." In Proceedings of the 1988 USENIX C++ Conference, pp 293-304, Denver, Colorado, 17-21 October. url: http://web.archive.org/web/20060221054001/https://people.debian.org/~aaronl/Usenix88-lexic.pdf

[5] Järvi, J et al. "Lambda Expressions and Closures: Wording for Monomorphic Lambdas (Revision 4)". url: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2550.pdf

[6] Boost.Lambda http://www.boost.org/doc/libs/1_62_0/doc/html/lambda.html

[7] Jarvi, J and and G. Powell. "The Lambda Library : Lambda abstraction in C++." Technical Report 378, Turku Centre for Computer Science, November 2000. url: http://web.archive.org/web/20060428170631/http://www.tucs.fi:80/publications/techreports/TR378.php

Bibliography

• Graham, Paul, "The Roots of Lisp", 2001. http://www.paulgraham.com/rootsoflisp.html

• van Emden, Maarten, "McCarthy’s recipe for a programming language", 2011. https://vanemden.wordpress.com/2011/10/31/mccarthys-recipe-for-a-programming-language/

• Cardone, Felice and J. Roger Hindley, "History of Lambda-calculus and Combinatory Logic", 2006. https://github.com/aistrate/Articles/blob/master/Haskell/History%20of%20Lambda-calculus%20and%20Combinatory%20Logic%20(Cardone,%20Hindley).pdf