In Actor Model of Computation: Scalable Robust Information Systems, arXiv:1008.1459, Hewitt writes, at p 7 that “lambda calculus cannot implement concurrency”. At p.13-14 he writes:
… the semantics of the lambda calculus were expressed using variable substitution in which the values of parameters were substituted into the body of an invoked lambda expression. The substitution model is unsuitable for concurrency because it does not allow the capability of sharing of changing resources.
Correct. However, the graphic lambda calculus does not have this problem because reductions don’t need evaluations. See The graphic beta move, with details to understand this better.
All the arguments listed further apply also verbatim to graphic lambda calculus! (Hewitt loc cit, p. 14)
Inspired by the lambda calculus, the interpreter for the programming language Lisp [McCarthy et. al. 1962] made use of a data structure called an environment so that the values of parameters did not have to be substituted into the body of an invoked lambda expression.
Note that in the definition in ActorScript [Hewitt 2011] of the lambda-calculus below:
- All operations are local.
- The definition is modular in that each lambda calculus programming language construct is an Actor.
- The definition is easily extensible since it is easy to add additional programming language constructs.The definition is easily operationalized into efficient concurrent implementations. The definition easily fits into more general concurrent computational frameworks for many-core and distributed computation.
That Actors which behave like mathematical functions exactly correspond with those definable in the lambda calculus provides an intuitive justification for the rules of the lambda calculus:
- Lambda identifiers: each identifier is bound to the address of an Actor. The rules for free and bound identifiers correspond to the Actor rules for addresses.
- Beta reduction: each beta reduction corresponds to an Actor receiving a message. Instead of performing substitution, an Actor receives addresses of its arguments.
Further I try to understand this, as a particular case of the Chemical actors sketch.
We have Actors, we have addresses and we have lambda identifiers (it’s about usual lambda calculus, not the better graphic lambda calculus). The idea, as far as I understand, is to “bound” lambda identifiers to the address of an Actor. The second idea is “each beta reduction corresponds to an Actor receiving a message”.
I want a way to identify Actors with graphs in or with molecules in , if I wish to use the chemlambda. Actually, because, after some thinking, is better to think about Actors as if they are a sort of decoration of the arrows of a graph, almost like a decoration with types. (I shall not use the epsilon gates further, just concentrating on the pure logic side)
We shall have actors A, B, etc, with actor names :A. :B. There are other names, like which is a placeholder for indetermination (that’s just a name, if you don’t like this one then change it with 😕 , or whatever), there is also :talk and :listen names. These are not names of actors.
By using these rules we can decorate all half-arrows (meaning that we may have arrows with two decorations. For concreteness, look at the example of the combinator K.
I shall take another Actor named A and make it interact with the Actor K, in order to mimick the couple of reductions.
Here “1” and “2” mean anything you want, from “they can be names of actors” to “I don’t care what follows next”.
Now, they are in position to communicate:
What happens next? The :listen:talk decoration indicates that a graphic beta reduction can be applied (cf. Hewitt 2nd suggestion). But we need a rule for decorations with names before and after the graphic beta move. Here is what I propose:
We apply this for our example:
Is that nice or what? The actor K lost one of it’s “lambda identifiers”, the actor A also simplified a bit, but they still talk one to another:
Remark that graphic lambda calculus easily did what Hewitt wants. This example is not showing any concurrency, though, because here there is no concurrency involved, properly speaking. I only wanted to implement the 2 suggestions of Hewitt with graphic lambda calculus. But take examples where concurrency does appear, like here, to see that everything works really nice. This will be explained in another post.