UNB/ CS/ David Bremner/ teaching/ cs4613/ assignments/ Assignment 4

Background

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 syntactic continuation based interpreter from Lecture 17 and add two arithmetic operations to it.

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.

(module+ test
  (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))
  )

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.

(module+ 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))
  )

Tests

Referring to the grading grading rubric for guidance, add any needed tests for your solution.

As always, make sure you have complete test coverage.