Jadis, il était difficile de prévoir si un couple donnerait naissance à des jumeaux. Il y a encore quelques décennies, il était rare de pouvoir confirmer s'il s'agissait simplement de vrais ou de faux jumeaux. De nos jours, ceci est possible dès les premiers mois de grossesse. La science a évolué, et les langages de programmation la suivent.

Cet article va traiter l’implémentation de la logique de vérification de jumeaux dans différents types de langages : JavaScript, Java, Scala et Idris. Le jeu de données sera presque le même tout au long de cet article et se résume par le tableau suivant :

Langage non typé : JavaScript

Modélisation

Commençons par une modélisation minimale du domaine, une classe maman avec la propriété nom, et une classe child avec la propriété âge :

    function maman(name) {
        this.name = name;
    }

    function child(age, maman) {
        this.age = age;
        this.mam = maman;
    }

    function isTwins(c1, c2) {

     var result =  (c1  instanceof child ) && (c2 instanceof child) &&
                   (c1.mam instanceof maman ) && (c2.mam instanceof maman) 
                   && (c1.mam === c2.mam) 
                   && c1.age == c2.age ;

     return (result);
    }

Interprétation

Outre la nature interprétée du langage, on s’intéresse plutôt à l’aspect non typé qui se manifeste dans la fonction isTwins. Cette fonction accepte deux objets en paramètres, et peu importe... c’est le rôle du développeur de faire les checks nécessaires dans l’ordre comme suit :

1. Sur les types : vérifier si c1 et c2 sont des instances de child et s’ils font référence à des instances de mamans
2. Si les deux enfants sont des frères
3. Et enfin, s’ils ont le même âge

La résolution est un peu lourde surtout avec cette histoire de type et de classes. Les langages à nature typée vont permettre de résoudre le premier point ; voyons cela.

Langage Typé : Java

Modélisation

Modélisons le domaine avec les classes Maman et Child :

    public class Maman {
        String name;

        public Maman(String name) {
            this.name = name;
        }
    }

    public class Child {
       public int age;
       public Maman mam;

        public Child(int age, Maman mam) {
            this.age = age;
            this.mam = mam;
        }
    }

Pour vérifier les jumeaux :

    public static boolean isTwins(Child c1, Child c2) {
        return c1.mam == c2.mam && c1.age == c2.age ; 
    }

Interprétation

Pas de vérification sur l’exactitude des types et des classes, on a deux instances de Child qui sont liées à des instances de Maman.

Les checks qui restent délégués aux développeurs sont :

1. Vérifier si les bébés ont la même maman
2. Vérifier s’ils ont le même âge

Mais, il reste un autre point qui nous gêne encore : Est-il possible de définir des types Child comme instances identifiées par leurs mamans respectives ?

Path Dependent Type : Scala

Java ne permet pas de créer des instances dont le type est défini en partie par des instances de classes. Par contre, Scala le permet.

Modélisation

Au lieu de faire passer une instance de Maman en tant que paramètre à la classe Child, on définit la classe Child en tant que classe interne de la classe Maman comme suit :

    case class Maman(name : String) {

      case class Child(age : Int)

      def isTwice(b1 :Child, b2 : Child)={
        b1.age == b2.age
      }
    }

Toute instance de Child aura comme type « Instance de la Maman ».Child

Désormais, m1.isTwice(b11,b22) ne compile pas.

    Error:(15, 761) type mismatch;
     found   : A$A3.this.m2.Child
     required: A$A3.this.m1.Child

Interprétation

Avec le « Path Dependent Type », le rôle du développeur est réduit uniquement à :

1. Vérifier si les bébés ont le même âge

Cette technique fonctionne également si notre méthode isTwice n'est pas définie au sein de la classe Maman, mais dans un autre module. Si c’est le cas, nous pouvons faire usage des types dépendants de méthodes où le type d’un paramètre dépend du paramètre précédent :

    def isTwice(m: Maman)(b1 : m.Child, b2 : m.Child) {
      b1.age == b2.age
    }

    isTwice(m1)(b11,b22)

Par la suite, d’autres techniques seront élaborées avec Scala, mais qui nécessiteront des connaissances avancées. Il serait plus simple de consulter directement la section Idris.

Les valeurs : tagged type (avancé)

Posons encore la question pourquoi nous avons créé les classes Child et Maman ? C’est tout simplement pour avoir des types statiques où notre méthode isTwice vérifie lors de la compilation qu’il s’agisse bien des Child. Pourtant, la classe Child n’est qu’une enveloppe (wrapper) de Int.

Il serait plus simple de passer des Ints à la méthode isTwice sans perdre la notion de type.

Modélisation

On ne peut pas définir la méthode isTwice comme mentionné ci-dessous car on va ouvrir la porte à toutes les utilisations incorrectes et à tous les entiers sans qu’il soient évidemnent des Child.

    def isTwice(m: Maman)(b1 : Int, b2 : Int) {
      b1 == b2
    }

Mais, il serait plus avantageux de faire (b1 == b2) sans avoir recours à b1.age ?

Pour avoir le beurre et l’argent du beurre (traiter des Child comme des entiers), on va tagguer les entiers par les Child.

Pour y parvenir, Child ne sera qu’un trait dans la classe Maman et on va définir deux types Tagged et @@ comme suit (également défini dans scalaz) :

    case class Maman(name : String) {
      trait Child
    }

    type Tagged[U] = { type Tag = U }
    type @@[T, U] = T with Tagged[U]

Pour utiliser ces types avec la classe Int, on pourra utiliser la factory suivante :

    def tag[U](i : Int) : Int @@ U = i.asInstanceOf[Int @@ U]

Ou une autre plus générique :

    object Tag {
      def apply[A, T](a: A): A @@ T = a.asInstanceOf[A @@ T]
    }

Pour définir un Int qui sera à la fois un Child, on devra utiliser ces constructeurs :

    val b11 = tag[m1.Child](1)
    val b12 = tag[m1.Child](1)
    val b21 = tag[m2.Child](5)

Où par exemple b21 a le type :

    b21: @@[Int,m2.Child] = 5

Ainsi, la méthode isTwice peut être réécrite :

    def isTwice(m: Maman)(c1 : Int @@ m.Child, c2 : Int @@ m.Child) = {
      c1 + 0 == c2
    }

Interprétation

On a bien défini des Int, mais qui sont également des Child. Le rôle du développeur ne reste qu’à faire une simple égalité entre les nombres : égalité entre deux nombres.

La méthode isTwice est réduite au maximum et c’est le langage qui se charge du reste.

Pour aller plus loin : cette fois, on veut vérifier s’ils sont de vrais ou faux jumeaux.

Vrais ou faux jumeaux : Dependent Types (avancé mais bon à savoir)

Pour vérifier s’ils sont de vrais ou de faux jumeaux, on aura besoin d'ajouter l’ADN de chaque Child par exemple et supposer que la classe Child possède le «hash» de l’ADN.

Modélisation 1

La méthode isTrueTwice peut être définie comme suit :

    def isTrueTwice(c1: Child, c2 : Child) :Boolean = {
        // d’abord verifier s’il sont des jumeaux 
        c1.age == c2.age &&
        // ensuite faire le check sur l’adn
        c1.adn == c2.adn
    }

Interprétation 1

Par contre, c’est très générique comme paramètre, on revient à la case départ avec la vérification sur les âges.

1. Vérifier s’ils sont des jumeaux
2. Faire le check sur le hash de l’ADN

Il serait plus confortable que le langage vérifie que c1 et c2 aient les mêmes âges dès la phase de compilation : C’est ce qu’on appelle «dependent type» où les valeurs seront des types.

Modélisation 2

Il sera un peu compliqué d’implémenter les «dependent type» avec un langage qui ne les supporte pas par défaut comme on le verra par la suite. Pour y parvenir, on va s’inspirer un peu du pattern fluent builder où la méthode build ne sera accessible que si tous les paramètres obligatoires ont été bien saisis.

Pour rendre les âges comme des types, on va définir les traits suivants :

    sealed trait Nat

    sealed trait Z extends Nat

    sealed trait S[A <: Nat] extends Nat

Z est notre zéro alors que S [A <: Nat] est le successeur du nombre naturel A. Afin que nous puissions créer les nombres naturels de manière récursive : Z == 0, S [Z] == 1, S [S [Z] ] == 2, ...etc.

Nos classes Maman et Child seront :

    case class Maman(name : String) {

      class Child[A <: Nat]( val adn : Int) {

        type age = A

        def isTrueTwice[C](l: Child[age]) ={
          adn == l.adn
        }
      }

      def child[A <: Nat]( adn: Int): Child[A]= {
        new Child(adn)
      }
    }

Notre jeu de données sera le suivant :

    val c1 = m1.child[Z](5)
    val c2 = m1.child[Z](5)
    val c3 = myMother1.child[Z](6)
    val c4 = m1.child[S[Z]](5)

    c1.isTrueTwice(c2) → true
    c1.isTrueTwice(c3) → false
    c1.isTrueTwice(c4) // ne compile pas vu qu'ils n’ont pas déjà le même âge.

Interprétation 2

Scala ne supporte pas les dependent types par défaut (faute de sa nature hybride). Les contournements qu’on vient de faire montrent la difficulté de rendre disponible cette fonctionnalité (bien que Shapeless en tant que librairie, facilite l'utilisation de ces astuces).

D’autres langages supportent cette fonctionnalité par défaut. Idris, à titre d’exemple, est un langage qui commence à prendre de l'ampleur grâce à cette fonctionnalité.

Idris : Les Dependent Types

Bien que ce soit un langage qui commence à naître tout comme nos bébés, Idris commence à faire du bruit grâce à sa syntaxe très proche de Haskell, son paradigme fonctionnel pur, et surtout grâce au support des types dépendants.

Les types dépendants sont notre objectif d'origine. Voyons plus en détails.

Modélisation

Simplifions notre modèle. La classe Child qui est définie et dépend de ses valeurs respectives : Age et le hash de l’ADN. La fonction isTrueTwice ne fait rien sauf renvoyer la valeur true.

    data Child : Nat -> Nat -> Type where
            Nil : Child Z a
            nextYear :  Child k a -> Child (S k) a 



    isTrueTwice: Child m a-> Child m a-> Bool
    isTrueTwice_ _ = True

    c1 : Child 1 2
    c1  = nextYear Nil

    c2 : Child 2 2
    c2  =  nextYear (nextYear Nil)

    c3 : Child 2 2
    c3  =   nextYear (nextYear Nil)

    c4 : Child 2 4
    c4  =   nextYear (nextYear Nil)

    isTrueTwice c3  c2
    True : Bool

Par contre :

    isTrueTwice c3  c4 -- ne compile pas 
    Can't unify
                    Child (fromInteger 2) (fromInteger 4)
            with
                    Child (fromInteger 2) 2

            Specifically:
                    Can't unify
                            2
                    with
                            0

Interprétation

Toute la phase de check est garantie par la signature. Il n'est envisageable de faire appel à isTrueTwice dès la compilation que si les Child ont le même âge et le même hash ADN.

Le rôle du développeur est réduit uniquement à :

1. Rien (renvoyer true)

La nature expressive d’Idris et la manière avec laquelle il traite les valeurs comme des types ajoute plus de sérénité. Rien n’est laissé au hasard et tout est vérifié avant de commencer.

Conclusion

Tout au long de cet article, nous avons essayé de faire le parcours de certaines familles de paradigmes tout en s'appuyant sur des langages particuliers. Certes, il y a d’autres implémentations plus ingénieuses, mais le but de l’article reste d'éviter la comparaison directe entre ces langages et de mettre l'accent sur ces différents paradigmes. D’autres paradigmes supportés par des langages de programmation existent, dont je vous laisse le choix de découvrir, comme Coq, Agda ou VB et Cobol.

Enfin, Idris, Scala ou Haskell possèdent tous un compilateur vers le langage JavaScript.

Références

• The Neophyte's Guide to Scala Part 13: Path-dependent Types

• Practical uses for Unboxed Tagged Types

• A Taste of Dependent Types in Scala

À propos de l'Auteur

Slim Ouertani est un Architecte logiciel avec une expérience dans le monde télécoms et systèmes d’information. Il a participé à la construction et la mise en place de plusieurs solutions, notamment au sein de multi-nationales. Certifié SOA, Java, Spring et MongoDB, Slim est passionné par Scala et JEE.

Vous pouvez en savoir plus sur ses récents travaux sur son blog et le suivre sur Twitter : @ouertani.