## Sample problems

### Easy to moderate problems

• 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 (y-1))

and odd y =
if y = 0
then false
else (x := !x + 1;
even (y-1))
```

• 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 store-passing 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
```

• 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