Control

First, we'll give big-step semantics for IMP without break.

Evaluation relations:

• \(\evalStmt{\text{Statement}, \text{Store}}{\text{Store}}\)
• \(\evalExpr{\text{Expression}, \text{Store}}{\text{Value}}\)

We can add break to IMP by modifying the evaluation relation for statements as follows: \[ \evalStmtB{\text{Statement}, \text{Store}}{\text{Store}, \text{DidBreak?}} \] We now track an additional flag that tells us whether we are currently trying to break out of a loop.

We can update our semantics for IMP to track this flag:

Note that our semantics got quite a bit longer. We now have three rules for handling while and two for sequencing. In addition, every part of the semantics had to change to handle the break flag.

If we decided that we also wanted to add continue, we would have to make another significant modification to the semantics.

We can solve some of our issues with extensibility by switching to a continuation based semantics for IMP. If we keep around an explicit representation of "what to do next" (i.e. a continuation) we can more easily add language constructs that modify that continuation.

We change our evaluation relation to the following: \[\evalStmtK{\text{Continuation}, \text{Store}}{\text{Continuation}, \text{Store}}\] (We also switch to a small-step presentation, because it's a bit clearer.)

Continuations are defined to be either: the special stop continuation Kstop, a statement followed by a continuation Kseq, or a while loop followed by a continuation Kwhile. Formally, this is written \[ k : \text{Continuation} ::= \kstop ~|~ \mathsf{Kseq}\ s\ k ~|~ \kwhile\ e\ s\ k. \] We also define a shorthand for writing \(\mathsf{Kseq}\): \[\mathsf{Kseq}\ s\ k = s \kseqd k.\]

The semantics of IMP using continuations are:

The initial state of a program \(p\) is \(\langle p \kseqd \kstop, \emptyset \rangle\), and final states are of the form \(\langle \kstop, \sigma \rangle\). We define a multistep evaluation relation \(\rightarrow^{*}\) as usual: \[ \frac{ \evalStmtK{s \kseqd \kstop, \sigma}{k, \sigma'} \quad \langle k, \sigma' \rangle \rightarrow^* \langle \kstop, \sigma'' \rangle }{ \langle s \kseqd \kstop, \sigma \rangle \rightarrow^* \langle \kstop, \sigma'' \rangle } \]

Imagine that we are performing some computation, and we want to be able to finish the computation early. In this example, we have a tree with integers at the leaves, and we want to take a product of the leaf values. Recursion is the most natural way to write this program:

let tree = {
  left: 3,
  right: {
    left: 1,
    right: 2
  }
};
function tree_product(t) {
  if (typeof t === 'number') {
    return t;
  } else {
    return tree_product(t.left) * tree_product(t.right);
  }
}

console.log(tree_product(tree));

6

We might like to finish this function early if one of the leaves is zero, to avoid looking at the rest of the tree. We could rewrite our function to use iteration instead of recursion, so we could use an early return, but we have another option.

If we instead translate our code into CPS, adding an early return is straightforward, even one that returns from deep in a stack of recursive calls.

function tree_product_cps(t, k) {
  console.log('tree product', t);
  if (typeof t === 'number') {
    k(t);
  } else {
    tree_product_cps(t.left, function(left) {
      tree_product_cps(t.right, function(right) {
	k(left * right);
      })
    });
  }
}

tree_product_cps(tree, console.log);

tree product { left: 3, right: { left: 1, right: 2 } }
tree product 3
tree product { left: 1, right: 2 }
tree product 1
tree product 2
6

Here's the version that returns early. We pass an additional "early return" continuation, which allows us to avoid looking at the remaining tree once we have seen a zero.

let tree = {
  left: {
    left: 0,
    right: 2
  },
  right: {
    left: 1,
    right: 3
  }
};

function tree_product_cps(t, k_early_return, k) {
  console.log('tree product', t);
  if (typeof t === 'number') {
    if (t === 0) {
      k_early_return(t);
    } else {
      k(t);
    }
  } else {
    tree_product_cps(t.left, k_early_return, function(left) {
      tree_product_cps(t.right, k_early_return, function(right) {
	k(left * right);
      })
    });
  }
}

tree_product_cps(tree, console.log, console.log);

tree product { left: { left: 0, right: 2 }, right: { left: 1, right: 3 } }
tree product { left: 0, right: 2 }
tree product 0
0

Exceptions are a close cousin of non-local exits. We could use the early exit continuation as a "failure continuation," and that would let us write programs that fail. If we want more standard exception handling with try/catch and throw, we have to do a little bit of additional work.

The following example shows how we could write a simple version of try/catch and throw for programs in CPS. The try_catch function takes two functions---body and on_exn—and a continuation k. Execution begins with body (the try clause of the try-catch), but if throw_ is called inside body, execution jumps to on_exn (the catch clause). Execution continues with k after either the body completes or it raises an exception.

We use a stack of exception handlers handlers to keep track of catch clause to execute. When we enter a try-catch, we push the handler onto the stack. When we finish the body of the try-catch, we pop the handler off and continue. When throw_ is called, we discard whatever computation remains after throw_ and call the topmost handler, popping it off the stack.

let handlers = [];

function try_catch(body, on_exn, k) {
  handlers.push(function () {on_exn(k);});
  body(function (x) {
    handlers.pop();
    k(x);
  });
}

function throw_(k) {
  handlers.pop()();
}

try_catch(function(k) {
  console.log('Starting computation.');
  try_catch(function(k) {
    console.log('Trying out nested exceptions...');
    throw_(k);
  }, function(k) {
    console.log('Caught nested exception. Ignoring.');
    k();
  }, function(k) {
    console.log('Starting actual work.');
    tree_product_cps(tree, throw_, k);
  });
}, function(k) {
  console.log('Caught an exception! Returning dummy value -1.');
  k(-1);
}, function(prod) {
  console.log(`Computed product ${prod}`);
})

Starting computation.
Trying out nested exceptions...
Caught nested exception. Ignoring.
Starting actual work.
tree product { left: { left: 0, right: 2 }, right: { left: 1, right: 3 } }
tree product { left: 0, right: 2 }
tree product 0
Caught an exception! Returning dummy value -1.
Computed product -1

This implementation of exceptions doesn't support throwing and catching named exceptions (e.g. RuntimeError, SyntaxError, etc). We can add this feature in a straightforward way by adding a new handler stack for each kind of exception.