FLOC 2018: FEDERATED LOGIC CONFERENCE 2018
Abstract Representation of Binders in OCaml using the Bindlib Library

Authors: Rodolphe Lepigre and Christophe Raffalli

Paper Information

Title:Abstract Representation of Binders in OCaml using the Bindlib Library
Authors:Rodolphe Lepigre and Christophe Raffalli
Proceedings:LFMTP Regular papers
Editors: Giselle Reis and Frédéric Blanqui
Keywords:Binders, Higher-order abstract syntax (HOAS), OCaml library
Abstract:

ABSTRACT. 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.

Pages:15
Talk:Jul 07 17:00 (Session 31H: Implementation)
Paper: