It's Actors All The Way Down

In part 3 of our series implementing programming language constructs with actors, we explore parallel evaluation of sub-expressions and introduce pairs. Pairs allow the construction of tuples, generalizing structured multi-part patterns and values.

In order to support pair expressions and patterns, we’ve refactored the grammar from part 2 to separate out literal constants expressions and introduce additional syntax for ‘,‘ the pairing operator and grouping with ‘(‘ and ‘)‘. The resulting grammar looks like this:

expr  ::= <term> ',' <expr>
        | <term>;
term  ::= <const>
        | <ident>
        | <term> '(' <expr>? ')'
        | 'CASE' <expr> 'OF' {<ptrn> ':' <expr>}+ 'END'
        | '(' <expr>? ')';
ptrn  ::= <pterm> ',' <ptrn>
        | <pterm>;
pterm ::= '_'
        | <const>
        | <ident>
        | '$' <term>
        | '(' <ptrn>? ')';

You may notice that the rules involving ‘,‘ are right-recursive. This means that pair expressions (and patterns) group from right-to-left. The expression (a, b, c) is equivalent to (a, (b, c)). This is important for understanding how partial matches are handled. However, before we examine the interpretation of pairs, let’s look at parallel evaluation in applications like f(x).

Parallel Application

Application expressions from part 1 were represented like this:

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
		]
	]
]

The abstraction (first expression) was evaluated first, then the argument (second expression), then the argument was “applied” to the abstraction. Since our language is free of side-effects, we can safely evaluate both the abstraction expression and the argument expression in parallel, then carry out the application step with the resulting values. Of course, we still must keep track of which value is the abstraction and which is the argument. With this in mind, our parallel application expression can be represented like this:

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

Both the abstraction expression abs_expr and the argument expression arg_expr are sent #eval messages, but with distinct customers. The customers k_abs and k_arg are dynamically-created actors which tag messages with their own identity before sending them on the join. The join actor is also dynamically-created, and given the identities of both #eval customers, and a customer of its own. The join customer k_app receives an ordered pair of values resulting from evaluation of each expression, and sends an #apply message just like the original behavior.

LET tag_beh(cust) = \msg.[ SEND (SELF, msg) TO cust ]

As mentioned earlier, tag_beh simply adds its own identity as a “tag” on the front of any message it receives. Then it sends this tagged message on to its pre-defined customer cust. This allows us to uniquely identify particular messages as coming from a specific source because the identity of a tag actor is only known (initially) to the actor that created it.

A join actor uses tagged messages to distinguish between a pair of response sources. It waits until both responses arrive and then passes the ordered pair of response values on to the final customer.

LET join_beh(cust, k_first, k_rest) = \msg.[
	CASE msg OF
	($k_first, first) : [
		BECOME \($k_rest, rest).[
			SEND (first, rest) TO cust
		]
	]
	($k_rest, rest) : [
		BECOME \($k_first, first).[
			SEND (first, rest) TO cust
		]
	]
	END
]

When join_beh receives a message, it matches the prefix against each of the tags k_first and k_rest. Based on which tag matches, the actor’s behavior changes to expect the other tagged value. Once both tagged values are received, the ordered pair of values (first, rest) is sent to the join customer cust.

Figure 1 illustrates the process of evaluating a parallel application expression.

Figure 1 – Evaluating a Parallel Application

Pair Expression

A pair expression produces an ordered pair of values from an ordered pair of expressions. Like the application expression, the two sub-expressions of a pair expression can be evaluated in parallel.

LET pair_expr_beh(head_expr, tail_expr) = \(cust, #eval, env).[
	SEND (k_head, #eval, env) TO head_expr
	SEND (k_tail, #eval, env) TO tail_expr
	CREATE k_head WITH tag_beh(join)
	CREATE k_tail WITH tag_beh(join)
	CREATE join WITH join_beh(cust, k_head, k_tail)
]

Notice how pair_expr_beh is almost the same as par_app_expr_beh (described above). In fact, pair_expr_beh is slightly less complicated because it doesn’t have to perform the “apply” step, only return the result value pair. Based on this observation, we can extract the commonality between par_app_expr_beh and pair_expr_beh into a new generalized behavior.

The “call” behavior encapsulates the process of sending the same request to an ordered pair of actors and collecting an ordered pair of responses.

LET call_pair_beh(head, tail) = \(cust, req).[
	SEND (k_head, req) TO head
	SEND (k_tail, req) TO tail
	CREATE k_head WITH tag_beh(join)
	CREATE k_tail WITH tag_beh(join)
	CREATE join WITH join_beh(cust, k_head, k_tail)
]

Now we can refactor pair_expr_beh to use call_pair_beh.

# refactored...
LET pair_expr_beh(head_expr, tail_expr) = \(cust, #eval, env).[
	CREATE call WITH call_pair_beh(head_expr, tail_expr)
	BECOME \(cust, #eval, env).[
		SEND (cust, #eval, env) TO call
	]
	SEND (cust, #eval, env) TO SELF
]

This behavior uses a private initialization technique to create a call actor and then replace its own behavior with one that forwards all properly-formed messages on to call. This way we can enforce that only #eval messages are allowed, while using a more generic behavior under the covers.

Similarly, we can refactor par_app_expr_beh to use call_pair_beh.

# refactored...
LET par_app_expr_beh(abs_expr, arg_expr) = \(cust, #eval, env).[
	CREATE call WITH call_pair_beh(abs_expr, arg_expr)
	BECOME \(cust, #eval, env).[
		SEND (k_app, #eval, env) TO call
		CREATE k_app WITH \(abs, arg).[
			SEND (cust, #apply, arg) TO abs
		]
	]
	SEND (cust, #eval, env) TO SELF
]

Again, a private call actor is created to do most of the work, but once the (abs, arg) value is available, we take the final step of “apply”ing the argument arg to abstraction abs.

Pair Pattern

The final behavior required to complete support for pairs is the pair pattern. A pair pattern matches the components of a pair value against a pair of sub-patterns. This kind of pattern will only match if the corresponding value is a pair. In addition, any identifiers in the sub-patterns will be bound to the corresponding components of the value.

LET pair_ptrn_beh(head_ptrn, tail_ptrn) = \(cust, req).[
	CASE req OF
	(#match, (head, tail), env) : [
		SEND (k_head, #match, head, env) TO head_ptrn
		CREATE k_head WITH \env'.[
			CASE env' OF
			? : [ SEND ? TO cust ]
			_ : [ SEND (cust, #match, tail, env') TO tail_ptrn ]
			END
		]
	]
	_ : [ SEND ? TO cust ]
	END
]

When a pair pattern receives a #match request, it first attempts to match the head_ptrn against the head component of the pair value by sending a #match message to head_ptrn. The customer in this message k_head receives the extended environment env’ resulting from the match. The undefined value ? indicates a match failure, which is passed on to the original customer cust. If the match succeeds the extended environment env’ is passed on to attempt to match the tail_ptrn against the tail component of the pair value. The result of this match attempt is sent to the original customer cust.

Test Case: swap function

We can use the new pair expression and pair pattern to create a test case with code like this:

# LET swap = \(x, y).(y, x)
CREATE global_env WITH env_beh(
	#swap,
	ptrn_closure_beh(
		NEW pair_ptrn_beh(
			NEW ident_ptrn_beh(#x),
			NEW ident_ptrn_beh(#y)
		),
		NEW pair_expr_beh(
			NEW ident_expr_beh(#y),
			NEW ident_expr_beh(#x)
		),
		empty_env
	),
	empty_env
)
# swap(0, 1, 2) -> ((1, 2), 0)
SEND (NEW assert_eq_beh((1, 2), 0), #eval, global_env) TO
	NEW app_expr_beh(
		NEW ident_expr_beh(#swap),
		NEW pair_expr_beh(
			NEW const_expr_beh(0),
			NEW pair_expr_beh(
				NEW const_expr_beh(1),
				NEW const_expr_beh(2)
			)
		)
	)

First we create actor representing the definition of a swap function, which exchanges the components of a pair value. Then we bind that function in a global environment global_env. Finally we send a test #eval message that specifies a customer (using assert_eq_beh) which throws an exception if it receives the wrong response.

Note that when swap(x, y) is applied to the value (0, 1, 2) the variable x is bound to 0 and the variable y is bound to (1, 2). This demonstrates the semantics of partial matching between pair values and pair patterns.

Summary

We’ve added two important new concepts to our evolving language evaluator. Parallel evaluation of sub-expressions and the construction of ordered pair values (with corresponding pair pattern matching). Along the way we refactored our actor behaviors to capture and use a common fork/join pattern for concurrent evaluation. By adding pairs to our language, we can now extend our single-valued function arguments and return values to accept (and return) multi-valued tuples and other structured values. The corresponding extension to our matching patterns allows recognition and decomposition of structured values built from pairs.

In part 4 we will extend our pattern matching behaviors to support pattern equations. These are true equations that express relationships between patterns. They form the basis for introducing LET and IF expressions.