Metacircular Evaluator Part 1
Up until now we have thought of programs as describing machines. A character string description of a wiring diagram.
 |
| This is the factorial program described using a wiring diagram |
In the computation world you can have a universal machine called "EVAL". It is a machine that takes as input a description of another machine (such as factorial). This is a simple program, and would be very difficult to replicate as an analog circuit.
This is an "ugly" version of the evaluator because Sussman wants to keep it all on the blackboard...
Numbers we just want to return the number
Symbols we want to return the value, which exists in a table somewhere
Quoted expressions we want a evaluate to a constant
Lambda expressions: need a type tag noting that this is not a primative expression, need the bound variable list, the body, and an environment
Conditional expressions (COND, etc.)
Arbitrary expression like (+ x 3). All previous cases were special forms. In a production version, the condition would be data driven with a dispatch.
(DEFINE EVAL
(LAMBDA(EXP ENV)
(COND ((NUMBER? EXP) EXP)
((SYMBOL? EXP) (LOOKUP EXP ENV))
((EQ? (CAR EXP) 'QUOTE) (CADR EXP))
((EQ? (CAR EXP) 'LAMBDA)
(LIST 'CLOSURE (CDR EXP) ENV))
((EQ? (CAR EXP) 'COND)
(EVCOND (CDR EXP) ENV))
(ELSE (APPLY (EVAL (CAR EXP) ENV)
(EVLIST (CDR EXP) ENV))))))
Default case is a general combination. Still need EVCON, APPLY, EVLIST, and LOOKUP.
The kernel of this is APPLY. Procedure is either primitive or compound.
(DEFINE APPLY
(LAMBDA (PROC ARGS)
(COND ((PRIMATIVE? PROC)
(APPLY-PRIMOP PROC ARGS))
((EVAL (CADADR PROC)
(BIND (CAADR PROC)
ARGS
(CADDR PROC))))
(ELSE <error>))))
This does a lot of CAR and CDRing because we are basically parsing PROC to get the body of the expression, the variables list, and the environment, respectively. In production this code would be much more robust (using dispatch, check for compiled code, use other languages (Fortran, Algol, etc.)
(DEFINE EVLIST
(LAMBDA (L ENV)
(COND ((EQ? L '()) '())
(ELSE
(CONS (EVAL (CAR L) ENV)
(EVLIST (CDR L) ENV))))))
(DEFINE EVCOND
(LAMBDA (CLAUSES ENV)
(COND ((EQ? CLAUSES '()) '())
((EQ? (CAAR CLAUSES) 'ELSE)
(EVAL (CADAR CLAUSES) ENV))
((FALSE? (EVAL (CAAR CLAUSES) ENV))
(EVCOND (CDR CLAUSES) ENV))
(ELSE
(EVAL (CADAR CLAUSES) ENV)))))
(DEFINE BIND
(LAMBDA (VARS VALS ENV)
(CONS (PAIR-UP VARS VALS)
ENV)))
In BIND we are making a new frame for an environment structure.
(DEFINE PAIR-UP
(LAMBDA (VARS VALS)
(COND
((EQ? VARS '())
(COND
((EQ? VALS '()) '())
(ELSE (ERROR TMA))))
((EQ? VALS '()) (ERROR TFA))
(ELSE
(CONS (CONS (CAR VARS)
(CAR VALS))
(PAIR-UP (CDR VARS)
(CDR VALS)))))))
(DEFINE LOOKUP
(LAMBDA (SYM ENV)
(COND
((EQ? ENV '()) (ERROR UBV))
(ELSE
((LAMBDA (VCELL)
(COND
((EQ? VCELL '())
(LOOKUP SYM
(CDR ENV)))
(ELSE (CDR VCELL))))
(ASSQ SYM (CAR ENV)))))))
If environment is empty, we have an unbound variable.
(DEFINE ASSQ
(LAMBDA (SYM ALIST)
(COND
((EQ? ALIST '()) '())
((EQ? SYM (CAAR ALIST))
(CAR ALIST))
(ELSE
(ASSQ SYM (CDR ALIST))))))
This is pretty much the whole evaluator. lol now we are looking at it all with "Thus spoke Zarathustra" in the background. And now Sussman has a wand and a cape haha.
Now we are going to go through an entire evaluation using substitution.
(EVAL '(((LAMBDA(X) (LAMBDA (Y) (+ X Y))) 3) 4) <env>)
Environment model
<e0> (Global environment): +, -, *, /, EQ?, CAR, CDR, etc...
First we got through the special forms. Not a number, not a symbol, not a quoted expression, doesn't begin with lambda or cond. Therefore is is a combination of operator and operands (arbitrary expression)
(EVAL '(((LAMBDA(X) (LAMBDA (Y) (+ X Y))) 3) 4) <e0>)
(APPLY (EVAL '((LAMBDA(X) (LAMBDA (Y) (+ X Y))) 3) <e0>)
(EVLIST '(4) <e0>))
(APPLY (EVAL '((LAMBDA(X) (LAMBDA (Y) (+ X Y))) 3) <e0>)
(CONS (EVAL 4 <e0>)
(EVLIST '() <e0>)
-----------------------
(CONS 4 '())
simplifies to:
(APPLY (EVAL '((LAMBDA(X) (LAMBDA (Y) (+ X Y))) 3) <e0>)
'(4))
(APPLY (APPLY (EVAL '(LAMBDA(X) (LAMBDA (Y) (+ X Y))) <e0>)
'(3))
'(4))
(APPLY (APPLY '(CLOSURE((X)(LAMBDA (Y) (+ X Y))) <e0>)
'(3))
'(4))
The procedure argument CLOSURE is not a primitive, so we have to bind variables into a new environment, with a parent environment of <e0>
<e1>: x = 3
(APPLY (EVAL '(LAMBDA (Y) (+ X Y)) <e1>)
'(4))
(APPLY '(CLOSURE((Y)(+ X Y)) <e1>)
'(4))
Now we need a new environment, <e2>, which is a child of <e1>
<e2>: y=4
So now we have:
(EVAL '(+ X Y) <e2>)
(APPLY (EVAL '+ <e2>)
(EVLIST '(x y) <e2>))
(APPLY '+ '(3 4))
7
EVAL and APPLY are the two main players, they form a loop. EVAL produces a procedure and arguments for APPLY. APPLY produces an expression and an environment for EVAL.
Mullet is confused again, so Sussman is pretty printing the expression.
(((LAMBDA (X)
(LAMBDA (Y)
(+ X Y)))
3)
4)
(OPERATOR 4)
OEPRATOR => (LAMBDA (X) (LAMBDA (Y) (+ X Y)) 3) <- expression with respect to X applied to 3
(LAMBDA (Y) (+ 3 Y))
((LAMBDA (Y) (+ 3 Y)) 4) <- expression with respect to Y applied to 4
(+ 3 4)
7
Now we're looking at a program for computing exponentials, apparently we're going to see that definitions are not necessary
(DEFINE EXPT
(LAMBDA (X N)
(COND
((= N 0) 1)
(ELSE
(* (EXPT X (- N 1)))))))
Why does this self referential definition make any sense?
2x + 2y = 6 }
} infinite solutions
x + y = 3 }
} unique solution in <x, y>
x - y = 1 }
} no solutions
x - y = 2 }
These three sets of linear equations have different numbers of solutions. Number of solutions is not obvious by looking at the form.
We can't tell by looking the definition of EXPT how many solutions there are.
x = 3-y
y = x-1
this is linear transformation t
<x, y> = t<x, y>
The solution is a fixed point of t
We want to write down the function that corresponds to t whose function is the fixed point
F = (LAMBDA(G)
(LAMBDA(X N)
(COND
((= N 0) 1)
(ELSE
(* X
(G X (- N 1)))))))
EXPT is a fixed point of F
E0 = 1 <useless procedure, worst possible approximation>
E1 = will exponentiate to the zeroth power
E2 = will exponentiate to the 0 or 1 power.
E3 = will exponentiate to the 0, 1, or 2
...
EXPT = LIMIT Em
N->infinity
EXPT = (F (F (F ... (F 1)...)))
Now we need infinite things
((LAMBDA (X) (X X)) (LAMBDA (X) (X X)))
This is a simple infinite loop.
Y is an operator. "Curry's paradoxical combinator"
(LAMBDA (F)
((LAMBDA (X) (F (X X)))
(LAMBDA (X) (F (X X)))))
(Y F) = ((LAMBDA (X) (F (X X)))
(LAMBDA (X) (F (X X))))
= (F ((...)))
(Y F) = (F (Y F))
What we get is an infinite loop of extra Fs on the outside
DANGER
u = 1 + 1/2 + 1/4 + 1/8 + ...
u - 1 = 1/2 + 1/4 + 1/8 + ...
2(u - 1) = 1 + 1/2 + 1/4 + 1/8 + ...
2(u - 1) = u
Thus u = 2 is a true conclusion
But
v = 1 + 2 + 4 + 8 ...
v - 1 = 2 + 4 + 8 ...
(v - 1)/2 = 1 + 2 + 4 + 8 ...
(v - 1)/2 = v
thus v = -1 is a false conclusion because the sum of v is infinite
With limits, arguments that may work in one case may not work with another
No comments:
Post a Comment