Lisp is not based on the Lambda Calculus • Hacker News Board

Re: Lisp is not based on the Lambda Calculus

#101

Post by DonHopkins » Thu, Aug 15, 2019, 4:29 AM UTC

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…

So Lambda isn't the Ultimate Law of Nature, but Lambda isn't the Ultimate Scam either.

https://softwareengineering.stackexchange.com/questions/1076...

Re: Lisp is not based on the Lambda Calculus

#102

Post by namelosw » Thu, Aug 15, 2019, 4:36 AM UTC

The problem is like 'is Erlang an Actor language?'. The answer is yes.

Carl Hewitt developed the Actor model based on Smalltalk in the 1970s.

Joe Armstrong created Erlang in the 1980s, which he didn't know the Actor model at all at that time. Erlang doesn't even have the concept of Actor, it accidentally implemented Actor model by the elegant design of processes.

But when it comes to the Actor model nowadays, Erlang is basically a must-mention language, although the intention wasn't about Actor.

Re: Lisp is not based on the Lambda Calculus

#103

Post by jasonhansel » Thu, Aug 15, 2019, 4:37 AM UTC

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.

Question: if lexical scopes are in the language's data structures, but can't be explicitly created or made visible in the language's syntax, is it still homoiconic?

Re: Lisp is not based on the Lambda Calculus

#104

Post by cannabis_sam » Thu, Aug 15, 2019, 4:55 AM UTC

didibus wrote: post #98

cannabis_sam wrote: post #79

Earlier quoted context omitted.

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

That is correct.

From Landin’s paper:

6. Relationship to LISP

ISWIM can be looked on as an attempt to deliver LISP from its eponymous commitment to lists, its reputation for hand-to-mouth storage allocation, the hardware dependent flavor of its pedagogy, its heavy bracketing, and its compromises with tradition.

Re: Lisp is not based on the Lambda Calculus

#105

Post by fourthark » Thu, Aug 15, 2019, 5:53 AM UTC

jasonhansel wrote: post #103

vilhelm_s wrote: post #33

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.

Question: if lexical scopes are in the language's data structures, but can't be explicitly created or made visible in the language's syntax, is it still homoiconic?

Aren't lexical scopes visible in the language's syntax?

Re: Lisp is not based on the Lambda Calculus

#106

Post by edflsafoiewq » Thu, Aug 15, 2019, 7:31 AM UTC

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

x y z means (x y) z by definition, so there's only one way to reduce that expression.

Re: Lisp is not based on the Lambda Calculus

#107

Post by wvlia5 » Thu, Aug 15, 2019, 8:00 AM UTC

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…

Sounds like you are in need of transducers

Re: Lisp is not based on the Lambda Calculus

#108

Post by pron » Thu, Aug 15, 2019, 8:27 AM UTC

ProfHewitt wrote: post #95

pron wrote: post #86

Earlier quoted context omitted.

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.

That is a strong assertion that requires proof. The consensus view is that there aren't. For example, one could claim that a TM couldn't simulate a coin flip as it cannot simulate true randomness, but this assumes that the coin flip is "truly" random without establishing it (which would be hard because of pseudorandomness). Or, in the case of arbiters, you could claim that the arbiter behaves like the magical collaborator in the stop/go examples, converting two analog inputs to a binary decision that takes an arbitrarily long time, but this only introduces yet another magical collaborator capable of producing analog inputs that are equal to arbitrary precision.

This is a common problem when we appeal to continuous natural phenomena, as their common description is usually a convenient, but imprecise, abstraction. Goldreich addressed this in On the philosophical basis of computational theories [1]: "A computational model cannot be justified by merely asserting that it is consistent with some theory of natural phenomena ... The source of trouble is the implicit postulate that asserts that whatever is not forbidden explicitly by the relevant electrical theories, can actually be implemented"[2]

[1]: http://www.wisdom.weizmann.ac.il/~oded/VO/qc-fable.pdf

[2]: He adds "at no cost" because his focus is complexity, not computability

Re: Lisp is not based on the Lambda Calculus

#109

Post by tempguy9999 » Thu, Aug 15, 2019, 8:42 AM UTC

bontaq wrote: post #72

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

This seems (AFAICT) a bit higher what I'm after, but very interesting nonetheless, I'll have a play, thanks.

Re: Lisp is not based on the Lambda Calculus

#110

Post by aap_ » Thu, Aug 15, 2019, 8:51 AM UTC

vilhelm_s wrote: post #76

aap_ wrote: post #64

Earlier quoted context omitted.

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%…

The one on page 13 is not what LISP 1.5 does, that's more of an earlier purer idea. I meant the one on page 70 where FUNCTION packs a fucking together with its environment into a FUNARG closure, which when applied unpacks the environment it was created with.