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

91–100 of 138 posts

Re: Lisp is not based on the Lambda Calculus

#91

Post by paulddraper »

vilhelm_s wrote: post #33
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…

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.

Now, all the Lisps (Racket, Clojure) are lexically scoped.

Common LISP is lexically scoped, though it does still have opt-in dynamic scoping ("special variables").

Re: Lisp is not based on the Lambda Calculus

#92

Post by paulddraper »

carapace wrote: post #48
leshow wrote: post #5

Stupid question, why is it often written "_the_ lambda calculus" and not just "lambda calculus"

Because there's only one. E.g. If we meet aliens someday their Lambda Calculus will be the same as ours. Just like their integers will be the same as ours.

> Just like their integers will be the same as ours

"The one, the two, the three, the four,...."

Re: Lisp is not based on the Lambda Calculus

#93

Post by ProfHewitt »

kmill wrote: post #69
paulddraper wrote: post #53

Earlier quoted context omitted.

> In classic lambda calculus, everything is a lambda term OO says everything is an object. Even though Java has non-object primitives, we're still gonna classify Java as OO. > Lambda calculus does not have any evaluation rules. > The lambda terms in lambda calculus are not inspectable objects, but more just a sequence of symbols. It's not clear to me why this makes Lisp not in the family of Lambda implementations. >…

Unlike lambda calculus, OO is not a specific mathematical formalism but rather a methodology and ontology for organizing a program. Lambda calculus, defined by Alonzo Church, is a kind of 'arithmetic' of abstract function manipulation devoid of semantics. It has some strong theoretical footing as, in modern language, reflexive objects in a category. > It's not clear to me why this makes Lisp not in the family of Lamb…

Object orientation derived from Simula-67 which was lexically scoped and preceded Sch3me by many years.

Re: Lisp is not based on the Lambda Calculus

#94

Post by ProfHewitt »

pron wrote: post #62
paulddraper wrote: post #53

Earlier quoted context omitted.

> In classic lambda calculus, everything is a lambda term OO says everything is an object. Even though Java has non-object primitives, we're still gonna classify Java as OO. > Lambda calculus does not have any evaluation rules. > The lambda terms in lambda calculus are not inspectable objects, but more just a sequence of symbols. It's not clear to me why this makes Lisp not in the family of Lambda implementations. >…

> this contributes to the notion that LISP/Schema/Lambda Calculus were "discovered", not that Lambda calculus has an explicit pedigree. That notion is wrong (at least with a very high likelihood), and it's usually stated by people who fetishize the lambda calculus but know little of its long evolution. It's just your ordinary case (of hubris) where people aesthetically drawn to something describe it as inevitable or…

The lambda calculus and Turing machines are both adequate for Church/Turing computability. However, neither are adequate for all digital computation.

Re: Lisp is not based on the Lambda Calculus

#95

Post by ProfHewitt »

pron wrote: post #86
carlehewitt wrote: post #82

Earlier quoted context omitted.

BTW, the Church/Turing theory of computation is not universal for digital computation as explained in the following article: https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3418003

That proof is like disproving the conservation of energy by pointing out that the water inside a kettle boils. Or speaking about the "Toaster-Enhanced Turing Machine" ( https://www.scottaaronson.com/blog/?p=1121 ). It's easy to "disprove" Turing's thesis when you misstate it. Turing's thesis talks about some system transforming an input to an output. Clearly, a TM could simulate the actor itself in your proof. If it…

There are simple nondetermintic procedures that can be implemented by digital circuits using arbiters that cannot be implemented by a nondeterminustic Turing Machine.

Re: Lisp is not based on the Lambda Calculus

#96

Post by curryhoward »

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).

> Afaik, Haskell is a realization of the (typed!) lambda calculus. Lisps aren't because they don't do lazy evaluation.

Lazy evaluation is just one possible operational semantics for a lambda calculus. Eager evaluation is another. In fact, all of the versions of lambda calculi presented in Benjamin Pierce's widely-read textbook "Types and Programming Languages" feature eager evaluation rather than lazy evaluation.

So the claim that the reason that Lisps aren't based on the lambda calculus is due to lack of lazy evaluation is incorrect. There are other reasons that Lisps diverge from lambda calculi but the evaluation strategy isn't one of them.

Re: Lisp is not based on the Lambda Calculus

#97

Post by DonHopkins »

carlehewitt wrote: post #80
kmill wrote: post #34

Earlier quoted context omitted.

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…

Schemer (later renamed Scheme) was invented to scheme against Actors reprising Conniver, which was invented to connive against Planner. See the following for the current state of the art including the latest Actor approach to Eval, which is more modular and concurrent than the Eval in Lisp and Scheme: https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3418003 The above article explains exactly how Actors are much mo…

How wonderful to hear directly from the Master himself! Brilliant!!! Thank you! ;)

https://www.youtube.com/watch?v=dmZSkWBJwBU

https://www.youtube.com/watch?v=AtnBumt82_Y

Re: Lisp is not based on the Lambda Calculus

#98

Post by didibus »

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

Not really, Peter Landin’s ISWIM is essentially syntactic sugar over lambda calculus, and went on to influence ML and Haskell. So there is a more direct lineage from lambda calculus to functional programming via that route. (Regarding the sibling comment: Landin’s paper also predates Backus’ paper by about 10 years)

No idea how accurate it is, but Wikipedia says that ISWIM was influenced by Lisp...

Re: Lisp is not based on the Lambda Calculus

#99

Post by DonHopkins »

ProfHewitt wrote: post #93
kmill wrote: post #69

Earlier quoted context omitted.

Unlike lambda calculus, OO is not a specific mathematical formalism but rather a methodology and ontology for organizing a program. Lambda calculus, defined by Alonzo Church, is a kind of 'arithmetic' of abstract function manipulation devoid of semantics. It has some strong theoretical footing as, in modern language, reflexive objects in a category. > It's not clear to me why this makes Lisp not in the family of Lamb…

Object orientation derived from Simula-67 which was lexically scoped and preceded Sch3me by many years.

So Lisp 1, Lisp 2, Sch3me?

Re: Lisp is not based on the Lambda Calculus

#100

Post by quickthrower2 »

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.

Programming language grammars and spoken language grammars are two completely separate things. Someone can conceivably be a great programming language researcher who sometimes get's a rule of the English language wrong in a sentence.
Post reply on HN