After reading Michael Nielsen's "Lisp as the Maxwell's equations of software", I thought "that eval function is huge; there has got to be a way to simplify it". Additionally, I've long been annoyed by the fact that many of Lisp's syntactic forms and function calls look exactly the same; this leads to enormous frustration when you try to do something like (map and list-of-bools) and are informed by the compiler that "and" is not a function- it's a macro. If it looks like a function, it should act like a function. Ideally, it should actually be a function; the language should not treat it specially.
So, I started playing around trying to eliminate as many special forms as possible from the interpreter. Here's my modification of the tiddlylisp eval function, stripped down with as much as possible moved into the global environment, and with a little extra error handling thrown in:
def eval(x, env):
def eval(x, env):
"Evaluate an expression in an environment."
if isa(x, Symbol): # variable reference
return env.find(x)[x]
elif not isa(x, list): # constant literal
return x
elif x[0] == 'quote' or x[0] == 'q': # (quote exp), or (q exp)
(_, exp) = x
return exp
elif x[0] == 'if': # (if test conseq alt)
(_, test, conseq, alt) = x
return eval((conseq if eval(test, env) else alt), env)
elif x[0] == 'cond': # (cond (p1 e1) ... (pn en))
for (p, e) in x[1:]:
if eval(p, env):
return eval(e, env)
raise ValueError("No Branch Evaluates to True")
elif x[0] == 'set!': # (set! var exp)
(_, var, exp) = x
env.find(var)[var] = eval(exp, env)
elif x[0] == 'define': # (define var exp)
(_, var, exp) = x
env[var] = eval(exp, env)
elif x[0] == 'lambda': # (lambda (var*) exp)
(_, vars, exp) = x
return lambda *args: eval(exp, Env(zip(vars, args), env))
elif x[0] == 'begin': # (begin exp*)
for exp in x[1:]:
val = eval(exp, env)
return val
else: # (proc exp*)
exps = [eval(exp, env) for exp in x]
proc = exps.pop(0)
if hasattr(proc, '__call__'): return proc(*exps)
else: raise ValueError("%s is not a procedure" % to_string(x[0]))
The global environment looks like this:
global_env = Env({
'+': operator.add,
'-': operator.sub,
'*': operator.mul,
'/': operator.div,
'>': operator.gt,
'<': operator.lt,
'>=': operator.ge,
'<=': operator.le,
'=': operator.eq,
'eq?': lambda x,y:(not isa(x, list)) and (x == y),
'cons': lambda x,y:[x]+y,
'car': lambda x:x[0],
'cdr': lambda x:x[1:],
'list': lambda *x:list(x),
'append':operator.add,
'len': len,
'symbol?': lambda x:isa(x,Symbol),
'list?': lambda x:isa(x,list),
'atom?': lambda x:not isa(x,list),
'exit': exit,
'True': True,
'False': False
})
The only things that have to be coded into the eval function are basic syntactic forms that need to be able to control the evaluation of their arguments or directly access the environment. If we implemented macros, most of those could be extracted from eval and implemented as macro definitions in the global environment (in exchange for complicating eval with macro expansion). But, there's another way to simplify eval, without ever needing macros: rather than evaluating all of the arguments to a function, pass the unevaluated expressions along with a reference to the dynamic calling environment and let the function decide which ones it actually needs evaluated. A function that behaves that way is called a vau expression, and using it allows us to eliminate all special syntactic forms from the language; even the definition of a vau expression itself can be implemented as a vau expression!
The interpreter for vau expressions looks like this:
def eval(x, env):
"Evaluate an expression in an environment."
if isa(x, Symbol): # variable reference
return env[x]
elif isa(x, list): # procedure call
proc = eval(x[0], env)
if hasattr(proc, '__call__'):
return proc(env,*x[1:])
raise ValueError("%s = %s is not a procedure" %
(to_string(x[0]),to_string(proc)))
return x # literal constant
Much simpler! And this is the global environment:
def vau(clos_env, vars, call_env_sym, body):
def closure(call_env, *args):
new_env = Env(zip(self.vars, args), self.clos_env)
new_env[self.sym] = call_env
return eval(self.body, new_env)
return closure
def defvar(v,var,e):
val = eval(e, v)
v[var] = val
return val
def setvar(v,var,e):
val = eval(e, v)
env.find(var)[var] = val
return val
def cond(v,*x):
for (p, e) in x:
if eval(p, v):
return eval(e, v)
raise ValueError("No Branch Evaluates to True")
def sequence(v,*x):
for e in x[:-1]: eval(e, v)
return eval(x[-1], v)
def wrap(v,p):
p = eval(p,v)
return lambda v,*x: p(v,*[eval(expr,v) for expr in x])
global_env = Env({
'+': lambda v,x,y:eval(x,v) + eval(y,v),
'-': lambda v,x,y:eval(x,v) - eval(y,v),
'*': lambda v,x,y:eval(x,v) * eval(y,v),
'/': lambda v,x,y:eval(x,v) / eval(y,v),
'>': lambda v,x,y:eval(x,v) > eval(y,v),
'<': lambda v,x,y:eval(x,v) < eval(y,v),
'>=': lambda v,x,y:eval(x,v) >= eval(y,v),
'<=': lambda v,x,y:eval(x,v) <= eval(y,v),
'=': lambda v,x,y:eval(x,v) == eval(y,v),
'eq?': lambda v,x,y:
(lambda vx,vy: (not isa(vx, list)) and (vx == vy))(eval(x,v),eval(y,v)),
'cons': lambda v,x,y:[eval(x,v)]+eval(y,v),
'car': lambda v,x:eval(x,v)[0],
'cdr': lambda v,x:eval(x,v)[1:],
'list': lambda v,*x:[eval(expr, v) for expr in x],
'append': lambda v,x,y:eval(x,v)+eval(y,v),
'len': lambda v,x:len(eval(x,v)),
'symbol?': lambda v,x:isa(eval(x,v),Symbol),
'list?': lambda v,x:isa(eval(x,v),list),
'atom?': lambda v,x:not isa(eval(x,v), list),
'True': True,
'False': False,
'if': lambda v,z,t,f: eval((t if eval(z,v) else f), v),
'cond': cond,
'define': defvar,
'set!': setvar,
'vau': vau,
'begin': sequence,
'eval': lambda v,e,x: eval(eval(x,v),eval(e,v)),
'wrap': wrap
})
The definition of the environment is now more complex because every function has to handle the evaluation of its own arguments. The vau expression that defines new vau expressions takes a list of names of arguments and a body expression, just like a lambda would, but has an additional parameter for the symbol to which the calling environment should be bound. Now, if you look carefully, you may be wondering "where's quote? where's lambda? don't we need those?" Well, no, we don't; quoting is the default behavior anyway, since vaus don't evaluate arguments, and anything that we can do with lambdas we can do with vaus, always exercising explicit control over evaluation. But in order to save typing, we can write quote and lambda as standard library functions. They look like this:
(define q (vau (e) % e))
(define lambda (vau (args body) %
(wrap (eval % (list vau args (q $) body)))))
In order to define lambda, we needed an extra built-in function called "wrap"; wrap just takes a vau expression and returns a new vau expression that automatically evaluates all of its arguments. Lambda uses eval to produce a vau expression that takes the same list of argument names and the same body as the lambda expression did with a throwaway environment binding, and then wraps it to ensure that all of its arguments will be evaluated.
All that wrap does is essentially to map eval over the argument list. We can write map in vau expressions:
(define null? (vau (x) % (= (eval % x) (q ()))))
(define map (vau (f l) %
(begin
(define fv (eval % f))
(define lv (eval % l))
(if (null? lv) (q ())
(cons (fv (car lv)) (map fv (cdr lv)))))))
So, can we write lambda using an explicit map, and no wrap? Well, not very easily. An attempt is something like this:
(define curry (vau (f a) %
(begin
(define fv (eval % f))
(define av (eval % a))
(vau (b) & (fv av (eval & b))))))
(define lambda (vau (args body) %
(vau (eval % args) &
((eval & (list vau args (q $) body))
(map (curry eval &) (eval & args)))))
But the problem with this is that a call to (vau ...) does not evaluate its arguments! So, rather than lambda returning a vau expression that takes the same arguments as the lambda expression, it will end up returning a vau expression that takes arguments named "eval", "%", and "args". If you fix that by evalling the outer vau expression, then you'll have to quote the inner evalled vau expression, which unbinds its eventual evaluation from the environment in which lambda was called. Providing wrap as an additional primitive saves the day.
Wrap also allows us to simplify the definition of our global environment a bit:
global_env = Env({
'+': wrap(None,operator.add),
'-': wrap(None,operator.sub),
'*': wrap(None,operator.mul),
'/': wrap(None,operator.div),
'>': wrap(None,operator.gt),
'<': wrap(None,operator.lt),
'>=': wrap(None,operator.ge),
'<=': wrap(None,operator.le),
'=': wrap(None,operator.eq),
...
})
Although this formulation is somewhat less efficient. One could also simply write all of the built-in functions in forms that do not evaluate their arguments, assuming that they will only get primitive values and not expressions passed it, and then define the more general argument-evaluating forms as standard library functions using wrap.
Vau & wrap actually provide a more fundamental abstraction than lambda does, in the sense that they can be used to build lambdas and some other extra stuff. So, if the Lisp interpreter is like software's Maxwell equations, I see the vau-based interpreter as a bit like software's Schroedinger equation, with the special built-in global environment functions (like the definition of vau itself, or the define function, or the if function) filling the roles of the different fundamental particles that obey it, which can be composed to form all matter. Maybe vau expressions are like complex-valued quantum wave functions, while wraps are like the resulting probability distributions.
Vau essentially makes syntax and environments into first-class language citizens, while wrap allows us to drop into the more concise world of implicit evaluation when we want to. Making syntax with explicit control of evaluation into a first-class citizen means that we don't need macros anymore; notice that our definition of lambda used its arguments as components in constructing a new syntax tree and then evaluated that, just as macros are used for compile-time syntax transformations. Anything that can be accomplished with compile-time macros can be accomplished at run-time with a vau expression instead. (Of course, implementing compile-time macros may still be desirable for efficiency reasons.)
Since synactic forms and regular functions are no longer distinct, there's no need for keywords; anything can be used as a variable name, and anything can be shadowed or overwritten. This may seem like a very dangerous thing to allow, as any JavaScript hacker could tell you, but if you're paranoid about other code overwriting important functions in your dynamic environment, you can always write your code in a closure containing a reference to the unmodified global environment, and evaluate everything in that.
Since we have explicit control over when and how arguments are evaluated, we also no longer have to worry about laziness vs. strictness, or call-by-value vs. call-by-name vs. call-by-reference. Those distinctions only arise when the details of evaluation are abstracted away behind a lambda expression. Want strict evaluation? Write your function to evaluate all its arguments up front. Want lazy evaluation? Just evaluate arguments when you actually need them, and cache the results in a mutable local variable. Want call-by-name? Evaluate arguments when you need them and don't bother with caching.
With first-class environments, we can also build namespaces without built-in language support; referencing a symbol in a namespace is just a special case of evaluating an expression in an environment. This allows for cool things like returning an environment from a deeply nested nested closure, and using it to evaluate a function definition elsewhere, thus permitting flattening out of deeply nested closures without losing access to the static environment where the nested closure was originally defined. It's just like defining a class in, say, C++ with a bunch of private instance variables, and then defining all of the method implementations elsewhere, un-nested, with a little annotation that says that they belong to that environment.
For more examples of vau expressions, here's the tiddlylisp square root program from Michael's article re-written into vau form:
(define sqrt (vau (x) % (sqrt-iter 1.0 (eval % x))))
(define sqrt-iter
(vau (guess x) %
(begin
(define gv (eval % guess))
(define xv (eval % x))
(if (good-enough? gv xv) gv
(sqrt-iter (improve gv xv) xv)))))
(define good-enough?
(vau (guess x) %
(< (abs (- (eval % x) (square (eval % guess)))) 0.00001)))
(define improve (vau (guess x) %
(begin
(:= gv (eval % guess))
(average gv (/ (eval % x) gv)))))
(define abs (vau (x) % (begin (define xv (eval % x)) (if (< 0 xv) xv (- 0 xv)))))
(define square (vau (x) % (begin (define xv (eval % x)) (* xv xv))))
(define average (vau (x y) % (* 0.5 (+ (eval % x) (eval % y)))))
Now maybe you're wondering "why did we eval the argument to sqrt? It just gets passed straight on to sqrt-iter, and sqrt-iter evaluates it, so isn't that redundant?"
Well, if you instead write sqrt as (vau (x) % (sqrt-iter 1.0 x)), it will work so long as you only pass in primitive numbers as arguments. If you try (sqrt (+ 1 2)), though, Python will explode at you. What went wrong?
(vau (x) % (sqrt-iter 1.0 x)) passes sqrt-iter the symbol x, not it's value; sqrt-iter then evaluates the symbol x, and, since the dynamic environment of sqrt in which x was bound is included in the scope chain of the dynamic environment passed to sqrt-iter, it resolves to the expression passed to sqrt. If that was a number, all is well. But if it was a compound expression, it blows up! Defining sqrt as (vau (x) % (sqrt-iter 1.0 (eval % x))), however, ensures that when sqrt-iter evaluates the symbol x (which is value of sqrt-iter's formal parameter x), it will always get a number back. The square function actually could be simplified, since we know it's only ever called with primitive number arguments, but I've left it with its own call to eval so that it could be used in other situations.
Appendix: Syntactic Sugar
Based on the analogy of evaluating in an environment to referencing a namespace, we can add a little syntactic sugar to our parser to get rid of all the "evals". We'll have ENV::EXPR desugar to (eval ENV EXPR) and 'EXPR desugar to (q EXPR) so we can re-write our library functions like this:
(define sqrt (vau (x) % (sqrt-iter 1.0 %::x)))
(define sqrt-iter
(vau (guess x) %
(begin
(define gv %::guess)
(define xv %::x)
(if (good-enough? gv xv) gv
(sqrt-iter (improve gv xv) xv)))))
(define good-enough?
(vau (guess x) %
(< (abs (- %::x (square %::guess))) 0.00001)))
(define improve (vau (guess x) %
(begin
(:= gv %::guess)
(average gv (/ %::x gv)))))
(define abs (vau (x) % (begin (define xv %::x) (if (< 0 xv) xv (- 0 xv)))))
(define square (vau (x) % (begin (define xv %::x) (* xv xv))))
(define average (vau (x y) % (* 0.5 (+ %::x %::y))))
(define q (vau (e) % e))
(define lambda (vau (args body) %
(wrap %::(list vau args '$ body))))
(define null? (vau (x) % (= %::x '())))
(define map (vau (f l) %
(begin
(define fv %::f)
(define lv %::l)
(if (null? lv) '()
(cons (fv (car lv)) (map fv (cdr lv)))))))
(define curry (vau (f a) %
(begin
(define fv %::f)
(define av %::a)
(vau (b) & (fv av &::b)))))
We can also write an extra library function to get a handle on the current environment, in case we're not inside a vau expression:
(define get-env (vau () % %))
And that allows us to see that any variable reference
vau> (define a 2)
vau> a
2
is actually equivalent to
vau> (define std (get-env))
vau> std::'a
2
evaluating a symbol in the current namespace.
Code for a working vau interpreter can be found at https://github.com/gliese1337/schrodinger-lisp.
No comments:
Post a Comment