Verzögerte Evaluation und Streams

Aus ProgrammingWiki

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

zur Übungsübersicht

Inhaltsverzeichnis 1 Hilfsprozeduren 2 Delay und Force 3 Zahlenfolgen 4 Grenzwerte 5 Eulersche Zahl

Hilfsprozeduren

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

Bezeichnung	Parameter	Beschreibung
stream-car	stream	analog zu car
stream-cons	stream	analog zu car
stream?	parameter	testet, ob der Parameter ein Stream ist
make-stream	seed proc	gibt einen neuen Stream mit dem Anfangswert seed und der Prozedur 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-te Element eines Streams zurück
stream-map	funktion stream	gibt einen Stream zurück, bei dem die Funktion auf alle Glieder des Streams angewendet wird

Die im Folg. definierte Prozedur integer-stream-maker erzeugt einen Stream ganzer Zahlen, beginnend mit der als Argument übergebenen Zahl. Wir werden sie weiter unten benötigen.

(define integer-stream-maker (lambda (from) (stream-cons from (integer-stream-maker (+ from 1))))) (define integers (integer-stream-maker 0))

(stream->list integers 10)

ausführen

Delay und Force

Machen Sie sich mit den Sprachelementen delay und force 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 stream+, welche zwei streams mit Zahlen als Parameter nimmt und deren Werte paarweise bis zum n-ten Element addiert und als Liste zurückgibt.

(define stream+ (lambda (stream1 stream2) ...

(print-stream (stream+ integers integers) 5) ;0, 2, 4, 6, 8, ...

ausführen

Zahlenfolgen

In den folgenden Aufgaben geht es um Zahlenfolgen. Folgende zwei Zahlenfolgen und sind gegeben:

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.

(define an-stream-maker (lambda (start) ...

(define an (an-stream-maker 0)) (print-stream an 5) ;0, 0.7071067811865475, 0.6077812620656623, 0.6192477250610301,0.6178907764054561, 0.6180508933676908, ...

ausführen

(define bn-stream-maker (lambda (start) ...

(define bn (bn-stream-maker 0)) (print-stream bn 5) ;0, 1, 1/2, 2/3, 3/5, 5/8, ...

ausführen

Grenzwerte

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

(define grenzwert (lambda (stream epsilon max) ...

Ermitteln und vergleichen Sie die Grenzwerte der Zahlenfolgen und .

(grenzwert an 1/1000 10) ;0.6180339887498196

ausführen

(grenzwert integers 1/10 10) ; Achtung - break!

ausführen

Eulersche Zahl

(define fak (lambda (n) (if (= n 0) 1 (* n (fak (- n 1))))))

Die Eulersche Zahl ist gegeben durch folgende Reihe

.

Hinweis: 0! = 1

Schreiben Sie eine Prozedur en, die die Folge berechnet. Die Fakultätsprozedur ist in diesem Fall vordefiniert.

(define en (stream-map ... ...)

(print-stream en 5) ;1.0, 1.0, 0.5, 0.16666666666666666, 0.041666666666666664, ...

ausführen

Die folgende Prozedur berechnet die n-te Partialsumme einer betrachteten Zahlenfolge.

(define ntepartialsumme (lambda (stm n) (if (= n 0) (stream-car stm) (+ (stream-car stm)(ntepartialsumme (stream-cdr stm) (- n 1))))))

Vergleichen Sie die 10. Partialsumme mit dem Wert für :

(ntepartialsumme ... ) ;2.7182818011463845

ausführen

(exp 1)

ausführen

Nun bilden wir die Partialsummenfolge:

(define partialsummenfolge (lambda (stm) (stream-map ...

Schließlich fragen wir nach dem Grenzwert der Partialsummenfolge. Dieser beträgt .

(grenzwert (partialsummenfolge en) 1/100 10)

ausführen

zur Übungsübersicht