3.7.2 Ströme

In diesem Kapitel besprechen wir die Datenstruktur der Ströme, auch Folgen genannt. Vorläufig können wir uns Ströme einfach als Listen vorstellen, bis verschiedene Überlegungen uns eine verfeinerte Repräsentation von Strömen abverlangen werden.

Ströme tauchen in vielen Gebieten der Informatik in der einen oder anderen Form auf. In jedem Fall dient das Konzept der expliziten Formulierung von strukturellen Ähnlichkeiten in einer großen Klasse von Programmen. Zusammen mit Strömen beobachten wir folgende Grundgedanken:

1. Komplexe Mechanismen oder Module sollen als Kombination (funktionale Komposition, Hintereinanderschaltung, usw.) einfacherer Mechanismen oder Module entstehen.

2. Rekursion, ein unvermeidbares Konzept, immer dann, wenn Ein- und Ausgaben sowie Rechenprozesse unbeschränkte Länge haben dürfen, soll implizit bleiben. D.h. gewisse vorgegebene Standardbausteine sind intern rekursiv definiert. Die externe Kombination der Standardbausteine aber ist selbst nicht rekursiv.

3. Kommunikation zwischen Modulen verläuft auf der Basis des Austauschens von Folgen von Informationseinheiten. Diese Folgen von Daten sind die Ströme. Uniformität des Aufbaus eines Systems wird verbessert, weil die Eingaben und Ausgaben aller Module von derselben Struktur, Ströme eben, sind.

Wir finden diese Idee z.B. im Betriebssystem UNIX. Hier hat jeder Prozeß eine Standardein- und eine Standardausgabe. Auf diesen Leitungen fließen Ströme von Zeichen, die der Prozeß liest bzw. ausgibt. Durch Verwendung einer ”pipe“ kann die Ausgabe eines Prozesses mit der Eingabe eines zweiten Prozesses verbunden werden. Komplexe Prozesse entstehen als Hintereinanderschaltung von einfacheren Prozessen. Wollten wir aus dem Systemwörterbuch alle mit ”a“ beginnenden Wörter suchen, so daß Wörter nach ähnlichen Endungen sortiert werden, wäre eine Lösung

  cat /usr/dict/words | rev | sort | rev | grep "^a" | pr -t -3 | more

”|“ ist der Kompositionsoperator ”pipe“. Die primitiven Funktionen sind cat (zur Erzeugung (Aufzählung) des Stroms, der aus der Konkatenation aller Parameterdateien, hier /usr/dict/words, besteht), rev (zum zeichenweisen Spiegeln aller Zeilen des Stroms), sort (zum alphabetischen Sortieren von Zeilen), grep (zum Ausfiltern aller Zeilen, die ein bestimmtes Muster enthalten, hier mit ”a“ beginnen), pr -t -3 (zum 3-spaltigen, seitenweisen Tabellieren von Strömen) und more (zum seitenweisen Ausgeben eines Stroms auf dem Bildschirm). Das Ergebnis dieses Kommandos wäre so etwas wie

                a         anamorphic       aseptic
                amoeba    anthropomorphic  apocalyptic
                alba      anorthic         aspartic
                armada    acyclic          anachronistic
                addenda   angelic          autistic
                agenda    alcoholic        atavistic
                anaconda  apostolic        agnostic
                althea    acrylic          acoustic
                azalea    aerodynamic      attic
                area      academic         aeronautic
                alfalfa   algorithmic      astronautic
                alga      astronomic       analytic

was ein Amateurdichter zum Finden von Reimen, z.B. ”apostolic“ auf ”alcoholic“, benutzen könnte.

Bei Strömen spielt es keine Rolle, ob man sich bei Kombination p|q von p und q hintereinander oder parallel ausgeführt denkt. Üblicherweise benötigt q nicht seine gesamte Eingabe auf einmal, um Teilberechnungen anstellen zu können. Damit macht es Sinn, p und q parallel zu starten. Da p seinen Ausgabestrom elementweise produziert und q seine Eingabe elementweise und sequentiell liest, muß q aber dann warten, wenn es das nächste Element seines Eingabestromes lesen will, p aber dieses noch nicht produziert hat, d.h. die ”pipe“ zwischen p und q leer ist. Diese Form der Kommunikation zwischen parallelen Prozessen ist grundlegend, und daher spielen Ströme von Kommunikationseinheiten eine wichtige Rolle bei der mathematischen Modellierung sowie bei Spezifikation und Programmierung kommunizierender, parallel ablaufender Prozesse.

Wie gesagt sind Programme hier meist nichtrekursive Kombinationen von primitiven Bausteinen und damit nur implizit rekursiv. Implizite Rekursion hat den Vorteil, daß wir weitgehend die Probleme induktiven Schließens von Programmeigenschaften vermeiden können und mit algebraischen Gesetzen auskommen. Desweiteren bekommt man garantierte Terminierung aller Programme dann, wenn die vorgegebenen primitiven Elemente garantiert terminieren.

Literatur. Abelson, H. und Sussman, G.J.: Structure and Interpretation of Computer Programs, MPI Press, 1985.

Bird, R. und Wadler, Ph.: Introduction to Functional Programming, Prentice Hall, 1988.

Homomorphismen auf Strömen. Ströme sind immer endliche oder unendliche Folgen von Daten (von beliebigem Typ α). Die verschiedenen Ansätze unterscheiden sich darin, von welchen algebraischen Eigenschaften von Strömen ausgegangen wird. Wir wollen hier von einer sehr einfachen Struktur von Strömen ausgehen, wie sie durch die Operationen

                     Nil: α stream
                     Cons: α ∗ α stream → α stream
                     head: α stream → α
                     tail: α stream → α stream

repräsentiert wird. Dann werden endliche Ströme [e_{1} e_{2} … e_{n}] durch Ausdrücke der Form

   Cons(e_{1},Cons (e_{2}, . . ., Cons(e_{n},Nil). . .))

berechnet.^{1} Zunächst nehmen wir, wie bereits gesagt, an, daß Ströme wie Listen realisiert sind.

   datatype 'a stream = Nil
                     | Cons of 'a * 'a stream;
   fun head(Cons(x, )) = x;
   fun tail(Cons( ,xs)) = xs;

Später wollen wir besser geeignete Realisierungen besprechen, wenn wir einmal gesehen haben, wie typischerweise mit Strömen programmiert wird.

Eine wichtige Beobachtung ist, daß die meisten Programme, die Ströme als Eingabe akzeptieren, in einfacher, syntaxorientierter Weise ihr Ergebnis berechnen. Algebraisch formalisiert bedeute ”einfach“, daß das Programm einen Homomorphismus berechnet. Ein Homomorphismus h von Strömen in einen Typ β, repräsentiert durch eine Konstante a vom Typ β und eine binären Funktion ⊕ : α ∗ β → β, ist eine Abbildung h : α stream → β, gegeben durch die Gleichungen

                              h(Nil) = a

h(Cons(e, s)) = e ⊕ h(s) .

Ein Homomorphismus h ist also durch Angabe von ⊕ und a eindeutig bestimmt. Da man sich die Arbeitsweise von h als ein Reduzieren der Ströme von rechts her vorstellen kann,

h([e_{1}e_{2} … e_{n}]) = e_{1} ⊕ (e_{2} ⊕ … ⊕ (e_{n} ⊕ a) …)),

nennen wir die entsprechende Funktion foldr von ”fold right“ (in korrekter SML-Notation mit einem Identifikator f anstelle des Symbols ⊕):

   - fun foldr   a Nil      = a
       | foldr f a Cons(x,xs) = f(x, (foldr f a xs));
   val foldr = fn : ('a * 'b -> 'b) -> 'b -> 'a stream -> 'b

Als einfache, mit foldr berechnete Homomorphismen seien die folgenden genannt:

   fun sum s = foldr op+ 0 s;

sum berechnet die Summe aller Elemente eines Stroms von Zahlen. Hier ist a = 0 und ⊕ = +. Analog wird das Produkt der Elemente durch

   fun product s = foldr op* 1 s;

berechnet. Das Maximum der Elemente eines Stroms nichtnegativer Zahlen erhalten wir mit

   fun max element s = foldr max 0 s;

Die allen drei Anwendungen gemeinsame Rekursionsstruktur wird von derjenigen in foldr erfaßt. Die Definition von sum, product und max-element sind selbst nicht rekursiv.

1Für Ströme mit den Elementen e_{1}, …, e_{n} benutzen wir die Notation [e_{1} … e_{n}], wie wir sie auch für Listen verwenden.

Oftmals haben auch Funktionen auf Zahlen diese Homomorphismenstruktur, wenn man z.B. natürliche Zahlen n als Ströme [1 2 … n] repräsentiert. Hier wird die Funktion

   fun interval a b =
       if a>b then Nil else Cons(a,interval (1+a) b);

gebraucht, die das Intervall [a, b] als Strom der ganzen Zahlen zwischen a und b codiert. Jetzt können wir auch Funktionen, wie die Fakultät, als Funktion auf Strömen sehen,

   fun fac n = product (interval 1 n);

also als das Produkt der ganzen Zahlen im Intervall [1, n].

Um Programme auf Strömen wie in UNIX ”pipe“-artig komponieren zu können, müssen häufig genug Ströme auch als Resultate von Programmen auftreten.

Eine wichtige Funktion ist map, die wir schon bei Listen verwendent haben, und welche jetzt eine Funktion f auf alle Elemente eines Stroms anwendet und den Strom der Ergebnisse zurückliefert. Die Definition von map durch

   - fun map f s = foldr (fn (x,xs) => Cons((f x),xs)) Nil s;
   val map = fn : ('a -> 'b) -> 'a stream -> 'b stream

zeigt, daß auch map ein Homomorphismus ist, für jedes f. Dabei ist das ⊕ im wesentlichen ein Cons, nur werden die ursprünglichen Stromelemente x in f(x) übersetzt.

   fun sum squares n =
      let square x = x*x
       in sum (map square (interval 1 n))
      end;

berechnet die Summe ∑_{i=1}^{n} i^{2} der Quadrate von 1 bis n.

- sum_squares 5;
val it = 55 : int

Neben map, der Fortsetzung einer Abbildung von Elementen auf Ströme, ist das Filtern von Strömen durch ein Prädikat eine häufig vorkommende Teilaufgabe. Um auch filter als Familie von Homomorphismen zu erkennen, brauchen wir noch eine Operation für Ströme, mit ++ bezeichnet, die, wie das append bei Listen, seine Argumente konkateniert:

   fun ++ s1 s2 = foldr Cons s2 s1;

++ ist also, für jedes feste s2, ein Homomorphismus.

Algebraisch betrachtet spricht einiges dafür, wenn man Ströme mit den Konstruktoren

               Nil :  α stream
               ++ :  α stream ∗ α stream → α stream
               singleton : α → α stream

einführt, wobei (singleton e) den Strom erzeugt, der e als einziges Element besitzt. ++ und Nil bilden eine Monoidstruktur. Die Konstruktion von Strömen über Cons wiederum hat den Vorteil, daß die Sequentalität der Elemente in Strömen und der auf ihnen operierenden Prozesse direkter zum Ausdruck kommt. Beide Sichtweisen von Strömen können leicht wechselweise ineinander überführt werden.

Kommen wir zum Problem des Filterns von Strömen durch ein Prädikat p zurück.

   fun filter p s =
      foldr ++ Nil
         (map (fn x => if p x then singleton x else Nil) s);
 wobei singleton aus Cons durch
   fun singleton e = Cons(e, Nil);

abgeleitet werden kann. filter produziert aus dem gegebenen Strom s zunächst einen Strom s' von Strömen. Dieser enthält als Elemente die einelementigen Ströme [x], für alle x in s, für die (p x) wahr ist. Die Elemente y, die p nicht erfüllen, werden durch die leeren Ströme unter den Elementen von s' repräsentiert. Konkatenieren wir alle Ströme von s', so erhalten wir den Strom der Elemente von s, die p erfüllen. Letzteres geschieht durch ein foldr mit ++ als Kombinator.

Auch konventionelle Datenverarbeitungsprobleme sind durch stromorientiertes Programmieren oft einfach zu lösen.

”Finde die Note des bzw. der besten diesjährigen Absolventen unter den Studenten“

kann man durch

   fun markOfBestStudent recordStream =
       foldr min
             4.3   ;; schlechteste Note, mit der man noch besteht
             (map mark
                  (filter graduatedThisYear recordStream)))

berechnen, wenn recordStream der Strom der Daten über die Studenten ist, aus dem graduatedThisYear die diesjährigen Absolventen herausfindet, und mark deren Note liest.

Fassen wir die bisher besprochenen Funktionen auf Strömen noch einmal zusammen:

1. Aufzählen von Strömen: z.B. interval. Im übernächsten Paragraphen werden wir komplexere Mechanismen zu diesem Zweck besprechen.

2. Elementweises Abbilden von Strömen: map

3. Filtern von Strömen: filter

4. Implizite Rekursion durch Anwendung eines Homomorphismus: foldr

5. Konkatenation von Strömen: ++

Abarbeitung von links. Homomorphismen mit foldr arbeiten Ströme von rechts her ab. Dies ist algebraisch schöner, aber oftmals nicht sehr effizient. Für unendliche Ströme, wie wir sie noch besprechen werden, ist diese Methode natürlich ungeeignet.

Selbst für endliche Ströme ist es oftmals effizienter, wenn man sie von links her abarbeitet, insbesondere dann, wenn für das Ergebnis nicht alle Elemente des Stroms inspiziert werden müssen. Die lineare Rekursion von foldr will immer erst das Ende des Stromes finden, bevor irgendwelche Bestandteile des Ergebnisses berechnet werden. map und filter können neu programmiert werden, so daß sie von links her arbeiten:

   val Consq = Cons;
   fun map f Nil = Nil
     | map f xs  = Consq(f (head xs),map f (tail xs));
   fun filter p Nil = Nil
     | filter p xs =
       let val x = head xs
       in
          if p x
             then Consq(x,filter p (tail xs))
             else filter p (tail xs)
       end;

Wir verwenden ab jetzt absichtlich kein Cons mehr, und verzichten damit auch auf Cons-Muster, sondern arbeiten stattdessen mit head und tail sowie Consq (welches zunächst identisch mit cons ist), um der späteren Realisierung unendlicher Ströme vorzubauen.

Das Analogon zu foldr ist foldl. Es berechnet

foldl ⊕ a [e_{1}e_{2} … e_{n}] = (… (a ⊕ e_{1}) ⊕ e_{2}) ⊕ …) ⊕ e_{n})

und wird wie folgt definiert

   fun foldl f a Nil = a
     | foldl f a xs = foldl f (f(a,head xs)) (tail xs);
   val foldl = fn : ('a * 'b -> 'a) -> 'a -> 'b stream -> 'a

pack berechnet den Wert der durch eine Ziffernfolge gegebenen Dezimalzahl:

   fun pack xs = foldl (fn (n,x) => 10*n+x) 0 xs;
   - pack (interval 1 3);
   val it = 123 : int

Die endständige Rekursion von foldl, die sich in effizienter Weise in Schleifen übersetzen läßt, wird im folgenden dafür sorgen, daß die auf foldl aufbauenden Funktionen selbst im wesentlichen endständig rekursiv sind.

Zwischen foldl und foldr bestehen Zusammenhänge, gennant Dualitätsgesetze.

Proposition 1 Seien a, ⊕ und ⊗ so, daß

x ⊕ (y ⊗ z) = (x ⊕ y) ⊗ z
x ⊕ a = a ⊗ x

für alle x, y, z gilt. Dann ist

foldr ⊕ a xs = foldl ⊗ a xs  (1)

für alle endlichen Ströme xs.

Eine unmittelbare Folge hiervon ist:

Proposition 2 Bildet ⊕ und a ein Monoid, so ist

foldr ⊕ a xs = foldl ⊗ a xs  (2)

Dieses klärt den Zusammenhang zwischen foldl und foldr:

Proposition 3 Es gilt

                   foldr ⊕ a xs = foldl ⊕^{−} a (reverse xs)  (3)

für alle endlichen Ströme xs, wobei ⊕^{−} durch x ⊕^{−} y = y ⊕ x gegeben sei.

Wir verwenden diese Gesetze für einen Beweis von

                        reverse(reverse(xs)) = xs,

der keine explizite Induktion benötigt. Sei dazu

   fun prefix (xs,x) = Consq(x,xs);
   val reverse = foldl prefix Nil;

Die so definierte reverse-Funktion entspricht der nichtnaiven Variante mit endständiger Rekursion. Es ist prefix^{−} = cons, damit gilt wegen des zweiten Dualitätsgesetzes

            foldr Consq Nil xs = foldl prefix Nil (reverse xs)

und die Behauptung folgt aus der Tatsache, daß

                         xs = foldr Consq Nil xs.

Die Induktion ist versteckt in der Induktion, die man braucht, um die Dualitätsgesetze nachzuweisen.

Zum Abschluß einige Merksätze:

• foldl ist die endständig rekursive Variante von foldr und damit zumeist effizienter.

• Für Monoide (⊕, a) sind beide gleich. Die Verwendung von foldl entspricht einer automatischen Entrekursivierung.

• Weitgehend variablenfreie Programmierung durch Verwendung der Kombinatoren

     map, filter, foldl, foldr, ++.

• Algebraische Gesetze zwischen Kombinatoren wie z.B. die obigen Dualitätsgesetze, erlauben induktionsloses Verifizieren gewisser Programmeigenschaften.

Diese Aspekte ist besonders ausgearbeitet in der Backus-Sprache FP [?] und im sogennanten ”Bird/Meertens-Formalismus“ [?].

Aufzählen von Mengen und Multimengen. Eine weitere Anwendung der Ströme in der funktionalen Programmierung ist nahe verwandt zu einer wichtigen Technik des logischen Programmierens, bei der eine Menge (bzw. ein Prädikat) definiert wird, indem zunächst eine Grundmenge aufgezählt wird und dann die Elemente herausgefiltert werden, die das die Menge definierende Prädikat erfüllen. In der Mathematik schreiben wir ja genau nach dieser Methode Komprehensionsausdrücke

M = { x ∈ G | p(x) },

wenn wir eine Menge M aller Elemente x einer bereits gegebenen Grundmenge G, die die Eigenschaft p(x) besitzen, definieren wollen. In Prolog könnten wir dann schreiben

   'M'(X) :- 'G'(X), p(X).

G generiert die Grundmenge, p filtert diese nach der M charakterisierenden Eigenschaft. Wir sagen auch, G zählt den Suchraum auf, und p schränkt ihn auf die zu M gehörigen Werte ein.

Das Schema, welches wir hier anbieten wollen, ist etwas allgemeiner. Es basiert auf der Idee der abhängigen Produkte (”dependent types“) von Multimengen. Multimengen sind Strukturen wie Mengen, außer daß Elemente mehrfach auftreten können. Wie bei Mengen ist die Reihenfolge des Auftretens irrelevant. Mengen sind Spezialfälle von Multimengen. Wir wollen Multimengen^{2} der Form

M = [ f(x_{1}, …, x_{n}) | x_{1} ∈ M_{1}, p_{1}(x_{1}),
x_{2} ∈ M_{2}(x_{1}), p_{2}(x_{1}, x_{2}),
x_{3} ∈ M_{3}(x_{1}, x_{2}), p_{3}(x_{1}, x_{2}, x_{3}),
…
x_{n} ∈ M_{n}(x_{1}, …, x_{n−1}), p(x_{1}, …, x_{n}), ]

betrachten, wobei

• f eine n-stellige Funktion,

• M_{1}, M_{2}(x_{1}), M_{3}(x_{1}, x_{2}), …, M_{n}(x_{1}, …, x_{n−1}), n (bereits gegebene) Multimengenfamilien und

• die p_{i} i-stellige (gegebene) Prädikate sind, die weggelassenwerden, wenn sie trivial sind.

(Wir nehmen hierbei an, daß gewisse elementare Multimengen auf andere Weise, z.B. durch Aufzählung ihrer Elemente, vgl. interval, definiert werden.) Die Besonderheit der abhängigen Produkte ist, daß der i-te Faktor M_{i} von den Elementen der i − 1 vorangehenden Faktoren abhängig sein darf. Beispiele für Multimengen sind

pairs(k) = [ (i, j) | i ∈ [1, k], j ∈ [i + 1, k] ]

als die Menge aller Paare (i, j) mit 1 ≤ i ≤ k und i < j ≤ k, oder

triples(k) = [ (i, j, i + j) | i, j ∈ [1, k], j ∈ [1, i − 1] ]

2Zur Unterscheidung der Multimengen von Mengen benutzen wir eckige Klammern zu ihrer Notation.

Also, M = [x ∈ G | p(x)] sei die Multimenge M aller Elemente x der Multimenge G, die p(x) erfüllen.

als eine Menge von Tripeln, in der die dritte Komponente die Summe der beiden ersten ist. Daß das zweite Beispiel in die Klasse der hier betrachteten Multimengen fällt, ergibt sich mit n = 2, f(i, j) = (i, j, i + j), M_{1} = [1, k], M_{2}(i) = [1, i − 1], p = true.

In einigen funktionalen Programmiersprachen, wie z.B. Haskell oder Miranda, gibt es vordefinierte Notationen für solche Multimengenkomprehensionen. In SML können wir uns diese durch folgendes einfache, rekursive Übersetzungsschema herstellen:

[ x | x ∈ xs] = xs
[ f x | x ∈ xs] = map f xs
[ e | x ∈ xs, px, …] = [ e | x ∈ filter p xs, …]
[ e | x ∈ xs, y ∈ ys, …] = concat [ [ e | y ∈ ys, …] | x ∈ xs]

wobei concat definiert ist als

   val concat = foldl op++ Nil

und alle Elemente eines Strom von Strömen konkateniert.

Betrachten wir ein Beispiel, bei dem wir die Primzahlen unter den Summen von je zwei Zahlen im Intervall [1, k] ausrechnen wollen:

primeSum(k) = [ (u, v, u + v) | u ∈ [1, k], v ∈ [1, u − 1], u + v prim ]

Die Übersetzung hiervon ergibt

[ (u, v, u + v) | u ∈ [1, k], v ∈ [1, u − 1], prime (u+v) ]

= concat [ [ (u, v, u + v) | v ∈ [1, u − 1], prime (u+v) ] | u ∈ [1, k] ]
= concat [ [ (u, v, u + v) | v ∈ (filter (fn v => prime (u+v)) [1, u − 1]) ] | u ∈ [1, k] ]
= concat ([ P u | u ∈ [1, k] ])

 = concat (map P [1, k])

wobei P die Funktion

   fun P u = map (fn v => (u,v,u+v))
                 (filter (fn v => prime (u+v)) [1, u-1])

Mittels interval können wir das Ganze wie folgt aufschreiben:

   fun primeSum k =
   let fun P u = map (fn v => (u,v,u+v))
                     (filter (fn v => prime (u+v)) (interval 1 (u-1)))
       in concat (map P (interval 1 k))
   end;
- primeSum 6;

((2 1 3) (3 2 5) (4 1 5) (4 3 7) (5 2 7) (6 1 7) (6 5 11))

Wie wir den Primzahltest prime programmieren können, z.B. durch Aufzählung des Stromes aller Primzahlen, werden wir im nächsten Abschnitt sehen.

Daß es uns möglich ist, so komplexe Konstruktionen, wie die Multimengenkomprehensionen nur mit map, filter, ++ und foldr (für concat) zu simulieren, zeigt die Mächtigkeit, die man durch Kombination dieser elementaren Elemente erzielen kann. Andererseits kann man wohl feststellen, daß gerade die logische Komplexität der Mengenkomprehensionen eine gute Motivation dafür ist, daß eine geeignete Notation hierfür in jeder funktionalen Programmiersprachen vorgegeben sein sollte. Wer möchte schon primeSum, ein noch relativ harmloses Beispiel, so ”zu Fuß“ programmieren müssen.

Implementierung von Strömen. Bisher haben wir die Vorstellung propagiert, Ströme seien Listen. Die Verwendung von Strömen in der Praxis zeigt, daß diese Implementierung oft sehr ineffizient ist. Oftmals fließen nur wenige Elemente eines Stromes in das Endergebnis einer Rechnung ein. Wenn dann der Strom sehr lang ist, werden viele Elemente umsonst berechnet. Ein zweites Problem ist, daß bei Verwendung der stromorientierten Programmiertechnik ein komplexes Programm zumeist eine Komposition von recht vielen einfachen Funktionen ist. An der Schnittstelle zwischen je zwei Funktionen entstehen aber Ströme als Zwischenergebnis, die bei der Listensichtweise vollständig im Listenspeicher des Lisp-Systems abgelegt werden müssen.

Ein einfaches Beispiel kann beide Probleme illustrieren.

   fun secondPrimeSquareIn a b =
      head (tail (map square
                      (filter prime
                              (interval a b)))))

welches wir, unter Verwendung der polymorphen Komposition o von Funktionen

   infix o;
   fun o (f,g) = (fn x => f(g x));

die in dieser Weise bereits vordefiniert ist, kürzer und ”kombinatorischer“ als

   fun secondPrimeSquareIn a =
       head o (tail o ((map square) o ((filter prime) o (interval a))));

schreiben können. secondPrimeSquareIn berechnet das Quadrat der zweiten Primzahl im Intervall [a, b], wenn [a, b] mindestens 2 Primzahlen enthält. Der Aufruf

- secondPrimeSquareIn 34 100000

1681

produziert sein Ergebnis, nachdem 3 große Ströme als Zwischendatenstrukturen erstellt worden sind, wobei zusätzlich zumindest das Filtern auf Primzahleigenschaft sehr rechenaufwendig für jede große Zahl des ersten Stroms ist. Letztlich werden aber nur zwei Primzahlen wirklich gebraucht. Ad hoc hätte man das Beispielproblem vielleicht so programmiert:

   fun secondPrimeSquareIn a b =
       let nthPrimeSquareIn a b n =
          if a>b then error "Intervall erschoepft"
          else if prime a
                 then if n=1
                      then square a
                      else nthPrimeSquareIn (1+a) b (n-1)
                 else nthPrimeSquareIn (1+a) b n)

        in nthPrimeSquareIn a b 2
   end;

Dieses Programm braucht nur einen kleinen konstanten Speicher^{3} und eine kleine Laufzeit, wenn a nicht zu groß ist.

Natürlich kann man eine Methode, wie die der Programmierung mit Strömen, nicht dann propagieren, wenn sie zu derart dramatischen Verschlechterungen im Laufzeitverhalten und Speicherverbrauch führt. Was kann man also tun, um Ströme so zu realisieren, daß der Überhang in bezug auf Komplexität nur einen konstanten Faktor ausmacht? Eine Idee ist die der verzögerten Auswertung von Strömen. Ströme sollen nur soweit berechnet werden müssen, wie ihre Elemente auch tatsächlich von den Funktionen, die den Strom als Eingabe lesen müssen, gebraucht werden. Im Beispiel haben wir die Folge

   head o (tail o ((map square) o ((filter prime) o (interval a))))

von stromproduzierenden bzw. -konsumierenden Funktionen. Vom Strom, der Eingabe für tail ist, brauchen wir nur die ersten zwei Elemente. Um die von map berechnen zu lassen, braucht map seinerseits nur die ersten zwei Elemente seiner Eingabe. Also muß filter nur solange laufen, bis es in seiner Eingabe die ersten zwei Primzahlen gefunden hat, und mehr Eingaben muß interval nicht generieren.

Im allgemeinen muß erst dann das erste Element, und erstmal nur dieses, eines Stroms berechnet werden, wenn mit head darauf zugegriffen wird oder wenn mit tail zum Reststrom übergegangen wird.

Ein Standardtrick, um in SML, wo immer alle Argumentausdrücke einer Applikation ausgewertet werden, bevor die Auswertung des Funktionsrumpfes stattfindet, die Auswertung zu verzögern, ist das Einpacken eines Ausdrucks in einen λ-Ausdruck. Ist also e ein Ausdruck, so vermeidet man seine Auswertung dadurch, daß man stattdessen

        (fn () => e)

schreibt. Aus einem Wert wird hierdurch eine parameterlose Funktion, die genau diesen Wert als Ergebnis liefert. Mathematisch betrachet ist da kein Unterschied. Operational gesehen ist (fn () => e), im Gegensatz zu e nur ein Versprechen, den Wert von e zu berechnen, wann immer man es möchte.

Wie wir schon gesehen haben, wird ein λ-Ausdruck wird nur dann reduziert, wenn er linker Operand einer Applikation ist und die gesamte Applikation dann β-reduziert wird. Einen Auswertungswunsch äußert man daher, indem man (fn () => e) aufruft, also z.B. (fn () => e) () oder x() schreibt, wenn x eine Variable, z.B. Funktionsparameter, ist, an die (fn () => e) gebunden ist.

Dieses Erzwingen der Auswertung wollen wir augenfälliger machen, indem wir eine Funktion force definieren, die durch

   fun force x = x ()

gegeben sei. Entsprechend sei (delay e) von nun an immer als eine Abkürzung für (fn () => e) gebraucht, so daß bereits der Name uns den Grund für das Einpacken von e andeutet. Wohlgemerkt, wir können nicht, im Gegensatz zu force, delay als eine Funktion, etwa durch

   dun delay e = (fn () => e)

3Man beachte, daß die Prozedur endständig rekursiv ist, also einen iterativen Prozeß erzeugt.

programmieren. Jeder Aufruf (delay e) würde ja gerade den mit delay beabsichtigten Zweck zunichtemachen und e auswerten, bevor der sich ergebende Wert dann überflüssigerweise in ein lambda eingepackt wird. delay ist also als ein Makro zu verstehen. In Lisp wäre sowas unproblematisch, da praktisch jedes Lisp-System hat ein Makro-Konzept, schon aus den Gründen, die wir gerade besprechen. Im Falle von SML müssen wir uns oft anders selbst behelfen.

Nichtleere Strömen sollen wieder durch (Cons h t) erzeugt werden. Eine verzögernde Berechnung des Stroms erhalten wir, wenn unser Datentyp streams so geändert wird:

   datatype 'a stream = Nil
                      | Cons of 'a * (unit -> 'a stream);

Zudem legen wir fest, daß im folgenden

   Consq(h,t)

als Abkürzung für

   Cons(h,delay t)

und damit für

   Cons(h,(fun () => t))

steht. Damit ergibt sich klarerweise

   fun head Cons(h, ) = h;
   fun tail Cons( ,t) = force t;

Mit dieser neuen Realisierung der Operationen auf Strömen werden immer nur soviele Elemente eines Stromes wirklich ausgerechnet werden, wie durch aufeinandefolgende tail-Aufrufe erzwungen wird.^{4}

Einen erheblichen Nachteil unserer Neuimplementierung von Strömen wollen wir nicht verschweigen. Es kann jetzt vorkommen, daß ein Element eines Stromes mehrfach berechnet wird, dann nämlich, wenn mehrfach mit tail auf dasselbe Reststück zugegriffen wird. Jedesmal erfolgt dann ja ein force. Dies kann durch Verwendung der Memotechnik vermieden werden, die mithilfe von Zeigervariablen einmal berechnete Werte abspeichert und bei jedem weiteren Aufruf auf diese zurückgreift.

Damit diese Implementierung greift, müssen wir einige der grundlegenden Funktionen neu schreiben. Für concat, was wir bei der Realisierung von Multimengenkomprehensionen verwendet haben, schreiben wir

   fun concat Nil = Nil
     | concat(Cons(Nil,ss)) = concat (ss ())
     | concat(Cons(Cons(x,xs),ss)) =
              Consq(x,concat(Cons(xs(),ss)));

map, filter, interval usw. funktionieren richtig unter der neuen Interpretation von Consq. Man beachte aber auch, daß concat bei einem Strom ss mit unendlichen Strömen als Elementen unfair konkateniert: Elemente eines Stromes die hinter einen unendlichen Element in ss stehen, können mit keiner endlichen Folge von tail-Aufrufen aus concat(ss) extrahiert werden. Man sollte stattdessen concat so schreiben, daß das bekannte Zickzack-Schema, mit dem man z.B. zeigt, daß N ∗ N abzählbar ist, geeignet verallgemeinert wird (Übung!). Da hierbei die Reihenfolge der Stromelemente, je nach Implementierung von concat, unvorhersehbar ist, haben wir im Zusammenhang mit Komprehension von Multimengen, und nicht von Listen gesprochen.

4Tatsächlich ist es bei nichtleeren Strömen immer ein Element mehr als es aufeinanderfolgende tail-Aufrufe gibt, das berechnet wird.

Unendliche Ströme. Interessanterweise vermeidet unsere neue Realisierung von Strömen nicht nur, daß Elemente, die zur Berechnung des Endergebnisses einer Anwendung nicht gebraucht werden, nicht berechnet werden, sie erweitert auch das logische Konzept der Ströme. Wenn ein Strom potentiell unendlich ist, aber in jeder Verwendung des Stromes nur endlich viele Anfangselemente inspiziert werden müssen, so haben wir jetzt keine Terminierungsprobleme. Der Strom der Zahlen im rechtsoffenen Intervall [a, ∞[ ist durch

   fun integersFrom a = Consq(a,integersFrom (1+a))

in Lisp nun wohldefiniert, jeder Aufruf, etwa

- integersFrom 2

val it = Cons (2,fn) : int stream

produziert ja zunächst nur das erste Element des unendlichen Stroms, zusammen mit der Vorschrift zur Berechnung der weiteren Elemente. Im Beispiel steht fn für einen λ-Ausdruck mit dem Rumpf integersFrom (1+a) in dem die freie Variable a an 2 gebunden ist.

Auf unendlichen Strömen können wir auch Funktionen programmieren, die unendliche Ströme als Ergebnisse liefern. Die elementweise Addition von zwei Strömen ist ein Beispiel.

   fun addStreams(Nil,s2) = s2
     | addStreams(s1,Nil) = s1
     | addStreams(Cons(x1,s1), Cons(x2,s2)) =
                  Consq(x1+x1:int,addStreams(s1(),s2()));

Eine Anwendung hiervon wäre eine Neudefinition der Fibonnacci-Zahlen, diesmal als Strom.

   val fibs =
     let fun fibs1 () =
       Consq(0,
             Consq(1,
                  addStreams(fibs1 (),tail (fibs1 ()))))
     in fibs1 ()
   end;

(Leider können wir nicht einfach

   val fibs =
       Consq(0,
             Consq(1,
                   addStreams(fibs,tail fibs)));

schreiben, weil val-Definitionen nicht rekursiv sind.)

- fibs;
val it = Cons (0,fn) : int stream
- tail it;
val it = Cons (1,fn) : int stream
- tail it;
val it = Cons (1,fn) : int stream
- tail it;
val it = Cons (2,fn) : int stream
- tail it;
val it = Cons (3,fn) : int stream
- tail it;
val it = Cons (5,fn) : int stream

Hier wird in der Terminologie von Strömen ausgesagt, daß, bis auf die Anfangselemente 0 und 1, jedes Element der Folge der Fibonnacci-Zahlen sich als die Summe der beiden vorhergehenden berechnet. Addieren wir den Strom der Fibonnacci-Zahlen mit sich selbst um eins nach links verschoben, so erhalten wir die Folge der Fibonnacci-Zahlen ab ihrem dritten Element aufwärts. Daß das SML-Programm funktioniert liegt daran, daß immer, wenn addStreams(f,(tail f) mit irgendeinem Rest f der Fibonnacci-Zahlen ausgeführt wird, man die ersten beiden Elemente von f, und damit auch das erste Element von (tail f), bereits berechnet hat. Nur diese beiden Elemente werden gebraucht, um das erste Element von addStreams(f,(tail f) zu berechnen.

Als abschließenden Beispiel wollen wir den Primzahltest nach der Methode des Siebs des Eratosthenes stromorientiert programmieren. Wir definieren dazu die Folge aller Primzahlen. Diese ist rekursiv so aufgebaut, daß jedes Endstück der Folge möglichst viele ganze Zahlen in aufsteigender Reihenfolge enthält, die nicht durch ihr erstes Element teilbar sind, dieses natürlich ausgenommen. Erfüllt wirklich jedes Endstück einer Folge ansteigender Zahlen diese Eigenschaft und soll der Strom mit 2 beginnen, so muß der Strom tatsächlich gerade alle Primzahlen enthalten. Wir benötigen hierzu die Standardfunktion remainder, die den Rest bei ganzzahliger Division liefert.

   fun sieve n =
       Consq(n,filter (fn x => not(x mod n = 0))
                      (sieve (1+n)));
   val primes = sieve 2;

Der Nachteil dieser Definition ist, daß jede Zahl mit allen kleineren Primzahlen auf Unteilbarkeit getestet wird. Folgende Lösung kommt mit erheblich weniger solchen Tests aus. Hier sind die Primzahlen primes diejenigen ganzen Zahlen ≥2, die prim sind. Die Primzahleigenschaft prime? einer Zahl testet man, indem man sie durch alle kleineren Primzahlen zu teilen versucht. Wichtig ist nun hierbei zu wissen, daß man für jede Zahl n nur Teiler kleiner oder gleich \sqrt{n} testen muß. Denn ist n eine Primzahl, so ist sie kleiner als das Quadrat der nächstkleineren Primzahl. Mit dieser Erkenntnis kann man primes1 und den Test prime in gegenseitiger Abhängigkeit definieren.

   fun primes1 () = Consq(2,filter prime (integersFrom 3))
   and
       prime n =

let fun iter ps =
    if (square (head ps)) > n then true
    else if (n mod (head ps)) = 0 then false
    else (iter (tail ps))        (*)
in iter (primes1 ())
end;
val primes = primes1 ();

Daß diese gegenseitige Rekursion wohlfundiert ist, liegt also an dem zahlentheoretischen Zusammenhang p_{n+1} < p_{n}^{2} für die Folge p_{i} der Primzahlen. Man kann sich daher sicher sein, daß man nicht mehr Primzahlen aus primes in (*) anfordert, als es solche unterhalb von n gibt.