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 + \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})=\frac{1}{\sqrt{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!
     
===Implementierung===   
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>
<eval id="4b04f53cc055a">
(define an (an-stream-maker 0)))
(stream->list an 5)
0.7071067811865475, 0.6077812620656623, 0.6192477250610301,0.6178907764054561, 0.6180508933676908, ...
</eval>

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

==Grenzwerte== 
Schreiben Sie eine Prozedur <tt>grenzwert</tt>, die den Grenzwert einer Zahlenfolge bestimmt. Diese soll den Grenzwert einer als Stream repräsentierten Zahlenfolge <tt>stm</tt> zurückgeben, wenn dieser innerhalb einer hinreichend kleinen <math>\varepsilon</math>-Umgebung (<tt>eps</tt>) liegt. Falls nicht <tt>max</tt> Folgenglieder in dieser <math>\varepsilon</math>-Umgebung liegen, wird Divergenz vermutet und <tt>#f</tt> zurückgegeben.

<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>.

<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>

==Eulersche Zahl==
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 als eine Prozedur, die die Eulersche Zahl näherungsweise bis zum n-ten Glied berechnet. In der Sprache der Mathematik entspricht dies der Partialsummenfolge. 

'''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">
(define en
  (lambda (...)
    ...)
</code>
<eval id="4b04f53cc43be">(define en (en-stream-maker 0))
(stream->list en 5)
</eval>

<code>
(define partialsummenfolge
  (lambda (stm n)
    ...)
</code>

Mit Hilfe der Prozeduren <tt>grenzwert</tt> und <tt>partialsummenfolge</tt> kann nun der Wert der unendlichen Reihe näherungsweise ermittelt werden.
<eval id="4b04f53cc5b25">(grenzwert (partialsummenfolge en) 1/10 10)</eval>
<eval id="4b04f53cc6300">(grenzwert (partialsummenfolge en) 1/100 10)</eval>
<eval id="4b04f53cc6a69">(grenzwert (partialsummenfolge en) 1/1000 10)</eval>

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