Andreas Podelski Fachbereich 14 – Informatik Universität des Saarlandes, Max-Planck-Institut für Informatik

[figure: I N F O R M A T I K]

Programmiersprachen (WS 1996/97)

16. Januar 1997  Übungsblatt 11  Abdelwaheb Ayari Hubert Baumeister

Aufgabe 1: (3 Punkte) Begründe, warum es Sinn macht, daß in Java keine Klassenmethoden in Interfaces deklariert werden können. Folgende Deklaration ist zum Beispiel nicht möglich:

interface I {static void f(String s);}

Gib ein Beispiel dazu an und erläutere es.

Aufgabe 2: (7 Punkte) Gegeben ist eine Menge von Termgleichungen E = {s_{1} = t_{1}, …, s_{n} = t_{n}}. Gesucht ist eine Substitution σ, so daß s_{i}σ = t_{i}σ ist für alle i von 1 bis n. Hinweis: Implementiere den Unifikationsalgorithmus vom siebten Übungsblatt.

1. Implementiere eine Klassenhierarchie, die Terme und Variablen mit den folgenden Methoden implementiert.

         static Term Function(String s,Term[] args);  static Var Var(String s);
         String funct();                              boolean isVar();
         int  arity();                                boolean occurs(Var v);
         Term replace(Var x, Term t2);                Term[] args();
         boolean equals(Term t);

2. Schreibe eine Klassenhierarchie, die Substitutionen mit den folgenden Methoden und Konstanten implementiert.

         static Substitution Substitution(Var x, Term t);   static Substitution Empty;
         Substitution compose(Substitution s);              Substitution applyTo(Term s);

3. Implementiere eine Klasse Unify mit der Methode:

     Substitution solve(Equation[] s);

Die Klasse Equation implementiert Gleichungen. Unter anderem sollen Gleichungen die Nachricht solve() verstehen, die eine Substitution liefert, die die Gleichungen löst.

Teste das Lösungsverfahren an folgenden Gleichungssystemen (x, y, z sind dabei Variablen und a und b nullstellige Funktionen (= Konstanten)):

{(f(x, a), f(a, x))} {(f(x, a), f(b, y))} {(f(x, a), f(b, x))} {(x, y)} {(x, x)}

{(f(a, b), h(a, b))} {(g(x), x)} {(f(g(y), y), f(x, g(z)))} {(f(x, y), f(z, g(g(y))))}