windner, ich würde erwarten, dass ein gutes Lisp/Scheme einen speziell auf die Anforderungen dieser Sprachen (viele kleine kurzlebige Objekte) angepassten Garbage Collector hat und der Python-Interpreter da nicht mithalten kann. Das sollte dich aber nicht bei deinem Projekt stoppen. Ein tiefes Verständnis von Lisp/Scheme ist ein Wert an sich ;)
Ein wichtiger Unterschied zwischen Lisp und Scheme ist, ob es einen oder zwei Namensräume für Funktionsnamen und andere Variablen gibt. Scheme ist ein sogenanntes Lisp-1, wo beide Namensräume zusammenfallen. Das ist einfacher zu implementieren und prinzipiell eleganter, allerdings reduziert es die Menge der zur Verfügung stehenden Variablennamen – kurzum, es gibt auch Fans von Lisp-2.
Du schreibst, du möchtest Cons-Zellen durch Exemplare einer Cons-Klasse in Python repräsentieren und NIL mit Pythons None. Wenn du CommonLisp nachbauen willst, muss (CAR NIL) == NIL gelten, daher bietet sich an, NIL als eine spezielle Cons-Zelle zu realisieren, deren CAR und CDR auf sich selbst zeigen. Dummerweise muss NIL auch ein gültiges Symbol sein, etwas, das du ansonsten mit Python-Strings realisieren könntest. Dennoch, ein if-Test in CAR und CDR ist teuer als der Sonderfall in SYMBOLP.
Ich schlage dennoch Scheme als sauberer entworfene Sprache als Vorbild vor. Dort ist NIL IIRC ein eigener Typ und kommt ausschließlich als Markierung für eine proper list (einer Kette von Cons-Zellen, deren CDR entweder wieder eine Cons-Zelle ist oder NIL, aber nichts anderes) vor.
Du hast nach einer Eval-Funktion gefragt. Aus dem Kopf kann ich dir folgendes bieten:
Code: Alles auswählen
;; werte Ausdruck "e" in Umgebung "r" aus
(define (evl e r)
(if (pair? e)
((evl (car e) r) (cdr e) r)
(lookup e r)))
Ist "e" eine Liste, werte erstes Element (rekursiv) aus, welches eine Scheme-Funktion sein muss, die dann mit dem Rest der Liste aufgerufen wird. Andernfalls ist "e" ein Symbol (den Fall, dass es eine Zahl oder so sein könnte berücksichtige ich nicht, da mein Scheme nur Listen und Symbole kennt) und in Umgebung "r" wird nach dem an das Symbol gebundenen Wert gesucht.
Code: Alles auswählen
;; Suche an "n" gebundenen Wert in Umgebung "r"
(define (lookup n r)
(if (pair? r)
(if (eq? n (caar r)) (cdar r) (lookup n (cdr r)))
(error "unbound variable")))
Die Umgebung ist eine Liste von Paaren, in der ich rekursiv für jedes Paar prüfe, ob der CAR meinem Symbol entspricht. Dann ist dessen CDR der gesuchte Wert. Erreiche ich das Ende der Liste, ist "n" nicht gebunden.
Der Trick bei "evl" ist, dass ich Funktionsargumente nicht sofort auswerte, sondern auf diese Weise special forms wie normale Funktionen behandle, sodass diese nicht weiter speziell sind. Dazu gleich mehr. Doch erstmal einige Hilfsfunktionen:
Code: Alles auswählen
;; werte Liste "l" mit Ausdrücken in "r" aus und liefere neue Liste
(define (evll l r)
(if (pair? l)
(cons (evl (car l) r)
(evll (cdr l) r))))
;; werte Sequenz "l" in "r" aus, ist "l" leer, ist das Ergebnis "v"
(define (evlsq v l r)
(if (pair? l) (evlsq (evl (car l) r) (cdr l) r) v))
;; erweitere Umgebung "r" um Liste von Paaren aus Namen "n" und Werten "v"
(define (bind n v r)
(if (pair? n)
(cons (cons (car n) (if (pair? v) (car v) nil))
(bind (cdr n) (if (pair? v) (cdr v) nil) r))
r))
Eine special form ist etwas, das wie ein Funktionsaufruf aussieht, sich aber anders verhält, da es nicht alle Argumente auswertet. QUOTE ist die wohl einfachste special form, LAMBDA die wichtigste.
Code: Alles auswählen
;; liefere das erste Argument ohne es auszuwerten
(define (!quote e r)
(car e))
;; liefere eine lexikografisch gebundene anonyme Funktion
(define (!lambda e r)
(lambda (e1 r1)
(evlsq nil (cdr e) (bind (car e) (evll e1 r1) r))))
Normale eingebaute Funktionen müssen wie folgt definiert werden:
Code: Alles auswählen
(define (!cons e r) (apply cons (evll e r)))
(define (!car e r) (apply car (evll e r)))
(define (!cdr e r) (apply cdr (evll e r)))
In meiner Definition von Scheme in Scheme benutze ich absichtlich nur define, lambda, cons, car, cdr, pair?, eq? und apply. Damit sollte der Interpreter recht einfach zu bootstrappen sein. Das lambda-Kalkül sagt ja, dass man eigentlich nur LAMBDA (und dessen Anwendung) benötigt.
Das IF diskutiere ich wie folgt weg: Man fasse (if cond then else) als Makro auf (welches man normal in Scheme definieren könnte), und expandiere es in (cond (lambda () then) (lambda () else)).
Nun reicht der folgende Code:
Die Funktionen pair? und eq? müssen jetzt !true oder !false liefern.
Code: Alles auswählen
(define (!pair? e r) (if (apply pair? (evll e r)) !true !false))
(define (!eq? e r) (if (apply eq? (evll e r)) !true !false))
Ein (cons e1 e2) könnte man übrigens auch mit lambda ausdrücken, denn es definiert sich ja dadurch, dass (car (cons e1 e2)) == e1 und (cdr (cons e1 e2)) == e2 und (pair? (cons e1 e2)) == !true gilt. Dies überlasse ich dem Leser ;)
Ich merke gerade, dass DEFINE nicht in meinem Interpreter funktionieren wird, da es eine globale Umgebung verändern muss, ein Konzept, dass ich nicht habe. Dazu bräuchte man entweder eine globale, veränderliche Variable (igit) oder muss aus den Funktionen, die die special forms implementieren, eine neue Umgebung herausreichen. Dann hätte man aber auch gleich continuations... nun ganz so einfach ist das alles also doch nicht.
Code: Alles auswählen
(define *toplevel* (cons (cons (quote quote) !quote)
(cons (cons (quote lambda) !lambda)
(cons (cons (quote cons) !cons)
(cons (cons (quote car) !car)
...)...))
In Python könnte mein Interpreter vielleicht so aussehen:
Code: Alles auswählen
# cons cells
def cons(e1, e2): return [e1, e2]
def car(e): return e[0]
def cdr(e): return e[1]
def is_pair(e): return isinstance(e, list) and len(e) == 2
# the usual helpers
def caar(e): return car(car(e))
def cdar(e): return cdr(car(e))
def cadr(e): return car(cdr(e))
def cddr(e): return cdr(cdr(e))
def evl(e, r):
if is_pair(e):
return evl(car(e), r)(cdr(e), r)
return lookup(e, r)
def lookup(n, r):
if is_pair(r):
if n == caar(r): return cdar(r)
return lookup(n, cdr(r))
raise "unbound variable" + n
def evll(l, r):
if is_pair(l): return cons(evl(car(l), r), evll(cdr(l), r))
def evlsq(v, l, r):
if is_pair(l): return evlsq(evl(car(l), r), cdr(l), r)
return v
def bind(n, v, r):
def carV(e): return car(e) if is_pair(e) else None
def cdrV(e): return cdr(e) if is_pair(e) else None
if is_pair(n):
return cons(cons(car(n), carV(v)), bind(cdr(n), cdrV(v), r))
return r
# special forms
def _quote(e, r):
return car(e)
def _lambda(e, r):
return lambda e1, r1: evlsq(None, cdr(e), bind(car(e), evll(e1, r1), r))
def _if(e, r):
return evl(cadr(e) if evl(car(e), r) else car(cddr(e)), r)
# builtin functions
def _eq(e, r): ee = evll(e, r); return car(ee) == cadr(ee)
# initial env
def lst(*args):
if args: return cons(args[0], lst(*args[1:]))
def to_lst(v):
l = []
while is_pair(v): l.append(car(v)); v = cdr(v)
return l
def builtin(f): return lambda e, r: f(*to_lst(evll(e, r)))
env = lst(
cons('nil', None),
cons('#t', True),
cons('#f', False),
cons('quote', _quote),
cons('lambda', _lambda),
cons('if', _if),
cons('cons', builtin(cons)),
cons('car', builtin(car)),
cons('cdr', builtin(cdr)),
cons('pair?', builtin(is_pair)),
cons('eq?', builtin(lambda e1, e2: e1 == e2)),
cons('apply', builtin(lambda f, a: f(*a))),
)
def read(str):
import re
def _scan():
for t in re.findall(r'\s*([().]|[^ .()]*)', str):
yield t
s = _scan()
def _read(t):
if t == "": return None
if t == "(": return _readl(s.next())
if t == ")" or t == ".": raise SyntaxError
return t
def _readl(t):
if t == ")": return None
if t == "" or t == ".": raise SyntaxError
v = _read(t)
t = s.next()
if t == ".":
v = cons(v, _read(s.next()))
if s.next() != ")": raise SyntaxError
return v
return cons(v, _readl(t))
return _read(s.next())
print evl(read("(pair? (cons (quote a) nil))"), env)
PS: Es spricht IMHO für Scheme, dass der Interpreter in unter 100 Zeilen machbar ist, nicht so sehr für Python ;) Endrekursion erkennen kann ich übrigens nicht, der Scheme-Interpreter in Scheme würde es natürlich selbst können, doch meine Python-Version versagt. Der Weg, den ich hier kenne ist, auf einen continuation-basierten Interpreter umzustellen - das erschlägt dann nämlich dieses Konzept gleich mit. Ist aber schwerer verständlich und noch langsamer...
Stefan
