Grundlagen der funktionsorientierten Programmierung mit SCHEME/Von Fröschen und Tischlampen

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
<code id="4b52203274e13" hidden>
(define stream-car car)

(define stream-cdr
  (lambda (stm)
    (force (cdr stm))))

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

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

(define stream-map
  (lambda (proz stm)
    (stream-cons (proz (stream-car stm)) (stream-map proz (stream-cdr stm)))))

(define show-stream
  (lambda (stm n)
    (if (= n 0)
        (begin
          (display "...") (newline)
          'ok)
        (begin
          (display (stream-car stm)) (display ", ")
          (show-stream (stream-cdr stm) (- n 1))))))
</code>

[[Datei:FroschLampe.jpg|miniatur|Von Fröschen und Tischlampen]]

=== Der Lampen-Stream ===

Zunächst definieren wir den Stream (abzählbar) unendlich vieler Tischlampen, die alle ausgeschaltet sind.<br />
Jede Lampe ist mit einem Schalter ausgestattet, mit dem die Lampe entsprechend ihres Betriebszustandes entweder ein- oder ausgeschaltet werden kann:

<code id="4b522b2b0bfdc">
(define lamp-stream
  (stream-cons 'off lamp-stream))

(define switch
  (lambda (lamp)
    (if (eqv? lamp 'off)
        'on
        'off)))
</code>

<run id="4b52203279c19">
(show-stream lamp-stream 18)
</run>

=== Frosch-Sprünge mit verschiedenen Weiten ===

Um jede n-te Lampe schalten zu können, erweitern wir die Stream-Sprachelemente mit der Prozedur <tt>stream-map-n</tt>.<br />
In Analogie zu <tt>stream-map</tt> bewirkt <tt>stream-map-n</tt> eine Prozeduranwendung auf jedes n-te Element eines Streams:

<code id="4b52259a7cc63">
(define stream-map-n
  (lambda (proz stm n)
    (letrec
        ([help-stream
          (lambda (stm s)
            (if (= s n)
                (stream-cons (proz (stream-car stm)) (help-stream (stream-cdr stm) 1))
                (stream-cons (stream-car stm) (help-stream (stream-cdr stm) (+ s 1)))))])
      (help-stream stm 1))))
</code> 

Nun können wir Frosch-Sprünge mit aufsteigenden Sprungweiten definieren:

<code id="4b52288be1977">
(define jump
  (lambda (stm w)
    (stream-cons (switch (stream-car stm))
      (jump (stream-map-n (lambda (lamp) (switch lamp)) (stream-cdr stm) w) (+ w 1)))))
</code>

=== Unendlich viele Frösche springen über unendlich viele Tischlampen ===

<code id="4b52288be2905">
(define frog-lamp-stream
  (jump lamp-stream 1))
</code>

<run id="4b52259a80ac2">
(show-stream frog-lamp-stream 18)
</run>

=== Auswertung ===

Um das Resultat besser verallgemeinern zu können, fassen wir die Nummern der Lampen zusammen, die nach allen Frosch-Sprüngen ''eingeschaltet'' sind. In der Vermutung, dass das (abzählbar) unendlich viele Lampen sind, soll dieses Ergebnis wiederum als Stream repräsentiert werden:

<code id="4b52261eec295">
(define result-stream
  (lambda (stm)
    (letrec
        ([help-stream
          (lambda (stm i)
            (if (eqv? (stream-car stm) 'on)
                (stream-cons i (help-stream (stream-cdr stm) (+ i 1)))
                (help-stream (stream-cdr stm) (+ i 1))))])
      (help-stream stm 1))))
</code>

<run id="4b52259a81a5e">
(show-stream (result-stream frog-lamp-stream) 18)
</run>

'''Ergebnis:''' Offensichtlich sind nach den Frosch-Sprüngen alle Lampen eingeschaltet, deren Nummern ''Quadratzahlen'' sind.<br />

Zurück zu [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Streams|Streams]].