Lisp Evaluator

A Lisp evaluator with fully trampolined evaluation - no Rust stack recursion, enabling unlimited recursion depth (bounded only by heap/arena size).

Key Features

• Full Trampolining: All evaluation uses continuation-passing style with an explicit continuation stack. No Rust recursion means no stack overflow.
• Strict Evaluation: Call-by-value semantics - all arguments are evaluated before function application
• Proper TCO: Tail calls reuse the same continuation frame
• Lexically Scoped Closures: First-class functions with captured environments
• Rich Error Handling: Error messages with stack traces
• Pattern Matching: case for value matching
• Iteration: do loops for imperative-style iteration
• Meta-programming: eval for runtime code evaluation, quasiquote/unquote
• Mutation: set!, set-car!, set-cdr! for imperative programming

Evaluation Strategy

This evaluator uses strict (call-by-value) evaluation:

• All function arguments are fully evaluated before the function is called
• This provides predictable evaluation order and side-effect timing
• Tail call optimization is supported for constant-space recursion

Mutation

This Lisp supports mutation operations for imperative programming:

• set! - Mutate a variable binding
• set-car! - Mutate the car of a cons cell
• set-cdr! - Mutate the cdr of a cons cell

Note: Mutation breaks referential transparency but enables imperative patterns.

Truthiness

Only #f is false. Everything else (including the empty list '()) is truthy.

Special Forms

• quote - Return expression unevaluated
• if - Conditional
• cond - Multi-way conditional
• case - Pattern matching on values
• lambda - Create closure
• define - Define variable/function
• set! - Mutate variable binding
• let - Local binding
• let* - Sequential local binding
• begin - Sequence of expressions
• and / or - Short-circuit boolean operations
• do - Iteration with initialization and step expressions
• quasiquote - Template with unquote and unquote-splicing
• eval - Evaluate expression at runtime
• apply - Apply function to argument list
• values - Return multiple values as a list