The ECD Abstract Machine, A Programmer's Operational Semantics

There are many different styles of operational semantics but my favorite is not very well known. Hence this post. While in graduate school, I took a course on type systems from Amr Sabry in which we studied a miniature version of SML and used the style of operational semantics that I'm about to write about. Amr didn't give a name to this style, so I'm calling it the ECD abstract machine.

Why do I like the ECD machine? The ECD machine works a lot like a debugger. A debugger session has three components: a view of the source code for the currently executing procedure with the current position marked, a list of in-scope variables and their values, and a stack of the procedure calls. The ECD machine has the same three components.

Historical aside: the ECD machine is closely related to the SECD virtual machine created by Peter Landin. The ECD machine drops the operand Stack and instead uses evaluation contexts.

In the following I'm going to write down what an ECD machine looks like for the lambda calculus. The grammar for the lambda calculus is given below (using the keyword "fun" instead of "lambda"). Note that function application is just two expressions next to each other, where the first is the function and the second is the argument. The id terminal is for identifiers (variable names). $$\begin{array}{rcl} expr &::=& id \mid expr\, expr \mid \lambda id. expr \mid value \\ value &::=& \langle \lambda id. expr, env \rangle \end{array}$$ The only kind of value (the result of running the program) in the lambda calculus is a closure, which is the result of evaluating a function (a lambda). A closure is just a tuple containing a lambda and an environment. An environment (env) is a function from identifiers to values. Yes, this is a bit circular!

Unfortunately, the lambda calculus looks rather different from your typical imperative programming language, so that may make this particular ECD machine more difficult to understand to a reader not familiar with the lambda calculus or functional programming.

First, a word about how to represent source code with a mark on the current position. Because we're dealing with an expression-oriented language, the current position is not a line number but instead a sub-expression. So the current position can be visualized as a circle drawn around the next sub-expression to be evaluated. The traditional way to represent this is with two pieces: the first piece is a data structure called an evaluation context that represents the source code outside the circle. The second piece is just the sub-expression inside the circle. The following is the grammar for evaluation contexts for the call-by-value version of the lambda calculus. The $\Box$ is the hole in the context, i.e., the location of the circle. $$\begin{array}{rcl} \mathit{EvalContext} ::= \Box \mid \mathit{EvalContext} \,expr \mid value \,\mathit{EvalContext} \end{array}$$ The function fill takes an evaluation context and an expression and returns the result of plugging the expression into the hole and then rebuilding the rest of the program. In the following we use lowercase e's for expressions and uppercase E's for evaluation contexts. We use the notation $E[e]$ as shorthand for $\mathit{fill}(E,e)$. $$\begin{align*} \Box[e] = e \\ (E\, e_2)[e] = E[e]\, e_2\\ (e_1 \, E)[e] = e_1\, E[e] \end{align*}$$

Next, let's describe the ECD abstract machine. As stated above, the ECD has three components. The first is an Environment, the second is the Control, which we will represented with an expression of the lambda calculus, and the third component, the strangely named Dump, is the call stack. The following are the reduction rules for the ECD abstraction machine. The variable x ranges over variables, s over stacks, and r over environments. Each reduction rule has a name given in parenthesis on the right-hand side. $$\begin{align*} (r, E[x], s) &\longrightarrow (r, E[r(x)], s) & \text{(VAR)} \\ (r, E[\lambda x.e], s) &\longrightarrow (r, E[\langle \lambda x. e, r\rangle], s) & \text{(LAM)} \\ (r, E[\langle \lambda x.e',r'\rangle \,v], s) &\longrightarrow (r'[x:=v], e', (E,r) s) & \text{(APP)} \\ (r, v, (E,r') s) &\longrightarrow (r', E[v], s) & (RET) \\ \end{align*}$$ The VAR rule handles the case of evaluating a variable by looking it up in the environment. The LAM rule evaluates a lambda into a closure, capturing the current environment in the second part of the closure. The APP rule starts a function call whereas the RET rule finishes a function call. Each element of the call stack is a tuple containing an evaluation context and an environment.

Let's finish with an example: $$\begin{align*} & (\emptyset, (\lambda x. (\lambda y. x))\, (\lambda z. z)\, (\lambda w. w), []) \\ (LAM) \longrightarrow\;\;& (\emptyset, \langle \lambda x. (\lambda y. x), \emptyset\rangle \, (\lambda z. z) \, (\lambda w. w), []) \\ (LAM) \longrightarrow\;\;& (\emptyset, \langle \lambda x. (\lambda y. x), \emptyset\rangle\, \langle \lambda z. z, \emptyset\rangle \, (\lambda w. w), []) \\ (APP) \longrightarrow\;\;& (\{x:=\langle \lambda z. z, \emptyset \rangle\}, (\lambda y. x), [ (\Box\, (\lambda w. w), \emptyset) ]) \\ (LAM) \longrightarrow\;\;& (\{x:=\langle \lambda z. z, \emptyset \rangle\}, \langle \lambda y. x, \{x:=\langle \lambda z. z, \emptyset \rangle\}\rangle, [ (\Box\, (\lambda w. w),\emptyset) ]) \\ (RET) \longrightarrow\;\;& (\emptyset, \langle \lambda y. x, \{x:=\langle \lambda z. z, \emptyset \rangle\}\rangle\, (\lambda w. w), []) \\ (LAM) \longrightarrow\;\;& (\emptyset, \langle \lambda y. x, \{x:=\langle \lambda z. z, \emptyset \rangle\}\rangle \,\langle \lambda w. w, \emptyset \rangle, []) \\ (APP) \longrightarrow\;\;& (\{x:=\langle \lambda z. z, \emptyset \rangle, y:=\langle \lambda w. w, \emptyset \rangle\}, x, [(\Box, \emptyset)]) \\ (VAR) \longrightarrow\;\;& (\{x:=\langle \lambda z. z, \emptyset \rangle, y:=\langle \lambda w. w, \emptyset \rangle\}, \langle \lambda z. z, \emptyset \rangle, [(\Box,\emptyset)]) \\ (RET) \longrightarrow\;\;& (\emptyset, \langle \lambda z. z, \emptyset \rangle, []) \end{align*}$$

A parting question. Is the ECD machine space efficient with regards to tail-recursive functions? If not, how would you modify it to be space efficient?