On this page:
13.1 ADTs mit Listen und S-Expressions
13.2 ADTs mit Strukturdefinitionen
13.3 ADTs mit define-type
13.4 Ausblick:   ADTs mit Zahlen
13.5 Diskussion
13.6 Ausblick:   ADTs mit Dictionaries

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:

Beispiel:
; An Expression is one of:
; - (make-literal Number)
; - (make-addition Expression Expression)
; interp. abstract syntax of arithmetic expressions

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)))

Auf Basis dieses Interfaces können nun Funktionen definiert werden, wie zum Beispiel ein Interpreter für die Ausdrücke:
(define (calc e)
  (cond [(addition? e) (+ (calc (addition-lhs e))
                          (calc (addition-rhs e)))]
        [(literal? e) (literal-value e)]))

> (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))

Auch in dieser Variante können wir nun wieder Funktionen auf Basis des Interfaces implementieren. Die calc Funktion aus dem vorherigen Abschnitt funktioniert unverändert mit der define-struct Repräsentation von algebraischen Datentypen:
(define (calc e)
  (cond [(addition? e) (+ (calc (addition-lhs e))
                          (calc (addition-rhs e)))]
        [(literal? e) (literal-value e)]))

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

Wechseln Sie zum Nutzen von define-type auf die "Intermediate Student Language".

Eine neue Möglichkeit, um algebraische Datentypen zu repräsentieren, bietet das 2htdp/abstraction Teachpack mit dem define-type Konstrukt. Im Unterschied zu define-struct bietet define-type direkte Unterstützung für Summentypen, daher kann der Summentyp Expression mit seinen unterschiedlichen Alternativen direkt definiert werden. Ein weiterer wichtiger Unterschied zu define-struct ist, dass zu jedem Feld einer Alternative eine Prädikatsfunktion angegeben wird, die definiert, welche Werte für dieses Feld zulässig sind. Diese Prädikatsfunktionen sind eine Form von dynamisch überprüften Contracts (siehe Dynamisch überprüfte Signaturen und Contracts).

(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))))

Diese Kodierung ergibt sehr schnell sehr große Zahlen, daher ist sie nicht für praktische Zwecke brauchbar, aber sie funktioniert wie gewünscht:
> (define e-1 (make-addition (make-addition (make-literal 0) (make-literal 1)) (make-literal 2)))
> e-1

380166742320848568199802495386788316875

> (literal-value (addition-lhs (addition-lhs e-1)))

0

> (literal-value (addition-rhs (addition-lhs e-1)))

1

> (literal-value (addition-rhs e-1))

2

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).

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:

{ name: 'Ostermann', vorname: 'Klaus'}

In diesem Fall sind name und vorname die Keys und Ostermann und Klaus die jeweils zugeordneten Werte. Dictionaries sind wie Listen, bei denen die Elemente nicht durch ihre Position in der Liste sondern durch einen Key adressiert werden. Da Dictionaries genau wie Listen verschachtelt werden können, können Dictionaries ähnlich wie S-Expressions als universelle Datenstruktur verwendet werden.

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

{ kind: 'add', lhs: { kind: 'lit', val: 7}, rhs: { kind: 'lit', val: 12}};

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:

var calc = function (e) {

  switch (e.kind) {

    case 'lit': return e.val;

    case 'add': return calc(e.lhs)+calc(e.rhs);

  }

}

calc({ kind: 'add', lhs: { kind: 'lit', val: 7}, rhs: { kind: 'lit', val: 12}});

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.