Trace "manuelle" d'une fonction récursive

Bonjour,

Je cherche à reproduire manuellement le comportement de la fonction trace de Lisp sur une fonction récursive simple, c'est-à-dire imprimer à chaque appel la valeur de l'argument et en sortie la valeur retournée. Voici le début de mon expérimentation:

Code:

---

1 2 3 4 5

(defun fact (n) (format t "Entering fact ~A~%" n) (if (> n 0) (* n (fact (- n 1))) 1))

---

Ainsi j'obtiens la liste des appels.

CL-USER> (fact 3)
Entering fact 3
Entering fact 2
Entering fact 1
Entering fact 0
6

Mon problème concerne la liste des valeurs retournées. Comment imprimer par effet la valeur retournée par une fonction avant de sortir de celle-ci ?

Utilise les balises CODE et indente lisiblement ton code :

Code:

---

1 2 3 4 5 6

(defun fact (n) (format t "Entering FACT ~A~%" n) (if (> n 0) (* n (fact (- n 1))) 1 ))

---

Pour ce qui est de ta question, il suffit de stocker la réponse et de l'afficher avant de la renvoyer :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

(defun fact (n) (format t "Entering FACT ~A~%" n) (let ((resp (if (> n 0) (* n (fact (- n 1))) 1)) ) (format t "Leaving FACT ~A : ~A~%" n resp) resp ) )

---

Méfiance : cette construction va empêcher l'application de l'optimisation d'appel terminal et donc fausser ta trace dans certains cas (pas ici).
--
Jedaï

Bon, j'ai un peu progressé. Je problème que j'avais est que format renvoie NIL donc avec une forme du type:

Code:

---

(format t "==> ~A~%" (* n (fact (- n 1))))

---

je perds la valeur retournée par la fonction. J'utilise donc PRINT qui affiche la valeur calculée dans le corps de la fonction puis retourne cette valeur. Cela donne:

Code:

---

1 2 3 4 5

(defun fact (n) (format t "Entering fact ~A~%" n) (if (> n 0) (print (* n (fact (- n 1)))) (print 1)))

---

J'obtiens:

CL-USER> (fact 3)
Entering fact 3
Entering fact 2
Entering fact 1
Entering fact 0

1
1
2
6
6 (valeur de (fact 3))

La question suivante est comment obtenir un affichage du type:

Entering fact 3
Entering fact 2
Entering fact 1
Entering fact 0

==> 1
==> 1
==> 2
==> 6
6

ou même:

Entering fact 3
Entering fact 2
Entering fact 1
Entering fact 0

fact 0 ==> 1
fact 1 ==> 1
fact 2 ==> 2
fact 3 ==> 6
6

Citation:

---

Envoyé par Jedai

Utilise les balises CODE et indente lisiblement ton code :

---

C'est fait, je ne l'avais pas vue, je viens d'arriver sur le site, merci.

Citation:

---

Envoyé par Jedai

Méfiance : cette construction va empêcher l'application de l'optimisation d'appel terminal et donc fausser ta trace dans certains cas (pas ici).

---

C'était justement cela l'objet de ma réflexion. En humble débutant que je suis, puis-je te proposer d'essayer ta solution avant de poster ;) (je viens de le faire: tes FORMAT sont jetés au fur et à mesure, il ne reste que le dernier, logique puisque tu assignes une valeur à RESP et seule celle-ci est transmise au reste du corps). L'intéret de la trace pour moi est justement de coller au plus près à la structure de la fonction, de pouvoir imbriquer plusieurs fonctions récursives et détecter la récursivité terminale. Ici, toute la chaîne d'appels récursifs à lieu lors de l'évaluation du LET et non plus dans la fonction.
J'avoue que mélanger effets et programmation fonctionnelle relève d'un bon casse-tête, mais on aime ça ;)

Fait du Scheme, ça foncitonne parfaitement :

Code:

---

1 2 3 4 5 6 7 8

(define (fact n) (printf "Entering fact ~a~n" n) (let ((resp (if (> n 0) (* n (fact (- n 1))) 1))) (printf "fact ~a ==> ~a~n" n resp) resp))

---

sortie

Citation:

---

Entering fact 3
Entering fact 2
Entering fact 1
Entering fact 0
fact 0 ==> 1
fact 1 ==> 1
fact 2 ==> 2
fact 3 ==> 6
6

---

Citation:

---

Envoyé par pterosaurus

C'était justement cela l'objet de ma réflexion. En humble débutant que je suis, puis-je te proposer d'essayer ta solution avant de poster ;) (je viens de le faire: tes FORMAT sont jetés au fur et à mesure, il ne reste que le dernier, logique puisque tu assignes une valeur à RESP et seule celle-ci est transmise au reste du corps). L'intéret de la trace pour moi est justement de coller au plus près à la structure de la fonction, de pouvoir imbriquer plusieurs fonctions récursives et détecter la récursivité terminale. Ici, toute la chaîne d'appels récursifs à lieu lors de l'évaluation du LET et non plus dans la fonction.

---

J'ai testé ma solution, et elle marche parfaitement, je ne vois pas ce dont tu parles, de plus ta fonction n'est pas récursive terminale à l'origine donc cela n'a aucune influence ici.

Exemple de sortie de ma fonction :

Citation:

---

* (fact 5)
Entering FACT 5
Entering FACT 4
Entering FACT 3
Entering FACT 2
Entering FACT 1
Entering FACT 0
Leaving FACT 0 : 1
Leaving FACT 1 : 1
Leaving FACT 2 : 2
Leaving FACT 3 : 6
Leaving FACT 4 : 24
Leaving FACT 5 : 120
120

---

--
Jedaï

Citation:

---

Envoyé par Jedai

J'ai testé ma solution, et elle marche parfaitement, je ne vois pas ce dont tu parles, de plus ta fonction n'est pas récursive terminale à l'origine donc cela n'a aucune influence ici.

---

Toutes mes excuses Jedai, l'erreur vient de moi. Ta solution fonctionne effectivement.

Jedai:

L'erreur grossière tenait à ce que j'avais plusieurs définitions de FACT: FACT1, FACT2,... Bon j'ai repris ton idée sur la version récursive terminale:

Code:

---

1 2 3 4 5 6 7 8 9

(defun fact-tail (n) (labels ((iter (product counter) (format t "Entering ITER ~A~%" counter) (let ((val (if (> counter n) product (iter (* counter product) (+ counter 1))))) (format t "Leaving ITER ~A : ~A~%" counter val) val))) (iter 1 1)))

---

tout se passe comme prévu:

Citation:

---

CL-USER> (fact-tail 3)
Entering ITER 1
Entering ITER 2
Entering ITER 3
Entering ITER 4
Leaving ITER 4 : 6
Leaving ITER 3 : 6
Leaving ITER 2 : 6
Leaving ITER 1 : 6
6

---

Pourrais-tu m'en dire un peu plus sur ce problème d'optimisation de la récursivité terminale, peut-être me donner un exemple ?

-----
On apprend beaucoup plus de ses erreurs que de ses réussites !

Citation:

---

Envoyé par pterosaurus

tout se passe comme prévu:

....

Pourrais-tu m'en dire un peu plus sur ce problème d'optimisation de la récursivité terminale, peut-être me donner un exemple ?

---

Et bien tu as un exemple juste au-dessus. La fonction d'origine était récursive terminale, donc pour une "trace" qui suivrait bien l'ordre d'exécution originel, on aurait plutôt :

Citation:

---

CL-USER> (fact-tail 3)
Entering ITER 1
Entering ITER 2
Entering ITER 3
Entering ITER 4
Leaving ITER 4 : 6
6

---

Autrement dit, chaque appel de iter "écrase" le précédent et la valeur finalement retournée est celle directement renvoyée par le dernier appel d'ITER.

Malheureusement l'ajout manuel de la trace fait disparaître le caractère terminal récursif de la fonction tracée. Peut-être y a-t-il des outils d'instrumentation du code plus sophistiqué dans ton interpréteur Lisp qui pourrait te permettre d'observer le déroulement réel des choses, mais a priori c'est là la limite d'une trace manuelle.

--
Jedaï

Effectivement, j'utilise d'habitude la fonction trace de l'interpréteur. Le but de cet exercice était pour moi de tracer le code "de l'intérieur" dans différentes situations. C'est pour cela que la reconstruction avec LET, bien qu'elle fonctionne parfaitement, ne me plaisait pas trop car elle demande quand même une certaine réécriture. La trace de lisp donne le même résultat:

Code:

---

1 2 3 4

(defun iter (product counter n) (if (> counter n) product (iter (* counter product) (+ counter 1) n)))

---

Citation:

---

CL-USER> (trace iter)
;; Tracing function ITER.
(ITER)
CL-USER> (iter 1 1 3)
1. Trace: (ITER '1 '1 '3)
2. Trace: (ITER '1 '2 '3)
3. Trace: (ITER '2 '3 '3)
4. Trace: (ITER '6 '4 '3)
4. Trace: ITER ==> 6
3. Trace: ITER ==> 6
2. Trace: ITER ==> 6
1. Trace: ITER ==> 6
6

---

De toute façon la récursivité terminale apparaît clairement vu que tous les retours sont les mêmes, si cela n'était pas évident à l'examen du code:

Code:

---

(iter (* counter product) (+ counter 1) n)

---

Merci en tout cas pour ces aimables réponses et à bientôt sur les forums :-)