►Principles of Programming Languages
▼Assignments
•10 — Control
7.7.0.3
    ← prev  up  next → 

10 — Control

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:

        

        10 /

           xrun

           Other/

           ITests/

             [0-9]-in.json

             [0-9]-out.json

A name ending in / is a folder, and indentation means “contained in the closest folder listed above the current name.”

Programming Task

Step 1 0 Repair your interpreter from 5 — Simple Mutable Objects in case it failed test cases in the past. The prelude must contain "+", "*", "^", "@", "!", and "=".

Step Extend Toy with the following constructs:

  • ["seq*", Toy, Toy, ..., Toy], which evaluates the non-empty sequence of Toy expressions in order and returns the result of the last expression as its own.

    Adapt your parser so that a seq* expression is represented as a combination of existing expressions. This kind of transformation is known as macro.

  • ["grab", Var, Toy], which turns the continuation of the grab expression into a closure, binds it to the specified Var, and evaluates the “body” expression to obtain a value.

    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.

    See for some poetic sample uses (in plain Racket) of this still-unusual construct.

  • ["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").

I will get back to the idea of implementing different constructs in different parts of the model during the last week, when I will lecture on the expressive power of programming languages.

The point of realizing "stop" as a native construct permits us to exploit the semantic correctness theorem for cps from 20 — Control from CPS to debug your implementation.

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 123 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.

Code/10/Other/generator.rkt

  #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))
   

Figure 123: A Python-style Generator from grab

Testing Task Write the test harness xrun for your run program.

Create ten tests for xrun. Place them in ITests/. A test consists of three files: N-in.json N-cps.json and N-out.json for N in [0 .. 9]:

  • 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.

    ← prev  up  next →