Lips

A minimalist Lisp-like language in no_std Rust, inspired by ulisp.

While the original implementation was written by hand, a significant portion of this codebase was written by Claude. I am deeply ashamed.

Features

• Trait-based architecture: Shared core logic with multiple backends
• Two implementations:
  • lips-32: 32-bit cells, no_std compatible (embedded, WASM)
  • lips-64: 64-bit cells, reference implementation (development)
• 27 built-in functions: Arithmetic, lists, higher-order functions, control flow
• Tail-call optimization: Deep recursion via trampoline pattern
• Mark-and-sweep GC: Automatic memory management
• Unified REPL: Backend selection via --backend flag

Quick Start

# Start REPL (64-bit backend, default)
cargo run --bin lips-repl

# Use 32-bit backend (memory-constrained)
cargo run --bin lips-repl -- --backend 32

# Load a file
cargo run --bin lips-repl -- examples/factorial.lisp

# Read from stdin
echo "(+ 1 2)" | cargo run --bin lips-repl -- --stdin

Examples

Quicksort

(defn qsort (lst)
  (if (and lst (cdr lst))
    (let ((pivot (car lst))
          (tail (cdr lst)))
      (append
        (qsort (filter (fn (x) (< x pivot)) tail))
        (list pivot)
        (qsort (filter (fn (x) (not (< x pivot))) tail))))
    lst))

(qsort (list 3 1 2))
; => (1 2 3)

Memory Layout

All values are encoded as 32-bit tagged cells:

Cons (tag 000):
┌───┬─────┬─────────────────┬─────────────────┐
│ M │ 000 │  cdr (14 bits)  │  car (14 bits)  │
└───┴─────┴─────────────────┴─────────────────┘
 31  30 28  27            14  13             0

Int (tag 001):
┌───┬─────┬───────────────────────────────────┐
│ M │ 001 │     signed integer (28 bits)      │
└───┴─────┴───────────────────────────────────┘
 31  30 28  27                                0

Symbol (tag 010):
┌───┬─────┬───────────────────────────────────┐
│ M │ 010 │      symbol index (28 bits)       │
└───┴─────┴───────────────────────────────────┘
 31  30 28  27                                0

Builtin (tag 011):
┌───┬─────┬───────────────────────────────────┐
│ M │ 011 │       builtin id (28 bits)        │
└───┴─────┴───────────────────────────────────┘
 31  30 28  27                                0

Char (tag 100):
┌───┬─────┬───────────────────────────────────┐
│ M │ 100 │      unicode char (28 bits)       │
└───┴─────┴───────────────────────────────────┘
 31  30 28  27                                0

• M: Mark bit for garbage collection (bit 31)
• Tag: Type tag at bits 30-28 (3 bits)
• Pointers are 14-bit indices into arena (max 16,384 cells)
• NIL represented as max pointer value 0x3FFF
• Symbol table: null-terminated strings in flat buffer

Architecture

lips/
├── crates/
│   ├── lips-core/      # Trait definitions & shared logic
│   ├── lips-32/        # 32-bit no_std implementation
│   ├── lips-64/        # 64-bit reference implementation
│   ├── lips-repl/      # Unified REPL with backend selection
│   ├── lips-embedded/  # Embedded platform support (uses lips-32)
│   ├── lips-stm/       # STM microcontroller support (uses lips-32)
│   └── lips-wasm/      # WebAssembly bindings (uses lips-32)

Core Traits (lips-core)

• LipsObject: Tagged union encoding/decoding
• LipsArena: Memory management and allocation
• LipsRuntime: Evaluation, read, and built-in functions

All backends implement these traits, enabling code reuse and testing.

Built-in Functions

Arithmetic

+, -, *, /, <, =

Lists

cons, car, cdr, list, first, second, third

Higher-Order

map, apply

Control Flow

if, do, let, fn, def, defn

Logic

and, or, not

Meta

gc, env, eval

Documentation

• CLAUDE.md: Project overview and implementation details
• MIGRATION.md: Migration guide from old implementations
• AUDIT.md: Feature comparison and analysis
• TODO_CLEANUP.md: Cleanup and migration plan

Testing

# Run all tests
cargo test --workspace

# Test specific backend
cargo test -p lips-32
cargo test -p lips-64

# Test with example files
cargo run --bin lips-repl -- examples/factorial.lisp