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

71–80 of 138 posts

Re: Lisp is not based on the Lambda Calculus

#71

Post by kmill »

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…

Wow, that is an impressive survey --- thanks for putting that together!

Re: Lisp is not based on the Lambda Calculus

#72

Post by bontaq »

tempguy9999 wrote: post #58

This is not relevant directly to the subject but perhaps someone in formal langs can help me. I'm interested in optimisation of (necessarily) pure functional langs. Starting with deforesting (the elimination of intermediate structures) eg. map(f, map(g, list(1, 2, 3))) can be optimised trivially by a human to map(f.g, list(1, 2, 3)) (where f.g is functional composition) but I want to do this automatically, and the fi…

You could use uniplate and a small AST to play more with it, the paper has examples of transformations

the paper: https://ndmitchell.com/downloads/paper-uniform_boilerplate_a...

small tutorial: https://www.cs.york.ac.uk/fp/darcs/uniplate/uniplate.htm

Re: Lisp is not based on the Lambda Calculus

#73

Post by Cybiote »

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…

Adding a little to your wonderful post, another possibility for why the conflation of the original lisp as based on the lambda calculus is that its notation was heavily inspired by the lambda calculus, even though it was more properly a refinement of the μ-recursive functions (of form f:(N,N,...N) -> N) over the natural numbers.

While a lot of people are trying to defend the lambda calculus as a basis, I think this actually undersells the significance of LISP. Apart from Lisp the language family and its implementations, there is Lisp, (arguably) the first practically realizable mathematical model of computation. That is, it stands on its own as a model for computation†, continuing along a long line of which I think Grassmann's 1861 work on arithmetic and induction is a good starting point.

Turing Machines are intuitive and the lambda calculus is subtle and expressive, but Lisp's contribution was to place partial recursive function on a more intuitive/realizable basis in terms of simple building blocks of partial functions, predicates, conditional expressions and symbolic expressions (ordered pairs/lists of atomic symbols). Lambdas come in as a notation for functions with a modification to facilitate recursive definitions.

†Making Greenspun's Tenth Rule trivially true.

Re: Lisp is not based on the Lambda Calculus

#74

Post by tempguy9999 »

carapace wrote: post #67
tempguy9999 wrote: post #63

Earlier quoted context omitted.

I dunno. I thought the foundations were laid in mathematics considerably pre computer. eg. from wiki's page on haskell curry: " The focus of Curry's work were attempts to show that combinatory logic could provide a foundation for mathematics. (edit: accidentally stripped the part here mentioned that was in 1933 ie. very pre-computer) [...]. The paradox, developed by Rosser and Stephen Kleene, had proved the inconsist…

You reminded me of one of my favorite jokes: "Computer Science could be called the post-Turing decline in the study of formal systems." (I dunno who said it. Maybe Dijkstra.)

That is funny. But you could also restate that as "computer science could be called the post-turing mass commercialisation of formal systems" cos AFAIK being a pure mathematician was never a path to wealth.

Come to think of it, still isn't so here's one in return

Q. What's the difference between a mathematician and a large pizza?

A. A large pizza can feed a family of four.

Re: Lisp is not based on the Lambda Calculus

#75

Post by cat199 »

qubex wrote: post #52
foldr wrote: post #47

Earlier quoted context omitted.

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

When I was taught English it was most definitely frowned upon and disparaged as “at best an Americanism”. It is grating to the native British ear and has no place in formal writings. There is no situation where it cannot be avoided by rephrasing the sentence (usually, by no more than employing “will be going”, but occasionally resorting to other constructs). During the IB we were absolutely forbidden from using it an…

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

example #1 from a clearly educated british person:

'i was going to go' (yes, no negation, but still..)

agree, this is not formal language, but quite common.

Re: Lisp is not based on the Lambda Calculus

#76

Post by vilhelm_s »

aap_ wrote: post #64
btilly wrote: post #38

Earlier quoted context omitted.

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…

LISP 1.5 as described in the manual implements lexical scope, at least in the interpreter. I haven't studied the compiler too closely, I think there dynamic scope is more prevalent, but as far as I know it has lexical scope as well.

Where do you see that?

Looking at the "Universal LISP function" on page 13 in [0], the case for apply/LAMBDA just extends the current environment a with the arguments of the lambda, but it doesn't unpack a closure to get the environment the lambda function was defined in, so it implements the dynamic version. (Unlike, e.g., the interpreter in SICP [1].)

[0] http://www.softwarepreservation.org/projects/LISP/book/LISP%... [1] https://mitpress.mit.edu/sites/default/files/sicp/full-text/...

Re: Lisp is not based on the Lambda Calculus

#77

Post by ozmaverick72 »

Isamu wrote: post #24
pankajdoharey wrote: post #12

It is entirely possible to realise Lambda calculus using lisp. But McCarthy not understanding it is surprising.

>McCarthy not understanding it is surprising. I think he is commenting on the subtleties of it. I think many reading here will say they understand it or have studied it in a course but I am not so sure everyone gets the subtle points. Myself I have always puzzled over the difference between what programmers call LC and what seems to be discussed by Church.

I understand that Turing and Church came up with different approaches to describing the fundamentals of computing. You can see there is a relationship between LC and LISP. My question is how did we get to the von Neumann architecture and CPU instruction sets from either Church or Turing's work ?

Re: Lisp is not based on the Lambda Calculus

#78

Post by ptrott2017 »

phkahler wrote: post #30
danharaj wrote: post #29

Earlier quoted context omitted.

Because he was certainly aware of the literature and he was a top notch scholar. Your follow-up questions seem to be implying something, care to spell it out for me?

But was he top notch back then? He's most well known for "creating" Lisp. And I put that in quotes because he never meant for anyone to implement it on a real machine.

re:was he top notch? By 1955 he was an assistant professor of Mathematics and known in his field. In 1956 he organised the Dartmouth conference where the field of Artificial Intellgence - got its name. He was a peer of Claude Channon, Marvin Minsky and Nathanial Rochester - so yes he was top notch. YC audience knows him for Lisp - but he was known for a lot more in his fields of research.

Re: Lisp is not based on the Lambda Calculus

#79

Post by cannabis_sam »

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)

Re: Lisp is not based on the Lambda Calculus

#80

Post by carlehewitt »

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…

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 more powerful than lambdas with mutable environments.

Post reply on HN