Felix fragte mich, wie schwer es sei, eine Programmiersprache zu entwerfen. Ich möchte das hier einmal demonstrieren.
Zunächst werde ich mich auf einen Interpreter beschränken, also ein Programm, das den Quelltext einliest und direkt ausführt und nicht in (virtuellen) Maschinencode übesetzt, der dann von einer (virtuellen) Maschine ausgeführt wird.
Dann werde ich die Syntax der Programmierspache radikal einschränken. Typische (Mainstream-)Sprachen haben recht viel Syntax, die zu implementieren zwar nicht schwer, aber doch aufwendig ist. Manchmal ist es (ich schaue auf dich, Ruby) tatsächlich verdammt schwer.
Schließlich werde ich kein komplexes Laufzeitsystem, sondern eine einfache funktionale Sprache mit wenigen Operatonen haben und es den Lesern überlassen, das zu erweitern.
Ich bin jetzt versucht, einfach Lisp zu implementieren.
Ach warum nicht. Machen wir das als Fingerübung!
LISP (Lots of Irritating Superfluous Parentheses, äh, nein, LISt Processing) kennt Atome wie Zahlen oder Symbole und geklammerte Ausdrücke a.k.a. Listen, die aus Atomen oder anderen geklammerten Ausdrücken bestehen.
foo
(foo bar)
(foo (bar baz))
Als kontextfreie Grammatik in EBNF sieht das so aus:
expr = atom | "(" {expr} ")"
Ein atom sei jede nicht-leere Sequenz von Zeichen außer whitespace und den runden Klammern. Wir schließen auch noch ; aus, weil das einen Kommentar bis zum Zeilenende einleiten soll, der auch als whitespace zählt.
Ein expr ist also entweder so ein Atom oder eine Liste, die mit ( beginnt, wo dann null oder mehr weitere beliebig komplexe Ausdrücke folgen (die Grammatik ist damit rekursiv) und dann irgendwann eine ) kommt.
Es ist offensichtlich, dass das eine LL(1)-Sprache ist. Und auch egal.
Hier ist die Definition der Fibonacci-Funktion fib als Beispiel:
(define (fib n)
(if (< n 3) 1
(+ (fib (- n 1)) (fib (- n 2)))))
So ruft man sie auf:
(fib 30)
Ein Listen-Ausdruck wie (- n 2) heißt auch Form. Er wird berechnet, indem rekursiv alle Teilausdrücke berechnet von links nach rechts werden. Der erste Teilausdruck einer Form muss zu einer Proc (einer eingebauten oder benutzerdefinierten Prozedur) ausgewertet werden, die dann mit den Ergebnissen der Berechnung aller anderen Teilausdrücke aufgerufen wird. Das Ergebnis dieses Aufrufs (der auch Applikation heißt) ist dann das Ergebnis oder auch der Wert des Ausdrucks.
Der Wert von (- n 1), wenn n an 2 gebunden ist, ist somit 1.
Daneben gibt es sog. Special-Forms wie (define ...) und (if ...), für die andere Berechnungsvorschriften gelten. Daher sind sie special.
- Bei
ifmuss es immer drei weitere Teilausdrücke geben wobei zunächst nur der erste ausgewertet wird und abhängig davon, ob dieser als wahr oder falsch gilt, dann einer der anderen beiden Teilausdrücke berechnet und der andere ignoriert wird. definezum Erzeugen einer benutzerdefinierten Prozedur wertet gar nichts aus, sondern erwartet als ersten Teilausdruck eine nicht-leere Liste aus Atomen – sog. Symbolen – und legt dann unter dem ersten Symbol aus der Liste eine Proc an, die, wenn sie aufgerufen wird, den zweiten Teilausdruck ausführt, wobei noch alle Parameter (alle anderen Symbole aus dem ersten Teilausdruck) an die übergebenen Werte gebunden werden.
Hinweis: "Unter einem Namen anlegen" heißt dabei, dass in der globalen Umgebung dieser Wert an das entsprechende Symbol gebunden wird. Dies ist der gleiche Vorgang, der auch lokal für einen Prozeduraufruf passiert, für den jeweils eine lokale Umgebung angelegt wird, in der auch wieder Werte (die Argumente) an Symbole gebunden werden.
Jetzt kennt ihr (meine Teilmenge von) Lisp.
Ein Compiler oder Interpreter zerlegt traditionell den Quelltext zunächst in Token (mit Hilfe eines Scanners) und baut dann einen aus Knoten (Nodes) bestehenden abstrakten Syntaxbaum (AST) aus den Token auf (mit Hilfe eines Parsers). Ein Interpreter wertet jetzt (meist rekursiv) diesen AST direkt aus. Ein Compiler würde in ein oder mehreren Phasen daraus Maschinencode erzeugen, meist in Form einer Objektdatei, die dann mittels eines Linkers mit anderen Objektdateien und Bibliotheken solcher Dateien verknüpft wird und das Ergebnis als ausführbareres Programm abgespeichert wird.
Abstrakt sähe das in Dart so aus:
class Token {
Token(this.type, [this.value]);
final TokenType type;
final Object? value;
}
enum TokenType { ... }
class Scanner {
Scanner(this.source);
Iterable<Token> tokens { ... }
}
class Parser {
Parser(this.scanner);
Node parse() { ... }
}
abstract class Node {
dynamic evaluate(Environment e);
}Bei Lisp kann ich mir den Scanner sogar schenken, wenn ich einfach Listen meiner Programmiersprache – Dart – nehme. Weil dartfmt auf eine eher unkonventionelle Formatierung besteht, ist das nicht die lesbarste Variante, aber wir können uns den ganzen oben skizzierten Code sparen.
Hier ist fib in Dart:
const fib = [
'define',
['fib', 'n'],
[
'if',
['<', 'n', 3],
1,
[
'+',
[
'fib',
['-', 'n', 1]
],
[
'fib',
['-', 'n', 2]
]
]
]
];Ich kann mir auch dedizierte Node-Klassen schenken, denn ich nehme diese verschachtelte Listenstruktur (zusammen mit Zahlen und Strings) direkt als AST und interpretiere sie sofort mit Hilfe einer gleich zu definierenden Funktion eval().
Zunächst brauche ich aber eine Umgebung (oder Environment), in deren Kontext ich alles auswerten will. Das ist im Prinzip eine Map in Dart, allerdings kennt jede Umgebung immer noch ihren Vater, weil Lisp bzw. Scheme das so fordert, damit das Binden von Symbolen sinnvoll funktioniert. An dieser Stelle spare ich mir die Details und verweise auf eine beliebige Anfänger-Vorlesung zu diesem Thema.
class Env {
Env(this.bindings, [this.parent]);
final Map<String, dynamic> bindings;
final Env? parent;
}Will ich später ausdrücken, dass a für den Wert 42 steht (bzw. die 42 an das Symbol a gebunden ist bzw. das a den Wert 42 bindet), sieht das dann so aus:
final env = Env({'a': 42});Es ist noch praktisch zu definieren, was eine Proc ist:
typedef Proc = dynamic Function(List, Env);Es ist eine Dart-Funktion, die eine Liste mit unausgewerteten Teilausdrücken übergeben bekommt, sowie die Umgebung, in der ich sie auswerten muss. Ich mache das so, weil es sich in 50+ Jahren als besten Weg für einen kompakten Interpreter herausgestellt hat.
Nun kann ich die initiale Umgebung env definieren, in der alle Forms und Special-Forms, die ich für fib brauche, vordefiniert sind:
final env = Env({
'define': _spcl((exp, env) =>
env[exp[1][0]] = _proc(exp[1].skip(1), exp[2], env)),
'if': _spcl((exp, env) => env.eval(exp[env.eval(exp[1]) ? 2 : 3])),
'<': _form((args) => args[0] < args[1]),
'+': _form((args) => args[0] + args[1]),
'-': _form((args) => args[0] - args[1]),
});Ich nutze einen beliebten Trick, um Forms und Special-Forms gleich zu machen, indem ich Forms als Spezialfall der Special-Forms erkläre und nie Argumente automatisch auswerte. Ich mache damit alle Argumente zu thunks, nur um diesen Begriff mal zu erwähnen. Nur in den Fällen, wo ich's brauche, werte ich explizit aus und habe das in _form() für "normale" Prozeduren abstrahiert. Die Funktion _spcl() hilft Dart, den richtigen Datentyp zu finden und mir, die anonyme Funktion (exp, env) => ... nicht explizit typisieren zu zu müssen.
Proc _spcl(Proc proc) => proc;Hier ist _form:
Proc _form(dynamic Function(List) fn) {
return (exp, env) => fn(exp.skip(1).map(env.eval).toList());
}Bemerkung: Ich wünschte, Dart würde wie JavaScript destructing assignments beherrschen, damit ich eine Liste von Werten auf einzelne Parameter verteilen könnte, denn _form((a, b) => a + b) wäre so viel schöner zu lesen. Ebenfalls wünschte ich mir, es gäbe ein apply und/oder bind für Function-Objekte in Dart. Man könnte sich allerdings mit _form0 bis formN behelfen.
Ich möchte jetzt einfach sagen, die Implementierung aller Procs sollte naheliegend sein, gestehe aber, dass if ziemlich kompakt (aber einfach) ist und das define wahrscheinlich ein bisschen sacken muss. Mehr als diese beiden Befehle (und Rekursion) braucht es übrigens nicht, um eine universelle Programmiersprache zu bauen.
Hier ist _proc, was den Kern meines Interpreters ausmacht: Den Aufruf von eigenen Funktionen. Ich liebe die Eleganz – sprich Kompaktheit – dieser Implementierung von Lisp. (Den cast brauche ich nur, weil ich Env so definiert habe, dass alle Schlüssel String a.k.a. Symbole sind – das könnte man aufgeben und hoffen, dass Parameterlisten immer wohldefiniert sind, dann wäre auch diese Funktion ein Einzeiler):
Proc _proc(Iterable params, dynamic body, Env env) {
final p = params.cast<String>();
return _form((args) => Env(Map.fromIterables(p, args), env).eval(body));
}Was wir jetzt noch brauchen ist eval(), dass ich als Methode von Env implementiere und noch mal in drei Teile gespalten habe, damit es klarer wird:
extension on Env {
dynamic eval(dynamic exp) {
if (exp is String) return lookup(exp);
if (exp is List) return evalList(exp);
return exp;
}
dynamic lookup(String name) {
if (bindings.containsKey(name)) return bindings[name];
if (parent != null) return parent!.lookup(name);
throw Exception('unbound $name');
}
dynamic evalList(List exp) {
if (exp.isEmpty) return null;
return (eval(exp[0]) as Proc)(exp, this);
}
}Zu beachten ist, dass mein Interpreter zwar mit Zahlen und Boolschen Werten (die ich heimlich durch < eingeführt habe) klar kommt, aber keine Strings kennt, weil ich diesen Dart-Datentyp für Symbole nutze, die ich immer in Env nachschlage. Dart kennt zwar auch einen Type namens Symbol, der ist aber leider so systemnah und damit eingeschränkt, dass er für unsere Zwecke ungeeignet ist. In einem "richtigen" Interpreter würde man sich einen eigenen Typ definieren. Ebenfalls zu beachten ist, dass ich ungebundene Symbole hart mit einer Exception bestrafe. Ich prüfe auch nicht, ob bei (foo bar) das foo wirklich ein Proc ist. Stattdessen kracht es bei as Proc.
Aber jetzt funktioniert dies:
void main() {
env.eval(fib);
print(env.eval(['fib', 30]));
}
Es sollte 832040 ausgegeben werden.
Weitere eingebaute Funktionen sollte jetzt jeder bequem in env einhängen können. Wer unbedingt möchte, kann sich auch noch ein set! zum Ändern von Bindings (und damit das Konzept von "echten" Variablen) definieren.
env['set!'] = _spcl((exp, env) =>
env.bindings[exp[1] as String] = env.eval(exp[2]));So richtig Spaß macht Lisp nur, wenn man auch anonyme Funktion (a.k.a. lambdas) definieren kann, wofür ich gerne den Namen fn (statt lambda) nehme.
Der Ausdruck (fn () 1) ist eine anonyme Funktion, die keine Parameter hat und eine 1 liefert.
Eigentlich ist mein define syntaktischer Zucker für (set! name value) wobei value natürlich auch eine anonyme Funktion (fn ...) sein kann, also (set! fib (fn (n) ...)).
Der "Zufall" will, dass fn sehr einfach mit Hilfe von _proc zu definieren ist:
env['fn'] = _spcl((exp, env) => _proc(exp[1], exp[2], env));
env['λ'] = env['fn'];Bemerkung: Die zweite Zeile ist ein Spleen von mir, weil ich es mag, wenn man auch das Unicode-Zeichen U+03BB (Greek Small Letter Lambda) λ als Symbol benutzen kann.
Funktionsrümpfe (oder Prozedurrümpfe, wie Lisp das korrekter nennt) werden manchmal auch des Seiteneffekts willens ausgeführt und sollen daher mehr als einen Ausdruck enthalten können. Dafür kennt Lisp IIRC traditionell die Special-Form begin, aber ich werde sie seq nennen. Es werden alle Teilausdrücke ausgewertet, aber nur das Ergebnis des letzten Teilausdrucks ist der Wert von seq. Gibt es keine Teilausdrücke, sei das Ergebnis null.
Man beachte, dass (seq a b) äquivalent zu ((fn (a b) b) a b) und damit eigentlich nur syntaktischer Zucker ist.
Mit seq kann man sowas schreiben:
(seq
(define (fib n) ...)
(fib 30))
Tatsächlich zieht Lisp einen Großteil seiner Mächtigkeit aus der Tatsache, dass man in Lisp Makros definieren kann, die dann automatisch bestimmte Formen in andere Formen umwandeln, noch bevor sie vom Interpreter ausgeführt werden und man auf diese Weise neue Varianten von if u.ä. definieren kann. Auf diese Weise könnte man dann seq als Makro definieren.
Unter der Annahme, dass expand als Meta-Operation gäbe, gilt dann:
expand[(seq)] → ()
expand[(seq a)] → a
expand[(seq a b...)] → ((fn (a b) b) a expand[b...])
Will man z.B. auch noch lokale Variablen erlauben, was Lisp traditionell mit der special form let (bzw. let*) kann, kann man auch solche Ausdrücke mittels Makroexpansion in fn umwandeln:
expand[(let () body)] → body
expand[(let (pairs) body)] →
((fn eval[(map 1st pairs)] body)
unsplice[eval[(map 2nd pairs)]])
So einen Makro-Expander schreibt man in nicht mehr als fünf oder sechs Zeilen Lisp, aber das kann ich leider nicht auswendig und lasse es daher hier weg. Wer möchte, kann sich selbst daran versuchen, er braucht eigentlich das quote von weiter unten.
Ich baue aber meinen Interpreter um, damit er mehr als einen Ausdruck innerhalb von _proc auswerten kann und dann das Ergebnis des letzten Ausdrucks liefert. Dann bekomme ich seq quasi geschenkt. Für den Fall, dass die Funktion gar keinen Rumpf hat, ist der Wert null. Statt eval werde ich nun evalSeq benutzen und dort nicht mehr einen einzelnen Teilausdruck, sondern eine Aufzählung von Teilausdrücken übergeben.
final env = Env({
'define': _spcl((exp, env) => env[exp[1][0]] = _proc(exp[1].skip(1), exp.skip(2), env)),
'fn' = _spcl((exp, env) => _proc(exp[1], exp.skip(2), env)),
...
});
Proc _proc(Iterable params, Iterable body, Env env) {
final p = params.cast<String>();
return _form((args) => Env(Map.fromIterables(p, args), env).evalSeq(body));
}
...
extension on Env {
dynamic evalSeq(Iterable exp) => exp.fold(null, (_, exp) => eval(exp));
}Ich habe ein Stück wichtige Syntax in Lisp bislang unterschlagen. Manchmal möchte man nicht, dass ein Ausdruck ausgewertet wird, sondern es einfach so für sich selbst als Datum nutzen. Man möchte es dazu quoten, d.h. etwas vor der Auswertung schützen. Dazu dient die Special-Form quote mit denkbar simpler Implementierung:
final env = Env({
...
'quote': _spcl((exp, env) => exp[1]),
});Gäbe es ein print in meinem Interpreter (sollte jeder selbst in 45sek hinzufügen können), könnte man jetzt (print (quote hallo-welt)) schreiben und würde dann das Symbol selbst und nicht den (falls vorhanden) an es gebundenen Wert ausgeben.
Da (quote …) ein bisschen umständlich ist, kann man das in Lisp auch als '… (eben das Quote-Zeichen) abkürzen und hat damit das erste bisschen "echte" Syntax in der Sprache.
Hier komme ich jedoch mit meiner Dart-Listen-Implementierung an ihre Grenze und zeige zum Abschluss daher noch, wie man einen Lisp-Scanner und -Parser baut, der diese um ' erweiterte Grammatik verarbeiten kann:
expr = atom | "(" {expr} ")" | "'" expr
Ich mache beides in einer Funktion read(), die einen regulären Ausdruck nutzt, um Atome zu erkennen. Die Funktion nutzt einen Stack statt Rekursion, was sie wahrscheinlich schwerer verständlich macht, aber ein alter Trick aus einer Zeit ist, wo Programme sehr darauf achten mussten, wie viele rekursive Aufrufe sie machen, da der System-Stack möglicherweise auf 16 Ebenen begrenzt war.
Sie muss außerdem noch damit klar kommen, dass ' speziell zu behandeln ist. Auch das habe ich schon mehrfach implementiert und daher einen recht kompakten Weg dafür gefunden, denke ich. Dennoch kratzt sie ein bisschen an der Eleganz des Stack-Parsers.
final _re = RegExp(r"\s+|;.*$|(\d+(?:\.\d+)?)|([()']|[^()'\s;]+)", multiLine: true);
dynamic read(String s) {
Iterable tokens() sync* {
for (final m in _re.allMatches(s)) {
if (m[1] != null) yield num.parse(m[1]!);
else if (m[2] != null) yield m[2]!;
}
}
final stack = [[]];
void pop() => stack[stack.length - 2].add(stack.removeLast());
bool quoting() => stack.last.first == 'quote';
for (final token in tokens()) {
if (token == '(') {
stack.add([]);
} else if (token == ')') {
pop();
if (quoting()) pop();
} else if (token == "'") {
stack.add(['quote']);
} else {
stack.last.add(token);
if (quoting()) pop();
}
}
return stack.single;
}Nun sollte dies gehen:
const s = '''
(define (fib n)
(if (< n 3) 1
(+ (fib (- n 1)) (fib (- n 2)))))
(fib 30)
''';
void main() {
print(env.evalSeq(read(s)));
}Einen Parser für eine syntax-reichere Sprache kommt ein anderes Mal. Tatsache ist, dass fast jede Programmiersprache im Prinzip die selbe Semantik wie mein Lisp hat und damit im Kern genau so ausgeführt wird.