BuK-Kreativaufgabe03 G1
Inhaltsverzeichnis |
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.