Due Tuesday, 31 March, 6am
The purpose of this homework problem is to understand the meaning of continuation conversions via the implementation of control operators.
Delivery Deliver your solutions in a folder called 10 in your github repo:
Step 1 0 Repair your interpreter from 5 —
Adapt your parser so that a seq* expression is represented as a combination of existing expressions. This kind of transformation is known as macro.
Change your cps transformation to eliminate "grab" before the interpreter gets to work on the code.
Besides Racket, a linguistic construct like "grab" is available in Haskell, OCaml, Scala, Scheme, and SML/NJ. An even stronger generalization was used in the runtime system of Microsoft’s Mach 4 (ultimately unsuccessful) operating system platform.
["stop", Toy], which eliminates its continuation and then evaluates its sub-expression to obtain the final answer.
Modify your interpreter to use constructs from your chosen implementation language to realize the behavior of "stop". We realize "stop" as a native construct (though we could also realize it in the same way as "grab").
The point of realizing "stop" as a native construct
permits us to exploit the semantic correctness theorem for cps from
Step 3 Design run, a program that accepts a Toy AST, converts it to continuation-passing style, constructs an application of the cpsed program to the function ["fun*", ["x"], ["stop", "x"]], and runs the interpreter on this application.
Remember Iterative Refinement from Fundamentals. Hint Deal with the first and third new construct first; then complete step 3 and return to the second expression.
Step 4 Get this generator test to evaluate via run. The expected result is 6, because the order of evaluation for "call" expressions is (still) right to left. If you replace the 3 in the using function with 2, the expected result is 111.
Figure 101 shows how to write this generator program in Racket. The require for "rename.rkt" imports four one-line definitions that give Toy names to Racket functionality. ~~ You may also wish to confirm that you can write this code in Python.
#lang racket (provide using using-exn) (require "rename.rkt") ;; - - - - - - - - - - - - - - - - - - - - - - - - - - ;; implementing a Python-style generator with 'grab' (define-syntax-rule (define/generator gen yield pythn) (define gen (local ((define (yield y) (grab c [(= resume (enter c)) y])) (define [[enter c] z] (grab k (= resume k) (c z))) (define resume [@ (enter (λ (x) (the-end (pythn x))))])) (λ (x) [(! resume) x])))) (define (the-end x) (raise (~a THE-END x))) (define THE-END "gen fell off the end ") ;; - - - - - - - - - - - - - - - - - - - - - - - - - - - ;; using the generator implementation (define/generator gen yield (λ [x] [letrec ([pythn (λ (x) (cond [(zero? x) using-exn] [else (yield x) (pythn (- x 1))]))]) (pythn x)])) (define using-exn 111) ;; - - - - - - - - - - - - - - - - - - - - - - - - - - - ;; a test client (define [using n] (let* ([x (gen n)] [y (gen 33)] [z (gen 33)]) (+ z y x))) (module+ test (require rackunit) (check-equal? (using 3) 6))
Testing Task Write the test harness xrun for your run program.
An input file in ITests contains a single Toy expression.
An output file in ITests contains a single JSON number or string ("closure", "cell", or one of the acceptable run-time error messages for untyped program: "variable ~a undeclared", "number of arguments does not match number of parameters", "primop domain error", "closure or primop expected". ; see 5 —
Simple Mutable Objects.)
Recall JSON: Simplicity and Complexity.