Dépassement de pile à partir d'un appel de fonction récursif en Lisp

Question

J'apprends le Lisp dans le livre "The Land of Lisp" de Conrad Barski. Maintenant, je l'ai frappé mon premier bloc d'achoppement, où l'auteur dit:

vous appel de cette manière est non seulement admis dans Lisp, mais il est souvent fortement encouragé

après avoir montré la fonction exemple suivant pour compter les éléments dans une liste:

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

Quand j'appelle cette fonction my-length avec une liste contenant un million d'articles, je reçois une erreur de débordement de pile. Donc soit vous ne vous attendez jamais à avoir une liste aussi longue dans Lisp (donc peut-être que mon cas d'utilisation est inutile) ou il y a une autre façon de compter les éléments dans une telle liste. Pouvez-vous peut-être faire la lumière là-dessus? (J'utilise GNU CLISP sur Windows, d'ailleurs).

Answer 1

La création de fonctions récursives pour fonctionner sur des structures de données récursives est en effet bonne pour le langage lisp. Et une liste (en langage lisp) est définie comme une structure de données récursive, donc vous devriez être ok. Cependant, comme vous l'avez expérimenté, si vous parcourez une infrastructure de données avec un million d'éléments en utilisant la récursivité, vous allouerez également un million d'images sur la pile et vous risquez un débordement de pile sauf si vous demandez spécifiquement à votre environnement d'exécution de stack-space (je n'ai aucune idée si ou comment vous pourriez le faire dans gnu clisp ...). Tout d'abord, je pense que cela montre que l'architecture list-dat n'est pas vraiment la meilleure pour tout, et dans ce cas une autre structure pourrait être meilleure (cependant, vous n'avez peut-être pas trouvé de vecteurs dans votre lisp- book yet ;-)

Une autre chose est que pour que de telles récursions soient efficaces, le compilateur devrait optimiser les récursions de queue et les convertir en itérations. Je ne sais pas si clisp a cette fonctionnalité, mais vous devrez changer votre fonction pour être réellement optimisable. (Si « l'optimisation de récursion de queue » n'a pas de sens, s'il vous plaît laissez-moi savoir et je peux déterrer quelques références)

Pour d'autres moyens de itérer, jetez un oeil à:

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

ou d'autres structures de données:

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

Answer 2

Vous recherchez queue recursion. Au moment où votre fonction est définie comme

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

Notez que, après my-length a appelé lui-même, il a besoin d'ajouter un au résultat avant de passer cette valeur à sa fonction d'appel. Ce besoin de modifier la valeur avant de la renvoyer signifie que vous devez allouer un nouveau cadre de pile pour chaque appel, l'espace utilisé est proportionnel à la longueur de la liste. C'est ce qui provoque un débordement de pile sur de longues listes.

Vous pouvez ré-écrire pour utiliser une fonction d'aide

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

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

La fonction d'aide prend deux paramètres, un paramètre d'accumulation acc, qui stocke la longueur de la liste jusqu'à présent, et une liste list qui est la liste dont nous calculons la longueur.

Le point important est que helper est écrit récursif, ce qui signifie que l'appel lui-même est la dernière chose qu'il fait. Cela signifie que vous n'avez pas besoin d'allouer un nouveau cadre de pile à chaque fois que la fonction s'appelle elle-même - puisque le résultat final sera tout simplement remonté dans la chaîne des cadres de pile, vous pouvez vous débarrasser de l'ancien cadre de pile avec un nouveau, ainsi votre fonction récursive peut fonctionner dans l'espace constant. Cette forme de transformation de programme - d'une définition récursive (mais non récursive) à une définition équivalente en utilisant une fonction auxiliaire récursive de la queue est un idiome important dans la programmation fonctionnelle - celui qui vaut la peine de passer un peu de temps compréhension.

Answer 3

TCO (optimisation sur mesure des appels) à CLISP en utilisant l'exemple de Chris Taylor:

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

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

HELPER 

maintenant compiler:

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

*** - Program stack overflow. RESET 

Maintenant, ne fonctionne pas au-dessus. Définissons le niveau de débogage bas. Cela permet au compilateur de faire le coût total de possession.

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

Compilez à nouveau.

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

Œuvres.

Autoriser le compilateur Common Lisp à faire du TCO est le plus souvent contrôlé par le niveau de débogage. Avec un niveau de débogage élevé, le compilateur génère du code qui utilise une trame de pile pour chaque appel de fonction. De cette façon, chaque appel peut être retracé et sera vu dans un backtrace. Avec un niveau de débogage inférieur, le compilateur peut remplacer les appels de queue par des sauts dans le code compilé. Ces appels ne seront pas visibles dans un backtrace - ce qui rend généralement le débogage plus difficile.

Answer 4

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