English alternative: My favourite Scheme feature: named let. With more implementation details.
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.
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.
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.
Anhang | Größe |
---|---|
2013-08-11-So-let-rekursion.org | 6.87 KB |
2013-08-11-So-let-rekursion-fib.w | 124 Bytes |
2013-08-11-So-let-rekursion-fib.scm | 130 Bytes |
2013-08-11-So-let-rekursion-fibloop.py_.txt | 143 Bytes |
2013-08-11-So-let-rekursion-fibrek.py_.txt | 99 Bytes |
2013-08-11-So-let-rekursion-fibrek2.py_.txt | 133 Bytes |
2013-08-11-So-let-rekursion-fibrek3.py_.txt | 136 Bytes |
2013-08-11-So-let-rekursion-skipindent.w | 937 Bytes |
2013-08-11-So-let-rekursion-skipindent.scm | 972 Bytes |
Use Node:
⚙ Babcom is trying to load the comments ⚙
This textbox will disappear when the comments have been loaded.
If the box below shows an error-page, you need to install Freenet with the Sone-Plugin or set the node-path to your freenet node and click the Reload Comments button (or return).
If you see something like Invalid key: java.net.MalformedURLException: There is no @ in that URI! (Sone/search.html)
, you need to setup Sone and the Web of Trust
If you had Javascript enabled, you would see comments for this page instead of the Sone page of the sites author.
Note: To make a comment which isn’t a reply visible to others here, include a link to this site somewhere in the text of your comment. It will then show up here. To ensure that I get notified of your comment, also include my Sone-ID.
Link to this site and my Sone ID: sone://6~ZDYdvAgMoUfG6M5Kwi7SQqyS-gTcyFeaNN1Pf3FvY
This spam-resistant comment-field is made with babcom.