Rénovation du sous-système Camlp4 d'Objective Caml

Introduction

Introduction, cadre du stage

Introduction, Caml et Objective Caml

Introduction, Camlp4

Simplification, nettoyage et organisation...

Simplification de la procédure de bootstrap

Je bootstrappe, tu bootstrappes, nous bootstrappons

  • L'ancienne procédure était trop compliquée :
  • Dû à la structure hautement bootstrappée de Camlp4.
  • Les sources en deux exemplaires (syntaxe révisée et non-révisée).
  • Pas assez comprise, car pas assez expliquée.
  • Objectif simplicité :
  • Rapprochement du mécanisme d'OCaml.
  • Meilleures explications.
  • Bootstrapper Camlp4 ne doit plus être un frein.

camlp4boot : tout ce qu'il faut, pas plus, pas moins

  • Contenu de camlp4boot :
  • La syntaxe révisée.
  • La syntaxe des parseurs et des grammaires.
  • Les quotations.
  • La syntaxe des macros, et une extension pour déboguer.

Que changer, et à quel moment

  • Doivent être modifiés en premier :
  • La syntaxe du langage d'entrée : les règles de grammaire.
  • La syntaxe du langage de sortie : les chaînes de format du pretty-printeur.
  • Le code produit par les extensions : les quotations (leur sémantique et non leur syntaxe).
  • Peuvent être modifiés dans un deuxième temps :
  • Les types des structures de données présentes dans le code généré.
  • Le nom des fonctions, modules et valeurs exportées.
  • La syntaxe des sources, et des quotations.

Procédure de bootstrap

La cible make bootstrap :
  • Sauvegarde le camlp4boot courant (make backup).
  • Fait la promotion du camlp4boot produit (make promote).
  • Nettoie l'environnement (make clean).
  • Compile tout avec le nouveau camlp4boot (make all).
  • Compare le résultat avec celui utilisé (make compare).
  • Si le point fixe n'est pas atteint il faut relancer make bootstrap.

Abstraction des locations

Historique des locations de Camlp4

Abstraction

  • Choix d'implémentation envisageable
  • Couple de Lexing.position, version actuelle.
  • Couple d'entiers, version précédente.
  • Location.t, comme dans OCaml.
  • unit lorsque les locations sont inutiles.
  • Ou une autre...

Passage à un style fonctionnel

Renommage et fonctorisation

Justification du renommage

Fonctorisation

Module d'extension de syntaxe

open Camlp4
module Id =
  struct let name = ... let version = ... end
(* An extension is just a functor: Syntax -> Syntax *)
module Make (Syntax : Sig.Syntax.S) = struct
  include Syntax ;; open Camlp4.Sig.Camlp4Token
  let foo = Gram.Entry.mk "foo"
  EXTEND Gram
    foo: [ [ ... ] ];
  END;;
  Gram.parse_string foo (Loc.mk "<string>") "foo x?"
end
(* Make it usable via the camlp4 binary. *)
module M = Register.SyntaxExtension(Id)(Make)

Module pré-construit : Camlp4.PreCast

Ajout et remplacement...

Un nouvel analyseur lexical

Un nouvel analyseur lexical

Ajout d'un système de filtrage

Camlp4 : un traducteur source-à-source

Des filtres, et la transformation de programmes devient possible

Map généré, filtrage aisé

Filtres disponibles et exemple

open Camlp4.PreCast
let f = object (self) inherit Ast.map as super
  method expr = function
  | <:expr< $x$ + 0 >> |
    <:expr< 0 + $x$ >> -> self#expr x
  | e -> super#expr e
end in AstFilters.register_str_item f#str_item

Réécriture des pretty-printeurs

Réécriture des pretty-printeurs

  • Se rapprocher de la technologie standard
  • Utilisation du module Format.
  • Parcours récursif descendant.
  • Parenthésage géré manuellement.
  • Les autres choix de design
  • Une classe fonctionnelle (extensibilité, gestion de l'état).
  • Filtrage à l'aide des quotations.

Priorités, et structures ambiguës

Extension des grammaires extensibles

Les grammaires extensibles de Camlp4

EXTEND Gram
  expr:
    [ [ x = expr; "+"; y = expr -> x + y
      | x = expr; "-"; y = expr -> x - y ]
    | [ x = expr; "*"; y = expr -> x * y
      | x = expr; "/"; y = expr -> x / y ]
    | [ x = INT -> int_of_string x
      | "("; e = expr; ")" -> e ] ];
END

Interface fonctorielle, ou pas

Deux modes étaient disponibles.
  • Interface classique :
  • Les entrées de grammaire sont du même type.
  • Les grammaires sont des valeurs accessibles.
  • Interface fonctorielle :
  • Paramétrée par un module de grammaire.
  • Les entrées sont incompatibles entre grammaires.
  • La grammaire du module n'est pas accessible.
  • Maintenant :
  • Statique : ancienne interface fonctorielle.
  • Dynamique : interface classique paramétrée par un module.

Motifs de lexèmes

Exemple de type algébrique des lexèmes

type my_token_type =
  | LIDENT of string
  | UIDENT of string
  | KEYWORD of string
  | STRING of string
  | INT of int * string

Exemple utilisant les nouveaux motifs de lexèmes

EXTEND Gram
expr:
[ [ "let"; `LIDENT i; "="; `INT (i, j);
    `UIDENT "Foo"; "in"; `STRING _ -> Let (s, i, j)
  | `LIDENT ("foo"|"bar" as s) ->
       FooOrBar s (* or patterns and alias *)
  | `ANTIQUOT (("exp"|"" as n), a) -> Ant (n, a)
  | `INT (42, s) -> Int s
  (* s can be 42, 000042, 0x2a, 0b0101010... *)
] ];
END

Transformation d'une règle de grammaire

`ANTIQUOT (("exp"|"" as n), a) -> Ant (n, a)
(* becomes after transformation *)
(([ (* token pattern *)
  Gram.Stoken
   ((function (* predicate in normal form *)
     | ANTIQUOT (("exp" | ""), ) -> true |->false),
    (* the pretty-print string in normal form *)
    "ANTIQUOT ((\"exp\" | \"\"), _)") ]),
 (Gram.Action.mk (* semantic action *)
    (fun (__camlp4_0 : Gram.Token.t) (_loc : Loc.t) ->
       (* this match extracts "n" and "a" *)
       match __camlp4_0 with
       | ANTIQUOT ((("exp" | "" as n)), a) -> Ant(n,a)
       | _ -> assert false)))

Quotations, Méta-élévation, et réflexion

Le système de quotations

  • Description
  • Syntaxe des quotations : <:expr<...>>, <:patt<...>>.
  • Syntaxe des antiquotations : $expr$, $name:expr$.
  • Utilité
  • Inutile de connaître les 200 constructeurs d'Ast.
  • Facilité d'écriture de larges Ast de programme.
  • Limitations du système précédent
  • Antiquotation de liste in-intuitive : <:expr< fun [ $list:pwel$ ] >>.
  • Syntaxe des quotations non-extensibles.

Parseurs standards et parseurs de quotations

Parseur P0, pour la règle de la flèche

  • Parseur standard (P0)
  • Lit un flot de lexèmes et produit un Ast.
  • En simplifiant, int -> string produit TyArr (TyInt, TyStr).
EXTEND Gram
  core_type:
  [ [ t1 = SELF; "->"; t2 = SELF ->
        Ast.TyArr (_loc, t1, t2)
     ...
  ] ];
END

Parseur P1, pour la flèche

  • Parseur P1, expanseur de quotations
  • Produit une expression représentant l'Ast.
  • En simplifiant, int -> string produit ExApp (ExUid "TyArr",ExUid "TyInt",ExUid "TyStr")
EXTEND Gram core_type:
[ [ meta_t1 = SELF; "->"; meta_t2 = SELF ->
    Ast.ExApp (_loc, Ast.ExApp (_loc, Ast.ExApp (_loc,
      Ast.ExAcc (_loc, Ast.ExUid (_loc, "Ast"),
                       Ast.ExUid (_loc, "TyArr")),
      Ast.ExLid (_loc, "_loc")),
    meta_t1), meta_t2)
... ] ];
END

P0 et P1 avec les quotations

P0 et P1 peuvent se réécrire en utilisant P1.
P0 utilisant les quotations t1 = SELF; "->"; t2 = SELF ->
  <:ctyp< $t1$ -> $t2$ >>
P1 utilisant les quotations t1 = SELF; "->"; t2 = SELF ->
  <:ctyp< Ast.TyArr _loc $t1$ $t2$ >>
Peut-on se contenter d'un seul parseur ? meta : <:ctyp< $t1$ -> $t2$ >> ->
       <:ctyp< Ast.TyArr _loc $meta t1$ $meta t2$ >>

Les antiquotations, le cauchemar des quotations

  • Pour se contenter d'un seul parseur :
  • Inclure les règles pour les antiquotations.
  • Utiliser des règles à la place des motifs de lexèmes.
  • Placer les antiquotations dans l'Ast.
  • Introduire les antiquotations dans l'Ast :
  • Sans tout dédoubler : type α t = A of α | B of string
  • Introduction d'un échappement : "\\$name:code"
  • Ajout d'un cas aux catégories syntaxiques.
  • Suppression des listes et des optionnels.
  • Utilisation d'opérateurs binaires et de Ast.XxNil.

Exemple avec les règles de filtrage

Type des règles de filtrage type match_case =
  | McNil of Loc.t
  | McOr of Loc.t * match_case * match_case
  | McArrow of Loc.t * patt * expr * expr
  | McAnt of Loc.t * string
Grammaire abstraite des règles de filtrage
mc ::= (* empty *)
     | mc "|" mc
     | patt "->" expr
     | patt "when" expr "->" expr
     | $s$

Facilité d'écriture

Avant il fallait : <:expr< fun [ $list:mc1 @ mc2 @
  [(<:patt< _ >>, None, <:expr< error... >>)]$ ] >>
Maintenant il suffit de : <:expr< fun [ $mc1$ | $mc2$ | _ -> error... ] >>

Quotations étendues, écriture détendue

On peut désormais écrire : <:expr< arr.{e1, e2, e3, e4} >>
<:expr< parser [: `42; s :] -> s >>
<:expr< EXTEND Gram expr: [[ ... ]]; END >>
<:expr< fun [ <:expr< $x$ + $y$ >> ->
              <:expr< $y$ + $x$ >> ] >>
De plus en syntaxe originale : <:expr< e1; e2; e3 >>
<:expr< arr.{e1, e2, e3, e4} >>
<:expr< parser [< '42; s >] -> s >>
<:expr< function <:expr< $x$ + $y$ >> ->
                 <:expr< $y$ + $x$ >> >>

Factorisation des grammaires

Pour changer la syntaxe officielle.
  • Avant, trois parseurs :
  • La syntaxe originale : pa_o.
  • La syntaxe révisée : pa_r.
  • La syntaxe des quotations : q_MLast.
  • Maintenant, un seul car :
  • Camlp4OCamlRevisedParser : pose la plupart des règles.
  • Camlp4OCamlParser : l'adapte à la syntaxe originale.
  • Camlp4Quotation{Common,Expander} : utilisent les fonctions de méta-élévation.

Conclusion

Conclusion

Questions