Homework #9: Extending a continuation based interpreter
Out: Monday, March 27th, Due: Wednesday, April 5th, 4:30pm

Background

The language for this homework is:

#lang plait

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...)))

In this assignment you will start with the continuation based FLANG interpreter from Lecture 16 and add two arithmetic operations to it.

Part 1: Unary Decrement

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.

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

Define an FLANG variant Sub1, and parse -- to Sub1. You will need to add a stub to interp to get the code compiling and the following test passing
(test (parse `{-- 2}) (Sub1 (Num 2))))
Define a variant [doSub1K (k : Continuation)] of the Continuation type.
Add a case for Sub1 in interp (using doSub1K) and doSub1K in continue.

Your finished code should pass the following tests.

(test (run `{-- 2}) (NumV 1))
(test (run `{{lam {x} {-- x}} 3}) (NumV 2))
(test (run `{{lam {y} {+ {-- y} {-- y}}} 10}) (NumV 18))
(test (run `{{lam {f} {f 4}} {lam {x} {-- x}}}) (NumV 3))

Part 2: Multiplication

The second part of the assignment is to define (binary) multiplication. 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. Your completed code (both parts) should pass the following test.

(define fact-prog
         `{{lam {mkrec}
              {{lam {fact}
                    ;; Call fact on 5:
                    {fact 5}}
               ;; Create recursive fact
               {mkrec
                {lam {fact}
                     {lam {n}
                          {if0 n
                               1
                               {* n {fact {-- n}}}}}}}}}
         ;; mkrec:
         {lam {body-proc}
              {{lam {fX}
                    {fX fX}}
               {lam {fX}
                    {body-proc {lam {x} {{fX fX} x}}}}}}})

(test (run fact-prog) (NumV 120))

Finally

Ensure you have complete test coverage.

Define minutes-spent as the number of minutes you spent on your homework.

Homework #9: Extending a continuation based interpreterOut: Monday, March 27th, Due: Wednesday, April 5th, 4:30pm

Background

Part 1: Unary Decrement

Part 2: Multiplication

Finally

Homework #9: Extending a continuation based interpreter
Out: Monday, March 27th, Due: Wednesday, April 5th, 4:30pm