[OCaml] Les flots de données

Formation

En Ligne

Prix sur demande

Appeler le centre

Avez-vous besoin d'un coach de formation?

Il vous aidera à comparer différents cours et à trouver la solution la plus abordable.

Description

  • Typologie

    Formation

  • Méthodologie

    En ligne

Grâce à cette formation vous pourrez acquérir les connaissances nécessaires qui vous permettrons d’ajouter des compétences à votre profil et obtenir de solides aptitude qui vous offriront de nombreuses opportunités professionnelles.

Questions / Réponses

Ajoutez votre question

Nos conseillers et autres utilisateurs pourront vous répondre

À qui souhaitez-vous addresser votre question?

Saisissez vos coordonnées pour recevoir une réponse

Nous ne publierons que votre nom et votre question

Les Avis

Le programme

Introduction du cours

Les flots de données (les stream d'OCaml) sont des outils très puissants et assez particuliers permettant, entre-autres, d'implémenter facilement des analyseurs syntaxiques descendants. Dans ce tutoriel, nous allons découvrir de quoi il retourne exactement avec une première sous-partie consacrée aux explications théoriques, une deuxième touchant plus le côté pratique et une troisième, plus dense, où l'on étudiera un exemple concret de programme réalisé à l'aide des stream.

Présentation des streamPrésentation générale

Le flot de données, dit stream dans le langage fonctionnel OCaml, est une structure de données d'un genre peut-être assez nouveau pour certains : c'est une structure abstraite. En gros, cela signifie que l'on ne connait pas son implémentation. Ceci est signalé par OCaml à l'aide de "<abstr>" que l'on reverra plus tard. Il peut y avoir plusieurs raisons à garder une implémentation "abstraite" :

  • Soit le type n'est pas représentable avec les moyens mis à disposition par OCaml pour le construire ;

  • Soit l'implémentation est volontairement cachée pour limiter le programmeur aux fonctions de manipulation du type déjà toutes faites.

Comme nous l'avons vu, les stream sont ce que l'on appelle des flots de données. Concrètement, un flot de données est en réalité une suite d'éléments du même type. Attention à ne pas confondre stream, list (liste chaînée) et array (tableau). Il peut être impossible d'arriver à la fin de cette suite, elle peut donc être infinie. En effet, les stream ont quelque chose de particulier : leur caractère paresseux. Cela signifie que chaque élément d'un stream n'est calculé que lorsqu'on le demande. Cette technique possède ses avantages et ses défauts et l'un des grands avantages, que n'ont pas les listes ou les tableaux par exemple, c'est qu'il est possible de créer des stream infinis. Autre caractère notable chez les stream : leur caractère destructif. Ici, cela veut simplement dire qu'une fois qu'un élément d'un stream a été reconnu, il est automatiquement supprimé du flot de données. Cela possède ses avantages et ses défauts aussi. Le regroupement du caractère paresseux et du caractère destructif dans le type stream a une importante conséquence :

  • Quand un élément vient d'être calculé, c'est qu'on a cherché à le reconnaitre et si on l'a reconnu, la définition veut qu'il soit immédiatement retiré du stream. Finalement, on constate que le stream en soi ne contient jamais rien, il retient juste comment il doit calculer le prochain élément ;

Stream et analyse syntaxique descendante

Les stream sont particulièrement utilisés dans les implémentations en OCaml d'analyseurs syntaxiques descendants. En effet, leurs caractéristiques et les fonctionnalités des extensions de camlp4 qui vont avec en font un outil de premier choix. En réalité, certains développeurs de compilateurs n'utilisent OCaml que pour cette structure de données. Nous allons d'ailleurs étudier un "bout" de mini-compilateur dans la troisième et dernière sous-partie.

OCaml met en réalité deux outils particulièrement puissants à disposition pour la construction d'analyseurs syntaxiques :

  • ocamlyacc qui n'est autre qu'une implémentation OCaml du célèbre générateur d'analyseurs syntaxiques Yacc (ou Bison, l'équivalent libre de Yacc). ocamlyacc produit un analyseur syntaxique ascendant, qui part des unités lexicales du programme pour retrouver l'axiome de la grammaire décrivant le langage. Pour plus d'informations, les bons sites ne manquent pas ;

  • Bien entendu, les stream. Comme nous l'avons déjà évoqué, on utilise les stream pour les analyses syntaxiques descendantes, plus simples à implémenter mais généralement moins efficaces que les analyses syntaxiques ascendantes. Dans une telle analyse, on part de l'axiome de la grammaire décrivant le langage pour arriver aux unités lexicales du programme.

Naturellement, ce qui vous intéresse, c'est de savoir comment s'y prendre pour créer et manipuler les stream. C'est au programme de la deuxième sous-partie.

Manipuler les streams

Tout au long du cours, je vais m'appuyer sur l'interpréteur interactif d'OCaml, c'est-à-dire le programme ocaml. Pour compiler avec ocamlc (qui produit du bytecode qui peut être interprété avec ocamlrun), la commande est "ocamlc -pp "camlp4o" source.ml". Pour le compilateur natif ocamlopt, c'est exactement la même chose.

Stream et camlp4

Quand on parle de stream en OCaml, on pense souvent à l'extension du langage camlp4. Mais en réalité, le type abstrait du stream est déjà présent dans le noyau stable d'OCaml et est manipulable grâce aux fonctions fournies par le module Stream. Ce n'est cependant pas très pratique et c'est très limité. Voici un exemple de code créant un stream vide sans utiliser l'extension camlp4 :

# let stm = Stream.of_list [] ;; val stm : '_a Stream.t = <abstr>

Comme on peut le voir, le type du stream en OCaml est en réalité le type Stream.t. Remarquez la signalisation de l'abstraction par <abstr>. Manipuler les stream uniquement avec le module Stream est une tâche très lourde et lassante (nous allons cependant revenir sur ce module à la fin de cette sous-partie). C'est l'une des raisons pour lesquelles les développeurs d'OCaml mettent à disposition l'extension camlp4. "camlp4" signifie "Caml Preprocessor and Pretty-Printer". camlp4 fournit entre-autres une extension de la syntaxe d'OCaml pour faciliter la création et la manipulation des stream, extension qui va nous intéresser ici et dont on va se servir pour le reste du cours.

Ce qui vous intéresse maintenant, c'est de savoir comment utiliser l'extension de la syntaxe pour les stream. Pour la dernière version d'OCaml, il va vous falloir charger deux choses : dynlink.cma puis camlp4o.cma, dans cet ordre précisément.

# #load "dynlink.cma" ;; # #load "camlp4o.cma" ;;

Si tout se passe comme prévu, vous devriez vous retrouver avec un message "Camlp4 Parsing version 3.11.0" (avec votre version d'OCaml si elle est différente de la mienne). Maintenant que cela est fait, camlp4 vous met à disposition une syntaxe de manipulation des stream très proche des array et des list. Pour rappel, la syntaxe pour les tableaux est "[| |]" et pour les listes, il s'agit de "[ ]", et pour les deux (les trois en fait, pour les stream il en sera de même comme nous allons le voir), on sépare chaque élément avec un point-virgule ';'. La syntaxe pour les stream est "[< >]" :

# [< >] ;; - : 'a Stream.t = <abstr>

Le flot de données vide s'écrit "[< >]". La manipulation des stream en utilisant cette syntaxe très légère est cependant assez différente de celle des array ou des list sur deux principaux points :

  • Chaque élément d'un stream doit être précédé d'une apostrophe ''', justement pour signaler qu'il s'agit bien d'un élément ;

  • On introduit la notion de sous-flot. Quand on décrit un stream avec la syntaxe "[< >]", le sous-flot est signalé par l'absence de l'apostrophe.

En gros, en écrivant "[< 'a >]", a est un élément du flot, mais en écrivant [< a >], a est considéré comme un sous-flot. Les sous-flots ne sont en aucun cas à considérer comme des "entités" d'un flot plus grand, ils ne représentent que des parties du flot principal (le terme "sous-flot" peut donc porter à confusion). Le cas du flot vide "[< >]" est particulier. Dans n'importe quel stream, on peut considérer [< >] comme un sous-flot omniprésent. Ainsi, "[< [<>]; 'a; [<>] >]" est strictement équivalant à "[< 'a >]". Petit essai :

# let stm = [< '4 >] ;; val stm : int Stream.t = <abstr> # let stm2 = [< stm; '5 >] ;; val stm2 : int Stream.t = <abstr> # let stm3 = [< stm; 'true >] ;; Characters 19-24: let stm3 = [< stm; 'true >] ;; ^^^^^ Error: This expression has type bool Stream.t but is here used with type int Stream.t

Au terme de ce code, stm est un stream d'entier contenant 4 et stm2 est un stream d'entier contenant 4 et 5, dans cet ordre. Remarquez qu'il est donc extrêmement simple de profiter du concept du sous-flot dans la concaténation de flot. Dans le précédent code, "[< stm; '5 >]" est donc strictement égal à "[< '4; '5 >]". Dans cet exemple, on retrouve aussi le typage fort d'OCaml : impossible de concaténer un stream d'int et un stream de bool et ce type d'erreur est signalé bien avant l'exécution du code.

Il faut également souligner une autre particularité dans la manipulation des stream avec camlp4, qui se trouve dans le filtrage de motif (pattern matching). Il faudra être plus vigilant que pour le filtrage de listes par exemple. Premièrement, il faut savoir que camlp4 introduit un nouveau mot-clef pour le filtrage de motif de stream : "parser". En effet, on écrit plus "match stm with" suivi des différents cas possibles mais "match stm with parser". Le raccourci bien connu du "function" est géré en utilisant "parser" tout seul et en omettant le dernier paramètre (le principe est en fait le même que "function" : on génère une fonction à un paramètre et on le "match" directement ; dans le cas de "parser", ce paramètre est forcément un stream). Deuxièmement, il faut savoir que chaque élément reconnu est retiré du flot, même si le reste du match case concerné peut potentiellement ne plus coller. Voici un petit exemple de filtrage :

let test stm = match stm with parser | [< '1; '2 >] -> "un deux" | [< >] -> "autre"

Ce qui est strictement la même chose que :

let test = parser | [< '1; '2 >] -> "un deux" | [< >] -> "autre"

Il faut également savoir que dans un tel pattern matching, un flot peut être reconnu par un flot plus petit si ce dernier correspond à une partie gauche du flot d'entrée. Par exemple, le flot "[< '1; '2; '3 >]" sera reconnu par le match case "[< '1; '2 >]" si ce dernier est évalué.

Encore une fois, le flot de données vide "[< >]" est à utiliser avec des pincettes. En effet, il ne faut pas le confondre avec la liste vide "[]" par exemple car il filtre tous les stream. En effet, n'importe quel stream "[< s >]" est équivalent à "[< [< >]; s >]", et par conséquent "[< >]" est une partie gauche de tous les stream. Il représente en réalité le cas "autre" ("_" n'est pas adapté pour les stream). Il doit ainsi se retrouver en dernier match case du filtrage. En l'omettant, vous n'aurez cependant aucun warning à la compilation comme on en retrouve dans d'autres cas analogues.

Gérer les erreurs

Bien gérer les erreurs, c'est primordial. Que se passe-t-il si aucun des match case du filtrage n'a été reconnu, et n'a ni même entamé en reconnaissance ? Ce genre de cas est géré à l'aide des exceptions et il y a en a précisément deux qui vont nous intéresser : Stream.Failure et Stream.Error. Stream.Failure est lancée quand aucun match case n'est un possible candidat pour le stream filtré, c'est-à-dire quand aucun premier élément du filtrage ne lui correspond. Stream.Error est beaucoup plus subtil : une telle exception est lancée quand un match case a partiellement reconnu l'entrée, mais que la suite ne colle plus. Cette dernière exception est intéressante dans les cas où l'on doit signaler précisément au programmeur ce qui ne va pas dans un stream donné. En effet, elle possède un attribut de type string, qui si rien n'est précisé est la chaîne vide "". En revanche, là où ça devient bénéfique, c'est quand on précise soi-même un message d'erreur. C'est possible avec l'opérateur "??" et ça se fond totalement dans la syntaxe du stream.

La syntaxe est simple : on sépare l'élément du message d'erreur associé à l'aide de "??". Exemple : la fonction suivante prend en entrée un stream, le filtre avec le motif [< '1; '2 >] est nous indique qu'il manque "2" si "1" a effectivement été reconnu.

let test = parser | [< '1; '2 ?? "Il manque 2 !" >] -> "un deux" | [< >] -> "autre" Algorithmes sur les stream

Le pattern matching de stream va encore beaucoup plus loin et vous allez encore découvrir certaines nouveautés dans cette section. Cette dernière est consacrée à la présentation d'algorithmes couramment utilisés lors de la manipulation de flot de données. Certains algorithmes seront déjà présents dans le module Stream mais il faut bien comprendre que le but ici est purement pédagogique, le but final étant de vous rendre à l'aise avec les stream. De plus, vous aurez ici un petit avant-goût de la puissance des stream.

Nous allons commencer par l'exemple classique : récupérer et retirer le premier élément d'un flot. Comme vous vous en doutez, ces deux actions n'en sont en réalité qu'une. Le nom traditionnel pour cette fonction est "next". Nous allons procéder simplement en considérant un seul cas possible qui sera "[< 'e >]" pour e représentant donc l'élément de tête. Le seul cas où ça ne passera pas est le flot vide, auquel cas une exception est lancée. On obtient donc le simple code suivant :

let next = parser [< 'e >] -> e

Un autre exemple classique est l'implémentation d'une fonction "map" adapté aux stream. Pour rappel, le principe de "map" (que l'on retrouve aussi dans le module List par exemple) est d'appliquer une fonction à chaque élément du conteneur d'entrée et de renvoyer un conteneur semblable mais contenant le retour des différents appels. Dans notre cas, nous allons donc utiliser une fonction récursive qui prend en argument le flot d'entrée et une fonction et qui construira le flot de sortie attendu. La définition fonctionnelle de cette fonction sera donc la suivante : "si le flot est un élément suivi d'un reste, le résultat est le flot contenant le retour de la fonction qui prend l'élément en paramètre suivi du (sous-) flot de sortie de l'appel récursif à "map" sur le reste; si le flot est vide, le résultat est le flot vide". L'idée peut donc très simplement se traduire en OCaml :

let rec map_stream f = parser | [< 'e; r >] -> [< 'f e; map_stream f r >] | [< >] -> [< >]

À présent, nous allons nous intéresser à une autre fonction qui prend en paramètre un stream et qui renvoie son inverse, c'est à dire, en termes plus simples, la même suite d'éléments mais dans l'autre sens. En utilisant le concept du sous-flot, l'idée de l'algorithme est très simple : "l'inverse d'un flot contenant un élément suivi un reste est le flot contenant l'inverse du reste suivi de l'élément; l'inverse du flot vide est le flot vide". En OCaml, on a donc :

let rec reverse = parser | [< 'e; r >] -> [< reverse r; 'e >] | [< >] -> [< >]

Tout à l'heure, j'ai parlé de nouveautés. Effectivement, un concept très puissant peut-être utilisé pour réécrire la précédente fonction reverse. En effet, on peut appeler une fonction et récupérer son retour au sein même d'un match case (retour qui n'est pas forcément de type Stream.t mais dans notre cas si). En résumé, le plus gros du travail peut-être effectué avant "->". Je crois qu'un exemple est plus compréhensible :

let rec reverse = parser | [< 'e; a = reverse >] -> [< a; 'e >] | [< >] -> [< >]

La variable a contient le retour de la fonction reverse qui prend en paramètre le fameux reste qu'on a laissé implicite. En gros, ici on met aussi l'accent sur la définition suivante : "l'inverse d'un stream non vide est l'élément de tête précédé de l'inverse du reste", sauf qu'on définit cet inverse avant l'expression de retour. Nous réutiliserons cette technique assez pratique dans la troisième sous-partie.

Enfin, pour finir cette section, intéressons-nous à un dernier algorithme...

Appeler le centre

Avez-vous besoin d'un coach de formation?

Il vous aidera à comparer différents cours et à trouver la solution la plus abordable.

[OCaml] Les flots de données

Prix sur demande