It's Actors All The Way Down

We continue exploring actor implementation of programming language constructs by adding a special form for conditional expressions. This will not increase the expressive power of the language. In part 1 we implemented a Turing-complete pure untyped lambda calculus. Now we add direct efficient support for conditional expressions and introduce basic pattern matching.

Changes from the language grammar from part 1 are highlighted in this grammar for our extended expression language:

expr  ::= <const>
        | <ident>
        | '\' <ptrn> '.' <expr>
        | <expr> '(' <expr> ')'
        | 'CASE' <expr> 'OF' {<ptrn> ':' <expr>}+ 'END';
ptrn ::= <const>
        | <ident>
        | '

CASE … OF … END

The new CASE expression is the first building block introducing pattern matching. We will have more to say about pattern matching in part 4. This simple case evaluates an expression and then attempts to match the resulting value against a series of patterns. The patterns may be constants, identifiers or value-expressions. The expression associated with the first matching pattern is evaluated to produce the result value for the CASE expression.

The behavior of the CASE expression is divided among several actors. The first is an actor responsible for evaluating the selection value expression.

LET case_expr_beh(value_expr, choices) = \(cust, #eval, env).[
	SEND (k_value, #eval, env) TO value_expr
	CREATE k_value WITH \value.[
		SEND (cust, #match, value, env) TO choices
	]
]

When case_expr_beh receives an #eval message, it sends an #eval message to value_expr. The customer in that message k_value receives the value and repackages it in a #match message sent to a chain of “choice” actors choices.

Each choice in the CASE holds a pattern to match, a result expression to evaluate if the match is successful, and a link to the next choice.

LET case_choice_beh(ptrn, expr, next) = \(cust, #match, value, env).[
	SEND (k_match, #match, value, env) TO ptrn
	CREATE k_match WITH \env'.[
		CASE env' OF
		? : [ SEND (cust, #match, value, env) TO next ]
		_ : [ SEND (cust, #eval, env') TO expr ]
		END
	]
]

When case_choice_beh receives a #match message, it sends a #match message to the pattern ptrn. The customer in this message k_match receives the extended environment (if the match was successful) or the undefined value ? (if the match failed). If the match fails the original #match message is forwarded to the next choice. If the match succeeds, an #eval message with the extended environment env’ is sent to the expression expr. The resulting value is sent to the original customer cust as the value of the CASE expression.

The case_end actor represents the end of the chain of choices.

CREATE case_end WITH \(cust, #match, _).[
	SEND ? TO cust
]

When case_end receives a #match message, it sends the undefined value ? to the original customer as the value of the CASE expression. We can use a shared singleton actor here since the behavior of END is the same for all instances of CASE.

The CASE expression is a limited form of conditional expression implemented as a special form. The special form controls the amount of work done during pattern matching and only evaluates the expression associated with a matching pattern. This is more efficient because it does less work than a conditional expression implemented in our eager-evaluating core lambda calculus.

LET true = \cnsq.\altn.cnsq
LET false = \cnsq.\altn.altn
LET if = \pred.\cnsq.\altn.(pred(cnsq))(altn)

With these definitions we can create “predicates” which evaluate to true or false and then pass them to if which uses them to select either the consequence cnsq or the alternative altn. The problem with this approach is that both consequence and alternative expressions are evaluated regardless of which value is finally selected by the predicate. This is why, even all the way back to McCarthy’s original LISP [1][2], the conditional expression is implemented as a special form.

Pattern Matching

Our version of conditional expression uses pattern matching rather than Boolean predicates. We will also generalize the lambda abstraction to take advantage of pattern matching. But first we will consider the patterns themselves.

Identifier Pattern

An identifier pattern matches any value and extends the environment to include a binding from the identifier to the matched value.

LET ident_ptrn_beh(ident) = \(cust, req).[
	CASE req OF
	(#match, value, env) : [
		CREATE env' WITH env_beh(ident, value, env)
		SEND env' TO cust
	]
	_ : [ SEND ? TO cust ]
	END
]

When an identifier pattern receives a #match request, it creates an extended environment env’ which binds ident to value and chains to the original environment env. This extended environment is sent to the customer cust.

Constant/Literal Pattern

A constant pattern matches only if the value to be matched is the same as the value held by the pattern.

LET const_ptrn_beh(value) = \(cust, req).[
	CASE req OF
	(#match, $value, env) : [ SEND env TO cust ]
	_ : [ SEND ? TO cust ]
	END
]

When a constant pattern receives a #match request that matches the constant value, the (unchanged) environment env is sent to the customer cust, indicating success. Otherwise the undefined value ? is sent to the customer, indicating failure.

Test Case: zero? Predicate

We can use the constant and identifier patterns to create a simple test case with code like this:

# LET zero? = \x.(
#	CASE x OF
#	0 : TRUE
#	_ : FALSE
#	END
# )
CREATE global_env WITH env_beh(
	#zero?,
	NEW closure_beh(
		#x,
		NEW case_expr_beh(
			NEW ident_expr_beh(#x),
			NEW case_choice_beh(
				NEW const_ptrn_beh(0),
				NEW const_expr_beh(TRUE),
				NEW case_choice_beh(
					NEW ident_ptrn_beh(#_),
					NEW const_expr_beh(FALSE),
					case_end
				)
			)
		),
		empty_env
	),
	empty_env)
# zero?(0) -> TRUE
SEND (NEW assert_eq_beh(TRUE), #eval, global_env) TO
	NEW app_expr_beh(
		NEW ident_expr_beh(#zero?),
		NEW const_expr_beh(0)
	)
# zero?(1) -> FALSE
SEND (NEW assert_eq_beh(FALSE), #eval, global_env) TO
	NEW app_expr_beh(
		NEW ident_expr_beh(#zero?),
		NEW const_expr_beh(1)
	)

First we create actor representing the definition of a zero? predicate function, which evaluates to TRUE if its argument is zero (0) and FALSE otherwise. Then we bind that function in a global environment global_env. Finally we send two test messages to applications of the function. Each test specifies a customer (using assert_eq_beh) which throws an exception if it receives the wrong response.

Wildcard Pattern

A wildcard pattern matches any value but does not extend the environment with a new binding. We use this pattern, denoted by ‘_‘, when we want a match, but don’t care about access to the value matched.

CREATE any_ptrn WITH \(cust, req).[
	CASE req OF
	(#match, _, env) : [ SEND env TO cust ]
	_ : [ SEND ? TO cust ]
	END
]

When a wildcard pattern receives a #match request, the (unchanged) environment env is sent to the customer cust, indicating success.

Expression Value Pattern

A value pattern evaluates an expression to produce a value and then attempts to match that value as if it was a constant pattern. We use this pattern to introduce computed values (often simply variable references) into our pattern matching. Normally, identifiers in patterns indicate new bindings to matched values. The value pattern, denoted by a ‘$‘ prefix, indicates a pattern matching the value of an arbitrary expression.

LET value_ptrn_beh(expr) = \(cust, req).[
	CASE req OF
	(#match, value, env) : [
		SEND (k_val, #eval, env) TO expr
		CREATE k_val WITH \value'.[
			CASE value' OF
			$value : [ SEND env TO cust ]
			_ : [ SEND ? TO cust ]
			END
		]
	]
	_ : [ SEND ? TO cust ]
	END
]

When a value pattern receives a #match request it first evaluates the expression expr in the context of the current environment env by sending an #eval message to expr. The customer in this message k_val receives the result value’. If value’ matches value then the original environment env is sent to the customer cust, indicating success. Otherwise the undefined value ? is sent to the customer, indicating failure.

Test Case: eq? Predicate

We can use the value and wildcard patterns to create another test case with code like this:

# LET eq? = \x.\y.(
#	CASE y OF
#	$x : TRUE
#	_ : FALSE
#	END
# )
CREATE global_env WITH env_beh(
	#eq?,
	NEW ptrn_closure_beh(
		NEW ident_ptrn_beh(#x),
		NEW ptrn_abs_beh(
			NEW ident_ptrn_beh(#y),
			NEW case_expr_beh(
				NEW ident_expr_beh(#y),
				NEW case_choice_beh(
					NEW value_ptrn_beh(
						NEW ident_expr_beh(#x)
					),
					NEW const_expr_beh(TRUE)
				),
				NEW case_choice_beh(
					any_ptrn,
					NEW const_expr_beh(FALSE),
					case_end
				)
			)
		),
		empty_env
	),
	empty_env
)
# (eq?(0))(1) -> FALSE
SEND (NEW assert_eq_beh(FALSE), #eval, global_env) TO
	NEW app_expr_beh(
		NEW app_expr_beh(
			NEW ident_expr_beh(#eq?),
			NEW const_expr_beh(0)
		),
		NEW const_expr_beh(1)
	)

First we create actor representing the definition of an eq? predicate function, which evaluates to TRUE if its arguments are the same and FALSE otherwise. Then we bind that function in a global environment global_env. Finally we send a test message that specifies a customer (using assert_eq_beh) which throws an exception if it receives the wrong response.

Pattern Abstraction

Our original grammar for lambda abstraction was:

'\' <ident> '.' <expr>

The identifier represented an identifier pattern, not a named variable reference. This is clear in an expression like \x.x, the identity function, where the first x is a pattern and the second x is a variable reference (to the pattern variable bound when the abstraction is applied to an argument). We can generalize based on this observation and change the grammar for lambda abstraction to:

'\' <ptrn> '.' <expr>

Now we can use any pattern in an abstraction instead of being restricted to only identifiers. If the pattern does not match the argument when the abstraction is applied, the expression evaluates to the undefined value, denoted by ‘?‘.

Our new ptrn_abs_expr_beh is just like abs_expr_beh, except that it creates a ptrn_closure_beh instead of a closure_beh.

LET ptrn_abs_expr_beh(ptrn, body_expr) = \(cust, #eval, env).[
	SEND NEW ptrn_closure_beh(ptrn, body_expr, env) TO cust
]

A pattern closure can be applied to an argument value, just like our previous closure. But instead of binding an identifier, it matches the argument value to the abstraction pattern and evaluates the body expression is the environment resulting from the match.

LET ptrn_closure_beh(ptrn, body, env) = \(cust, #apply, arg).[
	SEND (k_env, #match, arg, env) TO ptrn
	CREATE k_env WITH \env'.[
		CASE env' OF
		? : [ SEND ? TO cust ]
		_ : [ SEND (cust, #eval, env') TO body ]
		END
	]
]

When a pattern closure receives an #apply message, it sends a #match message with the argument value arg to the pattern ptrn. The customer in this message k_env receives the extended environment resulting from the match. If the environment is undefined, meaning the pattern failed to match, then the undefined value is sent to the customer cust. Otherwise, an #eval message with the extended environment env’ is sent to the body expression. The resulting value is sent to the original customer cust.

Summary

We continued to build on our evaluator for core lambda calculus from part 1 by adding a special form for conditional expressions. Rather than take the usual boolean-predicate approach, we used pattern matching instead. This led to implementation of a few basic patterns and motivated the need for a way to distinguish pattern matching variables (which cause binding) from bound variable references. Once the pattern matching and variable binding mechanisms where in place, we saw how patterns could generalize lambda abstraction variables.

In part 3 we will explore parallel evaluation of sub-expressions and introduce pairs. Pair expressions will lead to tuples, generalizing structured multi-part patterns and values.

References

[1]

H. Stoyan. The Influence of the Designer on the Design – J. McCarthy and LISP. Artificial Intelligence and Mathematical Theory of Computation, p.409-426, Academic Press, 1991.

[2]

J. McCarthy, et. al. LISP 1.5 Programmer’s Manual. MIT Press, Cambridge, Mass., 1962.