Sites Inria

Version française

Séminaire des équipes de recherche

Visitors Unchained

© INRIA Sophie Auvin - G comme Grille

Traversing and transforming abstract syntax trees is difficult to do in a correct, concise, modular, customizable manner -- especially when binding is involved.

  • Date : 22/05/2017
  • Place : Inria de Paris, Salle C334, bâtiment C
  • Guest(s) : François Pottier (Inria Paris)

In the setting of OCaml, I suggest using *visitor classes* as partial, composable descriptions of the operations that one wishes to perform on abstract syntax trees. I will present the *visitors* package, a simple type-directed facility for generating visitor classes.
Even though the visitors package has no knowledge of binding, it can be used to traverse abstract syntax trees that contain variables and binders. I will present *alphaLib*, a library of small hand-written visitor classes, each of which knows about a specific binding construct, a specific representation of names, and/or a specific operation on abstract syntax trees. By combining these components, a wide range of operations can be defined.

Multiple representations of names can be supported, as well as conversions between representations. Binding structure can be described either in a programmatic style, by writing visitor methods, or in a declarative style, via preprogrammed binding combinators.