XST 44: Further with Lisp.
Thoughts and observations. Stuff and nonsense.
I’m just going to munch along here, because I think it’s interesting, and because I think an eval of approximately Lisp’s power will be useful in creating a “high-level language” for the XST stuff–or at least the underlying mechanism for it.
On Twitter, @sleepyfox suggested that I look at MAL rather than Norvig for making a Lisp, and referred me to SICP, Structure and Interpretation of Computer Programs, by Sussman and Abelson, if I really wanted to get serious.
I’m pretty sure that I have a copy of SICP somewhere, but couldn’t find it. Fortunately I found a remote copy. When you think that SICP is used as the first-term computer course rext at MIT, it makes a person glad they didn’t go to MIT, although I’m sure that most people who did are glad of that as well. The book is great, but there’s a lot of it. (The authors do say that it’s probably too large to cover all the material in one semester.)
MAL, or Make a Lisp, is an implementation of a Lisp dialect in upwards of 70 different programming languages. It’s a very comprehensive learning experience, seems to be carefully broken out into well-documented steps. And there are 70+ versions to study should one want to learn by reading code.
I can imagine that I might have started with MAL had I known about it, and I’m enjoying my spotty reading in SICP, but I’ll stick with the horse I’ve got for now, continuing with Norvig’s example. I can imagine doing something more robust later, but more likely I’ll move in some other currently unpredicted direction.
Thanks for the tips, Nigel!
Where Were We?
We have these most recent tests:
_:test("eval", function()
local prog
local parsed
local result
prog = "(abs 10)"
parsed = LISP:parse(prog)
_:expect(parsed[1]:is_a(Symbol), "is_a Symbol").is(true)
_:expect(LISP:isInstance(parsed[1],Symbol),"isInstance").is(true)
_:expect(parsed[2],"found 10").is(10)
result = LISP:eval(parsed)
_:expect(result).is(10)
end)
_:test("plus", function()
local prog = "(+ 2 2)"
local parsed = LISP:parse(prog)
local result = LISP:eval(parsed)
_:expect(result).is(4)
prog = "(foo (+ 3 2))"
LISP:eval(LISP:parse(prog))
end)
If I correctly recall, foo is not a defined operation in Lisp, and our eval code converts that to print at the moment. That code is whatever the opposite of powerful, robust, and comprehensive might be:
function LISP:eval(x)
if self:isInstance(x, Symbol) then
if x.token == "abs" then
return math.abs
elseif x.token == "+" then
return function(a,b) return a+b end
else
return print
end
elseif type(x) == 'number' then
return x
else
local proc = self:eval(x[1])
local args = {}
for i = 2,#x do
local item = self:eval(x[i])
table.insert(args,item)
end
local ret = proc(table.unpack(args))
return ret
end
end
We aren’t even using the environment yet, we don’t have all the functions defined in it, and we don’t have all the eval options from Norvig yet. I’ve been going step by step, adding tests, which were not on the radar over at Norvig’s place.
Let’s plug in the environment and make it start to carry some load.
function LISP:eval(x, env)
env = env or Env:standard_env()
...
Now we need to refer to it:
function LISP:eval(x, env)
env = env or Env:standard_env()
if self:isInstance(x, Symbol) then
return env:at(Symbol)
elseif type(x) == 'number' then
return x
...
This is going to fail for many reasons, not least that Env doesn’t expect a Symbol as its input. Let’s test and see what transpires. I expect to try to execute a nil somewhere.
6: eval -- LISPCalc:62: attempt to call a nil value (local 'proc')
OK, first fix Env.
I see two options right now. We should really intern symbols as part of the Symbol class. I think for now I’ll try the simpler and ultimately probably wrong idea of using the token part of the symbol in Env.
function Env:at(aSymbol)
return self.tab[aSymbol.token]
end
Test. Same error:
6: eval -- LISPCalc:62: attempt to call a nil value (local 'proc')
I kind of thought that might work, since the test we’re running is (abs 10). I’ll poke in a print.
No. Reading the code–who wrote this???–suggests that I should have looked up x, not Symbol:
function LISP:eval(x, env)
env = env or Env:standard_env()
if self:isInstance(x, Symbol) then
return env:at(x)
...
Test. Probably fail on the +, is my guess.
7: plus -- LISPCalc:62: attempt to call a nil value (local 'proc')
I think I’d like to have a better idea what’s up, so I’ll add an error check to eval.
function LISP:eval(x, env)
env = env or Env:standard_env()
if self:isInstance(x, Symbol) then
local ret = env:at(x)
assert(ret,"No such symbol as "..tostring(x))
return env:at(x)
7: plus -- LISPCalc:53: No such symbol as Symbol +
Nice. Now we need to populate the environment a bit.
function Env:standard_env()
local tab = Env{}
tab.abs = math.abs
tab["+"] = function(a,b) return a+b end
return Env(tab)
end
This will fail on foo, since we have no default built in.
7: plus -- LISPCalc:53: No such symbol as Symbol foo
Shall we put in a default, or leave it this way? This way is closer to what Lisp would do, I think.
I’ll remove the foo check.
I am tempted just to add in Norvig’s examples. Here’s his environment setup:
import math
import operator as op
def standard_env() -> Env:
"An environment with some Scheme standard procedures."
env = Env()
env.update(vars(math)) # sin, cos, sqrt, pi, ...
env.update({
'+':op.add, '-':op.sub, '*':op.mul, '/':op.truediv,
'>':op.gt, '<':op.lt, '>=':op.ge, '<=':op.le, '=':op.eq,
'abs': abs,
'append': op.add,
'apply': lambda proc, args: proc(*args),
'begin': lambda *x: x[-1],
'car': lambda x: x[0],
'cdr': lambda x: x[1:],
'cons': lambda x,y: [x] + y,
'eq?': op.is_,
'expt': pow,
'equal?': op.eq,
'length': len,
'list': lambda *x: List(x),
'list?': lambda x: isinstance(x, List),
'map': map,
'max': max,
'min': min,
'not': op.not_,
'null?': lambda x: x == [],
'number?': lambda x: isinstance(x, Number),
'print': print,
'procedure?': callable,
'round': round,
'symbol?': lambda x: isinstance(x, Symbol),
})
return env
global_env = standard_env()
Some of them I definitely do not understand yet, such as apply. And he has some ability that I do not, such as using Python’s list as List. We’ll have to find our way as we do this.
I think we’ll need to deal with other matters before it’s worth putting much more into our environment. What is missing from eval? Here’s Norvig’s:
def eval(x: Exp, env=global_env) -> Exp:
"Evaluate an expression in an environment."
if isinstance(x, Symbol): # variable reference
return env[x]
elif isinstance(x, Number): # constant number
return x
elif x[0] == 'if': # conditional
(_, test, conseq, alt) = x
exp = (conseq if eval(test, env) else alt)
return eval(exp, env)
elif x[0] == 'define': # definition
(_, symbol, exp) = x
env[symbol] = eval(exp, env)
else: # procedure call
proc = eval(x[0], env)
args = [eval(arg, env) for arg in x[1:]]
return proc(*args)
Wow, look at that if. That’s going to take some study before I understand what it’s even doing. Anyway I think define should be next. Let’s have a test.
_:test("define", function()
local prog = "((define x -10)(abs x))"
local result = LISP:eval(LISP:parse(prog))
_:expect(result).is(10)
end)
I have high hopes for this after we define define. Test first to get the error.
8: define -- LISPCalc:53: No such symbol as Symbol define
Peter’s code grabs the three elements of the list x, ignoring the first, which is of course define. We’ll do similarly.
elseif x[1].token == 'define' then
_, symbol, exp = table.unpack(x)
env:atPut(symbol, self:eval(exp,env))
function Env:atPut(symbol, value)
self.tab[symbol] = value
end
I’m starting to wish I had just used a table as the environment, but I think when we link them together I’ll be glad of what I have. Run the test.
Main:14: attempt to call a nil value (field 'showTests')
stack traceback:
Main:14: in function 'draw'
Never, ever, store into _ when you’re using CodeaUnit.
elseif x[1].token == 'define' then
_ignored, symbol, exp = table.unpack(x)
env:atPut(symbol, self:eval(exp,env))
8: define -- LISPCalc:53: No such symbol as Symbol x
Right. Used the symbol not its token.
function Env:atPut(symbol, value)
self.tab[symbol.token] = value
end
But I get the same message. Irritating.
After some head scratching, I think the bug is that I’m recreating the environment sometimes. Should be setting up a global one and letting it be used.
function LISP:eval(x, env)
env = env or Env.standard
...
_:before(function()
Env.standard = Env:standard_env()
end)
8: define -- LISPCalc:69: attempt to call a nil value (local 'proc')
After yet more wondering, I try another test:
_:test("two things", function()
_:expect(2,"two things").is(2)
local prog = "((+ 1 1) (+ 2 20))"
local result = LISP:eval(LISP:parse(prog))
_:expect(result).is(22)
end)
This gets the same error. I guess I am not allowed to say that two-element thing. Some experimentation with LispPad, a handy iPad app, confirms this theory.
If I put in multiple expressions without the enclosing parens, I get the value of the first expression.
I notice a semi-test in Norvig:
>>> eval(parse("(begin (define r 10) (* pi (* r r)))"))
314.1592653589793
Let’s use that. That’s gonna fail on pi and begin.
_:test("define", function()
_:expect(2,"define test").is(2)
local prog = "(begin (define r 10) (* pi (* r r)))"
local result = LISP:eval(LISP:parse(prog))
_:expect(result).is(314.1592,.05)
end)
8: define -- LISPCalc:53: No such symbol as Symbol begin
His begin is this:
'begin': lambda *x: x[-1],
That’s a variable args thing. I think my equivalent is as shown below, together with pi and *.
function Env:standard_env()
local tab = Env{}
tab.abs = math.abs
tab.pi = math.pi
tab["+"] = function(a,b) return a+b end
tab["*"] = function(a,b) return a*b end
tab.begin = function(...)
local args = {...}
return args[#args]
end
return Env(tab)
end
Once I manage to understand the python, and to define * and pi, the tests run.
Commit: Implemented rudimentary environment, begin, pi, +, *. Env used in eval. Eval understands define.
Let’s sum up.
Summary
There was a lot of confusion behind the scenes, mostly caused by my poor memory of Lisp, which caused me to think that I could evaluate a list containing two expressions. Once I realized that that was improper, I quickly found the begin trick in Norvig and then all I had to do was figure out what *x means in Python.
However, I was in no shape to commit for a log time, though I could have committed after plugging in the environment.
I should mention that I needed to plug the environment into all my calls to eval, which I missed out for a while as part of my fumbling toward realizing that two expressions just wasn’t going to work.
All that not withstanding, we now have an incredibly complex program running:
(begin
(define r 10)
(* pi
(* r r)
)
)
Or however you pretty-print that. No doubt we’ll implement that soon.
Seriously, that’s actual a fairly complex program to be able to parse and execute. It’s a tribute to Lisp’s many creators and contributors that it’s that simple to make it go.
We’ll keep going with this, at least to the end of the calculator phase. At that point, we’ll look to see if it’s interesting enough to plug into XST. I suspect we’ll want more but this much might be enough to be useful.
See you then, I hope!