ChatGPT analysiert meinen Code

[pillmuncher]

Hi Forum.

Gerade hab ich mal ChatGPT gefragt, was mein Code in https://github.com/pillmuncher/yogic macht. Dazu habe ich den Code einfach kopiert und ChatGPT ein paar Hinweise gegeben. Zum Beispiel sagte es mir zuerst, dass es eine Parser Combinator Library sei, und ich habe ChatHPT dann darauf hingewiesen, dass es stattdessen eine Library für Logik Programmierung ist. Außerdem habe ich gebeten, nicht zu sehr ins Detail zu gehen.

Das Ergebnis ist recht gut, finde ich.

Code Snippet 1 (backtracking.py):

- The first code snippet implements a basic logic programming library using a monadic approach.
- It introduces functions like `bind`, `unit`, `zero`, `then`, `seq`, `alt`, and `predicate`.
- These functions enable backtracking, which is a fundamental aspect of logic programming.
- The library provides a way to define computations that explore alternative choices and generate multiple solutions.
- The `bind` function combines two monadic computations, allowing sequential composition and backtracking. If the first computation fails, it can backtrack and explore other options.
- The `unit` function represents a successful computation with a single solution, while the `zero` function represents a failed computation with no solutions.
- The `seq` function composes multiple monadic computations in sequence, enabling backtracking at each step. It attempts each computation one after the other and backtracks if any of them fail.
- The `alt` function combines multiple monadic computations in parallel, representing alternative choices. It tries each computation and backtracks if all of them fail.
- The `predicate` decorator creates another level of indirection, allowing for the definition of computations with deferred execution, which is useful for backtracking scenarios.

Through the combination of these functions, the library provides a framework for expressing logic programming computations and exploring multiple possible solutions. It enables backtracking by allowing the exploration of alternative choices and the systematic search for valid solutions in a logical context.

Code Snippet 2 (unification.py):

- The second code snippet implements logic programming capabilities using a monadic approach, which inherently enables backtracking.
- It introduces the concepts of variables, substitution environments, and unification.
- Variables are represented by the `Variable` class and are bound to values during the execution of monadic computations.
- The `Subst` class represents a substitution environment that maps variables to values. It serves as the context for backtracking and maintains variable bindings.
- The `unify` function performs unification between two objects, handling variables, and exploring multiple possible matches. It allows for backtracking by attempting different combinations of variable bindings.
- The `resolve` function initiates the logical resolution of a goal by initializing a substitution environment. It provides backtracking capabilities by iteratively generating solutions through the execution of monadic computations.
- Backtracking is achieved through the combination of variable bindings, unification, and the generation of multiple solutions in an iterative manner.

The key points of the code snippet are:
- Variables and substitution environments are used to handle variable bindings during computations.
- The `unify` function explores various possibilities to find valid unifications and enables backtracking when a unification attempt fails.
- The `resolve` function leverages the substitution environment to generate multiple solutions by executing monadic computations iteratively, allowing for backtracking and exploration of alternative choices.

Through the use of variables, unification, and the management of substitution environments, the code snippet provides the foundation for logic programming capabilities. It enables backtracking by exploring different bindings and paths, allowing the search for valid solutions in a logical context.

[Xbash_Zero]

Ich bin neugierig, was macht Backtracking, wofür benötigst du es, wenn ich fragen darf? Und wie hast du das implementiert?

[pillmuncher]

@Xbash_Zero: Backtracking nennt man ein Verfahren, bei dem man versucht, Schritt für Schritt eine Lösung eines Problems zu finden. Dabei kann es passieren, dass man an einen Punkt kommt, von dem aus es keine weiteren brauchbaren Schritte mehr gibt. Dann geht man einen Schritt zurück, und versucht eine Alternative zu finden. Man muss sich also für den gesamten Suchraum merken, an welchen Stellen man welche Anzweigung genommen hat, um ggf. wieder dorthin zurückkehren zu können, um dann von dort aus einen anderen Weg einzuschlagen, bis man entweder eine Lösung gefunden hat oder feststellt, dass es keine Lösung gibt.

Implemetiert habe ich das mittels sog. Continuation Passing. Eine Continuation ist eine Funktion, die die Zukunft des Programms repräsentiert. Sie wird als Argument durch die Kette von Funktionsaufrufen durchgereicht, bis am Ende ein Ergebnis berechnet ist, dass dann dieser Funktion als Argument übergeben wird. Ein Beispiel:

Code: Alles auswählen

def add(x, y):
    return x + y

def mul(x, y):
    return x * y

a = add(3, 5)
b = mul(a, 4)
print(b)

Statt dass diese Funktionen das Ergebnis einfach mittels return zurückgeben, kann man ihnen eine Funktion, die Continuation, übergeben, die sie dann aufrufen müssen:

Code: Alles auswählen

def add(x, y, c):
    c(x + y)

def mul(x, y, c):
    c(x * y)

add(3, 5, lambda a: mul(a, 4, lambda b: print(b)))

Das ist natürlich ein triviales Beispiel, bei dem man normalerweise kein Continuation Passing verwenden würde. Interessant wird es, wenn die Funktionen, die eine Continuation übergeben bekommen, diese mehrfach oder gar nicht aufrufen. Dann könnte man zB. sowas machen:

Code: Alles auswählen

def foreach(ns, c):
    for n in ns:
        c(n)

foreach([2, 3], 
        lambda u: foreach([5, 6, 7], 
                          lambda v: add(u, v, 
                                        lambda a: mul(a, 4, 
                                                      lambda b: print(b)))))

Dann bekommt man das hier als Ergebnis:

Code: Alles auswählen

28
32
36
32
36
40

Da das so ziemlich mühsam und unübersichtlich ist, habe ich stattdessen eine sog. Monade verwendet. Das ist ein Design Pattern aus der Funktionalen Programmierung, das ursprünglich aus der Kathegorientheorie in der Mathematik stammt.

Monaden sind gewissermaßen eine Verallgemeinerung des Konzepts des Monoids aus der Abstrakten Algebra. Ein Monoid ist einfach eine mathematische Strukur, die aus einer Menge von Dingen, einer assoziativen binären Operation und einem neutralen Element besteht, also zB. den ganzen Zahlen, der Multiplikation und der eins: <Z, *, 1>. Dann gelten folgende Gesetze für alle a, b, c ∈ Z:

Code: Alles auswählen

(a * b) * c  =  a * (b * c)

a * 1  =  1 * a  =  a 

Das ganze funktioniert auch für die ganzen Zahlen mit der Addition und der 0, <Z, +, 0>:

Code: Alles auswählen

(a + b) + c  =  a + (b + c)

a + 0  =  0 + a  =  a 

Und auch für ganz andere Dinge, wie etwa Strings, <str, +, ''>:

Code: Alles auswählen

(a + b) + c  =  a + (b + c)

a + ''  =  '' + a  =  a 

Also zB.

Code: Alles auswählen

('halllo' + 'welt') + '!'  =  'halllo' + ('welt' + '!')  == 'hallowelt!'

'hallo' + ''  =  '' + 'hallo'  =  'hallo'

Und das funktioniert auch für Funktionen, die ein Argument nehmen und ein Ergebnis vom selben Typ zurückgeben, also etwa einstellige Funktionen von Zahlen. Dazu gibt es den Kompositionsoperator und die Identitätsfunktion, die einfach ihr Argument unverändert zurückgibt:

Code: Alles auswählen

def identity(x):
    return x

def compose(f, g):
    return lambda x: f(g(x))

Dann gilt:

Code: Alles auswählen

compose(compose(f, g), h)  =  compose(f, compose(g, h))

compose(identity, f)  =  compose(f, identity)  =  f

Das funktioniert, wenn die Funktionen alle denselben Typ erwarten und zurückgeben. Was aber, wenn das Ergebnis irgendeine "erweiterte" Version des Arguments ist, also zB. eine Berechnung + ein Log, wie die Berechnung zustande kam? Dann erwarten die Funktionen einen Typ T und liefern einen Typ T + Log zurück. Man kann sie also nicht mehr so einfach komponieren. Dazu brauchen wir einen besondern Kompositionsoperator, der üblicherweise bind genannt wird und spezifisch für jede Monade implementiert werden muss:

Code: Alles auswählen

def bind(ma:tuple[int,str], mf:Callable[[int],[int,str]]) -> tuple[int,str]:
    old_n, old_log = ma
    new_n, new_log = mf(old_n)
    return new_n, f'{old_log}, {new_log}'

Dazu braucht man noch ein neutrales Element, genanntt unit, das ebenfalls spezifisch für jede Monade implementiert wird:

Code: Alles auswählen

def unit(n:int) -> tuple[int,str]:
    return n, f'value {n}'

Jetzt kann man schreiben:

Code: Alles auswählen

def add3(n:int) -> tuple[int,str]:
    return 3 + n, f'add 3 = {3 + n}'

def mul4(n:int) -> tuple[int,str]:
    return 4 * n, f'mul 4 = {4 * n}'

print(bind(bind(unit(2), add3), mul4))

Das Ergebnis ist:

Code: Alles auswählen

(20, 'value 2, add 3 = 5, mul 4 = 20')

Jetzt können wir eine Monade bauen, die Continuations kapselt:

Code: Alles auswählen

from typing import Callable, TypeVar

Value = TypeVar('Value')
Result = TypeVar('Result')

Cont = Callable[[Value], Result]  # Eine Continuation wandelt einen Wert in ein Ergebnis 
Ma = Callable[[Cont], Result]  # Ein monadisches Objekt bekommt eine Continuation, aus der es ein Ergebnis erzeugt
Mf = Callable[[Value], Ma]  # Eine monadische Funktion kapselt einen Wert in einem monadischen Objekt

def bind(ma:Ma, mf:Mf) -> Ma:
    return lambda c: ma(lambda v: mf(v)(c))  # mf wird zur neuen Continuation, die alte Continuation wird angehängt

def unit(v:Value) -> Ma:
    return lambda c: c(v)  # unit erzeugt eine Funktion, die eine Continuatiuon erwartet, der dann der Wert übergeben wird

def add3(v:Value) -> Ma:
    return lambda c: c(3 + v)

def mul4(v:Value) -> Ma:
    return lambda c: c(4 * v)

a_computation = bind(bind(unit(5), add3), mul4)  # Eine monadische Berechnung wird konfiguriert
a_computation(print)  # Die monadische Berechnung wird ausgeführt und das Ergenis (32) ausgegeben

Ein Ma ist ein monadisches Objekt (eine Funktion), das eine Berechnung repräsentiert, deren Ergebnis an eine Continuation weitergereicht wird. Ein Mf ist eine Funktion, die aus einem Wert ein Ma erzeugt. Mittels bind kann man eine Mf auf ein Ma anwenden und bekommt wieder ein Ma. Das kann man nun zu komplexeren Berechnungen zusammenstecken. Solche Funktionen höherer Ordnung nennt man Kombinatoren. Am Ende übergibt man einfach die Continuation, die das Endergebnis entgegennimmt, zB. um es am Bildschirm auszugeben.

In meinem Logik-Programm habe ich so ähnlich gemacht, wie bei der Continuation Monade. Dadurch ist es möglich, logische Formeln einfach zusammen zu stecken und anschließend auswerten zu lassen.

[Kebap]

Ich gebe diesem Beitrag einen Daumen hoch. Sehr spannend. Danke für die ausführlichen Erklärungen und Beispiele.
Also ich meine deine Monadenstruktur. Die ChatGPT Analyse finde ich jetzt eher weniger interessant. Der versteht ja nix, sondern rät nur (ganz ok) herum.

[Xbash_Zero]

...

Mega, Danke für die Erklärungen und den Code ... Ich werde mich, sobald ich etwas mehr Zeit habe, näher mit diesen Themen Beschäftigen!

[nezzcarth]

Ich bin neugierig, was macht Backtracking, wofür benötigst du es, wenn ich fragen darf?

Ein schönes und anschauliches Beispiel für Backtracking ist finde ich das Generieren zufälliger Labyrinthe, sehr gut dargestellt hier: https://weblog.jamisbuck.org/2010/12/27 ... cktracking
Die interaktiven Beispiele in dem Post visualisieren ganz gut, was beim Backtracking passiert, da hier tatsächlich wörtlich "zurückgegangen" wird. Ist zwar Ruby und kein Python, aber das ist nicht so entscheidend, um das Konzept zu veranschaulichen.

[Xbash_Zero]

Ich bin neugierig, was macht Backtracking, wofür benötigst du es, wenn ich fragen darf?

Ein schönes und anschauliches Beispiel für Backtracking ist finde ich das Generieren zufälliger Labyrinthe, sehr gut dargestellt hier: https://weblog.jamisbuck.org/2010/12/27 ... cktracking
Die interaktiven Beispiele in dem Post visualisieren ganz gut, was beim Backtracking passiert, da hier tatsächlich wörtlich "zurückgegangen" wird. Ist zwar Ruby und kein Python, aber das ist nicht so entscheidend, um das Konzept zu veranschaulichen.

Danke für die Info und den Link!