En programmation informatique , cons( / ˈ k ɒ n z / ou / ˈ k ɒ n s / ) est une fonction fondamentale dans la plupart des dialectes du Langage de programmation Lisp . cons construit des objets mémoire qui contiennent deux valeurs ou des pointeurs vers deux valeurs. Ces objets sont appelés (cons) cellules, cons, Expressions S non atomiques (« NATS ») ou (cons) paires . En jargon Lisp, l’expression “to cons x into y ” signifie construire un nouvel objet avec(cons x y ). La paire résultante a une moitié gauche, appelée le car(le premier élément, ou le contenu de la partie adresse du registre ), et une moitié droite, appelée le (le deuxième élément, ou le contenu du d incrémenter une partie du registre ) .cdr
Il est vaguement lié à la notion orientée objet d’un constructeur , qui crée un nouvel objet avec des arguments, et plus étroitement lié à la fonction constructeur d’un système de type de données algébrique .
Le mot “contre” et des expressions comme “vers contre” font également partie d’un jargon de programmation fonctionnelle plus général. Parfois, les opérateurs qui ont un objectif similaire, en particulier dans le cadre du traitement de liste, sont prononcés “contre”. (Un bon exemple est l’ ::opérateur dans ML , Scala , F# et Elm ou l’ :opérateur dans Haskell , qui ajoute un élément au début d’une liste.)
Utiliser
Bien que les contre-cellules puissent être utilisées pour contenir des paires ordonnées de données, elles sont plus couramment utilisées pour construire des structures de données composées plus complexes, notamment des listes et des arbres binaires .
Paires commandées
Par exemple, l’expression Lisp construit une cellule contenant 1 dans sa moitié gauche (le soi-disant champ) et 2 dans sa moitié droite (le champ). En notation Lisp, la valeur ressemble à :(cons 1 2)carcdr(cons 1 2)
(1 . 2)
Notez le point entre 1 et 2 ; cela indique que l’expression S est une “paire pointée” (une soi-disant “paire contre”), plutôt qu’une “liste”.
Listes
En Lisp, les listes sont implémentées au-dessus des paires cons. Plus précisément, toute structure de liste en Lisp est soit :
- Une liste vide (), qui est un objet spécial généralement appelé nil.
- Une cellule contre dont carest le premier élément de la liste et dont cdrest une liste contenant le reste des éléments.
Cela forme la base d’une structure de liste simple et simple dont le contenu peut être manipulé avec cons, caret cdr. Notez que nilc’est la seule liste qui n’est pas aussi une paire contre. Par exemple, considérons une liste dont les éléments sont 1, 2 et 3. Une telle liste peut être créée en trois étapes :
- Contre 3 sur nil, la liste vide
- Cons 2 sur le résultat
- Contre 1 sur le résultat
qui équivaut à l’unique expression :
( contre 1 ( contre 2 ( contre 3 nul )))
ou sa sténographie :
( liste 1 2 3 )
La valeur résultante est la liste :
(1 . (2 . (3 . néant)))
c’est à dire
*–*–*–néant | | | 1 2 3
qui est généralement abrégé en :
(1 2 3)
Ainsi, conspeut être utilisé pour ajouter un élément au début d’une liste chaînée existante. Par exemple, si x est la liste que nous avons définie ci-dessus, alors produira la liste :(cons 5 x)
(5 1 2 3)
Une autre procédure de liste utile est append, qui concatène deux listes existantes (c’est-à-dire combine deux listes en une seule liste).
Des arbres
Les arbres binaires qui ne stockent que des données dans leurs feuilles sont également facilement construits avec cons. Par exemple, le code :
( contre ( contre 1 2 ) ( contre 3 4 ))
résultats dans l’arbre :
((1 . 2) . (3 . 4))
c’est à dire
* / * * / / 1 2 3 4
Techniquement, la liste (1 2 3) de l’exemple précédent est aussi un arbre binaire, qui se trouve être particulièrement déséquilibré. Pour le voir, il suffit de réorganiser le diagramme :
*–*–*–néant | | | 1 2 3
à l’équivalent suivant :
* / 1 * / 2 * / 3 néant
Utiliser dans la conversation
Les inconvénients peuvent faire référence au processus général d’ allocation de mémoire , par opposition à l’utilisation d’opérations destructives du type de celles qui seraient utilisées dans un langage de programmation impératif. Par example:
J’ai un peu accéléré le code en mettant des effets secondaires au lieu de l’avoir par contre ridiculement.
Mise en œuvre fonctionnelle
Étant donné que Lisp a des fonctions de première classe , toutes les structures de données, y compris les cellules cons, peuvent être implémentées à l’aide de fonctions. Par exemple, dans Scheme :
( définir ( contre x y ) ( lambda ( m ) ( m x y ))) ( définir ( voiture z ) ( z ( lambda ( p q ) p ))) ( définir ( cdr z ) ( z ( lambda ( p q ) q )))
Cette technique est connue sous le nom de codage Church . Il réimplémente les opérations cons , car et cdr , en utilisant une fonction comme “cons cell”. L’encodage d’église est un moyen habituel de définir des structures de données dans le calcul lambda pur , un modèle de calcul abstrait et théorique étroitement lié à Scheme.
Cette implémentation, bien qu’intéressante sur le plan académique, n’est pas pratique car elle rend les contre-cellules indiscernables de toute autre procédure Scheme, et introduit des inefficacités de calcul inutiles.
Cependant, le même type d’encodage peut être utilisé pour des types de données algébriques plus complexes avec des variantes, où il peut même s’avérer plus efficace que d’autres types d’encodage. [1] Cet encodage a également l’avantage d’être implémentable dans un langage typé statiquement qui n’a pas de variantes, comme Java , en utilisant des interfaces au lieu de lambdas.
Voir également
- Lisp (langage de programmation)
- RCA et CDR
- Constructeur (informatique)
- Type de données algébrique
- Consigne de hachage
Références
- ^ “Copie archivée” (PDF) . Archivé de l’original (PDF) le 2010-03-31 . Récupéré le 01/03/2009 .{{cite web}}: Maint CS1 : copie archivée comme titre ( lien )
Liens externes
- SDRAW , code Common Lisp pour le dessin dessine contre les structures cellulaires. De David S. Touretzky.