Ich lerne Lisp aus dem Buch "Das Land von Lisp" von Conrad Barski. Jetzt habe ich meinen ersten Stolperstein getroffen, wo der Autor sagt:
Sich so zu nennen, ist nicht nur in Lisp erlaubt, sondern oft auch dringend empfohlen
nach dem Anzeigen der folgenden Beispielfunktion zum Zählen der Elemente in einer Liste:
%Vor% Wenn ich diese Funktion my-length mit einer Liste aufrufen, die eine Million Elemente enthält, bekomme ich einen Stapelüberlauffehler. Entweder erwartet man nie, dass eine Liste in Lisp lang ist (vielleicht ist mein Anwendungsfall nutzlos) oder es gibt eine andere Möglichkeit, Elemente in einer so langen Liste zu zählen. Kannst du vielleicht etwas Licht darauf werfen? (Ich verwende übrigens GNU CLISP unter Windows).
Das Erstellen rekursiver Funktionen für rekursive Datenstrukturen ist in der Tat gut für Lisp. Und eine Liste (in Lisp) ist als rekursive Datenstruktur definiert, also sollten Sie in Ordnung sein.
Wie Sie jedoch erfahren haben, wenn Sie eine Datenstruktur mit rekursiven Millionen Elementen durchqueren, werden auch eine Million Frames auf dem Stack zugewiesen, und Sie können einen Stack-Overflow erwarten, wenn Sie nicht ausdrücklich Ihre Runtime-Umgebung dazu auffordern stack-space (ich habe keine Ahnung, ob oder wie du das in gnu clisp machen kannst ...).
Erstens, ich denke, das zeigt, dass die Listen-Datenstruktur nicht wirklich die beste für alles ist, und in diesem Fall könnte eine andere Struktur besser sein (allerdings sind Sie vielleicht nicht zu Vektoren in Ihrem Lisp-Buch gekommen noch; -)
Eine andere Sache ist, dass für große Rekursionen wie diese, der Compiler Tail-Rekursionen optimieren und in Iterationen konvertieren soll. Ich weiß nicht, ob clisp diese Funktionalität hat, aber Sie müssten Ihre Funktion ändern, um wirklich optimierbar zu sein. (Wenn "Tail Recursion Optimization" keinen Sinn ergibt, lass es mich wissen und ich kann einige Referenzen ausgraben)
Für andere Möglichkeiten der Iteration werfen Sie einen Blick auf:
Oder andere Datenstrukturen:
TCO (Tail Call Optimierung) in CLISP mit dem Beispiel von Chris Taylor:
%Vor%Kompiliere es jetzt:
%Vor%Nun, oben funktioniert nicht. Lassen Sie uns den Debug-Level niedrig setzen. Dadurch kann der Compiler TCO ausführen.
%Vor%Kompilieren Sie erneut.
%Vor%funktioniert.
Das Zulassen, dass der Common Lisp-Compiler TCO durchführt, wird meistens von der Debug-Ebene gesteuert. Bei einer hohen Debug-Ebene generiert der Compiler Code, der für jeden Funktionsaufruf einen Stack-Frame verwendet. Auf diese Weise kann jeder Anruf verfolgt werden und wird in einem Backtrace angezeigt. Mit einer niedrigeren Debug-Ebene kann der Compiler Tail-Aufrufe durch Sprünge im kompilierten Code ersetzen. Diese Aufrufe werden dann nicht in einem Backtrace angezeigt - was das Debugging normalerweise schwieriger macht.
Sie suchen nach Tail-Rekursion . Im Moment ist deine Funktion wie
definiert %Vor% Beachten Sie, dass nachdem my-length sich selbst aufgerufen hat, muss eins zum Ergebnis hinzugefügt werden, bevor dieser Wert an seine aufrufende Funktion übergeben wird. Wenn Sie den Wert ändern müssen, bevor Sie ihn zurückgeben, bedeutet dies, dass Sie für jeden Aufruf einen neuen Stapelrahmen zuweisen müssen. Der verwendete Speicherplatz ist proportional zur Länge der Liste. Dies verursacht einen Stapelüberlauf bei langen Listen.
Sie können es neu schreiben, um eine Hilfsfunktion zu verwenden
%Vor% Die Hilfsfunktion benötigt zwei Parameter, einen Akkumulationsparameter acc , der die Länge der Liste speichert, und eine Liste list , die die Länge der Liste berechnet von.
Der wichtige Punkt ist, dass helper rekursiv in den Tail geschrieben wird, was bedeutet, dass Calling selbst das letzte ist, was es tut. Das bedeutet, dass Sie nicht jedes Mal, wenn die Funktion sich selbst aufruft, einen neuen Stack-Frame zuweisen müssen - da das Endergebnis nur die gesamte Kette von Stack-Frames zurück durchläuft, können Sie den alten Stack-Frame überschreiben mit einer neuen, so kann Ihre rekursive Funktion in einem konstanten Raum arbeiten.
Diese Form der Programmumwandlung - von einer rekursiven (aber nicht tail-rekursiven) Definition zu einer äquivalenten Definition unter Verwendung einer tail-rekursiven Hilfsfunktion - ist ein wichtiges Idiom in der funktionalen Programmierung - eine, die es wert ist, ein bisschen Zeit zu verstehen .
Tags und Links lisp common-lisp tail-recursion clisp land-of-lisp