Let-Rekursion ist toll!

Ich habe dank Pythonista in Scheme-Land von Let-Rekursion gelesen. Bis vorgestern fand ich sie noch sinnlos kompliziert.

Das hat sich alles geändert, als ich wirklichen Code damit geschrieben habe - zum Beispiel die Fibonacci-Folge (syntax: wisp1 für Guile Scheme2) (eigentlicher Augenöffner):

define : fib n
    let rek : (i 0) (u 1) (v 1)
        if : >= i : - n 2
            . v
            rek (+ i 1) v (+ u v) ; else

Um Let-Rekursion zu beschreiben, werde ich diese Funktion jetzt zu einer Schleife in Python transformieren und mich zu immer eleganteren Formulierungen vortasten, bis ich wieder bei dem gerade gezeigten Code bin; dann aber mit Hintergrundwissen darüber, wodurch er elegant wird, mit dem Verständnis, was genau er tut, und mit einem Gefühl dafür, wie viel diese Eleganz ausmacht - und warum sie erstrebenswert ist.

Let-Rekursion erklärt

Da ich selbst bis vor 2 Tagen nicht wirklich verstanden hatte, was Let-Rekursion ist und was sie bringt, will ich sie erklären.

Ich versuche an einem einfachen Beispiel zu beschreiben, wie sie funktioniert und was sie so besonders macht: Nehmen wir ein Programm, das Glieder aus einer Fibonacci-Folge berechnet. Die 1. Zahl ist eins, die 2. ist eins, die 3. ist die 1. + die 2., die vierte ist die 2. + die 3., usw.

\(f_n = f_{n-1} + f_{n-2}\) für \(n \geq 2\) mit \(f_1 = f_2 = 1\)

Meine Beispiele sind in Python (meiner „Muttersprache“), solange sich die Funktionalität in Python abbilden lässt.

In Schleifen-Notation würde die Fibonacci-Funktion z.B. so aussehen:

def fib(n):
   if n in (1, 2):
      return 1
   u = 1
   v = 1
   for i in range(n-2):
      tmp = v
      v = u+v
      u = tmp
   return v

Hier sehen wir deutlich, wie viel unnötiger Code benötigt wird (boiler plate): tmp, for, n= und v=.

Versuchen wir das also rekursiv:

def fibrek(n, i=0, u=1, v=1):
    if i >= n-2:
        return v
    return fibrek(n, i+1, v, u+v)

Das ist schon viel kürzer, aber dafür haben wir keine klare API mehr: Wer diese Funktion von außen nutzt, sieht Parameter, die eigentlich nicht genutzt werden sollten. Und das kann Verwirrung stiften, was Fehler provoziert.

Um das API-Problem zu beheben können wir in Python eine Hilfsfunktion verwenden:

def _rek(n, i, u, v):
    if i >= n-2:
        return v
    return _rek(n, i+1, v, u+v)

def fibrek2(n):
    return _rek(n, 0, 1,1)

Jetzt haben wir wieder eine saubere API der Funktion, aber eine im ganzen Modul sichtbare Hilfsfunktion, die nur in einer einzigen echten Funktion genutzt wird. Das Ergebnis ist ein vollerer Namensraum, der wieder zu Fehlern führt - erst recht mit der ganzen Code-Vervollständigung, die heutzutage üblich ist.

Aber es gibt noch Hoffnung: Wir können die Hilfsfunktion innerhalb der Hauptfunktion definieren:

def fibrek3(n):
    def rek(i=0, u=1, v=1):
        if i >= n-2:
            return v
        return rek(i+1, v, u+v)
    return rek()

Als Besonderheit wird hier das n implizit übergeben: Die Funktion rek hat es im Namensraum, weil es zur Zeit ihrer Definition in ihrem Namensraum war.

So sieht das ganze schon sehr schön aus. Was nur noch stört ist der Funktionsaufruf rek() am Ende: Den brauchen wir eigentlich nicht. Stattdessen bräuchten wir eine Möglichkeit, einen explizit-rekursiven Abschnitt der Funktion zu definieren, der automatisch aufgerufen wird.

Und genau das ist Let-Rekursion.

Um den letzten Schritt dorthin zu gehen, muss ich allerdings wirklich auf Scheme wechseln - im Interesse der Lesbarkeit für Nicht-Schemer in wisp-syntax.1, 2

define : fib n
    let rek : (i 0) (u 1) (v 1)
        if : >= i : - n 2
            . v
            rek (+ i 1) v (+ u v)

(Die Ähnlichkeit zum vorhin definierten Python-Code sollte klar machen, was der Code tut)

Diese Funktion hat einen sauberen Namensraum und klare Strukturen, und sie vermeidet jegliche unnötige Syntax.

Und das ist Wahnsinn.

Go Scheme!

Zum Abschluss zeige ich jetzt noch den Code, der mich dazu gebracht hat, diesen Artikel zu schreiben.

Mein Augenöffner (Code)

Dieser Code hat mir die Eleganz und Macht der Let-Rekursion vor Augen geführt.

Die definierte Funktion entfernt die Einrückung einer Zeile Text und gibt die Tiefe der Einrückung zurück. Anders als lstrip(), betrachtet sie Unterstriche am Anfang der Zeile als Einrückung und arbeitet auf einem port, aus dem ich nur einzelne Zeichen lesen kann.

Sie ist Teil meines (noch nicht fertigen) Whitespace-Lisp Parsers in Guile-Scheme.

define : skipindent inport
    let skipper
        : inunderbars #t
          indent 0
          nextchar : read-char inport
        ; when the file ends, do not do anything else
        when : not : eof-object? nextchar 
            ; skip underbars
            if inunderbars
                if : char=? nextchar #\_ ; still in underbars?
                    skipper 
                        . #t ; still in underbars?
                        + indent 1
                        read-char inport
                    ; else, reevaluate without inunderbars
                    skipper #f indent nextchar
                ; else: skip remaining spaces
                if : char=? nextchar #\space
                    skipper
                        . #f
                        + indent 1
                        read-char inport
                    begin
                        unread-char nextchar inport
                        . indent

Den Code zu schreiben hat mir das Gefühl gegeben, frei zu sein: Keine Definitionen um der Struktur willen, sondern nur genau das, was ich brauchte - und völlig natürlich in die normale let-Syntax eingebunden, die ich schon kannte.

Fußnoten:

1

: Wisp konvertiert über einen einfachen Präprozessor Einrückungs-Sensitiven Code zu Scheme. Im Endeffekt fügt es die Klammern hinzu, die Code mit dieser Einrückung hätte.

2

: Ich nutze Guile für mein Beispiel. Angehängt sind die Code-Beispiele, die Org-Mode Quellen und auch eine von Wisp auf Scheme übersetzte Version der Wisp-Codes.

Autor: Arne Babenhauserheide

Created: 2013-08-12 Mo 01:28

Emacs 24.3.1 (Org mode 8.0.2)

Validate XHTML 1.0

AnhangGröße
2013-08-11-So-let-rekursion.org6.87 KB
2013-08-11-So-let-rekursion-fib.w124 Bytes
2013-08-11-So-let-rekursion-fib.scm130 Bytes
2013-08-11-So-let-rekursion-fibloop.py_.txt143 Bytes
2013-08-11-So-let-rekursion-fibrek.py_.txt99 Bytes
2013-08-11-So-let-rekursion-fibrek2.py_.txt133 Bytes
2013-08-11-So-let-rekursion-fibrek3.py_.txt136 Bytes
2013-08-11-So-let-rekursion-skipindent.w937 Bytes
2013-08-11-So-let-rekursion-skipindent.scm972 Bytes
Inhalt abgleichen
Willkommen im Weltenwald!
((λ()'Dr.ArneBab))



Beliebte Inhalte

sn.1w6.org news