Notizen zur Vorlesung SE3: Logikprogrammierung

Wintersemester 2020/2021

2. Sitzung 13.11.2020

• Editor für Prolog -> beliebiger ASCII Editor
  • in Prolog eingebauteter Editor wird mit

    edit.

    geöffnet

Themen aus Vorlesung 1

• Berechnungsuniversalität (= Turing-Mächtigkeit)
• Warum ist eine relationale Datenbank nicht berechnungsuniversell?
  • relationale Datenbank besteht nur aus Tabellen mit Daten und relationaler Algebra
  • nicht in der Lage transitive Hülle zu bilden -> dadurch kein Bearbeiten von komplexen Problem (Beispiel: Navigationssystem)
  • deswegen Verwendung eines berechnungsuniversellen hybriden Modell: Datenbank mit eingebetteter Programmiersprache (aber Zusicherungen der relationalen Datenbank (z.B. das Anfrage immer terminiert, Kohärenz...) im allgemeinen Fall nicht garantiert)
• Warum ist ein Spreadsheet nicht berechnungsuniversell?
  • Berechnung beschränkt durch Größe der Tabelle
• Abstraktion
  • Vereinfachung der Realität, konzentrieren aufs Wesentliche
  • Hervorheben von wichtig erachteten Sachen und Vernachlässigen von unwichtig erachteten Sachen
  • Abstraktion ist notwendig, um Probleme zu vereinfachen
  • aber subjektive Sicht und damit vielleicht Ausblenden wichtiger Detail
  • Abstraktion muss kommuniziert werden
• Beispiele für Abstraktion:
  • Objektorientierte Programmierung (In der OOP schreiben wir Klassen, innerhalb der Klassen konzentrieren wir uns auf das wesentliche welches ein Objekt ausmacht.)
  • lineare Regression (eine beobachtete abhängige Variable durch eine oder mehrere unabhängige Variablen zu erklären)
    • ein Regressionsmodell vereinfacht die Realität auf eine endliche Zahl von Beobachtungsvariablen und einen linearen Zusammenhang. Beides muss nicht ausreichend sein, um die Realität angemessen zu becshreiben.
    • die Verwendung eines Modells, das durch lineare Regression erzeugt wurde, ist auch eine Abstraktion von der Realität. Die Realität wird vereinfacht auf eine endliche Sammlung von Datenpunkten. Sie Datensammlung muss aber nicht repräsentativ sein.
  • Neuronale Netze (abstrahieren vom biologischen Hirn und den eigentlichen chemischen Prozessen),
  • Simulationen, Programmiersprachen, Navigationssysteme (die Trajektorien)
  • Ignorieren physikalischer Einheiten
  • Vererbung (höher in der Vererbungshierarchie = höhere Abstraktion) <- this
  • Prototyping
  • Datentypen (max. INT)
  • Testen von Programmen (Beim Testen wird nicht jede einzelne Möglichkeit getestet, es konzentriert sich auf die wesentlichen Fälle. Hierzu werden beispielsweise Äquivalenzklassen gebildet)
  • Programmiersprachen an sich (als Abstraktion für Maschinencode)
  • Laufzeitenanalyse von Algorithmen (Wir bestimmen normalerweise nicht die konkrete Laufzeit eines Algorithmus, sondern geben die Klasse der Laufzeit an. Es ist uns (normalerweise) nicht wichtig, wie viele Schritte die Maschine exakt benötigt, die Klasse ist entscheidend).
  • Programmierung will weg vom Einzelfall
• Logikprogrammierung abstrahiert auch vom Algorithmusbegriff (algorithmischer Ablauf bleibt verborgen)
• Warum vertragen sich Logikprogrammierung und Objektorientierte Programmierung schlecht zusammen?
  • in OOP wird genau ein return-Wert erwartet
  • Logikprogrammierung gibt aber mehrere Werte zurück (durch ; )
  • um Problem zu umgehen, kann man zwar alle Werte in einen Container einfügen. Dies ist aber in vielen Fällen nicht sinnvoll, insbesoindere dann nicht, wenn man anschließend den Container erst mal wieder zerlegen muss, weil man die einzelnen Wete benötigt.

Themen aus Vorlesung 2

• Relationale Datenbanken
• Unifikation (Fundament der Logikprogrammierung)
  • einfachster Fall: Identitätstest, überprüft Name des Prädikats, Stelligkeit und paarweise identische Argumente
  • Später erweitert zu Gleichheit unter Variablensubstitution
• Eine elementare Anfrage ist vergleichbar mit Selektion in der relationalen Datenbank
• Programmierbeispiel in Prolog

3. Sitzung 20.11.2020

Fragen zur Vorlesung

Frage: Bei der Disjunktion herscht keine Koreferenz zwischen den Variablen verschiedener Klauseln, aber bei der Konjunktion schon, oder? Warum sollte man dann die Disjunktion vermeiden und nicht die Konjunktion?

Antwort: Die Konjunktion lässt sich nicht vermeiden. Ohne sie sind komplexe Anfragen unmöglich. Die Konjunktion stellt ja erst die notwendige Verbindung zwischen verschiedenen Prädikatsaufrufen (Teilanfragen) her. Eine Disjunktion hingegen kann man immer in zwei alternative Klauseln auflösen. Deshalb ist der Operator für die Disjunktion ja auch genau der gleiche, wie das Kommonado für die Suche nach alternativen Variablenbelegungen am interaktiven Prompt.

Die Gefahr bei der Disjunktion besteht darin, dass man bei der impliziten Klammerung (Konjunktion bindet stärker als Disjunktion) Fehler macht oder nicht beachtet, dass der Disjunktionsoperator immer wie ein Backtracking wirkt und alle bisher vorgenommenen Variablenbindungen wieder auflöst. Eine Koreferenz über den Disjunktions-Operator hinweg ist also nicht möglich und damit die einfache Grundregel: Der Gültigkeitsbereich einer Variablen ist die Klausel wird außer Kraft gesetzt. Die Variable X links vom ';' ist also in Wirklichkeit eine ganz andere Variable als die Variable X rechts vom ';'. Auch das ist eine potenzielle Fehlerquelle, vor allem weil man das ';' leicht übersehen kann.

Frage: Können Sie nochmal den Unterschied zwischen denotationeller und operationeller Semantik erklären? Das kommt mir immer wie das Gleiche vor, was es bei der Logikprogrammierung ja auch sein soll, aber hätten Sie ein Beispiel aus einem anderen Bereich, wo die beiden nicht übereinstimmen?

Antwort: Nein auch in der Logikprogrammierung ist das nicht immer identisch. Spätestens bei den deduktiven Datenbanken werden wir sehen, dass die beiden Semantikbegriffe systematisch voneinander abweichen.

Die denotationelle (auch deklarative) Semantik ist der Versuch, die Arbeitsweise eines Programms auf ein etabliertes mathematisches Konzept zurückzuführen. Bei den beiden deklarativen Programmierparadigma ist dieses Konzept entweder der lambda-Kalkül für die funktionale Programmierung oder die Prädikatenlogik erster Stufe (eingeschränkt auf den Spezialfall von Horn-Klauseln) für die Logikprogrammierung. Bei der Umsetzung dieser mathematischen Konstrukte in ein maschinell ausführbares Programm muss man aber Kompromisse eingehen. So muss etwa bei der funktionalen Programmierung festgelegt werden, ob die Argumente einer Funktion strikt (eager) ausgewertet werden, oder nicht strikt (lazy). Je nachdem wofür man sich entscheidet, muss man mit Artefakten rechnen, z.B. immer dann, wenn in einem Konditional eine Nebenwirkung auftritt (z.B. eine Division durch Null). Dann gibt es etwa bei der strikten Auswertung einen Fehler auch dann, wenn dieser Zweig des Konditionals gar nicht benutzt werden sollte. Bei der nicht strikten Auswertung hingegen können sich während der Auswertung eines Arguments Änderungen an den Wertebelegungen der für die folgenden Argumente benötigten Variablen oder sogar an den betreffenden Funktionsdefinitionen ergeben haben.

In der Logikprogrammierung hängen die unerwünschten Effekte der operationalen Semantik fast immer damit zusammen, dass der Prädikatenkalkül (denotationelle Semantik!) stets von Mengen von Variablenbindungen spricht, während das Prolog-System (operationale Semantik!) gezwungen ist, die Elemente dieser Mengen nacheinander aufzuzählen und dabei nicht merkt, dass es sich dabei lustig im Kreise dreht. Auf diese Weise entstehen Terminierungsprobleme. Auf der Ebene der relationalen Datenbanken spielt das aber noch keine Rolle.

Bei den imperativen Programmiersprachen ist nach meinem Wissen die Unterscheidung zwischen operationaler und denotationeller Semantik nicht sinnvoll, da das zugrundeliegende Maschinenmodell (die Turing-Maschine) bereits inhärent operational ist und daher keine explizit denotationelle Semantik dafür angegeben werden kann. Diese Information sollten Sie aber mit Vorsicht genießen, da ich in diesem Gebiet kein Experte bin.

Man könnte nun meinen, eine denotationelle Semantik ist eigentlich überflüssig. Das ist aber nicht der Fall, denn sie bietet ganz wesentliche Vorteile für die Programmentwicklung, die Programmtransformation (Optimierung!), und den Korrektheitsbeweis von Programmen. Bei einem deklarativen Programm, also eines, bei dem die beiden Semantikbegriffe zusammenfallen, ist das Berechnungsergebnis immer unabhängig vom Kontext in dem der Programmaufruf erfolgt. Damit lässt sich die Korrektheit eines solchen Programms immer lokal beurteilen. Daher kann auch die Reihenfolge der Berechnungen geändert werden, ohne dass sich dadurch das Ergebnis verändert. Die Auswirkungen auf die Effizienz der Programmabarbeitung können aber gravierend sein.

Themen zur Vorlesung

• Unterschiede und Gemeinsamkeiten der Begriffe Klausel, Fakt, Anfrage, Regel
  • Wie sehen sie aus (Syntax)
    • Klausel: Wird immer mit einem Punkt abgeschlossen.
    • Fakt: ein Spezialfall einer Klausel mit der Form: name(Term, Term, ...). Enthält genau eine Grundstruktur.
    • Regel: ein Spezialfall einer Klausel mit der Form: Regel : := Kopf ':-' Körper. Kopf ist eine Grundstruktur, Körper eine Anfrage
    • Anfrage: ein Spezialfall einer Klausel, die aus einer oder mehreren Grundstrukturen (Teilzielen) besteht. Die Teilziele können konjunktiv oder disjunktiv verknüpft sein.
  • Was bewirken sie (Semantik)
    • Fakten: Beenden eine Suche mit einem positiven Resultat Sie entsprechen einer universell gültigen Aussage.
    • Regeln: Ermöglichen das Ableiten von neuen Fakten, indem mit den Teilzielen im Körper der Regel neue Suchen gestartet werden. Sie entsprechen einer Implikation: Die Aussage im Kopf gilt, wenn die Bedingungen im Körper erfüllt sind.
    • Anfragen: Teilziele werden auf Unifizierbarkeit mit Einträgen in der Datenbank überprüft. Dadurch werden Variable gebunden (Berechnungsergebnisse ermittelt).
  • Wo treten sie auf (Pragmatik)
    • Klausel: in der Datenbank, in einer über consult/1 einzulesenden Datei, als Argument eines =assert=-Aufrufs
    • Anfrage: am Prompt, im Körper einer Regel

Pattern für relationale Datenbankanfragen

• Projektion (Wegfall von Spalten)

  ?- relation(X,_,Y,_,Z,...).
  

• Selektion (Auswahl von Tupeln)
  • Gleichheit

    ?- relation(Konstante1, X, Konstante2, Y, Konstante3,...).
    

  • sonst

    ?- relation(X,...Y,...Z), 
       X \= Konstante1, 
       Y < Konstante2, 
       Z =< Konstante3.
    

• (Equi-)Join (Kombination zweier Tabellen)

  ?- relation1(A,...,X,...,B), relation2(C,...,X,...,D).
  

• Extremwertdetektion, hier z.B. Max
  • deklarativ

    ?- relation(...,X,...,Max,...),
       \+ (relation(...,X,...,NotMax,...),
           NotMax > Max). 
    

  • prozedural

    ?- findall(Y,relation(...,X,...,Y,...),ListeY),
        max_list(ListeY,MaxY),
        relation(...,X,...,MaxY,...).
    

4. Sitzung 27.11.2020

Fragen zur Vorlesung

Frage: Was bedeutet Konsumtion einer rekursiven Struktur? Bspw. auf Folie 158

Antwort: Die Datenstruktur wird (durch Unifikation) in Ihre Bestandteile zerlegt. Das ist bei Peano-Zahlen trivial, weil jede Peano-Zahl immer nur genau einen Bestandteil hat, die um eins verringerte Zahl. Dadurch wird ein umfassenderes Problem auf ein einfacheres zurückgeführt: Um zu zeigen, dass s(s(s(0))) eine Peano-Zahl ist, muss ich zeigen, dass s(s(0)) eine Peano-Zahl ist. Um zu zeigen, dass s(s(0)) eine Peano-Zahl ist, muss ich zeigen, dass s(0) eine Peano-Zahl ist usw. Die ursprüngliche Zahl s(s(s(0))) wird als schritt weise konsumiert (verbraucht), bis ich bei der 0 angekommen bin. Dann weiß ich, dass die ursprünglich eingegebene Zahl eine Peano-Zahl ist.

Frage: Warum hilft das Hilfsprädikat (bei Symmetrie und Transitivität, Terminierungsprobleme zu vermeiden?

Antwort: Die Ursache für ein Terminierungsproblem ist immer eine unbeschränkte Rekursion. Sie bietet der Suche immer wieder eine Möglichkeit, Alternativen zu überprüfen, obwohl es möglicherweise gar keine Lösung geben kann. D.h. das System sucht unendlich lange. Typischerweise tritt dieses Problem immer auf, wenn ein rekursiver Aufruf noch uninstanziierte Argumente enthält.

Durch das Hilfsprädikat entfällt bei der Symmetrie die Rekursion (und damit die Ursache für das Terminierungsproblem) komplett. Bei der Transitivität wird zuerst durch das nichtrekursive erste Teilziel eine Datenbankabfrage durchgeführt, die freien Variablen durch die Fakten in der Datenbank (soweit dies möglich ist) instanziiert. Erst danach erfolgt mit dieser Variablenbindung der rekursive Aufruf im zweiten Teilziel.

Frage: Wird die '0' als erste Peano Zahl immer wieder ausgegeben? S. Folie 159

Antwort: Nein. Der Fakt peano(0) wird aber in jedem Rekursionsschritt benötigt, um die bis dahin vorliegende unterspezifizierte Datenstruktur durch "Hineinunifizieren" der Konstante 0 zu einer vollständigen Peano-Zahl zu ergänzen, die dann auch ausgegeben wird. Erst wenn nach dieser Ausgabe nach einer Alternative gefragt wird, wird statt der 0 dort die unterspezifizierte Struktur s(_23456) "hineinunifiziert". Deren uninstanziierte Variable (_23456) muss dann auf der nächsten Rekursionsebene instanziiert werden, entweder durch eine 0 (dann entsteht eine vollständige Peano-Zahl) oder durch die uninstanziierte Struktur s(_23457) (die wiederum instanziiert werden muss) usw. Auf diese Weise werden die Peano-Zahlen systematisch "von außen nach innen" aufgebaut:

     Aufruf: ?- peano(P)

Alternative 1                       Alternative 2 
mit Klausel 'peano(0).'             mit Klausel 'peano(s(X)) :- peano(X).'

P = 0                               P = s(_23456)
mit _23456=0: P = s(0)              mit _23456=s(_23457):  P = s(s(_23457)) 
mit _23457=0: P = s(s(0))           mit _23457=s(_23458):  P = s(s(s(_23458)))
mit _23458=0: P = s(s(s(0)))        mit _23458=s(_23459):  P = s(s(s(s(_23459))))
mit _23459=0: P = s(s(s(s(0))))     mit _23459=s(_23460):  P = s(s(s(s(s(_23460)))))
            . . .                               . . .

Nur die Alternative 1 wird ausgegeben. Sie wurde durch einen Fakt erzeugt, der die Suche erfolgreich abschließt. Alternative 2 ist ein Zwischenergebnis, das durch die Unifikation des Klauselkopfes mit der Anfrage entstanden ist. Es muss durch den Aufruf im Körper der Klausel noch weiter instanziiert werden (falls möglich). Die Ausdrücke der Art '_23456' usw. sind interne, vom System erzeugte Variable.

Typische Anwendungen für transitive Relationen

• Vorfahren- /Nachfahrenbeziehungen
• Hierarchien
  • Organisationen
  • Begriffshierarchien
  • Vererbungshierarchien, z.B. in der OO-Programmierung
  • Dateisystem
  • Bibliothekskatalog
• Teil-von-Beziehungen
• Produktionsprozesse, Planung

Pattern für spezielle Relationstypen

• Transitivität:

  relation_trans(X,Y,...) :- 
     relation_direkt(X,Y,...).
  
  relation_trans(X,Y,...) :- 
     relation_direkt(X,Z,...), relation_trans(Z,Y,...).
  

• Symmetrie

  relation_sym(X,Y,...) :- 
     relation_direkt(X,Y,...).
  
  relation_sym(X,Y,...) :-
     relation_direkt(Y,X,...).
  

• Transitivität und Symmetrie

  relation_sym_trans(X,Y,...) :- 
     relation_direkt(X,Y,...).
  
  relation_sym_trans(X,Y,...) :-
     relation_direkt(Y,X,...).
  
  relation_sym_trans(X,Y,...) :- 
     relation_direkt(X,Z,...), relation_sym_trans(Z,Y,...).
  
  relation_sym_trans(X,Y,...) :- 
     relation_direkt(Z,X,...), relation_sym_trans(Z,Y,...).
  

• Nichtreflexivität

  relation_nichtrefl(...,X,...,Y,...) :-
     relation_refl(...,X,...,Y,...), X\=Y.   
  

6. Sitzung 11.12.2020

Fragen zur Vorlesung

Frage: Sie haben in der Vorlesung gesagt, dass Operatoren und Listen syntaktischer Zucker sind, können Sie das nochmal erläutern?

Antwort: Operatoren sind nur eine alternative Schreibweise für ein- bzw. zweistellige Strukturen, die insbesondere im Bereich der Arithmetik die Verwendung der üblichen mathematischen Notation erlauben. Dadurch kann man zum Beispiel wie gewohnt

• statt '+'(1,2) auch 1+2 schreiben (Infix-Operator)
• statt lg(8) auch lg 8 (Präfixoperator) und
• statt '!'(4) auch 4! (Postfixoperator).

Die Operatoren vereinfachen nur die Nutzung. Intern wird immer mit Strukturen der Art funktor(Argument1, Argument2) bzw. funktor(Argument) gearbeitet. Deshalb habe ich es als "syntaktischen Zucker bezeichnet": Schmeckt gut, ist aber nicht unbedingt notwendig.

Gleiches gilt auch für die Listennotation. Einfach verkettete Listen werden intern immer als rekursiv eingebettete zweistellige Strukturen repräsentiert. Seit ein paar Jahren sind die im SWI-Prolog für den Nutzer nicht mehr sicht- bzw. nutzbar.

Frage: Was kann man machen, wenn ein Prädikat keine Richtungsunabhängigkeit unterstützt, diese aber erreicht werden soll? (is Operator ersetzen?)

Antwort: Man muss alle gewünschten Verarbeitungsrichtungen implementieren und dann durch Überwachung der Argumente überprüfen, welche Variante aktuell vorliegt. Zum Überprüfen kann man die Prädikate var/1 (Argument ist noch nicht instanziiert) bzw. nonvar/1 (Argument ist bereits instanziert) benutzen. Es gibt keinen Ersatz für die arithmetische Auswertungsumgebung. Der is - Operator ist ja nur ein (und zwar das wichtigste) Prädikat, das funktional auswertet.

Frage: In den Vorlesungsfolien befindet sich auf Seite 180 eine Tabelle mit speziellen Operatoren wie.B. numerischer Vergleich, Unifikation usw.. Weiterhin sind in der Tabelle Zahlen von 200-1200 als Präzedenzen aufgelistet. Könnten Sie noch einmal erklären was Präzedenzen bzw. die Zahlen genau bedeuten?

Antwort: Präzedenzen regeln die Bindungsstärke eines Operators, z.B. Punktrechnung geht vor Strichrechnung, d.h. ein Ausdruck wie 3 + 4 * 5 wird implizit geklammert als 3 + (4 * 5). Deshalb haben die Operatoren + und - eine höhere Zahl als * bzw. /. Höhere Zahlen binden schwächer. Das hat irgendjemand irgendwann mal so festgelegt.

8. Sitzung 8.1.2021

Frage: Was ist ein Atom?

Ein Atom ist eine alphanumerische Konstante, die im Normalfall mit einem Kleinbuchstaben beginnt. Soll das Atom aus irgendwelchen Gründen mit einer Ziffer, einem Großbuchstaben oder einem Sonderzeichen beginnen, muss es in Hochkommas eingeschlossen werden: 'Name' bzw. '1a' .

Themen der Vorlesung

Wie kann man Analogien zwischen Datentypen für die Programmentwicklung ausnutzen.

1. Analogie: Peanozahlen und Binärbäume

Peano-Zahlen bestehen aus einstelligen Strukturen des Typs s(X) bzw. einem (vereinbarten) Abschlusselement 0.

Binärbäume bestehen aus zweistelligen Strukturen des Typs s(X) (der Funktor ist beliebig). Die zweistelligen Strukturen entsprechen den Verzweigungen des Baumes. Als Blattknoten werden hier zur Vereinfachung immer nur Atome betrachtet.

Der einzige Unterschied besteht also in der Stelligkeit der elementaren Bausteine und der Art der Abschlusselemente. In diesem Sinne sind die Peano-Zahlen der Spezialfall einer nichtverzweigenden (d.h. linearen) Baumstruktur.

Diese Analogie kann man bei der Programmentwicklung ausnutzen. Bekannt sei z.B. eine Prädikatsdefinition für einen Typtest der Peano-Zahlen

% peano(?PeanoZahl)
peano(0).
peano(s(X)) :- peano(X).

dann ergibt sich ein analoger Typtest für Binärbäume zu

% bintree(+Binaerbaum)
bintree(X) :- atom(X).
bintree(s(X,Y)) :- bintree(X),bintree(Y).

indem man im Rekursionsabschluss den Test auf die Null durch einen Test auf das Vorliegen eines Atoms ersetzt. Im Rekursionsschritt müssen jetzt zwei Bedingungen überprüft werden: Ist sowohl der linke Zweig, als auch der rechte Zweig des Baumes ein (eingebetteter) Binärbaum. Da der Test im Rekursionabschluss (atom(X)) nicht richtungsunabhängig ist, kann auch das Gesamtprädikat nur zum Testen, nicht aber zum Generieren von Binärbäumen verwendet werden.

Will man die Einbettungstiefe eines Blattknotens in einem Binärbaum berechnen, dann entspricht das dem Integer-Äquivalent für eine Peano-Zahl: Wie viele s-Strukturen muss ich passieren, ehe ich das Abschlusselement erreiche? Dafür haben wir zwei Implementationsvarianten kennengelernt naiv reklursiv und endrekursiv. Hier die naive Variante

% peano2int(+PeanoZahl,?Integerzahl)
peano2int(0,0).
peano2int(s(X),N1) :-
   peano(X,N),
   N1 is N + 1.

Die Änderungen am Rekursionsabschluss sind wieder genau die gleichen. Den Rekursionsschritt müssen wir jetzt jedoch in zwei alternative Klauseln aufteilen, da Blattknoten ja auf unterschiedlichen Ebenen des Baumes auftreten können und wir für jede Verweigung sowohl die Einbettungstiefe im linken Zweig, als auch die im rechten Zweig ermitteln müssen.

% tiefe(Binaerbaum,Einbettungstiefe_eines_Blattknotens)
% Berechnet die Einbettungstiefe der Blattknoten auf allen Pfaden vom Spitzenknoten aus 
tiefe(A,0) :- atom(A).
tiefe(s(X,_),T) :-              % liegt eine Baumverzweigung vor?
  tiefe(X,T1),                  % dann inspiziere den linken Zweig
  T is T1+1.                    % und erhöhe die dabei gefundene Tiefe um eine
tiefe(s(_,Y),T) :-
  tiefe(Y,T1),                  % oder untersuche alternativ den rechten Zweig
  T is T1+1.

Die gleichen Modifikationen können bzw. müssen auch an der endrekursiven Implementation vorgenommen werden, wodurch sich das Peano-Prädikat

% peano2int_er(+PeanoZahl,?Integerzahl)
peano2int_er(Peano,Integer) :- p2i(Peano,0,Integer).

p2i(0,N,N).
p2i(s(X),Akk,N) :-
   Akk1 is Akk + 1,
   p2i(X,Akk1,N).

zu

% tiefe_er(+Baum,?Tiefe)

tiefe_er(Baum,Tiefe) :- tiefe2(Baum,0,Tiefe).

tiefe2(A,T,T) :- atom(A).
tiefe2(s(X,_),Akk,T) :-
  Akk1 is Akk + 1,
  tiefe2(X,Akk1,T).
tiefe2(s(_,Y),Akk,T) :-
  Akk1 is Akk + 1,
  tiefe2(Y,Akk1,T).

ändert.

Will man die maximale Einbettungstiefe eines Binärbaumes ermitteln, kann man dies entweder iterativ, oder rekusiv implementieren. Die iterative Lösung

% max_tiefe1(+Baum,?maximale_Einbettungstiefe)
max_tiefe1(Baum,Max) :-
  findall(T,tiefe(Baum,T),L),
  max_list(L,Max).

sammelt erst alle Einbettungstiefen in einer Liste und ermittelt dann das Maximum der Listenelemente mit dem bekannten Nachteil, dass für den Aufbau der Liste unnötig viel Resourcen (insbesondere Speicherplatz) verbraucht werden.

Dies lässt sich vernmeiden, wenn man die Maximumsdetektion direkt in die rekursive Definition integriert. Dazu muss man die beiden Klauseln für den Rekursionsschritt wieder zusammenfassen, denn jetzt will man ja die Zwischenergebnisse auf dem rechten und dem linken Zweig miteinander vergleichen. Da diese Zwischenergebnisse erst bekannt sind, wenn der Baum bereits bis hin zu den Blattknoten besucht wurde, bietet sich hier eine naiv rekursive Implementation an:

% max_tiefe2(+Baum,?Tiefe)

max_tiefe2(A,0) :- atom(A).
max_tiefe2(s(X,Y),T3) :-
  max_tiefe2(X,T1),          % ermittle die Tiefe auf dem linken Zweig
  max_tiefe2(Y,T2),          % ermittle die Tiefe auf dem rechten Zweig
  T3 is max(T1,T2),          % gib das Maximum davon zurück

2. Analogie: Binärbäume und vorwärtsverkettete Listen

Vorwärtsverkettete Listen setzen sich, wie Binärbäume auch, rekursiv aus zweistelligen Elementarstrukturen zusammen. Der wesentliche Unterschied besteht in der Behandlung des Listenendes, das immer durch ein spezielles Endesymbol (oftmals nil) markiert werden muss. Damit entspricht etwa die lineare Liste [a, b, c] der ausschließlich rechtsverzweigenden Baumstruktur s(a,S(b,s(c,nil))). Andere Beispiele sind

s(s(a,s(b,nil),s(c,nil))          [[a,b],c]
s(a,s(s(a,s(b,nil))))             [a,[b,c]]    

Der ausschließlich linksverzweigende Binärbaum s(s(s(a,nil),nil),nil) entspricht der Listeneinbettung [ [ [a] ] ] und weist eine deutliche Analogie zu den Peano-Zahlen auf.

Die Analogien zwischen Binärbäumen und vorwärtsverketteten Listen kann man ebenfalls bei der Programmentwicklung ausnutzen. So ist das folgende Prädikat, das testet, ob ein Element in einem Baum enthalten ist, aus der bekannten Definition von member/2 durch eine separate Behandlung von linkem und rechten Zweig entstanden.

% in_tree(?Element,+Baum)
in_tree(E,s(E,_)).           % Element im linken Zweig gefunden
in_tree(E,s(_,E)).           % Element im rechten Zweig gefunden
in_tree(E,s(L,_)) :-
  in_tree(E,L).              % Element im linken Zweig suchen
in_tree(E,s(_,R)) :-
  in_tree(E,R).              % Element im rechten Zweig suchen

Binäre Bäume in der von uns bisher betrachteten Form sind also nichts anderes als Container, wie Listen ja auch. Da sie aber im Vergleich zu Listen einen erheblich größeren, eigentlich sinnlosen Implementationsaufwand erzeugen, sind sie ohne weitere Modifikation auch nicht besonders nützlich. Sollen sie für praktische Zwecke eingesetzt werden, müssen die zweistelligen Grundlelemente durch weitere Argumentpositionen für die Beschriftung von Nicht-Blattknoten ergänzt werden: s(Label,LinkerZweig,rechterZweig)

s(f,s(e,s(b,a,c))),          % Spitzenknoten (f) und linke Verzweigung
          d),                % rechte Verzweigung unterhalb von e
     s(j,s(h,g,i),           % rechte Verzweigung unterhalb von f 
          k))                % rechte Verzweigung unterhalb von j

Zusätzlich wird es in den meisten Fällen erforderlich sein, die Blattknoten um die damit verbundene Nutzinformation (ein Web-Link, eine Übersetzung, ein Datenbankeintrag usw.) zu ergänzen. An der Grundstruktur der Prädikatsdefinitionen ändert sich durch diese Erweiterung nichts. Allerdings lassen sich mit derartigen Bäume z.B. im Bereich von Suchen und Sortieren erhebliche Effizienzgewinne erzielen.

9./10. Sitzung 15./22.1.2021

Pattern für die Listenverarbeitung (bzw. die Arbeit mit Strukturen)

Was haben die folgenden Prädikatsdefinitionen gemeinsam?

% member(?Element, ?Liste)
my_member(E,[E|_]).
my_member(E,[_|T]) :-
  my_member(E,T).

% nextto(?X, ?Y, ?Liste): Y follows X in List.
mynextto(X,Y,[X,Y|_]).
mynextto(X,Y,[_|T]) :- mynextto(X,Y,T).

% nth0(?N, ?List, ?Elem) ``Elem is the N'th element of List. 
% Counting starts at 0.''

% endrekursiv
mynth0(0,[E|_],E).
mynth0(N,[_|T],E) :- 
N1 is N-1,
mynth0(N1,T,E).

% naiv rekursiv
mynth0(0, [E|_], E).
mynth0(N, [_ | List], K) :-
 mynth0(N1, List, K), 
 N is N1 + 1.

• Sie arbeiten eine lineare Liste rekursiv ab
• Sie ermitteln Information in Abhängigkeit vom jeweils ersten oder den ersten n Elementen und stellen diese zur Verfügung bzw. überprüfen diese. Solche Information können z.B. die Identität des Elements (member/2, nextto/3), seine Position (nth0/3), seine Größe usw. sein.

Dieses Verhalten kann man im folgenden Programm-Pattern zusammenfassen:

foo(E,...,[X,...|_]) :- cond(E,...,X,...). 
foo(E,...,[_,...|T]) :-
   bar(E,..., E1,...),   %optional
   foo(E1,...,T).

• Die Bedingung im Körper der ersten Klausel ist optional. Sie fehlt in allen drei Beispielfällen.
• Das erste Teilziel im Körper der zweiten Kausel kann fehlen. Nur bei nth0/3 ist es vorhanden. Es kann auch nach dem rekursiven Aufruf stehen (z.B. bei der naiv rekursiven Variante von nth0/3.
• Es können ein Kopf (z.B. member/2, nth0/3) oder auch mehrere Köpfe (nextto/3) der Liste betrachtet werden.
• In die optionale Berechnung (bar(...)) können kein (member/2, nextto/3), ein (nth0/3) oder mehrere freie Parameter einbezogen werden.

Lassen sich auch verschachtelte Listen, wie z.B. in dem folgenden Programm, in das Pattern integrieren?

% in_tree(+Element,+NestedList)
in_tree(E,[E|_]) :- atom(E).
in_tree(E, [H|_]) :- 
  in_tree(E,H).
in_tree(E, [_|T]) :-
  in_tree(E,T).

Ja, dann muss man das Pattern aber erweitern:

foo(E,...,[X,...|_]) :- cond1(E,...,X,...).  % für die atomaten Blattknoten
foo(E,...,[X,...|_]) :- cond2(E,...,X,...),  % für die rekursiv eingebetteten Listen
   foo(E,...,X).
foo(E,...,[_,...|T]) :-
   bar(E,..., E1,...),   %optional
   foo(E1,...,T).

Da Listen ein Spezialfall binär verzweigender Strukturen sind (traditionelle Prolog-Listen: '.'(X,Y), aktuelle SWI-Prolog_Listen: '[|]'(X,Y), allgemeine binäre Strukturen: z.B. s(X,Y)), lässt sich das Pattern sinngemäß auch für Binärbäume der Art s(s(a,b),s(c,s(d,e))) anwenden:

% in_tree(+Element,+BinTree)
in_tree(E, E).
in_tree(E,s(X,_)) :-
   in_tree(E,X).
in_tree(E,s(_,Y)) :-
   in_tree(E,Y).

bzw.

inTree(E, s(E,_)) :- atom(E).
inTree(E, s(_,E)) :- atom(E).
inTree(E, s(Y,_) :-
        inTree(E, Y).
inTree(E, s(_,Y) :-
        inTree(E, Y)

Ein häufig benötigtes Pattern ist das Mapping, das eine Liste in eine Ausgabeliste transformiert, indem jedes Eingabeelement in gleicher Weise in ein Ausgabelement umgewandelt wird. Ein Beispiel ist das Normieren eines Vektors:

% normalize(+Factor, +Vector1, ?Vector2)

normalize(_,[],[]).
normalize(F, [E|T], [X|List2]) :- 
   X is E * F, 
   normalize(F,T,List2).

das dem folgenden Pattern entspricht:

foo(P,...,[],[]).
foo(P,...,[E1|T1],[E2|T2]) :-
  bar(P,...,E1,E2),
  foo(P,...,T1,T2).

Hier passiert der Strukturaufbau für die Ergebnisliste bereits im Kopf der zweiten Klausel. Dabei werden bereits beim rekursiven Abstieg Listen mit offenem Ende erzeugt. In das offene Ende wird dann in jedem Rekursionsschritt ein weiteres gepunktetes Paar mit dem neuen Element hineinunifiziert. Dabei entsteht wieder eine offene Liste, die in weiteren Rekursionsschritten neue Elemente aufnehmen kann, d.h. die Liste wird "von außen nach innen" aufgebaut. Sie steht zu jedem Zeitpunkt der Verarbeitung zur Verfügung, ist aber noch nicht vollständig bekannt (im Inneren ist noch ein Loch, in das weitere Information eingefügt werden kann).

Der Strukturaufbau kann auch beim rekursiven Aufruf im Klauselkörper erfolgen, allerdings benötigt man dafür einen Akkumulator. Der Akkumulator muss beim ersten Aufruf mit der leeren Liste initialisiert werden und kann beim Rekusionsabschluss per Koreferenz auf die Ergebnisargumentstelle übergeben werden:

normalize2(F,L1,L2):-
  normalize(F,L1,[],L2).

normalize(+Faktor,+Liste1,+Akk,?Liste2)
normalize(_,[],Akk,Akk).
normalize(F, [E|T], Akk, List) :- 
   X is E * F, 
   normalize(F,T,[X|Akk],List).

Die so entstanden Lösung ist zwar ebenfalls voll funktionsfähig, aber unnötig komplex, da man ja das gleiche Resultat auch ohne Akkumulator erreichen kann.

Für den Listenaufbau wird in der Regel kein Akkumulator benötigt. Das angegebene Pattern garantiert die Beibehaltung der ursprünglichen Reihenfolge. Grundlage dafür ist die prinzipielle Richtungsunabhängigkeit der Unifikation, durch die eine Liste auch "von außen nach innen" aufgebaut werden kann. Das jeweils noch unbekannte Listenende kann später noch hinzugefügt werden.

Wegen ihres sehr hohen Ressourcenverbrauchs ist eine Konstruktion der Ergebnisliste mit Hilfe des Prädikats append/2 unbedingt zu vermeiden:

normalize_app(+Faktor,+Liste1,?Liste2)
normalize(_,[],[]).
normalize(F, [E|T], List) :- 
   X is E * F, 
   normalize(F,T,L1),
   append(L1,[E],List).

Dies fügt zwar die neuen Resultate korrekt am Ende der Ergebnisliste hinzu, die im Laufe der Verarbeitung immer länger werdende Liste muss

1. immer wieder durchsucht werden, um das Listenende, an dem hinzugefügt werden kann, zu finden und
2. dabei wird durch das append eine neue Liste aufgebaut, um die originale Eingabeliste durch das Hinzufügen nicht zu zerstören (es also de facto die bisher schon aufgebaute Ausgabeliste immer wieder kopiert).

Dadurch erhöht sich die Komplexitätsklasse von linear zu quadratisch. sowohl für den Freispeicherkonsum, als auch für die Rechenzeit.

Ausnahmen von diesen Regeln sind immer dann gegeben, wenn aus irgend einem Grund die Reihenfolge der Listenelemente umgedreht werden muss, entweder, weil das die primäre Aufgabe des Prädikats ist (reverse/2), oder weil der Programmkontext die "falsche" Reihenfolge verursacht hat. Im zweiten Fall sollte man aber immer zuerst versuchen, die Ursachen für die falsche Reihenfolge zu beseitigen.

Ein zum Mapping sehr ähnliches Prädikat ist das Filtern. Dabei werden nur diejenigen Elemente der Eingabeliste in die Ausgabeliste übernommen, die eine bestimmte Bedingung erfüllen.

Ein sehr einfaches Beispiel ist das Erzeugen einer Liste, die nur all diejenigen Elemente der Eingabeliste aus Zahlen enthält, die einen vorgegebenen Schwellwert überschreiten:

spitzengruppe(N,[],[]).
spitzengruppe(N,[X|T1],[X|T2]) :- 
    X>N, 
    spitzengruppe(N,T1,T2).
spitzengruppe(N,[X|T],List) :-
    X=<N,
    spitzengruppe(N,T,List).

Das Pädikat gehört zu dem Pattern:

foo(P,...,[],[]).
foo(P,...,[X|T],[X|List2]) :- 
    bar(P,...,X), 
    foo(P,...,T,List2).

foo(P,...,[X|T],List) :-
    \+ bar(P,...,X),
    foo(P,...,T,List).

Die Eingabeliste wird linear durchlaufen und für jedes Element entschieden, ob es in die Ergebnisliste aufgenommen wird (Bedingung bar(...) erfüllt) oder nicht (Bedingung bar(...) nicht erfüllt). Der Aufbau der Ergebnisliste sollte auch hier wieder im Klauselkopf erfolgen, um die richtige Reihenfolge mit minimalem Aufwand zu garantieren.