Selbstgebauter Lisp/Scheme-Interpreter (Proof of Concept)

Du hast eine Idee für ein Projekt?
Antworten
windner
User
Beiträge: 76
Registriert: Freitag 19. Oktober 2007, 11:25

Sonntag 25. November 2007, 21:09

Hallo an die Runde!

Ich habe vor kurzem in einem Thread den Vorschlag gelesen, einen Lisp-Interpreter in Python zu implementieren. Dazu möchte ich ein paar konzeptionelle Fragen an die Runde stellen (für das Projekt-Forum finde ich das zu wenig konkret).

Wenn ihr euch mit konkreten Problemen befassen wollt, lest bitte nicht weiter. So weit bin ich noch nicht.

Ich habe ein wenig darüber nachgedacht, und bin zu dem Schluss gekommen, dass das vergleichsweise einfach sein sollte, weil:

1.) Lisp eine garbage collection verwendet. Die hat Python schon eingebaut.
2.) Lisp ein Typ-System verwendet. Auch bei Python dabei.
3.) Man folglich nur wenige Lisp-Funktionen bereitstellen muss (zB. cons, car, cdr, defun), der restliche Aufwand sollte sich auf das Parsen von S-Expressions beschränken.

Meine Idee ist nicht, Lisp-Listen auf Python-Listen abzubilden, sondern eigene Cons-Objekte zu haben (ich glaube, in Scheme heißt das "pair" statt "cons"):

Code: Alles auswählen

class Cons(object):
    def __init__(self, car, cdr):
        self.car = car
        self.cdr = cdr
car und cdr zeigen dann entweder wieder auf ein Cons-Objekt oder auf ein anderes Objekt. Als Indikator für NIL könnte man None verwenden, weil es ebenfalls ein Singleton ist.

Was ich mir davon erwarte:
Solange ich eine Referenz auf ein Cons-Objekt habe, habe ich eine brauchbare Referenz auch eine Lisp-Listenstruktur und die Objekte, auf die diese zeigt. Wenn ich die Referenz fallen lasse, verschwinden rekursiv auch die Referenzen auf die nachfolgenden Cons- und anderen Objekte. So sollte ich eine fertige garbage collection haben.

Glaubt ihr, dass das funktionieren könnte? Mit brauchbarer Performance?
Benutzeravatar
birkenfeld
Python-Forum Veteran
Beiträge: 1603
Registriert: Montag 20. März 2006, 15:29
Wohnort: Die aufstrebende Universitätsstadt bei München

Sonntag 25. November 2007, 22:04

Hier haben wir endlich mal ein Einsatzgebiet für `__slots__`: mit einem ``__slots__ = ["car", "cdr"]`` solltest du den benötigten Speicherplatz für Cons-Objekte reduzieren können.
Dann lieber noch Vim 7 als Windows 7.

http://pythonic.pocoo.org/
BlackJack

Montag 26. November 2007, 09:05

Eine Hürde die man auf jeden Fall nehmen muss, ist dass erkennen und beseitigen/umformen von Endrekursion. Sonst ist bei Python mit dem Rekursions-Limit recht schnell Schluss.
Costi
User
Beiträge: 544
Registriert: Donnerstag 17. August 2006, 14:21

Montag 26. November 2007, 12:48

ich hatte so eine aenliche idee auch schon mal:
http://www.python-forum.de/topic-10958.html

wobei ich pythons builtin listen genommen habe (sollte viel schneller sein)

spaeter habe ich das ganze nochmal uebersichtlicher und bug-freier implementiert und dabei die syntax so definiert, dass bloecke wie in python durch einrueckung statt augentoetende klammern definiert werden kann
(mal sehen ob ichs noch finde....)


ps:
juhhuuuu deutsch klausur 2 punkte und gerade eben PW verckackt!
cp != mv
windner
User
Beiträge: 76
Registriert: Freitag 19. Oktober 2007, 11:25

Montag 26. November 2007, 13:18

wobei ich pythons builtin listen genommen habe (sollte viel schneller sein)
Und wie hast du sowas gemacht?

Code: Alles auswählen

(1 2 3 . 4)
Edit:
Ich will ja nicht einfach Python eine andere Syntax verpassen, sondern richtige Lisp-artige Bäume haben, sodass man Lisp-Funktionen wie cons und rest udgl. transparent implementieren und eben Sachen wie dotted lists machen kann.
Costi
User
Beiträge: 544
Registriert: Donnerstag 17. August 2006, 14:21

Montag 26. November 2007, 15:10

hmmm,
dan mach das lieber mit dem knoten.
moeglicherweise kann man aber -wenn du lisp 1:1 uebernehmen willst- dotted lists und so ueber pythons listen emulieren.
oder du lagerst den kritischen teil deiner implementierung in C oder D um
cp != mv
windner
User
Beiträge: 76
Registriert: Freitag 19. Oktober 2007, 11:25

Montag 26. November 2007, 15:26

windner hat geschrieben:Und wie hast du sowas gemacht?

Code: Alles auswählen

(1 2 3 . 4)
Scheinbar gar nicht. Damit geht ja der Reiz verloren. Aber ich verstehe fremden unkommentierten Code meistens falsch.

@birkenfeld:
Das schreit wirklich geradezu nach __slots__.

@BlackJack:
Wenn ich nur soweit wäre!

@mods:
Bitte verschieben nach Ideen.

Das ganze funktioniert tatsächlich. Ich konnte eine read() und eine write() Funktion bauen:

Code: Alles auswählen

>>> # mein S-Expression-Parser
... import stoken
>>> # S-Expression einlesen, gibt ein Cons-object zurück
... c = stoken.read('( 1 2 () (3 4 ) 5 . 6)')
>>> c
<Cons at 0x9c85d0. car: 1, cdr: Cons at 0x9c85b0>
>>> # Schreiben
... stoken.write(c)
(1 2 () (3 4) 5 . 6)
>>> # Was Cons-objekte bis jetzt können:
... len(c)
5
>>> for cons_obj in c:
...   print cons_obj
...
<Cons at 0x9c85d0. car: 1, cdr: Cons at 0x9c85b0>
<Cons at 0x9c85b0. car: 2, cdr: Cons at 0x9c8570>
<Cons at 0x9c8570. car: None, cdr: Cons at 0x9c8550>
<Cons at 0x9c8550. car: Cons at 0x9c8530, cdr: Cons at 0x9c84d0>
<Cons at 0x9c84d0. car: 5, cdr: 6>
Vielleicht findet sich ja ein Lisp-Hacker, der mir hilft, die eval()-Funktion zu bauen.

Code:
http://paste.pocoo.org/show/12572/
http://paste.pocoo.org/show/12574/
Costi
User
Beiträge: 544
Registriert: Donnerstag 17. August 2006, 14:21

Montag 26. November 2007, 16:23

ups, mein letzter beitrag war etwas missverstaendlich

egal:
vieliecht kannst du dich an meiner methode inspirieren:
alles wird zu dem schema

Code: Alles auswählen

[[<vars.get>, '='], 'str', [[<vars.get>, 'raw_input'], 'string_eingeben:']] 
geparst. evaluation findet also folgendermassen statt:

Code: Alles auswählen

def do(code):
    debug("(do     arg: ", repr(code))    
    if type(code) == list:
        
        def_ = do(code[0])
        args = code[1:]
        
        global_.do_level += 1
        retval = def_(*args)
        global_.do_level -= 1
        
    else:
        retval = code
    debug(") returning:", repr(retval))   
    return retval
edit:
waere

Code: Alles auswählen

    if type(code) is list:
besser?
cp != mv
windner
User
Beiträge: 76
Registriert: Freitag 19. Oktober 2007, 11:25

Mittwoch 28. November 2007, 21:36

Ich denke am besten wäre:

Code: Alles auswählen

if isinstance(code, list)
Zumindest macht das BlackJack immer so, und der scheint zu wissen, was er sagt.

Was meinen Interpreter angeht: das ganze driftet langsam in den akademischen Bereich ab, weil's auch praktisch funtioniert. Ich wollte ja eigentlich wissen, warum Lisp für die AI so wichtig war (ist?). Jetzt weiss ich's.

Der Interpreter ist fertig (Alpha-Stadium). Ich suche dringender denn je Mitstreiter, entweder zum Testen oder zum Optimieren. Ich konnte folgendes evaluieren:

Code: Alles auswählen

(defun len2 (l)
    (if (rest l)
        (+ 1 (len2 (rest l)))
        1))

(len2 (list 1 2 3 4 . 5))
; ergibt 4 (Juhuu!)
Es spricht für Python, dass man in weniger als 400 Zeilen einen Lisp-Interpreter bauen kann, der solche Ausdrücke auswertet. Jetzt komme ich zu den richtig interessanten Themen, zB der Endrekursions-Erkennung.

Der Code ist mittlerweile zu lang/wertvoll für mich, um ihn einfach im Internet zu posten, aber ich gebe ihn gerne weiter, wenn die Hoffnung besteht, ihn zu verbessern. Bei Interesse bitte per PM melden oder hier posten.

Edit:
Das Ziel ist nicht weniger, als die Aufnahme in die Standard-Bibliothek von Python. :D
Zumindest die Funktionen, die proper lists in Python-Listen übersetzen, würden dort wirklich hineinpassen.
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Sonntag 2. Dezember 2007, 13:33

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:

Code: Alles auswählen

(define (!true t e) (t))
(define (!false t e) (e))
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
Zuletzt geändert von sma am Samstag 26. Juni 2010, 09:20, insgesamt 1-mal geändert.
windner
User
Beiträge: 76
Registriert: Freitag 19. Oktober 2007, 11:25

Freitag 14. Dezember 2007, 04:24

Wow! Da habe ich einiges zu verdauen.

Scheme ist in der Tat sehr schön, schöner als Common Lisp. Werde mich nach einem Scheme-Compilterpreter umschauen.

Ich hatte mich, ohne es zu wissen, sehr an Scheme angelehnt, weil ich ein Lisp-1 gebaut habe (schien auch mir eleganter). Daraus folgt auch, dass setq und defun zusammenfallen können (define). Mein (defun spam (eggs) eggs) war ohnehin nur ein makro-artiges synonym für (setq spam (lambda (eggs) eggs)).

Momentan bin ich, wenn mir Zeit bleibt, mit defmacro beschäftigt, wo ich mich in den (quotes) verliere.
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 ;)
Darüber hab' ich eine Weile nachgedacht. Ich schaff' es nicht.
Im Fall (cons) Höchstens durch Rückführung auf (list):

Code: Alles auswählen

(defun cons (e1 e2)
   ((lambda (ee1 ee2) (list ee1 ee2)) e1 e2)
Ich werde ein paar Tage brauchen, um das alles zu verstehen, ich melde mich dann wieder.

Danke!
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Samstag 15. Dezember 2007, 10:45

Du fragtest, wie car, cdr und cons aussehen müssen, damit (car (cons x y)) == x und (cdr (cons x y)) == y gelten. Zum Beispiel so:

Code: Alles auswählen

(define (cons e1 e2)
  (lambda (f) (f e1 e2)))

(define (car e)
  (e (lambda (e1 e2) e1)))

(define (cdr e)
  (e (lambda (e1 e2) e2)))
Stefan
windner
User
Beiträge: 76
Registriert: Freitag 19. Oktober 2007, 11:25

Montag 24. Dezember 2007, 01:03

Danke! Aber ich hätt's auch selbst aus Wikipedia kopieren können. :wink:

Wenn ich Cons-Zellen über Funktionen abbilden wollte, hätte ich btw nicht mit Cons-Objekten angefanden...
Antworten