BuK-Kreativaufgabe03 G1
Aus ProgrammingWiki
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 Paare 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 zurück, wenn es sich dabei um einen stream handelt, ansonsten
.
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. Das Schlüsselwort 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.
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 randomInt.
Zur Erzeugung unseres Zufallsstreams definieren wir einen Generator, den wir random-stream-maker nennen.
In dieser Definition sieht man sehr gut, wie notwendig es ist, die Evaluation des zweiten Arguments von stream-cons zu unterdrücken.
Unseren Zufallsstream erhalten wir durch einen Aufruf des Generators.
Das Ergebnis lässt die Paarstruktur des streams gut erkennen. Das cdr-Element ist der Reststream, dessen Evaluation verzögert wird.
Wir können nach dem Kopfglied und dem Reststream von rndstream fragen:
Wiederholt man die Erzeugung des Zufallsstreams (in obigem Definitionsfeld), so erhält man im unmittelbar voranstehenden Evaluationsfeld einen anderen Wert. Erproben Sie das.
Obwohl stream->list nicht zu den Operationen gehört, die den Datentyp definieren, ist dessen Implementation an dieser Stelle sehr lehrreich. Zur Eingabe eines streams stm und einer natürlichen Zahl n werden die ersten n Elemente von stm ausgegeben.
Einige Anwendungsbeispiele
Die Folge der natürlichen Zahlen
Verwendung einer expliziten Bildungsvorschrift
Da Zahlenfolgen einstellige Funktionen sind, die eine natürliche Zahl als Argument erwarten, können wir Folgen durch Anwendung dieser definierende Funktion angeben. Hierzu brauchen wir die Folge der natürlichen Zahlen, die wir gerade bereit gestellt haben.
Wir illustrieren dies für die Folge der ungeraden Zahlen.
Interessiert man sich für die Folge der geraden Zahlen, so hätte man die vorletzte Definitionszeile von odd-stream-maker entsprechend abzuändern.
Dies lässt sich verallgemeinern, indem man sich an dieser Stelle irgendeine (prinzipiell geeignete) einstellige Prozedur vorstellt. Dies führt zu Definition von stream-map in Analogie zum eingebauten map.
Wir verwenden stream-map zur Erzeugung der Folge der geraden Zahlen.
Da das für alle einstelligen Prozeduren funktioniert, können wir hier auch die Prozedur zur Abbildung der natürlichen auf die rationalen Zahlen aus Übung 2 verwenden. Allerdings müssen wir darauf achten, nur die natürlichen Zahlen ohne 0 zu verwenden, da für diesen Fall keine Abbruchbedingung existiert.
Die Summe zweier streams
Mit streams kann man rechnen. Genauer gesagt: Wir definieren exemplarisch eine zweistellige Operation stream+, die zwei streams nimmt und den stream zurückgibt, der sich aus der gliedweisen Addition ergibt.
Wir demonstrieren die Anwendung von stream+ für die Summe der geraden und der ungeraden Zahlen.
Hilbertbus
Ein wirkliches Hotel verfügt über genau n, also endlich viele Zimmer, und bietet folglich Platz für höchstens n Gäste.
Dem sehr bekannten Mathematiker David Hilbert (23.01.1862-14.02.1943) verdanken wir die Geschichte von einem Hotel mit unendlich vielen Zimmern. Ein solches unendliches Hotel nennen wir Hilberthotel. Wie viele Gäste können in einem Hilberthotel untergebracht werden?
Die Zimmer des unendlichen Hotels werden fortlaufend durchnummeriert. Darüber hinaus verabreden wir, dass die Nummerierung mit der Zahl 0 beginnt. Zur Vereinfachung gehen wir hier davon aus, dass das Hotel ausschließlich über Einzelzimmer verfügt.
Zur Veranschaulichung dient dieses Video und dieser Artikel.
