Implementing Actors in Kernel

Now is the time we come full-circle in our exploration of Kernel/Scheme/LISP and show how Actors can be implemented on this foundation. This should dispel the notion that Actors are just functions/procedures. Sure, when an Actor receives a message you could say that the message is “applied” to the Actor’s current behavior. In that sense, message reception is like function application. But when a message is sent, it does not directly invoke the behavior of the receiving Actor, and no value is returned to the sender. This asynchronous messaging, with fair delivery, is vital to expressing concurrency in the Actor Model.

The relationship between Actors and the Lambda Calculus has created considerable confusion and controversy over the years. As Gabriel and Steele described it [1,§4]:

Hewitt had noted that the actor model could capture the salient aspects of the lambda calculus; Scheme demonstrated that the lambda calculus captured nearly all salient aspects (excepting only side effects and synchronization) of the actor model.

While it is true that the Actor Model can implement Lambda Calculus, the reverse is not the case [2]. Moreover, side effects and synchronization have become critically important issues. Side effects (actually, effects in general) are modeled by changes in actor behaviors. Synchronization is handled by the atomic run-to-completion semantics of actor behaviors, and the asynchronous nature of messaging. Locality “laws” are respected by restricting changes to the currently-running actor, and restricting communication to known acquaintances.

Kernel provides a solid foundation on which we will build a simple implementation of the Actor primitives (CREATE, SEND and BECOME). Encapsulated types and first-class environments help express Actor semantics in a safe clean way. The introduction of asynchronous messaging, separating send and receive, is fundamental to understanding how Actors are different from functions/procedures. Actor message reception causes application of a combiner (behavior), but rather than producing a value, it produces effects in the form of Actor primitives.

Environment

Careful management of environments is key to our Kernel implementation of Actors. The meaning of symbolic references in Kernel expressions are entirely dependent on the environment in which they are evaluated [3,§3]. Actor behaviors are described by Kernel expressions. They have visibility into the environment in which they were defined (static scoping). In addition, they have visible bindings to SELF (the currently-running actor) and BECOME! (for changing their behavior). They do not have visibility into the environment from which a message is sent, nor do they know the identity of the sender.

Figure 1 – Environment Relationships

The operative $behavior serves a purpose similar to $lambda. It captures a message pattern, the behavior expression body, and the local environment where the behavior was defined. The configuration environment contains the queue of pending events, and the private combiners used to implement actors and behaviors as encapsulated types.

Configuration

A Configuration is an evolving collection of actors and events (messages in transit). The configuration environment exports the following symbols into the ground environment:

(CREATE behavior)
Create a new actor and specify its initial behavior.
(actor? . objects)
Return #t iff all objects are actors.
($behavior msg-ptrn . body)
Create a behavior that accepts messages matching msg-ptrn and executes the body expression.
(behavior? . objects)
Return #t iff all objects are behaviors.
(SEND! actor . message)
Queue an event which (asynchronously) delivers message to actor.
(RUN!)
Deliver queued events until there are no more events pending.

The Kernel $provide! operative creates an environment in which we define our configuration, and from which we export publicly-available Actor mechanisms.

($provide! (CREATE actor? $behavior behavior? SEND! RUN!)
	($define! (e-actor actor? d-actor) (make-encapsulation-type))
	($define! (e-beh behavior? d-beh) (make-encapsulation-type))
	($define! events (new-queue))
...

We use make-encapsulation-type to define two encapsulated data-types, one for actors and one for behaviors. Only the type predicates actor? and behavior? are exported. We also create an empty queue for events, using the object-oriented queue implementation shown previously.

...
	($define! CREATE
		($lambda (beh)
			($let ((actor (e-actor (cons () ()))))
				(set-beh! actor beh)
				actor)))
...

CREATE constructs a new encapsulated actor and assigns its initial behavior. The actor is represented internally as a single cons-cell. We have to set the behavior after the actor is created so that the actor environment can be created with a SELF binding that points to the actor. Finally, the newly created actor is returned.

...
	($define! get-beh-fn
		($lambda (actor)
			(car (d-actor actor))))
...

get-beh-fn takes an encapsulated actor and returns its current (raw) behavior function, which is stored in the car position of the cons-cell representation.

...
	($define! set-beh!
		($lambda (actor beh)
			(set-car!
				(d-actor actor)
				((d-beh beh) actor))))
...

set-beh! takes an encapsulated actor and an encapsulated behavior beh. The behavior is decapsulated and combined with the actor to produce a raw behavior function. This function is stored in the car position of the actor’s cons-cell representation.

...
	($define! $behavior
		($vau (msg-ptrn . body) env
			(e-beh ($lambda (actor)
				(eval
					(list* $lambda msg-ptrn body)
					(make-actor-env actor env))))))
...

$behavior is an operative that constructs a new encapsulated behavior. The behavior is represented internally by an applicative that, given an actor, will produce a raw behavior function. The raw behavior function matches an incoming message with msg-ptrn and evaluates the body in a specially-constructed environment.

...
	($define! make-actor-env
		($lambda (actor env)
			($let ((env (make-environment env)))
				($set! env SELF actor)
				($set! env BECOME!
					($lambda (beh)
						(set-beh! actor beh)))
				env)))
...

make-actor-env takes an actor and a local environment env. A new actor environment is created with env as its parent. The actor environment is populated with bindings for SELF and BECOME!, and then returned. SELF is a reference to the actor itself. BECOME! is an applicative that replaces the behavior of the actor.

...
	($define! SEND!
		($lambda (actor . message)
			($if (actor? actor)
				(queue-put! events (cons actor message))
				(d-actor actor))))  ; signal an error
...

SEND! takes a target actor and a message and creates a new event, which is added to the queue of pending events. If actor is not an actor, an error is signaled. This helps us catch errors at the point of creation, rather than when the event is dequeued for dispatch.

...
	($define! RUN!
		($lambda ()
			($if (queue-empty? events)
				#inert
				($sequence
					(dispatch! (queue-take! events))
					(RUN!)))))
...

RUN! checks the queue of events for a message to deliver. If the queue is empty, #inert is returned. Otherwise, an event is dequeued and delivered. After the delivery is completed, we make a tail-call to ourselves looking for additional events. Note that message delivery may have caused queuing of additional events, so this loop may never terminate. This mechanism requires proper tail-call semantics (which Kernel provides) to prevent stack overflow.

...
	($define! dispatch!
		($lambda ((actor . message))
			(apply (get-beh-fn actor) message))))

dispatch! delivers a single message to a target actor. The actor’s raw behavior function is extracted and applied to the message. The resulting behavior evaluation may perform any of the Actor primitives:

  • CREATE new actors
  • SEND! new messages (asynchronously)
  • BECOME! a new behavior (change state)

Delivery of a message is the unit of synchronization in an Actor system. Each behavior runs to completion, potentially triggering further computation via asynchronous messages. The “state” of an Actor is updated atomically by providing a new behavior for processing subsequent messages.

Example Usage

Let’s consider a few examples to show how our Kernel-based Actors work.

($define! sink_beh ($behavior #ignore))
($define! sink (CREATE sink_beh))

We first define sink_beh, a behavior which simply ignores any message it receives. Then we create a sink actor with sink_beh. Any messages sent to sink will be silently discarded.

($define! println
	(CREATE ($behavior (msg)
		(write msg)
		(newline))))

We can also create and use a behavior without giving it a name. Here we create a println actor with a behavior that writes any message received to the console (followed by a newline).

($define! tag_beh
	($lambda (cust)
		($behavior (msg)
			(SEND! cust (cons SELF msg))
			(BECOME! sink_beh))))
($define! tag
	(CREATE (tag_beh println)))

Often we would like to parameterize a behavior with information available at creation time, rather than just the information available in each message. This is easily accomplished by defining a behavior-generating function. tag_beh is a behavior-generating function that takes a customer cust and produces a behavior that sends cust the message msg prefixed with SELF, then takes on sink_beh to ignore subsequent messages. We create a tag actor with tag_beh parameterized with the customer println.

(SEND! sink 0)
(SEND! tag 1)
(SEND! tag 2)
(SEND! println 3)
(RUN!)

Now we exercise these actors by enqueuing a few messages and running the event-dispatch loop. The sink actor will ignore the message 0. The tag actor will receive either 1 or 2 (non-deterministically, in general) and send a new tagged message to println. After processing a single message, the tag actor will ignore any other messages received. The println actor will receive 3 and the message from tag (again, non-deterministically), printing each to the console as they arrive.

This Actor implementation uses an event queue to ensure fair delivery of messages, but there are other valid implementations. In general, message arrival order is non-deterministic, although message are guaranteed to be delivered eventually. In a distributed (or even multi-core) context, messages may be arbitrarily delayed in-transit.

Conclusion

We have demonstrated how a simple Actor system can be implemented in roughly a single page of Kernel code. Although delivery of a message to an actor uses the combiner-application mechanism, actors differ from functions/procedures in at least two important ways. First, actor behaviors are invoked via asynchronous message reception. Send and receive are decoupled, and no “return value” is produced. Second, an actor’s identity is separate from its behavior. The behavior of a given actor may change over time, and many actors may share the same behavior. Behavior-replacement models atomic state-change in an Actor system. It is my hope that this demonstration will help bring clarity to the historical confusion regarding the nature of Actors.

References

[1]
G. Steele and R. Gabriel. The Evolution of Lisp. History of Programming Languages, Volume 2. Edited by T. Bergin and R. Gibson. Addison-Wesley, 1996.
[2]
C. Hewitt. What is computation? Actor Model versus Turing’s Model. A COMPUTABLE UNIVERSE: Understanding Computation & Exploring Nature as Computation. Dedicated to the memory of Alan M. Turing on the 100th anniversary of his birth. Edited by H. Zenil. World Scientific Publishing Company, 2012.
[3]
J. Shutt. Revised-1 Report on the Kernel Programming Language. Technical report WPI-CS-TR-05-07, Worcester Polytechnic Institute, Worcester, MA, March 2005, amended 29 October 2009.

Special thanks to John Shutt for his guidance and assistance in this implementation.



Tags: , , , , , , , , , , ,
This entry was posted on Thursday, February 16th, 2012 at 10:12 pm and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Leave a Reply

Your comment