Verzögerte Evaluation und Streams

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
<code 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>     
==Hilfsfunktionen==
Die folgende Tabelle zeigt ihnen Hilfsfunktionne die Ihnen bei der Arbeit mit streams helfen. Machen Sie sich mit desen Vertraut

{|border="1px"
!Bezeichnung!!Parameter!!Beschreibung
|-
|stream-car||stream||Äquivalent zu car nur für streams
|-
|stream-cons||stream||Äquivalent zu car nur für streams
|-
|stream?||parameter||Testet ob der parameter ein Stream ist
|-
|make-stream||seed proc||gibt einen neuen stream mit den Anfngswert seed und der zu funktion proc zum berechnen der Folgeglieder
|-
|stream->list||stream n||gibt eine Liste der ersten n Glieder des Streams
|-
|stream-item||stream n||gibt das n. Element eines Streams aus 
|-
|stream-map||funktion stream||gibt einen Stream zurück bei dem die Funktion auf alle glieder des Streams angewendet wird 
|}


Desweiteren sind folgende Definitionen als Hilfestellung gegeben:
<code> 
(define integer-stream-maker
   (lambda (from)
      (stream-cons from ( integer-stream-maker (+ from 1)))))
(define integers (integer-stream-maker 0))
</code>
<eval>(stream->list integers 10)</eval>

==Delay und Force==
Machen Sie sich mit den Sprachelementen delay und force vertraut. Diskutieren Sie zu zweit darüber, warum streams in Scheme als Paar dargestellt werden und die Verbindung zu den eben genannten Sprachelementen.

Schreiben Sie eine Prozedur stream+, 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>;(stream+ stream1 stream2)</code>
<eval>(stream->list (stream+ integers integers) 5)</eval>

==Zahlenfolgen==
In den folgenden Aufgaben wird es um Zahlenfolgen gehen. Folgende zwei Zahlenfolgen sind gegeben:

===(a von n)===
<math>$(a_{n})=
\frac{1}{\sqrt{2 + \textcolor{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>

===(b von n)===
<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>
       
Es gibt in diesen Zahlenfolgen einen “Fortschritt”. Versuchen Sie das Erzeugungsmuster 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)))
 > (print-stream an 5)
 0.7071067811865475, 0.6077812620656623, 0.6192477250610301,0.6178907764054561, 0.6180508933676908, ...
<code>;(an-stream-maker start)</code>
<eval>
(define an (an-stream-maker 0)))
(print-stream 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>;(bn-stream-maker start)</code>
<eval>
(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:<br />
<tt>( grenzwert stm eps max )</tt><br />

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.
                                       
Ermitteln und vergleichen Sie die Grenzwerte der Zahlenfolgen (an ) und (bn ).
Testen Sie ihre Grenzwert-Prozedur wenigstens mit folgenden Aufrufbeispielen.
(Dabei wird nicht erwartet, dass Sie die Definition von tf wirklich verstehen):
<code>( define tf
      ( let make (( start 0))
         ( stream - cons (/ start (1+ start )) ( make (1+ start )))))</code>

<eval>(grenzwert tf 1/110 10)</eval>
<eval>(grenzwert tf 1/110 9)</eval>
<eval>(grenzwert tf 1/111 11)</eval>
<eval>(grenzwert tf 1/111 10)</eval>


==Zahlenfolge==
<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)))
 > (print-stream en 5)
 11, 1, 1/2, 1/6, 1/24, ...

===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:'''
 > (print-stream (pasu-stream en) 5)
 1, 2, 5/2, 8/3, 65/24, ...

Mit Hilfe der Prozeduren <tt>grenzwert</tt> und <tt>pasu-stream</tt> kann nun die Summe einer
Reihe ermittelt werden.
'''Aufrufbeispiele:'''
 > (grenzwert (pasu-stream en) 1/10 10)
 2
 23
 > (grenzwert (pasu-stream en) 1/100 10)
 2 17
 24
 > (grenzwert (pasu-stream en) 1/1000 10)
 2 517
 720