It's Actors All The Way Down

One of the best ways to understand programming language constructs is to implement them. We will begin by implementing a simple, yet Turing-complete, functional expression language. In subsequent articles, we will extend this language with additional features. For now we will focus on just the “untyped” lambda calculus, augmented with constants.

The grammar for our expression language looks like this:

expr  ::= <const>
        | <ident>
        | '\' <ident> '.' <expr>
        | <expr> '(' <expr> ')';

The language consists of constants, (variable) identifiers, (lambda) abstractions and (function) applications. We will define actor behaviors for each kind of language element. In order to focus on the evaluation process, we will skip lexical analysis and parsing. We assume that a stream of text has been transformed into a group of actors with the appropriate behaviors. Evaluation is initiated by sending an #eval message that specifies a customer to receive the resulting value. Our evaluation protocol is based on Carl Hewitt’s ActorScript [1].

Constant

Strictly speaking, constants are not needed in pure lambda calculus. They can be replaced by bound variables. However, the implementation is greatly simplified if we support constant (or literal) values directly.

LET const_expr_beh(value) = \(cust, #eval, _).[
	SEND value TO cust
]

When a constant expression receives an #eval message, it simply sends its value to the customer cust. Constants ignore any additional context information sent with the #eval message. They are not dependent on the evaluation context.

Identifier

Variables are referenced by identifiers. Identifier expressions evaluate to the value bound to that identifier in the environment of the evaluation context.

LET ident_expr_beh(ident) = \(cust, #eval, env).[
	SEND (cust, ident) TO env
]

When an identifier expression receives an #eval message, it must ask the environment for the value bound to that identifier. The environment env is passed as the context of the #eval message. Note that the customer cust is also passed to the environment, so the environment can respond directly to the original customer.

Environment

So what is this environment that is passed as the evaluation context? Well, the initial case is extremely simple. It is the singleton “empty” environment.

CREATE empty_env WITH \(cust, _).[ SEND ? TO cust ]

The empty environment responds to all lookup requests by sending the “undefined” value to the customer.

When we want to provide an environment that contains bindings from identifiers to values, we create an actor for each binding. Each environment binding actor references a next environment. If the identifier in a binding does not match the lookup request, the request is passed on to the next. Naturally, the empty_env is the final element in this chain.

LET env_beh(ident, value, next) = \(cust, req).[
	CASE req OF
	$ident : [ SEND value TO cust ]
	_ : [ SEND (cust, req) TO next ]
	END
]

When an environment binding receives a lookup request, the identifier to match is req. If req matches the identifier ident in the binding, then the value of the binding is sent to the customer cust. Otherwise the request is delegated to the next environment in the scope chain.

Abstraction

Lambda abstraction captures an expression containing a variable for later substitution. Essentially this defines an anonymous function that is “closed” in the lexical scope of its definition. For our purposes, this is accomplished by simply capturing the environment in which the abstraction expression is evaluated.

LET abs_expr_beh(ident, body_expr) = \(cust, #eval, env).[
	SEND NEW closure_beh(ident, body_expr, env) TO cust
]

When an abstraction expression receives an #eval message, a new “closure” actor is created, capturing the evaluation environment env. This actor is the “value” of the abstraction expression, so it is sent to the customer.

A function/closure can be “applied” to an argument value. This binds the abstraction variable to the argument value and evaluates the body expression.

LET closure_beh(ident, body, env) = \(cust, #apply, arg).[
	CREATE env' WITH env_beh(ident, arg, env)
	SEND (cust, #eval, env') TO body
]

When a function/closure receives an #apply message, the captured environment env is extended with a new binding of the abstraction variable ident to the argument value arg. This extended environment env’ is sent as the context of an #eval message to the body expression. The result of this evaluation is sent to the customer cust.

Application

Finally, we consider function application. This is where the rubber meets the road in functional programming. An application expression evaluates two sub-expressions, one in “function” position and the other in “argument” position, and then “applies” the argument result to the function result. This is “eager” argument evaluation. We will defer exploring “lazy” argument evaluation for now.

LET app_expr_beh(abs_expr, arg_expr) = \(cust, #eval, env).[
	SEND (k_abs, #eval, env) TO abs_expr
	CREATE k_abs WITH \abs.[
		SEND (k_arg, #eval, env) TO arg_expr
		CREATE k_arg WITH \arg.[
			SEND (cust, #apply, arg) TO abs
		]
	]
]

When an application expression receives an #eval message, it begins creating a chain of actors to carry out the evaluation work. First, an #eval message is sent to the abstraction sub-expression abs_expr. The customer in this message k_abs receives the abstraction value and sends an #eval message to the argument sub-expression arg_expr. The customer in this message k_arg receives the argument value and sends an #apply message with the arg to the function/closure abs. The resulting value is sent to the original customer cust.

An Example

As an example, let’s trace the evaluation of (\x.x)(42), which is the identity function applied to the constant value 42. This example could be demonstrated with code like this:

# (\x.x)(42) -> 42
CREATE example WITH app_expr_beh(
	NEW abs_expr_beh(
		#x,
		NEW ident_expr_beh(#x)
	),
	NEW const_expr_beh(42)
)
SEND (println, #eval, empty_env) TO example

The result would be 42 printed on the console. Figure 1 shows the message flow involved in evaluating this expression.

Figure 1 – Evaluation Message Flow

Summary

With only a handful of actor behaviors, we’ve implemented an evaluator for a complete functional expression language. Even this simple language can be amazingly useful [2]. Evaluation is accomplished through the collaboration of a group of actors, each representing either some language construct or some element of the evaluation process. There is no central “evaluator” that processes some data structure. Instead the data and behavior are distributed among active processing elements.

In part 2 we will add a special form for conditional expressions. This will not increase the expressive power of the language. We already have a Turing-complete lambda calculus implementation. We will be adding features that increase convenience or improve efficiency.

References

[1]

C. Hewitt. ActorScript(TM): Industrial strength integration of local and nonlocal concurrency for Client-cloud Computing. ArXiv 0907.3330, 2009.

[2]

A. van Meulebrouck. Lambda Calculus. MacTech 7(5), 1991.