tuple

Représentation schématique d'un tuple de deux nombres entiers.

Un tuple est une liste immuable et simplement chaînée de valeurs ordonnées.

Il est très facile de créer un tuple car ce type fait partie des littéraux du langage. Toute expression délimitée par des crochets («[» et «]») est un tuple. Par exemple, pour créer un tuple composé de deux nombres entiers, il suffit d'écrire ses nombres entre crochets. Ainsi, [25 87] est un tuple contenant les valeurs 25 et 87.

Les tuples sont intensivement utilisés dans le langage, notamment pour transmettre les arguments des fonctions.

Rappelons qu'en Abstrasy, toutes les fonctions sont variadiques. Elles peuvent recevoir un nombre indéfini d'arguments qui sont stockés dans un tuple que l'on peut récupérer à l'aide de (argv). Bien entendu, le langage offre les opérateurs nécessaires pour utiliser les éléments de ce tuple comme autant d'arguments pour obtenir une fonction d'arité n (c-à-d, à n arguments).

(function 'fx{display (argv)})
(fx 25 87)

⇒

[25 87]

Par conséquent, le type tuple est conçu pour être un conteneur efficace et performant dans la majorité des cas. Son usage est également sûr même dans un environnement concurrent. Ces qualités tiennent principalement de la simplicité de son implémentation. Cependant, cette simplicité sous-entend aussi quelques limitations qui peuvent avoir des conséquences importantes sur les performances des programmes si les tuples ne sont pas utilisés d'une manière judicieuse. Aussi, pour vous aider, ce chapitre donne également quelques indications sur les performances et la complexité des principaux opérateurs. Ces indications vous permettront de faire un bon usage des tuples et d'en tirer meilleur profit.

Comme les tuples contiennent uniquement des valeurs et que leur structure est immuable, ils répondent parfaitement aux exigences de la programmation concurrente. En outre, ils ne présentent aucun risque d'effets de bord et correspondent ainsi aux critères de la programmation fonctionnelle. Par exemple, pour ajouter un élément supplémentaire au début d'un tuple, on crée un nouveau tuple. Cependant, cela ne signifie pas que le tuple original est dupliqué complètement. Le nouvel élément est simplement chaîné devant le premier élément du tuple original qui reste inchangé.

Cette opération peut aisément être réalisée à l'aide de l'opérateur cons qui construit un nouveau tuple en ajoutant simplement les nouvelles valeurs en tête du chaînage.

(define 'A [25 87])
(define 'B (cons A 10))
(display B)

⇒

[10 25 87]

On peut donc schématiser le résultat obtenu de cette manière.

Ajout d'un élément à la tête d'un tuple avec cons.

cons est donc une opération très rapide réalisée en temps constant $O(1)$.

Il en va de même de cdr qui fonctionne sur le principe inverse.

(define 'B [10 25 87])
(define 'A (cdr B))
(display A)

⇒

[25 87]

cdr retourne un nouveau tuple dans lequel le chaînage commence avec le deuxième élément du tuple fournit comme argument. Bien entendu, comme dans le cas de cons, aucune copie n'est nécessaire. cdr construit simplement une nouvelle en-tête qui indique un nouveau point d'entré du chaînage des éléments.

Comme cdr, l'opérateur tail permet d'obtenir un nouveau tuple constitué des n derniers éléments d'un tuple sans nécessiter de duplication.

(define 'x [32 10 25 87])
(define 'y (tail x 2))
(display y)

⇒

[25 87]

Dans l'exemple ci-dessus, on crée le tuple y à l'aide de l'opérateur tail. Celui-ci ne copie aucun élément mais crée simplement une nouvelle en-tête dont le premier élément est le deuxième à partir de la fin de x. Ce qui peut être schématisé comme ceci…

L'opération tail est aussi très rapide. Toutefois, elle n'est pas réalisée en temps constant. Il faut en effet parcourir la liste chaînée pour sélectionner l'élément qui constituera le premier élément du nouveau tuple. tail reste cependant performant car il ne nécessite aucune duplication, ni du contenu, ni de la structure.

Pour extraire le premier élément d'un tuple, il suffit d'utiliser car.

(display (car [1 2 3]))

⇒

1

car est une opération extrêmement performante qui est réalisée en temps constant $O(1)$. Elle s'associe d'ailleurs très bien avec cdr.

(define tp [1 2 3 4 5])
(define '$t tp)
 
(while{$t}
  {
    (display (car $t))
    (set! $t (cdr $t))
  }
)

⇒

1
2
3
4
5

Comme vous pouvez le constater, on peut facilement énumérer les éléments d'un tuple à l'aide de car et de cdr. Bien sûr, ici nous avons utilisé une variable mutable pour y stocker la référence du nouveau tuple obtenu lors de chaque itération à l'aide de cdr. Ce traitement n'a aucun effet sur le tuple original qui reste inchangé et la boucle s'arrête lorsque le tuple $t est vide. Il s'apparente au traitement effectué par un itérateur. Nous en reparlerons un peu plus loin.

On peut également accéder aux éléments d'un tuple à l'aide de leur position index n. Ainsi, si on évalue ([“a” “b” “c” “d”] 2), on obtient “c”. Toutefois, cette méthode d'accès n'est pas performante. Elle nécessite un temps d'évaluation à croissance linéaire proportionnel à la position n recherchée, soit $O(n)$. Par conséquent, si vous devez accéder au données de manière directe à l'aide de la position index des éléments, il est préférable d'utiliser un array où les accès directs sont réalisés en temps constant $O(1)$.

Les tuples sont donc des conteneurs particulièrement efficaces et très légers. Comme leur structure est basée sur une liste d'éléments simplement chaînés et immuables, on peut les utiliser sans craindre d'effets de bord. Les opérateurs car, cons et cdr sont toujours évalués en temps constant $O(1)$. L'opérateur tail nécessite un temps inférieur à celui qui consisterait à recopier les n éléments en fin de tuple, mais le temps nécessaire à son traitement est néanmoins proportionnel à la position du premier élément du nouveau tuple dans le précédent, on le note donc $O(\log n)$. D'autres opérations sont également autorisées, toutefois, leur usage est plus coûteux en ressources.

Pensons par exemple à head qui produit un nouveau tuple en le formant des n premiers éléments d'un autre tuple. Illustrons cela par un exemple.

(define 'a [10 25 87])
(define 'b (head a 2))
(display b)

⇒

[10 25]

Ce qui peut être représenté schématiquement comme ceci…

L'opérateur head nécessite la duplication de la structure de chaînage.

Étant donné que le chaînage des éléments du nouveau tuple est complètement différent de celui du tuple source, head doit reconstruire entièrement une nouvelle structure. Cette opération ne permet pas de partager le chaînage précédent. head est donc une des opérations les moins performantes que l'on puisse réaliser à l'aide de tuples. Elle nécessite en effet la duplication de la structure originale sur les n éléments qui composent le nouveau tuple. On la note donc $O(n)$.

Il est toutefois intéressant de noter que seule la structure est dupliquée. Comme les éléments qui composent le contenu du tuple sont des valeurs, ceux-ci sont immuables et peuvent par conséquent être directement utilisés dans la structure du nouveau conteneur.

Il existe cependant un cas particulier où l'implémentation de l'opérateur head est optimisée pour les tuples. En effet, lorsque la taille de la section du nouveau tuple est identique à la longueur du tuple source, head se contente de créer une nouvelle en-tête qui partage la structure de chaînage du tuple original. Dans ce cas particulier, head est une opération réalisée en temps constant $O(1)$ et qui ne nécessite que très peu de ressources (seulement pour l'en-tête).

Il en va de même pour l'opérateur slice qui permet de créer un nouveau tuple à partir d'une section d'un tuple source.

(define 'a [9 10 25 87])
(define 'b (slice a 1 2))
(display b)

⇒

[10 25]

slice prend plusieurs paramètres. Tout d'abord, le tuple source à partir duquel on va créer le nouveau tuple. Ensuite, il y a la position de départ et la longueur du nouveau tuple.

Dans l'exemple ci-dessus, on crée un nouveau tuple basé sur le contenu de a à partir de la position 1 et sur une longueur de 2 éléments. Dans ce cas, aucune optimisation n'est possible et la structure du nouveau tuple est obtenue par duplication. Par contre dans l'exemple suivant, la structure du nouveau tuple n'est pas dupliquée. Ce slice correspond à un tail.

(define 'a [9 10 25 87])
(define 'b (slice a 1 3))
(display b)

⇒

[10 25 87]

Comme la section correspond à la fin du tuple original, il n'est pas nécessaire de la dupliquer. Seule une en-tête est créer pour indiquer l'élément qui commence le nouveau tuple, comme si on avait écrit (tail a 3).

L'interpréteur est donc conçu pour optimiser automatiquement le traitement des tuples dès lors que cela est possible et que cela ne présente aucun risque d'effet de bord.

Il y a cependant des opérations qu'il n'est pas possible d'optimiser. La plus courante est l'ajout à l'aide de l'opérateur +. Cette opération nécessite inévitablement la dupplication de toutes la structure existante pour produire un nouveau tuple auquel sont ajoutés les arguments de +.

(display (+ [1 2] 3 4 5))

⇒

[1 2 3 4 5]

L'utilisation de + est toutefois acceptable et pratique temps que le tuple à créer reste de petite taille.

Un autre opérateur difficile à optimiser est concat. Cet opérateur réalise la concaténation de plusieurs tuples en un seul. Mis à part celle du dernier tuple ajouté, toutes les structures qui précédent doivent être reconstruites pour obtenir le nouveau tuple.

(display (concat [1 2] [3 4 5] [6 7 8 9 10]))

⇒

[1 2 3 4 5 6 7 8 9 10]

L'utilisation de concat se justifie donc principalement lorsque les tuples manipulés sont de petites tailes.

Pour plus de facilité, vous pouvez facilement créer un itérateur ou un énumérateur à partir de n'importe quel tuple. Pour cela, il suffit d'utiliser l'opérateur iterator ou enumerator. Le premier crée un itérateur dérivé du type Iterator et le second un énumérateur dérivé de Enumerator.

Un itérateur implémente les opérateurs génériques next, next? et truth?, qui permettent respectivement de récupérer l'élément suivant et de savoir s'il y a encore un élément dans la séquence d'itérations. L'énumérateur implémente lui uniquement l'opérateur générique next qui retourne alors l'élément suivant ou rien du tout.

(define 'td [1 2 3 4 5])
(define 'iterateur (iterator td))
(while {next? iterateur} {display (next iterateur)})

⇒

1
2
3
4
5

Contrairement à l'itérateur (dont l'état peut varier entre le moment du test du prédicat next? et la récupération de l'élément suivant à l'aide de next), l'énumérateur peut être partagé par plusieurs processus dans un environnement concurrent. Le traitement de next est atomique. Dès lors, il suffit de l'imbriquer dans une structure short-cut pour s'assurer que tous les éléments sortiront une et une seule fois d'une manière cohérente.

(define 't [1 2 3 4 5 6 7 8 9 10])
 
(define 'enu (enumerator t))
 
(define 'model-acteur{
  (forever{
    (define 'e (shortcut {next enu} {break-loop}))
    (mutex{display (my-actor-id) " : " e})
    (sleep 50) 
  })
})
 
(void (actor model-acteur))
(void (actor model-acteur))
(void (actor model-acteur))
 
(while{actors} {sleep 100})

⇒

actor/27cff058-3f3a-4dec-8518-2ff1b11c53a5 : 1
actor/c6b7b203-2757-4827-9c8f-c43f664d4603 : 2
actor/dd502b46-46f1-4885-8ae9-2d0e37d1fc8d : 3
actor/27cff058-3f3a-4dec-8518-2ff1b11c53a5 : 4
actor/c6b7b203-2757-4827-9c8f-c43f664d4603 : 5
actor/dd502b46-46f1-4885-8ae9-2d0e37d1fc8d : 6
actor/27cff058-3f3a-4dec-8518-2ff1b11c53a5 : 7
actor/c6b7b203-2757-4827-9c8f-c43f664d4603 : 8
actor/dd502b46-46f1-4885-8ae9-2d0e37d1fc8d : 9
actor/27cff058-3f3a-4dec-8518-2ff1b11c53a5 : 10
Ready...

Sans vouloir entrer trop dans les détails, l'exemple ci-dessus partage un même énumérateur entre trois acteurs. Chaque acteur est un processus concurrent qui récupère l'élément suivant de l'énumération basée sur la séquence du tuple. On a ajouté des pauses pour permettre aux acteurs d'interagir d'une manière concurrente. On constate que l'énumération est parfaitement cohérente et qu'il n'y a ni processus affamé ni état manqué.

• +
• array
• string
• tuple