Scheme For NuttX

Last fall, I built a tiny lisp interpreter for AltOS. That was fun, but had some constraints:

• Yet another lisp-like language
• Ran only on AltOS, not exactly a widely used operating system.

To fix the first problem, I decided to try and just implement scheme. The language I had implemented wasn't far off; it had lexical scoping and call-with-current-continuation after all. The rest is pretty simple stuff.

To fix the second problem, I ported the interpreter to NuttX. NuttX is a modest operating system for 8 to 32-bit microcontrollers with a growing community of developers.

I downloaded the most recent Scheme spec, the Revised⁷ Report, which is the 'small language' follow on to the contentious Revised⁶ Report.

Converting ao-lisp to ao-scheme

Reading through the spec, it was clear there were a few things I needed to deal with to provide something that looked like scheme:

• quasiquote
• syntax-rules
• function names
• boolean type

Quasiquote turned out to be fun -- the spec described it in terms of a set of list forms, so I hacked up the reader to convert the convenient syntax using ` , and ,@ into lists and wrote a macro to emit construction code from the generated lists.

Syntax-rules is a 'nicer' way to write macros, and I haven't implemented it yet. There's nothing it can do which the underlying full macros cannot, so I'm planning on just writing it in scheme rather than having a pile more C code.

Scheme as a separate boolean type, rather than using the empty list, (), for false, it uses #f and has everything else be 'true'. Adding that wasn't hard, just tedious as I had to work through any place that used boolean values and switch it to using #f or #t.

There were also a pile of random function name swaps and another bunch of new functions to write.

All in all, not a huge amount of work, and now the language looks a lot more like scheme.

Adding more number types

The original language had only integers, and those were only 14 bits wide. To make the language a bit more usable, I added 24 bit integers as well, along with 32-bit floats. Then I added automatic promotion between representations and the usual scheme tests for exactness. This added a bit to the footprint, and maybe I should make it optional.

Porting to NuttX

This was the easiest piece of the process -- NuttX offers a posix-like API, just like AltOS. Getting it to build was actually a piece of cake. The only part requiring new code was the lack of any command line editing or echo -- I ended up using readline to get that to work.

I was pleased that all of the language changes I made didn't significantly impact the footprint of the resulting system. I built NuttX for the stm32f4-discovery board, compiling in basic and then comparing with and without scheme:

Before:

$ size nuttx
   text    data     bss     dec     hex filename
 183037     172    4176  187385   2dbf9 nuttx

After:

$ size nuttx
   text    data     bss     dec     hex filename
 213197     188   22672  236057   39a19 nuttx

The increase in text includes 11kB of built-in lisp code, so that when the interpreter starts, you already have all of the necessary lisp code loaded that turns the bare interpreter into a full scheme system. That makes the core interpreter around 20kB of code, which is nice and compact (at least for scheme, I think).

The BSS space includes the heap; this can be set to any size you like. It would probably be good to have that allocated on the fly instead of used even when the interpreter isn't running.

Where's the Code

I've pushed the code here:

$ git clone git://keithp.com/git/apps

Future Work

There's more work to complete the language support; here's some tasks needing attention at some point:

• No vectors or bytevectors
• Characters are just numbers
• No dynamic-wind or exceptions
• No environments
• No ports
• No syntax-rules
• No record types
• No libraries
• Heap allocated from BSS

A Sample Application!

Here's towers of hanoi in scheme for nuttx:

;
; Towers of Hanoi
;
; Copyright © 2016 Keith Packard <keithp@keithp.com>
;
; This program is free software; you can redistribute it and/or modify
; it under the terms of the GNU General Public License as published by
; the Free Software Foundation, either version 2 of the License, or
; (at your option) any later version.
;
; This program is distributed in the hope that it will be useful, but
; WITHOUT ANY WARRANTY; without even the implied warranty of
; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
; General Public License for more details.
;

                    ; ANSI control sequences

(define (move-to col row)
  (for-each display (list "\033[" row ";" col "H"))
  )

(define (clear)
  (display "\033[2J")
  )

(define (display-string x y str)
  (move-to x y)
  (display str)
  )

(define (make-piece num max)
                    ; A piece for position 'num'
                    ; is num + 1 + num stars
                    ; centered in a field of max *
                    ; 2 + 1 characters with spaces
                    ; on either side. This way,
                    ; every piece is the same
                    ; number of characters

  (define (chars n c)
    (if (zero? n) ""
      (+ c (chars (- n 1) c))
      )
    )
  (+ (chars (- max num 1) " ")
     (chars (+ (* num 2) 1) "*")
     (chars (- max num 1) " ")
     )
  )

(define (make-pieces max)
                    ; Make a list of numbers from 0 to max-1
  (define (nums cur max)
    (if (= cur max) ()
      (cons cur (nums (+ cur 1) max))
      )
    )
                    ; Create a list of pieces

  (map (lambda (x) (make-piece x max)) (nums 0 max))
  )

                    ; Here's all of the towers of pieces
                    ; This is generated when the program is run

(define towers ())

                    ; position of the bottom of
                    ; the stacks set at runtime
(define bottom-y 0)
(define left-x 0)

(define move-delay 25)

                    ; Display one tower, clearing any
                    ; space above it

(define (display-tower x y clear tower)
  (cond ((= 0 clear)
     (cond ((not (null? tower))
        (display-string x y (car tower))
        (display-tower x (+ y 1) 0 (cdr tower))
        )
           )
     )
    (else 
     (display-string x y "                    ")
     (display-tower x (+ y 1) (- clear 1) tower)
     )
    )
  )

                    ; Position of the top of the tower on the screen
                    ; Shorter towers start further down the screen

(define (tower-pos tower)
  (- bottom-y (length tower))
  )

                    ; Display all of the towers, spaced 20 columns apart

(define (display-towers x towers)
  (cond ((not (null? towers))
     (display-tower x 0 (tower-pos (car towers)) (car towers))
     (display-towers (+ x 20) (cdr towers)))
    )
  )

                    ; Display all of the towers, then move the cursor
                    ; out of the way and flush the output

(define (display-hanoi)
  (display-towers left-x towers)
  (move-to 1 23)
  (flush-output)
  (delay move-delay)
  )

                    ; Reset towers to the starting state, with
                    ; all of the pieces in the first tower and the
                    ; other two empty

(define (reset-towers len)
  (set! towers (list (make-pieces len) () ()))
  (set! bottom-y (+ len 3))
  )

                    ; Move a piece from the top of one tower
                    ; to the top of another

(define (move-piece from to)

                    ; references to the cons holding the two towers

  (define from-tower (list-tail towers from))
  (define to-tower (list-tail towers to))

                    ; stick the car of from-tower onto to-tower

  (set-car! to-tower (cons (caar from-tower) (car to-tower)))

                    ; remove the car of from-tower

  (set-car! from-tower (cdar from-tower))
  )

                    ; The implementation of the game

(define (_hanoi n from to use)
  (cond ((= 1 n)
     (move-piece from to)
     (display-hanoi)
     )
    (else
     (_hanoi (- n 1) from use to)
     (_hanoi 1 from to use)
     (_hanoi (- n 1) use to from)
     )
    )
  )

                    ; A pretty interface which
                    ; resets the state of the game,
                    ; clears the screen and runs
                    ; the program

(define (hanoi len)
  (reset-towers len)
  (clear)
  (display-hanoi)
  (_hanoi len 0 1 2)
  #t
  )