Lispirito

A portable LISP implementation for memory-constrained systems. It works from MOS 6502 to modern ARM/Intel 64-bit machines.

Project goals

• Binary size smaller than 31.5K on MOS 6502 (on a minimal build), yet capable with modern architectures.
• Macro expansion support for syntactic sugar.
• Depend on a minimal set of libc functions.
• The code should be small, portable, and pedagogical, easy to understand.
• The code prioritizes the reduction of binary image and making evident the evaluator's meta-circular property instead of focusing on performance.

This project is meant as a "software continuation" of a 6502 breadboard computer (such as the projects discussed in the 6502 Forum and Ben Eater's machine). Lispirito also aims to demonstrate how one can overcome limitations inherent to the 6502 such as the 256-byte hardware stack (with function frames in the heap), how to implement garbage collection and recycling using reference counting, how to overcome the problem that closures refer to their own environment and could create a reference counting loop (well... that one still needs work), and other similar implementation issues.

Importantly, the code should make evident the intricate the so-called meta-circular relationship between the eval (Evaluation) and apply (Function Application) subroutines in the code, as discussed in the beautiful Wizard Book (Structure and Interpretation of Computer Programs). Hence, the interpreter is written in a way to not trade clarity for performance: the code should be pedagogical and stylish. There are always rough edges to be revised, but as much thought will be given to style and clarity as to efficiency.

Quick tutorial over features

Please refer to TUTORIAL.md.

Supported features

We support a a good subset of the Scheme R7RS-small specification and C-style memory operations:

• "McCarthy" operators: quote, car, cdr, atom?, eq?, cons, cond, lambda, eval, define
• Association and substitution: assoc, subst
• Type support:
  • pair?, char?, boolean?, string?, number?, integer?, real?
  • integer->real, real->integer, integer->char, char->integer, number->string, string->number
• Arithmetic operators: +, -, *, /
  • If you want an n-ary operator, use apply together with the operators above
• Arithmetic comparison operators: <, =, >, <=, >=
• Logical operators: and, or, not
  • If you want an n-ary and/or, use apply together with and/or
• Environment and macro support: begin, let, let*, set!, macro, current-environment
• Low-level memory operations (C-style): mem-alloc, mem-read, mem-write, mem-fill, mem-copy, mem-addr
  • Display support: display, newline
• I/O and file load/save (Commodore 64 and systems with C I/O): open, close, read, write, load!, save!

Load the standard library files with load! to get access to additional routines:

Library	Functions
lib-funct.lsp	map, foldl, foldr, filter
lib-list.lsp	length, reverse, append, list, flatten, list?
lib-utils.lsp	if
lib-assoc.lsp	assoc-replace, assoc-delete
lib-math.lsp	abs, modulo
lib-strings.lsp	make-string, string-length, string-ref, string-set!, string-append, substring, string->list, list->string
lib-streams.lsp	stream-cons, stream-car, stream-cdr, stream-range, stream-map, stream-filter, stream-foreach, stream-yield

Lambda definitions create closures, and cond, and/or, and begin are all tail-recursive (just make sure to recur in tail-position).

Notably missing features

• Although a good subset of the Scheme R7RS-small specification is covered, many operators or data structures are left out due to space (notably vectors and maps). It should be fairly straightforward to extend the implementation to add them, but that would increase the footprint past our size goal of 31.5K.

Future plans

• Support for call/cc
• Versions for DOS, Amiga, and BSD 2.11 on a PDP-11. Building and running on modern systems should be already trivial.

Building

If you are building Lispirito in a modern system, just a simple make clean; make install should work. If you have working fopen, fclose etc, use make TARGET_LIBC_IO=1 to include I/O. To include debugging, use make DEBUG=1 as your build command.

If you are building for 6502 platforms, use make clean; make TARGET_6502=1. If you are building for the Commodore 64, use make clean; make TARGET_6502=1 TARGET_C64=1.

If you are compiling Lispirito for MOS 6502 (in particular Ben Eater's machine), first download the LLVM-MOS SDK in the link below, and place it alongside this project directory. You might want to adjust the CXX location in your Makefile depending on where your SDK is. You can find the SDK here:

• Linux
• Mac OS
• Windows

If you are using macOS, make sure to remove the quarantine of the file before extracting it.

$ xattr -d com.apple.quarantine llvm-mos-macos.tar.xz

Tweaks

You can change the default definitions of Integral and Real in extra.h to best accommodate the build to your system.

Have fun!