I’m pressing forward with the Lispy thing, but I have some concerns. I find it difficult to think about but I think I have an angle. (Spoiler: It’s a wrap!)

12 Jan 2022

(I started this article 12 Jan, finishing 28 Jan. Wow!)

I need to finish up the built-in functions. Here’s what Norvig has:

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

The ones I am not at all sure about are apply and proc. I’m also not sure about procedure?, and don’t know what callable is in python, but there I have at least a basic idea of what it must mean.

The problem is that I have no tests or examples, so I’m not entirely sure what these things should do. I’ll look around to try to find some.

Here’s one test, that does work as intended.

        _:test("Random Programs", function()
            local result
            result = LISP:exec("(if (> (* 11 11) 120) (* 7 6) oops)")
            _:expect(result).is(42)
        end)

I’m not sure why the “oops” is accepted but Norvig shows it working that way.

To try to get my head around what’s going on, our current eval looks like this:


function LISP:eval(x, env)
    env = env or Env.standard
    if self:isInstance(x, Symbol) then
        local ret = env:at(x)
        assert(ret,"No such symbol as "..tostring(x))
        return env:at(x)
    elseif type(x) == 'number' then
        return x
    elseif x[1].token == 'if' then
        _ignored,test,conseq,alt = table.unpack(x)
        local exp = self:eval(test,env) and conseq or alt
        return self:eval(exp,env)
    elseif x[1].token == 'define' then
        _ignored, symbol, exp = table.unpack(x)
        env:atPut(symbol, self:eval(exp,env))
    else
        local proc = self:eval(x[1], env)
        local args = {}
        for i = 2,#x do 
            local item = self:eval(x[i], env)
            table.insert(args,item)
        end
        local ret = proc(table.unpack(args))
        return ret
    end
end

28 Jan 2022

Events occurred. I don’t recall what stopped me writing about this on the 12th, but since then I’ve written other articles and even done a tiny bit of reading about Lisp. As someone suggested to me on Twitter, I do wish I had started with a more robust example.

There can be no doubt that in terms of elapsed time, the Lisp experiment has run on too long, and we need to make a decision about it. In terms of programming time, this is the sixth article relating to Lisp, so we can estimate that there are between 12 and 18 hours invested in the Lisp experiment.

It’s time to assess.

We decided to explore Lisp, because I liked the display format that I’d come up with:

(saveAs "C" (restrict (setNamed "A") (setNamed "B")))

And that reminded me of Lisp, and it was the weekend, so I decided to drill down a bit on Lisp.

But the real objective, what we’re supposed to be working on, is the question of whether we can come up with some high-level representation of an XST expression, and then optimize that representation, resulting in a less expensive expression to be evaluated.

My good friend Bill Wake thinks in terms of “expression trees” that we could optimize. That’s one good way. I was thinking, vaguely, that a Lisp-style expression might be optimized with pattern matching and substitution. Same thing, perhaps a higher-level notation.

That led me down the Lisp path, and it has been a fun path. But has it been productive enough to continue? I have serious doubts.

Thinking of the Lisp expression for a set operation, it’s “easy to see” that we could write a Lisp procedure for say, “restrict” that contained a check for an index and if it found one, executed one branch, and if it didn’t, executed another. It would be the Lisp equivalent of this:

function XSet:selectFieldValue(scope,value, index)
    local ix = self:findSelectIndex(scope,value,index)
    if ix then
        return self:scopeRestrict(ix)
    else
        return self:select(function(record, recordScope)
            return record:hasAt(value,scope)
        end)
    end
end

That’s the Lua code for our first optimizing set operation, selectFieldValue. It executes a function to determine whether there is a suitable index and if there is, uses it, and otherwise uses a long-hand search to find the records of interest.

Doing the same thing in a Lisp-like language proves nothing. If we had a solid Lisp implementation running in Lua inside the XSets program, we’d have a slightly better notation for what we can already do. My assessment is that we’re quite a ways away from a solid Lisp implementation, perhaps half-way there, but possibly further away than that.

My recommendation is that we terminate the Lisp experiment and get back to figuring out what (if anything) we need to do with XSets itself to prove whatever point we wanted to prove there.

However, I do like the Lisp-like notation shown above:

(saveAs "C" (restrict (setNamed "A") (setNamed "B")))

If we only permit existing known operations in our parenthesized lists, like the ones above, the parsing part of the Lisp experiment could be quickly adapted to provide that. We could certainly simplify the existing Lisp environment and eval, putting only our defined set operations into the Env environment variable, removing the arithmetic and such that’s in there now. We could remove the if and define, although I’m sure that both of those are working in the current Lispy thing.

With that much in place, it would be easier to write and test set expressions.

So I’m going to authorize us to move the current Lisp stuff into XSet if and when it seems useful, after which we’d define Lisp equivalents for the set operations. But I’m withdrawing funding for the Lisp project, although if the team want to play with it in their free time, I’m OK with it as a learning project. Implementing a Lisp is one of those things that some people say everyone should do at some point. Who am I to stand in the way of those things that some people say?

Is This a Win, or a Fail

Well, on the one hand, I found the Lisp experiment interesting at first, but frustrating as it became clear that the article I found as a basis was weak, in that it lacked tests and included bits of code that weren’t even mentioned in the article. I had high hopes for it, as I’ve always been a Lisp fan, even though I’ve not used it since about 1964 or thereabouts. Really.

But it was an experiment. A “spike”, although a fairly large one of a couple of working days. The point of a spike is to find out something, in this case, something like:

To what extent would a small Lisp implementation be useful in XSets, specifically aimed at optimization?

I think the answer is, roughly:

Not very interesting for optimization, bringing no real new learning, and at least double the cost so far. It might be useful as a notation for writing set expressions.

Seen as a few days’ work to answer a question, we have a win: we got an answer in which we are pretty confident.

But if you wanted to criticize me, you could certainly say:

Jeffries set out to write a Lisp in Lua and he picked a poor example and then didn’t even make that example work, what a loser! He should have used SICP! I could implement Lisp in an afternoon!

Me, I wish the answer had been that the few hours I spent produced a complete embeddable version of Common Lisp, complete with a trans-compiler to Apple silicon and ready to plug into XSets with several key set operations fully optimized, but I also wish I had a BMW M8 convertible.

I set out to play with Lisp, and to answer the question and I learned a bunch and got an answer that I believe. I call that a win. You can call it whatever you wish.

For now, I’m wrapping the Lisp project and will turn my attention back to XSets next time I write a programming article. Whether that’s right away depends on whether I get an idea for something else about Strawberries, or some other issue.

I can’t wait to find out what I do next.