Lesson Plan - 6.001 SP04 - recitation 23

analyze evaluator & halting theorem

problem 1

(define (analyze-let exp)
  (let ((val-procs (map analyze (let-values exp)))
        (body-proc (analyze-sequence (let-body exp)))
        (vars (let-variables exp)))
    (lambda (env)
      (body-proc (extend-environment
                  vars
                  (map (lambda (v) (v env)) val-procs)
                  env)))))

free variable - sketch environment diagram, where can you insert
insert frames with variables that won't change things (bound
variables).

problem 2

x val +

problem 3

(define (free-in-list exps free)
  (if (null? exps)
      free
      (free-in-list (cdr exps)
		    (merge-freelists (free-in (car exps))
				     free))))

problem 4

(define (free-in exp)
  (cond ((self-evaluating? exp)
	 (empty-free))
	((variable? exp)
	 (single-free exp))
	((lambda? exp)
	 (fold-right bind-var
		     (free-in-list (lambda-body exp)
				   (empty-free))
		     (lambda-parameters exp)))
	((if? exp)
	 (free-in-list (cdr exp) (empty-free)))
	((definition? exp)
	 (bind-var (define-variable exp)
		   (free-in (define-value exp))))
	((assignment? exp)
	 (free-in-list (cdr exp) (empty-free)))
	((let? exp)
	 (free-in (let->application exp)))
	((application? exp)
	 (free-in-list exp (empty-free)))
	(else
	 (error "free-in unknown exp" exp))))

problem 5

contradiction

some functions uncomputable

countability
 -> mapping to integers
 -> can build a stream of them

uncountable (reals)

show more functions than programs

programs are countable (write it down in binary, convert to int)

functions uncountable - diagonalization

consider only predicate functions of 1 positive integer arguments

if countable, can build a table

f1 t t t t t t t t ...
f2 t f t f t f t f ...
f3 f f t t f f t t ...
...

build function not in table
output on input 1 is not(f1(1))
output on input 2 is not(f2(2))
..
countable # of inputs, # functions, 1 different input for each function
thus function is not in the table