ngernest / church-rossser Goto Github PK

This repository contains a formalization of part of Chapter 3 of H.P. Barendregt, "The Lambda Calculus, Its Syntax and Semantics".

The main result shown here is a proof of the Church-Rosser theorem for the untyped lambda calculus, that Barendregt attributes to Tait and Martin-Lof.

The goal of this formalization is an advanced tutorial on the use of Ott/LNgen for working with the locally nameless representation of variable binding. It is intended to follow the Stlc tutorial found in the Penn metalib repository.

To start the tutorial, read overview.md.

This development has been tested with The Coq Proof Assistant, version 8.17.0.

If you have Coq, Ott, metalib and LaTeX installed (see below), the toplevel Makefile supports the following targets:

`make coq`   - compile the coq development
    
`make spec`  - use Ott to generate LaTeX definitions and then produce
               the document [spec/lc.pdf](spec/lc.pdf)
              
`make gen`   - use Ott and LNgen to regenerate the two Coq files 
               listed below.
              
`make clean` - remove all generated files

The command make triggers the coq and spec targets.

The specification of the lambda calculus grammar and associated inductive relations is in the Ott specification in lc.ott. The Makefile then uses this file to generate three files:

• spec/lc-rules.tex, containing LaTeX definitions of the system. This file is imported by spec/lc.mng, a LaTeX file that is preprocessed by Ott to produce spec/lc.pdf.

• coq/lc_ott.v, containing Coq definitions of the inductive datatypes specified in the system, and generated by Ott's locally nameless backend.

• and coq/lc_inf.v, containing auxiliary Coq definitions (open, size, etc.) and proofs about the substitution and free variable functions, generated by LNgen.

These generated files are included in the repository in case you would like to work through the details without installing Ott or LNgen.

To compile this code with Coq, you also need to install a copy of the Metalib library. This library is available from https://github.com/plclub/metalib.

You can install these tools via opam (https://opam.ocaml.org/):

 opam switch create 4.11.1
 opam repo add coq-released https://coq.inria.fr/opam/released
 opam pin coq 8.15.0
 opam pin add coq-metalib https://github.com/plclub/metalib.git

To regenerate the Ott and LNgen definitions, you will need to install these tools separately. The former is available through opam.

 opam install ott

The LNgen tool can be cloned from its repository and built using Haskell.