BuK/IIm10/BuK-Kreativaufgabe03 G1

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
<language>Scheme</language>
=Streams=

<language>Scheme</language>
==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 <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.

==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).
<code id="4d9329c2dab7b">(define stream-car car)</code>
<run id="4d9329c2daf34"></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="4d9329c2dac0f">
(define stream-cdr
  (lambda (stm)
    (force (cdr stm))))
</code>
<run id="4d9329c2db005"></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''.
<code id="4d9329c2dace5">
(define-syntax stream-cons
  (syntax-rules ()
    ((_ head tail) (cons head (delay tail)))))
</code>
<run id="4d9329c2db0a2"></run>
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''.
<run id="4d932cdf921d6">(randomInt 101)</run>
Zur Erzeugung unseres Zufallsstreams definieren wir einen Generator, den wir ''random-stream-maker'' nennen.

<code id="4d932cdf92091">
(define random-stream-maker
  (lambda ()
    (stream-cons (randomInt 101) (random-stream-maker))))
</code>
<run id="4d9329c2db119"></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 id="4d9329c2dae06">(define rndstream random-stream-maker)</code>
<run id="4d932cdf92255">
(rndstream)
</run>
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:
<run id="4d932cdf922cd">(stream-car (rndstream))</run>
<run id="4d932cdf9236f">(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 id="4d932cdf92129">
(define stream->list
  (lambda (stm n)
    (if (<= n 0)
      '()
      (cons
        (stream-car stm)
        (stream->list (stream-cdr stm) (- n 1))))))
(stream->list (rndstream) 20)
</code>
<run id="4d9329c2db196"></run>

<language>Scheme</language>
==Einige Anwendungsbeispiele==
===Die Folge der natürlichen Zahlen===
<code id="4d9a1a6220edd">
(define nat-stream-maker
  (lambda (start)
    (stream-cons start (nat-stream-maker (+ start 1)))))
(define natstream (nat-stream-maker 0))
</code>
<run id="4d9a1a6220f76">
(stream->list natstream 30)
</run>

===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.
<code id="4d931d8009d30">
(define odd-stream-maker
  (lambda (stm)
    (stream-cons
      (+ 1 (* 2 (stream-car stm)))
      (odd-stream-maker (stream-cdr stm)))))
(define oddstream (odd-stream-maker natstream))
</code>
<run id="4d931d800a032">(stream->list oddstream 30)</run>
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.
<code id="4d931d8009d9d">
(define stream-map
  (lambda (stm proc)
    (stream-cons
      (proc (stream-car stm))
      (stream-map (stream-cdr stm) proc))))
</code>
<run id="4d931d800a0f3"></run>
Wir verwenden ''stream-map'' zur Erzeugung der Folge der geraden Zahlen.
<code id="4d931d8009e28">
(define evenstream (stream-map natstream (lambda (x)(* 2 x))))
</code>
<run id="4d931d800a190">(stream->list evenstream 30)</run>

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.

<code>
(define biject
 (lambda (n)
  (cond
    ((= n 1) 1)
    ((ist-gerade n) (+ 1 (biject (/ n 2))))
    (else (/ 1 (biject (- n 1)))))))

(define ist-gerade
 (lambda (n)
  (cond
   ((= 1 (modulo n 2)) #f)
   (else #t))))

(define rationalstream (stream-map (stream-cdr natstream) biject))
</code>

<run>
(stream->list rationalstream 5)
</run>

===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.
<code id="4d931d8009eb4">
(define stream+
  (lambda (stm1 stm2)
    (stream-cons
      (+ (stream-car stm1) (stream-car stm2))
      (stream+ (stream-cdr stm1) (stream-cdr stm2)))))
</code>
<run id="4d931d800a229">(stream->list (stream+ oddstream evenstream) 30)</run>
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 [http://www.veoh.com/watch/v68132393EgApqc2 Video] und dieser [http://opinionator.blogs.nytimes.com/2010/05/09/the-hilbert-hotel/ Artikel].