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
Code: Alles auswählen
LOAD_FAST x
LOAD_FAST y
BINARY_ADD
RETURN_VALUE
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()
Code: Alles auswählen
print interpret(a, [3, 4]))
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
)
Code: Alles auswählen
def a(x): return x + 1
def b(f): return 3 + f(3)
print interpret(b, [a])
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())
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
...
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
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
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"))
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)
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
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