6.001 Recitation – April 23, 2003

RI: Konrad Tollmar

www.ai.mit.edu/~konrad/6001/

• Analyse – “a compiler”

• Computational & non-computational processes

1. Analyze Evaluator

• Analyze the program first, then run it
• The analyzed program is a procedure of one argument: the environment
• Running a program is just calling the procedure with the environment as input

(define (eval exp env)
 ((analyze exp) env))
 
(define (analyze exp)
 (cond ((self-evaluating? exp)
 (analyze-self-evaluating exp))
 ((quoted? exp) (analyze-quoted exp))
 ((variable? exp) (analyze-variable exp))
 ((assignment? exp) (analyze-assignment exp))
 ((definition? exp) (analyze-definition exp))
 ((if? exp) (analyze-if exp))
 ((lambda? exp) (analyze-lambda exp))
 ((begin? exp) (analyze-sequence (begin-actions exp)))
 ((cond? exp) (analyze (cond->if exp)))
 ((application? exp) (analyze-application exp))
 (else
 (error "Unknown expression type -- ANALYZE" exp))))
 
(define (analyze-self-evaluating exp)
 (lambda (env) exp))
 
(define (analyze-variable exp)
 (lambda (env) (lookup-variable-value exp env)))
 

(define (analyze-if exp)
 (let ((pproc (analyze (if-predicate exp)))
 (cproc (analyze (if-consequent exp)))
 (aproc (analyze (if-alternative exp))))
 (lambda (env)
 (if (true? (pproc env))
 (cproc env)
 (aproc env)))))
 
(define (analyze-lambda exp)
 (let ((vars (lambda-parameters exp))
 (bproc (analyze-sequence (lambda-body exp))))
 (lambda (env) (make-procedure vars bproc env))))
 
(define (analyze-sequence exps)
 (define (sequentially proc1 proc2)
 (lambda (env) (proc1 env) (proc2 env)))
 (define (loop first-proc rest-procs)
 (if (null? rest-procs)
 first-proc
 (loop (sequentially first-proc (car rest-procs))
 (cdr rest-procs))))
 (let ((procs (map analyze exps)))
 (if (null? procs)
 (error "Empty sequence -- ANALYZE"))
 (loop (car procs) (cdr procs)))) 
 
(define (analyze-application exp)
 (let ((fproc (analyze (operator exp)))
 (aprocs (map analyze (operands exp))))
 (lambda (env)
 (execute-application (fproc env)
 (map (lambda (aproc) (aproc env))
 aprocs)))))
 
(define (execute-application proc args)
 (cond ((primitive-procedure? proc)
 (apply-primitive-procedure proc args))
  ((compound-procedure? proc)
 ((procedure-body proc)
 (extend-environment (procedure-parameters proc)
 args
 (procedure-environment proc))))
 (else (error "Unknown procedure type -- EXECUTE-APPLICATION"
 proc))))

Notice that there are no calls to analyze at run time!

Analyzing expressions

Analyze the following expressions. (Note: this is equivalent to calling (analyze <exp>), NOT ((analyze <exp>) <env>). Your result in each case should be a procedure of one argument.)

1. (analyze 0)

2. (analyze x)

3. (analyze (> x 0))

4. (analyze (if (> x 0) x (- x)))

5. (analyze (lambda (x) (if (> x 0) x (- x))))

6. (analyze ((lambda (x) (if (> x 0) x (- x))) -4))

Add While
We want a special form called while with the following behavior:
(while <text-exp> <exp1> <exp1> ... <expn>) will first evaluate the <test-exp> expression. If it is true, then while will evaluate each of the consequence expressions in turn and recurse. If the <test-exp> is false, then the while returns the value false immediately.

Add the while special form to the analyze evaluator.

2. Computational & non-computational processes

1. Universal Machines

2. Turing machines
3. Halting problem

A Turing machine is an abstract representation of a computing device. It consists of a read/write head that scans a (possibly infinite) one-dimensional (bi-directional) tape divided into squares, each of which is inscribed with a 0 or 1. Computation begins with the machine, in a given "state", scanning a square. It erases what it finds there, prints a 0 or 1, moves to an adjacent square, and goes into a new state. This behavior is completely determined by three parameters: (1) the state the machine is in, (2) the number on the square it is scanning, and (3) a table of instructions. The table of instructions specifies, for each state and binary input, what the machine should write, which direction it should move in, and which state it should go into. (E.g., "If in State 1 scanning a 0: print 1, move left, and go into State 3".) The table can list only finitely many states, each of which becomes implicitly defined by the role it plays in the table of instructions. These states are often referred to as the "functional states" of the machine.

A Turing machine, therefore, is more like a computer program (software) than a computer (hardware). Any given Turing machine can be realized or implemented on an infinite number of different physical computing devices. Computer scientists and logicians have shown that Turing machines -- given enough time and tape -- can compute any function that any conventional digital computers can compute.