tiny-lisp

A small but real Lisp/Scheme interpreter written in pure Python (standard library only, no dependencies). It has a proper S-expression reader, an evaluator with lexical environments and closures, and enough special forms and primitives to write recursive programs like factorial, Fibonacci, list recursion, and stateful counter closures.

This is a learning-grade interpreter that is honest about being a subset of Scheme. See What it does NOT do below.

Requirements

• Python 3.8+ (developed and tested on CPython 3.12 / 3.14). Standard library only.

Usage

Run a file:

python3 lisp.py examples/demo.lisp

Load a file and then evaluate an extra expression:

python3 lisp.py examples/demo.lisp -e "(fact 5)"
# ... file output ...
# 120

Evaluate a one-off expression:

python3 lisp.py -e "(+ 1 (* 2 3))"
# 7

Interactive REPL (no arguments):

python3 lisp.py
tiny-lisp REPL. Ctrl-D to exit.
lisp> (define (square x) (* x x))
lisp> (square 12)
144

Example program

From examples/demo.lisp:

(define (fact n)
  (if (= n 0) 1 (* n (fact (- n 1)))))

(define (range a b)
  (if (>= a b) '() (cons a (range (+ a 1) b))))

(define (map1 f xs)
  (if (null? xs) '() (cons (f (car xs)) (map1 f (cdr xs)))))

(define (make-counter)
  (let ((n 0))
    (lambda () (set! n (+ n 1)) n)))

(define tick (make-counter))

(display (map1 (lambda (x) (* x x)) (range 1 6))) (newline)  ; (1 4 9 16 25)
(display (list (tick) (tick) (tick)))             (newline)  ; (1 2 3)

Output:

10! = 3628800
fib(20) = 6765
squares 1..5 = (1 4 9 16 25)
sum 1..100 = 5050
counter: (1 2 3)

Language reference

Reader

• Integers (42, -3), floats (3.14), symbols (foo, +, map1).
• Lists: (+ 1 2), nesting to any depth.
• Booleans: #t, #f. The empty list: () / '().
• Strings: "hello" with \n, \t, \", \\ escapes (minimal).
• Quote shorthand: 'x reads as (quote x).
• Line comments with ;.

Special forms

quote, if, define, lambda, let, begin, set!, and, or, cond.

• define supports both (define x 5) and the function shorthand (define (f a b) body...).
• lambda closes over its defining environment (true lexical closures).
• cond supports an else clause.

Builtins

• Arithmetic: + - * / mod
• Comparison: = < > <= >= (variadic chaining, e.g. (< 1 2 3))
• Lists: car cdr cons list null? pair? eq?
• Logic/other: not display newline

Semantics worth stating explicitly

• Truthiness: only #f is false; everything else (including 0 and ()) is true, as in Scheme.
• Division /: returns an exact int when the operands divide evenly (e.g. (/ 6 3) → 2), otherwise a Python float ((/ 7 2) → 3.5). A single argument gives the reciprocal ((/ 4) → 0.25). Division by zero is an error.
• mod: integers only, uses Python's % semantics (result takes the sign of the divisor, so (mod -17 5) → 3).
• Integers: are Python int, so they are arbitrary precision (bignum) for free — (fact 100) is exact.

Running the tests

python3 -m unittest -v

The suite (test_lisp.py) is hermetic and covers:

• Core programs with pinned results: (fact 10) → 3628800, (fib 20) → 6765, list sum/map-style recursion, let scoping, closures, a set!-based counter closure, cond, mutual recursion (even?/odd?), and nested recursion (small Ackermann).
• Arithmetic cross-checked against Python: ~2500 randomly generated nested (+ - *) integer expressions (fixed seeds) are evaluated by tiny-lisp and by Python's own eval, and compared exactly. Division has its own semantic tests.
• Reader round-trip: parse → write → parse yields the same structure, and unbalanced/stray parens and unterminated strings raise errors.
• Error cases: unbound symbol, wrong arity (user and builtin), car of empty list, applying a non-procedure, set! on an unbound name, and type errors in arithmetic all raise a clear LispError.

What it does NOT do

tiny-lisp is intentionally a subset of Scheme. It does not implement:

• Macros (define-syntax, syntax-rules) — no hygienic or unhygienic macros of any kind.
• call/cc or continuations of any form.
• Guaranteed tail-call optimization. Recursion runs on the Python call stack, so very deep non-tail recursion will hit Python's recursion limit and raise a RecursionError (the REPL reports this cleanly). Factorial/Fibonacci at the sizes shown are fine.
• Improper/dotted pairs. cons requires its second argument to be a list; there is no dotted-pair (a . b) reader syntax. Lists are backed by Python lists, not cons cells.
• The full numeric tower. There are only Python int and float. No exact rationals, no complex numbers. (Integers are arbitrary precision because Python's are — there are no bignum quirks beyond Python's own.)
• Rich strings/characters. Strings exist with a minimal escape set and no string-manipulation library; there is no character type, no string-append, etc.
• The full R7RS standard library. Only the builtins listed above are provided. There is no apply, map builtin (you define your own), vector, hash-table, ports/file I/O beyond display/newline, named let, letrec (top-level define covers recursion instead), or quasiquote/unquote.

If you need any of the above, this is the wrong tool — but the ~700 lines of lisp.py are meant to be readable and easy to extend.

License

MIT — see LICENSE.