CS440 Programming Languages - Machine Problems 3: Continuation Passing Style and Multitasking API
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)
1. Implement the factorial& function in CPS. E.g.,
2. Implement the map& function in CPS. Assume that the argument function is not written in CPS.
3. Implement the filter& function in CPS. Assume that the argument predicate is not written in CPS.
4. Implement the filter&& function in CPS. Assume that the argument predicate is written in CPS.
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:
spawn: Creates a new fiber. Similar to the Unix fork system call, when spawn is called it will return twice with different values. In our
implementation, it will return first with the value #t (true) and then again with the value #f (false).
yield: Performs a context switch to the next fiber, if there is one. I.e., returns back into the context of another fiber and resumes
executing it.
terminate: Terminates the calling fiber.
For these functions to work, you will need to maintain a global queue of fibers (using a list), which is updated as necessary.
> (factorial& 0 identity)
1
> (factorial& 5 add1)
121
> (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)
(define (even n)
(= 0 (remainder n 2)))
> (filter& even (range 10) identity) '(0 2 4 6 8)
(define (even& n k)
(k (= 0 (remainder n 2))))
> (filter&& even& (range 10) identity) '(0 2 4 6 8)
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
(terminate))
(begin (println
(yield)
(println
(if (spawn)
(begin (println (yield)) (begin (println (println (println "Cleaning up")
(terminate))
** **** ***** ***
fiber 1")
"In
"Back in fiber 2")))
"In fiber 3")
"In fiber 4")
"Still in fiber 4"))))
fiber 2")
Details and Hints
In our implementation a fiber is, simply, a continuation. spawn, yield, and terminate will all work by either creating and enqueueing a continuation and/or calling a continuation (possibly obtained by dequeueing) with the appropriate argument.
For debugging purposes, spawn will print <SPAWN> when it is invoked, yield will print <CST>, and terminate will print <TERM>. Additionally, if terminate discovers that the global queue is empty, it will print <QUEUE-EMPTY>.
You will not need to write much code for this part! As a sanity check, our implementations of spawn, yield, and terminate total around 5 lines of code each (with maybe another 8 lines for queue-related code).
Please reach out if you get stuck!
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).
"<SPAWN>"
"<SPAWN>"
"In fiber
"<TERM>"
"<SPAWN>"
"In fiber
"<CST>"
"In fiber
"<CST>"
"In fiber
"Still in
"Cleaning
"<TERM>"
"Cleaning
"<TERM>"
"Back in fiber 2"
"Cleaning up"
"<TERM>"
"<QUEUE-EMPTY>"
1"
3"
2"
up"
4"
fiber 4"
up"
