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.

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

https://youtu.be/QVEOq5k6Xi0

gjs: "what we did was a lot of fun but will it be useful for
anything?"

he says they are, for messing with new language ideas that can be
quickly tested

lets start by adding a simple feature to a lisp

but first, gjs needs to tell us a thing or two about "features"

many languages have a crisis of "creeping featurism", where far too
many things are implemented

there's also "feeping creaturism", where things barely work and the
language barely works because it requires too many resources
(i think… his example seems a little dated)

one useful feature is for things like + and * to be able to take any
arbitrary number of arguments

we need to think first of a notation and then a way to interpret that
notation.

(λ (x . y)
  (map (λ (u) (* x u))
        y))

(x . y)

is a representation of a cons'd pair

(λ x x) ;; = list

this one takes all args together

how do we do this? easy. modify the metacircular evaluator.

–> break

now, for a more substantial variation

dynamic variable binding

Variation 2: a famous "bug"

dynamic binding

a free var in a procedure has its value defined
in the chain of callers, rather than where the procedure is
defined

the most important problem with this technique is a modularity crisis

changing a name can change the behavior of a program in catastrophic
ways

–> break

in algol 60, args could be passed by name or value. if by name, the
arg would be delayed

we can add the feature, delayed parameters (by-name params)

like if we would like to add special forms like cond

(define (unless p c a)          ;; reverse if (like ruby!)
  (cond ((not y) c)
        (else a)))

(unless (= 1 0) 2 (/ 1 0))
;; => (cond ((not (= 1 0)) 2)
;;          (else (/ 1 0)))

;; this  errors. what we would like is to say something special
;; about c and a. that they are delayed.

;; here we will build a kludge
(define (unless p (name c) (name a))
  (cond ((not p) c)
        (else a)))