XST 43: Still Scheming
I’m going to push forward with this LISP / Scheme dialect. I’ll begin by explaining why, and why not.
0945
First of all, I’m not doing this because of some macho belief that you can’t be a true craftsman, woman, person, folk without at least once implementing a Lisp in your front room. I do think Lisp is a good thing to learn, but I know a lot of darn good programmers who don’t know it.
I am doing it for two reasons. First, because it occurred to me that the tree format I was working on for the XST higher level language looked a lot like Lisp, and it seems that it might be an easy way to write tests and actual code for the XST thing.
Second, and more important–SQUIRREL!–it has caught my attention as something nerdy and kind of fun to do. I like to learn and relearn about programming, and I mostly write for others who feel similarly, and the amazing simplicity of Lisp is a very enjoyable place to spend some time.
Above, you see the most distracting object in human history, the Shiny Chrome Squirrel of Unending Distraction. There may be many like it, but this one is mine. Look at it. Try to forget it. You’re still thinking about it, aren’t you?
So I’m going to push forward with this Lispy thing to see where it leads. If it leads to adventure and excitement, so much the better.
Where Are We [Going]?
We have the tokenizing and parsing from Norvig’s “Lispy Calculator” working in Lua. The Lua code is very similar to his Python, but I am a bit jealous of some of Python’s neat features.
I did look into the declarations Norvig used, and the -> annotation on his functions, and I’ve concluded that we should stay mindful of them but deal with the issues in a Lua fashion. It seems like Python 3 treats those things as useful optional documention more than anything else. I’m not sure whether it does any checking, and honestly I don’t care, since we don’t have a direct equivalent here chez Ron.
I’m observing that however Peter Norvig wrote his Lispy things, he didn’t write them up in a TDD fashion. He provides no tests, no sense of incremental development. In our development here in Codea, I’ve already found it desirable to write small tests and work incrementally. Sometimes I tried to take the same big bites as Peter did, and often some detail like a string pattern got in the way. So far, we have these tests:
_:test("number parsing", function()
_:test("tokenize", function()
_:test("split", function()
_:test("parse", function()
The number parsing one just assures me that the Lua tonumber function does what we need to determine whether a string is a number.
The next step in Norvig’s implementation is the “environment”, which is a data structure that maps from variable names to values. The names include our own Symbols, but also built-in standard functions.
Norvig just lays this on us:
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()
OK, I get that he’s director of research at Google and I’m just some guy, but I’m not buying that he just typed that in and it ran. Anyway, what we’ve got here is a dictionary from names to definitions. Norvig is working in a style of defining everything as functions, but I’m in the middle of an OO program, so I am inclined to build an environment object. I’m pretty sure that the statement:
env = Env()
defines a dictionary, and maybe remembers that it is a particular type of one called Env. Anyway what we have here is a function that builds the standard environment. Let’s do a class Env similarly. I’ll write a test or two so that I don’t forget how.
_:test("Env", function()
local env = Env()
env:standard_env()
_:expect(env:at('abs')).is(math.abs)
end)
I picked math.abs because it was something I thought I understood. Test will fail having no Env.
5: Env -- Tests:47: attempt to call a nil value (global 'Env')
Env = class()
function Env:init()
end
Now I imagine we fail on standard doodah:
5: Env -- Tests:48: attempt to call a nil value (method 'standard_env')
Must write some code:
Hm. I realize that Norvig has his standard env function as what amounts to a factory. That’s a good idea. Change the test:
_:test("Env", function()
local env = Env:standard_env()
_:expect(env:at('abs')).is(math.abs)
end)
Env = class()
-- class methods
function Env:standard_env()
local env = Env{ abs=math.abs }
return env
end
function Env:init(aTable)
self.tab = aTable or {}
end
--instance methods
Fail will be on at:
5: Env -- Tests:48: attempt to call a nil value (method 'at')
Implement:
--instance methods
function Env:at(aKey)
return self.tab[aKey]
end
Test runs. Now I think we’re going to get in trouble with Symbols versus strings. In Norvig’s scheme (haha) a symbol is just a string. In our version it is a class instance. I think we will have to intern them to make our at work. But that will show up soon enough.
I think this is enough Env to allow us to proceed with the next phase of Norvig’s implementation. He reminds use that the Lispy Calculator allows forms: variable reference, constant literal, conditional, definition, and procedure call.
Then he just slams in a dozen lines of code that deal with those cases. I’m tempted to transliterate his code but I’d really rather do it incrementally. It generally saves me time and distress to do that. I’ll write a test.
_:test("eval", function()
local prog
local parsed
prog = "(10)"
parsed = LISP:parse(prog)
_:expect(parsed[1]).is(10)
end)
This passes, as should surprise no one. Let’s evaluate. Should get ten.
result = LISP:eval(parsed)
_:expect(result).is(10)
Should fail on eval.
6: eval -- Tests:58: attempt to call a nil value (method 'eval')
Sweet. Let’s code up eval.
I’ve transliterated part of Norvig’s eval:
function LISP:eval(x)
if type(x) == 'number' then
return x
else
local proc = self:eval(x[1])
local a = table.remove(x,1)
local args = {}
for i,a in ipairs(a) do
table.insert(args,a)
end
return proc(args)
end
end
There’s an issue. If we read his larger eval we see that if we present a list (10), it’s going to try to call 10. My world’s simplest program isn’t legal. And the calculator can’t really deal with a program with no operations: our tokenizer expects to find something enclosed in parens. Well, OK, let’s do this:
_:test("eval", function()
local prog
local parsed
local result
prog = "(abs 10)"
parsed = LISP:parse(prog)
_:expect(parsed[2]).is(10)
result = LISP:eval(parsed)
_:expect(result).is(10)
end)
This probably fails on abs.
6: eval -- LISPCalc:53: attempt to index a nil value (local 'x')
Interesting. How did we get to a nil x?
Well, we are going to encounter a symbol now, and we don’t cater for them. Add the case:
Some ferreting around makes me think that my test for instance isn’t working. Here’s what I have:
function LISP:eval(x)
print("eval ", x)
if self:isInstance(x, Symbol) then
print("all symbols are abs")
return math.abs
elseif type(x) == 'number' then
print("number ", x)
return x
else
print("proc ", x, x[1])
local proc = self:eval(x[1])
local a = table.remove(x,1)
local args = {}
for i,a in ipairs(a) do
table.insert(args,a)
end
print("calling ", proc)
local ret = proc(args)
print("returning ", ret)
return ret
end
end
function LISP:isInstance(x, t)
if t==Symbol then
return type(x)==table and x.is_a and x:is_a(Symbol)
end
return false
end
What I’m seeing never includes “all symbols are abs”. A quick test of isInstance tells me that it isn’t working. Right. Should be:
function LISP:isInstance(x, t)
if t==Symbol then
return type(x)=='table' and x.is_a and x:is_a(Symbol)
end
return false
end
The type function returns a string. I forget that almost every time.
Now let me look at my trace. I hate doing that but I don’t quite see how to avoid it.
eval table: 0x2828e8940
proc table: 0x2828e8940 Symbol abs
eval Symbol abs
all symbols are abs
calling function: 0x102064d50
6: eval -- LISPCalc:66: bad argument #1 to 'proc' (number expected, got table)
This is true. I’m calling proc, which is math.abs, passing the table of args. Need to unpack them, I think.
But also we need to evaluate the args, don’t we? Yes.
I’ll fix that up:
Ah. My bug is in this line:
local a = table.remove(x,1)
Again I’m expecting that to return a table, but in fact it modifies the table in place.
I need to do the loop explicitly. The test runs. Let me rip out all the prints and see what I’ve got here.
function LISP:eval(x)
if self:isInstance(x, Symbol) then
return math.abs
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
I’m really glad that I decided to do the smaller step, and it still wasn’t small enough. I’m going to continue to hack a bit before I try to plug in the environment. Let’s do this test:
_:test("plus", function()
local prog = "(+ 2 2)"
local parsed = LISP:parse(prog)
local result = LISP:eval(parsed)
_:expect(result).is(4)
end)
This will fail. My guess is that it’ll return 2, the absolute value of 2.
7: plus -- Actual: 2, Expected: 4
This makes me think that I almost know what I’m doing.
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
The test passes. Note that I don’t know for sure how to pass the actual + function, though I have an idea about it. Also note that I returned print if I don’t know the function. Let’s test that.
_: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)
That does in fact print 5, because all unrecognized symbols are assumed to be the print function.
Commit: eval (+ 2 2)
OK, I’m about two hours in and it’s time to sum up.
Summary
That was more chaotic than I’d have liked, with the result that I didn’t get as far as I feel I “should” have. However, I do not “should” all over myself, so it is what it is.
What it is is that transliterating with limited understanding can lead to trouble, especially when the transliteration isn’t direct. We tend to make mistakes and because we don’t really understand what we’re doing, we don’t see quickly what we’ve done wrong.
Note also that I made a mistake that I’ve made recently, the assumption that
anArray = table.remove(anArray,1)
updates the array by removing the first element. It does not. It sets the variable to the first element, after updating the array in place.
I went to the trouble of unwinding the array by index, from 2 on, although it might be OK to modify the array in place. I’m not sure … because I don’t fully understand what’s going on.
I almost understand. I’ve used Lisp, I’ve read a bunch recently to refresh my memory, and I certainly understand the general idea of this kind of interpreter. In fact, I just wrote one for the XST code a few days ago. But I don’t grok it in fullness, and I think one really needs to when one does this stuff.
Python is very much like Lua, except where it isn’t. Details like the array handling and whatever help it is giving with the types are just different enough to give me trouble, while I understand what each side is probably doing.
I recall that when students in the German class I took would try to do translation on the fly, they’d tend to get tenses wrong, or not quite the right word, The same thing is happening here.
What will I do next time? More Scheming, and I’ll make a point of thinking a bit more deeply as I do it.
See you then!