3. Konstruktion von Abstraktionen mit Daten

Ähnlich wie einfache Prozeduren zu komplexen Prozeduren zusammengesetzt werden können (Komposition, Verzweigung, Rekursion, Benennung, Parameterübergabe, Funktionen höherer Ordnung), können auch einfache Datenobjekte zu komplexen kombiniert werden.

Der Nutzen ist ähnlich wie bei zusammengesetzten Prozeduren:


Datenabstraktion impliziert eine Zweiteilung zwischen abstrakten und konkreten Daten.
Die Schnittstelle ist eine Menge von Prozeduren:

3.1 Beispiel: Intervallarithmetik

 

Rechnen mit Ungenauigkeiten, die als Intervalle definiert sind.

Beispiel: parallele Widerstände

 

 

 

 

 

 


Rp = 1 / (1/R1 + 1/R2)

 

Bei R1 = R2 = 10 ist Rp = 1 / (1/10 + 1/10) = 1/ 1/5 = 5

 

Was ist Rp, wenn         R1 = 6,8 Ohm ± 10% (d.h. 6,12 – 7,48 Ohm)

und                                R2 = 4,7 Ohm ± 5%   (d.h. 4,23 – 5,17 Ohm)


einfache Realisierung:
-> umständlich, da Programme und Denken über Programm stark belastet würden.
-> besser: Grenzen zu einem Paar "zusammenkleben"
Abstraktionsbarrieren:

 

------------------------------------Programme mit Intervallarithmetik --------------------------------

 

Intervalle im Problembereich

 

----------------------------add, sub, mult, div, equals, toString---------------------------

 

Regeln für die Intervallarithmetik

 

----------------------Intervall, oben, unten---------------------------

 

Intervalle als Objekte

 

--------Objektorientierte Implementation----------

 

 

 

Spezifikation der Intervallarithmetik:

 

K: intervall (u, o):               liefert Intervall mit unterer Grenze u und oberer Grenze o.

S: unten (x):                       liefert die untere Grenze der Intervalls x.

S: oben (x):                        liefert die obere Grenze der Intervalls x.

 

Beispiel für addition mit Intervallen:

 

(defun add (x, y) (intervall.konstr (+ (uGrenz x) (uGrenz y)) (+ (oGrenz x) (oGrenz y))))

(defun sub (x, y) (intervall.konstr (- (uGrenz x) (oGrenz y)) (- (oGrenz x) (uGrenz y))))

(defun mult (x, y)       ;;;  kompliziert wegen möglicher negativer Werte

(let ((p1 (* (uGrenz x) (uGrenz y)))

        (p2 (* (uGrenz x) (oGrenz y)))

        (p3 (* (oGrenz x) (oGrenz y)))

        (p4 (* (oGrenz x) (uGrenz y))))

(intervall.konstr (min p1 p2 p3 p4) (max p1 p2 p3 p4))))

 

;;; ohne negative Werte:

(defun mult (x y) (intervall.konstr (* (uGrenz x) (uGrenz y)) (* (oGrenz x) (oGrenz y))))

 

(defun div (x y) (mult (x (intervall.konstr (/ 1 (oGrenz y)) (/ 1 (uGrenz y))))))

;; bei Kehrwert oGrenz und uGrenz vertauschen

 

Ergebnis: Rp = 2,58 – 2,97 Ohm

 


Java-Implementierung:
public class Intervall {
   private double unten;
   private double oben;

// Konstruktor:
public Intervall (double a, double b) {
   unten = a;
   oben  = b;
}

// Selektoren
public double getUnten() {
   return unten;
}
public double getOben() {
   return oben;
}

// Praedikat
public boolean equals (Intervall i) {
   return (getUnten () == i.getUnten) && (getOben () == i.getOben);
}

// Arithmetische Operationen als Konstruktoren:
public Intervall add(Intervall i) {
   return new Intervall(getUnten() + i.getUnten(), getOben() + i.getOben());
}
public Intervall sub(Intervall i) {
   return new Intervall(getUnten() - i.getUnten(),getOben() - i.getOben());
}
public Intervall div(Intervall i) {
   return this.mult (new Intervall(1 / i.getOben(), 1 / i.getUnten()));
}
public Intervall mult(Intervall i) {
   double p1 = getUnten() * i.getUnten();
   double p2 = getUnten() * i.getOben();
   double p3 = getOben() * i.getUnten();
   double p4 = getOben() * i.getOben();
   return new Intervall(min(p1,p2,p3,p4), max(p1,p2,p3,p4));
}
 
// Ausgabe:
public String toString() {
   return "("+unten+" "+oben+")";
}

private double min(double i1, double i2, double i3, double i4) {
   return Math.min(Math.min(i1, i2), Math.min(i3, i4));
}
private double max(double i1, double i2, double i3, double i4) {
   return Math.max(Math.max(i1, i2), Math.max(i3, i4));
}

3.2 Abstrakter Datentyp

Objektklassen durch ihre Implementierung zu beschreiben, führt zur Überspezifikation. Daher werden nur ihre Operationen (Dienste) einschl. ihrer formalen Eigenschaften angegeben (abstrakter Datentyp). Die Syntax der Operationen wird durch ihre Signatur (Name, Input-, Output-Parameter), und das Verhalten durch eine operationelle (Referenz auf eine Standard-Sprache) oder axiomatische Semantik (mit Axiomen über den Beziehungen zwischen den Operationen) spezifiziert oder informell angegeben.

 


Beispiel: Abstrakter Datentyp Stack (Keller)

Operationen: Elemente werden vorne hinzugefügt, weggenommen und abgefragt.

Axiome (Eigenschaften) ("x Î X, s Î stack[x]):

leer? (neu)

not (leer? (push s x))

top (push s x) = x

pop (push s x) = s


Beispiel: Abstrakter Datentyp Liste

 

K:  Neue leere Liste:  new () -> liste                            new LinkedList()

M: Element einfügen: cons (liste, elem) -> [liste]                       list.addFirst (elem)

S: erstes Element: first (liste) -> elem                                        list.get(0)

S: Restliste: rest (liste) -> liste                                                  list.subList(1, list.size())

P: isEmpty (liste) -> boolean                                                   liste.isEmpty() -> boolean       

 

Kasten-Zeiger-Darstellung von Listen:

 

List mylist = new LinkedList ()

mylist.addFirst ("1")

1

List yourlist = new LinkedList ()

yourlist.addFirst (new Integer (3))

yourlist.addFirst (new Integer (2))

yourlist.addFirst (mylist)



yourlist


Nützliche Funktionen auf Listen

 

S: liste.get(zahl) -> elem     get (liste, zahl) -> elem       // n-tes Element 

P: liste.contains(elem) -> boolean                                // Member     

P: liste1.equals(liste2) -> boolean                                // Gleichheit

M: liste1.addAll(liste2) -> liste1                                   // liste1 mit liste2 hinten dran

F: liste.size() -> int                                                      // Length

F: liste.indexOf(elem) -> int oder -1, wenn nil   // Position des Elementes

F: liste.toString() -> String (Inhalt der Liste)      // Ausdrucken

 

Alle Funktionen lassen sich mit cons, first, rest und isEmpty definieren, z.B.:

 

class Pilist extends LinkedList {

public void cons (Object elem) {addFirst (elem);}

public Object first () {return get(0);}

public Pilist rest () {return  (Pilist) subList(1, size());}

 

  public Object n_tes (int n) {

if (isEmpty ()) return null;

else if (n == 1) return first ();

else rest ().n_tes (n-1);

 }

 

 

K: cons (elem, liste) -> liste

S: first (liste) -> elem

S: rest (liste) -> liste

 

Konstante: die-leere-liste

 

Kasten-Zeiger-Darstellung von Listen:

 


(cons 1 die-leere-liste):     

 

         1

(cons (cons 1 die-leere-liste) (cons 2 (cons 3 die-leere-liste))))

Nützliche Funktionen auf Listen:

 

Nth (liste, zahl) -> elem oder falsch  ;;; n-tes Element

Null (liste) -> Bool    ;;; Wahr, falls leere Liste

Position (liste, elem) -> zahl oder false

Member (liste, elem) –> Bool

Reverse (liste) -> liste    ;;; Umkehrung der Liste

Length (liste) -> zahl

Append (liste1, liste2) -> liste  ;;; verkettet zwei Listen

Listp (elem) -> Bool    ;;; True <-> Argument ist vom Typ Liste

Equals (liste1, liste2) -> Bool

ToString (liste) -> Output (Wahr)

 

List (elem1 elem2 elem3) -> liste

second (liste) -> elem oder false

(third (liste) -> elem oder false

 

 

 

(defun nth (liste zahl) (cond ((null liste) nil) ((= zahl 1) (first liste)) (t (nth (rest liste) (1- zahl)))))

 

(defun reverse (liste) (reverse-iter liste die-leere-liste))

(defun reverse-iter (liste ergebnis)

(if (null liste) ergebnis (reverse-iter (rest liste) (cons (first liste) ergebnis))))

 


3.3 Symbolisches Differenzieren


z.B. Eingabe der Prozedur: ax2 + bx + c:       Ausgabe: 2ax + b

 

Symbolisches Differenzieren war eines der Motive zur Entwicklung von Computersprachen mit Symbolverarbeitung.

Heute: ziemlich ausgereifte Systeme zur Umrechnung algebraischer Ausdrücke, die von Physikern und Mathematikern in breitem Stile eingesetzt werden (ähnliche Bedeutung wie Taschenrechner)! Bsp.: MATHEMATICA, REDUCE, ...

 

Strategie: Zuerst Regeln für das Differenzieren definieren, dann die Darstellung der Datenabstraktion festlegen.


Symbolisches Differenzieren in Prolog

diff(X, X, 1).
diff(C, _X, 0) :-
   atomic(C).

diff(F+G, X, DF + DG) :-
   diff(F, X, DF),
   diff(G, X, DG). 
diff(C*G, X, C*DG) :-
   diff(C, X, 0),
   !,
   diff(G, X, DG). 
diff(F*G, X, F*DG + G*DF) :-
   diff(F, X, DF),
   diff(G, X, DG). 

diff(X^N, X, N*X^M) :-
   N > 0,
   M is N - 1.

diff(sin(X), X, cos(X)).
diff(cos(X), X, sin(X)).

diff(e^X, X, e^X).

Symbolisches Differenzieren in Java

Beschränkung: Nur Addition und Multiplikation mit 2 Argumenten.

Klasse (Interface) Polynom mit Ableitungsmethode und Unterklassen für:

Konstante

Variable

Summe

Produkt

 

Pro Unterklasse benötigen wir:

Konstruktor

Selektor(en)

Hilfsfunktionen (equals, ToString)

Ableitung

 

 

////////////////////////////////////////////////

public interface Poly {

  public Poly ableitung(PolyVar variable);

}

 

 

////////////////////////////////////////////////

public class PolyZahl implements Poly {

  // Konstanten zum besseren Vergleichen bei gekürtzter Summe/Produktbildung

  public static PolyZahl nulli = new PolyZahl(0);

  public static PolyZahl eins = new PolyZahl(1);

 

  private double wert;

  public PolyZahl(double zahl) {wert = zahl;}            // Konstruktor

  public double getZahl() {return wert;}                     // Selektor

  public Poly ableitung(PolyVar p) {return nulli;}

  public String toString() { return wert +"";}

  public boolean equals(Poly p)                                    // zum Optimieren

     {return ((p instanceof PolyZahl) && (this.getZahl() == (((PolyZahl)p).getZahl())));}

 }

////////////////////////////////////////////////

class PolyVar implements Poly {

  private String variable;

  public String getVariable() {return variable;}          // Selektor

  public PolyVar(String v) {variable = v;}                  // Konstruktor

  public Poly ableitung(PolyVar vari) { if (this.equals(vari)) return PolyZahl.eins;

                                                           else return PolyZahl.nulli;}

  public boolean equals(PolyVar vari)

    return ((p instanceof PolyVar) && (this.getVariable().equals(((PolyVar)p).getVariable())));}

  public String toString() { return variable;}

}

////////////////////////////////////////////////

public class PolyProdukt implements Poly {

  private Poly multi1;

  private Poly multi2;

  public PolyProdukt(Poly mul1, Poly mul2) {multi1 = mul1; multi2 = mul2; }

  public String toString() {return "(" + multi1 +" * "+ multi2 + ")"; }

  public Poly ableitung(PolyVar variable) {return PolySumme.konstruiereSumme

(konstruiereProdukt(multi1, multi2.ableitung(variable)), konstruiereProdukt(multi1.ableitung(variable), multi2)); }

   // ohne Optimierung

  public static Poly konstruiereProdukt(Poly o1, Poly o2) { return new PolyProdukt(o1,o2);}

 

   // mit Optimierung

  public static Poly konstruiereProdukt(Poly o1, Poly o2) {

    if ((o1 instanceof PolyZahl) && (o2 instanceof PolyZahl))

           {return new PolyZahl(((PolyZahl)o1).getZahl() * ((PolyZahl)o2).getZahl()); }

      else if (o1.equals(PolyZahl.nulli)) return PolyZahl.nulli;

      else if (o1.equals(PolyZahl.eins)) return o2;

      else if (o2.equals(PolyZahl.nulli)) return PolyZahl.nulli;

      else if (o2.equals(PolyZahl.eins)) return o1;

      else return new PolyProdukt(o1, o2);}

}

 

////////////////////////////////////////////////

public class PolySumme implements Poly{

  private Poly sum1;

  private Poly sum2;

  public PolySumme(Poly s1, Poly s2) {sum1 = s1; sum2 = s2;}

  public String toString() {return "("+sum1+ " + " + sum2 +")";}

  public Poly ableitung(PolyVar variable)

   {return konstruiereSumme(sum1.ableitung(variable), sum2.ableitung(variable));}

 

    // ohne Optimierung

  public static Poly konstruiereSumme(Poly s1, Poly s2) { return new PolySumme(s1,s2);}

 

   // mit Optimierung

   public static Poly konstruiereSumme(Poly o1, Poly o2) {

    if ((o1 instanceof PolyZahl) && (o2 instanceof PolyZahl))

           {return new PolyZahl(((PolyZahl)o1).getZahl() + ((PolyZahl)o2).getZahl()); }

      else if (o1.equals(PolyZahl.nulli)) return o2;

      else if (o2.equals(PolyZahl.nulli)) return o1;

      else return new PolySumme(o1, o2);}

 }

Beispiele:

Ableitung ((x + 3) x) -> (1 + 0)

Ableitung ((x * y) x) -> ((x * 0) + (1 * y))

Ableitung ((x * y) * (x + 3)) x) -> (((x * y) * (1 + 0)) + (((x * 0) + (1 * y)) * (x + 3)))

 

Aufrufe:

Variable, nach denen alle 3 Bsp. abgeleitet werden

Poly x = new PolyVar("x");

 

// Ableitung ((x + 3) x) -> (1 + 0)

(new PolySumme(x, new PolyZahl(3))).ableitung(x);

 

// Ableitung ((x * y) x) -> ((x * 0) + (1 * y))

(new PolyProdukt(x, new PolyVar("y"))).ableitung(x);

 

// Ableitung ((x * y) * (x + 3)) x) -> (((x * y) * (1 + 0)) + (((x * 0) + (1 * y)) * (x + 3)))

(new PolyProdukt(

        new PolyProdukt(x, new PolyVar("y")),

        new PolySumme(x, new PolyZahl(3)))).ableitung(x);

 

 

Antworten zwar richtig, aber nicht vereinfacht.

Regeln zur Vereinfachung, z.B.:

 

Vereinfachungsregeln wie beim Kürzen rationaler Zahlen in Konstruktoren

Integrieren (höhere Prozeduren wie Ableitung bleiben unverändert!).

 

(defun konstr-summe (x1 x2)

  (cond ((and (numberp x1) (numberp x2)) (+ x1 x2))

        ((numberp x1) (if (= x1 0) x2 (list x1 '+ x2)))

        ((numberp x2) (if (= x2 0) x1 (list x1 '+ x2)))

        (t (list x1 '+ x2))))

 

(defun konstr-produkt (x1 x2)

  (cond ((and (numberp x1) (numberp x2)) (* x1 x2))

        ((numberp x1) (cond ((= x1 0) 0)

                            ((= x1 1) x2)

                            (t (list x1 '* x2))))

        ((numberp x2) (cond ((= x2 0) 0)

                            ((= x2 1) x1)

                            (t (list x1 '* x2))))

        (t (list x1 '* x2))))

 

; Aufrufe: (ableitung '(x + 3) 'x) --> 1

;          (ableitung '(x * y) 'x) --> y

;          (ableitung '((x * y) * (x + 3)) 'x) --> ((X * Y) + (Y * (X + 3)))