LISP was one of the earilest programming languages, dating back to 1958 (it recently had its 60 anniversary as I write this). That makes it one of the oldest programming languages. Of languages that still see use today, only Fortran is older. It also has the distinction of being a direct or indirect influence on most of the languages in heavy use today. I'll bet you use all sorts of language features that were first implemented in LISP. Examples are conditional statements (i.e. if, else, ...), REPLs, and automatic garbage collection.
For the purposes of this guide, we'll be using ulisp which has versions that run on MCUs all the way down to the ATMega328. Of course the 32 bit ARM versions run faster, and let you write longer programs. As of version 2.4 uLisp-arm officially supports Adafruit's M4 line of boards.
Installing
An advantage of ulisp is that it's packaged as an Arduino project; once you clone/download the repo, you just load it into the Arduino IDE then compile and flash onto your board.
If you're not familiar with the Arduino IDE and its use, we have a guide for that to get you up and running. That will work with any of the SAMD boards.
Download the code from Github. Inside the ulisp-arm-master directory you get from unzipping the file you just downloaded will be a file named ulisp-arm.ino. Start up your Arduino IDE and open that file. Select your board and port as usual. Build and upload to your board. You will need to place your M4 board into bootloader mode by double pressing reset in order for the uploader to see it.
Connect via the Arduino serial terminal, screen or whatever way you use to connect to the Serial I/O on your board. When you do you'll be greeted by the REPL. You'll be greeted by a prompt of a number that is the number of lisp objects available (don't worry about it.. if it gets small you're running ourt of memory) followed by > and then wait for you to type code. Try (+ 1 2). As soon as you type the closing ) ulisp will evaluate what you typed and you should see 3.
uLisp 2.3 23551> (+ 1 2) 3 23551>
Syntax
Lisp uses a somewhat different style of syntax. There are two kinds of data objects (that's a simplification, but it's sufficient for this guide) in Lisp: atomic objects (e.g. numbers or strings) and lists of data. A list is written as a sequence of data objects surrounded by a pair of parentheses. For example, a list of the numbers 0 through 9 is: (0 1 2 3 4 5 6 7 8 9). Notice that there are no commas between data objects. As implied by the definition, lists can be recursive (since lists contain data objects and lists are data objects). E.g. (1 "hi" (4 5 (6 7))). This is a list of three items. The first is a number, the second is a string, and the third is a list of two numbers and a list (which contains two numbers). Clearly lists don't have to contain a single kind of data object (i.e. they are heterogeneous).
Symbols are another kind of atomic data object. Lisp doesn't have variables in the same way many other languages do. Lisp has names (i.e. symbols) that can be bound to values (i.e. have a value connected). If we have the name x bound to the number 5, whenever we refer to x, Lisp will look it up in its list of bindings and find the value 5, which it will then use. There are some exceptions to this, but they are mainly to do with making bindings. Lisp has a freer ideal about what makes a proper symbol (i.e. name) than most languages (I.e. what are valid identifiers in those languages). For example, in Lisp + is a perfectly fine symbol, as is even? or change!.
Another important kind of data object are boolean values, denoted in code as t (for True) and nil (for False).
If we type a list into the REPL it will get evaluated and the result returned. How does lisp evaluate a list? Let's say we type (+ 1 2) into the REPL. The system looks for a function as the first item. The symbol + is bound by default to a function that adds it's arguments together and returns the sum. The evaluator will call that function using the values of the rest of the items in the list as arguments to it (they are recursively evaluated). The result of that function call will be the result of the evaluation. So evaluating (+ 1 2) results in 3.
Yes, you read that right. Functions are values. Obviously they can be bound to symbols, but they can also be passed into other functions or returned by functions.
Hardware control functions
Ulisp has a quite capable set of features and is tuned for small environments, microcontrollers in particular. As such, it supports Arduino style I/O controls with a set of functions for using the hardware. For the LED blinking example, we'll only need two:
(pinmode pin mode) Sets the input/output mode of a pin, and returns nil. Mode determines the direction/pullup: 0 or nil is INPUT, 1 or t is OUTPUT, and 2 is INPUT_PULLUP.
(digitalwrite pin state) Sets the state of the specified output pin. State can be nil (LOW) or t (HIGH).
Blink
Using the above along with the delay function (identical to the delay that the Arduino framework provides) we can write the standard blink function:
(defun blink () (pinmode 13 t) (loop (digitalwrite 13 t) (delay 1000) (digitalwrite 13 nil) (delay 1000)))
A couple language points:
First of all, notice how Lisp code is simply lists. In fact, Lisp code is the same as Lisp data: the same syntax and internal structure is used for both. That lends itself to some incredibly powerful meta-programming techniques involving treating code as data (and data as code) that we won't get into here.
defun is the function that defines new functions. It takes the symbol to bind to the new function (blink in this case), a list of parameters (none in this case so the list is empty), and the code that is the body of the function (i.e. what to do when the function is called). It creates a function object and binds it to the name.
The loop function simply repeats the enclosed code indefinitely. It's like while True in Python or while (1) in C.
In the REPL we can execute the blink function by typing a list with the name blink. It needs to be in a list to be a function call; on its own it's just a symbol and the value bound to it will be fetched. There are no parameters because our blink function requires none.
(blink)
It does what you'd expect: starts by setting up the pin for output (we're using the onboard LED on pin 13 for simplicity). It then loops, setting the pin high, waiting a second, setting it low, waiting a second, and repeats forever. To stop it, type ~. This is just like you'd expect to see it in C or Python. The problem is that it's not very Lispy.
One of the fundamental idioms of Lisp is recursion, so much so that something called tail recursion optimization is a fairly standard feature in most Lisps. So an introduction to Lisp isn't complete without a discussion of recursion.
Recursion
Simple recursion (we won't worry about mutual recursion here) is when a function calls itself. Consider the factorial function. The factorial of n is n * (n-1) * (n-2) * ... * 1. We could do this with a loop, but it's more natural and elegant to do it with recursion. Factorial has two cases:factorial(1) = 1, and factorial(n) = n * factorial(n-1). This assumes we'll only pass positive integers to factorial. So:
factorial(5) 5 * factorial(4) 5 * 4 * factorial(3) 5 * 4 * 3 * factorial(2) 5 * 4 * 3 * 2 * factorial(1) 5 * 4 * 3 * 2 * 1 5 * 4 * 3 * 2 5 * 4 * 6 5 * 24 120
A recursive factorial function in Lisp would look like:
(defun factorial (n)
(if (= n 1)
1
(* n (factorial (- n 1)))))
This function works exactly as described above.
That (= n 1) check is called the base case, it's what stops the recursion. Always think about that first: how/when/why will the recursion stop? If you don't have that in place it's like an infinite loop.
Recursive solutions can be wonderfully simple and elegant, but at a cost. Each function call takes a bit of space, and they add up. Try to recurse too deeply and you run out of memory. The advantage of using a loop is that it uses a fixed amount of memory (not considering the case where you allocate more memory each time through the loop). Here again we have a somewhat nasty tradeoff. This one has a way around it, though: tail recursion optimization.
Tail Recursion
Tail recursion is the case when the last thing done in a function is the recursive call. In the factorial example above, the last thing done is the multiplication. We generally need to rearrange things a bit to accomplish tail recursion, often by passing a partial solution into the function. Here's a tail recursive version of factorial:
(defun f (n acc)
(if (= n 1)
acc
(f (- n 1) (* n acc))))
(defun factorial (n)
(f n 1))
In fact, we can define the recursive function inside the wrapper. This makes it completely local to the wrapper function.
(defun factorial (n)
(defun f (n acc)
(if (= n 1)
acc
(f (- n 1) (* n acc))))
(f n 1))
Doing a similar analysis as we did above:
(factorial 5) (f 5 1) (f 4 5) (f 3 20) (f 2 60) (f 1 120) 120
Even just looking at the trace, we can get a hint of the increased efficiency. In the non-tail recursive example, you can see the multiplication operations being saved and evaluated on the way back. In the tail recursive version, those multiplications are done right away, with the result passed into the recursive call. By the time we hit the base case and end the recursion, we have the final result and just have to return it.
The advantage of writing in a tail recursive way is that it can be simply and automatically optimized to run as if it were a simple loop, not actually making those nested recursive calls. Not all recursive algorithms can be written tail-recursively, but most can.
Revisiting Blink
For fun, let's rewrite `blink` in a tail-recursive way.
(defun blink (state) (pinmode 13 t) (digitalwrite 13 state) (delay 1000) (blink (not state)))
We could add a function if we wanted to get rid of the parameter, as well as the repeated pinmode call:
(defun blink ()
(defun b (state)
(digitalwrite 13 state)
(delay 1000)
(b (not state)))
(pinmode 13 t)
(b t))
The recursive function simply sets the pin's state to whatever was passed in, then waits and calls itself with the other state. The recursive call is the last thing done in the function so it's tail recursive and can be optimized automatically to have the same performance characteristics as the loop based version.
Resources
* ulisp with MetroM4Express support
* Lisp implementations and resources
Going further
Ulisp has all the hardware support you would expect/require from a language meant for microcontroller programming: serial, I2C, SPI, digital and analog I/O. It also has built-in SD card support.
As a quick example here's the code to reset and read temperature and relative humidity from an I2C si7021 temperature/humidity sensor.
(defun si7021-reset ()
(with-i2c (s #x40)
(write-byte #xFE s))
(delay 50)
nil)
(defun si7021-temperature ()
(with-i2c (s #x40)
(write-byte #xF3 s))
(delay 25)
(with-i2c (s #x40 3)
(let* ((hi (read-byte s))
(lo (read-byte s))
(ckecksum (read-byte s))
(raw-temp (float (logior (ash hi 8) (logand lo #xFF)))))
(- (/ (* raw-temp 175.72) 65536.0) 46.85))))
(defun si7021-humidity ()
(with-i2c (s #x40)
(write-byte #xF5 s))
(delay 25)
(with-i2c (s #x40 3)
(let* ((hi (read-byte s))
(lo (read-byte s))
(ckecksum (read-byte s))
(raw-temp (float (logior (ash hi 8) (logand lo #xFF)))))
(- (/ (* raw-temp 125.0) 65536.0) 6.0))))
> (si7021-reset) nil > (si7021-temperature) 27.7967 > (si7021-humidity) 40.7339
If you've done any work writing I2C drivers in C or CircuitPython this should pretty much make sense. One neat feature about ulisp's approach is that it wraps the I2C connection up as a stream and can then use it's standard stream I/O functions to interact with it. The same is true with SPI, serial, and other stream-like interfaces.
In this example, the with-i2c function creates a stream to the I2C device at address 0x40 (64 decimal) and binds that to the symbol s. Within the scope of the with-i2c s is just a stream that can be read from and written to (depending on whether it was created to read/write: if a number is supplied after the I2C address, the stream is readable for that number of bytes). See the ulisp docs for more detail.
Since ulisp is implemented as an Arduino sketch, it leverages all the portability capabilities of the platform: build it for the board you're using and all the interfaces are ready to use.
Shortcomings
Ulisp is a solid, very portable implementation of a lisp for microcontrollers. Two shortcomings are that the interface of the REPL is simple and rather unforgiving. The other is that it's not the easiest to get code into the system. It would benefit from a better REPL interface (line editing, history, and such) as well as CircuitPython style SPI flash drive support for loading code onto it.
Text editor powered by tinymce.
