Sample Final 2

Date: Wednesday, April 23rd
[csu660]
[overview]
[resources]
[assignments]
 
Name:

Administrative

This exam was given last year

Question Grade  
(1) Scheme Programming /20
(2) Language Extension: Extending Scheme /20
(3) Language Extension: Extending (Compiled) Toy /15
(4) Language Features /25
(5) Programming in Lazy Scheme /20
(6) Type System /20
Total /120
 

Remember: the correct answers are short. Also, questions that ask for a verbal answer rather than code should still be answered correctly and based on facts.



 

Question 1: Scheme Programming

 20 pts 

Assume that MzScheme has a new built-in special form called pcons. This form works just like the cons function, except that the two argument expressions are evaluated in two threads at the same time. We will explore some ways in which this form can be used. The first thing we will do is use this form in a wrapper for running “slow functions”.
The idea is that if some function foo takes a long time to run, then the following code (using another MzScheme primitive: sleep) will return the value of (foo 3), except that a message will be printed every seconds saying that foo is running:
(letrec ([notify (lambda () (printf "working on ~s...\n" (list 'foo 3)) (sleep 1) (notify))]) (car (pcons (foo 3) (notify))))
Note that there is a problem in this code: pcons waits for the two sub-expressions to finish evaluating before it returns the resulting pair, and because (notify) never terminates, so does the whole expression.
Your job is to do fix and generalize this code. Write a function called slow-wrapper that consumes two arguments: a unary function (not necessarily numeric), and the name of the function. slow-wrapper then returns a function that is similar to the input function, except that it prints a ‘working’ message every second. An example of using this:
> (define (fib n) ...) > (define fib* (slow-wrapper fib 'fib)) > (fib* 35) working on (fib 35)... ... working on (fib 35)... 9227465


 

Question 2: Language Extension: Extending Scheme

 20 pts 

We want to use the pcons form to implement a kind of function application that evaluates its arguments in parallel. First, we need a new pmap function that is similar to map except that all computations are running at the same time. This is easy to implement — it looks just like a plain map except that the pcons form is used instead of a cons function:
;; pmap : (A -> B) (Listof A) -> (Listof B) ;; Similar to `map', except that all function applications happen at the ;; same time. (define (pmap f l) (if (null? l) null (pcons (f (car l)) (pmap f (cdr l)))))
The new kind of function application should be implemented as a pcall syntax:
(pcall fun x ...)
is the same as (fun x ...) except that all argument expressions are evaluated simultaneously. Define the pcall syntax.
Hint: you will need to use thunks and apply. Also, remember that this is a syntax transformation — you do not need to write a contract, but you do need a purpose statement.


 

Question 3: Language Extension: Extending (Compiled) Toy

 15 pts 

Adding a parallel pcall form is a nice toy to play with, but it would be interesting to try a language that is inherently parallel. At the end of this exam you will find parts of the extended Toy compiler from the solution to Assignment #7. Your job is to change the compiler so that arguments for function calls and for named expressions in a Bind are evaluated in parallel (you do not need to deal with BindRec). Do not copy the whole function, specify only the parts should change, and what they should change to.


 

Question 4: Language Features

 25 pts 

  1. Your friend notes that pcall is more general than pcons, and that the former could be used to implement the latter as follows:
    (define (pcons x y) (pcall cons x y))
    Is this a correct definition? Explain if it is, or fix if it is incorrect.
  2. Did the change to the extended Toy language function applications that you did in the previous question change its semantics? Explain if it did not change, otherwise write a counter-example.
  3. If the same change was applied to the lazy Sloth implementation, would its semantics change? Again, explain if so, or produce an example. (Be careful here!)
  4. If the same change was applied to a statically typed language like Picky, would its semantics change? Explain.


 

Question 5: Programming in Lazy Scheme

 20 pts 

Bob is now going through a minimalist phase. He keeps looking for ways to have fewer built-in functions in any language, including Lazy Scheme. His recent discovery is that there is no need for a null predicate — instead, he claims that you can simply compare the length of the list to zero. For example, according to his claim, the following definition of append is perfectly fine:
;; append : (Listof A) (Listof A) -> (Listof A) (define (append l1 l2) (if (zero? (length l1)) l2 (cons (car l1) (append (cdr l1) l2))))
Your job is to open Bob's eyes. Write an expression that uses append in a way that does not work with this implementation, but would work if null? was used instead.


 

Question 6: Type System

 20 pts 

In class we have designed the statically-typed ‘Picky’ language. We wrote a few typing judgments for it:
Γ |- n : Number Γ |- x : Γ(x) Γ |- a : Number Γ |- b : Number     Γ |- {+ a b} : Number Γ[x:=τ1] |- E : τ2     Γ |- {fun {x : τ1} : τ2 E} : (τ1 -> τ2) Γ |- f : (τ1 -> τ2) Γ |- v : τ1     Γ |- {call f v} : τ2 Γ |- v : τ1 Γ[x:=τ1] |- E : τ2     Γ |- {with {x : τ1 v} E} : τ2
 The rule for with was achieved using the following rewrite:
{with {x : τ v} E} ==> {call {fun {x : τ} E} v}
Assume that the language is further extended by a bind* which is similar to Scheme's let*. This requires two rewrite rules that translate uses of bind* to (nested) uses of with:
{bind* {{x1 : τ1 v1} {x : τ v} ...} E} ==> {with {x1 : τ1 v1} {bind* {{x : τ v} ...} E}} {bind* {} E} ==> E
You need to specify two matching typing rules for bind*. This can be done by deriving the rules in a similar way: begin with each form of bind*, perform the syntactic transformation, and find the goals that need to be proved.


 

The Basic TOY Implementation

The following are parts of the extended TOY compiler implementation from HW#7:

   <TOY> ::= <num>
           | <id>
           | { bind    {{ <id> <TOY> } ... } <TOY> <TOY> ... }
           | { bindrec {{ <id> <TOY> } ... } <TOY> <TOY> ... }
           | { fun  { <id> ... } <TOY> <TOY> ... }
           | { rfun { <id> ... } <TOY> <TOY> ... }
           | { if <TOY> <TOY> <TOY> }
           | { set! <id> <TOY> }
           | { <TOY> <TOY> ... }
...
;; compile : TOY -> (env -> VAL)
;; compiles TOY expressions to Scheme procedures
(define (compile expr)
  (unless (unbox compiler-enabled?)
    (error 'compile "compiler disabled"))
  (cases expr
    [(Num n)
     (let ([v (ScmV n)]) ; make the ScmV value in advance
       (lambda (env) v))]
    [(Id v)
     (lambda (env) (unbox (lookup v env)))]
    [(Bind names exprs bound-body)
     (let ([compiled-exprs (map compile exprs)]
           [compiled-body  (compile-body bound-body)])
       (lambda (env)
         (compiled-body
          (extend names
                  (map (lambda (c) (c env)) compiled-exprs)
                  env))))]
    [(BindRec names exprs bound-body)
     (let ([compiled-exprs (map compile exprs)]
           [compiled-body  (compile-body bound-body)])
       (lambda (env)
         (compiled-body (extend-rec names compiled-exprs env))))]
    [(Fun names bound-body)
     (let ([compiled-body (compile-body bound-body)])
       (lambda (env) (FunV names compiled-body env)))]
    [(RFun names bound-body)
     (let ([compiled-body (compile-body bound-body)])
       (lambda (env) (RFunV names compiled-body env)))]
    [(Call fun-expr arg-exprs)
     (let ([compiled-fun  (compile fun-expr)]
           [compiled-args (map compile arg-exprs)]
           [id-args       (and (andmap Id? arg-exprs)
                               (map Id-name arg-exprs))])
       (lambda (env)
         (let ([fval (compiled-fun env)]
               ;; delay the evaluation of arguments (use if needed)
               [arg-vals (lambda ()
                           (map (lambda (c) (c env)) compiled-args))])
           (cases fval
             [(PrimV proc) (proc (arg-vals))]
             [(FunV names compiled-body fun-env)
              (compiled-body (extend names (arg-vals) fun-env))]
             [(RFunV names compiled-body fun-env)
              (if id-args
                (let ([boxes (map (lambda (id) (lookup id env))
                                  id-args)])
                  (compiled-body (extend-boxes names boxes fun-env)))
                (error 'call "rfun expects only variable names"))]
             [else (error 'call "got a non-function: ~s" fval)]))))]
    [(If cond-expr then-expr else-expr)
     (let ([compiled-cond (compile cond-expr)]
           [compiled-then (compile then-expr)]
           [compiled-else (compile else-expr)])
       (lambda (env)
         ((if (cases (compiled-cond env)
                [(ScmV v) v] ; Scheme value => use as boolean
                [else #t])   ; other values are always true
            compiled-then
            compiled-else)
          env)))]
    [(Set id expr)
     (let ([compiled-expr (compile expr)])
       (lambda (env)
         (set-box! (lookup id env) (compiled-expr env))
         bogus))]))