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