Keiner hat die ursprüngliche Frage beantwortet. Das möchte ich nachholen.
Wie baut man denn nun eine eigene Sprache - egal ob mit deutschen oder englischen Schlüsselwörtern?
Ich stelle informell eine einfache Programmiersprache mit Präfixnotation vor, zeige wie man einen Scanner für Wörter dieser Sprache baut, einen Parser, der geklammerte Blöcke erkennt und einen Interpreter, der Wörter ausführen kann. Nicht unbedingt in dieser Reihenfolge.
Hier sind Beispiele in meiner Sprache:
schreibe "Hallo"
gruß ist "Hallo Welt"
schreibe gruß
schreibe nur gruß
schreibe (addiere 3 4)
schreibe [addiere 3 4]
a ist 1 ; wenn nicht null? a [schreibe a]
Zahlen und Zeichenketten sehen so aus wie immer. Mit schreibe kann ich etwas auf dem Bildschirm anzeigen. Das ist weist dem Wort davor den Wert des Ausdruck dahinter zu. Das kann man auch kurz als wort: ausdruck schreiben. Steht vor einem Wort ein nur, ist nicht dessen zugewiesener Wert sondern das Wort selbst gemeint, was man auch als :wort schreiben darf.
Runde Klammern bestimmen die Auswertungsreihenfolge, die ansonsten strikt von links nach recht geht. Jedes Befehlswort weiß, wie viele Argumente es braucht. schreibe hat ein Argument, addiere hat zwei. Daher sind Trennzeichen wie ; optional. Eckige Klammern bilden einen Block, der nicht (wie Blöcke mit runden Klammern) implizit ausgewertet wird. Dies ist wichtig für z.B. Bedingungen. wenn hat zwei Argumente, etwas das zu einem Wahrheitswert wird und einen Block, der nur dann ausgeführt wird, wenn der Wert des ersten Arguments "wahr" ist.
Komplexe Fallunterscheidungen sind auch möglich:
falls [
[null? a] [schreibe "a ist 0"]
[null? b] [schreibe "b ist 0"]
]
Tatsächlich kann man dieses falls selbst definieren - es ist kein Syntax:
falls ist funktion [alternativen] [
wenn leer? alternativen [antworte nichts]
wenn führe_aus bei alternativen 1 [antworte bei alternativen 2]
falls nächster nächster alternativen
]
Mit funktion kann ich eigene Funktionen definieren. Zwei Argumente bestimmen die Parameter und den Rumpf der neuen Funktion - beides Blöcke. Die Befehlswörter leer?, bei oder nächster greifen auf Blöcke zu, die meine zentrale Datenstruktur sind. Hat ein Block keine Element, liefert leer? den Wahrheitswert wahr, ansonsten eben falsch. Mit bei hole ich mir ein Blockelement an dem entsprechenden Index, wobei das erste Element den Index 1 hat. Und nächster liefert einen Block mit allen Elementen außer dem ersten. Das würde ich mit erster block bekommen, einer Alternative zu bei block 1.
Im Gegensatz zu vielen anderen Sprachen hat meine Sprache also keine festgelegten Schlüsselwörter. Wirklich alles (auch wenn oder funktion) sind Befehlswörter (kurz Wörter) die umdefiniert werden können. Damit bin ich nicht auf Englisch oder Deutsch festgelegt. Das sollte doch jeden zufrieden stellen.
Zahlen und Zeichenketten kann ich in Python mit int und unicode (die einzig wahren Strings) repräsentieren. Auch None, True und False kann ich von Python übernehmen. Wörter und Blöcke repräsentiere ich mit folgenden Python-Klassen:
class Word(object):
def __init__(self, name):
self.name = name
def __unicode__(self):
return self.name
class GetWord(object):
def __init__(self, word):
self.word = word
def __unicode__(self):
return u":%s" % self.word.name
class SetWord(object):
def __init__(self, word):
self.word = word
def __unicode__(self):
return u"%s:" % self.word.name
class Block(object):
def __init__(self, values=None, start=0):
self.values, self.start = values or [], start
def __unicode__(self):
return u"[%s]" % " ".join(unicode(value) for value in self.values[self.start:])
class Paren(Block):
def __unicode__(self):
return u"(%s)" % " ".join(unicode(value) for value in self.values[self.start:])
Mein erstes Beispiel wird so angelegt:
Block([
Word("schreibe"), "Hallo",
SetWord(Word("gruß")), "Hallo Welt",
Word("schreibe"), Word("gruß"),
Word("schreibe"), GetWord(Word("gruß")),
Word("schreibe"), Paren([Word("addiere"), 3, 4]),
Word("schreibe"), Block([Word("addiere"), 3, 4]),
SetWord(Word("a")), 1, Word("wenn"), Word("nicht"), Word("null?"), Word("a"),
Block([Word("schreibe"), Word("a")]),
])
Meine Programme führe ich in einem Kontext aus, der mir sagt, welche Wörter an welche Werte gebunden sind. Dem Kontext übergebe ich das Programm als Block. Ich kann Kontexte schachteln, etwa wenn ich später im Rumpf einer Schleife lokale Variablen haben will. Daher sieht ein Kontext so aus:
class Context(object):
def __init__(self, parent, block):
self.parent, self.block, self.bindings = parent, block, {}
def eval(self):
result = None
while self.block.length():
result = self.eval_next()
return result
def eval_next(self):
first, self.block = self.block.first(), self.block.next()
if isinstance(first, GetWord):
return first.word
if isinstance(first, SetWord):
return self.bind(first.word.name, self.eval_next())
if isinstance(first, Paren):
first = self.eval_block(first)
elif isinstance(first, Word):
first = self.lookup(first.name)
if callable(first):
first = first(self)
return first
def eval_block(self, block):
return Context(self, block).eval()
def bind(self, name, value):
self.bindings[name] = value; return value
def lookup(self, name):
try:
return self.bindings[name]
except KeyError:
if self.parent:
return self.parent.lookup(name)
raise NameError, name
Die Methode eval wertet so lange Ausdrücke des eigenen Blocks aus, wie es welche gibt. Der Wert des letzten Ausdrucks ist der Wert des Blocks und wird zurückgegeben. Ein leerer Block hat somit den Wert None. Die Methode eval_block hilft mir, einen neuen Block in einem neuen Kontext auszuwerten. Die eigentliche Logik steckt in eval_next. Ich hole mir das erste Element des Blocks und speichere gleichzeitig einen neuen Block mit den restlichen Elementen, konsumiere also das erste Element aus dem Block. Nun kommt eine Fallunterscheidung, die man theoretisch auch über Methoden in meinen Klassen eleganter implementieren könnte, doch dann müsste ich auch eigene Klassen für Zahlen, Zeichenketten, usw. haben. Daher habe ich mich für die langsamere aber einfachere Variante entschieden. Haben wir ein GetWord vorliegen, also eines, das nur oder : als Präfix hat, liefert es einfach nur das enthaltene Wort zurück, ohne es auszuwerten. Wozu man dies braucht, sehen wir vielleicht später. Zur Zeit ist die Funktion eigentlich unwichtig und nur der Vollständigkeit halbe vorhanden. Ein SetWord, dem ein ist oder : folgt, erzeugt eine neue Bindung im Kontext. Es hat ein Argument, welches ich durch einen rekursiven Aufruf von eval_next auswerte und dann im Kontext unter dem entsprechenden Namen der ausgewerteten Wert mit bind speichere. Der dritte mögliche Fall ist ein Paren, also ein Block mit runden Klammern. Den werte ich einfach aus, gebe das Ergebnis aber noch nicht zurück. Alternativ haben wir vielleicht ein Wort vorliegen. In diesem Fall suche ich dessen Wert im Kontext mittels lookup. In den beiden letzten Fällen kann ich etwas haben, das eine Python-Funktion ist. Falls ja, rufe ich diese mit dem Kontext als Argument auf. Auf diese Weise werde ich alle Systemoperationen meinem Interpreter beibringen. Alles andere, also Zahlen, Zeichenketten, Wahrheitswerte und auch Block-Exemplare, werte ich nicht aus. Sie stehen für sich selbst.
Ich habe einige neue Methoden von Block benutzt, die ich noch schnell definieren will:
class Block...
def first(self):
return self.values[self.start]
def next(self):
return Block(self.values, self.start + 1)
def length(self):
return max(len(self.values) - self.start, 0)
Wie man sieht, können sich Blöcke die ihnen zugrunde liegende Python-Liste teilen. Die Variable start definiert, wo ein Block glaubt, dass sein erstes Element beginnt. Einen Block mit allen bis auf dem ersten Element kann ich auf diese Weise sehr effizient erzeugen. Ich zähle einfach start eins hoch.
Will ich das folgende Beispiel ausführen, fehlen mir die Wörter schreibe und addiere:
block = Block([Word("schreibe"), Word("addiere"), 3, 4])
Context(None, block).eval()
Es sollten Systemoperationen sein, die ich in einem Kontext namens Builtins binden werde:
Builtins = Context(None, None)
def word(name):
def inner(f):
return Builtins.bind(name, f)
return inner
@word("schreibe")
def print_word(context):
print unicode(context.eval_next())
@word("addiere")
def add_word(context):
return context.eval_next() + context.eval_next()
Builtins.eval_block(block)
Der Interpreter ist fertig!
Um mein erstes Beispiel auszuführen, muss ich noch die folgenden Wörter definieren:
@word("wenn")
def if_word(context):
value, block = context.eval_next(), context.eval_next()
return context.eval_block(block) if value else None
@word("nicht")
def not_word(context):
return not context.eval_next()
@word("null?")
def nullp_word(context):
return context.eval_next() == 0
Im zweiten Beispiel definiere ich eine eigene Funktion. Wie dies geht, möchte ich als nächstes zeigen. Hier ist ein einfacheres Beispiel:
verdopple ist funktion [x] [addiere x x]
schreibe verdopple 6
Das Wort funktion erzeugt ein Function-Exemplar, das ich von Python aus "callable" mache, damit es aus eval_next heraus aufgerufen wird. Systemoperationen und benutzerdefinierte Funktionen funktionieren genau gleich:
class Function(object):
def __init__(self, context, params, body):
self.context, self.params, self.body = context, params, body
def __call__(self, context):
body_context = Context(self.context, self.body)
params = self.params
while params.length():
first, params = params.first(), params.next()
body_context.bind(first.name, context.eval_next())
return body_context.eval()
@word("funktion")
def function_word(context):
return Function(context, context.eval_next(), context.eval_next())
Hinweis: Um eine korrekte lexikografische Bindung zu erreichen, kennt jede Funktion den Kontext zum Zeitpunkt ihrer Definition. Andernfalls würden lokale Funktionen (also Funktionen innerhalb von Funktionen) keinen Zugriff auf die Variablen in ihrem Kontext haben, sondern nur auf Variablen im Kontext zum Zeitpunkt des Aufrufs, was allgemein als falsch gilt. Nur die allerersten Lisp-Systeme hatte diese so genannte dynamische Bindung. Alle neueren Programmiersprachen (auch Python) haben eine statische a.k.a. lexikografische Bindung von Variablen.
Ich erzeuge daher einen neuen Kontext, in dem ich den Rumpf der Funktion ausführen will. In diesem Kontext muss ich dann die Funktionsparameter an die Argumente der Funktion binden. Diese finde ich, in dem ich den dem __call__ übergebenen Kontext benutze.
Testen wir das ganze. Es sollte 12 angezeigt werden:
Builtins.eval_block(Block([
SetWord(Word("verdopple")), Word("funktion"), Block([Word("x")]), Block([
Word("addiere"), Word("x"), Word("x"),
]),
Word("schreibe"), Word("verdopple"), 6,
]))
Nun möchte ich natürlich nicht jedes Mal per Hand ein Programm in meiner Sprache in Python-Ausdrücke umwandeln müssen. Dazu schreibe ich einen Scanner und Parser. Der Scanner benutzt reguläre Ausdrücke, die komplizierter aussehen als sie eigentlich sind, weil ich das ist und nur im Scanner erkennen möchte. Der Parser kümmert sich dann nur noch um Blöcke und erzeugt Block- und Paren-Exemplare. Beides habe ich in der Funktion read zusammengemangelt:
LITERALS = ur'(-?\d+)|"((?:\\"|[^"])*)"'
WORDS = ur'(?::|nur\s+)(\w+[?!]?)|(\w+[?!]?)(?:\s+ist\b|:)|(\w+[?!]?)'
TOKENS = ur'(?u)\s*(?:%s|%s|([()\[\];,]))' % (LITERALS, WORDS)
def read(source):
blocks = [Block()]
def append(value): blocks[-1].values.append(value)
for m in re.finditer(TOKENS, source):
if m.lastindex == 1:
append(int(m.group(1)))
elif m.lastindex == 2:
append(m.group(2))
elif m.lastindex == 3:
append(GetWord(Word(m.group(3))))
elif m.lastindex == 4:
append(SetWord(Word(m.group(4))))
elif m.lastindex == 5:
append(Word(m.group(5)))
else:
syntax = m.group(6)
if syntax == "(":
blocks.append(Paren())
elif syntax == "[":
blocks.append(Block())
elif syntax == ")":
assert len(blocks) > 1, "unexpected )"
b = blocks.pop()
assert isinstance(b, Paren), ") found, but ] expected"
append(b)
elif syntax == "]":
assert len(blocks) > 1, "unexpected ]"
b = blocks.pop()
assert isinstance(b, Block), "] found, but ) expected"
append(b)
assert len(blocks) == 1, "missing ) or ]"
return blocks[0]
Nun kann ich dann auch ein Programm, welches im Quelltext meiner Sprache vorliegt, direkt ausführen. Weil die Namen eval und exec schon von Python belegt sind, wähle ich run für diese Funktion:
def run(source):
return Context(Builtins, read(source)).eval()
run(u"""
verdopple ist funktion [x] [addiere x x]
schreibe verdopple 6
""")
Die Sprache ist fertig. Das Hinzufügen weiterer Befehlswörter ist nun reine Fleißarbeit. Natürlich sind auch weitere Datentypen wie z.B. Hashes denkbar. Vielleicht möchte man auch, dass http://python.org direkt als URL-Objekt erkannt wird, während 24-Jul-2009 als Datumsobjekt weiterverarbeitet werden kann. Oder man kann direkt <h1>Hallo</h1> schreiben und hat ein Elem-Objekt mit dem Namen h1 und dem Kind "Hallo".
Hier sind noch ein paar Befehlswörter für Schleifen:
wiederhole ist funktion [anzahl rumpf] [
wenn nicht null? anzahl [führe_aus rumpf wiederhole subtrahiere anzahl 1 rumpf]
]
Beispiele:
wiederhole 5 [schreibe "Hallo"]
i ist 0
wiederhole 10 [i ist addiere i 1]
schreibe i
solange ist funktion [bedingung rumpf] [
wenn führe_aus bedingung [führe_aus rumpf solange bedingung rumpf]
]
Beispiel:
i ist 0
solange [nicht gleich? i 10] [
schreibe i
i ist addiere i 1
]
für ist funktion [zählername von bis schrittweite rumpf] [
solange [nicht größer? von bis] [
binde zählername von
führe_aus rumpf
von ist addiere von schrittweite
]
]
Beispiele:
für nur i 0 10 2 [schreibe i]
für nur i 3 1 -1 [schreibe i]
für_alle ist funktion [elementname block rumpf] [
solange [nicht leer? block] [
binde elementname erster block
führe_aus rumpf
block ist nächster block
]
]
Beispiel:
für_alle nur element [a b c d] [schreibe element]
Mit dem neuen Wort führe_aus kann ich einen Block auswerten. Mit binde definiere ich eine neue lokale Variable. Das erste Argument wertet dabei zu dem Namen aus, das zweite Argument zu dem Wert.
@define("führe_aus")
def do_word(context):
return context.eval_block(context.eval_next())
@define("binde")
def bind_word(context):
return context.bind(context.eval_next(), context.eval_next())
Lästig ist, dass ich nur i bzw. nur element statt einfach element schreiben muss, denn ich will an dieser Stelle ja nicht ein Wort wie eine Variable betrachten sondern wie einen Namen. Doch es gibt einen Trick, wie ich das Problem lösen kann. Was auch noch nett wäre: Ein in zwischen element und dem Block als syntaktischer Zuckerguss, damit es sich etwas besser liest. Auch dies ist möglich.
Ich nutze aus, dass ich drei verschiedene Varianten von Wörter in Parameterlisten definieren kann. Ist es ein GetWord, so versuche ich nicht, mit eval_next() das Argument auszuwerten, sondern erwartete, dass das Argument ein Wort ist und nehme es direkt. Ein SetWord hingegen ignoriere ich als Syntax. So muss ich dazu Function (und auch nur diese eine Klasse) ändern:
class Function...
def __call__(self, context):
body_context = Context(self.context, self.body)
params = self.params
while params.length():
first, params = params.first(), params.next()
if isinstance(first, GetWord):
value, context.block = context.block.first(), context.block.next()
assert isinstance(value, Word)
body_context.bind(first.word.name, value)
elif isinstance(first, SetWord):
value, context.block = context.block.first(), context.block.next()
assert isinstance(value, Word) and first.word.name == value.name
continue
else:
body_context.bind(first.name, context.eval_next())
return body_context.eval()
Nun kann ich für_alle-Schleifen einfacher aufschreiben:
für_alle ist funktion [:element in: block rumpf] [ ... ]
für_alle element in [a b c] [schreibe element]
Damit es einfacher wird, Systemoperationen zu definieren, schlage ich vor, << ... >> als Syntax für eingebetteten Python-Quelltext zu definieren. Daraus kompiliert der Reader sofort eine Python-Funktion, die dann wie üblich gebunden werden kann.
Builtins = Context(None, load("builtins"))
Datei `builtins`:
wenn ist <<
value, block = context.eval_next(), context.eval_next()
return context.eval_block(block) if value else None
>>
funktion ist <<
return Function(context, context.eval_next(), context.eval_next())
>>
Die 6 Zeilen, die ich dazu in read() ändern musste, findet man im beiliegenden Quelltext.
Stefan