Ecrit par
Yliur le vendredi 7 septembre 2012
dans le thème :
Lisp
Bonjour
Voilà ce que j'ai fait (pour un essai de fonction qui prend en
paramètre une fonction et renvoie la version avec mémoïsation).
C'est un essai sur la suite de Fibonacci.
Voilà ce que j'ai fait :
- J'ai défini une fonction (récursive).
- J'ai défini une fonction memo, qui prend en paramètre une
fonction et renvoie une fonction qui gère le mémo.
- J'ai fait (setf (symbol-function 'fibonacci)
(memo #'fibonacci))
pour réassocier la fonction avec mémo au symbole d'origine.
Note : si j'utilise (memo 'fibonacci), sans le # (function) devant, ça
ne fonctionne pas comme je veux. Si je comprends bien ce qui se passe,
c'est parce que la fonction memo va contenir le symbole 'fibonacci, qui
ne lui permet plus de désigner la "vraie" fonction si une nouvelle
fonction a été associée au symbole.
A part ça, j'ai fait un essai avec CLisp et tout se passe comme prévu :
les valeurs sont accumulées au fur et à mesure au lieu d'être
recalculées.
Par contre si je compile la fonction fibonacci avec
(compile 'fibonnaci) juste après l'avoir définie, avant de retoucher au
symbole, ça ne fonctionne pas.
C'est comme si lors de la compilation la référence vers la fonction
était établie une fois pour toute. Je pensais au contraire que la
fonction associée au symbole serait récupérée à chaque exécution de la
fonction.
Est-ce qu'effectivement la compilation fige les choses ou est-ce que
j'ai manqué un élément ?
Il n'est donc pas possible de redéfinir une fonction et que toutes les
fonctions qui la référence appellent la nouvelle version (à part sans
doute en utilisant (funcall (symbol-function 'f))) ?
Merci
Yliur
Ecrit par
Pascal J. Bourguignon le samedi 8 septembre 2012
Yliur writes:
> Bonjour
>
> Voilà ce que j'ai fait (pour un essai de fonction qui prend en
> paramètre une fonction et renvoie la version avec mémoïsation).
>
> C'est un essai sur la suite de Fibonacci.
>
> Voilà ce que j'ai fait :
§>§ - J'ai défini une fonction (récursive).
§>§ - J'ai défini une fonction memo, qui prend en paramètre une
§>§ fonction et renvoie une fonction qui gère le mémo.
§>§ - J'ai fait (setf (symbol-function 'fibonacci)
§>§ (memo #'fibonacci))
§>§ pour réassocier la fonction avec mémo au symbole d'origine.
>
> Note : si j'utilise (memo 'fibonacci), sans le # (function) devant, ça
> ne fonctionne pas comme je veux. Si je comprends bien ce qui se passe,
> c'est parce que la fonction memo va contenir le symbole 'fibonacci, qui
> ne lui permet plus de désigner la "vraie" fonction si une nouvelle
> fonction a été associée au symbole.
En effet. Si tu utilise le symbole au moment de l'appel de la fonction,
(par funcall ou apply), alors c'est (symbol-function symbole) qui sera
appelée, et comme c'est la nouvelle fonction, ça boucle.
Mais tu peux permettre de passer un symbole dénotant une fonction à
MEMO, en effectuant l'indirection immédiatement:
(defun memo (function-designator)
(if (symbolp function-designator)
(memo (symbol-function function-designator))
?))
> A part ça, j'ai fait un essai avec CLisp et tout se passe comme prévu :
> les valeurs sont accumulées au fur et à mesure au lieu d'être
> recalculées.
>
> Par contre si je compile la fonction fibonacci avec
> (compile 'fibonnaci) juste après l'avoir définie, avant de retoucher au
> symbole, ça ne fonctionne pas.
>
> C'est comme si lors de la compilation la référence vers la fonction
> était établie une fois pour toute. Je pensais au contraire que la
> fonction associée au symbole serait récupérée à chaque exécution de la
> fonction.
>
> Est-ce qu'effectivement la compilation fige les choses ou est-ce que
> j'ai manqué un élément ?
En effet.
La compilation par COMPILE d'une fonction peut effectuer une
optimization des appels à la fonction elle-même, y inclu l'optimization
des appels terminaux.
De même, dans une unité de compilation (soit par WITH-COMPILATION-UNIT,
soit par COMPILE-FILE), les fonctions présentes dans la même unité
peuvent être appelées directement sans passer par le symbole, ou même
être compilées en-ligne.
Pour éviter celà, on peut utiliser la déclaration NOT-INLINE.
> Il n'est donc pas possible de redéfinir une fonction et que toutes les
> fonctions qui la référence appellent la nouvelle version (à part sans
> doute en utilisant (funcall (symbol-function 'f))) ?
Si, c'est possible, avec NOT-INLINE.
(defun fibonnaci (n)
(declare (not-inline fibonnaci))
(case n
(0 0)
(1 1)
(otherwise (+ (fibonnaci (- n 1))
(fibonnaci (- n 2))))))
(compile 'fibonnaci)
(setf (symbol-function 'fibonnaci) (compile (memo 'fibonnaci)))
(fibonnaci 10)
Mettre la déclaration not-inline à l'intérieur de la fonction ne la rend
NOT-INLINE que pour elle-même. Si tu veux qu'elle soit NOT-INLINE pour
les autres fonctions de la même unité de compilation il faut utiliser:
(declaim (not-inline fibonnaci))
au premier niveau.
--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.