TeX et traitement de données par flot e02 : les Iteratees

Dans cet épisode de la série TeX et traitement de données par flot, abordons le mécanisme utilisé dans ToolXiT pour implémenter le traitement de données par flot. Un peu de code sera présenté en deuxième partie, après une introduction à la solution technique retenue. Cet épisode met en place les outils nécessaires pour permettre de plonger dans ToolXiT lui-même dans les épisodes suivants.

Comme cet épisode reprend du vocabulaire et des concepts introduits dans l’épisode précédent, il est plus que recommandé de le lire avant de continuer plus avant.

Sommaire

• Résumé de l’épisode précédent
• Les besoins
• Iteratees
  • Mékeskecé ?
  • Une implémentation
  • Les compagnons indispensables
• Les Iteratees au service de ToolXiT
  • Les yeux
  • La bouche
  • L’estomac
• Conclusion

Résumé de l’épisode précédent

Lors du premier épisode de cette série j’avais abordé les bases pour lire du TeX.
Si vous ne l’avez pas lu ou oublié, les choses à retenir pour la suite sont les suivantes :

• TeX transforme une séquence de caractères en commandes de composition de document ;
• lire du TeX se fait au fil de l’eau et pas en bloc ;
• certaines commandes TeX sont interprétées à la volée et peuvent modifier la manière dont le reste est lu.

À ce point de notre voyage dans cette série, il est temps de passer au point suivant : le traitement de données par flot.

Les besoins

Afin d’implémenter complètement un analyseur de TeX, plusieurs outils sont indispensables. Premièrement, le comportement de l’analyseur peut changer au cours de l’analyse de l’entrée. Il apparait donc évident que cet analyseur possède un état interne qui peut être lu et mis à jour.
Ensuite, les caractères doivent être transformés en tokens, puis ces tokens transformés en commandes. Ceci met en avant le côté traitement de flot de données et transformation de flot d’un certain type en flot d’un autre type.
De plus, certaines commandes TeX sont développées, ce qui requiert la possibilité de remplacer une séquence de tokens par de nouveaux tokens. Il est donc nécessaire de pouvoir ajouter en tête d’un flot d’entrée de nouveaux éléments.

Ce sont les besoins de base que nous souhaitons couvrir. Regardons maintenant une solution pour les couvrir.

Iteratees

Mékeskecé ?

Maintenant que les besoins sont un peu plus clairement énoncés, parlons de l’outil choisi. Nous verrons ensuite en quoi il répond aux besoins point par point.

Les Iteratees nous viennent tout droit des langages fonctionnels et sont conçus pour décrire des traitements incrémentaux effectués sur une entrée fournie sous forme de séquence (par exemple une séquence de caractères ou d’octets). Ils sont particulièrement utilisés en Haskell pour lequel plusieurs implémentations existent et aussi en Scala notamment au sein du framework Play.
Globalement un Iteratee un objet qui effectue un calcul correspondant à un pas sur un morceau de séquence en entrée. Ce calcul fournit une nouvelle valeur à partir de ce morceau. Il est bien sûr possible que le calcul n’ait pas eu besoin de tout le morceau pour effectuer son calcul, auquel cas, le reste est retourné avec la valeur calculée. De même si plus d’entrée est nécessaire pour effectuer le calcul, l’Iteratee se met en attente de plus d’information pour continuer.

L’idée est vraiment là, on effectue un pas en avant, en consommant ce dont on a besoin et en laissant le reste pour le pas suivant.

Un autre point important à comprendre sur les Iteratees est qu’ils décrivent le calcul à effectuer sur une entrée séquentielle, mais à aucun moment ils n’ont besoin de savoir ce qu’est cette entrée. Les Iteratees sont en quelque sorte nourris depuis l’extérieur, et n’ont aucune connaissance de la manière dont cela est fait.

Les Iteratees sont aussi sans mémoire à priori et ne peuvent pas revenir en arrière sur leur entrée. Cette propriété est intéressante et permet de limiter la taille prise en mémoire car il n’est pas nécessaire de stocker un nombre arbitraire d’éléments de l’entrée pour faire du backtracking.

Si un Iteratee ne sait pas quoi faire d’une entrée il le signale en retournant une valeur d’erreur.

Ces propriétés les rendent particulièrement intéressants dans le traitement de flots de données et le streaming car ils produisent des valeurs au fil de l’eau dès qu’assez de données sont disponibles en entrée. Ça tombe rudement bien vu la nature des données TeX que l’on souhaite traiter dans cette série. Il apparait aussi qu’il est aisé de les combiner afin de produire une séquence de calculs transformant une séquence de valeurs en entrée en une séquence de valeurs en sortie.

Un exemple concret d’Iteratee que l’on peut prendre est le décodage de caractères encodés en UTF-8 en caractères Unicode. Dans cet encodage un caractère est stocké sur un nombre variable d’octets (entre 1 et 4) et un Iteratee s’occupant de l’encodage consommerait en entrée un groupe de un à quatre octets d’une séquence et produirait en sortie un unique caractère unicode. En appliquant de manière répétée cet Iteratee sur une séquence d’octets, nous obtenons une séquence de caractères unicode décodés. Tadam !

Une implémentation

Résumons donc ce que nous venons de dire sur ces mystérieux objets. Un Iteratee :

• mange des morceaux de séquence ;
• attend d’avoir eu tous les morceaux dont il a besoin pour effectuer son calcul ;
• produit une valeur ou une erreur à partir de ces morceaux ;
• laisse aux autres ce qu’il n’a pas mangé.

Qu’il est bien élevé, n’est-ce pas ?

Si maintenant nous souhaitons implémenter tout ça en Scala (ce qui est mon cas), il nous faut plusieurs types :

• Un type pour décrire une entrée séquentielle ;
• Un type de Iteratee qui indique au choix :
  • qu’il en a fini avec l’entrée et retourne donc la valeur calculée et les morceaux d’entrée non consommés,
  • qu’il aimerait bien en avoir plus pour continuer,
  • qu’il ne sait pas quoi faire de cette entrée et retourne donc ce qu’il n’a pas consommé avec une erreur.

L’implémentation complète et à jour est disponible sur GitHub sous licence Apache 2.0.

Pour le type d’entrée, il est assez simple et ne comporte que deux cas : l’entrée est épuisée, des données sont disponibles.

sealed trait Input[+Elt]

case object Eoi extends Input[Nothing]

final case class Chunk[Elt](elts: List[Elt]) extends Input[Elt]

De la même manière, un Iteratee est décrit de la manière suivante :

sealed abstract class Iteratee[In, +Out]

final case class Done[In, Out](v: Out, remaining: Input[In]) extends Iteratee[In, Out]

case class Error[In](t: Throwable, remaining: Input[In]) extends Iteratee[In, Nothing]

case class Cont[In, Out](k: Input[In] => Iteratee[In, Out]) extends Iteratee[In, Out]

• Le constructeur Done est un Iteratee qui a fini son calcul et permet de fournir la valeur résultant du calcul ainsi que l’entrée non consommée ;
• le constructeur Error est un Iteratee qui indique une erreur de traitement ;
• le constructeur Cont est un Iteratee qui indique qu’il a besoin de plus de données pour continuer, avec la fonction décrivant la fin du calcul (appelée continuation).

Ces trois constructeurs représentent les cas de base, mais à eux seuls ils sont assez limités. Le véritable intérêt serait de pouvoir les combiner pour exprimer des calculs plus complexes à partir de calculs plus simples.

Par exemple si nous utilisions les Iteratees pour écrire un analyseur lexical qui accepte en entrée des expressions arithmétiques simples. Si nous supposons que l’on possède déjà un Iteratee qui retourne un entier à partir d’une séquence de caractères, nommé integer pour l’exemple, et un autre qui retourne le premier caractère d’une séquence de caractère, nommé char. Nous avons donc à disposition ceci :

val integer: Iteratee[Char, Int] = ???
val char: Iteratee[Char, Char] = ???

Il serait agréable de pouvoir exprimer la chose suivante : si mon entrée consiste en un entier, suivi du caractère + puis d’un autre entier, alors je les consomme et retourne la somme des deux entiers.

Fort heureusement, ce genre de chose s’exprime plutôt bien avec les Iteratees. Nous ne l’avons pas encore dit jusqu’ici mais un Iteratee est une monade et nous pouvons donc définir l’opérateur de composition >>= que nous nommerons flatMap afin de profiter du sucre syntaxique de Scala.

Qu’est donc cet opérateur de composition ? Cet opérateur s’applique à un Iteratee et prend en paramètre une fonction qui, si on lui donne en entrée le résultat calculé par l’Iteratee auquel il s’applique, retourne un nouvel Iteratee ayant le même type d’entrée et un type de sortie quelconque.

Pfiou !

Traduisons cela dans notre exemple. Tout d’abord il faut ajouter l’opérateur flatMap au type Iteratee, ce qui nous donne :

sealed abstract class Iteratee[In, +Out] {

  def flatMap[Out1](f: Out => Iteratee[In, Out1]): Iteratee[In, Out1] = ???

}

Le but de cette dépêche n’étant pas de décrire toute l’implémentation, je renvoie le lecteur curieux au code et aux différents liens sur le sujet pour l’implémentation de l’opérateur.

Le calcul décrit plus haut peut maintenant s’exprimer en terme de flatMap :

integer.flatMap { i1 =>
  char.flatMap { c =>
    if(c == '+')
      integer.flatMap { i2 =>
        Done(i1 + i2, Eoi)
      }
    else
      Error(new Exception("+ expected", Eoi)
  }
}

En utilisant le sucre syntaxique de Scala et en ajoutant des opérateurs permettant de filtrer le résultat, la même chose peut s’écrire de la manière suivante :

for {
  i1 <- integer
  '+' <- char
  i2 <- integer
} yield i1 + i2

Cette notation est entièrement équivalente à la première mais permet de mettre en avant le côté séquentiel du calcul. Le résultat est un Iteratee qui prend des caractères en sortie et retourne un entier. Cet Iteratee est la composition de deux Iteratee plus simples et permet d’exprimer de manière très déclarative le calcul à effectuer sur le flot d’entrée.

Les compagnons indispensables

Souvenez vous, au début de cette section j’ai mentionné le fait qu’un Iteratee consommait une entrée fournie depuis l’extérieur, sans s’occuper du comment. Il nous faut donc un moyen d’alimenter un Iteratee avec une entrée. Ce moyen existe et s’appelle l’Enumerator.

Un Enumerator produit un flot d’entrée et le passe à un Iteratee. Il continue ainsi jusqu’à ce que :

• soit l’Iteratee dit qu’il en a fini (Done ou Error) ;
• soit l’entrée est épuisée.

Une fois que l’application de l’Iteratee s’arrête, l’Enumerator retourne le dernier Iteratee reçu. Ainsi un Enumerator peut se définir par le type simple suivant :

type Enumerator[In, Out] = Iteratee[In, Out] => Iteratee[In, Out]

Un exemple simple est l’Enumerator qui énumère les éléments d’une liste, que l’on peut définir ainsi :

def enumList[T, U](l: List[T]): Enumerator[T, U] = { it: Iteratee[T, U] =>
  it match {
    case Cont(k) =>
      l match {
        case x :: xs => enumList(xs)(k(Chunk(List(x))))
        case Nil     => k(Eoi)
      }
    case _ =>
      it
  }
}

Nous avons désormais les Iteratees qui décrivent la transformation de données d’entrée en une valeur, les Enumerators qui produisent les données d’entrée et nourrissent un Iteratee. Il nous manque encore un élément crucial : l’exécuteur du calcul pour en avoir le résultat. Dans cet article, un exécuteur est une simple méthode nommée run qui applique l’Enumeratee à un Iteratee et qui transforme le résultat soit en valeur soit en exception.

def run[In, Out](enum: Enumerator[In, Out], it: Iteratee[In, Out]): Out =
  enum(it) match {
    case Done(v, _) => v
    case Error(t, _) => throw t
    case Cont(_) => throw new Exception("Not enough data")
  }

Nous pouvons maintenant utiliser tous ces outils pour faire calculer la somme des entiers fournis en entrée via un Iteratee nommé sum.

val sum: Iteratee[Int, Int] = Cont {
  case Chunk(l) => sum.flatMap(s => Done(s + l.sum, Eoi))
  case Eoi      => Done(0, Eoi)
}

run(enumList(List(1, 2, 3, 4)), sum) // returns 10 as expected

Tout ça pour ça. C’est vrai que sur cet exemple ça parait un peu complexe pour pas grand chose, mais imaginons maintenant que les entiers ne viennent pas d’une liste connue à l’avance mais qu’ils soient envoyés par paquet sur le réseau. Chaque Chunk dans ce cas contiendrait les entiers d’un paquet reçu. Sans modifier notre Iteratee sum d’une seule virgule, le même calcul est effectué. Ce mécanisme permet donc une réelle indépendance du calcul par rapport à la source des données nécessaires pour le réaliser.

Comme autre raison à l’utilisation de ce mécanisme, il est temps d’introduire le dernier compagnon de bataille : l’Enumeratee. Moitié Iteratee moitié Enumerator il permet de transformer un flot d’un type dans un flot d’un autre type, à la fois consommateur et producteur.

type Enumeratee[EltOuter, EltInner, Out] = Iteratee[EltInner, Out] => Iteratee[EltOuter, Iteratee[EltInner, Out]]

Cet objet parait plutôt complexe mais a une utilité non négligeable. Pour comprendre son utilisation, reprenons notre exemple d’Iteratee qui convertit des octets en caractères unicode. Sa signature ressemblerait à celle-ci :

val utf8decoder: Iterate[Byte, Char]

Si maintenant nous disposons d’un Iteratee qui, étant donnée une suite de caractères, retourne les mots. Sa signature est :

val word: Iteratee[Char, String]

Si nous souhaitons composer ces deux Iteratees pour transformer un flot d’octets en flots de mots, nous obtenons un Iteratee qui retourne des mots et qui opère sur les caractères, eux-mêmes produits par un Iteratee interne qui transforme des octets en caractères. Pour ce faire nous pouvons définir un opérateur sequence_stream qui séquence deux Iteratees, le second consommant le résultat du premier.

def sequence_stream[EltOuter, EltInner, Out](it: Iteratee[EltOuter, EltInner]): Enumeratee[EltOuter, EltInner, Out] = ???

val words: Enumeratee[Byte, Char, String] = sequence_stream(utf8decoder)(word)

words transforme donc un flot d’octets en flot de mots.

Les Iteratees au service de ToolXiT

Nous y voilà ! Parlons maintenant de ToolXiT.

Dans la première partie de cette dépêche, nous avons défini des besoins, issus de la discussion du précédent épisode. Si je vous ai parlé d’Iteratee et consort dans la section précédente, vous devez vous douter que c’est parce qu’ils vont être utiles à ToolXiT.
Le but est, rappelons le, de lire un fichier TeX et de le transformer en suite de commandes TeX pour composer un document. Couvrons nous tous nos besoins avec ces outils ?

Lire du TeX nécessite un état interne contenant tout un tas de valeurs. Nous reviendrons sur cet état dans un prochain épisode, pour le moment, nous savons juste qu’il existe et qu’il nous permet d’accéder aux données qui nous intéressent ici en lecture comme en écriture.

La première étape identifiée transforme des caractères en tokens via ce que nous avons appelé les yeux dans la dépêche précédente. La seconde étape prend en entrée des tokens et produit des commandes. Pour produire ces commandes, certaines séquences de tokens peuvent être déroulées en une nouvelle séquence de tokens dans la bouche. Par exemple nous pouvons l’écrire ainsi avec les Iteratees :

val eyes: Iteratee[Char, Token]

val mouth: Iteratee[Token, Command]

val toolxitCore: Enumeratee[Char, Token, Command] = sequence_stream(eyes)(mouth)

Le déroulement de macros requiert de pouvoir ajouter des tokens en tête de l’entrée, ce qui peut s’exprimer comme un Iteratee qui ne consomme rien et laisse en entrée un morceau avec de nouveaux tokens en tête. Une implémentation possible est :

def pushback(el: Elt): Iteratee[Elt, Unit] = Cont {
  case Chunk(l) => Done((), Chunk(el :: l))
  case _        => Done((), Chunk(List(el)))
}

Nos besoins semblent donc bien couverts. Tant mieux, sinon tout le chemin parcouru aurait été inutile.

Les yeux

Le but à atteindre dans un premier temps, est d’exprimer la transformation de suite de caractères en suite de tokens. Ce processus est décrit dans les chapitres 7 et 8 du TeXbook. ToolXiT fait abstraction de l’encodage des caractères dans le flot initial en utilisant les fonction d’entrée/sortie de la bibliothèque standard de Scala et opère donc au plus bas niveau sur des flots de caractères, et pas d’octets.

L’entrée est d’abord pré-traitée pour remplacer des séquences de caractères du style ^^A par leur valeur pour TeX comme décrit dans le chapitre 8. Puis à partir de ces caractères, sont créés des tokens selon les catégories courantes de ces caractères dans l’environnement. Suivant la catégorie, selon les règles du chapitre 7, les tokens sont créés. L’interface de ces yeux est donc la suivante (en version simplifiée pour la clarté de l’exposé) :

class TeXEyes(env: TeXEnvironment) {

  val tokenize: Iteratee[Char, Token]

}

La bouche

Une fois les tokens obtenus, la bouche s’occupe de les dérouler au besoin et d’en faire des commandes. Beaucoup de travail est fait dans cette phase notamment la mise à plat des macros. Des modifications sont apportées à l’environnement, comme par exemple le changement de catégories de certains caractères, de nouvelles définitions de macros. Plusieurs commandes sont interprétées directement par la bouche et ce qui en sort est soit un simple caractère à ajouter au document, soit une séquence de contrôle que la bouche ne comprend pas. Son interface simplifiée est :

class TeXMouth(val env: TeXEnvironment) {

  val command: Iteratee[Token, Command]

}

L’estomac

La suite de l’histoire représente l’estomac et se charge de traiter les commandes qui lui parviennent d’une manière ou d’une autre. Si l’on souhaite réimplémenter totalement TeX, ces commandes sont à interpréter comme décrit dans le TeXbook. Il est aussi possible de vouloir générer du HTML, faire d’autres analyses sur l’entrée, les possibilités sont ouvertes.

Le but de ToolXiT est d’arriver à ce point afin de donner la séquence de commandes que TeX obtiendrait à partir d’une entrée qu’elle soit issue d’un fichier ou un de streaming sur Internet.

Conclusion

Cet article est encore très généraliste et introduit un concept qui peut être utilisé à d’autre fins. Par exemple il peut être utilisé pour analyser un flux JSON, déchiffrer par bloc, etc. L’implémentation des Iteratees telle que décrite dans cet article est volontairement simplifiée par rapport à la définition complètement générique que l’on peut trouver, notamment en Haskell. Cette simplification est due au fait que le but est de l’utiliser dans ToolXiT et pas comme bibliothèque générique, le besoin est donc bien circonscrit.

Si vous souhaitez voir des exemples d’Iteratees de base qui servent à en construire d’autres par combinaison, la classe Iteratees contient tout un tas de définitions simples.

Dans la suite de cette série nous entrerons plus dans les détails de ToolXiT lui même, maintenant que nous avons couvert des aspects plus généraux. En attendant je vous dis à la prochaine fois.

Aller plus loin

• ToolXiT (86 clics)
• Streams and Iteratees (20 clics)
• DLFP: TeX et traitement de données par flot e01 : lire du TeX (118 clics)