Midterm Solution

Substitution

It is impossible to avoid substitution at run time. Intuitively it is easy to see why: consider a recursive function with an argument called x. Even if we start with only one variable called x in the entire program, after a few recursive calls we might have more than one x and we should be careful not to confuse them.

Environments 

Check each axiom:

  (lookup (make_empty) x) 
= (lookup (lambda (x) (error ...)) x)
= ((lambda (x) (error ...)) x)
= (error ...)

  (lookup (make_extended env x v) x)
= (lookup (lambda (y) (if (eqv? x y) v (lookup env y))) x)
= ((lambda (y) (if (eqv? x y) v (lookup env y))) x)
= (if (eqv? x x) v (lookup env y)) 
= v

  (lookup (make_extended env x v) y)
= (lookup (lambda (y) (if (eqv? x y) v (lookup env y))) y)
= ((lambda (y) (if (eqv? x y) v (lookup env y))) y)
= (if (eqv? x y) v (lookup env y))
= (lookup env y)

Recursion to Iteration 

(define mult
  (lambda (m n)
    (if (zero? m)
	0
	(+ n (mult (sub1 m) n)))))

;; Step 1

(define multcps
  (lambda (m n k)
    (if (zero? m)
	(k 0)
	(multcps (sub1 m) n (lambda (v) (k (+ n v)))))))

;; Step 2

(define multcps
  (lambda (m n k)
    (if (zero? m)
	(apply k 0)
	(multcps (sub1 m) n (makek k n)))))

(define initk (lambda () (lambda (v) v)))
(define makek (lambda (k n) (lambda (v) (apply k (+ n v)))))
(define apply (lambda (k v) (k v)))

;; Axioms:
;; (apply (initk) v) = v
;; (apply (makek k n) v) = (apply k (+ n v))

(define initk (lambda () 0))
(define apply +)
(define makek +)

;; Check:
  (apply (initk) v) 
= (+ 0 v) 
= v

  (apply (makek k n) v) 
= (+ (+ k n) v)
= (+ k (+ n v))
= (apply k (+ n v))

Y Combinator 

Y = \f.(\x.f(x x)) (\x.f(x x)) 

  Y M 
= (\f.(\x.f(x x)) (\x.f(x x))) M
= (\x.M(x x)) (\x.M(x x))
= M ((\x.M(x x)) (\x.M(x x)))
= M (Y M)

Y (\x.x) = (\x.x) (Y (\x.x)) = Y (\x.x) = ... infinite loop

Y (\x.y) = (\x.y) (Y (\x.y)) = y

Program Execution

Run the following through Scheme or your own interpreter: 
(let ((x 1))
  (let ((x 2)
        (y x))
    (+ x y)))

(add1 (call/cc (lambda (k) (sub1 (k 3)))))

(let ((x 1))
  (let ((f (lambda (y) (+ x y))))
    (let ((x 2))
      (f 4))))

(let ((x 1))
  (let ((f (lambda (y) (let ((x y)) (lambda (g) (g (g x)))))))
    ((f 3) (let ((x x)) (lambda (z) (+ x z))))))

(let ((x 1))
  (let ((f (lambda (y) (+ x y))))
    (f ((lambda (d) x) (set! x 6)))))

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

Extra Credit

Look at the solution for the devils and angels problem that I posted in Scheme.

Visited times since March 23, 1999 (or the last crash).

sabry@cs.uoregon.edu