Algorithmic Equality for the Polymorphic Lambda-calculus (G-version)

We discuss completeness of algorithmic equality for typed lambda-terms with respect to declarative equality of lambda-terms. This case-study is part of ORBI, Open challenge problem Repository for systems reasoning with Binders. For a detailed description of the proof and a discussion regarding other systems see (Felty et al, 2014).

The mechanization highlights several aspects:

  • Context schemas with alternative assumptions
  • Induction on universally quantified objects
  • Stating and proving properties in a generalized context
  • Reasoning using context subsumption

Syntax

The polymorphic lambda-calculus is introduced with the following declarations:

LF tp : type =
| arr : tp → tp → tp
| all : (tp → tp) → tp;

--name tp T a.

LF term : type =
| app : term → term → term
| lam : (term → term) → term
| tlam : (tp → term) → term
| tapp : term → tp → term;

--name term M x.

Judgements and Rules

We describe algorithmic and declarative equality for the polymorphic lambda-calculus as judgements using axioms and inference rules. The Beluga code is a straightforward HOAS encoding of the associated rules.

Algorithmic Equality for types

We add the judgement for type equality atp of type tm -> tm -> type along with inference rules for universal quantifiers at_al and arrow types at_arr. 

LF atp : tp → tp → type =
| at_al : ({a : tp} atp a a → atp (T a) (S a)) → atp (all T) (all S)
| at_arr : atp T1 T2 → atp S1 S2 → atp (arr T1 S1) (arr T2 S2);

--name atp Q u.

Algorithmic Equality for terms

We extend the term equality judgement given for the untyped lambda-calculus with rules for type abstraction ae_tl and type application ae_ta. 

LF aeq : term → term → type =
| ae_a : aeq M1 N1 → aeq M2 N2 → aeq (app M1 M2) (app N1 N2)
| ae_l :
  ({x : term} aeq x x → aeq (M x) (N x)) →
    aeq (lam (\x. M x)) (lam (\x. N x))
| ae_tl :
  ({a : tp} atp a a → aeq (M a) (N a)) →
    aeq (tlam (\a. M a)) (tlam (\a. N a))
| ae_ta : aeq M N → atp T S → aeq (tapp M T) (tapp N S);

--name aeq D u.

Note that type equality atp A B can be defined independently of term equality aeq M N. In other words, aeq M N depends on atp A B, but not vice-versa.

Declarative Equality for types

We define declarative equality for types in order to establish its equivalence with algorithmic equality and prove completeness. Rules for reflexivity, transitivity, and symmetry are explicitly derived. 

LF dtp : tp → tp → type =
| dt_al : ({a : tp} dtp a a → dtp (T a) (S a)) → dtp (all T) (all S)
| dt_arr : dtp T1 T2 → dtp S1 S2 → dtp (arr T1 S1) (arr T2 S2)
| dt_r : dtp T T
| dt_t : dtp T R → dtp R S → dtp T S
| dt_s : dtp T S → dtp S T;

--name atp P u.

Declarative Equality for terms

Declarative equality for terms is encoded similarly to its counterpart. Again, we are extending the Untyped Equality case study to account for polymorphism with constructors for type abstraction de_tl and type application de_ta 

LF deq : term → term → type =
| de_l :
  ({x : term} deq x x → deq (M x) (N x)) →
    deq (lam (\x. M x)) (lam (\x. N x))
| de_a : deq M1 N1 → deq M2 N2 → deq (app M1 M2) (app N1 N2)
| de_tl :
  ({a : tp} dtp a a → deq (M a) (N a)) →
    deq (tlam (\a. M a)) (tlam (\a. N a))
| de_ta : deq M N → dtp T S → deq (tapp M T) (tapp N S)
| de_r : deq M M
| de_t : deq M L → deq L N → deq M N
| de_s : deq T S → deq S T;

Context declarations

Just as types classify expressions, contexts are classified by context schemas.

schema atpCtx = block (a : tp, _t : atp a a);

Since the case for lambda-abstraction lam deals with term assumptions while the type abstraction tlam introduces type assumptions, we need to specify alternating assumptions. This alternation of blocks is described by using + in Beluga's concrete syntax. 

schema aeqCtx = block (x : term, _u : aeq x x)
  + block (a : tp, _t : atp a a);

schema dtpCtx = block (a : tp, u : atp a a, _t : dtp a a);

schema deqCtx = block (x : term, u : aeq x x, _t : deq x x)
  + block (a : tp, u : atp a a, _t : dtp a a);

Proof of Reflexivity for Types

The reflexivity for types is implemented as a recursive function called reftp of type: {Γ:atpCtx}{T:[Γ |- tp]}[Γ |- atp T T]. This can be read as: for all contexts g that have schema atpCtx, for all types T, we have a proof that [g |- atp T T]. Quantification over contexts and contextual objects in computation-level types is denoted between braces {}; the corresponding abstraction on the level of expressions is written as mlam g => mlam T1 => e. 

rec reftp : {Γ : atpCtx} {T : (Γ ⊢ tp)} (Γ ⊢ atp T T) =
mlam Γ ⇒ mlam T ⇒
  case [Γ ⊢ T] of
  | [Γ ⊢ #p.1] ⇒ [Γ ⊢ #p.2]
  | [Γ ⊢ all (\x. T)] ⇒
    let [Γ, b : block (a : tp, _t : atp a a) ⊢ D[…, b.1, b.2]] =
      reftp [Γ, b : block (a : tp, _t : atp a a)] [Γ, b ⊢ T[…, b.1]] in
    [Γ ⊢ at_al (\x. \w. D)]
  | [Γ ⊢ arr T S] ⇒ let [Γ ⊢ D1] = reftp [Γ] [Γ ⊢ T] in
    let [Γ ⊢ D2] = reftp [Γ] [Γ ⊢ S] in [Γ ⊢ at_arr D1 D2];

In the proof for refltp we begin by introducing and T followed by a case analysis on [Γ |- T] using pattern matching. There are three possible cases for T:

  • Variable case. If T is a variable from g, we write [Γ |- #p.1] where #p denotes a parameter variable declared in the context g. Operationally, #p can be instantiated with any bound variable from the context g. Since the context g has schema atpCtx, it contains blocks a:tp , _t:atp a a;. The first projection allows us to extract the type component, while the second projection denotes the proof of _t:atp a a;.
  • Existential case. If T is an existential quantification, then we extend the context and appeal to the induction hypothesis by making a recursive call. Beluga supports declaration weakening which allows us to use T that has type [Γ, a:tp |- tp] in the extended context [Γ, b:block a:tp , _t: atp a a]. We simply construct a weakening substitution .. b.1 with domain g, a:tp and range g, b:block a:tp , _t: atp a a that essentially renames a to b.1 in T. The recursive call returns [Γ, b:block a:tp , _t:atp a a |- D[.., b.1 , b.2]]. Using it together with rule at_la we build the final derivation.
  • Arrow case. If T is an arrow type, we appeal twice to the induction hypothesis and build a proof for [Γ |- atp (arr T S) (arr T S)].

Proof of Reflexivity for Terms

The recursive function ref encodes the proof reflexivity for terms. The type signature reads: for all contexts g that have schema aeqCtx, for all terms M, we have a proof that [g |- aeq M M]. 

rec ref : {Γ : aeqCtx} {M : (Γ ⊢ term)} (Γ ⊢ aeq M M) =
mlam Γ ⇒ mlam M ⇒
  case [Γ ⊢ M] of
  | [Γ ⊢ #p.1] ⇒ [Γ ⊢ #p.2]
  | [Γ ⊢ lam (\x. M)] ⇒
    let [Γ, b : block (y : term, _t : aeq y y) ⊢ D[…, b.1, b.2]] =
      ref [Γ, b : block (y : term, _t : aeq y y)] [Γ, b ⊢ M[…, b.1]] in
    [Γ ⊢ ae_l (\x. \w. D)]
  | [Γ ⊢ app M1 M2] ⇒ let [Γ ⊢ D1] = ref [Γ] [Γ ⊢ M1] in
    let [Γ ⊢ D2] = ref [Γ] [Γ ⊢ M2] in [Γ ⊢ ae_a D1 D2]
  | [Γ ⊢ tlam (\a. M)] ⇒
    let [Γ, b : block (a : tp, _t : atp a a) ⊢ D[…, b.1, b.2]] =
      ref [Γ, b : block (a : tp, _t : atp a a)] [Γ, b ⊢ M[…, b.1]] in
    [Γ ⊢ ae_tl (\x. \w. D)]
  | [Γ ⊢ tapp M T] ⇒ let [Γ ⊢ D1] = ref [Γ] [Γ ⊢ M] in
    let [Γ ⊢ D2] = reftp [Γ] [Γ ⊢ T] in [Γ ⊢ ae_ta D1 D2];

This time, there are five possible cases for our meta-variable M:

  • Variable case. If M is a variable from g, we write [Γ |- #p.1] where #p denotes a parameter variable declared in the context g. Operationally, #p can be instantiated with any bound variable from the context g. Since the context g has schema aeqCtx, it contains blocks x:tm , ae_v:aeq x x. The first projection allows us to extract the term component, while the second projection denotes the proof of aeq x x.
  • Lambda-abstraction case. If M is a lambda-term, then we extend the context and appeal to the induction hypothesis by making a recursive call. Automatic context subsumption comes into play again, allowing us to use M that has type [Γ, x:tm |- tm] in the extended context [Γ, b:block y:tm , ae_v: aeq y y]. We simply construct a weakening substitution .. b.1 with domain g, y:tm and range g, b:block y:tm , ae_v:aeq y y. that essentially renames y to b.1 in M. The recursive call returns [Γ, b:block y:tm , ae_v:aeq y y |- D[.., b.1 b.2]]. Using it together with rule ae_l we build the final derivation.
  • Term application case. If M is an application, we appeal twice to the induction hypothesis and build a proof for [Γ |- aeq (app M1 M2) (app M1 M2)].
  • Type abstraction case. If M is a type abstraction, then we extend the context and appeal to the induction hypothesis by making a recursive call. We use M that has type [Γ, a:tp |- tp] in the extended context [Γ, b:block a:tp , _t: atp a a] and construct a weakening substitution .. b.1 with domain g, a:tp and range g, b:block a:tp , _t: atp a a that essentially renames a to b.1 in T. The recursive call returns [Γ, b:block a:tp , _t:atp a a |- D[.., b.1, b.2]]. Using it together with rule at_la we build the final derivation.
  • Type application case. If M is a type application, we appeal twice to the induction hypothesis and build a proof for [Γ |- aeqCtx (tapp M T) (tapp M T)].

Proof of Transitivity for Types

rec transtp : (Γ : atpCtx) (Γ ⊢ atp T R) → (Γ ⊢ atp R S) → (Γ ⊢ atp T S) =
fn ae1 ⇒ fn ae2 ⇒
  case ae1 of
  | [Γ ⊢ #p.2] ⇒ ae2
  | [Γ ⊢ at_al (\a. \u. D1[…, a, u])] ⇒
    let [Γ ⊢ at_al (\a. \u. D2[…, a, u])] = ae2 in
    let [Γ, b : block (a : tp, _t : atp a a) ⊢ D[…, b.1, b.2]] =
      transtp [Γ, b : block (a : tp, _t : atp a a) ⊢ D1[…, b.1, b.2]]
        [Γ, b ⊢ D2[…, b.1, b.2]] in [Γ ⊢ at_al (\a. \u. D[…, a, u])]
  | [Γ ⊢ at_arr D1 D2] ⇒ let [Γ ⊢ at_arr D3 D4] = ae2 in
    let [Γ ⊢ D] = transtp [Γ ⊢ D1] [Γ ⊢ D3] in
    let [Γ ⊢ D'] = transtp [Γ ⊢ D2] [Γ ⊢ D4] in [Γ ⊢ at_arr D D'];

Proof of Transitivity for Terms

rec trans : (Γ : aeqCtx) (Γ ⊢ aeq T R) → (Γ ⊢ aeq R S) → (Γ ⊢ aeq T S) =
fn ae1 ⇒ fn ae2 ⇒
  case ae1 of
  | [Γ ⊢ #p.2] ⇒ ae2
  | [Γ ⊢ ae_l (\x. \u. D1)] ⇒ let [Γ ⊢ ae_l (\x. \u. D2)] = ae2 in
    let [Γ, b : block (x : term, _t : aeq x x) ⊢ D[…, b.1, b.2]] =
      trans [Γ, b : block (x' : term, _t : aeq x' x') ⊢ D1[…, b.1, b.2]]
        [Γ, b ⊢ D2[…, b.1, b.2]] in [Γ ⊢ ae_l (\x. \u. D)]
  | [Γ ⊢ ae_a D1 D2] ⇒ let [Γ ⊢ ae_a D3 D4] = ae2 in
    let [Γ ⊢ D] = trans [Γ ⊢ D1] [Γ ⊢ D3] in
    let [Γ ⊢ D'] = trans [Γ ⊢ D2] [Γ ⊢ D4] in [Γ ⊢ ae_a D D']
  | [Γ ⊢ ae_tl (\a. \u. D1[…, a, u])] ⇒
    let [Γ ⊢ ae_tl (\a. \u. D2[…, a, u])] = ae2 in
    let [Γ, b : block (a : tp, _t : atp a a) ⊢ D[…, b.1, b.2]] =
      trans [Γ, b : block (a : tp, _t : atp a a) ⊢ D1[…, b.1, b.2]]
        [Γ, b ⊢ D2[…, b.1, b.2]] in [Γ ⊢ ae_tl (\x. \u. D)]
  | [Γ ⊢ ae_ta D1 Q1] ⇒ let [Γ ⊢ ae_ta D2 Q2] = ae2 in
    let [Γ ⊢ D] = trans [Γ ⊢ D1] [Γ ⊢ D2] in
    let [Γ ⊢ Q] = transtp [Γ ⊢ Q1] [Γ ⊢ Q2] in [Γ ⊢ ae_ta D Q];

Proof of Symmetry for Types

rec symtp : (Γ : atpCtx) (Γ ⊢ atp T R) → (Γ ⊢ atp R T) =
fn ae ⇒
  case ae of
  | [Γ ⊢ #p.2] ⇒ ae
  | [Γ ⊢ at_al (\x. \u. D)] ⇒
    let [Γ, b : block (a : tp, _t : atp a a) ⊢ D'[…, b.1, b.2]] =
      symtp [Γ, b : block (a : tp, _t : atp a a) ⊢ D[…, b.1, b.2]] in
    [Γ ⊢ at_al (\x. \u. D')]
  | [Γ ⊢ at_arr D1 D2] ⇒ let [Γ ⊢ D1'] = symtp [Γ ⊢ D1] in
    let [Γ ⊢ D2'] = symtp [Γ ⊢ D2] in [Γ ⊢ at_arr D1' D2'];

Proof of Symmetry for Terms

rec sym : (Γ : aeqCtx) (Γ ⊢ aeq T R) → (Γ ⊢ aeq R T) =
fn ae ⇒
  case ae of
  | [Γ ⊢ #p.2] ⇒ ae
  | [Γ ⊢ ae_l (\x. \u. D)] ⇒
    let [Γ, b : block (x : term, _t : aeq x x) ⊢ D'[…, b.1, b.2]] =
      sym [Γ, b : block (x : term, _t : aeq x x) ⊢ D[…, b.1, b.2]] in
    [Γ ⊢ ae_l (\x. \u. D')]
  | [Γ ⊢ ae_a D1 D2] ⇒ let [Γ ⊢ D1'] = sym [Γ ⊢ D1] in
    let [Γ ⊢ D2'] = sym [Γ ⊢ D2] in [Γ ⊢ ae_a D1' D2']
  | [Γ ⊢ ae_tl (\x. \u. D)] ⇒
    let [Γ, b : block (a : tp, _t : atp a a) ⊢ D'[…, b.1, b.2]] =
      sym [Γ, b : block (a : tp, _t : atp a a) ⊢ D[…, b.1, b.2]] in
    [Γ ⊢ ae_tl (\x. \u. D')]
  | [Γ ⊢ ae_ta D Q] ⇒ let [Γ ⊢ D'] = sym [Γ ⊢ D] in
    let [Γ ⊢ Q'] = symtp [Γ ⊢ Q] in [Γ ⊢ ae_ta D' Q'];

Proof of Completeness for Types

rec ctp : (Γ : dtpCtx) (Γ ⊢ dtp T S) → (Γ ⊢ atp T S) =
fn e ⇒
  case e of
  | [Γ ⊢ #p.3] ⇒ [Γ ⊢ #p.2]
  | [Γ ⊢ dt_r] ⇒ reftp [Γ] [Γ ⊢ _]
  | [Γ ⊢ dt_arr F1 F2] ⇒ let [Γ ⊢ D1] = ctp [Γ ⊢ F1] in
    let [Γ ⊢ D2] = ctp [Γ ⊢ F2] in [Γ ⊢ at_arr D1 D2]
  | [Γ ⊢ dt_al (\x. \u. F)] ⇒
    let [Γ, b : block (a : tp, u : atp a a, _t : dtp a a) ⊢ D[…, b.1, b.2]] =
      ctp [Γ, b : block (a : tp, u : atp a a, _t : dtp a a) ⊢ F[…, b.1, b.3]]
    in [Γ ⊢ at_al (\x. \v. D)]
  | [Γ ⊢ dt_t F1 F2] ⇒ let [Γ ⊢ D2] = ctp [Γ ⊢ F2] in
    let [Γ ⊢ D1] = ctp [Γ ⊢ F1] in transtp [Γ ⊢ D1] [Γ ⊢ D2]
  | [Γ ⊢ dt_s F] ⇒ let [Γ ⊢ D] = ctp [Γ ⊢ F] in symtp [Γ ⊢ D];

Proof of Completeness for Terms

rec ceq : (Γ : deqCtx) (Γ ⊢ deq T S) → (Γ ⊢ aeq T S) =
fn e ⇒
  case e of
  | [Γ ⊢ #p.3] ⇒ [Γ ⊢ #p.2]
  | [Γ ⊢ de_r] ⇒ ref [Γ] [Γ ⊢ _]
  | [Γ ⊢ de_a F1 F2] ⇒ let [Γ ⊢ D1] = ceq [Γ ⊢ F1] in
    let [Γ ⊢ D2] = ceq [Γ ⊢ F2] in [Γ ⊢ ae_a D1 D2]
  | [Γ ⊢ de_l (\x. \u. F)] ⇒
    let
      [Γ, b : block (x : term, u : aeq x x, _t : deq x x) ⊢ D[…, b.1, b.2]] =
      ceq
        [Γ, b : block (x : term, u : aeq x x, _t : deq x x) ⊢ F[…, b.1, b.3]]
    in [Γ ⊢ ae_l (\x. \v. D)]
  | [Γ ⊢ de_t F1 F2] ⇒ let [Γ ⊢ D2] = ceq [Γ ⊢ F2] in
    let [Γ ⊢ D1] = ceq [Γ ⊢ F1] in trans [Γ ⊢ D1] [Γ ⊢ D2]
  | [Γ ⊢ de_s F] ⇒ let [Γ ⊢ D] = ceq [Γ ⊢ F] in sym [Γ ⊢ D]
  | [Γ ⊢ de_tl (\a. \u. F[…, a, u])] ⇒
    let [Γ, b : block (a : tp, u : atp a a, _t : dtp a a) ⊢ D[…, b.1, b.2]] =
      ceq [Γ, b : block (a : tp, u : atp a a, _t : dtp a a) ⊢ F[…, b.1, b.3]]
    in [Γ ⊢ ae_tl (\x. \v. D)]
  | [Γ ⊢ de_ta F1 P2] ⇒ let [Γ ⊢ Q2] = ctp [Γ ⊢ P2] in
    let [Γ ⊢ D1] = ceq [Γ ⊢ F1] in [Γ ⊢ ae_ta D1 Q2];
Download the code

© Computation and Logic Group McGill University Logo
Department of Computer Science, McGill University
3480 University Street, Montreal, Quebec, Canada, H3A 0E9