Continuation Monade in Python

[pillmuncher]

Hi Forum.

Gestern Nacht hatte ich ziemlich frustriert einen langen Artikel geschrieben, den ich dann aber nochmal überschlafen wollte, weswegen ich ihn zunächst nicht abgeschickt habe. Darin hatte ich versucht ein Problem zu beschreiben, das ich nicht lösen konnte, bzw. ich konnte es zwar lösen, aber der Code war sehr unschön, lang und unübersichtlich. Dabei ging es darum, dass an verschiedenen Stellen in meinem Programm nach und nach eine Struktur aufgebaut werden sollte, wobei der Anfangszustand der Struktur erst nach diesem Prozess festgelegt werden konnte. Ich hatte drei Varianten durchgespielt, alle objektorientiert, die mir alle nicht gefallen haben. Ein paar Stunden Schlaf, etwas googlen und etwas systematisches Denken haben mich dann zu dem Ergebnis geführt, dass das Problem einfach durch Continuations zu lösen ist, und spezifisch durch die Continuation Monade. Diese sieht so aus:

Code: Alles auswählen

def unit(v):
    return lambda c: c(v)

def bind(ma, mf):
    return lambda c: ma(lambda v: mf(v)(c))

def then(ma, mb):
    return lambda v: bind(ma(v), mb)

Hier ein simples Beispiel, wie man sie verwenden kann:

Code: Alles auswählen

def identity(x):
    return x

def add(n):
    def adder(x):
        return lambda c: c(x + n)
    return adder

def double(x):
    return lambda c: c(x * 2)

def inc(x):
    return lambda c: c(x + 1)

first = add(5)
second = then(first, double)
third = then(second, inc)

compute = bind(unit(5), third)
assert compute(identity) == 21  # (((5 + 5) * 2) + 1) == 21

compute = bind(unit(3), third)
assert compute(identity) == 17  # (((3 + 5) * 2) + 1) == 17

Wie man sieht, erfüllt sie alle meine Anforderungen. Verschiedene Berechnungsschritte können reifiziert, aneinandergereiht und an Namen gebunden werden, so dass sie im Programm herumgereicht werden können. Wenn die Folge von Schritten sans Initialwert vollständig ist, kann man sie mit einem versehen und für diesen auswerten.

Continuation Passing Style hatte ich schon öfter verwendet, aber die Continuation Monade war mir bisher ein Rätsel. Dann habe ich heute Morgen einen Artikel [Link] gefunden, wo sie für Clojure erklärt wird, und zwar viel besser, als ich es könnte. Python ist ja so eine Art Lisp mit Syntax, deswegen war der Code sehr einfach zu übertragen. Nur die then() Funktion stammt von mir, es ist die rechte Hälfte der rechten Seite des monadischen Assoziativgesetzes:

Code: Alles auswählen

bind(bind(unit(v), f), g) == bind(unit(v), lambda x: bind(f(x), g))

Es war im Übrigen nicht das erste Mal, dass ich versucht habe, Monaden in Python zu programmieren. Aber es war das erste Mal, wo es nicht in Frustration endete.

[pillmuncher]

Hier ein Beispiel, wie man damit sukzessive Dictionaries aufbauen kann:

Code: Alles auswählen

def set_key(key):
    def set_value(value):
        def update(env):
            env[key] = value
            return lambda c: c(env)
        return update
    return set_value

set_foo = set_key('foo')
set_bar = set_key('bar')
set_baz = set_key('baz')

first = set_foo(1)
second = then(first, set_bar('brezel'))
third = then(second, set_baz(123))

compute = bind(unit({}), third)
assert compute(identity) == dict(foo=1, bar='brezel', baz=123)

compute = bind(unit(dict(joe='bob')), third)
assert compute(identity) == dict(foo=1, bar='brezel', baz=123, joe='bob')

[pillmuncher]

Oder man kapselt alles in Objekte:

Code: Alles auswählen

class Cont:

    def __init__(self, func):
        self._func = func

    def __call__(self, c=identity):
        return self._func(c)

    @staticmethod
    def unit(v):
        return Cont(lambda c: c(v))

    def bind(self, mf):
        return Cont(lambda c: self(lambda v: mf(v)(c)))

    def then(self, mb):
        return Cont(lambda v: Cont.unit(v)(self).bind(mb))

Dann ist es etwas schöner zu verwenden:

Code: Alles auswählen

def add(n):
    def adder(x):
        return Cont(lambda c: c(x + n))
    return adder

def double(x):
    return Cont(lambda c: c(x * 2))

def inc(x):
    return Cont(lambda c: c(x + 1))

first = Cont(add(5))
second = first.then(double)
third = second.then(inc)

compute = Cont.unit(5).bind(third)
assert compute() == 21  # (((5 + 5) * 2) + 1) == 21

compute = Cont.unit(3).bind(third)
assert compute() == 17  # (((3 + 5) * 2) + 1) == 17

Oder gleich so:

Code: Alles auswählen

compute = Cont(add(5)).then(double).then(inc)

assert compute(5)() == 21  # (((5 + 5) * 2) + 1) == 21

assert compute(3)() == 17  # (((3 + 5) * 2) + 1) == 17

Und man sollte natürlich prüfen, ob die Monaden-Gesetze erfüllt sind:

Code: Alles auswählen

def check_laws(x, f, g):
    mv = Cont.unit(x)
    assert mv.bind(f)() == f(x)()
    assert mv.bind(Cont.unit)() == mv()
    assert mv.bind(f).bind(g)() == mv.bind(lambda v: f(v).bind(g))()

from itertools import product
for f, g in product([add(3), double, inc], repeat=2):
    for n in range(5):
        check_laws(n, f, g)

[Leonidas]

Muss ja sagen, das schaut erstaunlich sauber aus Kann man fragen was der Original-Usecase war, also quasi das Real-Life-Beispiel?

[pillmuncher]

Danke Leonidas.

Der Anwendungsfall: Ich habe einen AST, der komplexe Ausdrücke repräsentiert. Es gibt eine Visitor-Basisklasse, die über den AST läuft und die spezialisiert werden kann. Dabei möchte ich deklarativ, mittels eines "fluid" Dekorators für die Visitor-Methoden, bestimmte Transformationen definieren können. Die Transformationen können alles mögliche beinhalten, von Validierung von Werten in den Ausdrucks-Knoten bis hin zum Verschieben von Ästen im Baum. Wenn ich zB. einen Ausdruck habe wie a << b & c & d, dann besitzt der ursprünglich die Form (((a << b) & c ) & d), die ich ändern möchte zu (a << (b & (c & d))). Dabei hat << eine verkehrte Ausgangs-Präzedenz gegenüber &, und bei beiden ist die Assoziativität verkehrt. Ich möchte nun folgendes programmieren können:

Code: Alles auswählen

class MyTransformer(ASTVisitor):

    @op.xfy.prio(50)
    def visit_And(self, left, right):
        return And(left, right)

    @op.xfx.prio(80)
    def visit_LShift(self, left, right):
        return LShift(left, right)

Der jeweils von der Methode zurückgegebene Knoten wird dann entsprechend modifiziert und ggf. seine Äste "umgehängt". Dieselbe Art von Dekoratoren möchte ich auch für die Knotenklassen verwenden, um damit die Defaulteinstellungen festlegen zu können.

xfy bedeutet übrigens rechts-assoziativ, xfx bedeutet nicht-assoziativ (so dass a << b << c ungültig wäre) und prio(n) legt die Stärke der Bindung fest, je höher die Zahl, desto geringer die Bindung.

Dazu sollten ürsprünglich noch andere Arten möglicher automatischer Transformationen kommen, die dann als Continuations codiert werden sollten. Wenn ich das jedoch weglasse, kann ich das ganze so vereinfachen, dass ich statt der Continuations nur ein Dictionary durch die fluiden Aufrufe weiterreichen muss, und bei aller Begeisterung für Rube-Goldberg-Maschinen hat das auch was für sich.

Das Ziel des ganzen Programms besteht darin, Python mit einer eingebetteten Horn-Klausel-Sprache zu versehen, also einem "Prolog". Die Audrücke werden ausgehend von Symbol-Objekten automagisch von Python zusammengesetzt, ähnlich wie SymPy das macht. Anschließend können die gewonnenen Ausdrucks-Bäume als Logik-Programm interpretiert werden. Es gibt schon einen (scheußlich programmierten, aber leidlich funktionierenden) Prototypen, hornet, d.h. HORN clauses via Expression Trees. Jetzt geht es darum, aus dem, was ich dabei gelernt habe, etwas ordentliches zu bauen.

Hier ein Beispiel, wie man es verwenden kann (der @hornet-Dekorator sorgt im Zusammenspiel mit Database dafür, dass alle Parameter außer dem ersten mit passenden logischen Variablen/Atomen belegt werden):

Code: Alles auswählen

from resolver import hornet, Database, UnificationFailed
from system import not_, greater, findall, let, equal, join, writeln, _, cut


@hornet
def fbtest(db, fizzbuzz, fb, fb_out, divisible, V, Vs, N, N1, Max, D, S, X):

    db.assertz(

        fizzbuzz(N, Max) <<
            not_(greater(N, Max)) &
            findall(V, fb(V, N), Vs) &
            fb_out(N, Vs) &
            let(N1, N + 1) &
            fizzbuzz(N1, Max),

        fb('fizz', N) << divisible(N, 3),
        fb('buzz', N) << divisible(N, 5),

        fb_out(N, []) << writeln(N) & cut,
        fb_out(_, Vs) << join(Vs, S) & writeln(S),

        divisible(N, D) << let(X, N % D) & equal(X, 0),

    )

    for subst in db.query(fizzbuzz(1, 100)):
        break


fbtest(Database())

Wie man sieht, ist es nah an Prolog. Es erzeugt die beliebte Fizz-Buzz-Reihe:

Code: Alles auswählen

$ python3 fizzbuzz.py
1
2
fizz
4
buzz
fizz
7
8
fizz
buzz
11
fizz
13
14
fizzbuzz
...

Andere Beispiele sind ein symbolischer Differentiator, die Türme von Hanoi mit graphischer Ausgabe, damit man sehen kann, wie Hornet in andere Programme integriert werden kann, ein Parser für ein paar deutsche Sätze und eine Turing-Maschine.

Gruß,
Mick.