Contexte (TL;DR)

Un de mes meilleurs souvenirs de fac fut le cours de Scheme, où nous avions notamment implémenté un interpréteur de Scheme.

Un des exercices que nous avait donné notre prof — et qui m’a particulièrement marqué — fut de tenter d’implémenter les listes chainées (structure de base de Scheme) en utilisant uniquement les éléments du langage que nous avions implémenté (à savoir lambda, apply, eval).

Autrement dit, on nous demandait d’implémenter une structure à partir de fonctions… et uniquement de fonctions. Impossible donc d’utiliser un simple tuple.

Si l’exercice vous amuse, je vous laisse y réfléchir, revenez quand vous aurez trouvé (ou que — comme moi à l’époque — vous aurez abandonné :p).

C’est bon ? Ok, place aux spoils.

La solution est assez élégante : utiliser une fermeture (qui se charge donc de stocker les données — c’est sa définition), et lui faire accepter une fonction qu’elle appellera avec les données. Si ça vous semble obscur ne paniquez pas, j’expliquerai plus bas.

J’ai récemment voulu recréer une implémentation basée sur ce concept, mais dans le langage que j’utilise maintenant : le Scala.

J’ai été confronté à un problème auquel je n’avais pas pensé : quel type utiliser pour définir cette implémentation ? La réponse qui parait évidente n’est en réalité pas utilisable (explications plus bas). Heureusement, halcat0x15a m’a gentiment aidé en me faisant découvrir forall, un joyau de Haskell (rapporté par Scalaz dans la JVM). (note perso : pour communiquer, nous avons parlé un tout petit peu en japonais/anglais, et beaucoup en Scala :p).

Avant de voir la bête en question, je propose de se pencher sur ce qu’est une implémentation orientée lambda-calcul des listes chainées.

Liste chainée

La plupart des programmeurs connaissent les listes chainées (surtout des développeurs Scala), mais résumons quand même au cas où : il s’agit d’une structure de donnée où chacun des maillons référence le prochain de la liste. Il est donc très facile d’ajouter un maillon au début de liste, sans modifier celle-ci.

Je vais reprendre la convention de Scheme : un maillon est appelé cons, la fonction qui rend le 1er élément du maillon est car et celle qui rend le 2e élément (en général c’est donc le reste de la liste) est cdr.

Je vais créer plusieurs implémentations. Pour éviter les confusions, je vais les nommer Cons0 (avec car0 et cdr0), puis Cons1 et ainsi de suite.

L’implémentation que tout développeur Scala imaginera sans doute est la suivante :

Version classique

case class Cons0[+A, +B](car0: A, cdr0: B)

Cette définition est basée sur l’orientation objet de Scala : car0 et cdr0 sont des méthodes de la classe Cons0.

Attention, il y a une grosse différence entre Cons0 défini ici et :: de la bibliothèque standard de Scala ! Le second élément de Cons0 (cdr0) peut-être de n’importe quel type, tandis que le second élément de :: est forcément de type List[A]. C’est cette plus grande flexibilité qui posera le problème de type que nous verrons plus tard.

case class Cons0[+A, +B](car0: A, cdr0: B)

Voyons comment faire une version plus fonctionnelle (où l’on appelle des fonctions et non des méthodes) :

Avec des fonctions

type Cons1[+A, +B] = (A, B)
def cons1[A, B](a: A, b: B): Cons1[A, B] = (a, b)
def car1[A, B](c: Cons1[A, B]): A = c._1
def cdr1[A, B](c: Cons1[A, B]): B = c._2

Je n’aime vraiment pas utiliser _1 et _2 (qui de surcroit sont des méthodes en Scala)…

Voyons comment faire une version plus jolie :-)

Avec du pattern matching

type Cons2[+A, +B] = (A, B)
def cons2[A, B](a: A, b: B): Cons2[A, B] = (a, b)
def car2[A, B](c: Cons2[A, B]): A = c match { case (a, b) => a }
def cdr2[A, B](c: Cons2[A, B]): B = c match { case (a, b) => b }

(note: il est possible de s’épargner le match facilement, mais cela nécessite de modifier un peu la signature des fonctions. J’ai préféré éviter pour ne pas vous embrouiller d’avantage ☺︎)

Ok, donc cette version me plait mieux : nous utilisons le mécanisme de déconstruction du langage pour ne récupérer que l’élément qui nous intéresse. Je trouve cela plus élégant :-)

Analysons un peu cette version : nous créons un tuple, qui contient les 2 valeurs, puis des fonctions qui viennent piocher la valeur (du tuple) qui les intéresse.

Je reformule : nous stockons les valeurs dans un tuple, afin de ne donner qu’un seul élément aux fonctions car2 et cdr2. Celles-ci déconstruisent cet élément en 2 valeurs, afin de les manipuler (pour ne rendre que l’une des deux).

Nous y sommes presque, il suffit de modifier un petit peu cette formule pour aboutir à la version lambda calcul :-)

Liste chainée fonctionnelle

Pour cette version, nous allons stocker les valeurs dans une fermeture (ou lambda, comme vous préférez). Ce sera cette lambda qui sera appelée avec une fonction en argument, et qui appellera cette fonction en lui fournissant les valeurs stockées.

Je reformule : nous stockons les valeurs dans une lambda, que nous donnerons aux fonctions car et cdr. Celles-ci appelleront la lambda en lui fournissant une fonction qui accepte 2 valeurs, afin de les manipuler (pour ne rendre que l’une des deux).

Malheureusement, c’est ici que nous allons rencontrer un problème avec la déclaration des types ☹.

Commençons par la version simple (qui marche mais que le système de type rend inutile) :

Version naïve — problème de types

type Cons3[A, B, C] = ((A, B) => C) => C
def cons3[A, B, C](a: A, b: B): Cons3[A, B, C] = { f => f(a, b) }
def car3[A, B](c: Cons3[A, B, A]): A = c((a, b) => a)
def cdr3[A, B](c: Cons3[A, B, B]): B = c((a, b) => b)

Cette version semble relativement simple : Cons3 est une fonction qui prend une fonction. car3 appelle l’instance de Cons3 en lui donnant une fonction qui prend 2 arguments et rend le 1er.

(note: oui oui, car3 est une fonction qui prend une fonction qui prend une fonction ☺︎)

Tout le problème vient du fait que nous définissons le type C dans Cons3.

La limitation de cette version est la suivante : car3 peut être appelé uniquement avec une valeur de Cons3 dont le type de C est égal au type de A (par exemple Cons3[Int, String, Int]).

Autrement dit, lorsque l’on créé un Cons3, il faut savoir quelle opération va être effectuée dessus. Et il est impossible d’appeler car3 et cdr3 sur le même Cons3, sauf si A, B et C sont identiques (par exemple Cons3[Int, Int, Int]). Bref, ça n’est pas super utile…

Avant d’attaquer la solution, voyons une version intermédiaire, qui reprend le concept de Cons3 mais triche pour déporter la déclaration de C :

Version objet

Nous allons ici stocker les valeurs dans une classe, qui sera appelée par car et cdr comme s’il s’agissait d’une lambda.

case class Cons4[+A, +B](a: A, b: B) {
  def apply[C](f: (A, B) => C): C = f(a, b)
}
def cons4[A, B](a: A, b: B) = Cons4(a, b)
def car4[A, B](c: Cons4[A, B]): A = c((a, b) => a)
def cdr4[A, B](c: Cons4[A, B]): B = c((a, b) => b)

(note: les implémentations de car3 et car4 sont identiques, seules leurs signatures changent)

Nous sommes revenu à une classe mais au lieu d’appeler ses méthodes ou de la déconstruire, nous allons lui fournir une fonction qu’elle appellera avec les valeurs qu’elle contient. Bref nous allons la traiter comme s’il s’agissait d’une fonction.

L’avantage de cette solution est que le type C n’est pas défini dans Cons4.

C’est peut-être plus clair si l’on écrit car4 sans prendre les raccourcis proposés par Scala :

def car4[A, B](c: Cons4[A, B]): A = c.apply[A]((a, b) => a)

On voit que nous spécifions un type à apply : ce type est le remplaçant de C qu’utilisait car3. Au lieu de devoir définir C dans la signature de Cons4, c’est directement la fonction car4 qui va le spécifier au moment où il en aura besoin ; étant donné qu’il veut rendre le 1er argument, il spécifie que le type est A.

C’est là la solution : il faut reporter le moment où l’on définira le type de retour de la fonction que l’on fourni à Cons, en le mettant dans la méthode apply.

Avant d’aller plus loin, je propose de modifier légèrement la définition de Cons4 comme ceci :

case class Cons4[+A, +B](a: A, b: B) {
  def apply[C]: ((A, B) => C) => C = { f => f(a, b) }
}

Maintenant apply rend une fonction dès qu’elle est appelée, et cette fonction accepte une fonction qu’elle appelle avec a et b. Cela ne change pas grand chose mais me permettra de faire un rapprochement dans la prochaine partie.

Bon en fait si ça change quelque chose : apply est maintenant une fonction qui ne prend pas de paramètre et rend une valeur. Il suffit de changer son type de retour pour changer virtuellement sa signature complète. Cette version est donc beaucoup plus générique.

Maintenant que nous sommes prêts, voyons comment il est possible de généraliser tout cela (de ne pas avoir à se créer une classes pour l’occasion), grâce à Forall.

Forall

Voici la définition de cet outil magique :

trait Forall[G[_]] { def apply[A]: G[A] }

Le principe est le même que la version précédente (Cons4) : le type est spécifié lors de l’appel de apply, pas à l’instanciation de l’objet qui hérite de Forall.

Le fait d’utiliser G[_] puis G[A] est l’astuce qui fait que ça marche :-)

On ne peut pas définir apply sans avoir une idée de son type de retour, mais le but est de ne pas spécifier ce type dans celui de Forall. La solution consiste à fournir un constructeur de type (aussi appelé « type paramétré ») à Forall. On demande donc à l’appelant de préciser le type de apply, et l’on construit le type de retour en utilisant le constructeur de type fourni. Cette solution permet donc bien de préciser le type de apply au moment de son appel, tout en ayant suffit d’informations sur ce type pour être capable de le manipuler. Si ça n’est pas clair, la suite aidera peut-être.

Forall nous permet de définir Cons comme suit :

type Cons5[+A, +B] = Forall[({ type G[C] = ((A, B) => C) => C })#G]

Ok, ça fait un peu peur…

En fait cette syntaxe est très pratique car elle permet de définir un type paramétré dont la définition utilise les types A et B fournis. En gros c’est l’équivalent d’une lambda mais pour les types :-)

Explication : Le type de Forall est un type paramétré qui, lorsqu’on lui fourni un type C, équivaut à ((A, B) => C) => C (bref, Cons3). Le type de apply de Cons5 est donc le même que celui de la 2e version de Cons4 (2e version que j’ai montrée précisément pour ce point ☺︎). La syntaxe #G permet de spécifier que le type est G (tel qu’il a été défini dans la parenthèse ({ type G[C] = … })). (merci halcat0x15a)

Note : Le fork de Scala de Typelevel propose une syntaxe de lambda pour les types. On aurait ainsi pu écrire Forall[[C] => ((A, B) => C) => C], ce qui ressemble plus à une fonction de type ☺︎.

Maintenant que nous avons le type de Cons5, il faut être capable d’en générer des instances :

def cons5[A, B](a: A, b: B): Cons5[A, B] = new Cons[A, B] {
  def apply[C]: ((A, B) => C) => C = { f => f(a, b) }
}

Pareil, le code peut faire peur, mais en fait si on le décompose il n’est pas si complexe :

  • la signature est toujours cons5[A, B](a: A, b: B): Cons5[A, B] (pas si complexe) ;
  • cons5 crée un objet qui hérite de Cons[A, B] ;
  • l’objet créé défini exactement la même méthode apply que la version précédente (Cons4).

Les instances de Cons5 peuvent donc être manipulées exactement comme les instances de Cons4. D’ailleurs les signatures de car5 et cdr5 sont identiques à celles de car4 et cdr4 (respectivement).

def car5[A, B](c: Cons5[A, B]): A = c[A]((a, b) => a)
def cdr5[A, B](c: Cons5[A, B]): B = c[B]((a, b) => b)

Et voilà, nous avons maintenant une version des listes chainées basée sur le lambda calcul :-)

Petite note

Vos yeux inquisiteurs ne l’auront surement pas raté, mais je viens de tricher de manière éhontée. J’ai instancié un objet, dont j’appelle une méthode (apply).

Cette implémentation tire donc partie de l’orientation objet de Scala ☹

Cependant — pour ma défense — je tiens à vous faire remarquer que cet objet a pour unique vocation de régler des problèmes de types. Nous ne stockons aucune information dans l’instance de Forall. Au contraire, la méthode apply de celle-ci ira chercher les valeurs a et b dans son environnement… en agissant donc comme une fermeture ☺︎

De plus, notons qu’il est impossible de s’abstraire totalement de l’orientation objet de Scala : une fonction est ici un objet comportant une méthode apply (et héritant de Function1 (ou 2 ou autre))…

Version finale

Voici le code complet de la version finale.

Ce code reprend exactement la définition de Cons5 et ajoute un peu de sucre (commentaires et helpers) pour le rendre plus sympa.

Conclusion

Je ne suis pas certain de l’utilité de cette structure de données (si une version des listes chainées avec des types hétérogènes vous tente, je vous recommande plutôt de vous pencher sur Shapeless :p), mais elle m’a permis de découvrir de nouveaux éléments du langage Scala.

J’espère que cet article vous aura intéressé, et que je n’ai pas écrit trop de bêtises :-)