package coq-autosubst-ocaml

This is an OCaml reimplementation of the Autosubst 2 code generator by Stark, Schäfer and Kaiser, which was the main focus of Stark's doctoral dissertation. Autosubst 2 in turn is based on previous work on Autosubst by Schäfer, Tebbi and Smolka.

If you ever were in the situation of looking at metatheorems of languages modelled in Coq (e.g. progress and preservation of lambda calculi) and were bothered by the tediousness of formalizing substitution of de Bruijn indices again, this tool might be for you. Autosubst is a tool that allows you to quickly generate boilerplate code to handle substitutions in languages with binders.

The output is Coq source code that contains

• an implementation of the language via (mutual) inductive types and de Bruijn indices for variables,
• definitions for capture avoiding substitution and renaming on de Bruijn indices,
• lemmas about the behavior and interaction of renaming and substitution,
• and a tactic to solve assumption-free substitution equations.