Stapelüberlauf von rekursiven Funktionsaufruf in Lisp

Question

Ich lerne Lisp aus dem Buch "Das Land von Lisp" von Conrad Barski. Jetzt habe ich meinen ersten Stolperstein getroffen, in dem der Autor sagt:

sich auf diese Weise aufrufen wird nicht nur in Lisp erlaubt, aber oft ermutigt stark

nach dem folgenden Beispielfunktion zeigt die Elemente in einer Liste zu zählen:

(defun my-length (list) 
    (if list 
    (1+ (my-length (cdr list))) 
    0)) 

Wenn ich diese Funktion aufrufen my-length mit einer Liste eine Million Elemente enthält, erhalte ich einen Stapelüberlauf-Fehler. 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).

Answer 1

Das Erstellen von rekursiven Funktionen zum Arbeiten mit rekursiven 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. Wenn Sie eine Datenstruktur mit einer Rekursion um eine Million Elemente durchqueren, werden auch eine Million Frames auf dem Stack zugeordnet, und Sie können einen Stack-Überlauf erwarten, sofern Sie Ihre Laufzeitumgebung nicht ausdrücklich auffordern, einen großen Betrag zuzuweisen von stack-space (ich habe keine Ahnung, ob und wie du das in gnu clisp machen könntest ...).

Erstens, ich denke, das zeigt, dass die Listendatenstruktur nicht wirklich die beste für alles ist, und in diesem Fall könnte eine andere Struktur besser sein (aber Sie haben vielleicht nicht zu Vektoren in Ihrem Lisp kommen) Buch noch ;-)

Eine andere Sache ist, dass für große Rekursionen wie diese effektiv sein sollte, sollte der Compiler Tail-Rekursionen optimieren und sie in Iterationen konvertieren. Ich weiß nicht, ob clisp diese Funktionalität hat, aber Sie müssten Ihre Funktion ändern, um wirklich optimierbar zu sein. (Wenn „Endrekursion Optimierung“ keinen Sinn macht, lass es mich wissen und ich kann einige Referenzen graben)

Für andere Arten von Iterieren, werfen Sie einen Blick auf:

• http://www.lispworks.com/documentation/HyperSpec/Body/c_iterat.htm
• http://www.lispworks.com/documentation/HyperSpec/Body/06_a.htm

oder andere Datenstrukturen:

• http://www.lispworks.com/documentation/HyperSpec/Body/t_vector.htm

Answer 2

Sie suchen Tail Rekursion. Im Moment ist Ihre Funktion definiert wie

(defun my-length (list) 
    (if list 
    (1+ (my-length (cdr list))) 
    0)) 

Beachten Sie, dass nach my-length selbst genannt hat, braucht es ein auf das Ergebnis hinzuzufügen, bevor dieser Wert auf seine Berufung Funktion übergeben. 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 eine Hilfsfunktion verwenden

(defun helper (acc list) 
    (if list 
    (helper (1+ acc) (cdr list)) 
    acc)) 

(defun my-length (list) 
    (helper 0 list)) 

Die Hilfsfunktion zwei Parameter nimmt, über ein Akkumulation Parameteracc, die die Länge der Liste speichert, so weit, und eine Liste list Welches ist die Liste, die wir berechnen die Länge von.

Der wichtige Punkt ist, dass helper Schwanz rekursiv geschrieben wird, was bedeutet, dass das Aufrufen selbst ist das letzte, 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 - eines, das es wert ist, ein wenig Zeit zu verbringen Verstehen.

Answer 3

TCO (Endrekursion Optimierung) in CLISP das Beispiel von Chris Taylor mit:

[1]> (defun helper (acc list) 
     (if list 
      (helper (1+ acc) (cdr list)) 
      acc)) 

(defun my-length (list) 
    (helper 0 list)) 

HELPER 

Jetzt ist es kompilieren:

[2]> (compile 'helper) 
MY-LENGTH 
[3]> (my-length (loop repeat 100000 collect t)) 

*** - Program stack overflow. RESET 

Nun ist oben nicht funktionieren. Lassen Sie uns den Debug-Level niedrig setzen. Dies ermöglicht dem Compiler, TCO auszuführen.

[4]> (proclaim '(optimize (debug 1))) 
NIL 

wieder übersetzen.

[5]> (compile 'helper) 
HELPER ; 
NIL ; 
NIL 
[6]> (my-length (loop repeat 100000 collect t)) 
100000 
[7]> 

Funktioniert.

Das Zulassen, dass der Common Lisp-Compiler TCO ausfü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 dann wird nicht in einem Backtrace gesehen - was in der Regel schwieriger Debugging macht.

Answer 4

(DEFUN nrelem(l) 
    (if (null l) 
     0 
     (+ (nrelem (rest l)) 1) 
))