All geek questions in one place

The relationship between lambda calculus and lambda expressions in C ++

I am trying to undesrtand what is the relationship between lambda calculus and lambda expressions in C ++.

First of all, in untyped lambda calculus, we don’t have “basic values”, such as logical or ints or whatevr, so everything should be encoded as a function, and then we can apply any term to any other term that is not quite true in C ++ when it has a type system.

In addition, I saw that lambda expressions are either converted to pointers to functions (when they don't commit anything) or functors (classes for the sole purpose of wrapping functions).

So, I wonder if the expression "lambda" is just a fancy name for anonymous functions and, therefore, it will resemble a lambda calculus (in the sense that the terms in lambda expressions can be considered as unnamed functions), or are there more of them?

Thanks in advance.

+5
source share
1 answer

Alonso’s church did more than just invent lambda calculus — he came up with a useful notation of functions, a lambda notation, which he describes on pages 5-7 of his 1941 book on lambda calculus [1]:

To take an example from the theory of functions of natural numbers, consider the expression (x ^ 2 + x) ^ 2 . If we say: " (x ^ 2 + x) ^ 2 greater than 1000, "we make a statement that depends on x and actually makes no sense, unless x is defined as some definite positive integer. On the other hand, if we say:" (x ^ 2 + x) ^ 2 - a primitive-recursive function ", we make a certain statement, the value of which in no way depends on the definition of the variable x (so in this case x plays the role of a visible or related variable). ... We will continue to distinguish using ... (\ lambda (x ^ 2 + x) ^ 2) as a designation of the corresponding function ....

In the 1950s, when John McCarthy developed Lisp, he adopted church notation. His 1960 paper describing Lisp explains:

Functions and forms. Usually in mathematics - outside of mathematical logic - use the word "function" implicitly and apply it to forms such as y ^ 2 + x. As we further compute expressions for functions, we need to distinguish between functions and forms and the designation for expressing this difference. This distinction and designation for the description from which we deviate trivially is given by the Church [with reference to the Church [2]].

(He later said: “To use functions as arguments, you need a notation function for functions, and it seems natural to use the Church's lambda notation. I did not understand the rest of the book, so I was not tempted to try to implement my more general mechanism for defining functions.” . [3] However, Lisp is unexpectedly close to implementing a form of lambda calculus.)

Suggestions for the inclusion of anonymous functions in C ++ date back to at least 1988 [4], only 9 years after the invention of C ++, and the authors seem to be well aware of the use of Lisp and used this name. The proposal introduced in the C ++ 11 standard [5], and the work leading to it (for example, [6], [7]) are simply spoken (for example). "The term comes from functional programming and lambda calculus, where the lambda abstraction defines an unnamed function." [6]

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

References

[1] Church, Alonso. Lambda transform calculus. Princeton University, 1941.

[2] McCarthy, John. "The recursive functions of symbolic expressions and their calculation by machine, part I." Communications 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] Breel, Thomas M. "Lexical closures for C ++." In the proceedings of the 1988 USENIX C ++ Conference, pp. 293-304, Denver, Colorado, October 17-21. 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 lambda (version 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] Jarvey, J., and G. Powell. "The Lambda Library: An Abstraction of Lambda in C ++." Technical Report 378, Turku Computer Science Center, November 2000 url: http://web.archive.org/web/20060428170631/http://www.tucs.fi:80/publications/techreports/TR378.php

Bibliography

+5
source

Source: https://habr.com/ru/post/1274636/

More articles:


All Articles