Evaluating Expressions, part 6 – Actor Primitives

In part 6 of our series implementing programming language constructs with actors, we explore meta-circular definition of imperative actor primitives. We have now moved beyond expressions which yield values, and focus on statements which cause effects. The constructs explored here are the heart of any actor-based system.

In order to support actor primitive statements, our language grammar is extended from part 5 as follows:

repl  ::= <stmt>+;
block ::= '[' <stmt>* ']';
stmt  ::= 'LET' <eqtn>
        | 'SEND' <expr> 'TO' <expr>
        | 'CREATE' <ident> 'WITH' <expr>
        | 'BECOME' <expr>
        | <expr>;
...
const ::= <block>
        | 'SELF'
        | ...

SEND statement

The SEND statement sends a message to an actor. The effect of sending is delegated to a sponsor. This allows the configuration, via the sponsor, to monitor and control resource usage.

LET send_stmt_beh(m_expr, a_expr) = \(cust, #exec, env, sponsor).[
	CREATE call WITH call_pair_beh(m_expr, a_expr)
	SEND (k_send, #eval, env) TO call
	CREATE k_send WITH \(msg, to).[
		SEND (cust, #send, msg, to) TO sponsor
	]
]

When send_stmt_beh receives an #exec request, it creates a call (defined in part 3) to evaluate the message expression m_expr and the actor expression a_expr. The customer for the call k_send receives the message msg and the target actor to and forwards them in a #send request to the sponsor.

Introducing the “sponsor” concept requires a change to the protocol of statements, adding the sponsor to the #exec request. To account for this, the LET statment from part 5 is modified as shown.

LET let_stmt_beh(eqtn) = \(cust, #exec, env, sponsor).[
	SEND (k_env, #unify, env) TO eqtn
	CREATE k_env WITH \env'.[
		CASE env' OF
		? : [ SEND #fail TO cust ]
		_ : [ SEND #ok TO cust ]
		END
	]
]

The LET statement currently makes no use of the sponsor.

CREATE statement

The CREATE statement creates a new actor and binds the actor’s identity to an identifier. As with SEND, the sponsor controls the actual resource allocation.

LET create_stmt_beh(ident, expr) = \(cust, #exec, env, sponsor).[
	SEND (k_create, #new) TO sponsor
	CREATE k_create WITH \actor.[
		SEND (SELF, #bind, ident, actor) TO env
		BECOME \env'.[
			SEND (SELF, #eval, env') TO expr
			BECOME \beh_fn.[
				SEND (cust, beh_fn, env') TO actor
			]
		]
	]
]

When create_stmt_beh receives an #exec request, is sends a #new request to sponsor. The customer k_create receives the newly-created actor and sends a #bind request to bind actor to ident in the environment env. The customer for the #bind request is the new behavior of k_create, which receives the extended environment env’ and sends an #eval request to evaluate the behavior expression expr in the extended environment env’. The customer for the #exec request is the subsequent behavior of k_create, which receives the behavior function beh_fn and initializes the actor with the behavior function beh_fn and the extended environment env’. The initialized actor responds to the original customer cust.

Sponsor

The sponsor controls allocation of resources, specifically new actor creation and new message sends.

LET sponsor_beh(monitor) = \(cust, req).[
	CASE req OF
	(#send, msg, target) : [
		SEND (monitor, SELF, msg) TO target
		SEND #ok TO cust
	]
	#new : [  # create uninitialized actor for early name-binding
		CREATE actor WITH new_actor_beh
		SEND actor TO cust
	]
	END
]

When sponsor_beh receives a #send request, it immediately sends the message msg to the target target, and responds with an #ok to the customer cust. This immediate send will not cause re-entrance, even if the target is SELF, because (as we shall see later) each actor is protected by a serializer.

When sponsor_beh receives a #new request, it creates a new uninitialized actor and sends it to the customer cust.

An uninitialized actor expects to receive its initial behavior and environment.

LET new_actor_beh = \(cust, beh_fn, env).[
	BECOME actor_beh(beh_fn, env)
	SEND #ok TO cust
]

When new_actor_beh receives its initial behavior beh_fn and environment env, it becomes initialized and sends #ok to the customer cust. Figure 1 illustrates the message flow involved in creating a new actor.

Actor Creation Message Flow

Figure 1 - Actor Creation Message Flow

Actor behavior

The behavior of an actor is represented by an actor that interacts with the configuration. A sponsor is provided so the actor can request resources. Since the actor can only process one message at a time, a serializer (described in “Composing Actors“) is used to protect the actor behavior.

LET actor_beh(beh_fn, env) = \msg.[
	CREATE self WITH self_beh(SELF, beh_fn, env)
	BECOME serializer_beh(self)
	SEND msg TO SELF
]

When actor_beh receives a message it creates a private self, becomes a serializer protecting self, and delegates the message to its own serialized behavior. Note that the public identity of the actor (which SELF will refer to) is the serializer.

The real work of handling messages is done by the private self, which carries a reference to the public self (the serializing wrapper). This behavior is a three-part state machine cycling through the states “ready for message”, “applying behavior function”, and “executing the behavior”.

LET self_beh(self, beh_fn, env) = \(cust, sponsor, msg).[
	SEND (SELF, #apply, msg) TO beh_fn
	BECOME \block.[
		CREATE env' WITH self_env_beh(self, env)
		SEND (SELF, #exec, env', sponsor) TO block
		BECOME \result.[
			BECOME self_beh(self, beh_fn, env)
			SEND result TO cust
		]
	]
]

When self_beh receives a message dispatch (consisting of a customer cust, a sponsor and a message msg), it first sends an #apply request to its behavior function beh_fn, applying the message msg. Then it becomes the customer for the #apply, which receives a statement block. It then sends an #exec message to block with an environment extended to resolve the public self. Then it becomes the customer for the #exec, which receives the result of the behavior execution. Finally it becomes its original behavior, ready to receive another message, and sends the result to the original customer cust.

Actor environment

When an actor’s behavior is executing, it does so in an environment which has a value for SELF (the public identity of the actor). This environment adds a #self request to the environment protocol.

LET self_env_beh(self, next) = \(cust, req).[
	CASE req OF
	#self : [ SEND self TO cust ]
	_ : [ SEND (cust, req) TO next ]
	END
]

When self_env_beh receives a #self request, it sends self to the customer cust. All other requests are forwarded on to the next actor in the environment chain.

When the SELF keyword appears in an expression, it generates a “self expression” which accesses the identity of the currently executing actor.

CREATE self_expr WITH \(cust, #eval, env).[
	SEND (cust, #self) TO env
]

When self_expr receives an #eval request, it sends a #self request to the environment env.

When the SELF keyword appears in an pattern, it generates a “self pattern” which matches the identity of the currently executing actor.

CREATE self_ptrn WITH \(cust, cmd, arg, env).[
	SEND (k_self, #self) TO env
	CREATE k_self WITH \self.[
		SEND (cust, cmd, arg, env) TO SELF
		BECOME const_ptrn_beh(self)
	]
]

When self_ptrn receives a message, it sends a #self request to the environment env. The customer k_self receives the identity of the currently executing actor self, and becomes a constant pattern which matches self. The original message is delegated to the constant pattern for matching.

Block statement

When an actor’s behavior function is applied to a message, it results in a block statement that represents the actions the actor will take in response to the message. The block establishes a dynamic environment for any bindings created by the statements. The statements are chained together and executed sequentially (parallel execution is described in part 7).

LET block_stmt_beh(stmt) = \(cust, #exec, env, sponsor).[
	CREATE env' WITH dynamic_env_beh(env)
	SEND (cust, #exec, env', sponsor) TO stmt
]

When block_stmt_beh receives an #exec request, it creates a dynamic environment env’ and uses that environment to send an #exec request to its statement stmt.

CREATE empty_stmt WITH \(cust, #exec, env, sponsor).[
	SEND #ok TO cust
]

The simplest form of statement is the (singleton) empty statement, which responds to #exec requests by sending #ok to the customer cust.

When multiple statements are included in a block, they are organized as a linear sequence of pairs.

LET stmt_pair_beh(h_stmt, t_stmt) = \(cust, #exec, env, sponsor).[
	SEND (k_exec, #exec, env, sponsor) TO h_stmt
	CREATE k_exec WITH \result.[
		CASE result OF
		#ok : [ SEND (cust, #exec, env, sponsor) TO t_stmt ]
		#fail : [ SEND #fail TO cust ]
		END
	]
]

When stmt_pair_beh receives an #exec request, it sends an #exec request to its head statement h_stmt. The customer for this request k_exec receives the result. If the result is #ok an #exec request is sent to the tail statement t_stmt. Otherwise #fail is sent to the customer cust.

BECOME statement

The BECOME statement designates a new behavior for handling subsequent messages to an actor. This is the only way to effect a state-change in an actor, since state is only observable as a change in behavior.

LET become_stmt_beh(expr) = \(cust, #exec, env, sponsor).[
	SEND (k_become, #eval, env) TO expr
	CREATE k_become WITH \beh_fn.[
		SEND beh_fn TO cust
	]
]

When become_stmt_beh receives an #exec request, it sends an #eval message to the behavior expression expr. The customer for this request k_become receives the behavior function beh_fn resulting from the evaluation and sends this abstraction (a closure) to the customer cust.

Now that a behavior function can be the result of executing a statement, we must modify the customer which handles combining the results of an execution chain.

LET stmt_pair_beh(h_stmt, t_stmt) = \(cust, #exec, env, sponsor).[
	SEND (k_exec, #exec, env, sponsor) TO h_stmt
	CREATE k_exec WITH \result.[
		CASE result OF
		#ok : [ SEND (cust, #exec, env, sponsor) TO t_stmt ]
		#fail : [ SEND #fail TO cust ]
		beh : [
			SEND (SELF, #exec. env, sponsor) TO t_stmt
			BECOME \result'.[
				CASE result' OF
				#ok : [ SEND beh TO cust ]
				_ : [ SEND #fail TO cust ]
				END
			]
		]
		END
	]
]

If result is not #ok or #fail, then it must be a behavior function generated by BECOME. If the result’ from executing the tail statement t_stmt is #ok then the behavior function beh is the result. Otherwise #fail is the result. Notice that only one BECOME is allowed in an actor’s behavior.

In order to effect the behavior replacement, the actor’s private self must be modified. If execution of the actor’s statement block results in a behavior function, that function is used to handle subsequent messages. Otherwise the actor’s original behavior function is used.

LET self_beh(self, beh_fn, env) = \(cust, sponsor, msg).[
	SEND (SELF, #apply, msg) TO beh_fn
	BECOME \block.[
		CREATE env' WITH self_env_beh(self, env)
		SEND (SELF, #exec, env', sponsor) TO block
		BECOME \result.[
			CASE result OF
			#fail : [
				BECOME self_beh(self, beh_fn, env)
				SEND #fail TO cust
			]
			#ok : [
				BECOME self_beh(self, beh_fn, env)
				SEND #ok TO cust
			]
			beh' : [
				BECOME self_beh(self, beh', env)
				SEND #ok TO cust
			]
			END
		]
	]
]

If result is #ok or #fail, the original behavior function beh_fn is used to handle subsequent messages and result is sent to the customer cust. Otherwise the new behavior function beh’ is used to handle subsequent messages and #ok is sent to cust.

Summary

In part 6 of our series implementing programming language constructs with actors, we explored meta-circular definition of SEND, CREATE and BECOME, the actor primitives. We’ve seen how a serialized actor behavior interacts with a sponsor to cause effects in the system. We’ve introduced blocks to capture groups of statements and provide a nested-scope environment for binding local variables. Blocks are values, subject to the same abstraction mechanism as all other functional values. Behaviors are invoked by applying a message to a behavior function, producing a block, which is then executed in an environment with access to SELF.

In part 7 we will convert sequential block execution to proper parallel execution. We will also introduce transactions and exception handling. For more discussion of actor primitive semantics, see “Deconstructing the Actor Model“.

This entry was posted in Uncategorized and tagged , , , , , , , , , , , . Bookmark the permalink. Post a comment or leave a trackback: Trackback URL.

2 Comments

  1. gray
    Posted 2010-11-22 at 1:10 am | Permalink

    hi, Dale
    thanks for those great post. and where can i get an runnable implementation of humus?

  2. Dale Schumacher
    Posted 2010-11-23 at 10:17 am | Permalink

    The versions of Humus I have running implement earlier versions of the language syntax. In addition, they exist in a proof-of-concept prototyping environment, so graceful handling of errors was not a priority. I’m making progress on a version that is appropriate for public consumption, but it’s not ready yet. If you’re interested in working with the prototype, and willing to work around the sharp edges, contact me via email. Thanks for your interest.

3 Trackbacks

  1. […] « Evaluating Expressions, part 4 – Pattern Equations Evaluating Expressions, part 6 – Actor Primitives » […]

  2. […] This post was mentioned on Twitter by Jonas Bonér, Dale Schumacher. Dale Schumacher said: Evaluating Expressions, part 6 – Actor Primitives (http://bit.ly/9KfHLI) Meta-circularity FTW! […]

  3. […] « Evaluating Expressions, part 6 – Actor Primitives […]

Post a Comment

Your email is never published nor shared. Required fields are marked *

*
*