Quelle est la meilleure approche pour une fonction optimisée pour calculer la longueur d’une liste?

Question

Voici un exemple donné par une affiche du forum, je ne peux pas dire si cette queue est optimisée. En outre, quelqu'un pourrait-il décrire en termes simples comment une version optimisée par rapport à une version supérieure l'emporterait sur la version normale.

(defun mylength (s)
  (labels ((mylength-inner (s x)
            (if (car s) (mylength-inner (cdr s) (+ x 1)) x)))
          (mylength-inner s 0)))

Une version non optimisée par la queue?

(defun l (s) (if (car s) (+ 1 (l (rest s))) 0))

Answer 1

Une fonction peut être optimisée pour un appel ultérieur si elle renvoie un appel direct à elle-même ou aucun appel à elle-même. La fonction mylength-inner renvoie x ou (mylength-inner (cdr s) (+ x 1)) , et peut donc être optimisée pour la queue.

Cela signifie que le compilateur peut le transformer en boucle au lieu d’appeler la fonction de manière récursive. Renvoyez x ou affectez (cdr s) à s, incrémentez x et recommencez en haut. (La norme Scheme exige que les implémentations soient capables de faire cette optimisation, tandis que la norme Common Lisp laisse le soin à l'implémentation. Bien sûr, cette optimisation est une chose très utile, donc la plupart des implémentations le feront.)

Dans la version non optimisée, l ne renvoie pas simplement un appel à l, mais plutôt le résultat d'un appel à l auquel un autre a été ajouté. Cela signifie qu'il ne peut pas être directement transformé en boucle, de sorte que tous les appels de fonction devront être effectués.

Supposons que le compilateur veuille transformer l en boucle. Il n'y a pas de problème avec l'attribution de (reste s) à s, mais où cela met-il le (1 + ...) ?

Answer 2

FWIW, CL ne garantit pas qu’elle optimisera les appels de suite; cela dépend de la mise en œuvre. SBCL le soutient. Ceci est différent de Scheme, où la spécification exige que le compilateur élimine les appels de fin. Si vous ne le faites pas, vous n'êtes pas Scheme.

En outre, la récursion de la queue est plutôt non idiomatique dans CL. Nous avons une macro loop , utilisez-la donc:)

Answer 3

Les appels de queue peuvent être optimisés pour ne pas nécessiter d'espace supplémentaire sur la pile d'appels, et la dernière opération de la fonction doit être l'appel récursif, ce qui semble être le cas dans votre exemple forum. La dernière opération de la version sans fin est un ajout. L’appel récursif nécessite donc son propre cadre de pile.

Ceci suit un modèle simple, définit une fonction interne qui prend un argument accumulateur en plus des arguments des fonctions externes et accumule votre réponse au fur et à mesure. Lorsque vous arrivez à la fin, donnez la valeur accumulée.

Il y a probablement une meilleure explication ici:

http: // mitpress.mit.edu/sicp/full-text/book/book-ZH-11.html#%_sec_1.2.1

Answer 4

Le manuel de Scheme " Voici un exemple de longueur de liste: http: //www.scheme. com / tspl3 / start.html #. / start: h8 recherche de " longueur. "