Discussion :

[stendhal666]

Bonjour,

Pour faire une liste plate à partir de x et y, où x et y peuvent être ou bien un atome, ou bien une liste, je me retrouve avec 4 possibilités:

Code :

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

1
2
3
4
5
6
7
8
(defun smart-append (x y)
   (if (atom x)
       (if (atom y)
           (list x y) ;; 1
           (cons x y)) ;; 2
       (if (atom y)
           (append x (list y)) ;; 3
           (append x y)))) ;; 4

Existe-t-il une façon plus performante/élégante de faire cela, par exemple une fonction déjà définie dans Common LISP?
Merci d'avance.

[Bruno-Vdh]

Bonsoir,

Sans fonction spécialisé mes propositions, à toi de décider ce qui te semble le plus élégant...

Version 1: Le plus simple en transmettant à append la valeur en retour des conditionnels.

Code :

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

1
2
3
4
(defun smart-append (x y)
  (append
    (if (atom x) (list x) x)
    (if (atom y) (list y) y)))

Version 2: Sinon convertissant préalablement les arguments de la fonction smart-append avant d'appeler la fonction append.

Code :

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

1
2
3
4
(defun smart-append (x y)
  (cond ((atom x) (smart-append (list x) y))
	((atom y) (smart-append x (list y)))
	((append x y))))

Cordialement
(Ps: moi je vote pour la version 1)

[stendhal666]

Merci, la version 1 me paraît tout à fait bien, je garde son principe mais l'élabore un peu pour garder le supplément d'efficacité de cons:

Code :

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

1
2
3
4
5
(defun smart-append (x y)
    (funcall
        (if (atom x) #'cons #'append))
        x
        (if (atom y) (list y) y)))

[Bruno-Vdh]

Re,
J'aime bien ta variante, sinon pour info je n'utilise pas Common Lisp donc pas de funcall, mais en adaptant ton code à mon dialecte Lisp, effectivement au Benchmark, il y a un léger "supplément d'efficacité", pas seulement dû à l'emploie du cons mais plutôt dû à l'implémentation dans mon dialecte qui permet l'écriture suivante:

Code :

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

1
2
3
4
(defun smart-append (x y)
  ((if (atom x) cons append)
    x
   (if (atom y) (list y) y)))

Maintenant avec l'emploie de la fonction funcall , je ne suis pas certain que le gain soit encore présent. Car chez moi si je remplace ta fonction funcall par eval:

Code :

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

1
2
3
4
(defun smart-append2 (x y)
  ((eval (if (atom x) 'cons 'append))
    x
   (if (atom y) (list y) y)))

Au Benchmark les fonctions ont des performances quasi équivalentes..

[jack-ft]

Sans fonction spécialisé mes propositions, à toi de décider ce qui te semble le plus élégant...

Version 1: Le plus simple en transmettant à append la valeur en retour des conditionnels.

Code :

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

1
2
3
4
(defun smart-append (x y)
  (append
    (if (atom x) (list x) x)
    (if (atom y) (list y) y)))

Version 2: Sinon convertissant préalablement les arguments de la fonction smart-append avant d'appeler la fonction append.

Code :

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

1
2
3
4
(defun smart-append (x y)
  (cond ((atom x) (smart-append (list x) y))
	((atom y) (smart-append x (list y)))
	((append x y))))

Cordialement
(Ps: moi je vote pour la version 1)

Hmmm... Juste pour information, dans ces 2 versions, lorsque x est un atome, on le met dans une liste (allocation d'un cons) qui est ensuite "appendée" avec le reste. En conséquence, le cons qu'on vient juste d'allouer est aussitôt "oublié" (plus de référence). Si on a un bon gc incrémental, pas de problème, il peut le reconnaître tout de suite, mais (comme je n'aime pas le gaspillage!), je trouve ça un peu dommage!

Je n'aime pas trop les funcall, qui mettent du dynamisme dans un code qui peut être plus lexical et donc probablement mieux optimisé par le compilateur (ça dépend très fortement de la version de lisp et du compilateur, évidemment).

Conclusion: je préfère encore la version originale!

Ou bien la version statique de celle proposée par stendhal666:

Merci, la version 1 me paraît tout à fait bien, je garde son principe mais l'élabore un peu pour garder le supplément d'efficacité de cons:

Code :

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

1
2
3
4
5
(defun smart-append (x y)
    (funcall
        (if (atom x) #'cons #'append))
        x
        (if (atom y) (list y) y)))

à savoir:

Code :

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

1
2
3
4
(defun smart-append (x y)
  (if (atom x)
      (cons x (if (atom y) (list y) y))
    (append x (if (atom y) (list y) y))))

Mais, si on a un bon compilateur, on peut aussi faire:

Code :

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

1
2
3
(defun smart-append (x y)
  (when (atom y) (setq y (list y)))
  (if (atom x) (cons x y) (append x y)))

car il va probablement stocker le (list y) dans la pile ou dans un registre.

Après, le plus élégant...
les coups et les douleurs...

[stendhal666]

@jack-ft: merci pour cette réponse très informée! Est-ce que tu pourrais développer un peu sur la différence entre code dynamique / code lexical et expliquer pourquoi en utilisant setq on incite à l'utilisation de la pile / d'un registre? PS: je plussoie "les coups et les douleurs" - dans le genre j'ai "au diable les varices"

@bruno: j'imagine que tu utilises Scheme? nettement plus élégant c'est certain... en revanche je ne pense pas que funcall = eval (il y a eval aussi bien en common lisp), il me semble que cela provient de l'existence de deux espaces de nommage, un pour les variables et un pour les fonctions.

[Bruno-Vdh]

@jack-ft, d'accord avec tes commentaires, et bien vu pour ta version statique de celle proposé par stendhal666, elle réunit le mieux performante/élégance et ce quelques soit le dialecte Lisp.

@stendahl666, en fait j'utilise un dialecte Lisp, intégré à un logiciel de dessin (Je suis dessinateur/projeteur de métier et "Lispeur occasionnel"), dans les faits c'est un Lisp simplifié qui à l'origine est dérivé de Xlisp (il me semble).

[jack-ft]

@jack-ft: merci pour cette réponse très informée! Est-ce que tu pourrais développer un peu sur la différence entre code dynamique / code lexical

Ouh la la!
Il y a une très (trop?) abondante littérature sur la différence entre "portée lexicale" et "portée dynamique" (ou lexical vs dynamic scope).
Je t'invite à t'y référer!

et expliquer pourquoi en utilisant setq on incite à l'utilisation de la pile / d'un registre?

Ouh la la!
La compilation, surtout en lisp (et notamment à cause du scope dynamique), est un processus assez compliqué.
Et, en plus, ça dépend très fortement du langage lui-même (quel "type" de lisp) et de l'implémentation de son compilateur!
Je ne suis pas un spécialiste en la matière. Je connais(sais) un peu les entrailles de la compilation en Le_Lisp pour avoir travaillé pendant quelques années avec le développeur (Bernard Serpette) du "nouveau" compilateur "complice" de Le_Lisp.
En gros, l'ancien compilateur mettait l'accent sur la portée dynamique alors que le nouveau mettait l'accent sur la portée lexicale.

De plus, certains langages n'aiment pas qu'on modifie la valeur d'un paramètre.
Une version parfaitement lexicale, portable et compilable par n'importe quel compilateur, pourrait être:

Code :

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

1
2
3
(defun smart-append (x y)
  (let ((y (if (atom y) (list y) y)))
    (if (atom x) (cons x y) (append x y))))

Dans cette version et la précédente, la référence à la variable "y" n'a pas "besoin" de faire référence à la variable "y"!
Je veux dire que le compilateur peut prendre les décisions suivantes:
- la fonction "smart-append" reçoit ses arguments quelque part (généralement dans la pile ou dans des registres)
- je génère un test pour vérifier si ce qui est dans la 2ème place de la pile ("y") est un atome
- si ce n'est pas un atome, goto "la suite"
- (si c'est un atome) je copie en sommet de pile ce qui est dans la 2ème place de la pile, puis j'appelle la fonction "list"
- je récupère le résultat (que je dépile) et le copie dans la 2ème place de la pile (à l'endroit où se trouvait "y")
- "la suite": je génère un test pour vérifier si ce qui est dans la 1ère place de la pile ("x") est un atome
- si ce n'est pas un atome, goto "la suite 2"
- (si c'est un atome) j'appelle directement (sans empilement) la fonction "cons" (avec les 2 arguments qui sont déjà en sommet de pile), je dépile les 2 éléments en tête de pile et je retourne la valeur retournée par la fonction appelée
- "la suite 2": j'appelle directement (sans empilement) la fonction "append" (avec les 2 arguments qui sont déjà en sommet de pile), je dépile les 2 éléments en tête de pile et je retourne la valeur retournée par la fonction appelée

Le code "interprété" fait référence au symbole "y" (quelque part en ram) pour lire et écrire sa valeur (sa "symbol-value").
Dans le "code" généré par le compilateur, il n'est plus question de faire appel au symbole "y": on lit et écrit directement dans la pile, ce qui est beaucoup plus rapide que de lire/écrire en ram.

Tout ça est bien sûr très très approximatif...

[stendhal666]

Merci pour vos réponses qui m'ont emmené bien au-delà de la question posée...
J'ajoute juste qu'après avoir testé la rapidité des 3 définitions:
- celle qui emploie funcall est de loin la plus lente (+25%): donc un point en moins pour le dynamic scope
- les deux autres ont une efficacité équivalente: le compilateur n'a pas profité du (setq y (list y)) pour optimiser. Il s'agit de clozure-cl.