Seite 3: Abstraktion, Monaden

Inhaltsverzeichnis

Abstraktion einführen

Mit der DSL lassen sich komplette DB-Programme schreiben. Eine häufige Anforderung ist allerdings auch, mehrere Programmfragmente getrennt voneinander zu erstellen und später zusammensetzen zu können. Ein praktisches Fragment könnte sein, einen Eintrag zu inkrementieren:

let inc (k: key) =
  Get (k, fun v -> Put (k, v + 1, ???))

Das letzte Feld vom Put, in dem stehen müsste, wie es im Anschluss weitergeht, fehlt, da es noch nicht bekannt ist. Die einzige Option ist, dort Done einzutragen:

let inc (k: key) =
  Get (k, fun v -> Put (k, v + 1, Done v))

Auf die Weise entsteht ein Fragment, wobei die Frage offen bleibt, wie es sich mit anderen zusammensetzen lässt.

Soll es nach dem inc-Fragment weitergehen, ist das Done zu ersetzen. Der Eintrag sollte am besten abhängig von dem Wert sein, den es zurückgibt. Dazu dient die folgende Funktion splice, die rekursiv alle Get und Put absteigt, bis sie auf ein Done stößt. Dort wendet sie eine Funktion f auf das Ergebnis an:

let rec splice (m: 'a t) (f: 'a -> 'b t): 'b t =
  match m with
  | Put (k, v, c) -> Put (k, v, splice c f)
  | Get (k, cont) -> Get (k, fun v -> splice (cont v) f)
  | Done v -> f v

Im jetzigen Zustand lässt sich inc mit anderen Programmfragmenten kombinieren. Beispielsweise inkrementiert das folgende Programm den Eintrag "new" und schreibt dessen vorherigen Wert in den Eintrag "old":

splice (inc "new") (fun v -> Put ("old", v, Done ()))
 

(Das () ist in OCaml so etwas wie void in Java – ein Wert, der nichts aussagt.)

Der gleiche Trick wie bei inc funktioniert auch bei get und put:

let get (k: key): value t = Get (k, fun v -> Done v)
let put (k: key) (v: value): unit t = Put (k, v, Done ())
 

Außerdem ist es möglich, Done den etwas eingängigeren Namen return zu geben:

let return v = Done v
 

Zudem lässt sich in OCaml für splice ein Infix-Operator >>= definieren:

let (>>=) = splice
 

Damit können Entwickler das Programm wie folgt gestalten:

get "x1" >>= fun x1 ->
get "x2" >>= fun x2 ->
put "r" (x1 + x2) >>= fun () ->
return (x1, x2)
 

Zu lesen ist der Code so: Lies "x1" aus und nenne den Wert x1, lies "x2" aus und nenne den Wert x2, schreibe das Ergebnis in "r" und liefere schließlich x1 und x2 als Ergebnis.

Monaden und Dependency Injection

Wer mit dem Konzept vertraut ist, wird erkennen, dass splice und return die Operationen sind, die Monaden ausmachen. (splice ist oft als bind oder flatMap bekannt, return auch als unit.) Monaden sind eine Art Allzweckwaffe der funktionalen Programmierung und oft als schwer verständlich verschrien. Im Beispiel entstehen sie einfach aus dem Bedürfnis, eine DSL zu entwickeln, mit der sich sequenzielle Programme schreiben lassen, bei denen Nachfolgeoperationen Zwischenergebnisse weiterverarbeiten können.

Um Dependency Injection durchführen zu können, fehlt nun noch eine andere Implementierung der Datenbank. Die folgende arbeitet mit Assoziationslisten, also Listen aus Schlüssel/Wert-Paaren:

let rec run_with_alist (al: (key * value) list) (p: 'a t): 'a =
  match p with
  | Put (k, v, next) ->
     run_with_alist ((k, v)::al) next
  | Get (k, cont) ->
     run_with_alist al (cont (List.assoc k al))
  | Done v -> v

((k, v)::al) fügt der Assoziationsliste al ein Paar aus Schlüssel k und Wert v hinzu, List.assoc schlägt einen Eintrag nach.