16 Written: Control

These are due by midnight on Friday, May 1.

CPS

• Translate this program to continuation-passing style using the mechanical transformation from the lecture/reading (they describe the same algorithm):

  ((lam (x) (+ 1 x)) 5)
  
  # [or, in Pyret notation]:
  
  lam(x): 1 + x end(5)

  Feel free to use either notation.

• Indicate which function(s) in the output were inserted by the transformation, and which one corresponds to the lam in the input expression.

Stack Space and CPS

Any program that consumes some amount of stack, when converted to CPS and run, consumes no stack space at all. Why?

Update: Two clarifications. (1) This assumes that closures are allocated in the store, and (2) if it aids your understanding, consider the question with “no stack space at all” replaced with “a small constant amount of stack space.”

As a corollary, does conversion to CPS reduce the overall memory needed to run the program? Why or why not?

Efficient Exceptions

Consider this stack-based interpreter:

https://code.pyret.org/editor#share=0B32bNEogmncOY3ExdmNlRThDTnc&v=v0.5r852

• Consider the process of catching an exception, starting from the time the exception expression (exn in e-throw) is done evaluating and lasting until the catch block (catch in e-try-catch) starts evaluating. What is the time complexity, given in terms of the initial stack’s size, of this process?

• Describe a modification of the interpreter that gives an O(1) implementation strategy for this process. Feel free to actually modify the interpreter and submit that, or give a precise description. (Hint: It may involve changing data definitions.)