Yogic jetzt mit cut Operator

[pillmuncher]

Hallo Forum.

Mein Spielzeug-Prolog habe ich jetzt um einen cut Kombinator erweitert. Damit ist es zB. möglich, logische Negation so zu definieren:

Code: Alles auswählen

def no(mf:Mf) -> Mf:
    return amb(
        seq(mf, cut, fail),
        unit,
    )

Das entspricht der Prolog-Definition:

Code: Alles auswählen

not(X) :- X, !, fail.
not(_).

unit ist immer wahr und fail ist immer falsch. amb() ist der oder-Operator, der wahr wird, wenn wenigstens eines seiner Argumente als wahr ausgewertet werden kann. Er definiert einen sog. Choice Point, also einen Punkt in der Auswertung, an dem aus mehreren Ausführungspfaden einer ausgewählt wird. Ein Scheitern dies gewählten Pfades veranlasst eine erneute Auswahl: Ein anderer Ausführungsfad wird versucht. Durch einen cut innerhalb eines amb() wird diese Auswahl beschitten - falls beim Backtracking der cut erneut erreicht wird, wird das nächst äußere amb() verlassen und es wird versucht, dazu einen alternativen Ausführungspfad zu finden.

Erreicht habe ich das durch Einführung von zwei zusätzlichen Continuations, einer Failure- und einer Escape-Continuation, zusätzlich zur bereits bestehenden Success-Continuation. Es ist also jetzt triple-barrelled. Dadurch wurde es auch möglich, alternative Ausführungspfade zu serialisieren, statt nacheinander in einem for-Loop durchzugehen, also den gesamten Ausführungsplan in einen Stack zu verwandeln. Alternativen werden einfach in die Failure-Continuation eingefädelt. Die Escape-Continuation wird zu Beginn jeder amb()-Auswertung auf die aktuelle Failure-Continuation gesetzt (vereinfachter Code):

Code: Alles auswählen

def choice(mf:Mf, mg:Mf) -> Mf:
    def mh(v:Value) -> Ma:
        def ma(y:Success, n:Failure, e:Escape) -> Solutions:
            def on_fail() -> Solutions:
                return mg(v)(y, n, e)
            return mf(v)(y, on_fail, e)
        return ma
    return mh

def amb(mfs:Iterable[Mf]) -> Mf:
    def mf(v:Value) -> Ma:
        def ma(y:Success, n:Failure, e:Escape) -> Solutions:
            return functools.reduce(choice, mfs, fail)(v)(y, n, n)  # <-  2 x n, nicht n und e!
        return ma
    return mf

Dadurch kann bei nachfolgendem Aufruf der Escape-Continuation (das zuvor gesetzte n) an diesen Punkt zurückgesprungen werden:

Code: Alles auswählen

def cut(v:Value) -> Ma:
    def ma(y:Success, n:Failure, e:Escape) -> Solutions:
        return y(v, e)  # <- statt n wird e als Backtrackingpfad gesetzt.
    return ma

Wer es genau wissen will: Es handelt sich um eine dreiläufige Continuation-Monade, die auf die List-Monade aufgepfropft wurde. Die Kombinatoren choice und unit bilden ein Monoid über den monadischen Kombinatoren, ebenso choice und fail. Alle vier zusammen bilden einen Verband.

Wegen der tief geschachtelten Closures habe ich alle lambda-Funktionen in richtige, benannte, Funktionen geändert und ich habe Type Hints verwendet. Das hat mir sehr dabei geholfen, den Überblick zu bewahren und mypy hat mir gesagt, wenn ich diese Closures falsch aufgerufen habe. Ich glaube, dass Type Hints selten nützlich sind und meistens nur nutzlosen optischen Lärm erzeugen, aber in manchen, seltenen Fällen wie hier, sind sie wirklich eine gute Sache.

Jedenfalls ist Yogic jetzt, mit cut, schon viel weniger ein Spielzeug. Hier ein Beispiel, wie man es verwenden kann:

Code: Alles auswählen

@predicate
def child(a, b):  # a is das Kind von b:
    return amb(
        unify([a, b], ['bob', 'archimedes']),
        unify([a, b], ['daisy', 'fluffy']),
        unify([a, b], ['fluffy', 'fifi']),
        unify([a, b], ['athene', 'zeus']),
    )
    

@predicate
def descendant(a, c):  # a ist ein Nachfahre von b:
    b = var()
    return amb(
        child(a, c),
        seq(child(a, b), descendant(b, c)),
    )


x = var()
y = var()

for each in resolve(descendant(x, y)):
    print(each[x], each[y])

Ergenis:

Code: Alles auswählen

bob archimedes
daisy fluffy
fluffy fifi
athene zeus
daisy fifi

Es gibt eine example.py, wo auch der cut verwendet wird.

Meine Bitte: Kommentare, Meinungen und Verrisse. Und hat jemand einen Home-Office Job zu vergeben? Oder einen im süd-östlichen Allgäu?