Einf. in das symbolische Programmieren      CIS, SS 2002, H.Leiss
=================================================================

Wer Probleme bei der Bedienung von Emacs und Prolog hat, sollte sich
bei mir (leiss@cis.uni-muenchen.de, Raum B 1.07) oder Alexander Voelz
(voeltz@informatik.uni-muenchen.de) melden!


Abgabe: Mittwoch, 22.5.2002, in der Vorlesung
----------------------------------------------


Aufgabe 5                                         (5 + 7 Punkte)
---------
Benutze die Definitionen von 

       Match(A:Atom,B:Atom)    und    Unify(A:Term,B:Term),

um die folgende Beispiele zu ueberpruefen:

a) Zeige, dass  

       Match(add(X,0,X),add(s(s(0)),s(0),Z)) = No

(Bem.: Deshalb ist auf Folie 24 der Vorlesung nicht die erste der 
 beiden Klauseln

       add(X,0,X) :- nat(X).
       add(X,s(Y),s(Z)) :- add(X,Y,Z).

 benutzt worden, um das Ziel  ?- add(s(s(0)),s(0),Z)  zu vereinfachen.)

Beschreibe ausfuehrlich, wie es zu dieser Antwort kommmt: 
welche Faelle der Definitionen von Match(A:Atom,B:Atom) (Folie 20) 
und Unify(A:Term,B:Term) (Folie 23) werden jeweils benutzt?

b) Zeige ebenso, wie die Berechnung von 

       Unify(f(X,g(h(Y))), f(h(Z),g(X)))

   verlaeuft und was das Ergebnis ist. 


Aufgabe 6                                                 (8 Punkte)
---------
In Prolog werden zwei Terme A und B unifiziert, wenn man die Anfrage

   ?- A = B.

stellt. **Aber** Prolog laesst den Occur-Check weg, implementiert also
die Unifikation nicht korrekt. (Der Programmierer muss darauf achten, 
dass das bei seinen Programmen nichts am Ergebnis ausmacht!)

a) Was ist die Antwort von  Unify(X,f(X))  und was antwortet
   SWI-Prolog auf  

   1) ?- X = f(X). 

   Waere die Unifikation richtig implementiert, muessten die Ziele

   1)   ?- X = f(X,X).   
   
   2)   ?- X = f(X,X), Y = f(Y,Y), X = Y.

   scheitern. Was antwortet SWI-Prolog?

b) SWI-Prolog verfuegt aber neben =/2 auch ueber eine richtig 
   implementierte Unifikation. Finden Sie mit

      ?- apropos(occurs).

   heraus, wie diese heisst und testen Sie damit, ob die Beispiele
   unter 1) - 3) die richtigen Antworten liefern.

c) Vergleichen Sie Ihr Ergebnis zu Aufgabe 5 b) mit dem, was Prolog 
   zur entsprechenden Anfrage antwortet.


Freiwillige Aufgabe                                       (5 Punkte)
-------------------
Beim Matchen und Unifizieren werden A und B wiederholt aktualisiert,
indem die gefundenen Substitutionen darauf angewendet werden.

Sei S = unify(A,B). Warum ist SS, also compose(S,S), dasselbe wie S,
wenn man es auf Variable aus A oder B anwendet?