Discussion :

[pterosaurus]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 ?

[Jedai]

Utilise les balises CODE et indente lisiblement ton code :

Code Lisp :

Sélectionner tout - Visualiser dans une fenêtre à part

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 Lisp :

Sélectionner tout - Visualiser dans une fenêtre à part

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ï

[pterosaurus]

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.

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

[Trap D]

Fait du Scheme, ça foncitonne parfaitement :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

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

[Jedai]

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 :

* (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ï

[pterosaurus]

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.

[pterosaurus]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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:

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 !

[pterosaurus]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

(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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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