Ein Python-Interpreter mit Continuations

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Samstag 19. Januar 2008, 19:08

Verrückte Idee? Oder machbar?

Ich würde gerne ein paar Experimente mit einem modalen Webrahmenwerk wie Seaside machen - jedoch in Python. Seaside benutzt Continuations, die es nur bei Stackless oder PyPy gibt.

Nun habe ich mir aber in den Kopf gesetzt (und darum schreibe ich auch in "Allgemein"), es mit dem normalen Python-Interpreter zu schaffen. Hat das schon mal wer versucht?

Ich brauche `callcc`. Warum? Siehe Anhang. Um `callcc` zu implementieren, dachte ich daran, einfach Python in Python zu interpretieren. Einfach? Nun, ja. Der Python Bytecode steht mir offen. Die meisten Interna (Code, Frame) ebenfalls. Ein solcher Interpreter hat einen Zustand. Dieser Zustand entspricht der Continuation. Schaffe ich es, den Interpreter derart zu schreiben, dass ich diesen Zustand kopieren und z.B. pickeln kann, habe ich wiederverwendbare Continuations geschaffen. Klingt doch einfach, oder?

Systemfunktionen aus bestimmten Moduln könnten mir natürlich in die Quere kommen... aber ohne Herausforderungen wäre das Leben doch langweilig. Hat jemand Lust, mitzumachen?

Hier ist ein Anfang.

Diese Funktion

Code: Alles auswählen

def a(x, y):
    return x + y
hat ein Code-Objekt, das die folgenden Bytecode enthält:

Code: Alles auswählen

LOAD_FAST x
LOAD_FAST y
BINARY_ADD
RETURN_VALUE
Hey, das kann ich interpretieren. Achtung! Ich habe nicht nachgeschaut, wie CPython wirklich funktioniert, sondern nur geschlussfolgert und geraten, was wohl die Aufgabe der verschiedenen Variablen ist und flux mein eigenes Frame-Objekte gebaut:

Code: Alles auswählen

class Frame(object):
    def __init__(self, frame, code, f_locals):
        self.f_back = frame
        self.f_code = code
        self.f_locals = f_locals
        self.f_lasti = 0
        self.f_stack = [] # maximum is code.co_stacksize

    def nexti(self):
        """Return the next bytecode instruction."""
        i = ord(self.f_code.co_code[self.f_lasti])
        self.f_lasti += 1
        return i
        
    def nexta(self):
        """Return the next bytecode argument."""
        lo = self.nexti()
        hi = self.nexti()
        return hi * 256 + lo
        
    def push(self, value):
        """Push `value` as new TOS."""
        self.f_stack.append(value)
        
    def pop(self):
        """Return TOS."""
        return self.f_stack.pop()
        
    def step(self):
        """Execute the next instruction and return what to step next."""
        return opcodes[self.nexti()](self)
    
    def LOAD_FAST(self):
        "Push local variable onto stack."
        self.push(self.f_locals[self.nexta()])
        return self

    def BINARY_ADD(self):
        "Implement TOS = TOS1 + TOS."
        b = self.pop()
        a = self.pop()
        self.push(a + b) # todo search for __add__ and __radd__ etc.
        return self
        
    def RETURN_VALUE(self):
        "Return the TOS to the caller of the current function."
        self.f_back.push(self.pop())
        return self.f_back
    
opcodes[opmap['LOAD_FAST']] = Frame.LOAD_FAST
opcodes[opmap['BINARY_ADD']] = Frame.BINARY_ADD
opcodes[opmap['RETURN_VALUE']] = Frame.RETURN_VALUE

class Initial(object):
    f_back = None
    
    def push(self, value):
        self.result = value
        
    def pop(self):
        return self.result

def f_locals(func, args, kw):
    code = func.func_code
    f_locals = [None] * code.co_nlocals
    f_locals[:len(args)] = args
    return f_locals

def interpret(func, args):
    """Take a function, step thru, return result."""
    frame = Frame(Initial(), func.func_code, f_locals(func, args))
    while frame.f_back:
        frame = frame.step()
    return frame.pop()
Nun habe ich alles zusammen und kann den seit Smalltalk legendären ersten Ausdruck eines Interpreters ausführen:

Code: Alles auswählen

print interpret(a, [3, 4]))
Edit: `CALL_FUNCTION` ist deutlich komplexer als ich ursprünglich dachte. Ich habe diesen Abschnitt gegenüber der ursprünglichen Fassung korrigiert.

Alles was `callable` ist, wird durch `CALL_FUNCTION` aufgerufen. Normale Argumente und Schlüsselwortargumente stehen zusammen mit dem Funktionsobjekt auf dem Stack. Aus diesen Informationen muss für den neuen Frame die `f_locals`-Liste zusammengeschraubt werden. Eingebaute Funktionen will ich dabei nicht interpretieren, sondern direkt aufrufen.

Code: Alles auswählen

class Frame...
    def CALL_FUNCTION(self):
        "Call a callable."
        argsc = self.nexti()
        kwc = self.nexti()
        
        kw = {}
        while kwc > 0:
            v = self.pop()
            n = self.pop()
            kw[n] = v
            kwc -= 1
        
        args = []
        while argsc > 0:
            args.append(self.pop())
            argsc -= 1
            
        func = self.pop()
        
        if isinstance(func, _BuiltinTypes):
            a.reverse()
            self.push(func(*a, **kw))
            return self
            
        # more special cases...
            
        a.reverse()
        return Frame(self, func.func_code, f_locals(func, args)) # todo add kw
        
_BuiltinTypes = ( # todo are there more strange types?
    type(object.__new__),    # bultin function/method
    type(object.__init__),   # wrapper descriptor
    type(object.__call__),   # wrapper method
    type(object.__reduce__), # method descriptor
)
Damit lässt sich jetzt folgendes erfolgreich auswerten:

Code: Alles auswählen

def a(x): return x + 1
def b(f): return 3 + f(3)
print interpret(b, [a])
Edit: Mein Denkansatz für Continuations war zu kompliziert. Ich habe diesen Abschnitt gegenüber der ursprünglichen Fassung korrigiert.

Eine Continuation ist der Zustand des aktuellen Frame inklusive aller daran hängenden. Genau so habe ich den Interpreter entworfen. Der jetzige Interpreter ändert allerdings Frames. Das ist nicht gut. Entweder erzeuge ich jedes Mal einen neuen Frame (klassisch funktionaler Ansatz), wenn ich den `f_stack` oder `f_lasti` ändere, oder aber ich spalte beim Erzeugen der Continuation eine Kopie aller Frames ab. Bei sehr tiefen Strukturen kopiere ich möglicherweise viel zu viel. Dennoch ist das leichter in mein jetziges Design einzubauen.

Code: Alles auswählen

def copy_frame(frame):
    """Copy a hierachry of frames upto not including the initial frame."""
    if frame and frame.f_back:
        f = Frame(copy_frame(frame.f_back), frame.f_code, frame.f_locals)
        f.f_lasti = frame.f_lasti
        f.f_stack = list(frame.f_stack)
        return f
    return frame

class Continuation(object):
    def __init__(self, frame):
        """Store a copy of the current frame (a.k.a. continuation)."""
        self.frame = frame
    
    def __call__(self, value=None):
        """Replace the current frame with the stored copy, returning `value`."""

def callcc(func):
    return func(Continuation())
Die obige Implementierung funktioniert nur mit Hilfe meines Interpreters. Wie man sieht, ist `Continuation.__call__` nicht implementiert. Soll eine neue Continuation erzeugt werden - d.h. mein Interpreter interpretiert z.B. `callcc`, schiebe ich explizit ein neues Continuation-Objekt mit einer Kopie des richtigen Frames auf den Stack des Interpreter - interpretiere aber nicht die Instantiierung selbst. Soll ein Continuation-Objekt aufgerufen werden, fange ich dies ebenfalls ab beende `CALL_FUNCTION` mit der Kopie des ursprünglichen kopierten Frames. Dies setzt die Ausführung an der alten Stelle fort. Da ich erneut kopiere - auch mehrfach.

Code: Alles auswählen

class Frame...
    def CALL_FUNCTION...
        ...
        # more special cases...
        if isinstance(func, type):
            if func is Continuation:
                self.push(Continuation(copy_frame(self.f_back)))
                return self
            ...
        elif type(func) is Continuation:
            frame = copy_frame(func.frame)
            frame.push(args[0] if len(args) else None)
            return frame
        ...
Funktionieren sollten jetzt das folgende Beispiel aus der Wikipedia:

Code: Alles auswählen

cont = None

def set_cont(k):
    global cont
    cont = k

def test():
    i = 0
    callcc(set_cont)
    i = i + 1
    return i

print test() # 1
print cont() # 2
print cont() # 3
orig = cont
print test() # 1
print cont() # 2
print orig() # 4
Ich muss dazu noch LOAD_GLOBAL, STORE_GLOBAL, LOAD_CONST, STORE_FAST, POP_TOP sowie PRINT_ITEM und PRINT_NEWLINE implementieren. Das ist aber machbar :)

Code: Alles auswählen

class Frame...
    def LOAD_GLOBAL(self):
        "Push value of global variable onto stack."
        self.push(self.f_globals[self.f_code.co_names[self.nexta()]])
        return self
    
    def STORE_GLOBAL(self):
        "Store TOS in global variable."
        self.f_globals[self.f_code.co_names[self.nexta()]] = self.pop()
        return self
    
    def LOAD_CONST(self):
        "Push a constant onto the stack."
        self.push(self.f_code.co_consts[self.nexta()])
        return self
    
    def STORE_FAST(self):
        "Store TOS in local variale."
        self.f_locals[self.nexta()] = self.pop() 
        return self
    
    def POP_TOP(self):
        "Remove TOS."
        self.f_stack.pop()
        return self
        
    def PRINT_ITEM(self):
        print self.pop(),
        return self
        
    def PRINT_NEWLINE:
        print
        return self
Was habe ich erreicht? Ich kann prinzipiell mehrfach ausführbare Continuations mit normalem Python-Code mischen, wenn ich denn den Preis dafür bezahle, dass mein Interpreter bestimmt 1-2 Größenordnungen langsamer ist als der echte Interpreter.

Um dieses in einem Web-Rahmenwerk einzusetzen, muss ich in der Lage sein, den gesamten Code des Webrahmenwerks zu interpretieren. Dazu muss ich eine große Menge fehlender Bytecodes implementieren, was aber in den meisten Fälle reine Fleißarbeit ist. Ein prinzipieller Schwachpunkt ist zur Zeit, dass ich in die "under-under"-Methoden nicht absteige (siehe `BINARY_ADD`), was eigentlich notwendig wäre. Ich berücksichtige auch keine Schlüsselwortargumente. Schleifen sowie `break` und `continue` könnten ebenfalls ein Problem sein, Exceptions und `yield` sind es definitiv.

Stefan


ANHANG:

Ich möchte Continuations an diesem klassischen Beispiel motivieren:

Code: Alles auswählen

def webapp():
    webprint("Ergebnis", webread("1. Zahl") + webread("2. Zahl"))
Dies soll drei Webseiten darstellen: Die erste Seite fragt mit Hilfe eines Formulars nach dem ersten Summanden. Wurde das Formular abgeschickt, fragt die zweite Seite auf gleiche Weise nach dem zweiten Summanden. Die dritte Seite zeigt die Summe an.

Der klassische Ansatz ist, die oben gezeigte geschlossene Form in drei Funktionen aufzuteilen, und jedes Mal zu wissen, wie es weitergeht. Etwa so:

Code: Alles auswählen

def dispatch(request):
    if request.url == '1':
        return """<form action='2'>2. Zahl:
                   <input type='text' name='z1'>
                   <input type='submit'>
                  </form>"""
    if request.url == '2':
        z1 = int(request.param['z1'])
        return """<form action='3'>1. Zahl:
                   <input type='hidden' name='z1' value='%i'>
                   <input type='text' name='z2'>
                   <input type='submit'>
                  </form>""" % z1
    if request.url == '3':
        z1 = int(request.param['z1'])
        z2 = int(request.param['z2'])
        return "<p>Ergebnis: %i</p>" % (z1 + z2)
Bei den ersten beiden Seiten wird durch die URL definiert, was als nächstes passiert. Bei der zweiten Seite sieht man, wie der gesamte Zustand des Programms mitgeführt wird. Dies zusammen ist eine Continuation.

Dies explizit zu machen, ist aber umständlich und fehleranfällig.

Postulieren wir daher, dass es eine Funktion `callcc(f)` gibt, der man eine Funktion übergibt, die dann sofort von `callcc` aufgerufen wird und dabei ein spezielles callable übergeben bekommt, welches für den Rest des Programms steht, der nach `callcc` folgt. Dieses callable hat wiederum einen Parameter, der zum Ergebnis von `callcc` wird.

Am Beispiel wird's hoffentlich verständlich. `k1` ist der Rest des Programms, bezogen auf `webread("1. Zahl")` und `k2` der Rest, bezogen auf das zweite `webread`:

Code: Alles auswählen

def k1(x):
    webprint("Ergebnis", x + webread("2. Zahl"))
    
def k2(x):
    webprint("Ergebnis", k + x) # k is a constant
Ich kann jetzt `webread` derart implementieren, dass die Funktion zwischen zwei Anfragen pausiert. Beachte: Im Gegensatz zu threads oder coroutinen kann ich mehrfach durch diese Continuation laufen - damit funktioniert automatisch der Back-Button! Ich erhalte den klassischen Dispatch, ohne ihn explizit programmieren zu müssen.

Code: Alles auswählen

def dispatch(request):
    if request.url == "1":
        return webapp()
    # search old continuation based on request URL
    # resume it, passing the request
    # return here, if exit() is called
    def f(k):
        exit = k # threadlocal
        continuations[request.url](request)
    return callcc(f)

def webprint(message, result):
    return "<p>%s: %i</p>" % (message, result)

def webread(prompt):
    def html(k):
        """<form action='%s'>
             %s: <input name='z'><input type='submit'>
           </form>""" % (k, prompt)
    request = show(html)
    return int(request.param['z'])

def show(html):
    def f(k):
        # register continuation "k" with a "random" URL
        url = str(len(continuations) + 2)
        continuations[url] = k
        # exit from dispatch() returning the HTML
        exit(html(url))
    return callcc(f) # continue here if registered URL is requested
Ich hoffe, das funktioniert so - ich kann es ja noch nicht ausprobieren :)
Zuletzt geändert von sma am Samstag 26. Januar 2008, 12:13, insgesamt 1-mal geändert.
mitsuhiko
User
Beiträge: 1790
Registriert: Donnerstag 28. Oktober 2004, 16:33
Wohnort: Graz, Steiermark - Österreich
Kontaktdaten:

Samstag 19. Januar 2008, 20:50

Und was genau kannst du mit greenlets nicht tun, was du mit callcc machen kannst? Bzw kannst du dein Problem warscheinlich auch mit Generatoren lösen.
TUFKAB – the user formerly known as blackbird
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Samstag 26. Januar 2008, 12:22

mitsuhiko hat geschrieben:Und was genau kannst du mit greenlets nicht tun, was du mit callcc machen kannst? Bzw kannst du dein Problem warscheinlich auch mit Generatoren lösen.
Ich glaube, wir hatten diese Diskussion schon mal hier im Forum. Continuations können im Gegensatz zu Generatoren mehrfach durchlaufen werden. Man damit in die Vergangenheit eines Programms gehen, und es von einem beliebigen Punkt aus nochmals ausführen. Das ist praktisch, wenn man in einer Webanwendung mit dem Back-Button umgehen will.

Das konkrete Beispiel aus der Wikipedia kann man sinngemäß natürlich auch mit Generatoren erstellen, es war wahrscheinlich schlecht gewählt.

Ich habe jetzt zumindest meine ursprünglichen theoretischen Überlegungen implementiert und gedenke, als nächsten Schritt man mein Web-Beispiel aus dem Anhang zu simulieren. Dort müsste man eigentlich besser sehen, wie zu jedem Request jeweils eine Continuation aufgehoben wird, die dann später nochmals ausgeführt werden kann.

Stefan

PS: Ich glaube, mit dem Artikel bin ich über der Grenze, was in diesem Forum eine vertretbare Länge ist, da das Landen und Ändern immer sehen blieb ;)
mitsuhiko
User
Beiträge: 1790
Registriert: Donnerstag 28. Oktober 2004, 16:33
Wohnort: Graz, Steiermark - Österreich
Kontaktdaten:

Sonntag 27. Januar 2008, 12:03

Hast du dir Generatoren und Greenlets überhaupt mal angesehen? Nur weil ein Generator nureinmal ausgeführt werden kann wird dein Problem nicht unlösbar. Und ich hab Greenlets erwähnt, die funktionieren im Gegensatz zu einem selbstgebastelten Python Interpreter.
TUFKAB – the user formerly known as blackbird
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Samstag 2. Februar 2008, 18:26

mitsuhiko hat geschrieben:Hast du dir Generatoren und Greenlets überhaupt mal angesehen?
Das habe ich. Ich hatte versucht zu motivieren, warum wiederholbare Continuations im Gegensatz zu Coroutinen (greenlets sind Coroutinen, mit Generatoren kann man ebenfalls eingeschränkte Coroutinen realisieren) unabdingbar sind. Vielleicht ist mir das nicht gelungen. Vielleicht hast du meinen Code nicht in allen Details gelesen. Es gibt einige Veröffentlichungen von Queinnec und Krishnamurthi aus dem Scheme-Umfeld zu diesem Thema. Die konnten das viel besser als ich. Ich möchte das jetzt hier nicht weiter ausführen.
mitsuhiko hat geschrieben:Nur weil ein Generator nureinmal ausgeführt werden kann wird dein Problem nicht unlösbar.
Ich behaupte doch. Das Problem ist ja die einmalige Ausführung. Du kannst es nicht lösen, indem du es wegdiskutierst. Ich will etwas (eine Continuation) haben, die ich mehrfach aufrufen kann und dann immer wieder den selben Code durchlaufen als wenn es das erste Mal wäre. Auf dieser Eigenschaft baut ein modaler Webserver nun mal auf.

Dennoch, wenn du ein Webrahmenwerk bauen kannst, in dem ich meine Programmlogik "modal" wie bei einer Kommandozeilenanwendung mit print und input formulieren kann, würde ich mich freuen, diese Implementierung zu sehen. Etwas wie ASP oder JSF, welches bei jedem Request einen Objektbaum erneut aufbaut, möchte ich aber ausschließen. Die Unterbrechung muss wie bei

Code: Alles auswählen

webPrint(webRead() + webRead())
mitten in einer Methode und einem Ausdruck möglich sein.
mitsuhiko hat geschrieben:Und ich hab Greenlets erwähnt, die funktionieren im Gegensatz zu einem selbstgebastelten Python Interpreter.
Über diesen Satz habe ich mich ein bisschen geärgert, wirkt er doch abfällig auf mich. Mein Code funktioniert bestens (nicht notwendigerweise die Version, die ich gepostet habe, da ich beim Zusammenschreiben vielleicht einen Fehler gemacht habe).

Stefan
Antworten