The embarrassment of riches truly astounds in the domain of ahem ‘very small’ lisp implementations… and who am I to refuse to fill an obvious missing link in the series? We got small covered…
Yes, I have in fact begun a super cut down lisp implementation for vfuncs, which I think will be a nice way to express such idioms as map [hey, lisp invented map, right? – maybe not, better check ]
I’ve uploaded the new files atto.c, atto.h, attotest.c to the vfuncs project page – grab v0.6.7.
Some of the earlier blog comments around vfuncs got me to wondering.. How would you implement closure and currying in straight C so it could be used in useful array verbs? It seems what you need is to replace some verb params with values from the ‘environment’. That way the verb can use both runtime args and design time args easily… I did hack up something, but it began to look more and more like I was writing an interpreter… so I decided the ‘honest, unenlightened hacker’ way to proceed was to actually _write_ an interpreter for as simple a language as I could think of…
The core guts of lisp is, well – calling functions with args, when any of those args could be a const, a variable or another function. So, the atto-kernel of lisp is something like this grammar [a comment pasted from the C source] –
// expr : left func args right // (func arg0 arg1 arg2 )
// args : arg args | empty // args is any length 0..n
// arg : ident | const | expr // each arg can be an expr itself – nested calls
In the spirit of ‘start small, get it working and add features’, this cut-down grammar allows you to parse expressions like the following –
// “(sqrt (add (sqr 3.0) (sqr 4.0)) )”
This is the ‘lisp way’ – everything is in prefix notation ie. (* a b) not (a * b). You get used to it, and it is very consistent [and the reason lisp macros are more part of the language than say C/C++ macros].
If this was a commercial project, Id probably err on the side of using yacc and lex – I have happily used bison/flex incarnations for DSLs – but vfuncs claims to be ‘an experiment in readable, performant C code for array verbs’, hence attolisp is written in pure C, with no dependencies.
So the lexer, parser, byte-code emitter, byte-code runner [I hesitate to call it a ‘machine’] comprise less that 1000 loc. The goal was not to save lines of code, so yes, there probably is a way to do this in 12 lines, but for me this was a ‘natural’ direct implementation, and I hope readable.
Next up, we will want to add these features for sure – defun [define callable functions], let [set variables] and ‘functions as args‘. Passing functions as arguments to other functions is not new – C has function pointers, which is just enough to do polymorphism [think vtable or linux VFS] and callbacks etc – it means you can implement map. In map, the iterator calls the user-supplied function on each item. Logically theres no reason that would be anything special… but it just is such useful ‘syntactic sugar’, that it changes the way you think, and the way you program – the existence of C++’s STL certainly supports this, as does googles map-reduce.
Writing attolisp takes me back… I once read a programming book by Herb Schildt. On balance, not recommended, unfortunately… but the one great thing that was an absolute revelation to me at the time [my teens :] was that ‘there is such a thing as a ‘Recursive Descent Parser’ a fantastic idea where your code matches the grammar for the language, so in an instant I went from ‘I have no idea how parsers work’ to ‘I know how you could make a parser that works’…
With 20-20 hindsight, Id recommend to go straight to the classic ‘Dragon Book’ by aho-sethi-ullman. I think a recent version has a chapter on JIT impl, which is of interest during this renaissance of scripting languages. Disclaimer, attolisp doesn’t do Just-In-Time… but what I am thinking of doing is another step where I do some type inference and see if some parts can be replaced by type-specific code for speed.
I do currently have a way to call to inbuilt C functions like sin cos etc – I define them in an array and simpy call the function pointer, so there is a small amount of work to add one to that array – I don’t want the overhead of going through a general ffi layer as the math functions will be called in inner loops…