Live data from Hacker News

Lisp is not based on the Lambda Calculus

danielsz.github.io

111–120 of 138 posts

Re: Lisp is not based on the Lambda Calculus

#111
post #107

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

Could you elaborate? A bit searching throws up some very interesting stuff but AFAICS a transducer is roughly comparable to a partial function, which doesn't relate to my request for manual expression manipulation support.

If I'm missing something, please say.

Re: Lisp is not based on the Lambda Calculus

#112

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?

If you look up a definition of lexical scope, you'll typically see something like this (from https://en.wikipedia.org/wiki/Scope_(computer_science)#Lexic... but others are similar).

"With lexical scope, a name always refers to its (more or less) local lexical environment. This is a property of the program text..."

So as local lexical environment isa property of the program text, lexical scope is explicit in the language's syntax.

Re: Lisp is not based on the Lambda Calculus

#113
post #108

Earlier quoted context omitted.

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

P.S

Goldreich demonstrates the problem by showing that our abstractions of electrical circuits don't in themselves preclude circuits that violate computational complexity results or even decide halting, but that alone is insufficient to show that such circuits can actually be built.

There are certain formalisms that make this kind of error harder to spot: actor formalisms make it easy to hide impossible "computation" in a collaborator; some typed formalisms could hide computation in the syntax (which requires a lot or even infinite computation to decide).

Re: Lisp is not based on the Lambda Calculus

#114
post #5

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

there are many lambda calculi.

Here's two:

A) Pure Lambda Calculus is defined by

1. the terms (metavariables t and u): λx.t | x | (t u)

2. the reduction rules, β

3. the two conversion rules, α and η

B) Another of Church's lambda calculus, defined by

1. the terms (metavariables t and u): λx.t | x | (t u)

2. the reduction rule, β

3. the conversion rule, α.

You might go .. wait, these are the same! They are not. Without the η rule, you cannot define extensional equivalence, thus you cannot do things like referential transparency.

There are a number of shortcomings with the pure lambda calculus of course, so over the years people have added things , creating variations of lambda calculi.

A particularly famous one is System F. System F extends the Simply Typed Lambda Calculus (which itself is an extension of the pure lambda calculus) with type generators and eliminators. The trick is to make the language of types into terms of the lambda calculus itself.

System F begets SML, SML(NJ), Ocaml, Haskell and F#.

Then you have the other extensions along Barendregt's Lambda Cube. You get things like Coq and Agda and Idris, which are extensions of System F in the same directions but different ways of constructing them.

On the other side of things people are trying to make sense of the pure lambda calculus itself. There exists a whole subindustry of people explaining substitutions (lambda calculi with explicit substitution), people explaining self interpretation which you can do in lisp but not really in pure lambda calculus (first clean attempt was in 1995!). There are people developing or splitting pure lambda calculus into two subsets - example are people who work with sequent calculus.

All these systems are lambda calculi. When people say _the_ lambda calculus then they usually mean the pure lambda calculus.

Re: Lisp is not based on the Lambda Calculus

#115
post #86

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…

The article referenced presents a strongly-typed proof that the halting problem is compurationally undecidable. Nevertheless, Actors can perform computations impossible on a nondeterministic Turing Machine.

Re: Lisp is not based on the Lambda Calculus

#116
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…

The article referenced presents a strongly-typed proof that the halting problem is compurationally undecidable. Nevertheless, Actors can perform computations impossible on a nondeterministic Turing Machine.

If they can, you haven't shown that. The "computation" you present is not just the actor's behavior, but the behavior of a combined actor-collaborator system (the collaborator is whatever it is that sends the actor messages). This system presents "super-Turing" behavior iff the collaborator is super-Turing. You haven't shown such a collaborator, that can reliably emit a `stop` command after an arbitrary number of `go`s, can exist. It's always possible that the scientific consensus is wrong, but that requires proof, and the "proof" in the paper isn't one.

Re: Lisp is not based on the Lambda Calculus

#117
post #116

Earlier quoted context omitted.

The article referenced presents a strongly-typed proof that the halting problem is compurationally undecidable. Nevertheless, Actors can perform computations impossible on a nondeterministic Turing Machine.

If they can, you haven't shown that. The "computation" you present is not just the actor's behavior, but the behavior of a combined actor-collaborator system (the collaborator is whatever it is that sends the actor messages). This system presents "super-Turing" behavior iff the collaborator is super-Turing. You haven't shown such a collaborator, that can reliably emit a `stop` command after an arbitrary number of `go…

There is no "collaborator" in the Actor computation that Plotkin:s proof shows cannot be preformed by a nondeterministic Turing Machine.

Re: Lisp is not based on the Lambda Calculus

#118
post #108

Earlier quoted context omitted.

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

A thesis in the referenced article is that the Actor model formalizes digital computation.

Re: Lisp is not based on the Lambda Calculus

#119
post #116

Earlier quoted context omitted.

If they can, you haven't shown that. The "computation" you present is not just the actor's behavior, but the behavior of a combined actor-collaborator system (the collaborator is whatever it is that sends the actor messages). This system presents "super-Turing" behavior iff the collaborator is super-Turing. You haven't shown such a collaborator, that can reliably emit a `stop` command after an arbitrary number of `go…

There is no "collaborator" in the Actor computation that Plotkin:s proof shows cannot be preformed by a nondeterministic Turing Machine.

Yes, there is. The "computation" of the actor (really, actor-collaborator) relies on something that can reliably emit a `stop` after an arbitrary number of `go`s. Please show that something can actually do that, and I'll show you a TM that can do the same. It's easy to describe non-computable behaviors; the difficulty is demonstrating that there are actual physical systems that can carry them out.

Re: Lisp is not based on the Lambda Calculus

#120

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…

The following article has a critique of Erlang as an Actor language:

https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3418003

Post reply on HN