circuitpython_lisp.jpg
XKCD "Lisp" CCA Non-Commerical 2.5

So why Lisp? What's so special about it?

Simplicity

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:

  1. 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).
  2. 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.

Consider the if special form:

(if condition
  then-expression
  else-expression)

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 then-expression or 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: quote, if, set!, define, lambda, and begin. The CircuitScheme adds cond to the list for convenience.

Macros

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:

(if condition
  (begin expression-1
         expression-2
         ...))

This can get unwieldy, and a when macro is often used:

(when condition
  expression-1
  expression-2
  ...)

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 if and begin as shown above.

Recursion and Tail Call Optimization

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.

while True:
    stuff

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:

def f(a_list):
    for i in a_list:

        print(i)

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:

def f(a_list):
    if a_list:
        print(a_list[0])
        f(a_list[1:])

If 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))
      (begin
        (display (car a-list))
        (newline)
        (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 print is called. When print returns, that stack space is reclaimed and used again by the next call to print. How much stack space we use is independent of the length of the list.

Now consider the recursive example. f is called which takes some stack space, as does the call to print but it is reclaimed when print returns. The embedded 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.

Non-tail Call Recursion

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)
        a
        (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.

This guide was first published on Feb 14, 2019. It was last updated on Feb 14, 2019. This page (Lisp) was last updated on Oct 13, 2019.