▼Make your own meta-circular evaluator!
►8 Refactoring to CPS
On this page:
8.1 Some stuff will have a continue-parameter
8.1.1 (eval-exp env continue exp)
8.1.2 (eval-sequence env continue exps)
8.1.3 (eval-application env continue fun args)
8.1.4 Our “primitives”
8.1.5 (make-function env parameters body)
8.1.6 (evaluate input)
8.2 So that did nothing
8.3 Couple of tips, maybe
8.4 Done?
7.2
    ← prev  up  next → 

8 Refactoring to CPS

If we’ve been through the previous part, we can keep using the same file. Or we can use 4-functions.rkt as our starting point.

CPS, besides being weird, is kind of neat. If you’re implementing a function, and the “continuation” —everything that is to happen after— is made available to you as a function, then, uh, that’s a thing you’re in control of.
You can decide not to invoke the continuation. Or you can try to invoke the continuation several times, with different values. Later on we want to use an amb-form for expressions that can have multiple possible values: We want to “continue” with some value, and if that turns out to be no good, we want to try some other value instead. CPS seems like a good fit.

8.1 Some stuff will have a continue-parameter

We will rewrite a few functions so they have a continue-parameter, and so that, instead of returning a result, they apply continue to a result. We will put continue just after env in the parameter lists. E.g. eval-application will go like (eval-application env continue fun args).

8.1.1 (eval-exp env continue exp)

eval-exp isn’t too bad. In most of the match-clauses we return a value pretty directly. In those cases we will pass the values along to continue instead. In the case where we call eval-application, we will pass our continue along to eval-application and put it in after env parameter. The same goes for eval-sequence.

8.1.2 (eval-sequence env continue exps)

The cases where we have some rest-expressions are a little trickier. In, say, the 'define-case, we must make a continuation-function to use with eval-exp. Like:

(eval-exp env
          (λ (value)
            your code here)
          exp)

Within this continuation-function, we will do the stuff we previously did after the call to eval-exp: Extend the environment and call eval-sequence again. We will pass our “original” continue to eval-sequence.

8.1.3 (eval-application env continue fun args)

Maybe the trickiest. We must evaluate the fun-expression with eval-exp, with a continuation that deals with the arguments. For every argument in the list, there will be a call to eval-exp with a continuation that deals with the rest of the arguments and performing the function application. Along the way we must keep track of the arguments we have evaluated. Finally, the function we are going to apply will take a continue-argument before the evaluated args: We will pass our continue-parameter along to it.
It is likely that evaluating the arguments is the hardest bit. We probably want this:
(define (eval-arguments env continue args)
  (match args
    ['() your code here]
    [(list arg rest ...) your code here]))
In '()-case: Evaluating all the arguments in the empty list is maybe not too hard?
In the (list arg rest ...)-case: We want to eval-exp the arg, then eval-arguments the rest of the arguments, and then cons the evaluated argument onto the evaluated rest-of-the-arguments. Like, we’re really “just” trying to map eval-exp over args. Having to work out what needs to go in which continuation makes things more confusing though.

8.1.4 Our “primitives”

Instead of e.g. the +-function we want a function that has a continue-argument first:

(define (my-plus continue . args)
  your code here)

When this function is applied, all the arguments after the continue are collected in args, as a list. We can use the apply-function to apply the original +-function to the args. (And we want to apply continue to the result rather than just returning it.)

It is pretty possible, while not exactly necessary, to make a helper-function for this. One that takes a regular function as its argument and returns a more CPS-compliant function. Something along the lines of
(define (primitive function)
  (λ (continue . args)
    your code here))

could be convenient.

8.1.5 (make-function env parameters body)

We’re not adding a continue-parameter to make-function function, but we need to add it to the function returned by make-function. That continue should be passed in as the second argument to eval-sequence.

8.1.6 (evaluate input)

For now, we want evaluate to work the same way as before, so we are not adding a continue-parameter to it. But it does use eval-exp so we need to add a continue-argument there. We will use Racket’s identity-function.

8.2 So that did nothing

So, if we got things right then we have kind of made no changes. Under the hood things work differently, but there are no new features and all the expressions in the language we’re making should evaluate to the same values.

How dull? On the plus side we didn’t have to write any new tests...

8.3 Couple of tips, maybe

Okay so this stuff is like not straightforward. Because CPS. Also because we have to change a bunch of of interdependent functions: We change one and everything breaks. So. Two tips:
One tip: Use Racket’s identity-function for stuff. If you pass identity in as the continue-argument to a function, then identity should just return the result we’re intersted in.
Another tip: Maybe change eval-exp so that it handles the simplest expression, the literals, correctly first, and let everything else break. Then, when rewriting each “feature” to CPS, we can test them with expressions where all the subexpressions are just literals. E.g. when working on eval-arguments, just use a list of numbers for the args to begin with.

8.4 Done?

Run and see that all the tests pass.
Next is Booleans. We can keep using the Racket-file we’re working with, or skip to 5-continuation-passing-style.rkt.

    ← prev  up  next →