common-lisp
Contre les cellules et les listes

Listes comme convention

Certaines langues incluent une structure de données de liste. Common Lisp et d'autres langages de la famille Lisp utilisent largement les listes (et le nom Lisp est basé sur l'idée d'un processeur LISt). Cependant, Common Lisp n'inclut pas réellement un type de données de liste primitif. Au lieu de cela, les listes existent par convention. La convention repose sur deux principes:

1. Le symbole nul est la liste vide.
2. Une liste non vide est une contre cellule dont la voiture est le premier élément de la liste et dont le cdr est le reste de la liste.

C'est tout ce qu'il y a aux listes. Si vous avez lu l'exemple appelé Qu'est-ce qu'une cellule contre? , alors vous savez qu'une cellule contre dont la voiture est X et dont le cdr est Y peut être écrite comme (X. Y) . Cela signifie que nous pouvons écrire des listes basées sur les principes ci-dessus. La liste des éléments 1, 2 et 3 est simplement:

(1 . (2 . (3 . nil)))

Cependant, étant donné que les listes sont si courantes dans la famille de langues Lisp, il existe des conventions d’impression spéciales au-delà de la simple notation par paires pour les cellules.

1. Le symbole nil peut aussi être écrit comme () .
2. Lorsque le cdr d'une cellule contre est une autre liste (soit une ( ou une cellule contre)), au lieu d'écrire la cellule contre avec la notation en pointillés, la "liste de notation" est utilisée.

La notation de liste est illustrée plus clairement par plusieurs exemples:

(x . (y . z))   === (x y . z)
(x . NIL)       === (x)
(1 . (2 . NIL)) === (1 2)
(1 . ())        === (1)

L'idée est que les éléments de la liste sont écrits dans l'ordre entre parenthèses jusqu'à ce que le cdr final de la liste soit atteint. Si le cdr final est nul (la liste vide), la parenthèse finale est écrite. Si le cdr final n'est pas nul (auquel cas la liste s'appelle une liste incorrecte ), alors un point est écrit et ensuite ce dernier est écrit.

Qu'est-ce qu'une cellule contre?

Une cellule cons, également appelée paire pointée (en raison de sa représentation imprimée), est simplement une paire de deux objets. Une contre cellule est créée par la fonction cons , et les éléments de la paire sont extraits à l'aide des fonctions car et cdr .

(cons "a" 4)

Par exemple, cela retourne une paire dont le premier élément (qui peut être extrait avec car ) est "a" , et dont le deuxième élément (qui peut être extrait avec cdr ) est 4 .

(car (cons "a" 4))
;;=> "a"

(cdr (cons "a" 4))
;;=> 3

Les cellules peuvent être imprimées en notation par points :

(cons 1 2)
;;=> (1 . 2)

Cons cellules peuvent également être lus dans la notation de la paire en pointillés, de sorte que

(car '(x . 5))
;;=> x

(cdr '(x . 5))
;;=> 5

(La forme imprimée des contre-cellules peut aussi être un peu plus compliquée. Pour en savoir plus à ce sujet, voyez l'exemple sur les cellules contre comme des listes.)

C'est tout; par contre les cellules ne sont que des paires d'éléments créés par la fonction cons , et les éléments peuvent être extraits avec car et cdr . En raison de leur simplicité, les cellules en opposition peuvent constituer un élément de base utile pour des structures de données plus complexes.

Esquisse contre des cellules

Pour mieux comprendre la sémantique des conses et des listes, une représentation graphique de ce type de structures est souvent utilisée. Une cellule cons est généralement représentée avec deux cases en contact, qui contiennent soit deux flèches qui pointent vers la car et les valeurs cdr , soit directement les valeurs. Par exemple, le résultat de:

(cons 1 2)   
;; -> (1 . 2)

peut être représenté avec l'un de ces dessins:

Notez que ces représentations sont purement conceptuelles et ne dénotent pas le fait que les valeurs sont contenues dans la cellule ou sont pointées depuis la cellule: en général, cela dépend de l'implémentation, du type des valeurs, du niveau d'optimisation, etc. Dans le reste de l'exemple, nous utiliserons le premier type de dessin, celui qui est le plus couramment utilisé.

Donc, par exemple:

(cons 1 (cons 2 (cons 3 4)))   ; improper “dotted” list
;; -> (1 2 3 . 4)

est représenté comme:

tandis que:

(cons 1 (cons 2 (cons 3 (cons 4 nil))))  ;; proper list, equivalent to: (list 1 2 3 4)
;; -> (1 2 3 4)

est représenté par:

Voici une structure arborescente:

(cons (cons 1 2) (cons 3 4))
;; -> ((1 . 2) 3 . 4)         ; note the printing as an improper list

L'exemple final montre comment cette notation peut nous aider à comprendre les aspects sémantiques importants du langage. Tout d'abord, nous écrivons une expression similaire à la précédente:

(cons (cons 1 2) (cons 1 2))
;; -> ((1 . 2) 1 . 2)

qui peut être représenté de la manière habituelle comme:

Ensuite, nous écrivons une expression différente, apparemment équivalente à la précédente, ce qui semble confirmé par une représentation imprimée du résultat:

(let ((cell-a (cons 1 2)))
  (cons cell-a cell-a))
;; -> ((1 . 2) 1 . 2)

Mais, si l' on trace le diagramme, nous pouvons voir que la sémantique de l'expression est différente, puisque la même cellule est la valeur à la fois de la car partie et la cdr partie des extérieurs cons (ce qui est, cell-a est partagée) :

et les tests suivants permettent de vérifier que la sémantique des deux résultats est réellement différente au niveau du langage:

(let ((c1 (cons (cons 1 2) (cons 1 2)))
      (c2 (let ((cell-a (cons 1 2)))
            (cons cell-a cell-a))))
  (list (eq (car c1) (cdr c1))
        (eq (car c2) (cdr c2)))
;; -> (NIL T)

Le premier eq est faux car la car et cdr de c1 sont structurellement égaux (c'est vrai par equal ), mais ne sont pas "identiques" (ie "la même structure partagée"), alors que dans le second test le résultat est vrai puisque le car et cdr de c2 sont identiques , c’est-à-dire qu’elles ont la même structure .