Verzögerte Evaluation und Streams-Loesung

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 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||äquivalent zu <tt>car</tt> 
|-
|<tt>stream-cons</tt>||stream||äquivalent 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>

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

==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.
          
 Aufrufbeispiel:
 > (stream->list (stream+ integers integers) 5)
 0, 2, 4, 6, 8, ...
<code id="4b04f53cbbe93">
(define stream+ 
  (lambda (stream1 stream2)
     ...
</code>
<eval id="4b04f53cbfd67">(stream->list (stream+ integers integers) 5)
0, 2, 4, 6, 8, ...
</eval>


==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})=\frac{1}{\sqrt{2 + \color{red}{0}}},
{\frac{1}{\sqrt{2 + {\frac{1}{\sqrt{2 + 0}}} }}},
{\frac{1}{\sqrt{2 + {\frac{1}{\sqrt{2 + \frac{1}{\sqrt{2 + 0 }}} }}} }}
</math>

<math>(b_{n})=\frac{1}{\sqrt{1 + \color{red}{0}}},
{\frac{1}{1 + {\frac{1}{1 + 0}} }},
{\frac{1}{1 + {\frac{1}{1 + \frac{1}{1 + 0 }}} } }
</math>
       
Versuchen Sie das rot hervorgehobene Erzeugungsmuster in der jeweiligen Zahlenfolge nachzuvollziehen.

'''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 zu notieren (es kommt manchmal vor, dass man eine gute Idee hat und eine Minute später wieder vergessen hat)!
     
===Implementation===   
Implementieren Sie nun die beiden Zahlenfolgen von oben in Scheme mit Hilfe von Streams und Rekursion.

'''Aufrufbeispiel''' für <math>$(a_{n})</math>:
 > (define an (an-stream-maker 0)))
 > (stream->list an 5)
 0.7071067811865475, 0.6077812620656623, 0.6192477250610301,0.6178907764054561, 0.6180508933676908, ...
<code id="4b04f53cbc662">;(an-stream-maker start)</code>
<eval id="4b04f53cc055a">
(define an (an-stream-maker 0)))
(stream->list an 5)
</eval>

'''Aufrufbeispiel''' für <math>$(a_{n})</math>:
 > (define bn (bn-stream-maker 0)))
 > (stream->list bn 5)
 1, 1/2, 2/3, 3/5, 5/8, ...
<code id="4b04f53cbce32">;(bn-stream-maker start )</code>
<eval id="4b04f53cc0d2d">
(define bn (bn-stream-maker 0)))
(stream->list bn 5)
</eval>

==grenzwert== 
Schreiben Sie eine Prozedur <tt>grenzwert</tt>, die den Grenzwert einer Zahlenfolge bestimmt. Diese soll wie folgt aussehen:

<tt>( grenzwert stm eps max )</tt>

Genauer gesagt soll diese Prozedur den Grenzwert einer als Stream repräsentierten Zahlenfolge <tt>stm</tt> zurückgeben, wenn dieser innerhalb einer hinreichend kleinen ε-
Umgebung <tt>(eps)</tt> liegt. Falls nicht max Folgenglieder in dieser ε-Umgebung liegen, wird Divergenz vermutet und <tt>#f</tt> zurückgegeben.

<code id="4b04f53cbd5fe">;(grenzwert stream epsilon maximum)</code>

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

<eval id="4b04f53cc149c">(grenzwert an 1/100 10)</eval>
<eval id="4b04f53cc1ce6">(grenzwert bn 1/100 10)</eval>

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>

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

==Zahlenfolge==
Erstellen sie einen STream der folgende Zahlenfolge implementiert:
<math>$(e_{n})=\frac{1}{0!},\frac{1}{1!},\frac{1}{2!},\frac{1}{3!},\frac{1}{4!},\frac{1}{5!},...,\frac{1}{n!}$</math>

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

'''Aufrufbeispiel''' für <math>$(e_{n})</math>
 > (define en (en-stream-maker 0)))
 > (stream->list en 5)
 11, 1, 1/2, 1/6, 1/24, ...
<code id="4b04f53cbe633">;Zahlenfolge en</code>
<eval id="4b04f53cc43be">(define en (en-stream-maker 0))
(stream->list en 5)</eval>



===Pasu Stream=== 
Schreiben Sie anschließend eine Prozedur <tt>pasu-stream</tt>, die eine Zahlenfolge als Stream nimmt und die zu dieser Zahlenfolge gehörende Partialsummenfolge als Stream zurückgibt. Falls diese Partialsummenfolge konvergiert, entspricht ihr Grenzwert der Summe der unendlichen Reihe
<math>\sum^\infty \limits_{i=0}\frac{1}{i!}=\frac{1}{0!},\frac{1}{1!},\frac{1}{2!},\frac{1}{3!}...</math> 

'''Aufrufbeispiel:'''
 > (stream->list (pasu-stream en) 5)
 1, 2, 5/2, 8/3, 65/24, ...

<code id="4b04f53cbedec">;(pasu-stream stream)</code>
<eval id="4b04f53cc507d"> (stream->list (pasu-stream en) 5)</eval>

Mit Hilfe der Prozeduren <tt>grenzwert</tt> und <tt>pasu-stream</tt> kann nun die Summe einer Reihe ermittelt werden.
<eval id="4b04f53cc5b25">(grenzwert (pasu-stream en) 1/10 10)</eval>
<eval id="4b04f53cc6300">(grenzwert (pasu-stream en) 1/100 10)</eval>
<eval id="4b04f53cc6a69">(grenzwert (pasu-stream en) 1/1000 10)</eval>

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