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…
Lisp is not based on the Lambda Calculus
121–130 of 138 posts
Re: Lisp is not based on the Lambda Calculus
#122Earlier 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.
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
#123The 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…
John McCarthy said that he never had the intention to realize the lambda calculus, but he followed that statement with the corollary that had someone "started out with that intention, he might have ended with something like LISP." Peter Landin was a pioneer in that regard. See "The Mechanical Evaluation of Expressions", published in 1964, and the SECD virtual machine. Machine interpreters like SECD and CEK may come close to a "realization" of the lambda calculus. Their design is directly inspired by its semantics. You don't necessarily end up with something like LISP, but you can, see Lispkit and LispMe.
Re: Lisp is not based on the Lambda Calculus
#124Earlier quoted context omitted.
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.
Googling a bit, it seems that McCarthy mentions this in "History of Lisp" [0], as a change from LISP 1 to LISP 1.5:
> In modern terminology, lexical scoping was wanted, and dynamic scoping was obtained. I must confess that I regarded this difficulty as just a bug and expressed confidence that Steve Russell would soon fix it. He did fix it but by inventing the so-called FUNARG device that took the lexical environment along with the functional argument. Similar difficulties later showed up in Algol 60, and Russell's turned out to be one of the more comprehensive solutions to the problem. While it worked well in the interpreter, comprehensiveness and speed seem to be opposed in compiled code, and this led to a succession of compromises. Unfortunately, time did not permit writing an appendix giving the history of the problem, and the interested reader is referred to (Moses 1970) as a place to start. (David Park tells me that Patrick Fischer also had a hand in developing the FUNARG device).
So I guess closures had been invented at least by 1962 (when the LISP 1.5 manual was published), but were not widely used because of performance considerations?
[0] http://www-formal.stanford.edu/jmc/history/lisp/node4.html
Re: Lisp is not based on the Lambda Calculus
#125Earlier quoted context omitted.
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
#126Re: Lisp is not based on the Lambda Calculus
#127Earlier quoted context omitted.
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").
Emacs Lisp is still dynamically scoped, no?
Since Emacs 24.1 (had to look up the version), it's been possible to enable lexical scope for a file or buffer. The default is still dynamic scope, and dynamic scope can be achieved even after enabling lexical scope with certain conditions.
Re: Lisp is not based on the Lambda Calculus
#128Earlier quoted context omitted.
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.
The Actor (which cannot be implemented by a nondeterministic TM) sends the 'stop' message to itself. However, just as there can be an arbitrarily long amount of time between two steps of a computation, there can be a arbitrarily long amount of time for a message to be delivered.
As you now describe it, it cannot be implemented (physically realized) at all. Or, conversely, any physically implementable refinement of it (which will not exhibit the entire range of behaviors) will be simulatable by a TM.
There are many abstract machines that cannot be implemented by TMs -- e.g. various oracle TMs. There is nothing special, surprising or new about that.
There are many formalisms that are more or less convenient abstractions for various kinds of systems. There is nothing special, surprising or new about that, either. In fact, some formalisms that can describe non-computable behaviors are commonly used to specify either software or hardware as they're convenient (like Lamport's TLA).
But you're making a claim about the Church-Turing thesis, which, as commonly interpreted today (as the physical Church-Turing thesis), is the claim that any mechanism that can be implemented by a physical mechanism can be simulated by a TM. Unless you show how to build a physical system that cannot be simulated by a TM, your claim is no refutation of the thesis; it has nothing to do with it. Your claim that arbiters in digital circuits cannot be simulated has not been established and is not recognized by scientific consensus.
> However, just as there can be an arbitrarily long amount of time between two steps of a computation, there can be a arbitrarily long amount of time for a message to be delivered.
This is a completely different use of "arbitrary". In TMs, the fact that an arbitrary amount of time can pass between steps means that any device, with any finite amount of time between steps, can produce the full range of TM behaviors. In your actor case, to get non-computable behavior, you need to show that the device can delay the message by every amount of time. You need to show that such a physical device can exist.
Put simply, it's one thing to propose a non-computable abstraction that's convenient to model some systems, and another thing altogether to claim that there are realizable physical systems that cannot be simulated by a Turing machine. The former is useful but mundane (in fact, all of classical analysis falls in this category); the latter has not been achieved to date.
Re: Lisp is not based on the Lambda Calculus
#129Earlier quoted context omitted.
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.