 Draw an arrow from each use of a variable to its binding
occurrence. No arrow should come out of a free variable.
((lambda (x)
((lambda (x) (x x))
x))
x)
class A {
int i = 0;
int m (int i) { return i + k (); }
int k () { return i; }
}
}
let x = 1 in
let y = x in
let x = y in
x + y
 What does each of the following Ocaml expressions evaluate to:
let f x = x + x in
f 7

let f x = x + x in
let x = 3 in
f 7

let x = 3 in
let f x = x + x in
f 7

let x = 3 in
let f y = x + y in
f 7

let x = 3 in
let f y = x + y in
let x = 5 in
f 7

let g = (let x = 3 in
let f y = x + y in
f)
in let x = 5
in g 7

let x = 3 in
let f y = x + y in
let x = 4 in
let g h = h (h 7) in
g f
 Convert the following Scheme definitions to DeBruijn notation in
which binding occurrences of variables are eliminated, and every use
of a bound variable is replaced by a number which represents how many
lambdas we have to cross to reach the binder for the variable. Free
variables should remain intact.
((lambda (x)
((lambda (x) (x x))
x))
x)
 Here are two recursive functions which communicate via a shared
reference that they update:
let x = ref 0
let rec even y =
if y = 0
then true
else (x := !x + 1;
odd (y1))
and odd y =
if y = 0
then false
else (x := !x + 1;
even (y1))
 What is the content of the reference
x
after a call
to even 1000
terminates?
 Rewrite the functions to eliminate the shared global variable
x
using a simplified storepassing style.
 Solution
 Trace the execution of the following Scheme program showing the
contents of the environment before and after each evalution step:
(let ((x 1))
(let ((f (lambda (y) (+ x y))))
(let ((x 2))
(f x))))
(Solution)
 What are the values of the following Scheme expressions:
(define exp_1
(let ((x 1))
(let ((x 2)
(y x))
(+ x y)))
)
(define exp_2
(let ((x 1))
(let ((f (lambda (y) (+ x y))))
(let ((x 2))
(f 4))))
)
(define exp_3
(let ((x 1))
(let ((f (lambda (y) (let ((x y)) (lambda (g) (g (g x)))))))
((f 3) (let ((x x)) (lambda (z) (+ x z))))))
)
(define exp_4
(let ((x 1))
(let ((f (lambda (y) (+ x y))))
(f ((lambda (d) x) (set! x 6)))))
)
(define exp_5
(letrec ((fact (lambda (n r)
(if (zero? n)
r
(fact (sub1 n) (* n r)))))
(memoized_fact (let ((arg 0) (result 1))
(lambda (n)
(if (= arg n)
result
(let ((r (begin
(printf "Calling fact~n")
(fact n 1))))
(begin (set! arg n)
(set! result r)
result)))))))
(begin
(memoized_fact 5)
(memoized_fact 5)
(memoized_fact 5)))
)

For this problem, we will consider the problem of
typechecking a tiny language of expressions. Here is the code
for the definitions and typechecker:
type bop = Plus  Div  Eq
type exp =
Number of int
 True  False
 Binary of exp * bop * exp
type exptype = Int  Bool
exception TypeError
let rec tc exp = match exp with
Number i > Int
 True > Bool
 False > Bool
 Binary (e1,bop,e2) >
let t1 = tc e1 in
let t2 = tc e2 in
match (t1,bop,t2) with
(Int,Plus,Int) > Int
 (Int,Div,Int) > Int
 (t1,Eq,t2) > if t1=t2 then Bool else raise TypeError
 _ > raise TypeError
Answer the following questions:
 Write an expression in our little language that fails to
typecheck.
 Write an expression in our little language that typechecks but
would cause an error if later executed.
 We are going to extend the type
exp
by adding the
following two lines:
 Let of string * exp * exp
 Var of string
For example, we can write:
Let("x", Number(3), Binary(Var "x", Plus, Variable "x"))
Extend the typechecker to handle the additional two cases.
 Solution