Peter Henderson created Lispkit lisp in the late 1970s while he was at Newcastle University. Lispkit lisp, which I'll just call Lispkit for short, is a subset of John McCarthy's lisp language. Lispkit is really very simple; it's an almost pure functional language. I say almost pure since there is a Lispkit compiler written in Lispkit and the compiler needed 1 impure operation and, because of the nature of that instruction Peter added a second impure instruction for symmetry rather than for need.
I should say something about the difference between pure functions and impure functions. It's pretty simple, really, a pure function takes one argument and returns one result and has no side effects. One argument? One result? This seems like a severe limitation and that you can't get much done with that. But, in Lispkit, the argument and result can both be S-expressions which can be arbitrarily complex.
I'm pretty sure I should give an example. So here's a simple function that creates an S-expression of all the natural numbers.
(letrec (i (quote 0))
(i lambda(n) (cons n (i (add (quote 1) n)))))
OK, so that may need a little explanation, but all it is doing is defining a recursive function, i and giving passing zero to it as it's argument. It's result is the list generated by putting the argument at the front of the result where the rest of the result is what you get by recursively calling i where the argument has been incremented by 1. Wow! the explanation is way longer than the function itself. Maybe I'm just bad at explaining, or maybe the language is just that powerful.
Another note about the example above. Execution of the function isn't going to terminate. OK, it will terminate; but only when the computer executing it runs out of memory or there's an integer overflow or any number of other bad conditions. If it's not going to terminate, then invoking it would be bad! However, there's a technique known as lazy evaluation where only as much of the function is computed as is needed. As long as I only need, say, the first n natural numbers, then I can pass the infinite S-expression created by i to another function called, say, front that produces the first n elements of a list l.
(letrec (front n l)
(front lambda(n l) (if (eq l nil) nil (if (eq n (quote 0)) nil (cons (car l) (front (sub n (quote 1)) (cdr l))))))
Which is a little ugly, made more so by worrying if the list l might not be long enough. Though, at this point, with these two examples, I've used nearly half the keywords of Lispkit. nil is just an empty S-expression
One of the exercises we had to do, when learning about this style of programming was to create an evaluator for propositional logic; the evaluator has to determine if a given expression was TRUE or FALSE given initial values for the propositions. That was quite fun and, given the simplicity, I thought a relatively easy task. So, at Peter's suggestion, I embarked on the more ambitious task of writing a function that generated new propositions and then evaluated the propositions to determine whether or not they were tautologies. I didn't find any new ones (given as long as I was prepared to let the program run), which is likely a comfort for logicians.
There's probably a whole lot more I could write about Lispkit, but the above is a quick introduction.
Oh, one last comment; the Lispkit compiler when printed out doesn't quite fit onto a single page of paper. OK, it could be made to fit using a smaller font, but then it would be less readable!
Why so small? For three reasons:
- There aren't a whole lot of keywords in Lispkit.
- A Lispkit program is written as an S-expression. This means that the program looks just like data.
- The object code produced by the Lispkit compiler is yet another S-Expression to be interpreted by the SECD machine.
If you're anything like me, you have to admire the pure simplicity of it all.