lecture.org 4.6 KB
Lecture 7A: Metacircular Evaluator, Pt 1
yahoo!! excited for this one
gjs: "today we are going to learn about something amazing"
so far, our programs are a character string description of some wiring diagram that could also be drawn some other way
we can have something called the "universal machine"
this is "eval"
it is a real machine, we will see it today. remarkably, it fits on the blackboard. eval is a machine that takes a description of a machine and becomes a simulator of the description.
we are getting real close to the spirit of the computer. to address the spirit gjs puts on his jacket and fez.
(define eval
(λ (exp env)
(cond ((number? exp) exp) ;;
((symbol? exp) (lookup exp env)) ;;
((eq? (car exp) 'quote) (cadr exp)) ;; special
((eq? (car exp) 'lambda) ;;
(list 'closure (cdr exp) env)) ;; forms
((eq? (car exp) 'cond) ;;
(evcond (cdr exp) env)) ;; ---------
(else (apply (eval (car exp) env) ;; default
(evlist (cdr exp) env))))))
(define apply
(λ (proc args)
(cond ((primitive? proc)
(apply-primop proc args))
((eq? (car proc) 'closure)
(eval (cadadr proc)
(bind (caadr proc)
args
(caddr proc))))
(else error))))
(define evlist
(λ (l env)
(cond ((eq? l '()) '())
(else
(cons (eval (car l) env)
(evlist (cdr l) env))))))
(define evcond
(λ (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
(λ (vars vals env)
(cons (pair-up vars vals)
env)))
(define pair-up
(λ (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
(λ (sym env)
(cond ((eq? env '()) (error UBV))
(else
((λ (vcell)
(cond ((eq? vcell '())
(lookup sym
(cdr env)))
(else (cdr vcell))))
(assq sym (car env)))))))
(define assq
(λ (sym alist)
(cond ((eq? alist '()) '())
((eq? sym (caar alist))
(car alist))
(else
(assq sym (cdr alist))))))
–> break
to walk thoroughly thru an example
(eval '(((λ (x) (λ (y) (+ x y))) 3) 4) <env>)
the environments:
e0 | + * - / car cdr cons eq? |
|------------------------------------------|
(apply (eval '((λ (x) (λ (y) (+ x y))) 3) <e0>)
(evlist '(4) <e0>))
(apply (eval '((λ (x) (λ (y) (+ x y))) 3) <e0>)
(cons (eval '4 <e0>)
(evlist '() <e0>)))
(apply (eval '((λ (x) (λ (y) (+ x y))) 3) <e0>)
(cons 4 '()))
(apply (eval '((λ (x) (λ (y) (+ x y))) 3) <e0>)
'(4))
(apply (apply (eval '(λ (y) (λ (y) (+ x y))) <e0>)
'(3))
'(4))
(apply (apply '(closure ((x) (λ (y) (+ x y))) <e0>)
'(3))
'(4))
|-------------------------------------------| e1 | x = 3 e0 | |-------------------------------------------|
(apply (eval '(λ (y) (+ x y)) <e1>)
'(4))
(apply '(closure ((y) (+ x y)) <e1>)
'(4))
|-------------------------------------------| e2 | y = 4 e1 | |-------------------------------------------|
(eval '(+ x y) <e2>)
(apply (eval '+ <e2>)
(evlist '(x y) <e2>))
(apply '*add* '(3 4))
7
+-------------------------------------+ | proc args | | V EVAL APPLY ^ | | exp env | +-------------------------------------+
–> break
consider the following small program:
(define expt
(λ (x n)
(cond ((= n 0) 1)
(else
(* x (expt x (- n 1)))))))
it's recursive. why does it make sense?
simplest infinite loop:
((λ (x) (x x)) (λ (x) (x x)))
curry's paradoxical combinator Y:
(λ (f) ((λ (x) (f (x x))) (λ (x) (f (x x)))))
(y F) = ((λ (x) (F (x x))) (λ (x) (F (x x))))
= (F ((λ (x) (F (x x))) (λ (x) (F (x x)))))
(y F) = (F (y F))