This is a substitute lecture by Yi Dai for the course //Programming Languages and Types// by Klaus Ostermann at the University of Marburg.

The material in this lecture is loosely based on the following two papers:

Mads Sig Ager, Dariusz Biernacki, Olivier Danvy, and Jan Midtgaard. A functional correspondence between evaluators and abstract machines. In Dale Miller, editor, Proceedings of the Fifth ACM-SIGPLAN International Conference on Principlesand Practice of Declarative Programming (PPDP'03), pages 8-19. ACM Press, August 2003.
Olivier Danvy. On evaluation contexts, continuations, and the rest of the computation. In Hayo Thielecke, editor, Proceedings of the Fourth ACM SIGPLAN Workshop on Continuations, Technical report CSR-04-1, Department of Computer Science, Queen Mary’s College, pages 13-23, Venice, Italy, January 2004. Invited talk.

This lecture consists of two parts. The first part goes from evaluators to abstract machines. The second part goes the other way around. In the first part, our object-language is the call-by-name lambda-calculus. In the second part, our object-language is the call-by-value lambda-calculus. For both parts, we use the de-Bruijn-index notation for lambda-expressions. (Please find more about de-Bruijn-index notation on Wikipedia.) Our meta-language is Scala as usual.

From Evaluators to Abstract Machines

In this part, we will look at how to derive an abstract machine, called Krivine’s machine, for the call-by-name lambda-calculus, from a standard interpreter by a series of program transformations.

Higher-Order Function

This interpreter implements the call-by-name lambda-calculus. It features meta-level higher-order functions in the following two senses:

Object-level first-class functions are implemented by meta-level first-class functions and object-level function application is implemented by meta-level function application. Since object-level functions are higher-order, meta-level functions implementing them must also be higher-order.
Since eval returns such meta-level functions as results, eval is higher-order too.

object HOF {
  sealed abstract class Exp
  sealed abstract class Value

  case class Id(ind: Int) extends Exp
  case class Fun(body: Exp) extends Exp
  case class App(funExpr: Exp, argExpr: Exp) extends Exp

  case class Proc(fun: Value => Value) extends Value

  type Env = List[Value]

  def eval(exp: Exp, env: Env): Value = exp match {
    case Id(ind) => env(ind)
    case Fun(body) => Proc(arg => eval(body, arg :: env))
    case App(funExpr, argExpr) => eval(funExpr, env) match {
      case Proc(fun) => fun(eval(argExpr, env))
    }
  }

  def interpret(exp: Exp): Value = eval(exp, Nil)
}

Note that in the implementation of HOF, the evaluation order of the object-language depends on the evaluation order of the meta-language. The dependence manifests at fun(eval(argExpr, env)).

On one hand, if the meta-language uses call-by-value, which happens to be so for Scala, the object-language is forced to be call-by-value; if instead the meta-language uses call-by-name, the object-language becomes call-by-name too.

On the other hand, if the meta-language uses call-by-value but we want the object-languge to be call-by-name, a special construct that can delay evaluation must be introduced into the meta-language; if the meta-language uses call-by-name but we want the object-language to be call-by-value, a special construct that can force evaluation must be introduced into the meta-language. In either case, the meta-language must be extended, which sometimes may be difficult or impossible.

Fortunately a program transformation technique can solve both problems gracefully, eliminating the evaluation-order dependence between the object-language and meta-language, that is, by transforming the interpreter into continuation-passing style.

But to make life a bit easier, let us first get rid of meta-level first-class functions that implement object-level first-class functions.

Closure Conversion

Closure conversion converts the representation of object-level first-class functions to meta-level data structures, namely closures. The consequences are twofold:

It eliminates the use of meta-level first-class functions to represent object-level first-class functions.
It turns meta-level higher-order functions back to first-order, particularly eval.

Keeping from meta-level first-class functions but with meta-level first-order functions opens more choices of meta-languages for implementation. For example, a language like C that does not natively support first-class functions can be used.

After closure conversion, we have an interpreter in direct style, that is, not manipulating explicit continuations.

object HOF_CC {
  sealed abstract class Exp
  sealed abstract class Value

  case class Id(ind: Int) extends Exp
  case class Fun(body: Exp) extends Exp
  case class App(funExpr: Exp, argExpr: Exp) extends Exp

  type Env = List[Value]

  case class ClosureV(body: Exp, env: Env) extends Value

  def eval(exp: Exp, env: Env): Value = exp match {
    case Id(ind) => env(ind)
    case Fun(body) => ClosureV(body, env)
    case App(funExpr, argExpr) => eval(funExpr, env) match {
      case ClosureV(body, closureEnv) => eval(body, eval(argExpr, env) :: closureEnv)
    }
  }

  def interpret(exp: Exp): Value = eval(exp, Nil)
}

Call-by-Name CPS-Transformation

The problem of evaluation-order dependence between the object-language and the meta-language remains in the interpreter in direct style after closure conversion, as evidenced by eval(body, eval(argExpr, env) :: closureEnv). To solve the problem without extending the meta-language, we must turn to CPS-transformation.

As to see how to implement a call-by-name language in a call-by-value language without extending the meta-language, we decide our object-language to be the call-by-name lambda-calculus and use the call-by-name CPS-transformation to transform the interpreter from direct style into continuation-passing style.

The result of the transformation has the following features:

The evaluation order of the object-language is call-by-name. It no longer depends on the evaluation order of the meta-language. Even if someday Scala switches to call-by-name, our interpreter still correctly implements the call-by-name lambda-calculus.
The whole interpreter is tail recursive and can readily be tail-call optimized.

object HOF_CC_CbNCPS {
  sealed abstract class Exp
  sealed abstract class Value
  sealed abstract class Computation

  case class Id(ind: Int) extends Exp
  case class Fun(body: Exp) extends Exp
  case class App(funExpr: Exp, argExpr: Exp) extends Exp

  type Env = List[Computation]

  case class ClosureV(body: Exp, env: Env) extends Value

  type Cont = Value => Value

  case class Thunk(fun: Cont => Value) extends Computation

  def eval(exp: Exp, env: Env, k: Cont): Value = exp match {
    case Id(ind) => env(ind) match {
      case Thunk(fun) => fun(k)
    }
    case Fun(body) => k(ClosureV(body, env))
    case App(funExpr, argExpr) =>
      eval(funExpr, env, v => v match {
        case ClosureV(body, closureEnv) =>
          eval(body, Thunk(k => eval(argExpr, env, k)) :: closureEnv, k)
      })
  }

  def interpret(exp: Exp): Value = eval(exp, Nil, v => v)
}

Defunctionalization

Defunctionalization is a general program transformation technique that eliminates higher-order functions, by replacing the creation of first-class functions with the construction of data structures and the application of first-class functions with the destruction of data structures.

A program that contains higher-order functions can be defunctionalized following three steps:

Encoding — Identify first-class functions in the program and classify them according to their types. For each function type, introduce an encoding data type. For each function instance (i.e. function of the encoded function type) introduce a constructor that will construct data of the encoding type. Make sure that each data constructor takes arguments that have the same types as the free variables of the function instance. The idea is that each constructor should save the values bound to the free variables of the function instance. Encoding should not cause any informatoin loss.
Decoding — For each encoding data type, define a function (conventionally called “apply”) that takes one argument of the data type and the other of the argument type of the encoded function type. This “apply” function will use pattern matching to do case analysis on its first argument in order to extract the saved values bound to the free variables of the encoded function instance. The right-hand side of each case will be the body of the encoded function instance, with variables renamed accordingly.
Refactoring — Go through the program. When an encoded function type is met, replace it with its encoding data type. When a function instance is met, encode it by constructing data from its free variables using the corresponding constructor. In this way, values bound to the free variables of the function instance are saved. Locate all the places where a function instance is applied, replacing its application with an explict call of the “apply” function on (the designator of) the function instance and its argument.

We illustrate how to defunctionalize a higher-order program following these two steps by an example. Below is a simple higher-order program that defines a function that will first add n to and then multiply by n every integer in a list xs.

def map(f: Int => Int, xs: List[Int]): List[Int] = xs match {
  case Nil => Nil
  case x :: xs => f(x) :: map(f, xs)
}

def addMulInts(n: Int, xs: List[Int]): List[Int] =
  map(x => x * n, map(x => x + n, xs))

Let us apply the three-step procedure to this program.

1. Encoding

There are two first-class functions in the program, namely x = > x * n and x => x + n. Both are instances of the type Int => Int. Therefore we only need to introduce one data type, call it IntF. Both functions also have n of type Int as their free variables. So we introduce two data constructors, call them AddN and MulN respectively. Each takes an argument n of type Int.

sealed abstract class IntF
case class AddN(n: Int) extends IntF
case class MulN(n: Int) extends IntF

2. Decoding

Next we define the “apply” function which takes one argument of type IntF and the other argument of the argument type of the encoded function type Int => Int, that is, Int. The “apply” function will distinguish two cases, MulN(n) or AddN(n), and respectively add n to or multiply by n its second argument. Note that we use the same names (“x” and “n” respectively) for the second parameter and the pattern variable of each case in apply, as those for the parameter and free variable in each encoded function instance, so that we are not concerned with variable renaming and can put the body of the encoded function instance as is directly to the right-hand side of each case. But normally, renaming variables in the body of the encoded function instance is required, for instance, if the second function instance in our example program is y => y * n instead of x => x * n.

def apply(f: IntF, x: Int): Int = f match {
  case MulN(n) => x * n
  case AddN(n) => x + n
}

3. Refactoring

Now we are ready to actually defunctionalize the original higher-order program. First, we replace the function type Int => Int of the parameter f of map with our encoding data type IntF. Second, we replace the two function instances x => x * n and x => x + n in the body of AddMulInts by MulN(n) and AddN(n) respectively. Note that both functions will be bound to f and passed in to map. In other words, where f is applied in map is where these function instances are applied. Thus the third is to replace the application of f to x with an explicit invocation of apply on f and x.

def map(f: IntF, xs: List[Int]): List[Int] = xs match {
  case Nil => Nil
  case x :: xs => apply(f, x) :: map(f, xs)
}

def addMulInts(n : Int, xs : List[Int]) : List[Int] =
  map(MulN(n), map(AddN(n), xs))

Defunctionalization can also be applied to non-trivial higher-order programs, like interpreters.

Actually closure conversion can be seen as a special case of defunctionalization. It is usually done before transforming the interpreter into continuation-passing style to ease the whole task. Below is what we get by defunctionalizing meta-level first-class functions that implement object-level first-class functions. applyClosure is the “apply” function. It can be easily verified that inlining applyClosure gives exactly the interpreter defined in HOF_CC.

object HOF_DFP {
  sealed abstract class Exp
  sealed abstract class Value

  case class Id(ind : Int) extends Exp
  case class Fun(body : Exp) extends Exp
  case class App(funExpr : Exp, argExpr : Exp) extends Exp

  type Env = List[Value]

  case class ClosureV(body : Exp, env : Env) extends Value

  def applyClosure(c: Value, arg: Value) : Value = c match {
    case ClosureV(body, closureEnv) => eval(body, arg :: closureEnv)
  }

  def eval(exp : Exp, env : Env) : Value = exp match {
    case Id(ind) => env(ind)
    case Fun(body) => ClosureV(body, env)
    case App(funExpr, argExpr) => applyClosure(eval(funExpr, env), eval(argExpr, env))
  }

  def interpret(exp : Exp) : Value = eval(exp, Nil)
}

Back to our original plan, since CPS-transformation reintroduced meta-level first-class functions and in turn higher-order functions as well into the closure-converted interpreter, we are going to apply defunctionalization to our CPS-transformed interpreter HOF_CC_CbNCPS.

There are two function types, namely Value => Value for continuation and Cont => Value for delayed computation. We will defunctionalize them separately. We choose to first handle Cont => Value. The other way around works as well and is left as an exercise.

Defunctionalizing Computation

For the function type Cont => Value, we introduce an encoding data type Computation. The is only one instance of type Cont => Value, that is, k => eval(argExpr, env, k).
It contains two free variables, namely argExpr of type Exp and env of type Env. Therefore we introduce one data constructor Thunk that takes one argument of type Exp and the other of type Env, without loss of generality, named argExpr and env respectively. The “apply” function, called applyComp is readily defined. During refactoring, the only function instance is replaced with Thunk(argExpr, env), and the application of the encoded function fun(k) is replaced with an explicit invocation of applyComp on env(ind) which is supposed to be data encoding compuation and the continuation k. The result is the following interpreter.

object HOF_CC_CbNCPS_DFC {
  sealed abstract class Exp
  sealed abstract class Value
  sealed abstract class Computation

  case class Id(ind: Int) extends Exp
  case class Fun(body: Exp) extends Exp
  case class App(funExpr: Exp, argExpr: Exp) extends Exp

  type Env = List[Computation]

  case class ClosureV(body: Exp, env: Env) extends Value

  type Cont = Value => Value

  case class Thunk(exp: Exp, env: Env) extends Computation

  def applyComp(thunk: Computation, k: Cont): Value = thunk match {
    case Thunk(exp, env) => eval(exp, env, k)
  }

  def eval(exp: Exp, env: Env, k: Cont): Value = exp match {
    case Id(ind) => applyComp(env(ind), k)
    case Fun(body) => k(ClosureV(body, env))
    case App(funExpr, argExpr) =>
      eval(funExpr, env, v => v match {
        case ClosureV(body, closureEnv) => 
          eval(body, Thunk(argExpr, env) :: closureEnv, k)
      })
  }

  def interpret(exp: Exp): Value = eval(exp, Nil, v => v)
}

Inlining

We can similarly inline applyComp, giving:

object HOF_CC_CbNCPS_DFC_Inl {
  sealed abstract class Exp
  sealed abstract class Value
  sealed abstract class Computation

  case class Id(ind: Int) extends Exp
  case class Fun(body: Exp) extends Exp
  case class App(funExpr: Exp, argExpr: Exp) extends Exp

  type Env = List[Computation]

  case class ClosureV(body: Exp, env: Env) extends Value

  type Cont = Value => Value

  case class Thunk(argExpr: Exp, env: Env) extends Computation

  def eval(exp: Exp, env: Env, k: Cont) : Value = exp match {
    case Id(ind) => env(ind) match {
      case Thunk(exp, env) => eval(exp, env, k)
    }
    case Fun(body) => k(ClosureV(body, env))
    case App(funExpr, argExpr) =>
      eval(funExpr, env, v => v match {
        case ClosureV(body, closureEnv) => eval(body, Thunk(argExpr, env) :: closureEnv, k)
      })
  }

  def interpret(exp: Exp): Value = eval(exp, Nil, v => v)
}

Defunctionalizing Continuation

Next we defunctionalize functions of type Value => Value for continuation. First, we introduce a new data type Cont. Second, we find that there are two instances of the function type: v => v match { … } and v => v. The former has three free variables: argExpr of type Exp, env of type Env and k of type Cont. The latter has no free variable. Therefore we introduce two data constructors: AppCont with two parameters exp of type Exp and env of type Env, IdCont with no parameter. The apply function, called applyCont is again easily defined. Third, we replace the two instances v => v match { … } and v => v with AppCont(exp, env, k) and IdCont() respectively, the application of them k(ClosureV(body, env) with an explicit invocation of applyCont on k and ClosureV(body, env). We obtain the following interpreter without meta-level first-class functions and higher-order functions.

object HOF_CC_CbNCPS_DFC_Inl_DFC {
  sealed abstract class Exp
  sealed abstract class Value
  sealed abstract class Computation
  sealed abstract class Cont

  case class Id(ind: Int) extends Exp
  case class Fun(body: Exp) extends Exp
  case class App(funExpr: Exp, argExpr: Exp) extends Exp

  type Env = List[Computation]

  case class ClosureV(body: Exp, env: Env) extends Value

  case class Thunk(exp: Exp, env: Env) extends Computation

  case class AppCont(exp: Exp, env: Env, k: Cont) extends Cont
  case class IdCont() extends Cont

  def applyCont(k: Cont, v: Value): Value = k match {
    case AppCont(exp, env, k) => v match {
      case ClosureV(body, closureEnv) => eval(body, Thunk(exp, env) :: closureEnv, k)
    }
    case IdCont() => v
  }

  def eval(exp: Exp, env: Env, k: Cont): Value = exp match {
    case Id(ind) => env(ind) match {
      case Thunk(exp, env) => eval(exp, env, k)
    }
    case Fun(body) => applyCont(k, ClosureV(body, env))
    case App(funExpr, argExpr) => eval(funExpr, env, AppCont(argExpr, env, k))
  }

  def interpret(exp: Exp): Value = eval(exp, Nil, IdCont())
}

Refactoring (Again)

Notice the structural similarity between the two constructors ClosureV and Thunk: both take as arguments an Exp and an Env. They can be unified them by keeping only one of them, say Thunk. Note that Computation is renamed ClosureV as a reminder for this unification.

Next observe another structual similarity between constructors of data type Cont and those of Scala’s built-in generic type List[T]: IdCont is isomorphic to Nil and AppCont is isomorphic to :: if we group Exp and Env together as one data type, naturally ClosureV. Thanks to this isomorphism, we can use Nil and :: in place of IdCont and AppCont. In other words, we can listify continuations.

Again we can inline applyCont.

Finally, we modify the return type of eval to be the triple (Exp, Env, Cont).
Now if we consider the triple as a kind of “state”, eval can be viewed as a state transition function:

(Exp, Env, Cont) ==eval=> (Exp, Env, Cont)

More accurately, eval takes a big-step, jumping from an initial state (exp, Nil, Nil) directly to a final state (body, env, Nil).

We will soon see that we thus obtain an implementaion of an abstract machine, called Krivine’s machine.

object KAM {
  sealed abstract class Exp
  sealed abstract class ClosureV

  case class Id(ind: Int) extends Exp
  case class Fun(body: Exp) extends Exp
  case class App(funExpr: Exp, argExpr: Exp) extends Exp

  type Env = List[ClosureV]

  case class Thunk(exp: Exp, env: Env) extends ClosureV

  type Cont = List[ClosureV]

  def eval(exp: Exp, env: Env, k: Cont): (Exp, Env, Cont) = exp match {
    case Id(ind) => env(ind) match {
      case Thunk(exp, env) => eval(exp, env, k)
    }
    case Fun(body) => k match {
      case Nil => (body, env, Nil)
      case (Thunk(exp, thunkEnv) :: k) => eval(body, Thunk(exp, thunkEnv) :: env, k)
    }
    case App(funExpr, argExpr) => eval(funExpr, env, Thunk(argExpr, env) :: k)
  }

  def interpret(exp: Exp): (Exp, Env, Cont) = eval(exp, Nil, Nil) 
}

Krivine’s Abstract Machine

An abstract machine is a conceptual model of a computer system. It seems a machine because it allows step-by-step program execution. It is abstract in that it leaves out lots of subtle details of real machines. A virtual machine (like the JVM) can be similarly charaterized except that it also has an instruction set. Source programs must first be compiled to object programs in these instructions before they can be executed by a virtual machine. An abstract machine does not have such an instruction set and in turn it executes source programs directly. In this sense, an abstract machine works like an interpreter. Like a real machine, an abstract machine also has states and works by updating states. In other words, one run of an abstract machine can be viewed as a series of state transition. To understand an abstract machine boils down to understand its states and transition function.

We present here an abstract machine, called Krivine’s machine (simply K-machine), for the call-by-name lambda-calculus. The K-machine has three registers: Exp to store lambda-expressions, Env to keep thunks, and Cont to save continuations. The triple (Exp, Env, Cont) completely renders the state of the K-machine. Before we see the transition function of the K-machine, we need to know the syntax for things stored in these three registers.

The syntax for lambda-expressions is:

(expression)  e ::= i    (index)
                  | \ e  (abstraction)
                  | e e  (application)

That is, a lambda-expression can be a natural number (as de-Bruijn index for a nameless variable), or “\” (mimicing the look of the Greek letter lambda) followed by an expression (together notating lambda-abstraction, designating anonymous function), or two expressions juxtaposed (together designating function application). Here are some lambda-expressions in this syntax (call it “de Bruijn”) and Scala syntax:

| de Bruijn | Scala                       |
| \ 0       | (x : Any) => x              |
| \ \ 1     | (x : Any) => (y : Any) => x |

Recall that de-Bruijn indices for a lambda-abstraction start with 0 from the innermost lambda-bound variable and count outward. Thus the inner parameter y in the example (x : Any) => (y : Any) => x is indexed 0, the outer x indexed 1. Hence the body of the de-Bruijn notation is 1. Note that Scala is typed whereas the pure lambda-calculus is not. That is why there is no type annotation in the corresponding lambda-expression in de-Bruijn syntax.

The syntax for environments is:

(environment) r ::= []
                  | (e, r) :: r

That is, an environment is either empty or a thunk bundled with other thunks accumulated into another environment.

The syntax for continuation is as follows:

(continuation) c ::= []
                   | (e, r) :: c

That is, a continuation is either nothing (left to do) or “to apply to a thunk” bundled with to-dos afterwards which manifests as another continuation.

Notice that even though environments and continuations have isomorphic syntactic structure, they have different interpretations as clearly stated above.

Now we are ready to see the state-transition function of the K-machine. It is given by three transition rules (numbered from 1 to 3) presented in the following table:

| (Exp , Env, Cont         ) | ——> | (Exp, Env          , Cont        ) |
| (i   , r  , c            ) | —1-> | (e1 , r1           , c           ) |
|                            |       |          where r(i) = (e1, r1)     |
| (\ e , r  , (e1, r1) :: c) | —2-> | (e  , (e1, r1) :: r, c           ) |
| (e e1, r  , c            ) | —3-> | (e  , r            , (e1, r) :: c) |

Each transition rule covers one-step transition of states. A run of the K-machine is a series of these transition steps. There must be an initial state and a final state. Let the lambda-program to be executed on the K-machine, in other words, the lambda-expression to be evaluated by the K-machine, be e. The initial state of a run will always be (e, [], []), that is, with the register Exp initialized to e, and the register Env to empty and the register Cont to nothing. The final states of runs for different expressions may be different. But two things are common: the machine halts when there is nothing left to do, that is, the register Cont must be []. So the final state will always have the pattern (e, r, []). e in the register Exp together with r in the register Env could be taken as the result. Let us take a simple example, (\ 0) (\ 0), and simulate its run on the K-machine.

      ( Exp        , Env            , Cont            )
      ( (\ 0) (\ 0), []             , []              )
—3-> ( \ 0        , []             , (\ 0, []) :: [] )
—2-> ( 0          , (\ 0, []) :: [], []              )
—1-> ( \ 0        , []             , []              )

To see another example, (\ \ 1) (\ 0), in run:

      ( Exp          , Env            , Cont            )
      ( (\ \ 1) (\ 0), []             , []              )
—3-> ( \ \ 1        , []             , (\ 0, []) :: [] )
—2-> ( \ 1          , (\ 0, []) :: [], []              )

This example shows that in the final state, the register Env does not necessarily hold the empty environment.

As an exercise, try to simulate the execution of ((\ \ 1) (\ 0)) (\ 0) on the K-machine.

We see that to evaluate a lambda-expression e, the K-machine sets the initial state to (e, [], []), applies the three transition rules repeatedly (for zero or more times) until the register Cont holds [] again, which means there is nothing left to do, and then halts. This hints the following idea for an implementation of the K-machine: we can define a Scala function, red1(exp : Exp, env : Env, k : Cont) : (Exp, Env, Cont), and then form a do-while loop with a loop variable s : (Exp, Env, Cont) initialized to (exp, [], []), with a loop condition checking whether k is [], and in the body tries to apply one of the transition rules. The actual implementation is left as an exercise.

We finally remark that KAM we have defined above is indeed such an implementation. Note that eval is tail-recursive, thus it is equivalent to a loop in effect. The difference between eval and red1 is: the former implements a big-step transition, while the latter a small-step transition.

To conclude, we have demonstrated how to reach an abstract-machine-level impelementation of the call-by-name lambda-calculus from a high-level implementation using higher-order features by performing a series of program transformations on the evaluators. Next, we will do reverse engineering: we will start with an abstract-machine-level implementation of the call-by-value lambda-calculus, do the reverse of those program transformations we have seen, and reach a high-level implementation using higher-order features.

From Abstract Machines to Evaluators

The CEK-Machine

object CEK {
  sealed abstract class Exp
  sealed abstract class Value
  sealed abstract class Ctx

  case class Id(ind : Int) extends Exp
  case class Fun(body : Exp) extends Exp
  case class App(funExpr : Exp, argExpr : Exp) extends Exp

  type Env = List[Value]

  case class ClosureV(body : Exp, env : Env) extends Value

  case class IdCont() extends Ctx
  case class ACL(argExpr : Exp, env : Env, ctx : Ctx) extends Ctx
  case class ACR(clo : Value, ctx : Ctx) extends Ctx

  def applyCont(ctx : Ctx, v : Value) : Value = ctx match {
    case IdCont() => v
    case ACL(argExpr, env, ctx) => v match {
      case clo@ClosureV(_, _) => eval(argExpr, env, ACR(clo, ctx))
    }
    case ACR(ClosureV(body, closureEnv), ctx) => eval(body, v :: closureEnv, ctx)
  }

  def eval(exp : Exp, env : Env, ctx : Ctx) : Value = exp match {
    case Id(ind) => applyCont(ctx, env(ind))
    case Fun(body) => applyCont(ctx, ClosureV(body, env))
    case App(funExpr, argExpr) => eval(funExpr, env, ACL(argExpr, env, ctx))
  }

  def interpret(exp : Exp) : Value = eval(exp, Nil, IdCont())
}

Refunctionalization

object CEK_RF {
  sealed abstract class Exp
  sealed abstract class Value

  case class Id(ind : Int) extends Exp
  case class Fun(body : Exp) extends Exp
  case class App(funExpr : Exp, argExpr : Exp) extends Exp

  type Env = List[Value]

  case class ClosureV(body : Exp, env : Env) extends Value

  type Ctx = Value => Value

  def eval(exp : Exp, env : Env, ctx : Ctx) : Value = exp match {
    case Id(ind) => ctx(env(ind))
    case Fun(body) => ctx(ClosureV(body, env))
    case App(funExpr, argExpr) =>
      eval( funExpr, env
          , clo => eval( argExpr, env
                       , arg => clo match {
                           case ClosureV(body, closureEnv) => eval(body, arg :: closureEnv, ctx)
                         } ) )
  }

  def interpret(exp : Exp) : Value = eval(exp, Nil, v => v)
}

Direct-Style Transformation

object CEK_RF_DS {
  sealed abstract class Exp
  sealed abstract class Value

  case class Id(ind : Int) extends Exp
  case class Fun(body : Exp) extends Exp
  case class App(funExpr : Exp, argExpr : Exp) extends Exp

  type Env = List[Value]

  case class ClosureV(body : Exp, env : Env) extends Value

  def eval(exp : Exp, env : Env) : Value = exp match {
    case Id(ind) => env(ind)
    case Fun(body) => ClosureV(body, env)
    case App(funExpr, argExpr) => eval(funExpr, env) match {
      case ClosureV(body, closureEnv) => eval(body, eval(argExpr, env) :: closureEnv)
    }
  }

  def interpret(exp : Exp, env : Env) : Value = eval(exp, Nil)
}

Higher-Order-Function Conversion

object CEK_RF_DS_HOF {
  sealed abstract class Exp
  sealed abstract class Value

  case class Id(ind : Int) extends Exp
  case class Fun(body : Exp) extends Exp
  case class App(funExpr : Exp, argExpr : Exp) extends Exp

  type Env = List[Value]

  case class Prc(fun : Value => Value) extends Value

  def eval(exp : Exp, env : Env) : Value = exp match {
    case Id(ind) => env(ind)
    case Fun(body) => Prc(arg => eval(body, arg :: env))
    case App(funExpr, argExpr) => eval(funExpr, env) match {
      case Prc(fun) => fun(eval(argExpr, env))
    }
  }

  def interpret(exp : Exp) : Value = eval(exp, Nil)
}

Rationalized *

object HOF { sealed abstract class Imp

case class Id(ind : Int) extends Imp case class Fun(body : Imp) extends Imp case class App(funExpr : Imp, argExpr : Imp) extends Imp case class Prc(fun : Imp => Imp) extends Imp

type Env = List[Imp]

def norm(imp : Imp, env : Env) : Imp = imp match { case Id(ind) => env(ind) case Fun(body) => Prc(arg => norm(body, arg :: env)) case App(funExpr, argExpr) => norm(funExpr, env) match { case Prc(fun) => fun(norm(argExpr, env)) } }

def interpret(imp : Imp) : Imp = norm(imp, Nil) }

/* ## Call-by-Name CPS-Transformation

object HOF_CbNCPS {
  sealed abstract class Imp

  case class Id(ind : Int) extends Imp
  case class Fun(body : Imp) extends Imp
  case class App(funExpr : Imp, argExpr : Imp) extends Imp

  type Env = List[Imp]

  type Cont = Imp => Imp

  case class Prc(fun : Imp => Cont => Imp) extends Imp
  case class Cmp(fun : Cont => Imp) extends Imp

  def norm(imp : Imp, env : Env, k : Cont) : Imp = imp match {
    case Id(ind) => env(ind) match {
      case Cmp(fun) => fun(k)
    }
    case Fun(body) => k(Prc(cmp => k => norm(body, cmp :: env, k)))
    case App(funExpr, argExpr) =>
      norm( funExpr, env
          , prc => prc match {
              case Prc(fun) => fun(Cmp(k => norm(argExpr, env, k)))(k)
            } )
  }

  def interpret(imp : Imp) : Imp = norm(imp, Nil, nfd => nfd)
}

Defunctionalizing Procedures and Computation

object HOF_CbNCPS_DFPC {
  sealed abstract class Imp

  case class Id(ind : Int) extends Imp
  case class Fun(body : Imp) extends Imp
  case class App(funExpr : Imp, argExpr : Imp) extends Imp

  type Env = List[Imp]

  case class ClosureV(body : Imp, env : Env) extends Imp
  case class Thunk(argExpr : Imp, env : Env) extends Imp

  type Cont = Imp => Imp

  def applyClosure(clo : Imp, cmp : Imp, k : Cont) : Imp = clo match {
    case ClosureV(body, closureEnv) => norm(body, cmp :: closureEnv, k)
  }

  def apTh(thk : Imp, k : Cont) : Imp = thk match {
    case Thunk(argExpr, thunkEnv) => norm(argExpr, thunkEnv, k)
  }

  def norm(imp : Imp, env : Env, k : Cont) : Imp = imp match {
    case Id(ind) => apTh(env(ind), k)
    case Fun(body) => k(ClosureV(body, env))
    case App(funExpr, argExpr) =>
      norm( funExpr, env
          , clo => applyClosure(clo, Thunk(argExpr, env), k) )
  }

  def interpret(imp : Imp) : Imp = norm(imp, Nil, nfd => nfd)
}

Defunctionalizing Continuation

object HOF_CbNCPS_DFPC_DFC {
  sealed abstract class Imp
  sealed abstract class Cont

  case class Id(ind : Int) extends Imp
  case class Fun(body : Imp) extends Imp
  case class App(funExpr : Imp, argExpr : Imp) extends Imp

  type Env = List[Imp]

  case class ClosureV(body : Imp, env : Env) extends Imp
  case class Thunk(argExpr : Imp, env : Env) extends Imp

  case class IdCont() extends Cont
  case class AppCont(argExpr : Imp, env : Env, k : Cont) extends Cont

  def applyClosure(clo : Imp, cmp : Imp, k : Cont) : Imp = clo match {
    case ClosureV(body, closureEnv) => norm(body, cmp :: closureEnv, k)
  }

  def apTh(thk : Imp, k : Cont) : Imp = thk match {
    case Thunk(argExpr, thunkEnv) => norm(argExpr, thunkEnv, k)
  }

  def applyCont(k : Cont, clo : Imp) : Imp = k match {
    case IdCont() => clo
    case AppCont(argExpr, contEnv, k) => applyClosure(clo, Thunk(argExpr, contEnv), k)
  }

  def norm(imp : Imp, env : Env, k : Cont) : Imp = imp match {
    case Id(ind) => apTh(env(ind), k)
    case Fun(body) => applyCont(k, ClosureV(body, env))
    case App(funExpr, argExpr) => norm(funExpr, env, AppCont(argExpr, env, k))
  }

  def interpret(imp : Imp) : Imp = norm(imp, Nil, IdCont())
}

Refactoring

object HOF_CbNCPS_DFP_DFC_Rfc {
  sealed abstract class Imp

  case class Id(ind : Int) extends Imp
  case class Fun(body : Imp) extends Imp
  case class App(funExpr : Imp, argExpr : Imp) extends Imp

  type Env = List[Imp]

  case class ClosureV(imp : Imp, env : Env) extends Imp

  type Cont = List[Imp]

  def norm(imp : Imp, env : Env, k : Cont) : Imp = imp match {
    case Id(ind) => env(ind) match {
      case ClosureV(argExpr, closureEnv) => norm(argExpr, closureEnv, k)
    }
    case Fun(body) => k match {
      case Nil => ClosureV(body, env)
      case ClosureV(argExpr, thunkEnv) :: k => norm(body, ClosureV(argExpr, thunkEnv) :: env, k)
    } 
    case App(funExpr, argExpr) => norm(funExpr, env, ClosureV(argExpr, env) :: k)
  }

  def interpret(imp : Imp) : Imp = norm(imp, Nil, Nil)
}

object HOF_CbVCPS {
  sealed abstract class Imp

  case class Id(ind : Int) extends Imp
  case class Fun(body : Imp) extends Imp
  case class App(funExpr : Imp, argExpr : Imp) extends Imp

  type Env = List[Imp]

  type Cont = Imp => Imp

  case class Prc(fun : Imp => Cont => Imp) extends Imp

  def norm(imp : Imp, env : Env, k : Cont) : Imp = imp match {
    case Id(ind) => k(env(ind))
    case Fun(body) => k(Prc(arg => k => norm(body, arg :: env, k)))
    case App(funExpr, argExpr) =>
      norm( funExpr, env
          , prc => norm( argExpr, env
                       , arg => prc match {
                            case Prc(fun) => fun(arg)(k)
                         } ) )
  }

  def interpret(imp : Imp) : Imp = norm(imp, Nil, nfd => nfd)
}

object HOF_CbVCPS_DFP {
  sealed abstract class Imp

  case class Id(ind : Int) extends Imp
  case class Fun(body : Imp) extends Imp
  case class App(funExpr : Imp, argExpr : Imp) extends Imp

  type Env = List[Imp]

  case class ClosureV(body : Imp, env : Env) extends Imp

  type Cont = Imp => Imp

  def applyClosure(prc : Imp, arg : Imp, k : Cont) : Imp = prc match {
    case ClosureV(body, closureEnv) => norm(body, arg :: closureEnv, k)
  }

  def norm(imp : Imp, env : Env, k : Cont) : Imp = imp match {
    case Id(ind) => k(env(ind))
    case Fun(body) => k(ClosureV(body, env))
    case App(funExpr, argExpr) =>
      norm( funExpr, env
          , clo => norm( argExpr, env
                       , arg => applyClosure(clo, arg, k) ) )
  }
}

object HOF_CbVCPS_DFP_DFC {
  sealed abstract class Imp
  sealed abstract class Cont

  case class Id(ind : Int) extends Imp
  case class Fun(body : Imp) extends Imp
  case class App(funExpr : Imp, argExpr : Imp) extends Imp

  type Env = List[Imp]

  case class ClosureV(body : Imp, env : Env) extends Imp

  case class IdCont() extends Cont
  case class ACL(argExpr : Imp, env : Env, k : Cont) extends Cont
  case class ACR(clo : Imp, k : Cont) extends Cont

  def applyClosure(prc : Imp, arg : Imp, k : Cont) : Imp = prc match {
    case ClosureV(body, closureEnv) => norm(body, arg :: closureEnv, k)
  }

  def norm(imp : Imp, env : Env, k : Cont) : Imp = imp match {
    case Id(ind) => k(env(ind))
    case Fun(body) => k(ClosureV(body, env))
    case App(opr, argExpr) =>
      norm( opr, env
          , clo => norm( argExpr, env
                       , arg => applyClosure(clo, arg, k) ) )
  }
}

 ****************
 * Rationalized *
 ****************/