Abstract Representation of Binders in OCaml using the Bindlib Library

Rodolphe Lepigre
(Inria, LSV, CNRS, Université Paris-Saclay, Cachan, France)
Christophe Raffalli
(LAMA, CNRS, Université Savoie Mont Blanc, Chambéry, France)

The Bindlib library for OCaml provides a set of tools for the manipulation of data structures with variable binding. It is very well suited for the representation of abstract syntax trees, and has already been used for the implementation of half a dozen languages and proof assistants (including a new version of the logical framework Dedukti). Bindlib is optimised for fast substitution, and it supports variable renaming. Since the representation of binders is based on higher-order abstract syntax, variable capture cannot arise during substitution. As a consequence, variable names are not updated at substitution time. They can however be explicitly recomputed to avoid "visual capture" (i.e., distinct variables with the same apparent name) when a data structure is displayed.

In Frédéric Blanqui and Giselle Reis: Proceedings of the 13th International Workshop on Logical Frameworks and Meta-Languages: Theory and Practice (LFMTP 2018), Oxford, UK, 7th July 2018, Electronic Proceedings in Theoretical Computer Science 274, pp. 42–56.
Published: 3rd July 2018.

ArXived at: http://dx.doi.org/10.4204/EPTCS.274.4 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org