Noch ein Prolog in Python

Stellt hier eure Projekte vor.
Internetseiten, Skripte, und alles andere bzgl. Python.
Antworten
Benutzeravatar
pillmuncher
User
Beiträge: 1164
Registriert: Samstag 21. März 2009, 22:59
Wohnort: München

Sonntag 29. Dezember 2019, 23:26

Hallo Hivemind.

Zuerst: Was wäre ein guter Name für diese Monade? Mir fällt nix ein. Mit meiner Plüsch-Eule (in Ermangelung einer Gummi-Ente) reden hat auch nix gebracht. Bitte helft!

Code: Alles auswählen

from functools import reduce

# Look, Ma! It's a monad!
def unit(v):
    yield v

def bind(m, gen):
    return lambda v: (u for w in m(v) for u in gen(w))

def either(*gens):
    return lambda v: (u for gen in gens for u in gen(v))
    
def and_then(*gens):
    return reduce(bind, gens, unit)

def nothing(_):
    yield from ()
Damit konnte ich Kombinatoren zur Logik-Programmierung bauen, d.h. ein Prolog in Python als EDSL:

Code: Alles auswählen

from collections import namedtuple, ChainMap
from functools import singledispatch
from itertools import count, starmap


Variable = namedtuple('Variable', 'name')

class MetaVar(type):
    def __getattr__(cls, name, counter=count()):
        return Variable(name + str(next(counter)))

class Var(metaclass=MetaVar):
	pass

def unify_variable(that, this):
    def _(subst):
        if this in subst:
            yield from unify(subst[this], that)(subst)
        else:
            yield subst.new_child({this: that})
    return _


@singledispatch
def unify_list(that, this):
    return lambda _: ()

@unify_list.register(Variable)
def _(that, this):
    return unify_variable(that, this)

@unify_list.register(list)
def _(that, this):
    if len(this) != len(that):
        return nothing
    elif len(this):
        return and_then(*starmap(unify, zip(this, that)))
    else:
        return unit

@singledispatch
def unify(this, that):
    def _(subst):
        if this == that:
            yield subst
    return _

@unify.register(Variable)
def _(this, that):
    return unify_variable(that, this)

@unify.register(list)
def _(this, that):
    return unify_list(that, this)


def resolve(goal):
    return goal(ChainMap())
Verwenden kann man das so:

Code: Alles auswählen

def child(a, b):
    return either(
        unify([a, b], ['archimedes', 'bob']),
        unify([a, b], ['fluffy', 'fifi']),
        unify([a, b], ['daisy', 'fluffy']),
        unify([a, b], ['athene', 'zeus']),
    )

def descendant(a, c):
    b = Var.b
    return either(
        child(a, c),
        and_then(child(a, b), child(b, c)),
    )

def human(a):
    return either(
        unify(a, 'socrates'),
        unify(a, 'plato'),
        unify(a, 'bob'),
    )

def dog(a):
    return unify(a, 'fifi')

def mortal(a):
    b = Var.b
    return either(
        human(a),
        dog(a),
        and_then(descendant(a, b), either(human(b), dog(b))),
    )

x = Var.x
y = Var.y
for each in resolve(mortal(x)):
    print(each[x])
print()
for each in resolve(mortal('archimedes')):
    print('yes.')
print()
for each in resolve(mortal('joe')):
    print('yes.')
else:
    print('no.')
Ergebnis:

Code: Alles auswählen

socrates
plato
bob
fifi
archimedes
fluffy
daisy

yes.

no.
Meinungen? Kritik? Anregungen? Alles willkommen.
In specifications, Murphy's Law supersedes Ohm's.
__deets__
User
Beiträge: 7374
Registriert: Mittwoch 14. Oktober 2015, 14:29

Montag 30. Dezember 2019, 14:04

Der abstrakte Programmierknoten in meinem Hirn ist leider zu atrophiert und das auf Anhieb zu durchsteigen.

descendant hätte ich rekursiv definiert. So kann’s doch nur eine Enkel-Beziehung auflösen, oder?
Benutzeravatar
pillmuncher
User
Beiträge: 1164
Registriert: Samstag 21. März 2009, 22:59
Wohnort: München

Dienstag 31. Dezember 2019, 05:00

Danke für deine Anmerkungen, @__deets__,
__deets__ hat geschrieben:
Montag 30. Dezember 2019, 14:04
Der abstrakte Programmierknoten in meinem Hirn ist leider zu atrophiert und das auf Anhieb zu durchsteigen.
s.u.
__deets__ hat geschrieben:
Montag 30. Dezember 2019, 14:04
descendant hätte ich rekursiv definiert. So kann’s doch nur eine Enkel-Beziehung auflösen, oder?
Wollte ich auch, das war ein Versehen. Als ich es dann geändert hatte, ist mir ein RecursionError um die Ohren geflogen. Das Problem war, dass in descendant() sofort wieder descendant() aufgerufen wurde. Um das zu umgehen habe ich nun mittels des @recursion-Dekorators weitere eine Indirektionsstufe eingebaut.

WIe das ganze funkltioniert: Generator-Funktionen sind ja Coroutinen, also Funktionen, die ihre Arbeit unterbrechen und wieder aufnehmen können. Als Ergebnis liefern sie jedesmal mittels yield einen Wert - oder auch nicht, wenn sie nichts mehr zu sagen haben. Das kann man interpretieren als Erfolg (ein Wert wurde ausgespuckt), oder als Scheitern (kein Wert mehr). Die Monade dient dazu, die einzelnen Generator-Funktionen zu verketten. Ein anderes Bild für das, was da passiert, wäre ein Stack von solchen Generatoren, wobei immer der oberste aktiv ist und Werte ausgibt, während die darunter auf dessen Ende warten. Oder der oberste Generator kann seine Arbeit unterbrechen, indem er neue Element oben auf den Stack packt und die Kontrolle dorthin weitergibt. Mittels der Monade kann man Kombinatoren definieren, die man einfach deklarativ zusammenstecken kann. Wenn man so eine "Datenbank" aufgebaut hat, kann man Anfragen stellen. Dazu kann man Variablen verwenden, die dann in einem Environment durch diese Kette von Kombinatoren durchgereicht und werden und dieses nach und nach füllen. Dieses Environment bildet Variablen auf ihre Bindungen ab, also auf konstante Werte (beliebige Python-Objekte) oder andere Variablen. Es handelt sich hier um logische Variablen, also solche, die nachdem sie in einem Kontext an einen Wert gebunden wurden, diese Bindung nicht mehr verändern können, außer wenn dieser Kontext beim impliziten Backtracking wieder entsorgt wird. Dadurch kann man auch Programme schreiben, die rückwärts laufen, was IMO der ganze Witz der Logik-Programmierung ist.

Ich hoffe, diese Erkläreung hilft ein bisschen. Den Code habe ich übrigens nochmal überarbeitet und aufgeteilt und auf BitBucket gestellt:
https://bitbucket.org/pillmuncher/yogic

Das Sytsem hab ich yogic genannt, also yogisch, das Yoga betreffend, weil Logik-Programmierung einen weiteren Schritt zur Erleuchtung darstellt ;)

Einen Namen für die Monade brauch ich übrigens immer noch.
In specifications, Murphy's Law supersedes Ohm's.
Benutzeravatar
pillmuncher
User
Beiträge: 1164
Registriert: Samstag 21. März 2009, 22:59
Wohnort: München

Mittwoch 8. Januar 2020, 03:00

Jetzt hab ich nochmal alles aufgeräumt und kommentiert. Es sind - ohne Leerzeilen, Kommentare und top blurbs - 100 LOC. Und verständlicher ist es auch.

Die Monade heißt jetzt Backtracking Monade.

Hier nochmal der Link: https://bitbucket.org/pillmuncher/yogic

Meinungen und Kritik sehr willkommen.
In specifications, Murphy's Law supersedes Ohm's.
Antworten