Streams

Beschreibung des Datentyps

Streams (Ströme) sind potentiell unendliche Daten. In einem Programmiersystem können sie nur dann repräsentiert werden, wenn man das Konzept der verzögerten Evaluation (lazy evaluation) verwendet. Anderenfalls würde sich eine Endlosschleife ergeben.

In der Tat kann man Prozeduren schreiben, die mit diesen unendlichen Objekten umgehen können. Um von einem stream ein beliebig langes Anfangsstück sehen zu können, brauchen wir eine Prozedur stream->list, die dieses Anfangsstück als Liste zurückgibt.

Klassische Anwendungsbeispiele sind Zahlenfolgen, die entweder endlich oder potentiell unendlich sind. Aus der Sicht der Informatik handelt es sich um aufzählbare Mengen, genauer: Listen.

Die Idee besteht darin, streams als Paar zu speichern. Das car-Element dieses Paares, enthält das erste Element des streams, beispielsweise das erste Glied einer Zahlenfolge. Das cdr-Element des Paares enthält den Reststream. Ebenso wie bei Listen, die aus einem Kopfglied und der sich anschließenden Restliste bestehen, handelt es sich auch hier um eine rekursive Datenstruktur. Wir müssen lediglich dafür Sorge tragen, dass die Evaluation des Reststreams verzögert (aufgeschoben) wird.

Bei der Definition des Datentyps "stream" machen wir uns eine Analogie zum Datentyp "Liste" zunutze.

Selektoren

stream-car gibt das Kopfglied eines streams zurück. stream-cdr gibt den Reststream (ohne Kopfglied) eines streams zurück.

Konstruktor

stream-cons nimmt das Kopfglied und den Reststreams und gibt den daraus erzeugten stream zurück.

Prädikat

stream? erwartet einen Eingabewert und gibt \#t zurück, wenn es sich dabei um einen stream handelt, ansonsten \#f.

Um eine endliche Folge oder Liste in einen stream konvertieren zu können, benötigen wir zusätzlich den the-null-stream. Dies ist ein stream, der nur aus dem *the-end-of-stream-tag*, etwa der Zeichenkette "eos", besteht. Dies führen wir hier jedoch nicht weiter aus. Eine endliche Zahlenfolge wird durch einen (unendlichen!) stream definiert, der ab einer gewissen Stelle nur noch aus dem the-null-stream besteht.

Implementation

Wie beginnen mit den Selektoren und denken immer daran, einen stream als Paar darzustellen. delay sorgt für das "Einschläfern" der Evaluation und force weckt sie wieder auf (bzw. erzwingt sie).

stream-cdr ist nicht ganz so einfach, denn ein schlichtes cdr würde nur den eingeschläferten Reststream leifern. Wir müssen ihn also noch zum Leben erwecken.

Noch schwieriger wird es bei stream-cons. Wenn wir uns den zukünftigen Aufruf (stream-cons head tail) vorstellen, dann würde der Reststream tail evaluiert werden noch bevor er (in stream-cons) eingeschläfert werden kann. Das in Scheme eingebaute Evaluationskonzept sorgt dafür, dass bei einer Prozeduranwendung alle Argumente evaluiert werden, bevor sie ihrer bestimmungsgemäßen Verarbeitung zugeführt werden.

Bei Sonderformen, wie beispielsweise define, ist das anders. Ein vorgebbares Muster wird nur durch textuelle Ersetzung (vgl. copy and paste) transformiert. Unser Wunschergebnis lautet (cons head (delay tail)). Sonderformen definiert man mit define-syntax. Schlagen Sie im Manual die Einzelheiten nach.

Nun können wir die neuen Sprachelemente schon einmal erproben. Wir möchten einen Zufallsstream erzeugen, dessen Elemente natürliche Zahlen zwischen 0 und 100 sind. Solche Zufallszahlen liefert random.

Hilbertbus