Praktische Informatik 1

Kapitel 7: Objektorientierung

Das Grundparadigma der objektorientierten Programmierung ist, dass ein Programm eine Ansammlung von Objekten ist, die miteinander interagieren. Jedes Objekt gehört zu einer bestimmten Klasse, und ist mit Datenfeldern und Methoden ausgerüstet. Der Wert der Datenfelder beschreibt den Zustand des Objektes, die Methoden dienen dazu, diesen Zustand zu verändern und mit anderen Objekten zu kommunizieren.

7.1 abstrakte Datentypen, Objekte, Klassen

Abstrakte Datentypen (ADT) sind ein Konzept aus der theoretischen Informatik, welches für die objektorientierte Programmierung eine ähnliche grundlegende Rolle spielt wie der
λ-Kalkül für die funktionale Programmierung oder die Turing-Maschine für die imperative Programmierung. Formal definieren wir den Begriff der Signatur: Eine Signatur Σ ist ein Paar, bestehend aus einer Grundmenge Μ und einer Menge von Operationen und Prädikaten Φ:

Σ = (Μ, Φ)

Zu jedem Element von Φ wird außerdem ihre Stelligkeit angegeben (zur Erinnerung: eine n-stellige Operation auf einer Menge Μ ist eine Funktion Μⁿ  Μ, eine n-stellige Operation auf einer Menge Μ ist eine Funktion Μⁿ  B)

Beispiel für eine Signatur ist also etwa : (N₀,0,s,+,*). Dabei sei 0 nullstellig, s einstellig, und + und * zweistellig.

0 : ® N₀

s : N₀ ® N₀

+: N₀×N₀ ® N₀

*: N₀×N₀ ® N₀
Es erhebt sich die Frage, welche Datenobjekte vom Typ N₀ es (mindestens) gibt. Unter der Termalgebra einer Signatur versteht man alle Objekte, die sich als Ergebnis wohlgeformter Terme auf Grund der Signatur darstellen lassen. Beispiele sind

• 
  0, s(0), s(s(0)), s(s(s(0))), …
  
• 
  0+0, (0+0)+0, …
  
• 
  s(0)+s(0), s(s(0))+s(s(s(0))), …
  
• 
  s(s(0))*(s(s(0))*(s(s(0)))), (0*s(0))+s(0), …
  

Die Objekte, die sich so darstellen lassen, nennt man die Termalgebra der Signatur.

Nicht alle Terme geben verschiedene Werte: z.B ist s(0)+s(0) gleich zu s(s(0))

(manchmal ist 1+1=2). Daher nimmt man eine Äquivalenzklassenbildung durch Angabe von (allgemeingültigen) Gesetzen vor:

• 
  x+0=x
  
• 
  x+s(y)=s(x+y)
  
• 
  x*0=0
  
• 
  x*s(y)=x+(x*y)
  

Damit lässt sich obige Aussage beweisen (1+1=2):

s(0)+s(0) =? s(s(0))
s(0)+s(0) = s(0 + s(0))

= s(s(0 + 0))

= s(s(0))
Ein abstrakter Datentyp (ADT) Τ besteht aus einer Signatur Σ und einer Menge von algebraischen Gesetzen (Gleichungen) Γ
Τ = (Σ, Γ)

Wenn die Gesetze ausschließlich aus Gleichungen zwischen Elementen von Μ bestehen, spricht man auch von einer Varietät (engl.: variety). Oft lässt man auch Bedingungen und Ungleichungen zu, dies ist aber eine Erweiterung des ursprünglichen Konzepts. Die Gesetze beschreiben, was für alle Objekte dieses Typs gelten soll.

Beispiel: ADT IntSet „Menge ganzer Zahlen“

Signatur:(IntSet, Æ, Î, Í, È, Ç, –)

Æ : ® IntSet

È : IntSet × IntSet ® IntSet

Î : Z × IntSet ® boolean

Gesetze: z.B.

x È y = y È x

x Ç Æ = Æ

…
Konkrete Mengen ganzer Zahlen (z.B. {1,2,3} oder {x | x%2=0} sind Instanzen des abstrakten Typs. Die Gesetze legen fest, was für alle Instanzen gelten soll. Beispiel:

{1,2,3} È {4,5} = {4,5} È {1,2,3}

{x | x%2=0} Ç Æ = Æ
Beispiel: Paare ganzer Zahlen Z´Z:

ADT ZZ = (ZZ, first, second, conc)

first, second : ZZ ® Z

conc : Z ´ Z ® ZZ

Gesetze:

first(conc(x,y))=x

second(conc(x,y))=y

Instanzen:

á3,-5ñ, á0,0ñ, á-12,12ñ, …

first(á3,0ñ)=3

conc(1,2)=á1,2ñ
Beispiel: Sequenzen (parametrisiert mit Basistyp s)
ADT seqásñ:( seqásñ, empty, isEmpty,
prefix, first, rest,
postfix, last, lead):

empty : ® seqásñ

isEmpty : seqásñ ® boolean
prefix: s × seqásñ ® seqásñ

first: seqásñ ® s

rest: seqásñ ® seqásñ
postfix: seqásñ × s ® seqásñ

last: seqásñ ® s

lead: seqásñ ® seqásñ
isEmpty(empty) = true

isEmpty(prefix(a,x)) = false

isEmpty(postfix(x,a)) = false
first(prefix(a,x))= a

rest(prefix(a,x))= x

last(postfix(x,a))= a

lead(postfix(x,a))= x

Eigenschaften
first(rest(prefix(a, prefix(b, empty)))) = b

rest(rest(prefix(a, prefix(b, empty)))) = empty

last(lead(postfix(a, postfix(b,empty)))) = b

…

prefix(a,empty) =? postfix(empty,a)

Typerweiterung

abgeleitete Operation +:

+: (seqásñ Ès) × (seqásñ Ès)® seqásñ

prefix(a,x)=a+x

postfix(x,a)=x+a

x+empty=x

empty+x=x

x+(y+z)=(x+y)+z

+ ist also ein “überladener” Operator, der für mehrere verschiedene Eingabetypen eine Sequenz liefert. Er kann wie folgt rekursiv definiert werden:
x+empty=x

x+postfix(y,a) = postfix(x+y,a)

empty+x=x

prefix(a,x)+y = prefix(a,x+y)

Stapel und Schlangen
Stapel („stack“): einseitiger Zugriff

empty, isEmpty, first, rest, prefix – oder –

empty, isEmpty, last, lead, postfix

top @ first/last, pop @ rest/lead, push @ prefix/postfix

Schlange („queue“):

empty, isEmpty, first, rest, postfix – oder –

empty, isEmpty, last, lead, prefix

head @ first/last, tail @ rest/lead, append @ postfix/prefix

Multimengen
bagásñ :

empty : ® bagásñ

isEmpty : bagásñ ® boolean

insert: bagásñ × s ® bagásñ

delete: bagásñ × s ® bagásñ

elem: s × bagásñ ® boolean

any: bagásñ ® s
isEmpty(empty) = true

isEmpty(insert(x,a)) = false

insert(insert(x,a),b)= insert(insert(x,b),a)
delete(empty,a) = empty

delete(insert(x,a),a) = x

delete(insert(x,b),a) = insert(delete(x,a),b)
elem(a, empty) = false

elem(a, insert(x,a)) = true

elem(a,insert(x,b) = elem(a,x) (a≠b)

elem(any(x),x) = true (x≠empty)

Beispiel-Algorithmus für Multimengen
card: bagásñ × s ® N₀
int card (bagásñ x, s a){

if (isEmpty(x)) return 0;

else {

s b = any(x);

return card(delete(x,b)) + ((a=b)?1:0);

}

}