UNB/ CS/ David Bremner/ teaching/ cs3613/ tutorials/ CS3613 Tutorial 8

Background

The example interpreter from Lecture 16 uses several new (to us) techniques including continuations

Roughly speaking, the Continuation Passing Style (CPS) takes a function call like

  (...stuff... (f ...args...) ...more-stuff...)

into

  (f/k ...args...
       (lambda (<*>)
         (...stuff... <*> ...more-stuff...)))

We'll learn more about continuations in the lectures, but today I want to take hands-on approach and modify an interpreter that uses CPS. This interpreter is higher level version of the one from Lecture 16, but uses CPS in the same way. This has several benefits, most obviously that the final eval function is tail-recursive. This is part of what lets our low-level interpreter work without a stack.

The overall goal of the lab is to add several arithmetic operations to the language.

Step 1

To get started, let's add support for a single argument decrement function. I've written it here as --, even though it doesn't mutate like -- does in most languages. Note that the parser already generates Sub1 abstract syntax for you.

In this "inside out" style, we need to call eval on the argument, with a last argument of "what to do next". The function continue will then handle processing the evaluated argument.

a. Define a variant doSub1K of the FAE-Cont type. Unlike the doSubK variant, it has no need to store a value for one of the arguments, because the only argument will be the parameter v of continue. So doSub1K needs only one field, which is an FAE-Cont (i.e. the next step).

At the same time add a dummy case to continue using ...., so your code compiles.

b. Mimic doSubK to define doSub1K. You can re-use num- by supplying a constant for one of it's arguments.

c. Fill in the case for Sub1 in eval, using (doSub1K k) as the third argument of your recursive call.

d. Your finished code should pass the following tests.

  (test (eval (parse `{-- 2}) (mtEnv) init-k) (NumV 1))
  (test (eval (parse `{{fun {x} {-- x}} 3}) (mtEnv) init-k) (NumV 2))
  (test (eval (parse `{{fun {y} {+ {-- y} {-- y}}} 10}) (mtEnv) init-k) (NumV 18))
  (test (eval (parse `{{fun {f} {f 4}} {fun {x} {-- x}}}) (mtEnv) init-k) (NumV 3))

2. Add Mul

The second part of the tutorial is to complete the definition for Mul. Since there are two arguments, we need to add two continuation steps. Luckily this works almost exactly the same as Add, and Sub, so you can copy and modify one of those cases. Note that you will probably want to define num*.

Your completed code (both parts) should pass the following test.

  (define fact-prog (parse
                 `{{fun {mkrec}
                        {{fun {fact}
                              ;; Call fact on 5:
                              {fact 5}}
                         ;; Create recursive fact
                         {mkrec
                          {fun {fact}
                               {fun {n}
                                    {if0 n
                                         1
                                         {* n {fact {-- n}}}}}}}}}
                   ;; mkrec:
                   {fun {body-proc}
                        {{fun {fX}
                              {fX fX}}
                         {fun {fX}
                              {body-proc {fun {x} {{fX fX} x}}}}}}}))
  (test (eval fact-prog (mtEnv)  init-k) (NumV 120))
(trace eval)
(trace continue)

(eval fact-prog (mtEnv) init-k)

This will produce lots of output, but see if you can make some educated guesses about the program flow.