____________________________________________________________________________ #on("b")##on ("u")# #center#Betriebssystem E U M E L #off ("u")# #center#Prolog #off("b")# #center#Lizenzfreie Software der #on ("b")# #center#Gesellschaft für Mathematik und Datenverarbeitung mbH, #center#5205 Sankt Augustin #off("b")# #center#Die Nutzung der Software ist nur im Schul- und Hochschulbereich für #center#nichtkommerzielle Zwecke gestattet. #center#Gewährleistung und Haftung werden ausgeschlossen ____________________________________________________________________________ #page# Dr.P.Heyderhoff 12.03.1987 GMD.F2.G2 E L A N - P R O L O G _____________________ (Die Fachsprache der künstlichen Intelligenz) #on("u")#Benutzungsanleitung und technische Beschreibung#off("u")# Elan-Prolog ist eine Computersprache der fünften Generation, die für die Praxis der Programmierung und die Lehre in Informatik eine neue Dimension erschließt. Für den professionellen Programmierer eröffnet sie neue Möglichkeiten, mächtige Anwendungen, wie Expertensysteme und andere neuartige Systeme der Wissensverarbeitung zu entwickeln. Elan-Prolog unterscheidet sich grundsätzlich von üblichen konventionellen Programmiersprachen. In Sprachen wie Elan und Pascal muß der Programmierer genau angeben, wie ein gewünschtes Ergebnis errechnet werden soll. Um was es sich dabei handelt, steht bestenfalls dann in der Dokumentation. Ganz anders ist es in Prolog. PROLOG steht für PROgrammieren in LOgik und basiert auf dem Prädikaten-Kalkül, der bekanntesten Form der formalen Logik. Also in Prolog schreibt der Programmierer hin, worin das Problem besteht. Er bedient sich dabei dieser formalen Logik. Prolog versucht dann eine Lösung zu finden. Der Lösungsweg ist dabei im Programm nicht vorgeschrieben. Das entlastet den Programmierer, und er kann seine ganze Kraft auf die logische Beschreibung des Problems konzentrieren. Elan-Prolog ist ein interpretatives System, das voll kompatibel ist mit dem Edinburgh Standard Prolog und in in komfortabler Weise in das Betriebssystem Eumel eingebettet ist. Eigenschaftes von Elan-Prolog: - Syntax gemäß dem Edinburgh Standard Prolog nach Clocksin-Mellish - Interpretierendes System mit inkrementellem Einpass-Compiler - Interaktiver Mehrfenster-Texteditor des Eumelsystems - Zugriff auf Elan-Prozeduren als Prolog-Regeln - Geschwindigkeit ca. 100 LIPS auf IBM/PC-XT - optionale dynamische Ablaufverfolgung - Erklärungskomponente - Eingabe und Ausgabe von Prolog-Ausdrücken und Klartext - Programmiert und dokumentiert in ELAN (über 2000 Zeilen) - daher besonders für den Informatik-Unterricht geeignet #page# #on("u")#Beschränkungen des Elan-Prolog:#off("u")# Folgende Beschränkungen gelten für die Implementierung von Elan-Prolog im Eumel-Systems: - Maximal 16000 Fakten und Regeln - Maximal 16000 Terme zur Konstruktion von Ausdrücken, Listen und Regeln - Maximal 800 Variablenbindungen - Maximal 800 Einträge im Beweisbaum - Maximal 4000 Bezeichner für Atome und Variablen - Maximal 16000 Buchstaben für alle Bezeichner zusammen Wie sieht ein Prolog-Programm aus? Ein Prolog-Programm besteht aus - Fakten über Objekte und ihre Beziehungen - Regeln über Objekte und ihre Beziehungen und besonders wichtig: - Der Benutzer kann Prolog über die Fakten und Regeln ausfragen. Fakten aus einer Wissensbasis, nämlich dem Prolog-Programm, sind z.B.: enthaelt (wisky, aethanol). Das wird gelesen als: "Wisky enthält Aethanol.". Grundzüge der sehr einfachen Syntax lassen sich hieran erklären. Ein Faktum wird geschrieben wie in diesem Beispiel: - Erst kommt der Name der Relation, geschrieben wie ein Elan-Name in kleinen Buchstaben. - Dann folgt in runden Klammern und durch Kommata getrennt eine Liste von Objektnamen. - Zum Schluß steht ein Punkt. Regeln sind Problembeschreibungen in der Form von logischen Ausdrücken der symbolischen Logik, wie z.B. die folgende Regel: bewirkt (A, B, kopfschmerz) :- enthaelt (A, aethanol), enthaelt (B, aspirin ). Das wird gelesen als: "Wenn man eine Droge A, die Aethanol enthält, und eine Droge B, die Aspirin enthält gleichzeitig einnimmt, dann bewirkt das Kopfschmerzen." Wie man sieht werden logische Variablen mit großen Buchstaben (wie Elan-Operatoren) geschrieben. Das Zeichen ":-" steht für das logische Wenn, und das Komma(",") für die logische Konjunktion. Die logische Disjunktion wird durch Semikolon(";") ausgedrückt. #page# Neben der hiermit vorgestellten Prefix-Schreibweise für Relationen gibt es in ELAN-Prolog auch noch eine Infix-Schreibweise für zweistellige Relationen. Hierbei werden die Relationen als Infix-Operatoren in großen Buchstaben geschrieben (wie in ELAN) und zwischen die beiden Operanden gesetzt. Als Operatoren sind auch die in Elan üblichen Operatoren ( +, -, *, /, MOD, =, <, >, <=, >=, <> ) zulässig. In Infixausdrücken (wie z.B. 2+3*4) gelten die bekannten Vorrangregeln. Auch Klammern sind zulässig. Selbstdefinierte Operatoren haben niedrigste Priorität. Obiges Beispiel in Infix-Schreibweise: wisky ENTHAELT aethanol. bewirkt (A, B, kopfschmerz) :- A ENTHAELT aethanol, B ENTHAELT aspirin. Objekte in Prolog können Atome oder Listen sein. Für Atome gibt es zwei Schreibweisen: - genau so wie Elan-Bezeichner, also bestehend aus kleinen Buchstaben und Blanks. Dabei werden die Blanks eliminiert. - genauso wie Elan-Texte, nämlich in Gänsefüßchen eingeschlossen. Für Listen von Objekten gibt es wiederrum zwei Schreibweisen, wie folgende zwei unterschiedlichen Notationen des gleichen Beispiels zeigen: - [ das, ist, [ zum, beispiel ], eine, liste ] - [ das, ist, [ zum | [ beispiel | [] ] ], eine, liste ] Im zweiten Fall ist die als drittes Element in der Gesamtlisten enthaltene Teilliste mit dem Konstruktor "|" und der leeren Liste "[]" zusammengesetzt. Die Grundoperationen, die aus der Programmiersprache LISP bekannt sind, können als Prolog-Fakten unmittelbar wie folgt definiert werden: eq (X, X). head ([X|Y], X). tail ([X|Y], Y). cons (X, Y, [X|Y]). #page# #on("u")#Standard - Operatoren von Elan-Prolog:#off("u")# Im System sind nur ganz wenige Standardoperatoren eingebaut. Es sind die folgenden Fakten: - ! . der CUT-Operator schaltet des Backtracking ab. - bye. beendet die prolog Anwendung. - listing. zeigt alle insertierten Regeln. - listing (X). zeigt alle insertierten Regeln über X. - call (X). X wird ausgeführt. - write (X). das an X gebundenen Prolog-Objekts wird ausgegeben, writeq (X). und wenn nicht eindeutig, gequotet, put (X). das Zeichen, dessen ASCII-Code X ist wird ausgegeben, name (X,[Y]). unifiziert das Atom X mit der Liste seiner Buchstaben. - read (X). ein Objekt wird gelesen und an die Variable gebunden. get0 (X). das nächste Zeichen wird gelesen, get (X). das nächste druckbare Zeichen wird gelesen, - X = Y . Die an X und Y gebundenen Objekte sind gleich, X <> Y . sie sind ungleich, X <= Y . sie sind kleiner oder gleich, X == Y . sie sind wörtlich gleich, X =.. [F|A] . X ist der Term mit Funktor F und Argumentliste A. - X + Y . sie sollen addiert, X - Y . subtrahiert, X * Y . multipliziert, X / Y . dividiert, X MOD Y . der Divisionsrest soll ermittelt werden, die Auswertung geschieht durch den 'is'-Operators. - X IS EXPR . Das Ergebnis des arithmetischen Ausdrucks EXPR wird gebildet und mit X unifiziert. - incr (X). der arithmetische Wert von X wird um eins erhöht. - assertz ([X]). insertiert die Regel X am Ende einfügend. asserta ([Χ]). insertiert die Regel X am Anfang einfügend. retract ([X]). entfernt die Regel X wieder. clause (X,[Y]). holt die Regel Y mit dem Kopf X aus der Knowledgebase. - functor (X,Y,Z) Y ist der Funktor von X und Z ist seine Arität. arg (X,Y,Z). Z ist das x-te Argument der Funktion Y. - elan (X). Ausführung der insertierten ELAN-Prozedur X elan (X,Y). Ausführung von X mit dem TEXT-CONST-Parameter Y - elan(trace,on). schaltet den dynamischen Ablaufverfolger ein und elan(trace,off) schaltet ihn wieder ab. - elan(consult,X) lädt das Prologprogramm aus der Datei namens X hinzu. elan(reconsult,X) ersetzt das Prologprogramm aus der Datei X. elan(abolish,X) entfernt alle Regeln mit dem Namen X. #page# #on("u")#Das Dialogverhalten von Elan-Prolog:#off("u")# Elan-Prolog wird, sobald es in das Eumel-System insertiert ist, als Prozedur mit dem Namen "prolog" und einem optionalen TEXT-Parameter aufgerufen. Der Textparameter enthält den Namen einer Datei, die ein Prolog-Programm enthält, das geladen werden soll. Fehlt der Parameter, wird, wie üblich, die zuletzt bearbeitete Datei genommen. Im Prolog-Dialog können später weitere Prolog-Programme mit der Prozedur namens "consult" hinzugeladen werden. Also einfachster Aufruf: prolog ("") Antwort: ?- Beispiel-Eingabe: 3 = 3 Antwort: yes ?- Eingabe: 4 = -5 Antwort: no ?- Besondere Dialogkommandos: ?- Eingabe: ? Antwort z.B.: 13.5 SEC ?- Eingabe: listing Antwort: { zeigt alle aktuell verfügbaren Regeln } ?- Eingabe: {ESCAPE} q Ausgabe: gib kommando: Eingabe: prolog again Ausgabe: ?- Eingabe: [sum, permute] {in eckigen Klammern!} { konsultiert diese beiden Dateien } Antwort z.B.: 25 rules inserted. ?- Eingabe: [-sum, -permute] { löscht und rekonsultiert aus diesen Dateien } Antwort z.B.: 25 rules inserted. Eingabe: {ESCAPE} {ESCAPE} Antwort: gib kommado: Elan-Eingabe z.B.: show ("standard") { zeigt die Datei dieses Namens } ?- Auf diese Weise können bequem Eumel-Kommandos gegeben werden. Die Umschaltung vom Prolog- zum Eumelmonitor-Betrieb erfolgt durch die Tasten {ESCAPE},{ESCAPE} und {RETURN}. Wie üblich ist das zuletzt verwendete Kommando auch im Prolog-Dialog mit dem Escapekommando "{ESCAPE} k" wiederzubekommen. Das Kommando "{ESCAPE} q" beendet den Dialog. #page# #on("u")#Ausprobieren der Prolog-Programmbeispiele:#off("u")# Zum Ausprobieren sind die Prologbeispiele "eq", "permute" und "mann" beigefügt. Beispiel: ?- Eingabe: [permute] {in eckigen Klammern!} Antwort: 5 rules inserted. ?- Eingabe: marquise(X) Antwort: beautiful marquise your beautiful eyes make me die of love Eingabe: {Semicolon} Antwort: your beautiful eyes beautiful marquise make me die of love { usw } Eingabe: {Return} Antwort: ?- Jede #on("u")#Eingabe von Semicolon#off("u")# liefert als Antwort die nächste Permutation. Wenn eine andere Taste gedrückt wird, bricht die Ausgabe weiterer Ergebnisse ab. #on("u")#Eingabe von Fragezeichen#off("u")# liefert neben der Angabe der benötigten Rechenzeit eine Erklärung der letzten Antwort durch Ausgabe aller zu dieser Antwort führenden Schlußfolgerungen. Dabei wird der Beweisbaum in Form einer Einrückstruktur dargestellt. Die Einrückung stellt die Erklärungstiefe dar. #on("u")#Benutzung von Prolog von Elan-Programmen aus#off("u")# Wenn man Prolog als Unterprogramm von Elan aus aufrufen will, geht man folgendermaßen vor: 1. Laden einer Wissensbasis, die in einer Datei namens z.B."permute" bereitsteht: push ("bye"13""); prolog ("permute"); 2. Abfragen an diese Wissensbasis: TEXT VAR query, answer; query:= "marquise (X)"; IF prolog ( query, answer) THEN put (answer) ELSE put ("NO") FI; In diesem Anwendungsbeispiel liefert die Ausgabeanweisung 'put (answer)': beautiful marquise your beatiful eyes make me die of love #page# #on("u")#Literatur:#off("u")# 1.) W.F.Clocksin, C.S.Mellish: Programming in Prolog Springer 1984 2.) M.H.van Emden: An interpreting algorithm for prolog programs in Implementations of Prolog, Ellis Herwood Ltd, 1984 3.) Alain Colmerauer: Prolog in 10 Figures Communications of the ACM December 1985 4.) J. Cohen: Describing Prolog by its Interpretation and Compilation Communications of the ACM December 1985 5.) Alain Colmerauer: Les system q ou un formalisme pour alalyser et synthetiser des phrases sur ordinateur. Intern.Rep. 43, Departement d'informatique. Universite de Montreal Sept. 1970 #page# (*************************************************************************) (* *) (* Elan-Prolog *) (* *) (* Programm-Beispiele: *) (* *) (****************** standard (nach Clocksin-Mellish) ********************) abolish (X) :- elan (abolish, X). append ([], X, X) :- !. append ([X|Y], Z, [X|W]) :- append (Y, Z, W). atom (X) :- functor (X, Y, 0). atomic (X) :- atom (X); integer (X). consult (X) :- elan (consult, X). end :- bye. fail :- []. findall (X, Y, Z) :- tell ("$$"), write ("("), findall (X,Y); write (")"), told, see ("$$"), read (Z), seen, elan (forget, "$$"). findall (X, Y) :- call (Y), writeq (X), write (","), []. integer (X) :- functor (X, Y, -1). listing (X). member (X, [X|Z]). member (X, [Y|Z]) :- member (X, Z). nl :- elan (line). non var (X) :- var (X), !, []; . not (X) :- call (X), !, []; . notrace :- elan (trace, off). reconsult (X) :- elan (reconsult, X). repeat. repeat :- repeat. see (X) :- elan (sysin, X). seen :- elan (sysin, ""). tab (X) :- tab(X,1). tab (X,Y) :- Y<=X, !, put (32), incr(Y), tab(X,Y);. tell (X) :- elan (sysout, X). told :- elan (sysout, ""). trace :- elan (trace, on). true. < (X, Y) :- <= (X, Y), <> (X, Y). > (X, Y) :- <= (Y, X). >= (X, Y) :- < (Y, X). #page# (**************************** sum ***********************************) suc (0, 1). suc (1, 2). suc (2, 3). suc (3, 4). suc (4, 5). suc (5, 6). suc (6, 7). suc (7, 8). suc (8, 9). sum (0, X, X). sum (X, Y, Z):- suc (V, X), sum (V, Y, W), suc (W, Z). plus (X, [0,0], X):- !. plus (X, Y, Z):- plus one (V, Y), plus (X, V, W), !, plus one (W, Z). plus one ([X, Y], [V, W]):- suc (Y, W), X = V, !; Y = 9, suc (X, V), W = 0. treereverse (X,Y):- rev (X,Y), !; rev (Y,X), !. rev ([], []). rev ([X|Y], Z):- X <> [H|T], rev (Y, W), !, append (W, [X], Z); rev (X, V), rev (Y, W), !, append (W, [V], Z). (**************************** permute ************************************) permute ([], []). permute ([E|X], Z):- permute (X, Y), insert (E, Y, Z). insert (E, X, [E|X]). insert (E, [F|X], [F|Y]):- insert (E, X, Y). marquise(RESULT):- permute (["beautiful marquise", "your beautiful eyes", "make me", "die", "of love" ], RESULT). (**************************** puzzle ************************************) {Solution: 9,5,6,7,0,8,2} puzzle:- repeat, permute ((9,8,7,6,5,2,0), SENDMORY), write (SENDMORY), puzzle (SENDMORY, SEND, MORE, MONEY), elan (line), write (SEND), write (+), write (MORE), write (=), write (MONEY). puzzle([S,E,N,D,O,R,Y], SEND, MORE, MONEY):- SEND IS ((S * 10 + E) * 10 + N) * 10 + D, MORE IS ((10 + O) * 10 + R) * 10 + E, MONEY IS (((10 + O) * 10 + N) * 10 + E) * 10 + Y, MONEY IS SEND + MORE. permute ([], []). permute ([E|X], Z):- permute (X, Y), insert (E, Y, Z). insert (E, X, [E|X]). insert (E, [F|X], [F|Y]):- insert (E, X, Y). repeat. repeat:- repeat. #page# (**************************** prieks ***********************************) ist priek (bo priek). ist priek (ki priek). ist priek (bla priek). WER GNASELT WEN :- population (B), member ([WEN, WER, _], B), bedingungen (B). WER KNAUDERT WEN:- population (B), member ([WER, _, WEN], B), bedingungen (B). population (B):- sind prieks (U, V, W), sind knauderarten (R, S, T), B = [ [drausla puemfe, U, R], [glessla puemfe, V, S], [hapla puemfe, W, T] ]. sind prieks (X,Y,Z):- ist priek (G), ist priek (H), H<>G, ist priek (I), I<>G, I<>H, !, permute ([G,H,I], [X,Y,Z]). sind knauderarten (X,Y,Z):- ist knauderart (G), ist knauderart (H), H<>G, ist knauderart (I), I<>G, I<>H, !, permute ([G,H,I],[X,Y,Z]). ist knauderart (an). ist knauderart (ab). ist knauderart (ueber). bedingungen (B):- not member ([hapla puemfe,ki priek,_],B) , not member ([hapla puemfe,_,ueber],B) , not member ([drausla puemfe,bo priek,_],B) , not member ([_,bo priek,ab],B) , noch ne bedingung (B) , weitere bedingungen (B) , !. weitere bedingungen (B):- not member([_,ki priek,ueber],B), not member([_,bo priek,ueber],B) ; member([drausla puemfe,_,an],B). noch ne bedingung (B):- not member ([drausla puemfe,ki priek,_],B) ; not member ([glessla puemfe,_,ueber],B). permute ([], []). permute (X, [Y|Z]):- delete (Y ,X, E), permute (E, Z). delete (X, [X|Z], Z). delete (X, [Y|Z], [Y|E]):- delete (X, Z, E). member (X, [X|Z]). member (X, [Y|Z]):- member (X, Z). not member (X, []). not member (X, [Y|Z]):- X <> Y, not member (X,Z). #page# (**************************** calc ************************************) { CALC evaluates arithmetic expressions with store } calc:- eval ([], RS), write (result store), write (RS), nl. eval (SI, SO):- read (CALC), nonvar (CALC), eval member (CALC, SI, SO). eval member (CALC, SI, SO):- member (CALC, [stop,end,bye,eof]), SO=SI; eval (CALC,I,SI,ST), write (I), eval (ST,SO); write (error in), write (CALC), nl, eval (SI, SO). eval (I, I, S, S):- integer (I). eval (N, I, S, S):- atom (N), eval atom (N, I, S). eval atom (N, I, S):- member (N=I, S); write ("error: Cell"), write (N), write("not found in store. 0 substituted."), nl, I=0. eval ( L+R,I,SI,SO):- eval (L,J,SI,ST), eval (R,K,ST,SO), I IS J+K. eval ( L-R,I,SI,SO):- eval (L,J,SI,ST), eval (R,K,ST,SO), I IS J-K. eval ( L*R,I,SI,SO):- eval (L,J,SI,ST), eval (R,K,ST,SO), I IS J*K. eval ( L/R,I,SI,SO):- eval (L,J,SI,ST), eval (R,K,ST,SO), I IS J/K. eval (N=O, I, SI, SO):- atom (N), eval (O,I,SI,ST), eval repl (N,I,ST,SO). eval repl (N, I, [], [=(N,I)]). eval repl (N, I, [=(N,_)|S], [=(N,I)|S]). eval repl (N, I, [=(M,J)|SI], [=(M,J)|SO]):- eval repl (N, I, SI, SO).