Iron Lambda

Iron Lambda is a collection of Coq formalisations for functional languages of various complexities. The aim of the project is to get the proofs done and not worry too much about using the coolest new approaches.

All proofs use straight deBruijn indices for binders, which are fairly usable once you understand what lifting lemmas are required. They use a "semi-​Chilpala" approach to mechanisation -- most lemmas are added to the global hint and rewrite databases, but if the proof script of a particular lemma was already of a sane length, then we haven't invested time writing tricky LTac code to make it smaller.

Style guidelines:

• Verbose comments explaining what the main definitions and theorems are for. The scripts should be digestable by intermediate Coq users.

• No unicode or infix operators for judgement forms. When I use them in my proofs they make perfect sense, but when you use them in yours they're completely unreadable.

• Heavy use of the 'burn' megatactic. This is in the same vein as Chilpala's 'crush' tactic, but at the time I couldn't work out what 'crush' was doing...

• Uses the 'Case' meta-tactic to add structure.

Installation

• You will need a working version of ​Coq. The proofs are known to work with Coq 8.4.

• We use ​darcs for version control.

  $ darcs get http://code.ouroborus.net/iron/iron-head/
  

​Simple

Simply Typed Lambda Calculus (STLC).

"Simple" here refers to the lack of polymorphism.

​SimplePCF

STLC with booleans, naturals and fixpoint.

​SimpleRef

STLC with mutable references.

The typing judgement includes a store typing.

​SimpleData

STLC with algebraic data and case expressions.

The definition of expressions uses indirect mutual recursion. Expressions contain a list of case-alternatives, and alternatives contain expressions, but the definition of the list type is not part of the same recursive group. The proof requires that we define our own induction scheme for expressions.

​SystemF

Compared to STLC, the proof for SystemF needs more lifting lemmas so it can deal with deBruijn indices at the type level.

​SystemF2

Very similar to SystemF, but with higher kinds.

​SystemF2Data

SystemF2 with algebraic data and case expressions. Requires that we define simultaneous substitutions, which are used when subsituting expressions bound by pattern variables into the body of an alternative. The language allows data constructors to be applied to general expressions rather than just values, which requires more work when defining evaluation contexts.

​SystemF2Store

SystemF2 with algebraic data, case expressions and a mutable store. All data is allocated into the store and can be updated with primitive polymorphic update operators.

​SystemF2Effect

• Still under development.

SystemF2 with a region and effect system.