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

Wiki-Quelltext dieser Seite.

<language>SchemeJS</language>
<code id="5ba6aa64adda0" hidden>
(define stream-car car)

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

(define-macro (stream-cons 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)
    (letrec
        ([show
          (lambda (stm n ls)
            (if (= n 0)
                (apply display (append ls (list "...")))
                (show (stream-cdr stm) (- n 1) (append ls (list (stream-car stm) ", ")))))])
      (show stm n ()))))
</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="5beb53443aa6d">
(show-stream lamp-stream 20)
</run>

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

Um jede n-te Lampe schalten zu können, erweitern wir die Stream-Sprachelemente mit der Prozedur höherer Ordnung<tt>(stream-map-n <n>)</tt>.<br />
In Analogie zu <tt>stream-map</tt> bewirkt ein Aufruf von <tt>(stream-map-n <n>)</tt> die Anwendung einer Prozedur <tt>proz</tt> auf jedes <tt>n</tt>-te Element eines Streams <tt>stm</tt>:

<code id="5beb28d1485e5">
(define stream-map-n
  (lambda (n)
    (lambda (proz stm)
      (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> 

In folgendem Beispiel wird jede dritte Lampe eingeschaltet...
<run id="5beb28d148759">
(show-stream ((stream-map-n 3) switch lamp-stream) 20)
</run>

... bzw. ein- und wieder ausgeschaltet:
<run id="5c935079a5aa0">
(show-stream ((stream-map-n 3) switch ((stream-map-n 3) switch lamp-stream)) 20)
</run>

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

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

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

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

<run id="4b52259a80ac2">
(show-stream frog-lamp-stream 20)
</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="5ba6aa64ade24">
(show-stream (result-stream frog-lamp-stream) 15)
</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]].