Metacircular Evaluator Part 2
Question is if these metacircular interpreters are useful, and the answer is Yes (if you say so...)
Languages have made a mess of themselves by adding too many features.
"Creeping featurism" - everyone adds their own features, and eventually we have such a complicated system that no one can understand it.
"Feeping Creaturism" - You have all this fancy IO and your language is too small to handle it.
Looking at primitive operators + and *
(+ (* a x x)
(* b x)
c)
Indefinite number of arguments, not handled by our current interpreter. We need to notate the additional arguments. Once we notate it, we need to interpret it correctly.
(LAMBDA (X . Y) X REQUIRED, MANY ARGUMENTS IN LIST Y
(MAP (LAMBDA (U) (* X U))
Y)
Dot operator is related to CONSs.
By changing the PAIR-UP procedure, we can evaluate unlimited list of arguments.
Dynamic binding of variables.
(DEFINE SUM
(LAMBDA (TERM A NEXT B)
(COND
((> A B) 0)
(ELSE
(TERM A)
(SUM TERM
(NEXT A)
NEXT
B)))))
With this sum procedure we can define the sum of powers like this;
(DEFINE SUM-POWERS
(LAMBDA (A B N)
(SUM (LAMBDA (X) (EXPT X N))
A
1+
B)))
(DEFINE PRODUCT-POWERS
(LAMBDA (A B N)
(PRODUCT (LAMBDA (X) (EXPT X N))
A
1+
B)))
There is a lot of repetition here, should be able to abstract some of it:
(DEFINE SUM-POWERS
(LAMBDA (A B N)
(SUM NTH-POWER A 1+ B )))
(DEFINE SUM-POWERS
(LAMBDA (A B N)
(PRODUCT NTH-POWER A 1+ B )))
(DEFINE NTH-POWER
(LAMBDA (X)
(EXPT X N)))
Problem is that the environment model does not give a value for this N above. It is a free variable, it is an unbound variable in the global environment. What we want is for it to be N in the SUM-POWERS and PRODUCT-POWERS procedures.
The desire to make this work led to the famous "bug" - Dynamic binding. A free variable in a procedure has its value defined in the chain of callers, rather than where the procedure is defined. (you search up the chain of callers to find the value)
Easy to implement, but...
Change to EVAL to allow for dynamic binding:
(DEFINE EVAL
(LAMBDA(EXP ENV)
(COND
((NUMBER? EXP) EXP)
((SYMBOL? EXP) (LOOKUP EXP ENV))
((EQ? (CAR EXP) 'QUOTE) (CADR EXP))
((EQ? (CAR EXP) 'LAMBDA) EXP) ;! no need to define CLOSURE and such
((EQ? (CAR EXP) 'COND)
(EVCOND (CDR EXP) ENV))
(ELSE (APPLY (EVAL (CAR EXP) ENV)
(EVLIST (CDR EXP) ENV)
ENV))))) ;! Application must get env of caller
The APPLY definition will extend the callers env.
... problem with dynamic binding is the modularity crisis. You want names that don't interfere, and dynamic binding can violate that.
We want a procedure that produces an exponentiator
(DEFINE PGEN
(LAMBDA (N)
(LAMBDA (X) (EXPT X N))))
We can now better abstract the POWERS procedures:
(DEFINE SUM-POWERS
(LAMBDA (A B N)
(SUM (PGEN N) A 1+ B)))
(DEFINE PROCEDURE-POWERS
(LAMBDA (A B N)
(PRODUCT (PGEN N) A 1+ B)))
Ugh, Mullet speaks...
Ok, so now we have another break. Gotta download the video, lag is killing me...
With streams, caller and callee had to agree on the Delay/Force principle. It works ok with streams but in general you want to have this much more clear. Don't want to have to have an agreement between the writer of a procedure and the user of the procedure.
Now were going to add a feature to LISP, BY-NAME parameters. Default is a value of a pointer. Why do we need this?
Suppose we want to invent reserve words.
(DEFINE (UNLESS P C A)
(COND
((NOT P) C)
(ELSE A))
(UNLESS (= 1 0) 2 (/ 1 0))
=> (COND
((NOT (= 1 0)) 2)
(ELSE (/ 1 0)))
Because all the arguments are evaluated before being passed to UNLESS, the call to UNLESS will produce an error. We want C and A to be delayed automatically. Important that our solution is syntactically unambiguous, though it might interfere with other declarations. It is not a general solution. It's a cludge.
(DEFINE (UNLESS P (NAME C) (NAME A))
(COND
((NOT P) C)
(ELSE A)))
We are explicitly declaring that certain parameters are delayed. We're going to start with the lexical (non-dynamic) evaluator
(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 (UNDELAY (EVAL (CAR EXP) ;! The application part changes.
ENV))
(CDR EXP)
ENV))))))
(DEFINE APPLY
(LAMBDA (PROC ARGS)
(COND
((PRIMATIVE? PROC)
(APPLY-PRIMOP PROC
(EVLIST OPS ENV))) ;EVLIST has to do a bunch of forcing
((EQ? (CAR PROC) 'CLOSURE)
;;PROC = (CLOSURE (BVRN body) env)
(EVAL (CADADR PROC) ;body
(BIND (VNAMES (CAADR PROC))
(GEVLIST (CAADR PROC)
OPS
ENV)
(CADDR PROC)))) ;env
(ELSE ERROR))))
(DEFINE EVLIST
(LAMBDA (L ENV)
(COND
((EQ? L '()) '())
(ELSE
(CONS (UNDELAY (EVAL (CAR L) ENV)
(EVLIST (CDR L) ENV)))))))
(DEFINE GEVLIST
(LAMBDA (VARS EXPS ENV)
(COND
((EQ? EXPS '()) '())
((SYMBOL? (CAR VARS)) ;applicative
(CONS (EVAL (CAR EXPS) ENV)
(GEVLIST (CDR VARS)
(CDR EXPS)
ENV)))
((EQ? (CAAR VARS) 'NAME)
(CONS (MAKE-DELAY (CAR EXPS) ENV)
(GEVLIST (CDR VARS)
(CDR EXPS)
ENV)))
(ELSE ERROR))))
(DEFINE EVCOND
(LAMBDA (CLAUSES ENV)
(COND
((EQ? CLAUSES '()) '()) ;arbitrary
((EQ? (CAAR CLAUSES) 'ELSE)
(EVAL (CADAR CLAUSES) ENV))
((FALSE? (UNDELAY
(EVAL (CAAR CLAUSES)
ENV)))
(EVCOND (CDR CLAUSES ENV)))
(ELSE
(EVAL (CADAR CLAUSES) ENV)))))
(DEFINE FALSE?
(LAMBDA (X) (EQ? X NIL))) ;any more this should use '() instead of NIL
(DEFINE MAKE-DELAY
(LAMBDA (EXP ENV)
(CONS 'THUNK (CONS EXP ENV))))
(DEFINE (UNDELAY V)
(COND
((PAIR? V)
(COND
((EQ? (CAR V) 'THUNK)
(UNDELAY (EVAL (CADR THUNK)
(CDDR THUNK))))
(ELSE V)))
(ELSE V)))
"thunk" comes from ALGOL, apparently its the sound of something falling onto the stack.
There are a couple cases where it is reasonable to call primitives by name. CONS and array data structures, we can combine the promises for the things as easy as we can combine the things. Data constructors, selectors, side effects don't need to do any forcing in lazy interpreters. Predicates on data structures have to (like PAIR?).
No comments:
Post a Comment