PROgramming in LOGic

a.o.Univ.Prof. Dr. Franz Hörmann 1

PROgramming in LOGic

Von Alain Colmerauer in Marseille entwickelt (70er Jahre)Standardwerk „Programming in Prolog“ (Clocksin/Mellish)Deklarative Sprache (Problem wird beschrieben, Interpreter sucht selbst nach Lösung)Keine Schleifen sondern Rekursion (Datentyp: Liste)ISO-StandardViele unterschiedliche ImplementationenProblem oftmals: Integration grafischer Oberflächen (dazu zumeist objektorientierte Spracherweiterungen)



Verwendete Version: SWI-Prolog (http://www.swi-prolog.org/)

Programme bestehen aus Fakten und Regeln, die zur Laufzeit geändert werden können (auch Regeln können geladen, verändert oder gelöscht werden – selbstmodifizierende Programme AI)

Lösungssuche durch Interpreter: Backtracking

FRAGE: Können Programme jemals „intelligent“ sein? Was wären die Kriterien?



EXPERTENSYSTEME: – Programme, die selbst Probleme lösen (wie

menschliche Experten)– Programme, die menschliche Experten unterstützen

Expert System Shell:– Benutzeroberfläche– Leere Fakten- und Regelbank– Schlußfolgerungsmechanismus (Inference Engine) Knowledge Engineer



Beispiele erfolgreicher Expertensysteme:– PROSPECTOR (fand ein Molybdänvorkommen im Wert von über

US-$ 100 Mio)

– R1 (konfigurierte VAX-Computersysteme)

– DENDRAL (chemische Strukturanalysen)

– CADUCEUS (Expertenwissen über interne Medizin)

– PUFF (Expertensystem zur Diagnose von Lungenkrankheiten)



Facts:– fact(a, b, c).

Rules:– rule(A, B, C) :- rule1(A, B, C), rule2(A, B, C).

Queries (Goal):– ?-rule(A, B, C).

Variablen beginnen mit Großbuchstaben oder „_“



SWI-Prolog:– File/Consult

Program1.pl– likes/2: Prädikat (predicate) von der Stelligkeit 2 (arity 2)

– Wer liebt Erdbeeren?– ?- likes(X,strawberry).– X wird nach Suche in der Faktenbank gebunden (instantiated)



Program2.pl– Ausgabe der Lösung mittels write

Program2a.pl (verbesserte Ausgabe)Program2b.pl (wer liebt was? Durch fail wird die Suche wiederholt = Backtracking ausgelöst)Program2c.pl (fehlerhafte Programmänderung Variable X kann nicht gebunden werden!



Program3a.pl (kommt man von Raum a2 nach Raum a5?)– trace,r(a2,a5).– Goal ändern: r(a1, a5).– Funktioniert ebenfalls



Program3a.pl (Endlosschleife!)– Goal r(a5,a1) testen– trace, r(a5,a1)– Mittels Taste ‚a‘ abbrechen!

(jedem) Prolog fehlt (noch) Loop-Check Function!

Program3b.pl (Fakten wurden in c(a1, a2) umbenannt!)– r(a5,a1).– No funktioniert problemlos!



Datenstrukturen: Terme

Ein Term besteht aus einem Funktor und einem oder mehreren Argumenten– functor(arg1, arg2, ...).

Auch Regeln (rules) sind Terme (terms)!

Program4.pl (arithmetische Prädikate)

Program4a.pl (allgemeingültige Version unter Verwendung des „Ungleich“-Prädikats)



Program5.pl (Verwendung von Listen: r(X,Y) geht X in der Liste Y voran?)



Program6.pl (Modifikation der Datenbank zur Laufzeit: assert, retract)– ?- add_between(b1, a2, a3) funktioniert!

– Danach:

– ?- remove_between(b1, a2, a3) funktioniert NICHT (Datenbank wird zu Beginn wieder mit den URSPRÜNGLICHEN Fakten geladen, d.h. ohne b1!!)

Program6.pl (ein Element am Anfang einfügen: add_first)



Program7.pl (Einsatz des Prädikats not)– Fragen wie ?-tier(hund) sind möglich, aber auch

„Generatoren“ wie– ?-tier(X),write(X),write(" ist ein Tier"),nl.

Program7a.pl – Fragen wie ?-tier(hund) funktionieren, aber– ?-tier(X),write(X),write(" ist ein Tier"),nl. sind nun NICHT

MÖGLICH (im Prädikat not können keine Variablen gebunden werden!!)

Program7b.pl– Andere Möglichkeiten not darzustellen, Generatoren nicht

darstellbar!



Program8.pl (einfache Arten der Wissensrepräsentation)– ?- X(lassie), write(X), nl. in SWI-Prolog leider nicht möglich!

Program9.pl (Mitarbeiterdatenbank)

Program10.pl (Kundendatenbank)– Es wird nur ein relevanter Kunde gefunden

Program10a.pl– Nun werden alle relevanten Kunden gefunden!

Program10b.pro– Wie Program10a.pro, aber ohne „No“ am Ende



Program11.pl (Prädikate zur Listenverarbeitung)– ?- member(c,[a,b,c,d]).– ?- member(X,[a,b,c,d]),write(X),nl,fail.– ?- append([1,2,3],[4,5],X),write_list(X).– ?- append([1,2,3],X,[1,2,3,4,5]),write_list(X).

Program11.pl (vollständige Zerlegung einer Liste in zwei Teil-Listen mittels append)



Program12.pl (verschachtelte Listen)

Program13.pl (Anwendung verschachtelter Listen: Einkaufsbummel)

Program14.pl (Arithmetische Listen- und andere Prädikate)



Program15.pl (Darstellung eines semantischen Netzwerks zum Liebesleben)– ?-likes(mary,john).– ?-likes(mary,X), write(X), nl.– ?-likes(X,Y), dislikes(Y,X), write(‘Poor ‘), write(X), nl.– ?-likes(X,Y), dislikes(Y,X), write(‘Poor ‘), write(X), nl, fail.

– FRAGE: Wer wird von Anne nicht gemocht und beneidet jemanden, den Anne mag?



Program15a.pl – Allgemeingültige Formulierung von envies/2.

Program15b.pl (Strukturiertes Wissen mit verschachtelten Termen)– ?-knows(john,X),write(X),nl.– ?-knows(john,likes(anne,X)),write(X),nl.– ?-is_a(john,person).– ?-is_a(john,man).



Program16.pl (Klassifizierte Fähigkeiten)– ?-can(dolphin,swim).– Modifizieren, damit das stimmt (auch alle anderen Fakten

ergänzen!)

– FRAGE: Ein neues Säugetier wurde entdeckt – das Quirn. Was wissen wir alles über das Quirn? Woher wissen wir es? Wie sieht eine Prolog-Datenbank dazu aus?



Program16a.pl selbst erstellen nach folgenden Regeln:– If a patient is sweating and has high temperature then the

patient has a fever.– If the patient has a fever and a cough then the patient has

the flu.– If the patient has a rash and a fever then the patient has

chicken-pox.– If the patient has the flu then go to bed and take aspirin.– If the patient has chicken-pox then keep away from other

people and go to bed.



Anwendung dieser Regeln von links nach rechts forward chaining (aus Indizien werden Schlüsse gezogen)

Zweite Möglichkeit: die Regeln von rechts nach links anwenden Vermutungen werden (durch Fakten) bewiesen = backward chaining

Die meisten Expertensysteme wenden beide Techniken an.


PROgramming in LOGicProgram17.pl (Infektionsgefahr!)– ?-infect(john,X).– ?-infect(X,Y).– ?-infect(mary,X).– Im Trace-Modus beobachten!

Program18.pl (Expertensystem zur Tiererkennung)– Wird mittels ?-recognize(animal). gestartet

Program18.pl (Erweiterte Version – erklärt die Schlußfolgerung)– Wo muß der Term explain(List) eingebaut

werden?


PROgramming in LOGicProlog-Versionen im Internet– SWI-Prolog: http://www.swi-prolog.org/– Strawberry Prolog: http://www.dobrev.com/– Trinc-Prolog: http://www.trinc-prolog.com/– BinProlog: http://www.binnetcorp.com/– Visual Prolog: http://www.visual-prolog.com/– Amzi Prolog: http://www.amzi.com/– Arity Prolog: http://www.arity.com/– LPA Prolog: http://www.lpa.co.uk/

Ausführlichere Liste:– Logic Programming Archive: http://archive.comlab.ox.ac.uk/logic-prog.html

Documents

PROgramming in LOGic