Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Lisp is not based on the Lambda Calculus

danielsz.github.io

Post reply on HN
Print view View original

41–50 of 138 posts

Re: Lisp is not based on the Lambda Calculus

#41

Post by kazinator »

kmill wrote: post #34
vga805 wrote: 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…

and (e) mutation: `setq`, `rplacd`, ...

Re: Lisp is not based on the Lambda Calculus

#42

Post by bjourne »

Afaik, Haskell is a realization of the (typed!) lambda calculus. Lisps aren't because they don't do lazy evaluation. The LC beta reduction of (\a. a) (\c. d) (\e. f) is (\c. d) (\e. f) but most lisps will reduce it to (\a. a) d. This might seem like a minor detail but means general recursion using the y combinator isn't actually implementable in lisps (I could be wrong though).

Re: Lisp is not based on the Lambda Calculus

#43

Post by deckard1 »

When pedantry goes wrong...?

This article repeats this "TL;DR Lisp is not based on the Lambda Calculus"

But that's not actually what McCarthy said. McCarthy said:

> 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

"Based on" and "realization of" are two different things. This kind of exaggerated or hyperbolic pedantry strikes me as clickbait. Which is unfortunate, because the article does contain some good content.

If you read the LISP I manual, you will see that concepts beyond the obvious lambda notation are used directly from The Calculi of Lambda Conversion. Notably, the distinction between forms and functions.

Clearly, we're splitting some very fine hairs here.

Re: Lisp is not based on the Lambda Calculus

#44

Post by nils-m-holm »

Lambda Calculus (LC) versus LISP is not just about lexical scoping, but also about partial application (currying), which is cumbersome in LISP and natural in LC. In LC (where \ = lambda)

    (\xy.x)M  ==>  \y.M
while in LISP

    ((lambda (x y) x) M)  ==>  undefined
because the lambda function expects two arguments. Of course

\xy.x is just an abbreviation for \x.\y.x, so the LISP counterpart would really be

    ((lambda (x) (lambda (y) x)) M)  ==>  (lambda (y) M)
but this only proves the point that currying is natural in LC and not in LISP, because LC provides syntactic sugar that allows to treat higher-order functions and functions of multiple variables in the same way.

Also, LC is not compatible with functions with a variable number of arguments, which is common in LISP. For instance,

    (+ 1)  ==>  1
in most LISPs, but given PLUS == \mnfx.mf(nfx) and 1 == \x.fx

    PLUS 1  ==>  \nfx.f(nfx) == SUCC
i.e., (PLUS 1) reduces to "SUCCessor", the function adding one to its argument.

In most LISP dialects, you can pass any number of arguments to a variable-argument function like +. So what does the syntax (F X) denote in general? The application of a unary function to one argument or the partial application of a binary function? Or a ternary one...?

In LC it does not matter, because multi-variable functions and higher-order functions are the same.

I have developed a LISPy language that uses currying instead of functions of multiple arguments in the book Compiling Lambda Calculus (https://www.t3x.org/clc/index.html).

You can download the code here: https://www.t3x.org/clc/lc1.html.

Re: Lisp is not based on the Lambda Calculus

#45

Post by qubex »

Anybody who holds forth of syntactical matters (lambda calculus and LISP being two examples thereof) and commits the grammatical heresy of writing “I wasn’t going to go home” (emphasis mine) in lieu of “I wouldn’t be going home” has just neutered themselves, in my humble opinion at least.

Re: Lisp is not based on the Lambda Calculus

#46

Post by carapace »

didibus wrote: post #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?

We know "the root of the tree for the origin of functional programming": John Backus's Turing Award lecture "Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs"

https://amturing.acm.org/award_winners/backus_0703524.cfm It's not obvious but the "ACM Turing Award Lecture" link is the PDF.

Re: Lisp is not based on the Lambda Calculus

#47

Post by foldr »

qubex wrote: post #45

Anybody who holds forth of syntactical matters (lambda calculus and LISP being two examples thereof) and commits the grammatical heresy of writing “I wasn’t going to go home” (emphasis mine) in lieu of “I wouldn’t be going home” has just neutered themselves, in my humble opinion at least.

There's nothing grammatically wrong with "going to go home".

Re: Lisp is not based on the Lambda Calculus

#50

Post by mrkeen »

bjourne wrote: post #42

Afaik, Haskell is a realization of the (typed!) lambda calculus. Lisps aren't because they don't do lazy evaluation. The LC beta reduction of (\a. a) (\c. d) (\e. f) is (\c. d) (\e. f) but most lisps will reduce it to (\a. a) d. This might seem like a minor detail but means general recursion using the y combinator isn't actually implementable in lisps (I could be wrong though).

> general recursion using the y combinator isn't actually implementable in lisps

I think the 'typed' bit is key. You can't implement Y in plain old Haskell because it would need to recurse infinitely during type-checking.

Post reply on HN