Lispy: Wie man einen Lisp-Interpreter in Python schreibt

Peter Norvigs “How to Write a (Lisp) Interpreter (in Python)” ist eines der berühmtesten Tutorials zur Sprachimplementierung. Der Artikel erklärt, wie man einen Interpreter baut – ausgehend von einem einfachen Taschenrechner bis zum vollständigen Scheme-Subset.

Warum Lisp?

Lisp ist syntaktisch rein. Alan Kay nannte LISP die “Maxwell’s Equations of Software” – ein mathematisch elegantes Fundament. Steve Yegge beschrieb Lisp als “eine Programmiersprache, die sich selbst schreibt”.

Die Syntax ist minimal:

• Zwei atomare Formen: Zahlen und Symbole
• Zwei Sonderformen: if und define
• Alles andere sind Listenausdrücke

Zwei-Schritt-Implementierung

1. Lispy Calculator

Zuerst baut Norvig einen Interpreter für fünf syntaktische Formen:

• Variablen-Referenzen
• Konstanten-Literale
• Conditionals (if test conseq alt)
• Definitionen (define symbol exp)
• Prozedur-Aufrufe (proc arg...)

Das reicht für jeden Taschenrechner – plus if-Expressions und Variable-Definitionen.

2. Vollständiger Scheme-Interpreter

Dann erweitert er Lispy um:

• Lambda-Ausdrücke
• Lexikalische Scoping
• Quote und Quasiquote
• Tail-Call-Optimierung

Die Core-Insight: Parsing + Evaluation

Jeder Interpreter macht zwei Dinge:

Parsing verwandelt Zeichenketten in abstrakte Syntaxbäume (ASTs). Norvig zeigt, wie man mit minimaler Tokenisierung und rekursivem Descent aus einem String (sqrt (* 2 8)) die verschachtelte Liste ['sqrt', ['*', 2, 8]] macht.

Evaluation führt den AST aus. In Scheme ist das besonders elegant: Eval rekursiv über die Struktur, Umgebungen als Dicts {variable: value}, und Scheme-Prozeduren als Python-Callables.

def eval(x, env):
    if isinstance(x, Symbol):
        return env[x]
    elif isinstance(x, Number):
        return x
    elif x[0] == 'if':
        _, test, conseq, alt = x
        return eval(conseq if eval(test, env) else alt, env)
    # ... mehr Cases

Warum das Tutorial zeitlos ist

Norvig zeigt nicht nur wie, sondern warum. Er erklärt:

• Environment-Chains für lexikalisches Scoping
• Closures als “Datenstruktur mit Code”
• Die Eleganz minimaler Syntax

Für jeden, der Compiler und Interpreter verstehen will, ist Lispy der goldene Standard. In ~130 Zeilen Python hat man einen funktionierenden Scheme-Interpreter.

Link zum Originalartikel