So why Lisp? What's so special about it?
Lisp is one of those languages that is so simple it's almost nonsensically trivial. There is essentially two things to the syntax of Lisp:
- Atomic pieces of data; things that you will be familiar with, like numbers, strings, and symbols. Symbols are similar to identifiers in other languages. They can have a value bound to them. When a symbol is used, it's looked up in the environment and the bound value is used. If it's not found, an error is raised. Like Python identifiers, symbols can have different values, possibly of different types, over time. Additionally in CircuitScheme, atomic data can be any piece of Python data (e.g. an instance of a class).
- Lists of data. Like Python, items in a list can be any data including other lists. Also, like Python, items in a list do not have to be of the same type.
That's it. It gets more interesting when you consider that Lisp code is just Lisp data: there is no difference at all. Data can be evaluated. Atomic data simply evaluates to itself, while symbols get looked up resulting in the bound value.
Evaluating a list is where things get interesting. The first item in the list is expected to evaluate to a function. The rest of the list items are evaluated and used as arguments to that function.
Once more, that's all there is to it. Well, almost. There are a few function-like things that are called special forms. They are often implemented in the interpreter, rather than as a function, and take their arguments verbatim, without evaluating them first.
if special form:
Based on what the condition evaluates to either the then or else expression should be evaluated. You can see how they can't be evaluated before being passed to if; we only want to evaluate one of
else-expression based on
condition. There are a handful of forms like this in any Lisp. In Norvig's original version of Lispy, there are 6 of these:
begin. The CircuitScheme adds
cond to the list for convenience.
Another defining feature of most Lisp implementations is a very powerful macro system. This makes it possible to build language level capabilities that act like special forms.
For example, having a block of code evaluate when a condition of true is very common. With
if we have to do something like:
This can get unwieldy, and a when macro is often used:
This is a cleaner, more concise alternative. The
when macro can be written as so:
(define-macro when (lambda args
`(if ,(car args) (begin ,@(cdr args)))))
Even without being familiar with the macro syntax (i.e.:
` , ,@), it should be clear how
when is being rewritten into the form using
begin as shown above.
One feature that is required of a proper scheme (but not of other Lisps) is tail call optimization. Before diving into this, let's consider recursion.
Writing iterative code should be familiar to everyone whose done any amount of Python programming.
Is about as simple of an iteration as you can get. It just does the same thing over and over. That's all iteration is: doing the same thing multiple times. We see this when using iterables in Python. For instance:
for i in a_list:
We say that we iterate over the list, printing each item.
There isn't a way to do this in CircuitScheme, although real Scheme has some iterative control structures. So how do we do this sort of thing in CircuitScheme (and this sort of thing is very common when programming).
Well, the other way to do repeated processing is to use recursion. Instead of doing the same thing for each item, the function calls itself to process the rest of the list. In Python this would be:
a_list isn't empty, print the first item and call
f again with the rest of
a_list (i.e. from the second item on).
The CircuitScheme equivalent would be:
(define (f a-list)
(if (not (null? a-list))
(display (car a-list))
(f (cdr a-list)))))
Consider the two examples above as the list gets longer. Specifically think about what a function call does: it allocates some stack space to store enough information so that it can return properly. The call stack is typically allocated some finite amount of memory. Certainly in a microcontroller context that can be fairly small.
The iterative example above uses some stack space when
f is called and a bit when
Now consider the recursive example.
f is called which takes some stack space, as does the call to
f takes more stack space. That leads to another call to
f which takes more stack space. In fact, you can see that there is a call to
f for each item in the list, so the amount of stack space used is proportional to the length of the list. A longer list will result in more stack space being used. Given that the stack has a finite amount of space, this puts a limit on how long of a list can be processed. Too long and we get a stack overflow error.
This would seem to be a bad thing. And it is, but there's a way to mitigate the problem. Tail Call Optimization. What's a tail call? That's the name for the style of recursion where the recursive call (when the function calls itself) is the last thing done before the function returns. We can see that that is indeed the case above. The last thing
f does if the list wasn't empty is call itself with the rest of the list.
The neat thing about tail calls is that they can be changed quite easily into iteration. By doing so, excessive stack use may be avoided. Now the recursive code can process any size of list, just like the iterative one.
Scheme and, more importantly for us, CircuitScheme does this optimization within the evaluator.
Notably the folks that have controlled Python have steadfastly resisted supporting tail call optimization. To be fair, they encourage writing iterative code (just think about iterables, generators, list comprehensions, ...) Python is full of constructs that reinforce an iterative style of thinking. Which is fine, if not a little limiting and not always very mathematically elegant.
Since we have a special name for tail call recursion it's logical that there are other forms of recursion that are not tail-call. Generating Fibonacci numbers is a great example. Recall that a Fibonacci number is the sum of the two previous ones. I.e. fib(n) = fib(n-1) + fib(n-2). In Lispy, the obvious solution is:
(define (fib n) (if (<= n 1) n (+ (fib (- n 1)) (fib (- n 2)))))
Note that this does not involve tail-calls. Two recursive calls are made and the results added. The last thing done is the addition. Therefore this can not be optimized. We need to restructure it to use a tail-call. In essence we turn it inside out and accumulate the result as we make the recursive calls. When we reach the base-case (n being 0) the result is in hand and is returned, rippling back through the tail-calls. Note that this often requires a helper function (using a nested definition to hide it) in order to maintain the same API:
(define (fib n)
(define (iter a b count)
(if (<= count 0)
(iter b (+ a b) (- count 1))))
(iter 0 1 n))
Now it does use a tail-call and can be optimized by the evaluator. This is a very powerful feature and it's worth making the effort to restructure the recursion to take advantage of it.