Actors all the way down

Recently, there has been renewed interest in meta-circular interpreters. For example, see ActorScript, Fexpr the Ultimate Lambda, and Dale Schumacher's recent posts.

Here is the lambda calculus in ActorScript:

"lambda" id body ~~ eval(env) --> (argument) -->body.eval(Environment(id,argument, env))

Environment(id, value, env) ~~ lookup(id2) --> id=id2 ?~ true --> value ?? false --> env.lookup(id) ~?

Operator Operand ~~ eval(environment) --> Operator.eval(environment)(Operand.eval(environment))

Identifier ~~ eval(environment) --> environment.lookup(Identifier)

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.


Alan Kay comments on Fexpr the Ultimate Lambda:

Yep, this was the picture of “what Lisp was really about”, and the approach I took to do Smalltalk-72 (as the result of a hallway bet at Xerox PARC).

"eval" should be a message instead of a procedure

Note that implementation of the lambda calculus given above uses "eval" as a message and *not* as the procedure used in Lisp.

How SmallTalk-72 influenced the development of Actors is discussed in Actor Model of Computation: Scalable Robust Information Systems

Open, extensible composition models

Reminds me of Ian Piumarta's new TR, Open, extensible composition models (slides).

Simple functional languages like LISP are useful for explor-
ing novel semantics and composition mechanisms. That use-
fulness can be limited by the assumptions built into the
evaluator about the structure of data and the meaning of
expressions. These assumptions create difficulties when a
program introduces a composition mechanism that differs
substantially from the built-in mechanism of function ap-
plication. We explore how an evaluator can be constructed
to eliminate most built-in assumptions about meaning, and
show how new composition mechanisms can be introduced
easily and seamlessly into the language it evaluates.

Extensitibility using "eval" messages

To extend syntax and semantics, it's easier using "eval" messages than to try to use the type system.


I cited Piumarta's Maru in my opening paragraph. It would be interesting to experiment with an actor-based evaluator that takes a Maru-like strategy. If I understand it correctly, Maru associates "evaluators" and "applicators" with the type of the object in the operator position of a combination. This relationship is captured by:

eval(x; e) = apply(evaluators[type(x)]; cons(x; nil); e)
apply(f; a; e) = apply(applicators[type(f)]; cons(f; a); e)

Evaluators are equivalent to my "#eval" messages, which are interpreted in a type-specific way by the behavior of the receiving object/actor. Applicators are equivalent to my "#comb" messages, with type-specific behavior for interpreting combinations.

Using "eval" messages for extensibility

Why not just use "eval" messages as follows:

Eval(x, e) ~~ x.eval(e)

f "(" a ")" ~~ eval(e) --> f.eval(e)(a.eval(e))

Functional/Object-Oriented Operations

This seems to be a natural consequence of converting from representing operations in functional form to representing operations in object-oriented form, as I discussed here.

If I read your implementation correctly, it is essentially the same algorithm I started with in this article, where I cited your ActorScript as inspiration. That version implicitly uses eager evaluation (requiring special-forms for operatives) and strictly lexical scope (motivating a variety of mutable environment implementations).

The more recent Kernel-inspired evaluator is distinguished by building on the explict-evaluation strategy of Vau, and uses a single consistent implementation of environments with controlled mutability. The message-based evaluation, with explicit customers, also implicitly handles tail-calls appropriately, and introduces concurrency in both operand evaluation and parameter matching.

Actors as a foundation for funtional and imperative programming

Integrating functional and imperative programming using message passing is subtle. ActorScript attempts the integration along with logic programming (based on Direct Logic) as well!

In ActorScript, types play an important role in affording binary interfaces so that program defined symbols never have to be looked up at run-time, which is slow and error prone.

ActorScript implementation

I'm looking forward to seeing an implementation of ActorScript that I can play with. I'd love to try out some of your examples.

ActorScript implementation in progress

We're working on it :-)