Live data from Hacker News

Lisp is not based on the Lambda Calculus

danielsz.github.io

31–40 of 138 posts

Re: Lisp is not based on the Lambda Calculus

#31
post #4

It is difficult to believe that McCarthy did not understand he was beating the same horse along with Church, Curry, Schoenfinkel, et al.

I mean, he obviously was aware of lambda-calculus as a thing that existed (since he used lambda notation for functions!), but might not have bothered to study it very closely. Nowadays the lambda calculus is considered very elegant, but in the 1940s I think it was considered quite weird and not very well known. (I forget who, but I think some famous logician complained that people did not read his thesis because it used the lambda-calculus formalism, or was adviced not to use it for that reason, or something like that.)

I think, actually the main reason it became so popular is exactly because it was implemented in Lisp/Scheme...

Re: Lisp is not based on the Lambda Calculus

#32
post #3

The post quotes McCarthy: "one of the myths concerning LISP that people think up or invent for themselves becomes apparent, and that is that LISP is somehow a realization of the lambda calculus, or that was the intention. The truth is that I didn't understand the lambda calculus, really" - John McCarthy So there are a two issues here, 1) whether or not it was McCarthy's intention to realize the Lambda Calculus in LIS…

> So there are a two issues here, 1) whether or not it was McCarthy's intention to realize the Lambda Calculus in LISP, and 2) whether or not LISP is such a realization. Or at least some kind of close realization.

This would fit in with Graham's suggestion that McCarthy more "discovered" Lisp than "invented" it.

Re: Lisp is not based on the Lambda Calculus

#33
post #3

The post quotes McCarthy: "one of the myths concerning LISP that people think up or invent for themselves becomes apparent, and that is that LISP is somehow a realization of the lambda calculus, or that was the intention. The truth is that I didn't understand the lambda calculus, really" - John McCarthy So there are a two issues here, 1) whether or not it was McCarthy's intention to realize the Lambda Calculus in LIS…

Modern lisps do realize the lambda calculus, but this was not immediate. In particular, in order to exactly match the lambda-calculus beta-reduction rule, you need to use lexical rather than dynamic scope, which did not really become popular until Scheme in the 1970s.

Re: Lisp is not based on the Lambda Calculus

#34
post #3

The post quotes McCarthy: "one of the myths concerning LISP that people think up or invent for themselves becomes apparent, and that is that LISP is somehow a realization of the lambda calculus, or that was the intention. The truth is that I didn't understand the lambda calculus, really" - John McCarthy So there are a two issues here, 1) whether or not it was McCarthy's intention to realize the Lambda Calculus in LIS…

If it was a realization of a lambda calculus, then it is one with (a) primitives, (b) strict evaluation, (c) quoted lambda terms, and (d) "dynamic" bindings.

(a) In classic lambda calculus, everything is a lambda term. McCarthy's Lisp has primitives like lists and numbers. However, it is known that lambda calculus is powerful enough to encode these things as lambda terms (for example,

  null = (lambda (n c) (n))
  (cons a b) = (lambda (n c) (c a b))
gives a way to encode lists. The car function would be something like

  (car a) = (lambda (lst)
              (lst (lambda () (error "car: not cons"))
                   (lambda (a b) a)))
This would not work in the original Lisp because of binding issues: the definition of cons requires the specific a and b bindings be remembered by the returned lambda.)

(b) Lambda calculus does not have any evaluation rules. Rather, it is like algebra where you can try to normalize an expression if you wish, but the point is that some lambda terms are equivalent to others based on some simple rules that model abstract properties of function compositions. Lambda-calculus-based programming languages choose some evaluation rule, but there is no guarantee of convergence: there might be two programs that lambda calculus says are formally equivalent, but one might terminate while the other might not. Depending on how you're feeling, you might say that no PL for a computer can ever realize the lambda calculus, but more pragmatically we can say most languages use lambda calculus with a strict evaluation strategy.

(c) The lambda terms in lambda calculus are not inspectable objects, but more just a sequence of symbols. Perhaps one of the innovations of McCarthy is that lambda terms can be represented using lists, and the evaluator can be written as a list processor (much better than Godel numbering!). In any case, the fact that terms have the ability to evaluate representations of terms within the context of the eval makes things a little different. It's also not too hard to construct a lambda evaluator in the lambda calculus[1], but you don't have the "level collapse" of Lisp.

(d) In lambda calculus, one way to model function application is that you immediately substitute in arguments wherever that parameter is used in the function body. Shadowing is dealt with using a convention in PL known as lexical scoping, and an efficient implementation uses a linked list of environments. In the original Lisp, there was a stack of variable bindings instead, leading to something that is now known as dynamic scoping, which gives different results from the immediate substitution model. Pretty much everything fun you can do with the lambda calculus depends on having lexical scoping.

All this said, the widespread belief about Lisp being the lambda calculus probably comes from Scheme, which was intentionally lambda calculus with a strict evaluation model. Steele and Sussman were learning about actors for AI research, and I think it was Sussman (a former logician) who suggested that their planning language Schemer (truncated to Scheme) ought to have real lambdas. At some point, they realized actors and lambdas (with mutable environments) had the exact same implementation. This led to "Scheme: An Interpreter for Extended Lambda Calculus" (1975) and the "Lambda the ultimate something" papers. Later, many of these ideas were backported to Lisp during the standardization of Common Lisp.

[1] https://math.berkeley.edu/~kmill/blog/blog_2018_5_31_univers...

Re: Lisp is not based on the Lambda Calculus

#35
It isn't clear though if McCarthy didn't know anything about the Lambda Calculus, or simply didn't know it well and didn't create Lisp as a concrete realization of Lambda Calculus. In that, he might have created Lisp for whatever other reasons and was doing his own exploration, but it's probable that in doing so, he used his inherent knowledge of many pre-existing literature, which could include some of Lambda Calculus, thus Lisp having some resemblance to it, like the use of lambda to define functions.

Also, realistically speaking, no programming language is based on the Lambda Calculus as is, even those that try to be.

Re: Lisp is not based on the Lambda Calculus

#36
post #3

The post quotes McCarthy: "one of the myths concerning LISP that people think up or invent for themselves becomes apparent, and that is that LISP is somehow a realization of the lambda calculus, or that was the intention. The truth is that I didn't understand the lambda calculus, really" - John McCarthy So there are a two issues here, 1) whether or not it was McCarthy's intention to realize the Lambda Calculus in LIS…

both fair points but I'd like to know if he mentioned why on earth did he pick lambda. lambda expressions/closures turned out to be a very peculiar and important path.

[deleted]

Re: Lisp is not based on the Lambda Calculus

#37
Can we extend from this another misconception then? That functional programming stems from the Lambda Calculus? When in reality, it might come from Lisp, which does not come from Lambda Calculus, thus making Lisp the root of the tree for the origin of functional programming?

Re: Lisp is not based on the Lambda Calculus

#38
post #3

The post quotes McCarthy: "one of the myths concerning LISP that people think up or invent for themselves becomes apparent, and that is that LISP is somehow a realization of the lambda calculus, or that was the intention. The truth is that I didn't understand the lambda calculus, really" - John McCarthy So there are a two issues here, 1) whether or not it was McCarthy's intention to realize the Lambda Calculus in LIS…

Modern lisps do realize the lambda calculus, but this was not immediate. In particular, in order to exactly match the lambda-calculus beta-reduction rule, you need to use lexical rather than dynamic scope, which did not really become popular until Scheme in the 1970s.

Did not become popular, or did not become implemented?

My understanding is that lexical scope was first implemented in Algol and Pascal, and then was first implemented with true garbage collection in Scheme. (Thereby leading to the restriction in Algol and Pascal that closures existed, but they could only be passed into functions, and never returned from them. That way the variables being closed over could live on the stack.)

But I'd love to learn that I'm wrong and that these things came before that.

Re: Lisp is not based on the Lambda Calculus

#39
post #34
post #3

The post quotes McCarthy: "one of the myths concerning LISP that people think up or invent for themselves becomes apparent, and that is that LISP is somehow a realization of the lambda calculus, or that was the intention. The truth is that I didn't understand the lambda calculus, really" - John McCarthy So there are a two issues here, 1) whether or not it was McCarthy's intention to realize the Lambda Calculus in LIS…

If it was a realization of a lambda calculus, then it is one with (a) primitives, (b) strict evaluation, (c) quoted lambda terms, and (d) "dynamic" bindings. (a) In classic lambda calculus, everything is a lambda term. McCarthy's Lisp has primitives like lists and numbers. However, it is known that lambda calculus is powerful enough to encode these things as lambda terms (for example, null = (lambda (n c) (n)) (cons…

Thank you.

This is probably the most informative comment that I've read on HN in the last couple of months.

Re: Lisp is not based on the Lambda Calculus

#40
post #38

Earlier quoted context omitted.

Modern lisps do realize the lambda calculus, but this was not immediate. In particular, in order to exactly match the lambda-calculus beta-reduction rule, you need to use lexical rather than dynamic scope, which did not really become popular until Scheme in the 1970s.

Did not become popular, or did not become implemented? My understanding is that lexical scope was first implemented in Algol and Pascal, and then was first implemented with true garbage collection in Scheme. (Thereby leading to the restriction in Algol and Pascal that closures existed, but they could only be passed into functions, and never returned from them. That way the variables being closed over could live on th…

Oh, I think you're right, Scheme was at least the first lexically scoped Lisp.

Wikipedia says

> The concept of closures was developed in the 1960s for the mechanical evaluation of expressions in the λ-calculus and was first fully implemented in 1970 as a language feature in the PAL programming language to support lexically scoped first-class functions.

> PAL, the Pedagogic Algorithmic Language, is a programming language developed at the Massachusetts Institute of Technology in around 1967 to help teach programming language semantics and design. It is a "direct descendant" of ISWIM and owes much of its philosophy to Christopher Strachey.

Post reply on HN