Verzögerte Evaluation und Streams

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
<code id="4b04f53cbaeef" hidden>
(define stream-car car)
(define stream-cdr
  (lambda (stm)
    (force (cdr stm))))

;; Konstruktoren
(define-syntax stream-cons
  (syntax-rules ()
    ((_ head tail) (cons head (delay tail)))))

;; Praedikat
(define stream?
  (lambda (stm)
    (and (pair? stm)(promise? (cdr stm)))))

;; Operationen mit streams
(define make-stream 
  (lambda (seed proc)
    (letrec 
      ((stream-builder
         (lambda (n)
           (stream-cons n (stream-builder (proc n))))))
      (stream-builder seed))))

(define *the-end-of-stream-tag*
  (make-stream
   "eos"
   (lambda (str) str)))  

(define stream-item
  (lambda (str k)
    (if (= k 0)
      (stream-car str)
      (stream-item (stream-cdr str) (- k 1)))))

(define stream->list
  (lambda (str n)
    (if (<= n 0)
      '()
      (cons 
        (stream-car str) 
        (stream->list (stream-cdr str) (- n 1))))))

(define print-stream
  (lambda (str n)
    (cond
      ((<= n 0)(display "..."))
      (else
       (display (stream-car str))
       (display ", ")
       (print-stream (stream-cdr str) (- n 1))))))

(define stream-map
  (lambda (f str)
    (stream-cons
     (f (stream-car str))
     (stream-map f (stream-cdr str)))))    
</code>


[[Programmierparadigmen_-_Computerübungen|zur Übungsübersicht]]

==Hilfsprozeduren==
Die folgende Tabelle zeigt Ihnen Hilfsprozeduren, die Sie bei der Arbeit mit streams verwenden können. Machen Sie sich mit diesen Prozeduren vertraut.

{|border="1px"
!Bezeichnung!!Parameter!!Beschreibung
|-
|<tt>stream-car</tt>||stream||analog zu <tt>car</tt> 
|-
|<tt>stream-cons</tt>||stream||analog zu <tt>car</tt> 
|-
|<tt>stream?</tt>||parameter||testet, ob der Parameter ein Stream ist
|-
|<tt>make-stream</tt>||seed proc||gibt einen neuen Stream mit dem Anfangswert <tt>seed</tt> und der Prozedur <tt>proc</tt> zum Berechnen der Folgeglieder
|-
|<tt>stream->list</tt>||stream n||gibt eine Liste der ersten n Glieder des Streams
|-
|<tt>stream-item</tt>||stream n||gibt das n-te Element eines Streams zurück
|-
|<tt>stream-map</tt>||funktion stream||gibt einen Stream zurück, bei dem die Funktion auf alle Glieder des Streams angewendet wird 
|-
|}

Die im Folg. definierte Prozedur <tt>integer-stream-maker</tt> erzeugt einen Stream ganzer Zahlen, beginnend mit der als Argument übergebenen Zahl. Wir werden sie weiter unten benötigen.
<code id="4b04f53cbb6b2"> 
(define integer-stream-maker
   (lambda (from)
      (stream-cons from (integer-stream-maker (+ from 1)))))
(define integers (integer-stream-maker 0))
</code>

<run id="4b04f53cbf599">(stream->list integers 10)</run>

==Delay und Force==
Machen Sie sich mit den Sprachelementen <tt>delay</tt> und <tt>force</tt> vertraut. Diskutieren Sie zu zweit darüber, warum Streams in Scheme als Paare dargestellt werden, und erläutern Sie die Verbindung zu den oben genannten Sprachelementen.

Schreiben Sie eine Prozedur <tt>stream+</tt>, welche zwei streams mit Zahlen als Parameter nimmt und deren Werte paarweise bis zum n-ten Element addiert und als Liste zurückgibt.
          
<code id="4b04f53cbbe93">
(define stream+ 
  (lambda (stream1 stream2)
     ...
</code>
<run id="4b04f53cbfd67">(print-stream (stream+ integers integers) 5)
;0, 2, 4, 6, 8, ...
</run>

==Zahlenfolgen==
In den folgenden Aufgaben geht es um Zahlenfolgen. Folgende zwei Zahlenfolgen <math>(a_n)</math> und <math>(b_n)</math> sind gegeben:

<math>(a_{n})=0,\frac{1}{\sqrt{2 + \bf{0}}},
{\frac{1}{\sqrt{2 + \frac{1}{\sqrt{2 + 0}}}}},
{\frac{1}{\sqrt{2 + \frac{1}{\sqrt{2 + \frac{1}{\sqrt{2 + 0 }}}}}}},\ldots
</math>

<math>(b_{n})=0,\frac{1}{1 + 0},
{\frac{1}{1 + \frac{1}{1 + 0}}},
{\frac{1}{1 + {\frac{1}{1 + \frac{1}{1 + 0 }}}}},\ldots
</math>
       
Versuchen Sie das jeweilige Erzeugungsmuster in der jeweiligen Zahlenfolge zu erkennen. Beschreiben Sie die rekursive Gestalt dieser Ausdrücke.

'''Hinweis:''' Aus eigener Erfahrung weiß ich, dass es oft hilfreich ist, beim Programmieren einen Zettel und einen Stift parat zu haben, um sich einige Gedankengänge oder weiterführende Ideen zu notieren!
     
Implementieren Sie nun die oben definierten Zahlenfolgen mit Scheme unter Verwendung von Streams und Rekursion.

<code id="4b04f53cbc662">
(define an-stream-maker
  (lambda (start)
     ...
</code>
<run id="4b04f53cc055a">
(define an (an-stream-maker 0))
(print-stream an 5)
;0, 0.7071067811865475, 0.6077812620656623, 0.6192477250610301,0.6178907764054561, 0.6180508933676908, ...
</run>

<code id="4b04ff9684c74">
(define bn-stream-maker
  (lambda (start)
     ...
</code>
<run id="4b04ff9685466">
(define bn (bn-stream-maker 0))
(print-stream bn 5)
;0, 1, 1/2, 2/3, 3/5, 5/8, ...
</run>

==Grenzwerte== 
Schreiben Sie eine Prozedur <tt>grenzwert</tt>, die den Grenzwert einer Zahlenfolge bestimmt. Diese soll den Grenzwert <math>g</math> einer als Stream repräsentierten Zahlenfolge <tt>stm</tt> zurückgeben, wenn ab einem gewissen Index <math>i</math> sämtliche Folgenglieder in einer hinreichend kleinen <math>\varepsilon</math>-Umgebung (<tt>eps</tt>) von <math>g</math> liegen. Falls <tt>max</tt> Folgenglieder in dieser <math>\varepsilon</math>-Umgebung liegen, wird Konvergenz vermutet und <tt>#t</tt> zurückgegeben. Ist das nicht der Fall, muss der Prozeduraufruf per Hand abgebrochen werden.

<code id="4b04f53cbd5fe">
(define grenzwert 
  (lambda (stream epsilon max)
    ...
</code>

Ermitteln und vergleichen Sie die Grenzwerte der Zahlenfolgen <math>(a_{n})</math> und <math>(b_{n} )</math>.

<run id="4b04f53cc149c">(grenzwert an 1/1000 10)
;0.6180339887498196</run>
<run id="4b04f53cc1ce6">(grenzwert integers 1/10 10)  ; Achtung - break!</run>

<!-- 

Testen Sie ihre Grenzwert-Prozedur wenigstens mit folgenden Aufrufbeispielen. (Dabei wird nicht erwartet, dass Sie die Definition von tf wirklich verstehen):
<code id="4b04f53cbde45">
(define tf
   (let make ((start 0))
      (stream-cons (/ start (+ 1 start)) (make (+ 1 start)))))</code>

<run id="4b04f53cc249b">(grenzwert tf 1/110 10)</run>
<run id="4b04f53cc2c6c">(grenzwert tf 1/110 9)</run>
<run id="4b04f53cc3453">(grenzwert tf 1/111 11)</run>
<run id="4b04f53cc3b91">(grenzwert tf 1/111 10)</run>

 -->


==Eulersche Zahl==

<code id="4b05193aa89ae" hidden>
(define fak
  (lambda (n)
    (if (= n 0)
        1
        (* n (fak (- n 1))))))
</code>

Die Eulersche Zahl ist gegeben durch folgende Reihe
: <math>e = \sum_{k=0}^{\infty}{\frac{1}{k!}} = 1 + \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \frac{1}{4!} + \cdots</math>.

'''Hinweis:''' 0! = 1

Schreiben Sie eine Prozedur <tt>en</tt>, die die Folge <math>1,\frac{1}{1!}, \frac{1}{2!},\ldots</math> berechnet. Die Fakultätsprozedur ist in diesem Fall vordefiniert.

<code id="4b04f53cbe633">
(define en
  (stream-map ...
    ...)
</code>
<run id="4b04f53cc43be">
(print-stream en 5)
;1.0, 1.0, 0.5, 0.16666666666666666, 0.041666666666666664, ...
</run>

Die folgende Prozedur berechnet die n-te Partialsumme einer betrachteten Zahlenfolge.
<code id="4b05193aa9339">
(define ntepartialsumme
  (lambda (stm n)
    (if (= n 0)
        (stream-car stm)
        (+ (stream-car stm)(ntepartialsumme (stream-cdr stm) (- n 1))))))
</code>

Vergleichen Sie die 10. Partialsumme mit dem Wert für <math>e</math>:

<run id="4b05193aaa516">
(ntepartialsumme ... )
;2.7182818011463845
</run>
<run id="4b05193aaad61">
(exp 1)
</run>

Nun bilden wir die Partialsummenfolge:
<code id="4b05193aa9d74">
(define partialsummenfolge
  (lambda (stm)
    (stream-map ...
</code>

Schließlich fragen wir nach dem Grenzwert der Partialsummenfolge. Dieser beträgt <math>e</math>.

<run id="4b04f53cc5b25">(grenzwert (partialsummenfolge en) 1/100 10)</run>


[[Programmierparadigmen_-_Computerübungen|zur Übungsübersicht]]