# S Expression Interpreter > Build and understand s-expression interpreters in Python and C. Covers lexer-free tokenization, recursive descent parsing, eval-apply cycles, SymbolTable scoping, lval heap allocation with mpc, sfsexp library integration, and language semantics across Scheme (R4RS/R7RS), Common Lisp, and Clojure. Use when building a Lisp/Scheme interpreter from scratch, implementing s-expression data structures in C, adding function definitions and lexical scoping to an evaluator, or understanding how homoiconic languages process code-as-data through read-eval-print loops. - Skill: `tangledgroup/s-expression-interpreter` (Agent Skill, multi-file: 17 files) - Install (CLI): `npx skillmds@latest add tangledgroup/s-expression-interpreter` - Raw SKILL.md: https://api.skillmd.com/api/skills/tangledgroup/s-expression-interpreter/raw - Safety review: pending - Works with: Claude Code, Claude.ai, OpenAI Codex - Category: Integrations & APIs - Author: tangledgroup (https://skillmd.com/u/tangledgroup) - Updated: 2026-09-17 - Page: https://skillmd.com/skills/tangledgroup/s-expression-interpreter --- # S-Expressions Interpreter ## Overview An s-expression interpreter reads parenthesized prefix notation (s-expressions), parses them into an internal representation, evaluates the resulting structure through a recursive eval-apply cycle, and prints the result. The same syntax represents both code and data — this property, called **homoiconicity**, is what enables Lisp-family languages to manipulate programs as data structures. This skill covers three implementation approaches: - **Python interpreters** — from 16-line proofs-of-concept to full implementations with function definitions, lexical scoping, and special forms - **C s-expression libraries** — production parsing/manipulation (sfsexp) and educational heap-based lval structures with mpc parsing - **Language semantics** — how Scheme, Common Lisp, and Clojure define functions, handle arguments, and evaluate expressions ## When to Use - Building a Lisp or Scheme interpreter from scratch in Python or C - Implementing s-expression parsing without external lexer/parser libraries - Adding lexical scoping and function definitions to an existing evaluator - Understanding the eval-apply cycle that powers all Lisp implementations - Integrating sfsexp for s-expression data handling in C/C++ programs - Translating idioms between Python, Scheme, Common Lisp, and Clojure - Studying how homoiconic languages separate reading from evaluation ## Core Concepts **Homoiconicity**: Code is data. The expression `(+ 1 2)` is simultaneously a computation (returns 3) and a data structure (a list of three elements). Interpreters exploit this by manipulating programs as lists before evaluating them. **S-expression structure**: Every s-expression is either an **atom** (number, symbol, string) or a **list** of s-expressions in parentheses. This recursive definition represents any finite tree exactly. **Tokenization without lexers**: Lisp's parenthesized syntax allows trivial tokenization — pad parentheses with whitespace and split. No complex lexer needed: `input.replace('(', ' ( ').replace(')', ' ) ').split()`. **Recursive descent parsing**: Walk the token stream, building nested lists on `(` and returning atoms otherwise. The parser output is the AST — no separate transformation step required. **Eval-apply cycle**: `eval` takes an expression and environment, returns a value. For procedure calls, it evaluates the operator and all arguments, then `apply` creates a new environment frame binding parameters to arguments and evaluates the body. This recursion continues until expressions reduce to atoms. **Lexical scoping**: Functions capture the environment where they were defined. Environments form a chain of frames; variable lookup walks from innermost outward. This enables closures — functions that remember their defining context. **Special forms**: Certain operators (`if`, `define`, `lambda`, `and`, `or`) do not evaluate all arguments before execution. They control evaluation order and must be handled as explicit cases in the evaluator. ## Advanced Topics ### Python Interpreter Implementations - **Minimal 16-line proof-of-concept**: Ultra-concise tokenize→parse→eval pipeline for add/sub only → [Minimal 16-Line Lisp in Python](reference/02-bytegoblin-minimal-lisp-python.md) - **Minimal Scheme with comments**: ~25 lines, bytegoblin pattern plus `;` line comment support, four arithmetic ops → [Minimal Scheme with Comments in Python](reference/13-minimal-scheme-comments-python.md) - **Full Scheme with closures**: Complete tokenize→parse→eval→REPL with `;` comment support, SymbolTable scoping, closures, Scheme truth semantics → [Full Scheme Interpreter in Python](reference/12-full-scheme-interpreter-python.md) - **Full Lisp with defun/if/format**: Complete interpreter with SymbolTable scoping, user-defined functions, recursion → [Full Lisp Interpreter in Python](reference/01-lwcarani-full-lisp-python.md) - **Scheme with Lark parser**: Modern grammar-based parsing, tuple data model, TDD workflow → [Scheme Interpreter with Lark Parser](reference/03-johnj-scheme-python.md) ### C S-Expression Implementations - **sfsexp production library**: Continuation-based parser, linked-list sexp_t, embedded systems support → [Small Fast S-Expression Library](reference/04-sfsexp-c-library.md) - **Build Your Own Lisp Ch. 9**: lval struct with heap allocation, mpc parsing, pop/take helpers, eval-sexpr → [S-Expressions in C — BYOL Chapter 9](reference/05-byol-ch9-s-expressions-c.md) ### Scheme Language Semantics - **Academic introduction**: Expressions, compound values (cons/car/cdr), quoting, variadic functions, parameter passing modes → [Introduction to Scheme — Functional Notes](reference/06-eecs390-scheme-functional.md) - **R4RS standard procedures**: Boolean semantics, equivalence predicate tower (eq/eqv/equal/equalp?) → [R4RS Standard Procedures Reference](reference/07-r4rs-standard-procedures.md) - **R7RS expression specification**: Variable references, literals, procedure calls, lambda formal argument lists → [R7RS Expression Types Specification](reference/08-r7rs-expressions.md) ### Common Lisp and Clojure Semantics - **Python→Common Lisp cheatsheet**: Equality tower, sequence operations, hash-tables/alists/plists, LOOP macro, strings, regex, file I/O → [Python to Common Lisp Cheatsheet](reference/09-lispstudent-cl-cheatsheet.md) - **Common Lisp functions**: defun, funcall vs apply, multiple return values → [Common Lisp Functions Guide](reference/10-lisp-lang-functions.md) - **Clojure functions**: defn/fn, multi-arity, variadic with &, anonymous #(), Java interop → [Clojure Functions Guide](reference/11-clojure-functions.md)