3.1.5 Signaturen und Strukturen€¦ · ML-Module heißen Strukturen und fassen Datentyp- und Funktionsdeklarationen zusammen. Jede Struktur besitzt eine Signatur, die angibt,

14.10.08 84© A. Poetzsch-Heffter, TU Kaiserslautern

3.1.5 Signaturen und Strukturen

Begriffsklärung: (Modulsystem)

Ein Programmmodul fasst mehrere Deklarationenzusammen und stellt sie unter einem Namen zur Verfügung.

ML-Module heißen Strukturen und fassen Datentyp- und Funktionsdeklarationen zusammen. Jede Struktur besitzt eine Signatur, die angibt,

- welche Typen und

- welche Funktionen

eine Struktur deklariert.

Bemerkung: (Signaturen/Strukturen)

Die Sprachkonstruktre „Signatur“ und „Struktur“implementieren und verallgemeinern die in 3.1.1 eingeführten Konzepte von Datenstrukturen mit Signaturen:

- ML-Strukturen können auch Ausnahmen (engl. Exception) und andere Strukturen enthalten

- ML-Signaturen können unabhängig von Strukturen deklariert werden.


Definition von Strukturen:structure Environment = struct type env = (string,int) list; val emptyEnv = nil; fun lookup (n:string, nil:env) = NONE | lookup (n, (n1,i)::ev) = if n = n1 then SOME i else lookup (n,ev)

fun insert ((n,i), ev) = ((n,i)::ev):env

fun delete (n, nil:env) = nil:env | delete (n, (n1,i)::env) = if n = n1 then delete (n,env) else (n1,i)::(delete (n,env))end;

ML inferiert aus der Strukturdefinition eine Signatur:

structure Environment : sig type env = (string * int) list val emptyEnv : env val lookup : string * env -> int option val insert : (string*int) * env -> env val delete : string * env -> env end


Definition und Anwendung von Signaturen:

signature SSTRINTENV =sig type env = (string * int) list val emptyEnv : env val lookup : string * env -> int option val insert : (string*int) * env -> env end;

Signaturen sind „Typen für Strukturen“. Sie können benutzt werden, um Strukturen einzuschränken:

- auf weniger Funktionen, Werte, …

- auf eingeschränktere Typen

structure StrIntEnv : SSTRINTENV = Environment;

Beispiel: (Anwendung von Signaturen)

Struktur StrIntEnv besitzt keine Funktion delete.


Anwendung von Strukturen in ML:

- Ist S eine Struktur in ML, dann kann man ihre Deklarationen d mit S.d verwenden.

- Das Kommando „open“ macht die Deklarationen eines Moduls direkt sichtbar:

open S; (* d kann nun direkt verwendet werden *)

Beispiel: (Öffnen einer Struktur)

open StrIntEnv;

macht die Name der drei Funtionen von StrIntEnv direkt verwendbar.


3.1.6 Ein- und Ausgabe

Die ML Basis-Bibliothek stellt u.a. Strukturen zur Verfügung, um

- Werte auf der Standardausgabe auszugeben und

- aus Dateien zu lesen und in Dateien zu schreiben.

Ausgabe auf dem Standardausgabestrom

Ein- und Ausgabe von Programmen wird in den meistenSprachen/Betriebssytemen über Ströme realisiert:

- Eingabestrom (standard input)

- Ausgabestrom (standard output)

- Fehlerausgabestrom (standard error)

Für die Ausgabe einer Zeichenreihe in den Standard-ausgabestrom bietet ML die Funktion:

print : string -> unit

Beispiele: (Anwendung print)

Ausgabe aller Elemente einer string-Liste:

3.1.6 Ein- und Ausgabe

fun printStringList [] = ()

| printStringList (s::xs) =

(print s; printStringList xs) ;


Bisher haben wir Ausdrücke zur Beschreibung von Werten verwendet (siehe Folie 3.23).

Ausdrücke, die die print-Funktion enthalten, liefernnicht nur einen Wert, sondern haben außerdem einenSeiteneffekt, nämlich die Veränderung der Standard-ausgabe.

Bedeutung von Ausdrücken undAusdruckssequenzen

Begriffsklärung: (Seiteneffekt, Anweisung, Anweisungssequenz)Ausdrücke haben einen Wert als Ergebnis und können Seiteneffekte verursachen:

- Verändern von Ein-/Ausgabeströmen,

- Verändern von Dateien,

- Verändern des Zustands von Variablen.

Ein Ausdruck A, bei dem nur die Seiteneffekte eineRolle spielen, nennen wir eine Anweisung.

Listen von Anweisungen A0, ... , A

n, die nacheinander

ausgeführt werden sollen, nennen wir Anweisungssequenzen. Notation in ML:

( A0 ; ... ; An )


1. Aufeinander folgende Ausgaben:

fun printSum (m,n) = ( print (“Die Summe von “); print (Int.toString m); print (“ und “); print (Int.toString n); print (“ ist “); print (Int.toString (m+n)); print (“\n“) ) ;

Beispiele: (Ausdruckssequenz)

2. Ausgabe aller Quadratzahlen kleiner n :

fun printQZ (n:int):unit = if n<0 then () else printQZemb (0,n)

and printQZemb (i:int,n:int):unit = let val isq = i*i in if isq >= n then () else ( print (Int.toString isq); print "\n"; printQZemb (i+1,n) ) end ;


©

Programmieren mit Ein-/Ausgabeströmen:

type elem = chartype vector = string

val stdIn = instreamval stdOut = outstreamval stdErr = outstream

val output = fn: outstream * string -> unitval flushOut = fn: outstream -> unit

val inputLine = fn: instream -> string optionval inputN = fn: instream * int -> stringval input1 = fn: instream -> char optionval inputAll = fn: instream -> string

val endOfStream = fn: instream -> bool

Die Struktur TextIO stellt u.a. die folgenden Ströme und Funktionen zur Verfügung:

Erklärung siehe Vorlesung und unter http://www.smlnj.org/doc/basis/


Beispiel: (Programmieren mit Strömen)

2. Sukzessives Einlesen und Ausgeben :

open TextIO;

(* cumulateInput setzt Eingabezeilen solange*) (* hintereinander, bis das Ende des Stroms *)(* erreicht ist; dann wird alles Eingelesene*) (* ausgegeben. *)fun cumulateInput () = successiveRead ""

and successiveRead str = if endOfStream stdIn then output (stdOut,"\n"^str) else case inputLine stdIn of SOME s => successiveRead (str^s) | NONE => output (stdErr,"Error");

1. Lesen und Ausgeben eines Zeichens:

open TextIO;

(* charReadPrint liest zeichenweise ein *)(* und gibt die gelesenen Zeichen aus *)fun charReadPrint () = case input1 stdIn of SOME c => ( print(str c); charReadPrint()) | NONE => print "Error: no character";


©

Lesen und Schreiben von Dateien:

val openIn = fn : string -> instreamval closeIn = fn : instream -> unit

val openOut = fn : string -> outstreamval closeOut = fn : outstream -> unit

Dateien können nur bearbeitet werden, nachdem sie geöffnet wurden.

Nach der Bearbeitung sollte man die Datei schließen, um sie anderen Nutzern wieder zugänglich zu machen.

Für das Öffnen und Schließen enthält die Struktur TextIO die folgenden Funktionen:

Der string-Parameter von openIn und openOut liefert den Namen der Datei.


Beispiel: (Lesen & Schreiben von Dateien)

open TextIO;

(* readWriteFile liest Eingabezeilen aus *) (* der Datei inFile und schreibt sie in *)(* die Datei outFile *) fun readWriteFile (inFile,outFile) = let val inStream = openIn inFile ; val content = inputAll inStream ; val _ = closeIn inStream ; val outStream = openOut outFile in ( output (outStream,content); closeOut outStream ) end;

3.1.7 Zusammenfassung von 3.1

- Begriffe und Sprachmittel wie Ausdruck, Bezeichner, Vereinbarung, Wert, Typ, Muster, ...

- rekursive Funktionen

- rekursive Datentypen (insbesondere Listen)

- Strukturen und Signaturen

- Ströme und Dateibehandlung


3.2 Algorithmen auf Listen und Bäumen

Sortieren und Suchen sind elementare Aufgaben, die in den meisten Programmen anfallen.

Verfahren zum Suchen und Sortieren spielen einezentrale Rolle in der Algorithmik.

Bemerkung:

Lernziele:

- Intuitiver Algorithmusbegriff

- Kenntnis wichtiger/klassischer Algorithmen und Algorithmenklassen

- Zusammenhang Algorithmus und Datenstruktur

- Wege vom Problem zum Algorithmus

- Implementierungstechniken für Datenstrukturen und Algorithmen (vom Algorithmus zum Programm)

Wir führen in den Bereich Algorithmen und Datenstrukturen ausgehend vom Problem ein.Andere Möglichkeit wäre gemäß der benutztenDatenstrukturen (Listen, Bäume, etc.).


3.2.1 Sortieren

Übersicht über 3.2:

• Sortieren

• Suchen

Sortieren ist eine Standardaufgabe, die Teil vielerspeziellerer, umfassenderer Aufgaben ist.

Untersuchungen zeigen, dass „mehr als ein Viertelder kommerziell verbrauchten Rechenzeit aufSortiervorgänge entfällt“ [Ottmann, Widmayer:Algorithmen und Datenstrukturen, Kap. 2].

Begriffsklärung: (Sortierproblem)

Gegeben ist eine Folge s , ..., s von sogenanntenDatensätzen. Jeder Satz s hat einen Schlüssel k .Wir gehen davon aus, dass die Schlüssel ganzzahligsind. Aufgabe des Sortierproblems ist es, eine Permutation π zu finden, so dass die Umordnung derSätze gemäß π folgende Reihenfolge auf den Schlüsseln ergibt:

k ≤ k ≤ ... ≤ k

1 N

ii

π (1) π (2) π (N)


Bemerkung:

Offene Aspekte der Formulierung des Sortierproblem:

- Was heißt, eine Folge ist „gegeben“?

- Ist der Bereich der Schlüssel bekannt?

- Welche Operationen stehen zur Verfügung, um π zu bestimmen?

- Was genau heißt „Umordnung“?

Wir benutzen Datensätze folgenden Typs

type dataset = int * string

mit Vergleichsoperator:

infix 4 leq fun op leq((kx:int,dx),(ky:int,dy))= (kx<=ky)

Entwickle eine Funktion

sort: dataset list dataset list

so dass sort(xl) für alle Eingaben xl aufsteigend sortiert ist. Insbesondere sind mehrere Einträge mit gleichem Schlüssel nicht ausgeschlossen.

Aufgabenstellung:


Sortieren durch Auswahl (selection sort)

Algorithmische Idee:

• Entferne einen minimalen Eintrag min aus der Liste.

• Sortiere die Liste, aus der min entfernt wurde.

• Füge min als ersten Element an die sortierte Liste an.

Wir betrachten: • Sortieren durch Auswahl (engl. selection sort)• Sortieren durch Einfügen (engl. insertion sort) • Bubblesort• Sortieren durch rekursives Teilen (quick sort)• Sortieren durch Mischen (merge sort)• Heapsort


(* select: Hilfsfunktion liefert einen minimalen Eintrag der Liste bzw. x, falls x minimal. *)

fun select x nil = x | select x (y::yl) = if x leq y then select x yl else select y yl;

(* delete: Hilfsfunktion löscht ein Vorkommen von x aus der Liste.*)

fun delete x nil = nil | delete x (y::yl) = if (x = y) then yl else y :: delete x yl;

(* selectionsort: sortiert Liste min: ein minimaler Eintrag in Liste xl. rest: die Liste xl ohne min *)

fun selectionsort nil = nil | selectionsort (x::xl) = let val min = select x xl; val rest = delete min (x::xl); in min :: (selectionsort rest) end;


Sortieren durch Einfügen (insertion sort)


• Sortiere zunächst den Rest der Liste.

• Füge dann den ersten Eintrag in die sortierte Liste ein.

(* insert: Hilfsfunktion fügt Argument in sortierte Liste ein *)

fun insert a nil = [a] | insert a (y::yl) = if (a leq y) then a :: (y :: yl) else y :: (insert a yl)

(* insertionsort: sortiert Liste *)

fun insertionsort nil = nil | insertionsort (x::xl) = insert x (insertionsort xl)


Bubblesort

(* bubble: Hilfsfunktion liefert einen maximalen Eintrag der Liste und die Liste ohne den maximalen Eintrag *)

fun bubble rl e nil = (rl,e) | bubble rl e (y::yl) = if (e leq y) then bubble (rl@[e]) y yl else bubble (rl@[y]) e yl

(* bubblesort: sortiert Liste *)

fun bubblesort nil = nil | bubblesort (x::xl) = let val (rl,max) = bubble nil x xl in (bubblesort rl)@[max] end


• Schiebe einen Eintrag nach rechts heraus:

- Beginne dazu mit dem ersten Eintrag e.

- Wenn schieben von e auf einen gleichen oder größeren Eintrag y stößt, schiebe y weiter.

- Ergebnis: maximaler Eintrag max und Liste ohne max

• Sortiere die Liste ohne max und hänge max an.


Quicksort: Sortieren durch Teilen

fun split p nil = (nil,nil) | split p (x::xr) = let val (below, above) = split p xr in if p leq x then (below,x::above) else (x::below,above) end

fun qsort nil = nil | qsort (p::rest) = let val (below,above) = split p rest in (qsort below) @ [p] @ (qsort above) end


• Wähle einen beliebigen Datensatz mit Schlüssel k aus, das sogenannte Pivotelement.

• Teile die Liste in zwei Teile: - 1. Teil enthält alle Datensätze mit Schlüsseln < k - 2. Teil enthält die Datensätze mit Schlüsseln ≥ k

• Wende quicksort rekursiv auf die Teillisten an.

• Hänge die resultierenden Listen und das Pivotelement zusammen.


Bemerkung:

Quicksort ist ein typischer Algorithmus gemäß der Divide-and-Conquer-Strategie:

- Zerlege das Problem in Teilprobleme.

- Wende den Algorithmus auf die Teilprobleme an.

- Füge die Ergebnisse zusammen.

Sortieren durch Mischen:


• Hat die Liste mehr als ein Element, berechne die Länge der Liste div 2 (halfsize).

• Teile die Liste in zwei Teile der Länge halfsize (+1).

• Sortiere die Teile.

• Mische die Teile zusammen.

Bemerkung:

Mergesort ist auch effizient für das Sortieren vonDatensätzen, die auf externen Speichermedienliegen und nicht vollständig in den Hauptspeichergeladen werden können.


open List;

fun merge nil nil = nil

| merge nil yl = yl

| merge xl nil = xl

| merge (x::xl) (y::yl) =

if (x leq y)

then x :: (merge xl (y::yl))

else y :: (merge (x::xl) yl);

(* mergesort: sortiert gegebene Liste halfsize: Hälfte der Listenlänge. front: Vordere Hälfte der Liste. back : Hintere Hälfte der Liste. *)

fun mergesort nil = nil

| mergesort (x::nil) = [x]

| mergesort xl =

let

val halfsize = (length xl) div 2;

val front = take (xl,halfsize);

val back = drop (xl,halfsize);

in (* Merge 2 sortierte Listen! *)

merge (mergesort front) (mergesort back)

end;


Heapsort

Heapsort verfeinert die Idee des Sortierens durchAuswahl: Minimum bzw. Maximum wird nicht durch lineare Suche gefunden, sondern mit logarithmischem Aufwand durch Verwendung einer besonderen Datenstruktur, dem sogenannten Heap.


• 1. Schritt: Erstelle den Heap zur Eingabeliste.

• 2. Schritt:

- Entferne Maximumelement aus Heap (konstanter Aufwand) und hänge es an die Ausgabeliste.

- Stelle Heap-Bedingung wieder her (logarithmischer Aufwand). - Fahre mit Schritt 2 fort bis der Heap leer.

Bemerkung:

• Ziele des Vorgehens:

- Beispiel für komplexe, abstrakte Datenstruktur

- Zusammenhang der algorithmischen Idee und der Datenstruktur.

• Der Begriff „Heap“ ist in der Informatik überladen. Auch der Speicher für zur Laufzeit angelegte Variablen wird im Englischen „heap“ genannt.


Begriffsklärung: (zu Bäumen)

Wir betrachten im Folgenden Binärbäume, die

- entweder leer sind oder

- aus einem markierten Knoten mit zwei Unterbäumen bestehen.

Ein Blatt ist ein Knoten mit zwei leeren Unterbäumen.

Ein Binärbaum heißt strikt, wenn jeder Knoten ein Blatt ist oder zwei nicht-leere Unterbäume besitzt.

Ein Binärbaum der Höhe h heißt vollständig, wenner strikt ist und alle Blätter die Tiefe h-1 haben.

Ein Binärbaum der Höhe h heißt fast vollständig, wenn

- jedes Blatt die Tiefe h-1 oder h-2 hat,

- jeder Knoten mit einer Tiefe kleiner h-2 zwei nicht- leere Unterbäume hat,

- für die Knoten K des Niveaus h-2 gilt:

1. Hat K 2 nicht-leere Unterbäume, dann auch alle linken Nachbarn von K.

2. Ist K ein Blatt, dann sind auch alle rechten

Nachbarn von K Blätter.

3. Es gibt maximal ein K mit genau einem nicht-leeren Unterbaum und der ist links.


Beispiel: (Fast vollständiger indizierter undmarkierter Binärbaum)

88

572

1514231

0:

1: 2:

3: 4: 5:

Ein Baum der Größe n heißt indiziert, wenn man seine Knoten mittels der Indizes 0,...,n-1 ansprechen kann.

Bemerkung:

Im Folgenden gehen wir bei indizierten Bäumen immer davon aus, dass die Reihenfolge der Indices einem Breitendurchlauf folgt (siehe Beispiel unten).


signature FVBINTREE = sig (* Typ fast vollständiger Binärbäume, ggf. leer *) type fvbintree;

(* Erzeugt fast vollständigen Binärbaum, wobei die Listenelemente zu Markierungen werden *) val create : dataset list -> fvbintree;

(* Anzahl der Knoten des Baums *) val size : fvbintree -> int ;

(* Markierung am Knoten mit Index i *) val get : fvbintree * int -> dataset ;

(* Vertausche Markierungen der Knoten mit Ind. i, ,j *) val swap : fvbintree * int * int -> fvbintree;

(* Entferne letzten Knoten *) val removeLast: fvbintree -> fvbintree ;

(* Knoten mit Index i hat linkes Kind *) val hasLeft : fvbintree * int -> bool ;

(* Knoten mit Index i hat rechtes Kind *) val hasRight : fvbintree * int -> bool

(* Index des linken Kinds von Knoten mit Index i *) val left : fvbintree * int -> int ;

(* Index des rechten Kinds von Knoten mit Index i *) val right : fvbintree * int -> int

end;

Signatur für fast vollständige, markierte,indizierte Binärbäume:


Vorgehen:

• Wir gehen im Folgenden davon aus, dass wir eine Datenstruktur zur Signatur FVBINTREE haben (steht zum Testen bereit) und realisieren heapsort damit; d.h. ohne die Struktur/Implementierung zu kennen.

• Im Zusammenhang mit der objektorientierten Programmierung werden wir dann eine sehr effiziente Implementierung für die Signatur kennen lernen.

Bemerkung:• Wir benutzen die Datenstruktur ohne die Implemen- tierung zu kennen; man sagt die Datenstruktur ist für den Nutzer abstrakt und spricht von abstrakter Datenstruktur.

• Die Signatur beschreibt die Schnittstelle der abstrakten Datenstruktur. Die Benutzung von Schnittstellen abstrakter Datenstrukturen ist ein zentraler Bestandteil der SW-Entwicklung.

• Eine abstrakte Datenstruktur kann unterschiedliche Implementierungen haben. Implementierungen können ausgetauscht werden, ohne dass der Nutzer seine Programme ändern muss!


Begriffsklärung: (Heap)

Ein markierter, fast vollständiger, indizierter Binärbaummit n Knoten heißt ein Heap der Größe n, wenn die folgende Heap-Eigenschaft erfüllt ist:

Ist M ein Knoten und N ein Kind von M mit Markierungen k und k , dann gilt:

k ≥ k .N

M

M

N

Beispiel: (Heap)

88

5762

25514231

10

Heap der Größe 8:

Bei einem Heap sind die Knoten entsprechend einemBreitendurchlauf indiziert (siehe Beispiel unten).

0:

1: 2:

3: 4: 5: 6:

7:


Herstellen der Heap-Eigenschaft:

Bemerkung:

Die Heap-Eigenschaft garantiert, dass der Schlüsseleines Knotens M größer gleich aller Schlüssel in denUnterbäumen von M ist. Insbesondere steht in derWurzel ein Element mit einem maximalen Schlüssel.

Sei ein markierter, fast vollständiger Binärbaumgegeben, der die Heap-Eigenschaft nur an der Wurzel verletzt.

Die Heap-Eigenschaft kann hergestellt werden, indem man den Wurzelknoten M rekursiv in dem Unterbaum mit dem größeren Schlüssel versickern lässt:

- Gibt es kein Kind, ist nichts zu tun.

- Gibt es genau ein Kind N, dann ist dies links und kinderlos: Ist k < k , vertausche die Markierungen.

- Gibt es zwei Kinder und ist N das Kind mit dem größeren Schlüssel: Ist k < k , vertausche die

Markierungen und fahre rekursiv mit dem Unterbaum zu N fort.

NM

NM


Beispiel: (Versickern lassen)

62

5718

5142

0:

1: 2:

3: 4: 5:10

62

5742

5118

0:

1: 2:

3: 4: 5:10

18

5762

5142

0:

1: 2:

3: 4: 5:10


(* Annahme: Die Kinder von ix in b erfüllen die Heap-Eigenschaft *)fun heapify b ix = let val ds = get(b,ix) in if hasLeft(b,ix) andalso not (hasRight(b,ix)) then let val lx = left(b,ix) in if get(b,lx) leq ds then b else swap(b,ix,lx) end else if hasRight(b,ix) then let val lx = left(b,ix) ; val rx = right(b,ix); (* zu betrachtendes Kind *) val cx = if get(b,lx) leq get(b,rx) then rx else lx in if get(b,cx) leq ds then b else heapify (swap(b,ix,cx)) cx end else b end

Funktion heapify formuliert auf Basis von FVBINREE:


Konkretisierung des Heapsort-Algorithmus:

1. Schritt:

- Erzeuge Binärbaum-Repräsentation aus Eingabefolge.

- Stelle Heap-Eigenschaft her, indem heapify ausgehend von den Blättern für jeden Knoten aufgerufen wird. Es reicht, nur Knoten mit Kindern zu berücksichtigen.

2. Schritt::

- Schreibe den Wurzel-Datensatz in die Ausgabe.

- Schreibe den Datensatz des letzten Elementes in den Wurzelknoten.

- Entferne das letzte Element.

- Stelle die Heap-Eigenschaft wieder her.

- Fahre mit Schritt 2 fort, solange die Größe > 0.

Lemma:

In einem fast vollständigen Binärbaum der Größe n sind die Knoten mit den Indizes (n div 2) bis n-1 Blätter.


Heapsort: Abstrakte Version

Wir betrachten zunächst Heapsort auf Basis desabstrakten Datentyps mit Signatur FVBINTREE:

Heapsort profitiert davon, dass sich fast vollständige,markierte, indizierte Binärbäume sehr effizient mitFeldern realisieren lassen:

(* Hilfsfunktion für Schritt 1 *)fun heapifyAll b = hpfyEmb b ((size b) div 2)and hpfyEmb b 0 = if size b = 0 then b else heapify b 0 | hpfyEmb b ix = hpfyEmb (heapify b ix) (ix-1)

(* heapsort: sortiert gegebene Liste *)

fun heapsort xl = rev (sortheap (heapifyAll (create xl)))and sortheap hp = if size hp = 0 then [] else let val maxds = get(hp,0) ; in if size hp = 1 then [maxds] else let val hp1 = swap(hp,0,(size hp)-1); val hp2 = removeLast hp1 ; val hp3 = heapify hp2 0 in maxds::(sortheap hp3) end end;


Es hätte klar werden müssen:

• Zu einem algorithmischen Problem (hier Sortieren) gibt es im Allg. viele Lösungen.

• Lösungen unterscheiden sich in:

- der Laufzeiteffizienz (messbar)

- der Speichereffizienz (messbar)

- der „Komplexität“ der Verfahrensidee (im Allg. nicht messbar).

In den folgenden Kapiteln werden wir demonstrieren,

• wie einige der obigen Algorithmen in anderen Programmierparadigmen formuliert werden können;

• wie der Effizienz/Komplexitätsbegriff präzisiert werden kann.

3.2.2 Suchen

Abschließende Bemerkungen zu 3.2.1

Die Verwaltung von Datensätzen basiert auf drei grundlegenden Operationen:

- Einfügen eines Datensatzes in eine Menge von Datensätzen;

- Suchen eines Datensatzes mit Schlüssel k;

- Löschen eines Datensatzes mit Schlüssel k.


Weitere oft gewünschte Operationen sind: sortierte Ausgabe, Suchen aller Datensätze mit bestimmtenEigenschaften, bearbeiten von Daten ohne eindeutigeSchlüssel, etc.

Entsprechend unseren Datensätzen betrachten wirdie folgende Signatur / Schnittstelle:

Ziel ist es, Datenstrukturen zu finden, bei denen derAufwand für obige Operationen gering ist. Wir betrach-ten hier die folgenden Dictionary-Realisierungen:

• lineare Datenstrukturen (Übung)

• (natürliche) binäre Suchbäume (Vorlesung)

signature DICTIONARY = sig type dict; val Empty: dict; val get : dict * int -> bool * string ; val put : dict * int * string -> dict ; val remove: dict * int -> dict;end;

Bemerkung: In der Literatur zur funktionalen Programmierung wir „get“ oft „lookup“ oder „search“, „put“ oft „insert“ und „remove“ oft „delete“ genannt. Um den Zusammenhang zu OO-Schnittstellen augenfälliger zu machen, benutzen wir die dort üblichen Namen.


Binäre Suchbäume

Begriffsklärung: (binärer Suchbaum)

Ein markierter Binärbaum B ist ein natürlicher binärer Suchbaum (kurz: binärer Suchbaum),wenn die Suchbaum-Eigenschaft gilt, d.h. wenn für jeden Knoten K in B gilt:

- Alle Schlüssel im linken Unterbaum von K sind echt kleiner als der Schlüssel von K.

- Alle Schlüssel im rechten Unterbaum von K sind echt größer als der Schlüssel von K.

• „Natürlich“ bezieht sich auf das Entstehen der Bäume in Abhängigkeit von der Reihenfolge der Einfüge-Operationen (Abgrenzung zu balancierten Bäumen).

• In einem binären Suchbaum gibt es zu einem Schlüssel maximal einen Knoten mit entsprechender Markierung.

Bemerkung:


Datenstruktur:

Wir stellen Dictionaries als Binärbäume mit Markierungen vom Typ dataset dar:

Die Konstante Empty repräsentiert das leereDictionary.

Binärbäume, die als Dictionary verwendet werden,müssen die Suchbaum-Eigenschaft erfüllen.

Alle Funktionen, die Dictionaries als Parameterbekommen, gehen davon aus, dass die Suchbaum-Eigenschaft für die Parameter gilt.

Die Funktionen müssen garantieren, dass die Eigenschaft auch für Ergebnisse gilt.

Man sagt:

Die Suchbaum-Eigenschaft ist eine Datenstrukturinvariante von Dictionaries.

Wir guarantieren die Datenstrukturinvariante u.a.dadurch, dass wir Nutzern der Datenstruktur keinen Zugriff auf den Konstruktor Node geben.

datatype btree = Node of dataset * btree * btree | Empty ;


structure Dictionary : DICTIONARY = struct

datatype btree = Node of dataset * btree * btree | Empty ;

type dict = btree ;

fun get ... (* siehe unten *)

fun put ... (* siehe unten *)

fun remove ... (* siehe unten *)

end;

Die Struktur Dictionary stellt nur die in der SignaturDICTIONARY vereinbarten Typen, Werte und Funktionen den Nutzern zur Verfügung.

Insbesondere sind Node und btree nur in Dictionaryverfügbar und nicht für Nutzer von Dictionary.

Suchen eines Eintrags:

Wenn kein Eintrag zum Schlüssel existiert, liefere(false,““) ; sonst liefere (true,s), wobei s der Stringzum Schlüssel ist:

fun get (Empty, k) = (false,"") | get (Node ((km,s),l,r),k) = if k < km then get (l,k) else if k > km then get (r,k) else (* k = km *) (true,s)


Einfügen:

Algorithmisches Vorgehen:

- Neue Knoten werden immer als Blätter eingefügt.

- Die Position des Blattes wird durch den Schlüssel des neuen Eintrags festgelegt.

- Beim Aufbau eines Baumes ergibt der erste Eintrag die Wurzel.

- Ein Knoten wird in den linken Unterbaum der Wurzel eingefügt, wenn sein Schlüssel kleiner ist als der Schlüssel der Wurzel; in den rechten, wenn er größer ist. Dieses Verfahren wird rekursiv fortgesetzt, bis die Einfügeposition bestimmt ist.

45

5722

65524217

49

Beispiel:

Einfügen von 33:

33


fun put (Empty,k,s) = Node((k,s),Empty,Empty) | put (Node ((km,sm),l,r),k,s) = if k < km then Node ((km,sm),put(l,k,s),r) else if k > km then Node ((km,sm),l,put(r,k,s) else (* k = km *) Node ((k,s),l,r)

Die algorithmische Idee lässt sich direkt umsetzen.

Beachte aber, dass das Dictionary nicht verändertwird, sondern ein neues erzeugt und abgeliefert wird:

• Die Reihenfolge des Einfügens bestimmt das Aussehen des binären Suchbaums:

Reihenfolgen:

2 ; 3 ; 1 1 ; 3 ; 2 1 ; 2 ; 3

Bemerkungen:

1 3

2 1

3

2

2

1

3


• Es gibt sehr viele Möglichkeiten, aus einer vorgegebenen Schlüsselmenge einen binären Suchbaum zu erzeugen.

• Bei sortierter Einfügereihenfolge entartet der binäre Suchbaum zur linearen Liste.

• Der Algorithmus zum Einfügen ist schnell, insbesondere weil keine Ausgleichs- oder Reorganisationsoperationen vorgenommen werden müssen.

Algorithmisches Vorgehen:

- Die Position eines zu löschenden Knotens K mit Schlüssel X wird nach dem gleichen Verfahren wie beim Suchen eines Knotens bestimmt.

- Dann sind drei Fälle zu unterscheiden:

Löschen:

Löschen ist die schwierigste Operation, da

- ggf. innere Knoten entfernt werden und dabei

- die Suchbaum-Eigenschaft erhalten werden muss.


1. Fall: K ist ein Blatt.

Lösche K:

X

Y

Z

Y

Z

2. Fall: K hat genau einen Unterbaum.

K wird im Eltern-Knoten durch sein Kind ersetzt und gelöscht:

X

Y

Z

Y

Z

Entsprechend, wenn X in rechtem Unterbaum.

Die anderen links-rechts-Varianten entsprechend.


3. Fall: K hat genau zwei Unterbäume.

Problem: Wo werden die beiden Unterbäume nach dem Löschen eingehängt?

Hier gibt es 2 symmetrische Lösungsvarianten:

- Ermittle den Knoten KR mit dem kleinsten Schlüssel im rechten Unterbaum, Schlüssel von KR sei XR.

- Speichere XR und die Daten von KR in K.

- Lösche KR gemäß Vorgehen zu Fall 1 bzw. 2.

(andere Variante: größten Schlüssel im rechten UB)

X

Y Z

XR

XR

Y Z


fun removemin (Node (d,Empty,r)) = (d,r) | removemin (Node (d,l,r)) = let val (min,ll) = removemin l; in (min, Node(d,ll,r)) end;

fun remove (Empty,k) = Empty | remove (Node((km,s),l,r),k)= if k < km then Node ((km,s), remove(l,k), r) else if k > km then Node ((km,s), l, remove(r,k)) else (* k = km *) case (l,r) of (Empty,rt) => rt | (lt,Empty) => lt | (lt,rt) => let val (min,rr) = removemin r in Node (min,lt,rr) end

Umsetzung in ML:

• Die Fälle 1 und 2 lassen sich direkt behandeln.

• Für Fall 3 realisiere Hilfsfunktion removemin, die

- nichtleeren binären Suchbaum b als Parameter nimmt;

- ein Paar (min,br) als Ergebnis liefert, wobei -- min der kleinste Datensatz in b ist und -- br der Baum ist, der sich durch Löschen von min aus b ergibt.


Diskussion:

Der Aufwand für die Grundoperationen Einfügen, Suchen und Löschen eines Knotens ist proportional zur Tiefe des Knotens, bei dem die Operation aus-geführt wird.

Ist h die Höhe des Suchbaumes, ist der Aufwand derGrundoperationen im ungünstigsten Fall also O(h),wobei log (N+1)-1 ≤ h ≤ N-1 für Knotenanzahl N.

Folgerung:

Bei degenerierten natürlichen Suchbäumen kannlinearer Aufwand für alle Grundoperationen entstehen.Im ungünstigsten Fall ist das Laufzeitverhalten alsoschlechter als bei der binären Suche auf Feldern.

Im Mittel verhalten sich Suchbäume aber wesentlichbesser (O(log N)). Zusätzlich versucht man durch gezielte Reorganisation eine gute Balancierung zu erreichen (siehe Kapitel 5).

Bemerkung:

Mit modifizierenden Operationen kann man das Auf- und Abbauen der Suchbäume vermeiden unddamit die Effizienz steigern.


3.3 Abstraktion mittels Polymorphieund Funktionen höherer Ordnung

Überblick:

• Grundbegriffe der Typisierung

• Polymorphie als Abstraktionsmittel

• Typsysteme und Typinferenz

• Einführung in Funktionen höherer Ordnung

• Wichtige Funktionen höherer Ordnung

• Abstraktionen über Datenstrukturen

3.3.1 Typisierung

Inhalte:

• Was ist ein Typ?

• Ziele der Typisierung

• Polymorphie und parametrische Typen

• Typsystem von ML und Typinferenz

Fast alle modernen Spezifikations- und Programmiersprachen besitzen ein Typsystem.


Ein Typ beschreibt Eigenschaften von Elementender Modellierung oder Programmierung:

• Elementare Typen stehen häufig für die Eigenschaft, zu einer bestimmten Wertemenge zu gehören ( bool, int, char, string, ... ).

• Zusammengesetzte Typen beschreiben die genaue Struktur ihrer Elemente ( Tupel-, Listen- und Funktionstypen).

Was ist ein Typ?

• Parametrische Typen beschreiben bestimmte Eigenschaften und lassen andere offen; z.B.:

- Elemente vom Typ ‘a list sind homogene Listen; man kann also null, hd, tl anwenden. Offen bleibt z.B. der Ergebnistyp von hd.

- Elemente vom Typ ‘a * ‘a list sind Paare, so dass die Funktionen für Paare angewendet werden können. Außerdem besitzen sie die Eigenschaft, dass die zweite Komponente immer eine Liste ist, deren Elemente vom selben Typ sind wie die erste Komponente:

fun f ( p:('a * 'a list ) ): 'a list =

let val (fst,scd) = p

in fst::scd end;


Die Typisierung verfolgt drei Ziele:

• Automatische Erkennung von Programmier- fehlern (durch Übersetzer, Interpreter);

• Verbessern der Lesbarkeit von Programmen;

• Ermöglichen effizienterer Implementierungen.

Wir konzentrieren uns hier auf das erste Ziel.

Zentrale Idee:

- Für jeden Ausdruck und jede Funktion wird ein Typ festgelegt.

- Prüfe, ob die Typen der aktuellen Parameter- ausdrücke mit der Signatur der angewendeten Funktion oder Operation übereinstimmen.

Ziele der Typisierung

f: int int, dann sind:

f 7 , f (hd [ 1,2,3 ]) , f ( f 78 ) + 9 typkorrekt;

f true , [ f, 5.6 ] , f hd nicht typkorrekt.

Beispiele: (Typprüfung von Ausdrücken)


Bemerkung:

Typisierung war lange Zeit nicht unumstritten.Hauptgegenargumente sind:

• zusätzlicher Schreibaufwand

• Einschränkung der Freiheit: - inhomogene Listen - Nutzen der Repräsentation von Daten im Rechner

Es gibt viele Programme, die nicht typkorrekt sind,sich aber trotzdem zur Laufzeit gutartig verhalten; z.B:

Aufgabe 1:

Schreibe eine Funktion frp:

- Eingabe: Liste von Paaren entweder vom Typ bool * int oder bool * real

- Zulässige Listen: Wenn 1. Komponente true, dann 2. Komponente vom Typ int, sonst vom Typ real

- Summiere die Listenelemente und liefere ein Paar mit beschriebener Eigenschaft.

Beispiel:


Realisierung in ML-Notation (kein ML-Programm, da nicht typkorrekt!):

fun frp [ ] = (true, 0)

| frp ((true,n)::xs ) =

case frp xs of

(true,k) => (true, k+n )

| (false,q) => (false, q + (real n))

| frp ((false,r)::xs ) =

case frp xs of

(true,k) => (false, (real k) + r)

| (false,q) => (false, q + r)

Bemerkung:

Wegen fehlender Typisierung ist es schwierig, dieÜberladung des Pluszeichens aufzulösen.

Aufgabe 2:

Schreibe eine Funktion,

- die ein n-Tupel (n>0) nimmt und

- die erste Komponente des Tupels liefert.


Das Typsystem einer Sprache S beschreibt,

- welche Typen es in S gibt bzw. wie neue Typen deklariert werden;

- wie den Ausdrücken von S ein Typ zugeordnet wird;

- welche Regeln typisierte Ausdrücke erfüllen müssen.

Ein Typsystem heißt polymorph, wenn es Werte bzw.Objekte gibt, die zu mehreren Typen gehören.

Begriffsklärung: (polymorphes Typsystem)

Polymorphie und parametrische Typen

Im Allg. bedeutet Polymorphie Vielgestaltigkeit.

In der Programmierung bezieht sich Polymorphieauf die Typisierung bzw. das Typsystem.

Realisierung in ML-Notation (kein ML-Programm, da nicht typkorrekt!) :

- fun f n = #1 n;

stdIn:14.1-14.15 Error: unresolved flex record

(can't tell what fields there are besides #1)


• In polymorphen Typsystemen gibt es meist eine Relation „ist_spezieller_als“ zwischen Typen T1, T2 :

T1 heißt spezieller als T2, wenn die Eigenschaften, die T1 garantiert, die Eigenschaften von T2 implizieren (umgekehrt sagt man: T2 ist allgemeiner als T1).

Beispiel:

Der Typ int list ist spezieller als der parametrische Typ ‘a list . Insbesondere gilt:

Jeder Wert vom Typ int list kann überall dort benutzt werden, wo ein Wert vom Typ ‘a list erwartet wird.

Bemerkung:

• Man unterscheidet:

- Parametrische Polymorphie

- Subtyp-Polymorphie (vgl. Typisierung in Java)

• Oft spricht man im Zusammenhang mit der Überladung von Funktions- oder Operatorsymbolen von Ad-hoc-Polymorphie.

Beispiel:

Dem +-Operator könnte man in ML den Typ

„int * int int oder real * real real “ geben.


Typsystem von ML und Typinferenz

Typen werden in ML durch Typausdrücke beschrieben:

- Typkonstanten sind die elementaren Datentypen: bool, int, char, string, real, ...

- Typvariablen: ‘a, ‘meineTypvar, ‘‘a, ‘‘gTyp

- Ausdrücke gebildet mit Typkonstruktoren:

Sind TA, TA1, TA2, TA3, ... Typausdrücke, dann sind die folgenden Ausdrücke auch Typausdrücke:

TA1 * TA2 Typ der Paare

TA1 * TA2 * TA3 Typ der Triple

...

TA list Listentyp

TA1 -> TA2 Funktionstyp

...


Beispiele: (Typausdrücke)

- int, bool

- ‘a, ‘b

- int * bool , int * ‘a , int * ‘b * ‘a

- int list, ‘a list , (int * ‘b * ‘a ) list

- int -> int , ‘a list -> (int * ‘b * ‘a ) list

- (int -> int) -> (real -> real)

Präzedenzregeln für Typkonstruktoren:

list bindet am stärksten

* bindet am zweitstärksten

-> bindet am schwächsten und ist rechtsassoziativ

Beispiele: (Präzedenzen)

int * bool list steht für int * ( bool list )

int * real -> int list steht für (int * real) -> (int list )

‘a -> char -> bool steht für ‘a -> ( char -> bool )


Begriffserklärung: (Vergleich von Typen)

Seien TA und TB Typausdrücke und var(TA) dieMenge der Typvariablen, die in TA vorkommen.

Eine Variablensubstitution ist eine Abbildung β von var(TA) auf die Menge der Typausdrücke.

Bezeichne TA den Typausdruck, den man aus TAerhält, wenn man alle Variablen v in TA konsistentdurch β (v) ersetzt.

TB ist spezieller als TA, wenn es eine Variablensubstitution β gibt, so dass TA = TB.

TA und TB bezeichnen den gleichen Typ, wenn TA spezieller als TB ist und TB spezieller als TA.

β

β

Beispiele:

int list ist spezieller als ‘a list

‘a list ist spezieller als ‘b list und umgekehrt

‘a -> ‘a ist spezieller als ‘a -> ‘b

int list * ‘b und ‘c list * bool sind nicht vergleichbar,d.h. der erste Ausdruck ist nicht spezieller als derzweite und der zweite nicht spezieller als der erste.


Bemerkung:

• Bezeichne TE die Menge der Typausdrücke in ML.

- Die „ist_spezieller_als“ Relation auf TE x TE ist reflexiv und transitiv, aber nicht antisymmetrisch.

- Identifiziert man alle Typausdrücke, die den gleichen Typ bezeichnen, erhält man die Menge T der Typen. ( T, ist _spezieller_als ) ist eine partielle Ordnung.

• Das Typsystem von ML ist feiner als hier dargestellt. Insbesondere wird zwischen allen Typen und der Teilmenge von Typen unterschieden, auf denen die Gleichheit definiert ist, den sogenannten Gleichheitstypen.

Beispiel:

- fun listcompare [] [] = true

| listcompare [] (x::xs) = false

| listcompare (x::xs) [] = false

| listcompare (x::xs) (y::ys) =

if x=y then listcompare xs ys else false;

val listcompare = fn : ''a list -> ''a list -> bool


• Typvariablen für Gleichheitstypen beginnen mit zwei Hochkommas. Damit verstehen wir nun auch den Typ der Gleichheitsfunktion in ML:

- val eq = fn (x,y) => x = y ;

val eq = fn : ''a * ''a -> bool

Damit ist gesagt, was Typen in ML sind.

Wir nennen eine Ausdruck A typannotiert, wenn A und allen Teilausdrücken von A ein Typ zugeordnet ist.

Beispiel:

Die Typannotationen von abs ~2

ist ( (abs:int->int)(~2:int) ):int

Die Typregeln legen fest, wann ein typannotierter Ausdruck typkorrekt ist. In ML muss gelten:

- die Typen der formalen Parameter müssen gleich den Typen der aktuellen Parameter sein.

- if-then-else, andalso, orelse müssen korrekt typisierte Parameter haben.

Typregeln in ML:


Typinferenz:

Typinferenz bedeutet das Ableiten der Typ-annotation für Ausdrücke aus den gegebenen Deklarationsinformationen.

Sie ist in gängigen Programmiersprachen oft recht einfach, in modernen Programmiersprachen teilweise recht komplex.

Beispiele:

1. Leere Liste:

- val a = [ ];

val a = [ ] : 'a list

2. Einsortieren in geordnete Liste von Zahlen:

- fun einsortieren (p1,p2) =

case p2 of

x::xs => if p1 <= x then p1::p2

else x::(einsortieren (p1,xs))

| [ ] => [ p1 ] ;

val einsortieren = fn : int * int list -> int list


3. Einsortieren in geordnete Liste mit Vergleichs- funktion:

- fun einsortieren2 (v,p1,p2) =

case p2 of

x::xs => if v (p1,x) then p1::p2

else x::(einsortieren2 (v,p1,xs))

| [ ] => [ p1 ] ;

val einsortieren2 = fn: ('a * 'a-> bool) * ‘a * 'a list -> 'a list

Bemerkung:

Bei der Typinferenz versucht man immer den allgemeinsten Typ herauszufinden.


Parametrische markierte Binärbaumtypen:

1. Alle Markierungen sind vom gleichen Typ:

datatype ‘a bbaum =

Blatt of ‘a

| Zweig of ‘a * ‘a bbaum * ‘a bbaum

2. Blatt- und Zweigmarkierungen sind möglicherweise von unterschiedlichen Typen:

datatype (‘a,‘b) bbaum =

Blatt of ‘a

| Zweig of ‘b * (‘a,‘b) bbaum * (‘a,‘b) bbaum


Funktionen höherer Ordnung sind Funktionen, die

- Funktionen als Argumente nehmen und/oder

- Funktionen als Ergebnis haben.

Selbstverständlich sind auch Listen oder Tupel vonFunktionen als Argumente oder Ergebnisse möglich.

Eine Funktion F, die Funktionen als Argumentenimmt und als Ergebnis liefert, nennt man häufig auchein Funktional.

Einführung

3.3.2 Funktionen höherer Ordnung

Funktionale, die aus der Schule bekannt sind, sind

- Differenzial

- unbestimmtes Integral

Überblick:

• Einführung in Funktionen höherer Ordnung

• Wichtige Funktionen höherer Ordnung

• Abstraktionen über Datenstrukturen


Zwei konzeptionelle Aspekte liegen der Anwendungvon Funktionen höherer Ordnung in der Software-Entwicklung zugrunde:

1. Abstraktion und Wiederverwendung

2. Metaprogrammierung, d.h. das Entwickeln von Programmen, die Programme als Argumente und Ergebnisse haben.

Wir betrachten im Folgenden den ersten Aspekt.

Sprachliche Aspekte:

Alle wesentlichen Sprachmittel zum Arbeiten mitFunktionen höherer Ordnung sind bereits bekannt:

- Funktionsabstraktion

- Funktionsdeklaration

- Funktionsanwendung

- Funktionstypen

Konzeptionelle Aspekte:


Aufgabe: Sortiere eine Liste xl von Zahlen

Rekursionsidee:

- Sortiere zunächst den Rest der Liste.

- Das ergibt eine sortierte Liste xs.

- Sortiere das erste Element von xl in xs ein.

Umsetzung in ML:

- fun einsortieren e [ ] = [ e ]

| einsortieren e (x::xr) =

if e <= x then e::x::xr

else x::(einsortieren e xr) ;

val einsortieren = fn : int -> int list -> int list

- fun sort [] = [] | sort (x::xr) = einsortieren x (sort xr);val it = fn : int list -> int list

Frage:

- Warum kann man mit sort nicht auch Werte der Typen char, string, real, etc. sortieren?

Antwort: Auflösung der Überladung von <=


Wiederverwendung zur Sortierung von real-Listen:

- fun einsortieren (e:real) [] = [e]

| einsortieren e (x::xr) =

if e <= x then e::x::xr

else x::(einsortieren e xr) ;

val einsortieren = fn : real -> real list -> real list

Unbefriedigend: Verändern einer Funktion, die für den Anwender vonsort ggf. nicht bekannt.

Abstraktion durch Parametrisierung:

Wiederverwendung von sort wird möglich, wennwir die Vergleichsoperation als zusätzlichen Parameter einführen:

- fun einsortieren vop e [ ] = [ e ]

| einsortieren vop e (x::xr) =

if vop (e,x) then e::x::xr

else x::(einsortieren vop e xr) ;

- fun sort vop [ ] = [ ]

| sort vop (x::xr) =

einsortieren vop x (sort vop xr) ;


Anwendung:

- sort (op <=) [ 2,3, 968,~98,34,0 ] ;

val it = [~98,0,2,3,34,968] : int list

- sort (op >=) [ 2,3, 968,~98,34,0 ] ;

val it = [968,34,3,2,0,~98] : int list

- sort ((op >=):real*real->bool) [1.0,1e~4];

val it = [1.0,0.0001] : real list

- val strcmp = ((op <=):string*string->bool);

- sort strcmp ["Abbay", "Abba", "Ara", "ab"];

val it = ["Abba","Abbay","Ara","ab"]

: string list

Polymorphe Funktionen können häufig auchFunktionen als Parameter nehmen.

Beispiel:

1. Funktion cons: abs::fac::nil

2. Identitätsfunktion: (fn x => x) (fn x => x) (Ausdruck ist von der Typisierung her problematisch)

Bemerkung:


Wichtige Funktionen höherer Ordnung

Dieser Abschnitt betrachtet einige Beispielefür Funktionen höherer Ordnung und diskutiertdas Arbeiten mit solchen Funktionen.

Funktionskomposition:

- fun fcomp f g = (fn x => f(g x));

val fcomp = fn : ('a->'b)->('c->'a)->'c->'b

In ML gibt es die vordefinierte Infix-Operation ofür die Funktionskomposition.

Map:

Anwendung einer Funktion auf die Elemente einerListe map f [ x1, ..., xn ] = [ (f x1), ... , (f xn) ]

- fun map f [] = []

| map f (x::xs) = (f x):: map f xs;

Anwendungsbeispiel 1:

- map size [“Schwerter“,“zu“,“Pflugscharen“];

val it = [9,2,12] : int list


Currying und Schönfinkeln:

Anwendungsbeispiel 2:

Aufgabe:

- Eingabe: Liste von Listen von ganzen Zahlen- Ausgabe: gleiche Listenstruktur, Zahlen verdoppelt

- fun double n = 2*n;

- map (map double) [ [1,2], [34829] ];

val it = [ [2,4], [69658] ] : int list list

Funktionen mit einem Argumenttupel kann man die Argumente auch sukzessive geben. Dabei entstehenFunktionen höherer Ordnung.

Beispiele:

- fun times m n = m * n;

val times = fn : int -> int -> int

- val double = times 2;

val double = fn : int -> int

- double 5;

val it = 10 : int


Zwei Varianten von map im Vergleich:

1. Die beiden Argumente als Paar:

- fun map (f , [ ]) = [ ]

| map (f,(x::xs)) = (f x) :: map (f,xs);

val map = fn: ('a->'b) * 'a list -> 'b list

2. Die Argumente nacheinander („gecurryt“):

- fun map f [] = []

| map f (x::xs) = (f x) :: map f xs;

val map = fn: ('a->'b) -> 'a list -> 'b list

Bemerkung:Die gecurryte Fassung ist flexibler: Sie kann nicht nur auf ein vollständiges Argumententupel angewendetwerden, sondern auch zur Definition neuer Funktionenmittels partieller Anwendung benutzt werden.

Beispiele:

val double = times 2 ;

val ilsort = sort (op <=) ;

val doublelist = map double ;


Curryen von Funktionen:

Die Funktion curry liefert zu einer Funktion auf Paarendie zugehörige gecurryte Funktion:

- fun curry f x y = f (x,y);

val curry = fn: ('a*'b->'c) -> 'a -> 'b -> 'c

Prüfen von Prädikaten für Listenelemente:

Die folgenden Funktionen exists und all prüfen, ob

- es Elemente in einer Liste gibt, die ein gegebenes Prädikat erfüllen bzw.

- alle Elemente einer Liste ein gegebenes Prädikat erfüllen.

- fun exists pred [ ] = false

| exists pred (x::xs) = pred x orelse exists pred xs;

val exists = fn: ('a->bool) -> 'a list -> bool

- fun all pred [ ] = true

| all pred (x::xs) = pred x andalso all pred xs;

val all = fn : ('a -> bool) -> 'a list -> bool


Anwendungsbeispiel:

Prüfen, ob ein Element in einer Liste enthalten ist:

- fun ismember x xs = exists (fn y=> x=y) xs;

val ismember = fn : ''a -> ''a list -> bool

Falten von Listen:

Eine sehr verbreitete Funktion ist das Falten einerListe mittels einer binären Funktion und einemneutralen Element:

foldr ⊗ n [e1, e2,...,en] = e1 ⊗ (e2 ⊗ (...(en ⊗ n)...))

Deklaration von foldr:

- fun foldr f n [ ] = n

| foldr f n (x::xs) = f (x,foldr f n xs);

val foldr = fn: ('a*'b->'b)->'b->'a list->'b

Punktweise Veränderung von Funktionen:

Die „Veränderung“ einer Funktion an einem Punktdes Argumentbereichs:

- fun update f x v y = if x = y then v else f y ;

val update = fn:(''a->'b)->''a->'b-> ''a -> 'b


- fun implode1 cl = foldr op^ "" (map str cl);

val implode = fn : char list -> string

- val implode2 = foldr (fn(x,y)=>(str x)^y) ““;

val implode2 = fn : char list -> string

Auf Basis von foldr lassen sich viele Listenfunktionendirekt, d.h. ohne Rekursion definieren:

- val sum = foldr op+ 0 ;

val sum = fn : int list -> int

- fun l1 @ l2 = foldr op:: l2 l1;

val @ = fn : 'a list * 'a list -> 'a list

Bäume mit variabler Kinderzahl lassen sich allgemeiner und kompakter behandeln (vgl. Folie 3.78):

datatype 'a vbaum = Kn of 'a*('a vbaum list)

fun zaehlekn (Kn (_,xs)) =

foldr op+ 1 (map zaehlekn xs)


Bemerkung:

Die Programmentwicklung mittels Funktionenhöherer Ordnung (funktionale Programmierung) ist ein erstes Beispiel für:

• das Zusammensetzen komplexerer Bausteine,

• programmiertechnische Variationsmöglichkeiten,

• die Problematik der Wiederverwendung:

- die Bausteine müssen bekannt sein,

- die Bausteine müssen ausreichend generisch sein.


Abstraktion über Datenstrukturen

Datenstrukturen lassen sich bzgl. einiger in ihnenverwendeten Typen und Funktionen parametrisieren.

Der Parameter ist dann kein Wert sondern eine Struktur.Der „Typ“ des Parameters, d.h. dessen Eigenschaften, werden durch eine Signatur angegeben.

Eine derart abstrahierte/parametrisierte Datenstrukturnennt man in ML einen Funktor. Ein Funktor nimmteine Datenstruktur als Parameter und liefert eineDatenstruktur als Ergebnis.

Exemplarisch betrachten wir hier Dictionaries, die bzgl.

- des Schlüsseltyps key

- des Typs der Daten data

- eines Dummy-Elements dummydata und

- der Vergleichsoperation auf Schlüsseln

parametrisiert sind.

signature ENTRY = sig eqtype key; type data; val dummydata : data; val leq: key * key -> boolend;


Der Funktor nimmt also eine Datenstruktur mit Signatur ENTRY als Parameter und liefert eineDatenstruktur für Dictionaries:

functor MakeBST ( Et: ENTRY ):

sig type dict; val Empty: dict; val get: dict * Et.key -> bool * Et.data ; val put: dict * Et.key * Et.data -> dict ; val remove: dict * Et.key -> dict end= struct

open Et;

type dataset = key * data ;

datatype btree = Node of (dataset*btree*btree) | Empty ;

type dict = btree ;

fun get (Empty, k) = (false,dummydata) | get (Node ((km,s),l,r),k) = if k = km then (true,s) else if leq(k,km) then get (l,k) else get (r,k)

... (* Fortsetzung auf kommender Folie *)


(* vgl. Folie 120, 122 und 126 *)

fun put (Empty,k,s) = Node((k,s),Empty,Empty) | put (Node ((km,sm),l,r),k,s) = if k = km then Node ((k,s),l,r) else if leq(k,km) then Node ((km,sm),put(l,k,s),r) else (* leq(km,k) *) Node ((km,sm),l,put(r,k,s))

fun removemin (Node(d,Empty,r)) = (d,r) | removemin (Node(d,l,r)) = let val (min,ll) = removemin l; in (min, Node(d,ll,r)) end;

fun remove (Empty,k) = Empty | remove (Node((km,s),l,r),k) = if leq(k,km) then Node ((km,s), remove(l,k), r) else if leq(km,k) then Node ((km,s), l, remove(r,k)) else (* k = km *) case (l,r) of (Empty,rt) => r | (lt,Empty) => l | (lt,rt) => let val (min,rr) = removemin r in Node (min,l,rr) endend;


structure IntStringDataset = struct type key = int; type data = string; val dummydata = ""; val leq = op <end;

structure Dictionary = MakeBST(IntStringDataset);

Zur Anwendung übergeben wir dem Funktor eineDatenstruktur mit Signatur ENTRY:

Bemerkung:

• Bei der Abstraktion über Datenstrukturen übernimmt die Signatur die Rolle des Parameter- und Ergebnis- typs.

• Wie bei der Funktionsabstraktion geht es auch bei der Abstraktion über Datenstrukturen darum, den einmal geschriebenen Rumpf für mehrere unterschiedliche Eingaben wiederzuverwenden.

• Bzgl. der präzisen Abstraktion von Programmen hinsichtlich unterschiedlicher Aspekte sind funktionale Programmiersprachen am weitesten.


Bemerkungen: (zur ML-Einführung)

• Ziel des Kapitels war es nicht, eine umfassende ML-Einführung zu geben. ML dient hier vor allem als Hilfsmittel, wichtige Konzepte zu erläutern.

• Die meisten zentralen Konstrukte wurden behandelt.

• Es fehlt Genaueres zu:

- Fehlerbehandlung

- Modularisierungskonstrukte (Signaturen, Strukturen, abstrakte Typen, Funktoren)

- Konstrukte zur imperativen Programmierung

• Viele Aspekte der Programmierumgebung wurden nicht näher erläutert.


3.4 Semantik, Testen & Verifikation

Übersicht:

• Einführung in Semantik von Programmiersprachen

• Testen und Verifikation

3.4.1 Zur Semantik funktionaler Programme

Lernziele in diesem Unterabschnitt:

- Was bedeutet Auswertungssemantik?

- Wie sieht sie im Falle von ML aus?

- Welche Bedeutung haben Bezeichner- umgebungen dabei?


In erster Näherung definiert eine Funktionsdeklarationeine partielle Funktion. Gründe für Partialität:

1. Der Ausdruck, der die Funktion definiert, ist bereits partiell:

- fun division (dd,dr) = dd / dr ;

- fun hd x::xs = x ;

2. Behandlung rekursiver Deklarationen:

a. Insgesamt unbestimmt: - fun f x = f x ;

b. Teilweise unbestimmt (hier für negative Zahlen): - fun fac (n:int):int = if n=0 then 1 else n*fac (n-1)

Ziel:

Ordne jeder syntaktisch korrekten Funktionsdeklarationeine partielle Funktion zu. Die Semantik beschreibt diese Zuordnung.

Wir unterscheiden hier denotationelle und operationelle Semantik. Statt operationeller Semantik spricht manhäufig von Auswertungssemantik.


Eine Semantik, die jeder Funktionsdeklaration explizit eine partielle Funktion als Bedeutung zuordnet, d.h. eine Abbildung von Funktions-deklarationen auf partielle Funktionen definiert, nennen wir denotationell.

Begriffsklärung: (denotationelle Semantik)

Eine denotationelle Semantik würde der obigenFunktionsdeklaration von fac eine Funktion f

f: Int Int

zuordnen, wobei

Int = { x | x ist Wert von Typ int } ∪ { }

Diese Funktion muss die Gleichung für fac erfüllen.Das Symbol steht dabei für „undefiniert“ und wird häufig als bottom bezeichnet.

Beispiel: (denotationelle Semantik)

⊥

⊥ ⊥

⊥

⊥


Zwei mögliche Lösungen:

⊥ , falls k = ⊥ oder k < 0 f (k) = k! , sonst

⊥ , falls k = ⊥

f (k) = 0 , k < 0

k! , sonst

Wir zeigen, dass f eine Lösung der Gleichung ist:

n= ⊥ : links: f (⊥) = ⊥

rechts: if ⊥=0 then 1 else ⊥ * f (⊥ -1) = ⊥

1

2

2

2

2

n<0 : links: f (n) = 0

rechts: if n=0 then 1 else n*f (n-1) = n*0 = 0

n≥ 0 : links: f (n) = n!

rechts: if n=0 then 1 else n*f (n-1) = n*(n-1)! = n!

Genauso lässt sich zeigen, dass f eine Lösung ist.

2

2

1

2

2


Die denotationelle Semantik muss sicherstellen,

• dass es für jede Funktionsdeklaration mindestens eine Lösung gibt, und

• eine Lösung auszeichnen, wenn es mehrere gibt.

Üblicherweise wählt man die Lösung, die an denwenigsten Stellen definiert ist, und betrachtet nurstrikte Funktionen als Lösung:

Begriffsklärung: (strikte Funktionen)Eine n-stellige Funktion oder Operation heißt strikt, wenn sie ⊥ als Ergebnis liefert, sobald eines derArgumente ⊥ ist.

Beispiele: (nicht-strikte Funktionen)if-then-else, andalso, orelse sind nicht-strikte Funktionen/Operationen.

Bemerkungen:• Denotationelle Semantik basiert auf einer Theorie partieller Funktionen und Fixpunkttheorie.

- Vorteile: Für Beweise besser geeignet.

- Nachteil: Theoretisch aufwendiger zu handhaben.

• ⊥ steht für undefiniert, unabhängig davon, welcher der Gründe für Partialität vorliegt.


Eine Semantik, die erklärt, wie eine Funktions-deklaration auszuwerten ist, nennen wir operationelloder Auswertungssemantik.

Begriffsklärung: (operationelle Semantik)

Begriffsklärung: (Auswertungsstrategie)Die Auswertungsstrategie legt fest,

- in welchen Schritten die Ausdrücke ausgewertet werden und

- wie die Parameterübergabe geregelt ist.

Wir erläutern

• eine Auswertungsstrategie für funktionale Programme,

• welche Rolle Bezeichnerumgebungen dabei spielen,

• und führen wichtige Begriffe ein.

Begriffsklärung: (formaler/aktueller Parameter)Ein Bezeichner, der in einer Funktionsdeklaration einenParameter bezeichnet, wird formaler Parameter genannt.

Der Ausdruck oder Wert, der einer Funktion bei einerAnwendung übergeben wird, wird aktueller Parameter genannt.


Beispiele: (Parameterübergabeverfahren)

Parameterübergabe:

1. Call-by-Value: - Werte die aktuellen Parameter aus. - Benutze die Ergebnisse anstelle der formalen Parameter im definierenden Ausdruck/Rumpf. - Werte den Rumpf aus.

2. Call-by-Name: - Ersetze alle Vorkommen der formalen Parameter durch die (unausgewerteten) aktuellen Parameterausdrücke. - Werte den Rumpf aus.

Unterschiedliche Auswertungsstrategien führen im Allg. zu unterschiedlichen Ergebnissen.

Betrachte:

fun f ( x, y ) = if x=0 then 1 else f( x-1, f(x-y,y)) ;

Werte den Ausdruck f(1,0) aus:

Beispiel: (Auswertungsstrategien)


1. Call-by-Value:

f ( 1, 0 )= if 1=0 then 1 else f( 1-1, f(1-0,0)) = if false then 1 else f( 1-1, f( 1-0,0) ) = f( 1-1, f( 1-0, 0 ) ) = f( 0, f( 1-0, 0 ) )= f( 0, f( 1-0, 0 ) )= f( 0, f( 1, 0 ) )= f( 0, if 1=0 then 1 else f( 1-1, f(1-0,0)) )= ....= f( 0, f( 0, f( 1, 0 ) ) )= ....

Diese Auswertung kommt nicht zum Ende, d.h. sie terminiert nicht.


2. Call-by-Name:

f ( 1, 0 )= if 1=0 then 1 else f( 1-1, f(1-0,0)) = if false then 1 else f( 1-1, f( 1-0,0) ) = f( 1-1, f( 1-0, 0 ) ) = if 1-1=0 then 1 else f(1-1 -1, f(1-1- f( 1-0, 0 ), f( 1-0, 0 ) ))= if true then 1 else f(1-1 -1, f(1-1- f( 1-0, 0 ), f( 1-0, 0 ) )) = 1

Mit Call-by-Name terminiert die Auswertung von f(1,0).

Begriffsklärung: (Normalform)

Der Ergebnisausdruck einer terminierenden Auswertung wird Normalform genannt.


Informelle Auswertungssemantik von ML

ML benutzt Call-by-Value Parameterübergabe.

Die Ausdrücke werden von

- links nach rechts (engl. leftmost) und

- innen nach außen (engl. innermost)

ausgewertet.

Die Auswertung eines Ausdrucks A kann in ML

- zu einem Ergebnis führen, dem Wert von A,

- eine Ausnahme auslösen,

- nicht terminieren.

Beispiel: (Ausnahmen)

• Die Auswertung des Ausdrucks 8 div 0 löst die Ausnahme „divide by zero“ aus.

• Die Anwendung der Funktion head auf die leere Liste löst die Ausnahme „non exhaustive match failure“ aus:

- fun head ( x::xs ) = x;

- head [ ]


Ausdrücke ohne benutzerdefinierte Funktionen:

Wir betrachten zunächst Ausdrücke, die nur über

- Konstante,

- Bezeichner für Werte von Datentypen,

- Bezeichner für vordefinierte Funktionen,

- sonstige Ausdruckskonstrukte von ML

aufgebaut sind und beschreiben die Auswertung informell.

Sei E eine Bezeichnerumgebung, die die Bindungen für die Bezeichner eines Ausdrucks A enthält.

Die Auswertung von A in E wird rekursiv über denAufbau von A beschrieben:

• Ist A eine Konstante K, dann liefere den Wert von K.

• Ist A ein Bezeichner für den Wert w eines Datentyps, dann liefere w.


• Ist A eine Funktionsanwendung einer vordefinierten Funktion, dann

- werte die aktuellen Parameterausdrücke aus;

- wird dabei eine Ausnahme ausgelöst, löst die Auswertung von A die gleiche Ausnahme aus;

- andernfalls wende die vordefinierte Funktion auf die aktuellen Parameter an;


- andernfalls liefere das Ergebnis.

• Ist A ein if-then-else-Ausdruck, dann

- werte zunächst die Bedingung aus;


- andernfalls werte je nach Ergebnis den then- oder else-Zweig aus;


- andernfalls liefere das Ergebnis der Auswertung des betrachteten Zweiges.

• Ist A ein andalso- oder orelse-Ausdruck: analog zu if-then-else


• Ist A ein case-Ausdruck, dann

- werte zunächst den Ausdruck nach dem Schlüsselwort case aus;


- andernfalls prüfe der Reihe nach, auf welches Muster das Ergebnis passt;

- passt es auf ein Muster, werte den zugehörigen Ausdruck aus;

> wird dabei eine Ausnahme ausgelöst, löst die Auswertung von A die gleiche Ausnahme aus;

> andernfalls liefere das Ergebnis;

- passt es auf kein Muster, löse die Ausnahme „non exhaustive match failure“ aus.


• Ist A ein let-Ausdruck, let DL in B end, dann

- werte DL aus;


- andernfalls erweitert die Auswertung von DL die Umgebung E zu E1;

- werte B in E1 aus;


- andernfalls liefere das Ergebnis der Auswertung von B.

• Terminiert einer der Teilauswertungen nicht, dann terminiert die Gesamtauswertung auch nicht.

Funktionsabschlüsse:

Kernfragen:

Wie wird das Ergebnis eines funktionswertigen Ausdrucks dargestellt?

Wie wird eine benutzerdeklarierte Funktion in derBezeichnerumgebung dargestellt?


Beispiel:

val a = 5;val b = 8;fun f (x: int):int = (x+a) * b ;val a = ~4;val d = f a;

Was soll für die Funktion f eingetragen werden:

Das Ergebnis eines funktionswertigen Ausdrucks wird durch ein Paar ( (x,AR), FE ) dargestellt, den sogenannten Funktionsabschluss (engl. Closure):

- x bezeichnet den formalen Parameter;

- AR bezeichnet den Ausdruck, der den Funktions- rumpf beschreibt.

- FE bezeichnet die aktuell gültige Umgebung.

Beispiel:Bezeichnerumgebung jeweils nach Auswertung einer Vereinbarung im obigen Programmbeispiel:

[ (a,5) ]

[ (b,8) , (a,5) ]

[ (f, ( (x,(x+a)*b), [ (b,8) , (a,5) ] ) ) , (b,8) , (a,5) ]

[ (a,~4) , (f, ( (x,(x+a)*b) , [ (b,8) , (a,5) ] ) ) , (b,8) ]

[ (d,8), (a,~4) , (f, ( (x,(x+a)*b), [(b,8),(a,5) ]) ) , (b,8) ]


Ausdrücke mit benutzerdefinierten Funktionen:

Auswertung der Anwendung von benutzerdefiniertenFunktionen, d.h. von Ausdrücken A der Form:

<funktionswertiger Ausdruck> <Parameterausdruck>

- werte zunächst den funktionswertigen Ausdruck aus;


- andernfalls liefert die Auswertung einen Funktionsabschluss ( (x,AR), FE );

- werte den Parameterausdruck aus;


- andernfalls liefert die Auswertung den Wert w des aktuellen Parameters;

- werte den Ausdruck AR in der Umgebung (x,w)::FE aus;


- andernfalls ist das Ergebnis der Auswertung von AR in (x,w)::FE das Ergebnis der Auswertung von A.


Beispiel: (Auswertung von Funktionsanw.)

Wir betrachten die Funktionsanwendung (f a) in der aktuellen Umgebung (vgl. obiges Beispiel):

[ (a,~4) , (f, ( (x,(x+a)*b), [ (b,8) , (a,5) ] ) ) , (b,8) ]

1. Die Auswertung von f in der aktuellen Umgebung liefert den Funktionsabschluss:

( ( x, (x+a)*b) , [ (b,8) , (a,5) ] )

2. Die Auswertung von a in der aktuellen Umgebung liefert den Wert ~4 .

3. Also ist (x+a)*b in [ (x,~4), (b,8), (a,5) ] auszuwerten:

- Auswertung von x liefert ~4 .

- Auswertung von a liefert 5 .

- Auswertung von + liefert vordefinierte Funktion, deren Anwendung auf ~4 und 5 liefert den Wert 1.

- Auswertung von b liefert 8.

- Auswertung von * liefert vordefinierte Funktion, deren Anwendung auf 1 und 8 liefert den Wert 8.

Insgesamt liefert die Auswertung von (f a) in der aktuellen Umgebung also den Wert 8.


Bemerkung:• Im Zusammenhang mit Pattern Matching ist die Bindung der aktuellen Parameter etwas aufwendiger.

• Für den Fall rekursiver Funktionen sind die Bezeichnerumgebungen komplexer.

Bei jeder parametrisierten Softwarekomponentemuss man sich überlegen und dokumentieren,

- welche aktuellen Parameter bei einer Anwendung zulässig sein sollen (der Anwender hat dann die Verantwortung, dass die Komponente nie mit unzulässigen Parametern angewendet wird); üblicherweise sollte die Komponente für zulässige Parameter normal terminieren;

- bei welchen Parametern möglicherweise Ausnahmen ausgelöst werden und welche.

Zulässige Parameterwerte und Ausnahmen


Bemerkungen:

• Beachte: Es ist eine Entwurfsentscheidung, welche Parameter zulässig und welche unzulässig sind, da man in der Softwarekomponente die Parameter zunächst prüfen kann.

Beispiel: zwei Varianten einer Funktion foo:

1. fun foo (m,n) =

if m<n then m div n else foo (m-n, n)

Zulässig für a) m < n, n ungleich 0 b) n > 0

2. exception unerwuenschteParameter;

fun foo (m,n) =

if ( m>= n orelse n=0 ) andalso n<=0

then raise unerwuenschteParameter

else if m<n then m div n else foo (m-n, n)

Bei dieser Variante könnte man alle Parameter als zulässig erklären.

Das Abprüfen der Zulässigkeit von Parametern (defensive Programmierung) führt zu besserer Stabilität, allerdings oft auf Kosten der Lesbarkeit und Effizienz der Softwarekomponente.


• Design by Contract:

Die Schnittstelle ist wie ein Vertrag zwischen

- dem Anwender der Komponente (client),

- demjenigen, der die Komponente realisiert (provider).

Beispiel: Vertrag zur Funktion heapifiy

heapify : fvbintree -> int -> fvbintree

Vorbedingung, die ein Anwender von heapify b ix erfüllen sollte:

- ix muss eine Index von b sein, d.h. 0<= ix < size b

- die Kinder von ix in b erfüllen die Heap-Eigenschaft

Nachbedingung, die das Ergebnis e von heapify b ix erfüllen sollte:

- size e = size b ;

- die Markierungen der Knoten, die sich nicht im Unterbaum von ix befinden, sind in e und b gleich;

- die Menge der Markierungen der Knoten, die sich im Unterbaum von ix befinden, sind in e und b gleich;

- der Knoten mit Index ix und alle seine Kinder in b erfüllen die Heap-Eigenschaft.


3.4.2 Testen und Verifikation

Qualitätssicherung: Kleine Einführung

Bei der Qualitätssicherung in der Softwareentwicklungspielen zwei Fragen eine zentrale Rolle:

• Wird das richtige System entwickelt?

• Wird das System richtig entwickelt?

Validation hat die Beantwortung der ersten Frage zum Ziel. Beispielsweise ist zu klären, ob

- die benutzten Anforderungen die Vorstellungen des Auftraggebers richtig wiedergeben,

- die Anforderungen von allen Beteiligten gleich interpretiert werden,

- Unterspezifizierte Aspekte richtig konkretisiert wurden.

Ein zentraler Teil der Software-Entwicklung bestehtdarin zu prüfen, ob die entwickelte Software auch den gestellten Anforderungen entspricht.

Überblick:- einführende Bemerkungen zur Qualitätssicherung- Testen- Verifikation von Programmeigenschaften


Validation prüft also die Übereinstimmung vonSoftware mit den Vorstellungen der Auftraggeber/Benutzer bzw. mit der Systemumgebung, in derdie Software eingesetzt wird.

Unter Verifikation verstehen wir den Nachweis,dass Software bestimmte, explizit beschriebene Eigenschaften besitzt. Beispiele:

- Mit Testen kann man prüfen, ob ein Programm zu gegebenen Eingaben die erwarteten Ausgaben liefert (Beschreibung: Testfälle).

- Mittels mathematischen Beweisen kann man zeigen, dass ein Programm für alle Eingaben ein bestimmtes Verhalten besitzt (Beschreibung: boolesche Ausdrücke, logische Formeln).

- Nachweis, dass ein Programm einen gegebenen Entwurf und die darin festgelegten Eigenschaften besitzt (Entwurfsbeschreibung).

Liegen die beschriebenen Eigenschaften in einerformalen Sprache vor, kann die Verifikationautomatisiert werden.

Zu prüfende Eigenschaften:

- Terminierung für zulässige Parameter

- Verhalten wie im Entwurf festgelegt


• Grundsätzlich können sich Validation und Verifikation auf alle Phasen der Software- entwicklung beziehen.

• Wir betrachten im Folgenden Testen und Verifikation durch Beweis anhand einfacher Beispiele im Kontext der funktionalen Programmierung. Eine systematischere Betrachtung von Aspekten der Qualitätssicherung ist Gegenstand von SE 2.

Bemerkung:

Testen

Testen bedeutet die Ausführung eines Programmsoder Programmteils mit bestimmten Eingabedaten.

Testen kann sowohl zur Validation als auch zurVerifikation dienen.

Bei funktionalen Programmen bezieht sich Testenüberwiegend auf Eingabe- und Ausgabeverhalten vonFunktionen. Wir betrachten:

• Testen mit Testfällen

• Testen durch dynamisches Prüfen


Testen mit Testfällen:

• Beschreibe das „Soll-Verhalten“ der Software durch eine (endliche) Menge von Eingabe-Ausgabe-Paaren.

• Prüfe, ob die Software zu den Eingaben der Testfälle die entsprechenden Ausgaben liefert.

Beispiel:

Testen der folgenden Funktionsdeklaration:

exception unzulaessigerParameter

fun fac 0 = 1

| fac n = if 0<n orelse n<=12

then n * fac (n-1)

else raise unzulaessigerParameter

Testfälle:

0 1

12 479001600

13 Ausnahme: unzulaessiger Parameter

~1 Ausnahme: unzulaessiger Parameter

~1073741824 Ausnahme: unzulaessiger Parameter


Beobachtetes Verhalten:

0 1

12 479001600

13 Ausnahme: overflow

~1 keine Terminierung beobachtet

~1073741824 Ausnahme: overflow

• Das Verhalten von Funktionen mit unendlichem Argumentbereich kann durch Testen nur teilweise verifiziert werden. Testen kann im Allg. nicht die Abwesenheit von Fehlern zeigen.

• Wichtig ist die Auswahl der Testfälle. Sie sollten die „relevanten“ Argumentbereiche abdecken.

Bemerkung:


Testen durch dynamisches Prüfen:

• Beschreibe Eigenschaften von Zwischen- oder Ergebniswerten mit den Mitteln der Programmier- sprache (meist boolsche Ausdrücke); d.h. implementiere Prüfprädikate.

• Rufe die Prüfprädikate an den dafür vorgesehenen Stellen im Programm auf.

• Lasse die Prüfprädikate in der Testphase des zu testenden Programms auswerten. Bei negativem Prüfergebnis muss eine Fehlermeldung erstellt werden.

Anders als beim Testen mit Testfällen wird also dasVerhalten des Programms an bestimmten Stellen automatisch während der Auswertung geprüft.

1. Prüfung der Zulässigkeit von Parametern bei Aufruf

2. Prüfung durch Ergebniskontrolle

Beispiel: (typische Prüfungen)

Bemerkung:Viele moderne Programmiersprachen bieten spezielleSprachkonstrukte für das Testen durch dynamische Prüfung an.


Verifikation durch Beweis

Verifikation im engeren Sinne meint meist Verifikationdurch Beweis. Hier verwenden wir den Begriff in diesemengeren Sinne.

Im Gegensatz zum Testen erlaubt Verifikation (durch Beweis) die Korrektheit zu zeigen, d.h. insbesonderedie Abwesenheit von Fehlern.

Wir betrachten hier nur Programmverifikation,d.h. den Nachweis, dass ein Programm einespezifizierte Eigenschaft besitzt.

Die Spezifikation kommt üblicherweise aus dem Entwurf bzw. den Anforderungen.

Zwei zentrale Eigenschaften:

- Programm liefert die richtigen Ergebnisse, wenn es terminiert (partielle Korrektheit).

- Programm terminiert für die zulässigen Eingaben.

Beide Eigenschaften zusammen ergeben totale Korrektheit.


Eine Funktionsdeklaration ggt zur Implementierungdes ggT zweier natürlicher Zahlen soll implementiertwerden.

Spezifikation:

Für m,n ≥ 0, m,n nicht beide null soll gelten:

ggt(m,n) = max { k | k teilt m und n }

Implementierung (Euklidscher Algorithmus):

(* m, n >= 0, nicht beide gleich 0 *)

fun ggt (m,n) =

if m=0 then n else ggt( n mod m, m )

Beispiel: (Spezifikation)

Bei funktionalen Programmen spielen zweiBeweistechniken eine zentrale Rolle:

1. Strukturelle oder Parameterinduktion

2. Berechnungsinduktion (computational induction)

Wir stellen nur die strukturelle Induktion vor.


Parameterinduktion:

Bei der Parameterinduktion werden die Eigenschafteneiner Funktion für alle Parameter gezeigt, indem maneine Induktion über die Menge der zulässigen Parameter führt.

Beispiel: (Korrektheit von ggt)

Vorüberlegung:

Für n ≥ 0, m>0 gilt:

k teilt m und n k teilt m und k teilt (n mod m)

Induktion über den Parameterbereich:

Wir zeigen:

a) ggt ist korrekt für m=0 und beliebiges n.

b) Vorausgesetzt ggt ist korrekt für alle (k,n) mit k ≤ m, dann auch für (m+1,n).

Ad a) Induktionsanfang:

ggt(0,n) = n = max { k | k teilt n }

= max { k | k teilt 0 und n }


Ad b) Induktionsschritt:

Voraussetzung: Sei m gegeben. Für alle n, k mit k ≤ m gilt: ggt ist korrekt für (k,n)

Zeige: Für alle n gilt: ggt ist korrekt für (m+1,n) ! ggt(m+1,n)

= (* Deklaration von ggt *)

ggt(n mod (m+1),m+1)

= (* n mod (m+1) ≤ m, Induktionsvoraussetzung *)

max { k | k teilt (n mod (m+1)) und m+1 }

= (* Vorüberlegung *)

max { k | k teilt m+1 und n }

QED.

Bemerkung:So wie Testen Testfälle oder Prüfprädikate voraussetzt,so benötigt Verifikation mit Beweis eine Spezifikationoder andere Beschreibung der zu zeigenden Eigenschaften.


Äquivalente Funktionsdeklarationen:

Wir haben gesehen, dass unterschiedlicheFunktionsdeklarationen das gleiche Ein- undAusgabeverhalten haben können.

Zum Beispiel kann eine Deklaration in einer „aufwendigeren“ Rekursionsformen einfacher zu lesen sein, aber eine entsprechende lineare oder repetitive Funktionsdeklaration performanter sein.

Transformiert man die eine in die andere Formist es wichtig, die Äquivalenz zu beweisen.

Bemerkung:

• Semantisch äquivalente Programme können große Unterschiede bei der Effizienz aufweisen.

• Bedeutungserhaltende Transformationen spielen in der Programmoptimierung und dem Refactoring von Software eine wichtige Rolle.


Wir betten die Fakultätsfunktion

fun fac (n :int) :int = if n = 0 then 1 else n * fac(n-1) ;

in eine Funktion mit einem weiteren Argument ein,das Zwischenergebnisse aufsammelt:

fun facrep ( n: int, res: int ): int = if n=0 then res else facrep(n-1,res*n)

Damit läßt sich die Fakultät definieren als:

fun fac1 (n :int) :int = facrep(n,1) ;

Dadurch wurde eine lineare Rekursion in einerepetitive Form gebracht.

Korrektheit von Transformationen:

Wir transformieren die rekursive Funktionsdeklarationenin einfachere Deklarationen und zeigen Äquivalenz:

Beispiel: (linear repetitiv)


Lemma:

Für die obigen Deklarationen von fac und facrep gilt:

∀n mit n ≥ 0, r mit r ≥ 0 : fac ( n ) * r = facrep ( n, r )

insbesondere: ∀n mit n ≥ 0 : fac (n) = fac1 (n)

Beweis: mittels Parameterinduktion nach n

Induktionsanfang:

Zu zeigen: ∀r mit r ≥ 0 : fac(0) * r = facrep( 0,r )

fac( 0 ) * r

= (* Deklaration von fac *)

( if 0 = 0 then 1 else 0 * fac (0-1) ) * r

= (* Ausdrucksauswertung *)

r


if 0=0 then r else facrep( 0-1, r*0 )

= (* Deklaration von facrep *)

facrep( 0, r )


Induktionsschritt: k k+1

Induktionsvoraussetzung: für k ≥ 0 : ∀r mit r ≥ 0 : fac ( k ) * r = facrep ( k, r )

Zu zeigen: fac ( k+1 ) * r = facrep ( k+1, r )

fac( k+1 ) * r

= (* Deklaration von fac *)

( if k+1 = 0 then 1 else (k+1) * fac (k+1-1) ) * r


( (k+1) * fac (k) ) * r

= (* Kommutativität & Assoziativität der Multiplikation *)

fac (k) * (r * (k+1))

= (* Induktionsvoraussetzung *)

facrep (k, r * (k+1) )


if k+1=0 then r else facrep( k, r * (k+1) )

= (* Deklaration von facrep *)

facrep( k+1, r )


Wir wollen die Fibonacci-Funktion fib in eine lineareForm transformieren.

Idee: Führe zwei zusätzliche Parameter ein, die benutzt werden, um die Anzahl der Paare ausgehend vom Anfang zu berechnen.

Es soll also gelten:

fib1 (n) = fibemb( n,1,1)

Wir definieren fibemb zu:

fun fibemb(n:int,letzt:int,res:int):int = if n<=1 then res else fibemb(n-1,res,letzt+res)

Dadurch wurde eine kaskadenartige Rekursion in eine repetitive Form gebracht.

Beispiel: (kaskadenartig linear)

Beweis:

(siehe Vorlesung)

mittels Parameterinduktion nach n


Terminierung

Zentrale Eigenschaft einer Funktionsdeklaration ist,dass ihre Anwendung auf die zulässigen Parameter terminiert.

Diese Eigenschaft gilt für alle nicht-rekursiven Funktionsdeklarationen, die sich nur auf terminierende Funktionen abstützen.

Bei rekursiven Funktionsdeklarationen muss die Terminierung nachgewiesen werden.

Idee: Die Parameter sollten bei jedem rekursiven Aufruf „kleiner“ werden.

Beispiele: („kleiner werdende“ Parameter)

1. fun foldrplus [ ] = 0

| foldrplus (x::xs) = x + foldrplus xs

2. fun einfuegen ( [ ], el, ix ) = [ el ]

| einfuegen ( xs, el, 0 ) = el::xs

| einfuegen ( x::xs, el, ix ) = einfuegen (xs,el, ix -1)

3. fun foo (m,n) =



Definition: (Ordnung)

Eine Teilmenge R von M x N heißt eine (binäre)Relation. Gilt M=N, dann nennt man R homogen.

Eine homogene Relation heißt:

• reflexiv, wenn für alle x ∈ M gilt: (x,x) ∈ R

• antisymmetrisch, wenn für alle x, y ∈ M gilt:

wenn (x,y) ∈ R und (y,x) ∈ R, dann x = y

• transitiv, wenn für alle x, y, z ∈ M gilt:

wenn (x,y) ∈ R und (y,z) ∈ R, dann (x,z) ∈ R

Eine reflexive, antisymmetrische und transitive homogene Relation auf M x M heißt eine (partielle)Ordnungsrelation.

Eine Menge M mit einer Ordnungsrelation R heißteine (partielle) Ordnung.

Meist benutzt man Infixoperatoren wie ≤ (oder ⊆ )zur Darstellung der Relation und schreibt

x ≤ y statt (x,y) ∈ R .


Definition: (Kette, noethersche Ordnung)

Sei (M, ≤ ) eine Ordnung. Eine Folge ϕ : IN Mheißt eine (abzählbar unendliche) aufsteigende Kette,wenn für alle i ∈ IN gilt:

ϕ (i) ≤ ϕ (i+1) (absteigende Kette: entsprechend).

Eine Kette ϕ wird stationär, falls es ein j ∈ IN gibt, so dass ϕ (j) = ϕ (j+k) für alle k ∈ IN.

Sei N eine Teilmenge von M. x ∈ N heißt :

größtes Element von N, wenn ∀y ∈ N gilt: y ≤ x .

kleinstes Element von N, wenn ∀y ∈ N gilt: x ≤ y .

maximales Element von N, wenn ∀y ∈ N gilt: x ≤ y impliziert x=y .

minmales Element von N, wenn ∀y ∈ N gilt: y ≤ x impliziert x=y .

Eine Ordnung (M, ≤ ) heißt noethersch, wennjede nicht-leere Teilmenge von M ein minimales Element besitzt.


Lemma:

Eine Ordnung ist genau dann noethersch, wennjede absteigende Kette stationär wird.

Beweis: (siehe Theorievorlesung)

Terminierungskriterium:

Sei f: S T eine rekursive Funktionsdeklarationmit formalem Parameter n und sei P die Menge der zulässigen Parameter von f.

Jede Anwendung von f auf Elemente von P terminiert,

- wenn es eine noethersche Ordnung (M, ≤ ) und

- eine Abb. δ : P M gibt,

- so dass für jede rekursive Anwendung f (G(n) ) im Rumpf der Deklaration gilt:

i) G(n) ist ein zulässiger Parameter, d.h. G(n) ∈ P.

ii) Die aktuellen Parameter werden echt kleiner, d.h.

δ (G(n)) < δ (n) .


Bemerkung:• Da die aktuellen Parameter nur endlich oft echt kleiner werden können (und dann stationär werden), garantiert das obige Kriterium die Terminierung.

• Um die Terminierung nachzuweisen, muss man also eine geeignete noethersche Ordnung und eine geeignete Abbildung δ finden.

• Ist der Argumentbereich bereits noethersch geordnet, kann δ selbstverständlich auch die Identität sein.

Beispiele: (Terminierungsbeweis)

1. fun foldrplus xs =

if null xs then 0 else (hd xs) + foldrplus ( tl xs )

P ist die Menge aller endlichen Listen.

Noethersche Ordnung (IN, ≤ ).

Als δ wähle die Funktion länge (Länge einer Liste).

Zu zeigen:

i) tl xs ist ein zulässiger Parameter : ok.

ii) länge( tl xs) < länge( xs ) : ok.


2. fun einfuegen ( [ ], el, ix ) = [ el ]

| einfuegen ( xs, el, 0 ) = el::xs

| einfuegen ( x::xs, el, ix ) = einfuegen (xs,el, ix -1)

P ist die Menge aller Tripel aus ‘a list * ‘a * int .


Als δ wähle die Funktion längefst, die länge auf die erste Komponente anwendet.

Zu zeigen:

i) (xs, el, ix-1 ) ist ein zulässiger Parameter : ok.

ii) längefst( xs, el, ix-1 ) < längefst( x::xs,el,ix ) : ok.

Bemerkung:

Hätte man stattdessen für δ die Selektion auf die dritte Komponente gewählt, hätte man Terminierung nur für eine kleinere Menge zulässiger Parameter zeigen können, nämlich z.B. für Parametertripel (xl,el,ix) mit ix ≥ 0.


3. fun foo (m,n) =


P ist die Menge aller Paare (m,n) aus int * int mit (m < n und n ≠ 0) oder n > 0


δ : Z x Z IN mit 0 , falls m < n δ ( m,n ) = m-n+1, falls m ≥ n

Zu zeigen:

i) (m-n,n) ist ein zulässiger Parameter : ok.

ii) Unter der Voraussetzung m ≥ n und n > 0 :

1. Fall: m-n ≥ n :

δ (m-n,n) = m-n-n+1 < m-n+1 = δ (m,n)

2. Fall: m-n < n :

δ (m-n,n) = 0 < m-n+1 = δ (m,n)


Bemerkung:

• Terminierungsbeweise sind bei der Entwicklung von Qualitätssoftware sehr wichtig, und zwar unabhängig vom verwendeten Modellierungs- bzw. Programmierparadigma.

• Es sollte zur Routine der Softwareentwicklung, gehören, den zulässigen Parameterbereich festzulegen und dafür Terminierung zu zeigen.

Documents

3.1.5 Signaturen und Strukturen€¦ · ML-Module heißen Strukturen und fassen Datentyp- und Funktionsdeklarationen zusammen. Jede Struktur besitzt eine Signatur, die angibt,