* Lecture 7A: Metacircular Evaluator, Pt 1
https://youtu.be/aAlR3cezPJg

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.

#+BEGIN_SRC scheme
  (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))))))
#+END_SRC

#+BEGIN_SRC scheme
  (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))))
#+END_SRC

#+BEGIN_SRC scheme
  (define evlist
    (λ (l env)
      (cond ((eq? l '()) '())
	    (else
	     (cons (eval (car l) env)
		   (evlist (cdr l) env))))))
#+END_SRC

#+BEGIN_SRC scheme
  (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)))))
#+END_SRC

#+BEGIN_SRC scheme
  (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))))))
#+END_SRC

--> 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:
#+BEGIN_SRC scheme
  (define expt
    (λ (x n)
      (cond ((= n 0) 1)
	    (else
	     (* x (expt x (- n 1)))))))
#+END_SRC

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