BuK/IIm10/BuK-Kreativaufgabe03 G1

Wiki-Quelltext dieser Seite.

=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 <math>\#t</math> zurück, wenn es sich dabei um einen stream handelt, ansonsten <math>\#f</math>.

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.

<language>Scheme</language>
==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).
<code id="4d9317c14d24d">(define stream-car car)</code>
<run id="4d9317c14d3a1"></run>
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.
<code id="4d9317c14d2c2">(define stream-cdr
  (lambda (stm)
    (force (cdr stm))))
</code>
<run id="4d9317c14d470"></run>
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. 
<code id="4d9317c14d321">
(define-syntax stream-cons
  (syntax-rules ()
    ((_ head tail) (cons head (delay tail)))))
</code>
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.
<run id="4d9317c14d4f5">(random 101)</run>
Zur Erzeugung unseres Zufallsstreams definieren wir einen Generator, den wir
random-stream-maker nennen.
<code>
(define random-stream-maker
  (lambda ()
    (stream-cons (random 101) (random-stream-maker))))
</code>
<run></run>
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.
<code>(define rndstream (random-stream-maker</code>
<run>rndstream</run>
Das Ergebnis läßt 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:
<run>(stream-car rndstream)</run>
<run>(stream-car rndstream)</run>
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.
<code>
(define stream->list
  (lambda (stm n)
    (if (<= n 0)
      '()
      (cons
        (stream-car stm)
        (stream->list (stream-cdr stm) (- n 1))))))
</code>
<run>(stream->list rndstream 20)</run>
Würde man die Länge dieser Liste mit dem zweiten Argument von stream->list weiter erhöhen, wird die Ausgabezeilenbeschränkung überschritten. Dies führt zu unerwünschten Zeilenumbrüchen. Dies wird verhindert, indem wir dieses Limit deutlich anheben.
<run>
(begin
  (pretty-line-length 10000)
  (pretty-one-line-limit 10000))
</run>
Lassen Sie sich nun ein längeres Anfangsstück des Zufallsvektors anzeigen. Falls im Antwortfenster nur ein Teil der Liste sichtbar ist, kann sie im Monitor vollständig betrachtet werden.

Die Implementation des Prädikats stream? führen wir hier nicht weiter aus.

=Hilbertbus=