13 Sprachunterstützung für Algebraische Datentypen

Wie wir in Datendefinition durch Alternativen und Zerlegung: Algebraische Datentypen und Rekursive Datentypen gesehen haben, sind algebraische Datentypen essentiell zur Strukturierung von komplexen Daten. Ähnlich dazu wie Signaturen und Datendefinitionen unterschiedlich gut durch Sprachmittel unterstützt werden können (Sprachunterstützung für Datendefinitionen und Signaturen), gibt es auch bei algebraischen Datentypen Unterschiede darin, wie gut diese von der Programmiersprache unterstützt werden.

Wir werden uns vier verschiedene Arten anschauen, wie man algebraische Datentypen ausdrücken kann und diese im Anschluss bewerten.

Zu diesem Zweck betrachten wir folgende Datendefinitionen für arithmetische Ausdrücke:

Als "Interface" für den Datentyp wollen wir die folgende Menge von Konstruktoren, Destruktoren und Prädikaten betrachten:

; Number -> Expression

; constructs a literal exression

(define (make-literal value) ...)

; Expression -> Number

; returns the number of a literal

; throws an error if lit is not a literal

(define (literal-value lit) ...)

; [X] X -> Bool

; returns #true iff x is a literal

(define (literal? x) ...)

; Expression Expression -> Expression

; constructs an addition expression

(define (make-addition lhs rhs) ...)

; [X] X -> Bool

; returns #true iff x is an addition expression

(define (addition? x) ...)

; Expression -> Expression

; returns left hand side of an addition expression

; throws an error if e is not an addition expression

(define (addition-lhs e) ...)

; Expression -> Expression

; returns right hand side of an addition expression

; throws an error if e is not an addition expression

(define (addition-rhs e) ...)

Wir werden nun unterschiedliche Arten betrachten, wie wir diesen Datentyp repräsentieren können.

13.1 ADTs mit Listen und S-Expressions

Wie in S-Expressions diskutiert, können verschachtelte Listen mit Zahlen, Strings etc. – also S-Expressions – als universelle Datenstruktur verwendet werden. Hier ist eine Realisierung der Funktionen von oben auf Basis von S-Expressions:

(define (make-literal n)

(list 'literal n))

(define (literal-value l)

(if (literal? l)

(second l)

(error 'not-a-literal)))

(define (literal? l)

(and

(cons? l)

(symbol? (first l))

(symbol=? (first l) 'literal)))

(define (make-addition e1 e2)

(list 'addition e1 e2))

(define (addition? e)

(and

(cons? e)

(symbol? (first e))

(symbol=? (first e) 'addition)))

(define (addition-lhs e)

(if (addition? e)

(second e)

(error 'not-an-addition)))

(define (addition-rhs e)

(if (addition? e)

(third e)

(error 'not-an-addition)))

> (make-addition    (make-addition (make-literal 0) (make-literal 1))    (make-literal 2))

(addition (addition (literal 0) (literal 1)) (literal 2))

> (calc (make-addition          (make-addition (make-literal 0) (make-literal 1))          (make-literal 2)))

3

Beachten Sie, dass der Code von calc in keiner Weise von der Repräsentation der Ausdrücke abhängt, sondern lediglich auf Basis des Interfaces definiert wurde.

13.2 ADTs mit Strukturdefinitionen

In dieser Variante verwenden wir Strukturdefinitionen, um das obige Interface zu implementieren. Wir haben die Namen so gewählt, dass sie mit denen, die durch define-struct gebunden werden, übereinstimmen, deshalb können wir in zwei Zeilen das gesamte Interface implementieren:

(define-struct literal (value))

(define-struct addition (lhs rhs))

Allerdings haben wir durch define-struct nun eine neue, komfortablere Möglichkeit, um algebraische Datentypen zu verarbeiten, nämlich Pattern Matching (Pattern Matching):

(define (calc e)

(match e

[(addition e1 e2) (+ (calc e1) (calc e2))]

[(literal x) x]))

> (make-addition    (make-addition (make-literal 0) (make-literal 1))    (make-literal 2))

#(struct:addition   #(struct:addition #(struct:literal 0) #(struct:literal 1))   #(struct:literal 2))

> (calc (make-addition          (make-addition (make-literal 0) (make-literal 1))          (make-literal 2)))

3

13.3 ADTs mit define-type

(define-type Expression

(literal (value number?))

(addition (left Expression?) (right Expression?)))

Analog zu define-struct (Strukturdefinitionen) definiert define-type für jede Alternative Konstruktor-, Selektor- und Prädikatsfunktionen, so dass wir Werte dieses Typs auf die gleiche Weise definieren können:

> (make-addition    (make-addition (make-literal 0) (make-literal 1))    (make-literal 2))

#(struct:addition   #(struct:addition #(struct:literal 0) #(struct:literal 1))   #(struct:literal 2))

Allerdings wird bei Aufruf der Konstruktoren überprüft, ob die Felder die dazugehörige Prädikatsfunktion erfüllen. Der folgende Aufruf, der bei der define-struct Variante ausgeführt werden könnte, schlägt nun zur Laufzeit fehl:

> (make-addition 0 1)

make-addition: expects an undefined or a Expression, given 0   in: the 1st argument of       (->        (or/c undefined? Expression?)        (or/c undefined? Expression?)        addition?)   contract from: make-addition   blaming: use    (assuming the contract is correct)   at: eval:13:0

Passend zu define-type gibt es auch eine Erweiterung von match, nämlich type-case. Mit Hilfe von type-case kann die calc Funktion nun wie folgt definiert werden:

(define (calc e)

(type-case Expression e

[literal (value) value]

[addition (e1 e2) (+ (calc e1) (calc e2))]))

> (calc (make-addition          (make-addition (make-literal 0) (make-literal 1))          (make-literal 2)))

3

Der wichtigste Unterschied zwischen match und type-case ist, dass der Typ Expression, auf dem wir eine Fallunterscheidung machen möchten, explizit mit angegeben wird. Dies ermöglicht es der DrRacket Umgebung, bereits vor der Programmausführung zu überprüfen, ob alle Fälle abgedeckt wurden. Beispielsweise wird die folgende Definition bereits vor der Ausführung mit einer entsprechenden Fehlermeldung zurückgewiesen.

> (define (calc2 e)     (type-case Expression e       [addition (e1 e2) (- (calc2 e1) (calc2 e2))]))

type-case: syntax error; probable cause: you did not include a case for the literal variant, or no else-branch was present

Der Preis für diese Vollständigkeitsüberprüfung ist, dass type-case nur ein sehr eingeschränktes Pattern Matching erlaubt. Beispielsweise ist es nicht erlaubt, Literale, verschachtelte Pattern, oder nicht-lineares Pattern Matching zu verwenden. Im Allgemeinen haben die Klauseln von type-case stets die Form ((variant (name-1 ... name-n) body-expression)), wobei in body-expression die Namen name-1 bis name-n verwendet werden können.

13.4 Ausblick: ADTs mit Zahlen

Ist es auch möglich, algebraische Datentypen zu repräsentieren, wenn man weder Listen/S-expressions noch define-struct oder define-type zur Verfügung hat, sondern der einzige eingebaute Datentyp (natürliche) Zahlen sind? Diese Frage ist von großer Bedeutung in der theoretischen Informatik, denn dort möchte man häufig möglichst minimale und einfache Rechenmodelle definieren, die dennoch prinzipiell mächtig genug wären, um beliebige Programme darin auszudrücken. Es spielt hierbei in der Regel keine Rolle, ob diese Techniken praxistauglich oder effizient sind. Wichtig ist nur, ob eine Kodierung prinzipiell möglich ist. Der Grund, wieso die Rechenmodelle möglichst minimal sein sollen, ist der, dass dann leichter wichtige Eigenschaften dieser Rechenmodelle analysiert und bewiesen werden können.

Beispielsweise ist es in vielen Rechenmodellen wichtig, ob es eine Art universelles Programm gibt, das die Repräsentation eines Programms als Eingabe bekommt und dann dieses Programm quasi simuliert. In der BSL wäre dies beispielsweise ein Programm, welches eine Repräsentation eines BSL Programms als Eingabe bekommt und dann die Ausführung dieses Programms simuliert. Ein solches Programm nennt man auch Selbstinterpreter. In der theoretischen Informatik kommen solche Konstruktionen häufig vor, beispielsweise bei der sogenannten Universellen Turing-Maschine, im Normalformtheorem in der Theorie rekursiver Funktionen, beim sogenannten "Halteproblem", und im Beweis der Unvollständigkeitstheoreme von Gödel. Als Anerkennung der Beiträge von Kurt Gödel werden solche Repräsentationstechniken in der Berechenbarkeitstheorie auch "Gödelisierung" genannt. All diese Rechenmodelle haben gemein, dass Zahlen quasi der einzige eingebaute Datentyp sind.

Bevor wir algebraische Datentypen durch Zahlen repräsentieren, überlegen wir uns erstmal einen Spezialfall: Wie können wir ein Paar von zwei Zahlen, beispielsweise 17 und 12, durch eine einzelne Zahl repräsentieren? Eine Idee wäre, die Zahlen in Dezimalrepräsentation hintereinander zu schreiben: 1712. Aber woher wissen wir dann, dass 17 und 12 gemeint waren und nicht etwa 1 und 712 oder 171 und 2? Eine Lösung hierzu wäre, als Trennzeichen bestimmte Zahlenfolgen zu wählen, die in den Zahlen selbst nicht vorkommen dürfen. Wir werden eine andere Technik wählen, die von Kurt Gödel vorgeschlagen wurde und die auf der Eindeutigkeit der Primfaktorzerlegung beruht.

Die Eindeutigkeit der Primfaktorzerlegung sagt aus, dass jede Zahl eindeutig in ihre Primfaktoren zerlegt werden kann. Wenn die Primzahlen durch p_1,p_2,\ldots bezeichnet werden, so bedeutet dies, dass es für jede natürliche Zahl n eine Zahl k sowie Zahlen n_1,\ldots,n_k gibt, so dass n = p_1^{n_1} \cdot p_2^{n_2} \cdot \ldots \cdot p_k^{n_k} . Beispielsweise kann die Zahl 18 zerlegt werden in 18 = 2^1 \cdot 3^2.

Aufgrund der Eindeutigkeit der Primfaktoren könnten wir beispielsweise Paare mit Hilfe der ersten beidem Primzahlen, 2 und 3, repräsentieren. Beispielsweise könnten die Zahlen 17 und 12 von oben durch die Zahl 2^{17} \cdot 3^{12} = 69657034752 repräsentiert werden. Um die beiden Zahlen wieder zu extrahieren, berechnen wir, wie häufig sich die Zahl ohne Rest durch 2 bzw. 3 teilen lässt.

Diese Idee können wir durch folgendes Programm ausdrücken:

; Nat Nat -> Nat

; computes how often n can be divided by m

(define (how-often-dividable-by n m)

(if (zero? (modulo n m))

(add1 (how-often-dividable-by (/ n m) m))

0))

> (how-often-dividable-by 69657034752 2)

17

> (how-often-dividable-by 69657034752 3)

12

Offensichtlich können durch Nutzen von mehr Primzahlen mit der gleichen Technik beliebig lange Listen von (natürlichen) Zahlen durch eine einzelne Zahl repräsentiert werden. Verschachtelte Listen, also quasi S-Expressions, können durch Verschachtelung der gleichen Kodierungstechnik repräsentiert werden. Wollen wir beispielsweise ein Paar von zwei Paaren repräsentieren und n_1 ist die Kodierung des ersten Paars und n_2 die Kodierung des zweiten Paars, so kann das Paar der beiden Paare durch 2^{n_1} \cdot 3^{n_2} repräsentiert werden.

Bleibt noch die Frage, wie wir Summentypen repräsentieren. Hierzu können wir einfach für jede Variante disjunkte Mengen von Primzahlen nehmen.

Auf Basis dieser Idee können wir nun das Interface für den Expression Datentyp implementieren:

(define prime-1 2)

(define prime-2 3)

(define prime-3 5)

(define (make-literal value) (expt prime-1 value))

(define (literal-value l) (how-often-dividable-by l prime-1))

(define (make-addition e-1 e-2)

(* (expt prime-2 e-1)

(expt prime-3 e-2)))

(define (addition-lhs e)

(how-often-dividable-by e prime-2))

(define (addition-rhs e)

(how-often-dividable-by e prime-3))

(define (addition? e)

(zero? (modulo e prime-2)))

(define (literal? e)

(or (= e 1) (zero? (modulo e prime-1))))

Auch Funktionen wie die calc Funktionen funktionieren weiterhin auch auf Basis dieser ADT Repräsentation:

(define (calc e)

(cond [(addition? e) (+ (calc (addition-lhs e))

(calc (addition-rhs e)))]

[(literal? e) (literal-value e)]))

> (calc e-1)

3

13.5 Diskussion

Die unterschiedlichen Möglichkeiten, algebraische Datentypen (ADTs) zu unterstützen, unterscheiden sich in wichtigen Eigenschaften. Im folgenden bezeichnen wir die Variante ADTs mit Listen und S-Expressions als a), ADTs mit Strukturdefinitionen als b), ADTs mit define-type als c), und ADTs mit Zahlen als d).

• Boilerplate: Gibt es in der Art, wie ADTs kodiert werden, Verstöße gegen das DRY-Prinzip? Solchen Code nennt man boilerplate code. Bei a) und d) haben wir solchen boilerplate code, denn die Konstruktoren, Destruktoren und Prädikate müssen manuell auf eine mechanische Art und Weise implementiert werden.

• Unterscheidbarkeit der Alternativen: Können die Alternativen bei Summentypen stets unterschieden werden? Bei b) und c) bekommen wir durch die Sprache eindeutige Prädikate geliefert, mit denen wir die Alternativen unterscheiden können. Bei a) und d) muss der Programmierer diszipliniert genug arbeiten um diese Eigenschaft sicherzustellen.

• Erweiterbarkeit der Summen: Können Summen leicht um weitere Alternativen erweitert werden? Ein Beispiel wäre, dass der Typ für arithmetische Ausdrücke von oben noch durch eine Alternative zur Multiplikation von zwei arithmetischen Ausdrücken erweitert werden soll. Mit "erweitert" ist gemeint, dass hierzu keine Modifiktion von bestehendem Code erforderlich ist. Bei den Varianten a), b) und d) können wir leicht weitere Alternativen zu der jeweiligen Repräsentation des ADTs hinzufügen, beispielsweise in der Variante b) durch Definition einer weiteren Struktur. Allerdings werden bestehende Programme, die solche ADTs als Eingabe bekommen, in der Regel nicht korrekt auf diesen erweiterten ADTs arbeiten, denn sie berücksichtigen den hinzugekommenen Fall nicht. Es ist auch nicht ohne weiteres möglich, ohne Modifikation dieser Programme die Funktionalität für den hinzugekommenen Fall hinzuzufügen. Dieses und ähnliche Erweiterungsprobleme werden unter dem Namen "Expression Problem" in vielen wissenschaftlichen Artikeln diskutiert. Die Variante c) hingegen ist eine "geschlossene" Kodierung eines ADTs: Alle Alternativen werden an einer Stelle definiert, daher ist eine Erweiterung um weitere Alternativen ohne Modifikation von Code nicht ohne weiteres möglich.

• Erweiterbarkeit der Produkte: Können Produkte leicht um weitere Komponenten erweitert werden? Ein Beispiel wäre, dass die Alternative für Literale noch um eine weitere Zahl erweitert werden soll, welche aussagt, dass die Zahl nur eine Annäherung an die genaue Zahl ist und die zweite Zahl gibt an, wie präzise die Annäherung ist. In der Variante a) können wir Produkte leicht dadurch erweitern, dass wir die Listen länger machen. Auf eine ähnliche Weise können wir auch in der Variante d) die Produkte erweitern. In den Varianten b) und c) hingegen ist die Anzahl der Komponenten (die "Arität") der Konstruktoren in den Struktur- bzw. Typdefinitionen festgelegt und diese läßt sich nicht ohne Modifikation des bestehenden Codes erweitern.

• Typsicherheit: Ist sichergestellt, dass die Datendefinition vom Programm eingehalten wird? Bei den Varianten a) und d) gibt es keinerlei Unterstützung für Typsicherheit; falls Daten konstruiert werden, die gegen die Datendefinition verstossen, so wird dies weder vor der Programmausführung noch während der Konstruktion sondern erst möglicherweise im weiteren Verlauf der Programmausführung festgestellt. Bei b) wird zumindest sichergestellt, dass den Konstruktoren die korrekte Anzahl von Parametern übergeben wird (Arität). Diese Prüfung findet, je nach Sprachvariante, schon vor der Programmausführung (BSL) bzw. während der Ausführung des Konstruktors (ISL) statt. Bei der Variante c) hingegen wird eine Variante von Contracts verwendet (siehe Dynamisch überprüfte Signaturen und Contracts), um während der Konstruktion der Daten zu überprüfen, ob die Komponenten zur Datendefinition passen.

• Vollständigkeit von Fallunterscheidungen: Wird sichergestellt, dass Fallunterscheidungen bei Summentypen alle Möglichkeiten berücksichtigen? Die einzige Variante, die die Vollständigkeit vor der Programmausführung überprüfen kann, ist c). Dies ist ein wichtiger Vorteil, der daraus resultiert, dass ADTs in dieser Variante "geschlossen" sind.

• Zeit- und Platzeffizienz: Ist die Kodierung von ADTs effizient bezüglich des Platzbedarfs zur Repräsentation der Daten im Speicher sowie bezüglich des Zeitbedarfs zur Konstruktion und Destruktion (Analyse) von ADTs? Effizienz ist kein wichtiges Thema in dieser Lehrveranstaltung, aber die Variante d) fällt aus diesen Grund für praktische Anwendungen aus.

• Datentyp-generische Programme: Ist es möglich, Programme zu schreiben, die mit jedem algebraischen Datentyp funktionieren, wie beispielsweise eine Funktion, die zu einem Wert, der einen beliebigen algebraischen Datentyp hat, die Tiefe des Baums berechnet? Bei universellen Datenformaten wie S-Expressions ist dies leicht, während es nicht offensichtlich ist, wie man dies bei mittels define-struct oder define-type definierten ADTs hinbekommen könnte. Datentyp-generische Programmierung, insbesondere für statisch getypte Sprachen, ist ein sehr aktiver Zweig in der Programmiersprachenforschung.

13.6 Ausblick: ADTs mit Dictionaries

Eine wichtige Datenstruktur, die es in fast allen Programmiersprachen gibt, sind dictionaries, manchmal auch bezeichnet als associative array, map, oder hash table. Dictionaries repräsentieren partielle Funktionen mit einer endlichen Definitionsmenge (den sog. keys); jedem key wird also maximal ein Wert zugeordnet. Eine gängige Notation für Dictionaries ist JSON, die JavaScript Object Notation. Eine Person mit Namen und Vornamen könnte in JSON beispielsweise so aufgeschrieben werden:

Beispielsweise könnten die arithmetischen Ausdrücke von oben auch durch Dictionaries repräsentiert werden:

Dictionaries spielen in einer Reihe von Programmiersprachen eine zentrale Rolle und werden als universelle Datenstruktur im Sinne von S-Expressions verwendet, beispielsweise in JavaScript, AWK, Lua, Python, Perl und Ruby. Unter dem Schlagwort "NoSQL" gibt es auch eine Reihe von Datenbanktechnologien, in denen Dictionaries eine zentrale Rolle spielen.

Ein Interpreter für arithmetische Ausdrücke, die als Dictionaries repräsentiert werden, kann beispielsweise in JavaScript wie folgt aussehen:

Bezüglich der Diskussion in Diskussion verhalten sich dictionary-repräsentierte ADTs ähnlich wie S-Expressions. Einige Sprachen, wie beispielsweise Python, verwenden statt der Dot-Notation die Notation e[’lhs’]. Ein wichtiger Vorteil gegenüber S-Expressions ist, dass der Zugriff auf die Komponenten keinen "boilerplate" Code erfordert sondern mit Hilfe der "Dot-Notation" (wie e.lhs) effizient ausgedrückt werden kann.