CS 440 MP3

Overview

In this machine problem you will practice writing some functions in continuation passing style (CPS), and implement a simple lightweight multitasking API using first-class continuations (call/cc).

Exercises

Part 1: Continuation Passing Style (16 points)

Before starting on the following exercises, it might help to review the lecture notes on CPS. Inspect the definitions of sum& and sum2& for examples of CPS.

  1. Implement the factorial& function in CPS. E.g.,

    > (factorial& 0 identity)
    1
    
    > (factorial& 5 add1)
    121
    
  2. Implement the map& function in CPS. Assume that the argument function is not written in CPS. You should not use the built-in map.

    > (map& add1 (range 10) identity)
    '(1 2 3 4 5 6 7 8 9 10)
    
    > (map& (curry * 2) (range 10) reverse)
    '(18 16 14 12 10 8 6 4 2 0)
    
  3. Implement the filter& function in CPS. Assume that the argument predicate is not written in CPS. You should not use the built-in filter.

    (define (even n)
      (= 0 (remainder n 2)))
    
    > (filter& even (range 10) identity)
    '(0 2 4 6 8)
    
  4. Implement the filter&& function in CPS. Assume that the argument predicate is written in CPS. You should use neither the built-in filter nor filter& from the previous exercise.

    (define (even& n k)
      (k (= 0 (remainder n 2))))
    
    > (filter&& even& (range 10) identity)
    '(0 2 4 6 8)
    

Part 2: Fibers with call/cc (18 points)

Using first-class continuations, we can implement a lightweight unit of cooperative-multitasking known as a fiber. We will do this by implementing the following functions:

For these functions to work, you will need to maintain a global queue of fibers (using a list), which is updated as necessary.

Here are some test functions that make use of the above API, along with their output when run:

    (define (test1)
      (if (spawn)
          (begin (println "In fiber 1")
                 (terminate))
          (begin (println "In fiber 2")
                 (terminate))))

    "<SPAWN>"
    "In fiber 1"
    "<TERM>"
    "In fiber 2"
    "<TERM>"
    "<QUEUE-EMPTY>"

    * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

    (define (test2)
      (if (spawn)
          (begin (println "In fiber 1")
                 (yield)
                 (println "Back in fiber 1")
                 (terminate))
          (begin (println "In fiber 2")
                 (yield)
                 (println "Back in fiber 2")
                 (terminate))))

    "<SPAWN>"
    "In fiber 1"
    "<CST>"
    "In fiber 2"
    "<CST>"
    "Back in fiber 1"
    "<TERM>"
    "Back in fiber 2"
    "<TERM>"
    "<QUEUE-EMPTY>"

    * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

    (define (test3)
      (if (spawn)
          (if (spawn)
              (begin (println "In fiber 1")
                     (terminate))
              (begin (println "In fiber 2")
                     (yield)
                     (println "Back in fiber 2")))
          (if (spawn)
              (begin (println "In fiber 3")
                     (yield))
              (begin (println "In fiber 4")
                     (println "Still in fiber 4"))))
      (println "Cleaning up")
      (terminate))

    "<SPAWN>"
    "<SPAWN>"
    "In fiber 1"
    "<TERM>"
    "<SPAWN>"
    "In fiber 3"
    "<CST>"
    "In fiber 2"
    "<CST>"
    "In fiber 4"
    "Still in fiber 4"
    "Cleaning up"
    "<TERM>"
    "Cleaning up"
    "<TERM>"
    "Back in fiber 2"
    "Cleaning up"
    "<TERM>"
    "<QUEUE-EMPTY>"

Details and Hints

Testing

We have provided you with test cases in "mp3-test.rkt". Feel free to add to and alter any and all tests, as we will be using our own test suite to evaluate your work.

No tests are included for part 2, as we will be inspecting your implementation and its functionality manually.

Grading

Each exercise in part 1 is worth 4 points for a total of 16 points.

Each function in part 2 is nominally worth 6 points for a total of 18 points, though we will award credit for your implementation as a whole.

The maximum possible points = 16 + 18 = 34

Submission

When you are done with your work, simply commit your changes and push them to our shared private GitHub repository. Please note that your submission date will be based on your most recent push (unless you let us know to grade an earlier version).