%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
ML; Scope (15 points)

What do the following ML expressions evaluate to:

let fun f x = x+x
in f 7
end 
------------------------ 14
let fun f x = x+x
    val x = 3
in f 7 
end
------------------------ 14
let val x = 3
   fun f x = x+x
in f 7
end
------------------------ 14
let val x = 3
   fun f y = x+y
in f 7
end
------------------------ 10
let val x = 3
    fun f y = x+y
in let val x = 5
   in f 7
   end
end 
------------------------ 10
let val g = let val x = 3
                fun f y = x+y
            in f 
            end
in let val x = 5
   in g 7
   end 
end
------------------------ 10
let val x = 3
    fun f y = x+y
in let val x = 4
       fun g h = h (h 7)
   in g f
   end
end 
------------------------ 13

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
CPS (10 points)

Convert the function preorder to CPS. Do not convert the functions ::
(cons) and @ (append) to CPS; just use them as they are in the CPS
version of preorder:

datatype tree = 
    Empty
  | Bin of int * tree * tree

fun preorder Empty = []
  | preorder (Bin(i,t1,t2)) = i :: ((preorder t1) @ (preorder t2))

fun preordercps Empty k = k []
  | preordercps (Bin(i,t1,t2)) k = 
    preordercps t1 (fn l1 =>
    preordercps t2 (fn l2 => 
    k (i :: (l1 @ l2))))

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Streams (20 points)

Given the following datatype for streams:

datatype stream = S of int * (unit -> stream)

1. Write a function genOnes that generates a stream in which every
element is a 1, i.e., generate the stream that represents an infinite
sequence of ones.

fun genOnes () = S (1, fn () => genOnes())

2. Write a function addStreams that takes two streams s_1 and s_2 and
produces a stream s such that the ith element in s is the sum of the
ith elements in s_1 and s_2.

fun addStreams (S(i1,f1)) (S(i2,f2)) = 
    S (i1+i2, fn () => addStreams (f1()) (f2()))

3. What would the stream s below represent?

fun genS () = S(1, fn () => addStreams (genOnes()) (genS()))
val s = genS()

It is the stream of positive natural numbers 1,2,3,4,5,6,...

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
beta-Reduction (15 points)

Using the beta-rule of the lambda-calculus, evaluate the following
expressions. Show the intermediate steps:

  (((lambda f.f) (lambda x.x)) 3)
= ((lambda x.x) 3)
= 3 

  ((lambda x.(x (lambda x.x+x))) (lambda f.(f 3)))
= ((lambda f.(f 3)) (lambda x.x+x))
= ((lambda x.x+x) 3)
= 3+3
= 6

  ((lambda y.(((lambda x.(lambda y.x+y)) y) 4)) 3)
= (((lambda x.(lambda y.x+y)) 3) 4)
= ((lambda y.3+y) 4)
= 3+4
= 7

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
CPS Interpreters (25 points)

Here is an almost conventional interpreter for a small functional
language. Instead of raising errors using an exception mechanism, this
interpreter uses a value Error that is propagated just like other
values.

datatype prim = Plus

datatype exp = 
    Num of int
  | Primapp of exp * prim * exp
  | Var of string
  | Fun of string * exp
  | App of exp * exp 

datatype value = 
    Int of int
  | Error
  | Closure of string * exp * env
withtype env = (string * value) list

fun lookup [] y = Error
  | lookup ((x,v)::env) y = if x=y then v else lookup env y
fun extend env x v = (x,v) :: env

fun add (Int i1) (Int i2) = Int (i1+i2)
  | add _ _ = Error

fun interp (Num i) env = Int i
  | interp (Primapp(e1,Plus,e2)) env = add (interp e1 env) (interp e2 env)
  | interp (Var s) env = lookup env s
  | interp (Fun(s,e)) env = Closure(s,e,env)
  | interp (App(e1,e2)) env = 
    let val f = interp e1 env
        val a = interp e2 env
    in case f of 
        Closure(s,e,env) => interp e (extend env s a)
      | _ => Error
    end

Your job is to convert the function interp to CPS. Do not convert
lookup, extend, and add to CPS; just use them as they are in the CPS
version of interp. Try to optimize the propagation of Error values in
the CPS version.

fun interpcps (Num i) env k = k (Int i)
  | interpcps (Primapp(e1,Plus,e2)) env k = 
    interpcps e1 env (fn v1 => 
    interpcps e2 env (fn v2 => 
    k (add v1 v2)))
  | interpcps (Var s) env k = k (lookup env s)
  | interpcps (Fun(s,e)) env k = k (Closure(s,e,env))
  | interpcps (App(e1,e2)) env k = 
    interpcps e1 env (fn f => 
    interpcps e2 env (fn a => 
    case f of 
      Closure(s,e,env) => interpcps e (extend env s a) k
    | _ => Error))

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Combinatory Logic (15 points)

Combinatory logic is another formalism related to the
lambda-calculus. It consists of two constants S and K and one
operation: application. The semantics of the language is given by just
two rules. For any terms x, y, and z:

S x y z = x z (y z) 
K x y = x 

Surprisingly, combinatory logic is also a universal language!

Your job is to write an interpreter for combinatory logic. The
abstract syntax of the language is:

datatype cl = S | K | App of cl * cl

The set of possible values is:

datatype clvalue = S0 | S1 of cl | S2 of (cl*cl) | K0 | K1 of cl 

The values have the following intuitive meaning: 
* S0 is the result of evaluating the constant S, 
* S1(cl) is the result of evaluating the application of the
constant S to the argument cl, 
* S2(cl1,cl2) is the result of evaluating the application
of the constant S to the two arguments cl1 and cl2. 
* K0 is the result of evaluating the constant K, 
* K1(cl) is the result of evaluating the application of the
constant K to the argument cl.

Note that applying the original constant S to x, y, and z is
equivalent to applying S2(x,y) to z.

fun interp S = S0
  | interp K = K0
  | interp (App(cl1,a)) = 
    case (interp cl1) of 
        S0 => S1 a
      | S1 cl => S2 (cl,a)
      | S2 (cl1,cl2) => interp (App(App(cl1,a),App(cl2,a)))
      | K0 => K1 a
      | K1 cl => interp cl

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%