Manipuler les Types

Manipuler les Types

> Tutoriel LeekScript

Cet article repose sur la connaissance des expressions, variables, et fonctions. Il vise seulement à offrir un outils de plus pour la résolution de problèmes. De part le fait que le leekscript ne possède pas d'outils d'annotation natif (comme la plupart des langages à typage dynamique), chaque personne aura tendance à avoir sa propre syntaxe.

Objet et Type

Pour rappel, les objets sont simplement quelque chose de manipulable par le langage, on peut les assigner à des variables, les passer en argument, les donner aux retours de fonctions, et les utiliser dans des expressions. En leekscript nous avons accès aux objets de base suivants:

Comme vous pouvez le voir, ces objets ont été rassemblés de manière non anodine. Chaque objet fait partie d'une famille, que l'on appellera type.

Notation

Types Concrets

Chaque objet possède donc un type, et afin de pouvoir raisonner avec, il va nous falloir une mannière de les écrire. Nous utiliserons dans le cadre de cet article la notation suivante: object : Type, le nom du type commençant par une lettre majuscule. Libre à vous d'utiliser un autre système de notation. Voici la liste des types les plus basiques, accompagné de quelques valeurs possibles:

null : Null true, false : Bool 1, -273 : Int 1.0, 2,34 : Float "a", "abc" : String

Les noms utilisés ici restent arbitraires. Ce n'est pas une convention utilisée par la communauté de Leek Wars. Il est aussi possible de rassembler les objets compris dans Int et Float dans une même catégorie Num car il est très rare d'avoir à faire la distinction lorsque nous les manipulons.

Attention, le Leekscript ne supporte pas l'annotation des types, vous devrez vous contentez de les mettre en commentaire si vous souhaitez en garder trace.

// object : Type object; object; // : Type

Types Variables

Cette notation sert à pouvoir représenter la possibilité qu'un objet possède n'importe quel type. On le note de la même manière, mais avec une lettre minuscule en début de nom. object : a, ici, on ne sait pas quel est le type d'object. Cela peut être n'importe quoi. Si on définit otherObject : b, on ne sait pas non plus quel est son type, il peut même être du même type qu'object. Cependant, si nous définissons sameObject : a, nous avons un peu plus d'information. Nous ne savons toujours pas quel est le type exact de sameObject, mais nous savons que c'est le même que celui d'object. Par exemple, si object : Num alors sameObject est aussi de type Num. otherObject pourrait être de type Num, mais il pourrait aussi être de type String ou bien Bool, etc...

Types Paramétrés

Ce sont des types un peu plus complexes. Vous vous êtes surement demandé pourquoi les tableaux et les fonctions n'ont pas été présentés plus tôt. On peut dire, en quelques sorte, qu'ils contiennent d'autres types. Par exemple [1] contient Num, function(x) { return "" + x; } prend n'importe quoi (a) et le retourne sous forme de chaîne de caractères (String).

Pour annoter ces Types, nous utilisons un type concret, suivi d'autres types concrets ou variable. Par exemple, pour un tableau de nombres, nous pouvons l'annoter de la sorte: array : Array Num, et pour un tableau de chaînes de caractères: array : Array String. La fonction qui prenait un objet quelconque et retournait sa représentation sous forme de chaîne de caractères peut être annotée: toString : Function a String. Il est donc possible d'avoir plusieurs types en arguments. Les tableaux associatifs en sont un autre exemple. Par exemple, un tableau associatif qui indique si des cellules sont hors de vue d'un adversaire, peut être annoté: safeCells : Assoc Cell Bool.

À l'avenir, lorsque nous noterons des tableaux ou des fonctions, nous utiliserons une syntaxe plus légère:

array : [Num] toString : a -> String safeCells : {Cell : Bool}

Dans le cas des fonctions ne prenant pas d'argument, nous utiliserons (). Il est possible de l'utiliser par principe dans le retour des fonctions, mais toutes fonction que ne retourne rien, retourne implicitement null en Leekscript. Par exemple, rand : () -> Float, say : String -> () ou bien say : String -> Null.

Lorsque nous voudrons annoter un objet qui peut avoir plusieurs types, mais dont nous avons connaissance de tous, nous utiliserons la notation suivante a | b | ... Il est bien entendu possible d'avoir plus de deux alternatives. Une autre maniere de l'anoter serait Sum a b .... Un exemple de ce genre de type se retrouve dans le retour de getNearestEnemy. Si aucun ennemie n'est en vie, ou bien si ils sont tous situé sur des cases inaccessibles, cette fonction nous retourneras null au lieu d'un identifiant: getNearestEnemy : () -> ID | Null.

Lorsque nous voudrons annoter un objet qui contient plusieurs objets de differents types, utiliserons (a, b, ...). Ce qui correspondrait à Product a b .... Ce type est généralement appelé tuple, ou n-uplet. Il est surtout utile lorsque nous voudrons annoter des fonctions qui prennent plusieurs arguments. En Leekscript 2, il devrait être possible de retourner plusieurs objets en même temps. Pour l'instant, nous devons nous contenter de tableaux de type [a | b | ...], ou d'être astucieux avec les closures. Un exemple de fonction qui prends plusieurs arguments: lineOfSight : (Cell, Cell) -> Bool.

Types Synonymes

Lorsque nous avons annoté safeCells, nous avons fait usage de Cell. Ce type n'existe pas en Leekscript, en réalité, il s'agit d'un Int. Cependant, utiliser Cell est plus clair sur ce que contient safeCells. safeCells : {Int : Bool} reste cependant valide comme annotation. Si on imagine un tableau contenant les identifiants des poireaux et leurs positions sur la carte, {ID : Cell} est bien plus simple à manipuler qu'{Int : Int}. Ainsi, on peut considérer Num = Int | Float

Priorité

Lorsque nous annoterons des types complexes, nous pourrons utiliser des parenthèses pour éviter les ambiguïtés. En ce qui concerne les fonctions, de pars l'évaluation, la priorité est à gauche. Ainsi, une fonction qui prends une fonction en paramètre se notera (a -> b) -> (), mais une fonction qui retourne une fonction se notera () -> (a -> b) qui peut être simplifié en () -> a -> b.

Notation de la Documentation

La documentation utilise une notation différente pour le typage des ses fonctions. Voici quelques exemples avec la notation de la documentation et celle de cet article:

getCellsToUseChip(Nombre chip, Nombre leek) : TableauDeNombres cells arrayFilter(Tableau array, Fonction callback) : Tableau newArray getLife(Nombre leek) : Nombre life say(Chaîne message)

getCellsToUseChip : (Chip, ID) -> [Cell] arrayFilter : ([a], a -> Bool) -> [a] getLife : ID -> Num say : String -> ()

Type d'une Expression

Jusqu'ici nous avons vu uniquement le type d'un objet. Cependant, ce qui nous intéresse, c'est de manipuler ces objets, afin d'obtenir des résultats intéressants pour nos programmes. On peut ainsi annoter le type des expressions qui constitue notre programme. Lorsque vous lisez 1 + 1, vous pensez immédiatement au résultat, il s'agit d'un nombre: 1 + 1 : Num. Pour rappel, un objet seul est aussi une expression (1 : Num), il n'est cependant pas possible de l'évaluer (la réduire) plus. Annoter le résultat d'une expression peut être intéressant, mais lorsque elles deviennent complexes, ou qu'il y a une erreur, il se peut que notre annotation soit incorrect. Afin de s'assurer de la validité de notre type, nous allons décomposer notre expression, assigner un type évident à chaque éléments, et ensuite substituer ces types là où il le faut pour retrouver le type de notre expression une fois réduite. Ainsi, dans le cas de 1 + 1, nous avons trois élément:

Nous pouvons affirmer sans problème que les objets passés à (+) sont bien du type demandé. Si nous détaillons les étapes de la substitution, nous pouvons écrire cela comme suit:

Notez que l'avant dernière étape n'a pas vraiment d'intérêt, et celle d'avant peut être sauté. Elles sont montrées ici afin de rendre explicite la disparition des arguments.

Avec une expression un peu plus complexe, ici obtenir toutes les cellules avec lesquelles nous pouvons cibler nos ennemies en laissant les doublons:

arrayFlatten(arrayMap(getAliveEnemies(), getCellsToUseWeapon), 1) arrayFlatten : (a, 1) -> [a] arrayMap : ([a], a -> b) -> [b] getAliveEnemies : () -> [ID] getCellsToUseWeapon : ID -> [Cell]

getAliveEnemies() : [ID] arrayMap(_, getCellToUseWeapons) : ([ID],) -> Cell arrayMap(getAliveEnemies(), getCellToUseWeapons) : Cell arrayFlatten(arrayMap(getAliveEnemies(), getCellToUseWeapons), 1) : [Cell]

arrayFlatten à un comportement un peu spécial. Par défaut, lorsqu'il ne lui est fournis qu'un argument, elle ignore les sous-niveau et écrase la totalité. Malheureusement, cela sert très rarement. (Jamais dans le cas de l'auteur.) De plus, cela rends plus difficile la compréhension du comportement du programme. Du à cela, nous n'utilisons qu'un niveau de concaténation et le rendons explicite dans le type. Si nous souhaitons utiliser deux niveaux de concaténation, nous écrirons simplement arrayFlatten : ([a], 2) -> [a])

Expressions depuis un Type

Vérifier ce que nous faisons est correct est le travail du compilateur. Ce en quoi la manipulation de type peux nous aider, c'est nous guider lors de la construction de nouvelles expressions. En connaissant les types de ce que nous avons à disposition, et les types de ce que nous voulons obtenir, nous pouvons grandement réduire l'espace de recherche de la solution. Par exemple, si nous souhaitons réduire une liste de nombre en un seul nombre, la librairie standard nous fournit les fonctions suivantes avec le type correspondant:

average : [Num] -> Num sum : [Num] -> Num

count : [a] -> Num

arrayMax : [a] -> a arrayMin : [a] -> a pop : [a] -> a shift : [a] -> a

Cependant, nous aurons rarement la possibilité de trouver directement une fonction qui fait ce que nous voulons. Selon les données disponibles, nous pouvons placer un intermédiaire. En supposant une entrée de type a et une sortie de type b, commencer par faire l'inventaire des fonctions et opérateurs prenant a en entrée, ou retournant b en sortie constitue un bon point de départ. Il n'y a plus qu'à trouver les paires de fonctions dont les types coincident, et si aucune ne correspond, chercher plus loin en ajoutant un niveau d'indirection. Selon le nombre d'entrée ou de sortie à disposition, il est possible que certain types ne voient d'utilité que pour certaines indirections.

Voici exemple de type à résoudre qui était apparu quelques temps avant la préparation de cet article:

getLeekNamed : (String, ID) -> ID | Null function getLeekNamed(name, potentialID) { /* ... */ }

L'objectif était de retourner l'identifiant si le nom lui appartenant était le même que que celui en paramètre, sinon retournait null (pas de retour). Il aurait ensuite été demandé de transformer la fonction pour qu'elle puissent être appliqué à une liste d'identifiant. ((String, [ID]) -> ID | Null) Ainsi, en résolvant d'abord une expression dont nous avons simplifié le type, nous permet ensuite de résoudre le vrai problème de manière relativement simple, en ajoutant le mécanisme de manipulation du type paramétré. Ici, parcourir un tableau.

Aller plus loin

Types Contraints

L'opérateur (+) a été annoté plus haut comme ne fonctionnant que sur les Num. Cependant vous l'avez probablement utilisé pour d'autres types tel que String et []. Si on imagine les nombres comme étant représenté sous forme unaire (ce qui ne tient pas trop la route avec les nombres à virgule, mais faite comme si), alors l'addition devient une concaténation, tout comme pour les chaînes de caractères et les tableaux. Cette opération de concaténation peut être abstrait en tant que classe Concatenable. Avec cette nouvelle notation, nous pouvons maintenant généraliser le type de (+) : Concatenable a => (a, a) -> a. Il existes d'autres opérateurs et fonctions qui fonctionnent de cette manière. Notamment les opérateurs de comparaisons qui demande à ce que le type puissent être ordonné (Ord), et les opérateurs d'égalités qui demande un type pour lequel on puissent vérifier si les valeurs sont égales ou non (Eq).

Vous vous posez probablement la question, après avoir vu le type de (+), pourquoi est-il possible de faire quelque chose comme 1 + " Rue du Néant" ou bien null + [1, 2], et comment le représenter dans le type ? Nous ne le ferons pas. Lorsque les types ne s'accorde pas, soit nous avons une erreur, soit les objets sont automatiquement converties en chaîne de caractères avant de performer l'opération de concaténation.