Ces listes qui n\'en sont pas

[(gile)]

Salut,

On (dont moi) a coutume de dire qu'en LISP il n'y a que des atomes et des listes (excepté nil).
Mais que sont précisément ces listes, indistinctement programmes ou données, qui font du LISP un langage si particulier ?

La manière dont sont représentées les listes de données en LISP pourrait laisser croire à tord qu'il s'agit simplement d'un conteneur ayant autant de cases qu'il y a d'élément dans la liste, un peu comme un tableau (array) à une dimension. Il n'en est rien, les arrays utilisés par d'autre interfaces de programmation ont, en général, une taille fixe et ne peuvent contenir que des éléments de même type.

En interne, le LISP est basé sur l'utilisation de "cellules cons" (cons cells).
Une cellule cons est une double case formée de deux pointeurs (ou adresses) : la tête (head) et la queue (tail). Chacun des pointeurs pouvant pointer sur un atome ou une autre cellule cons.
Le nom de "cellule cons" vient de l'utilisation de la fonction cons pour la construire, les fonctions car (contents of address register) et cdr (contents of decrement register) en retournent respectivement la tête et la queue.

La représentation la plus évidente d'une cellule cons en LISP est la paire pointée. Dans ce cas, la tête comme la queue pointent sur un atome.

(cons 1 2) retourne (1 . 2)
(car (cons 1 2)) retourne 1
(cdr (cons 1 2)) retourne 2

Un cas particulier est celui où la queue pointe sur nil, atome particulier qui représente à la fois une expression vide (), une liste vide '(), un symbole vide (aucune valeur affectée) ou encore faux (false).

(cons 1 nil) ou (cons 1 ()) ou (cons 1 '()) retournent (1)
noter que l'interpréteur réduit les expressions '(1 . nil) et '(1 . ()) à (1)

On entrevoit maintenant mieux comment sont construites les simples listes avec la fonction cons.

(cons 1 (cons 2 (cons 3 (cons 4 nil)))) retourne (1 2 3 4)

'(1 2 3 4) est une représentation simplifiée de '(1 . (2 . (3 . (4 . nil)))) (l'interpréteur réduit celle-ci en celle-là).
Les fonctions lisp list et quote (') ne sont donc que des raccourcis pour construire les listes qui utilisent l'équivalent de cons en interne.
On voit aussi qu'une liste qu'on imaginait volontiers comme quelque chose de linéaire est en fait un arbre binaire.

Il en est de même pour une liste de sous listes (tableau, matrice, ...)

(cons (cons 1 (cons 2 nil))
     (cons (cons 3 (cons 4 nil))
    (cons (cons 5 (cons 6 nil)) nil)
     )
)

 

((1 2) (3 4) (5 6)) est une représentation simplifiée de :
'((1 . (2 . nil)) . ((3 . (4 . nil)) . ((5 . (6 . nil)) . nil)))

On comprend aussi mieux à quoi correspondent les "listes pointées" que construit la fonction vl-list*

(vl-list* 1 2 3 4 5) est équivalent à :
(cons 1 (cons 2 (cons 3 (cons 4 5))))
et retourne :
(1 2 3 4 . 5)

En espérant que cet exposé un peu théorique ne contiennent pas trop d'erreurs et qu'il éclairera ceux que ça intéresse sur les dessous du LISP et l'importance des fonctions fondamentales cons, car et cdr.

[Tramber]

On ne peut plus clair !

 

Mais alors question : à quoi sert donc (vl-list* 1 2 3 4 5) qui renvoie (1 2 3 4 . 5)

Quel différence à l'usage avec (cons 1 (cons 2 (cons 3 (cons 4 5)))) c-à-d '(1 2 3 4 5) ?

[(gile)]

Mais alors question : à quoi sert donc (vl-list* 1 2 3 4 5) qui renvoie (1 2 3 4 . 5)

Quel différence à l'usage avec (cons 1 (cons 2 (cons 3 (cons 4 5)))) c-à-d '(1 2 3 4 5) ?

 

Je n'ai jamais eu à utiliser vl-list* et ne vois pas dans quelles circonstances les "listes pointées" sont intéressantes...

 

Note :

(cons 1 (cons 2 (cons 3 (cons 4 5)))) retourne une liste pointée(1 2 3 4 . 5)

(cons 1 (cons 2 (cons 3 (cons 4 (cons 5 nil))))) retourne (1 2 3 4 5)

 

Les expressions (cons ...) ne sont données ci dessus que pour illustrer le propos, il va de soit qu'à part dans une boucle ou pour les paires pointées demandant une évaluation, il est plus simple d'utiliser list ou quote.

[(gile)]

Salut,

 

À y regarder de plus près, je ne trouve aucun intérêt aux listes pointées si ce n'est celui de maintenir la cohérence avec l'utilisation des cellules cons quand la queue de la cellule la plus imbriquée pointe sur un atome. Mais je ne désespère pas que quelqu'un me contredise...

La plupart des fonctions de traitement des listes ne fonctionnent pas avec les listes pointées (reverse, last, append, length...) et si vl-list-length ne provoque pas d'erreur avec ce type de liste, elle retourne nil ce qui n'est pas d'un grand intérêt...

 

La fonction vl-list*, par contre, peut être intéressante pour simplifier les expressions contenant des imbrications de cons quand on veut ajouter plusieurs éléments au début d'une liste.

 

(vl-list* 1 2 3 '(4 5 6))

est exactement équivalent à :

(cons 1 (cons 2 (cons 3 '(4 5 6))))

les deux retournent :

(1 2 3 4 5 6)

 

J'ai un peu poussé mes investigations pour essayer de mieux comprendre en quoi cons est plus performant que append.

Pour ce faire j'ai utilisé la fonction eq.

 

Petit rappel : la fonction eq retourne T si les deux expressions qui lui sont passées comme arguments pointent sur le même objet (la même adresse en mémoire).

(setq l1 '(1 2 3))

(setq l2 '(1 2 3))

(setq l3 l2)

 

(eq l1 l2) retourne nil parce que même si l1 et l2 contiennent les mêmes valeurs l1 et l2 ne pointent sur deux adresses différentes en mémoire.

(eq l2 l3) retourne T parce que l2 et l3 pointent bien sur le même objet (la même cellule cons).

Nota : (equal l1 l2) retourne t parce que equal compare les valeurs.

 

Comparons maintenant les listes retournées par des expressions utilisant cons ou vl-list* et append.

À partir une liste (l1) on en construit 3 autres en ajoutant 1 et 2 au début de l1 avec les fonctions cons (l2), vl-list* (l3) et append (l4).

 

(setq l1 '(3 4 5))

(setq l2 (cons 1 (cons 2 l1)))

(setq l3 (vl-list* 1 2 l1))

(setq l4 (append '(1 2) l1))

l2, l3 et l4 contiennent bien les même valeurs : (1 2 3 4 5)

 

Si on compare maintenant les listes l2, l3, et l4 privées de leurs deux premiers éléments avec l1 (toutes contiennent (3 4 5)).

(eq (cddr l2) l1) retourne T

(eq (cddr l3) l1) retourne T

(eq (cddr l4) l1) retourne nil

 

Lors de la construction des listes l2, l3 et l4 suivant le processus décris plus haut, dans les trois cas, il y a création d'une cellule cons dont la tête pointe vers 1 et la queue vers une nouvelle cellule cons dont la tête pointe vers 2 et...

Dans les deux premiers cas, la queue pointe directement vers la cellule cons qui contient l1 (qui existe déjà en mémoire).

Dans le dernier cas, la queue pointe vers une nouvelle cellule cons, autrement dit, la liste est entièrement reconstruite.

 

[VDH-Bruno]

Merci, très intéressant ce post :D .

[DenisHen]

Merci pour ce partage...

 

Mais j'ai juste une petite question.

 

Si LstSavant = "Albert EINSTEIN", comment faire pour avoir LstSavant = ("Albert EINSTEIN" "Isaac NEWTON") ?

 

Sachant que j'utilise ton super "InputBox" pour la saisie des noms. J'ai donc une variable à ajouter à LstSavant à chaque fois qu'il y a une saisie. Le retour d'InputBox est la variable Savant.

[(gile)]

Salut,

 

Il me semble que ce que tu demandes est clairement expliqué dans le premier message.

(setq lstSavant nil) ; <- ()
;; ...
(setq lstSavant (cons "Albert EINSTEIN" lstSavant)) ; <- ("Albert EINSTEIN")
;;...
(setq lstSavant (cons "Isaac NEWTON" lstSavant)) ; <- ("Isaac NEWTON" "Albert EINSTEIN")

 

Si la variable lstSavant est déclarée localement il n'est pas nécessaire de faire (setq lstSavant nil) avant le premier (cons ...).

[DenisHen]

Salut (gile), et merci de me répondre.

 

J'ai bien essayé, mais je n’obtient pas ce que j'aimerais.

 

J'ai écris un petit test, le voici :

  (setq Savant "Albert EINSTEIN")
 (setq lstSavant (cons Savant lstSavant))
 (setq Savant "Isaac NEWTON")
 (setq lstSavant (cons Savant lstSavant))

Mais lstSavant = (Isaac NEWTON Albert EINSTEIN) plutôt que ("Isaac NEWTON" "Albert EINSTEIN").

[(gile)]

Si l’interpréteur LISP transforme automatiquement une chaîne de caractères ("Albert EINSTEIN") en une plusieurs symboles (Albert et EINSTEIN), c'est que tu as vraiment un gros soucis avec ton AutoCAD...

[DenisHen]

Effectivement, ma liste était bien construite.

 

Mais à la fin de ma routine, j'avais un (princ lstSavant).

 

J'étais loin de penser que le (princ ne m'indiquerait pas la liste telle qu'elle est...

 

Encore merci (gile) pour ton aide... Et ta patience... ;)