adamc@223: (* Copyright (c) 2008-2009, Adam Chlipala
adamc@182:  * 
adamc@182:  * This work is licensed under a
adamc@182:  * Creative Commons Attribution-Noncommercial-No Derivative Works 3.0
adamc@182:  * Unported License.
adamc@182:  * The license text is available at:
adamc@182:  *   http://creativecommons.org/licenses/by-nc-nd/3.0/
adamc@182:  *)
adamc@182: 
adamc@257: (* begin hide *)
adamc@259: Require Import Arith Eqdep List.
adamc@257: 
adamc@257: Require Import Axioms DepList Tactics.
adamc@257: 
adamc@257: Set Implicit Arguments.
adamc@257: (* end hide *)
adamc@257: 
adamc@184: 
adamc@182: (** %\chapter{Intensional Transformations}% *)
adamc@182: 
adamc@260: (** The essential benefit of higher-order encodings is that variable contexts are implicit.  We represent the object language's contexts within the meta language's contexts.  For translations like CPS conversion, this is a clear win, since such translations do not need to keep track of details of which variables are available.  Other important translations, including closure conversion, need to work with variables as first-class, analyzable values.
adamc@260: 
adamc@260:    Another example is conversion from PHOAS terms to de Bruijn terms.  The output format makes the structure of variables explicit, so the translation requires explicit reasoning about variable identity.  In this chapter, we implement verified translations in both directions between last chapter's PHOAS language and a de Bruijn version of it.  Along the way, we show one approach to avoiding the use of axioms with PHOAS. *)
adamc@260: 
adamc@257: (* begin hide *)
adamc@257: 
adamc@257: Inductive type : Type :=
adamc@257: | Nat : type
adamc@257: | Arrow : type -> type -> type.
adamc@257: 
adamc@257: Infix "-->" := Arrow (right associativity, at level 60).
adamc@257: 
adamc@257: Fixpoint typeDenote (t : type) : Set :=
adamc@257:   match t with
adamc@257:     | Nat => nat
adamc@257:     | t1 --> t2 => typeDenote t1 -> typeDenote t2
adamc@257:   end.
adamc@257: 
adamc@257: Module Phoas.
adamc@257:   Section vars.
adamc@257:     Variable var : type -> Type.
adamc@257: 
adamc@257:     Inductive exp : type -> Type :=
adamc@257:     | Var : forall t,
adamc@257:       var t
adamc@257:       -> exp t
adamc@257: 
adamc@257:     | Const : nat -> exp Nat
adamc@257:     | Plus : exp Nat -> exp Nat -> exp Nat
adamc@257: 
adamc@257:     | App : forall t1 t2,
adamc@257:       exp (t1 --> t2)
adamc@257:       -> exp t1
adamc@257:       -> exp t2
adamc@257:     | Abs : forall t1 t2,
adamc@257:       (var t1 -> exp t2)
adamc@257:       -> exp (t1 --> t2).
adamc@257:   End vars.
adamc@257: 
adamc@257:   Definition Exp t := forall var, exp var t.
adamc@257: 
adamc@257:   Implicit Arguments Var [var t].
adamc@257:   Implicit Arguments Const [var].
adamc@257:   Implicit Arguments Plus [var].
adamc@257:   Implicit Arguments App [var t1 t2].
adamc@257:   Implicit Arguments Abs [var t1 t2].
adamc@257: 
adamc@257:   Notation "# v" := (Var v) (at level 70).
adamc@257: 
adamc@257:   Notation "^ n" := (Const n) (at level 70).
adamc@257:   Infix "+^" := Plus (left associativity, at level 79).
adamc@257: 
adamc@257:   Infix "@" := App (left associativity, at level 77).
adamc@257:   Notation "\ x , e" := (Abs (fun x => e)) (at level 78).
adamc@257:   Notation "\ ! , e" := (Abs (fun _ => e)) (at level 78).
adamc@257: 
adamc@257:   Fixpoint expDenote t (e : exp typeDenote t) : typeDenote t :=
adamc@257:     match e with
adamc@257:       | Var _ v => v
adamc@257:         
adamc@257:       | Const n => n
adamc@257:       | Plus e1 e2 => expDenote e1 + expDenote e2
adamc@257:         
adamc@257:       | App _ _ e1 e2 => (expDenote e1) (expDenote e2)
adamc@257:       | Abs _ _ e' => fun x => expDenote (e' x)
adamc@257:     end.
adamc@257: 
adamc@257:   Definition ExpDenote t (e : Exp t) := expDenote (e _).
adamc@257: 
adamc@257:   Section exp_equiv.
adamc@257:     Variables var1 var2 : type -> Type.
adamc@257: 
adamc@257:     Inductive exp_equiv : list { t : type & var1 t * var2 t }%type
adamc@257:       -> forall t, exp var1 t -> exp var2 t -> Prop :=
adamc@257:     | EqVar : forall G t (v1 : var1 t) v2,
adamc@257:       In (existT _ t (v1, v2)) G
adamc@257:       -> exp_equiv G (#v1) (#v2)
adamc@257: 
adamc@257:     | EqConst : forall G n,
adamc@257:       exp_equiv G (^n) (^n)
adamc@257:     | EqPlus : forall G x1 y1 x2 y2,
adamc@257:       exp_equiv G x1 x2
adamc@257:       -> exp_equiv G y1 y2
adamc@257:       -> exp_equiv G (x1 +^ y1) (x2 +^ y2)
adamc@257: 
adamc@257:     | EqApp : forall G t1 t2 (f1 : exp _ (t1 --> t2)) (x1 : exp _ t1) f2 x2,
adamc@257:       exp_equiv G f1 f2
adamc@257:       -> exp_equiv G x1 x2
adamc@257:       -> exp_equiv G (f1 @ x1) (f2 @ x2)
adamc@257:     | EqAbs : forall G t1 t2 (f1 : var1 t1 -> exp var1 t2) f2,
adamc@257:       (forall v1 v2, exp_equiv (existT _ t1 (v1, v2) :: G) (f1 v1) (f2 v2))
adamc@257:       -> exp_equiv G (Abs f1) (Abs f2).
adamc@257:   End exp_equiv.
adamc@258: 
adamc@258:   Definition Wf t (E : Exp t) := forall var1 var2, exp_equiv nil (E var1) (E var2).
adamc@257: End Phoas.
adamc@257: (* end hide *)
adamc@257: 
adamc@260: (** The de Bruijn version of simply-typed lambda calculus is defined in a manner that should be old hat by now. *)
adamc@260: 
adamc@257: Module DeBruijn.
adamc@257:   Inductive exp : list type -> type -> Type :=
adamc@257:     | Var : forall G t,
adamc@257:       member t G
adamc@257:       -> exp G t
adamc@257: 
adamc@257:     | Const : forall G, nat -> exp G Nat
adamc@257:     | Plus : forall G, exp G Nat -> exp G Nat -> exp G Nat
adamc@257: 
adamc@257:     | App : forall G t1 t2,
adamc@257:       exp G (t1 --> t2)
adamc@257:       -> exp G t1
adamc@257:       -> exp G t2
adamc@257:     | Abs : forall G t1 t2,
adamc@257:       exp (t1 :: G) t2
adamc@257:       -> exp G (t1 --> t2).
adamc@257: 
adamc@257:   Implicit Arguments Const [G].
adamc@257: 
adamc@257:   Fixpoint expDenote G t (e : exp G t) : hlist typeDenote G -> typeDenote t :=
adamc@257:     match e with
adamc@257:       | Var _ _ v => fun s => hget s v
adamc@257:         
adamc@257:       | Const _ n => fun _ => n
adamc@257:       | Plus _ e1 e2 => fun s => expDenote e1 s + expDenote e2 s
adamc@257:         
adamc@257:       | App _ _ _ e1 e2 => fun s => (expDenote e1 s) (expDenote e2 s)
adamc@257:       | Abs _ _ _ e' => fun s x => expDenote e' (x ::: s)
adamc@257:     end.
adamc@257: End DeBruijn.
adamc@257: 
adamc@257: Import Phoas DeBruijn.
adamc@257: 
adamc@257: 
adamc@257: (** * From De Bruijn to PHOAS *)
adamc@257: 
adamc@260: (** The heart of the translation into PHOAS is this function [phoasify], which is parameterized by an [hlist] that represents a mapping from de Bruijn variables to PHOAS variables. *)
adamc@260: 
adamc@257: Section phoasify.
adamc@257:   Variable var : type -> Type.
adamc@257: 
adamc@257:   Fixpoint phoasify G t (e : DeBruijn.exp G t) : hlist var G -> Phoas.exp var t :=
adamc@257:     match e with
adamc@257:       | Var _ _ v => fun s => #(hget s v)
adamc@257: 
adamc@257:       | Const _ n => fun _ => ^n
adamc@257:       | Plus _ e1 e2 => fun s => phoasify e1 s +^ phoasify e2 s
adamc@257: 
adamc@257:       | App _ _ _ e1 e2 => fun s => phoasify e1 s @ phoasify e2 s
adamc@257:       | Abs _ _ _ e' => fun s => \x, phoasify e' (x ::: s)
adamc@257:     end.
adamc@257: End phoasify.
adamc@257: 
adamc@257: Definition Phoasify t (e : DeBruijn.exp nil t) : Phoas.Exp t :=
adamc@257:   fun _ => phoasify e HNil.
adamc@257: 
adamc@260: (** It turns out to be trivial to establish the translation's soundness. *)
adamc@260: 
adamc@257: Theorem phoasify_sound : forall G t (e : DeBruijn.exp G t) s,
adamc@257:   Phoas.expDenote (phoasify e s) = DeBruijn.expDenote e s.
adamc@257:   induction e; crush; ext_eq; crush.
adamc@257: Qed.
adamc@257: 
adamc@260: (** We can prove that any output of [Phoasify] is well-formed, in a sense strong enough to let us avoid asserting last chapter's axiom. *)
adamc@260: 
adamc@260: Print Wf.
adamc@260: (** %\vspace{-.15in}% [[
adamc@260: Wf = 
adamc@260: fun (t : type) (E : Exp t) =>
adamc@260: forall var1 var2 : type -> Type, exp_equiv nil (E var1) (E var2)
adamc@260:      : forall t : type, Exp t -> Prop
adamc@260:      ]] *)
adamc@260: 
adamc@257: Section vars.
adamc@257:   Variables var1 var2 : type -> Type.
adamc@257: 
adamc@260:   (** In the course of proving well-formedness, we will need to translate back and forth between the de Bruijn and PHOAS representations of free variable information.  The function [zip] combines two de Bruijn substitutions into a single PHOAS context. *)
adamc@260: 
adamc@260:   Fixpoint zip G (s1 : hlist var1 G)
adamc@260:     : hlist var2 G -> list {t : type & var1 t * var2 t}%type :=
adamc@257:     match s1 with
adamc@257:       | HNil => fun _ => nil
adamc@257:       | HCons _ _ v1 s1' => fun s2 => existT _ _ (v1, hhd s2) :: zip s1' (htl s2)
adamc@257:     end.
adamc@257: 
adamc@260:   (** Two simple lemmas about [zip] will make useful hints. *)
adamc@260: 
adamc@257:   Lemma In_zip : forall t G (s1 : hlist _ G) s2 (m : member t G),
adamc@257:     In (existT _ t (hget s1 m, hget s2 m)) (zip s1 s2).
adamc@257:     induction s1; intro s2; dep_destruct s2; intro m; dep_destruct m; crush.
adamc@257:   Qed.
adamc@257: 
adamc@257:   Lemma unsimpl_zip : forall t (v1 : var1 t) (v2 : var2 t)
adamc@257:     G (s1 : hlist _ G) s2 t' (e1 : Phoas.exp _ t') e2,
adamc@257:    exp_equiv (zip (v1 ::: s1) (v2 ::: s2)) e1 e2
adamc@257:    -> exp_equiv (existT _ _ (v1, v2) :: zip s1 s2) e1 e2.
adamc@257:     trivial.
adamc@257:   Qed.
adamc@257: 
adamc@257:   Hint Resolve In_zip unsimpl_zip.
adamc@257: 
adamc@260:   (** Now it is trivial to prove the main inductive lemma about well-formedness. *)
adamc@260: 
adamc@260:   Lemma phoasify_wf : forall G t (e : DeBruijn.exp G t) s1 s2,
adamc@257:     exp_equiv (zip s1 s2) (phoasify e s1) (phoasify e s2).
adamc@257:     Hint Constructors exp_equiv.
adamc@257:     
adamc@257:     induction e; crush.
adamc@257:   Qed.
adamc@257: End vars.
adamc@257: 
adamc@260: (** We apply [phoasify_wf] manually to prove the final theorem. *)
adamc@260: 
adamc@258: Theorem Phoasify_wf : forall t (e : DeBruijn.exp nil t),
adamc@258:   Wf (Phoasify e).
adamc@258:   unfold Wf, Phoasify; intros;
adamc@258:     apply (phoasify_wf e (HNil (B := var1)) (HNil (B := var2))).
adamc@258: Qed.
adamc@258: 
adamc@260: (** Now, if we compose [Phoasify] with any translation over PHOAS terms, we can verify the composed translation without relying on axioms.  The conclusion of [Phoasify_wf] is robustly useful in verifying a wide variety of translations that use a wide variety of [var] instantiations. *)
adamc@260: 
adamc@257: 
adamc@257: (** * From PHOAS to De Bruijn *)
adamc@258: 
adamc@260: (** The translation to de Bruijn terms is more involved.  We will essentially be instantiating and using a PHOAS term following a convention isomorphic to %\textit{%#<i>#de Bruijn levels#</i>#%}%, which are different from the de Bruijn indices that we have treated so far.  With levels, a given bound variable is referred to by the same number at each of its occurrences.  In any expression, the binders that are not enclosed by other binders are assigned level 0, a binder with just one enclosing binder is assigned level 1, and so on.  The uniformity of references to any binder will be critical to our translation, since it is compatible with the pattern of filling in all of a PHOAS variable's locations at once by applying a function.
adamc@260: 
adamc@260:    We implement a special lookup function, for reading a numbered variable's type out of a de Bruijn level typing context.  The last variable in the list is taken to have level 0, the next-to-last level 1, and so on. *)
adamc@260: 
adamc@260: Fixpoint lookup (ts : list type) (n : nat) : option type :=
adamc@260:   match ts with
adamc@258:     | nil => None
adamc@260:     | t :: ts' => if eq_nat_dec n (length ts') then Some t else lookup ts' n
adamc@258:   end.
adamc@258: 
adamc@258: Infix "##" := lookup (left associativity, at level 1).
adamc@258: 
adamc@260: (** With [lookup], we can define a notion of well-formedness for PHOAS expressions that we are treating according to the de Bruijn level convention. *)
adamc@260: 
adamc@258: Fixpoint wf (ts : list type) t (e : Phoas.exp (fun _ => nat) t) : Prop :=
adamc@258:   match e with
adamc@258:     | Phoas.Var t n => ts ## n = Some t
adamc@258:     | Phoas.Const _ => True
adamc@258:     | Phoas.Plus e1 e2 => wf ts e1 /\ wf ts e2
adamc@258:     | Phoas.App _ _ e1 e2 => wf ts e1 /\ wf ts e2
adamc@258:     | Phoas.Abs t1 _ e1 => wf (t1 :: ts) (e1 (length ts))
adamc@258:   end.
adamc@258: 
adamc@260: (** ** Connecting Notions of Well-Formedness *)
adamc@260: 
adamc@260: (** Our first order of business now is to prove that any well-formed [Exp] instantiates to a well-formed de Bruijn level expression.  We start by characterizing, as a function of de Bruijn level contexts, the set of PHOAS contexts that will occur in the proof, where we will be inducting over an [exp_equiv] derivation. *)
adamc@260: 
adamc@258: Fixpoint makeG (ts : list type) : list { t : type & nat * nat }%type :=
adamc@258:   match ts with
adamc@258:     | nil => nil
adamc@258:     | t :: ts' => existT _ t (length ts', length ts') :: makeG ts'
adamc@258:   end.
adamc@258: 
adamc@260: (** Now we prove a connection between [lookup] and [makeG], by way of a lemma about [lookup]. *)
adamc@260: 
adamc@258: Opaque eq_nat_dec.
adamc@258: Hint Extern 1 (_ >= _) => omega.
adamc@258: 
adamc@258: Lemma lookup_contra' : forall t ts n,
adamc@258:   ts ## n = Some t
adamc@258:   -> n >= length ts
adamc@258:   -> False.
adamc@258:   induction ts; crush;
adamc@258:     match goal with
adamc@258:       | [ _ : context[if ?E then _ else _] |- _ ] => destruct E; crush
adamc@258:     end; eauto.
adamc@258: Qed.
adamc@258: 
adamc@258: Lemma lookup_contra : forall t ts,
adamc@258:   ts ## (length ts) = Some t
adamc@258:   -> False.
adamc@258:   intros; eapply lookup_contra'; eauto.
adamc@258: Qed.
adamc@258: 
adamc@258: Hint Resolve lookup_contra.
adamc@258: 
adamc@258: Lemma lookup_In : forall t v1 v2 ts,
adamc@258:   In (existT (fun _ : type => (nat * nat)%type) t (v1, v2)) (makeG ts)
adamc@258:   -> ts ## v1 = Some t.
adamc@258:   induction ts; crush;
adamc@258:     match goal with
adamc@258:       | [ |- context[if ?E then _ else _] ] => destruct E; crush
adamc@258:     end; elimtype False; eauto.
adamc@258: Qed.
adamc@258: 
adamc@258: Hint Resolve lookup_In.
adamc@258: 
adamc@260: (** We can prove the main inductive lemma by induction over [exp_equiv] derivations. *)
adamc@260: 
adamc@258: Hint Extern 1 (_ :: _ = makeG (_ :: _)) => reflexivity.
adamc@258: 
adamc@258: Lemma Wf_wf' : forall G t e1 (e2 : Phoas.exp (fun _ => nat) t),
adamc@258:   exp_equiv G e1 e2
adamc@258:   -> forall ts, G = makeG ts
adamc@258:     -> wf ts e1.
adamc@258:   induction 1; crush; eauto.
adamc@258: Qed.
adamc@258: 
adamc@258: Lemma Wf_wf : forall t (E : Exp t),
adamc@258:   Wf E
adamc@258:   -> wf nil (E (fun _ => nat)).
adamc@258:   intros; eapply Wf_wf'; eauto.
adamc@258: Qed.
adamc@259: 
adamc@260: (** ** The Translation *)
adamc@260: 
adamc@260: (** Implementing the translation itself will require some proofs.  Our main function [dbify] will take [wf] proofs as arguments, and these proofs will be critical to constructing de Bruijn index terms.  First, we use [congruence] to prove two basic theorems about [option]s. *)
adamc@260: 
adamc@259: Theorem None_Some : forall T (x : T),
adamc@259:   None = Some x
adamc@259:   -> False.
adamc@259:   congruence.
adamc@259: Qed.
adamc@259: 
adamc@259: Theorem Some_Some : forall T (x y : T),
adamc@259:   Some x = Some y
adamc@259:   -> x = y.
adamc@259:   congruence.
adamc@259: Qed.
adamc@259: 
adamc@260: (** We can use these theorems to implement [makeVar], which translates a proof about [lookup] into a de Bruijn index variable with a closely related type. *)
adamc@260: 
adamc@259: Fixpoint makeVar {ts n t} : ts ## n = Some t -> member t ts :=
adamc@260:   match ts with
adamc@259:     | nil => fun Heq => match None_Some Heq with end
adamc@260:     | t' :: ts' => if eq_nat_dec n (length ts') as b return (if b then _ else _) = _ -> _
adamc@260:       then fun Heq => match Some_Some Heq with refl_equal => HFirst end
adamc@259:       else fun Heq => HNext (makeVar Heq)
adamc@259:   end.
adamc@259: 
adamc@260: (** Now [dbify] is straightforward to define.  We use the functions [proj1] and [proj2] to decompose proofs of conjunctions. *)
adamc@259: 
adamc@259: Fixpoint dbify {ts} t (e : Phoas.exp (fun _ => nat) t) : wf ts e -> DeBruijn.exp ts t :=
adamc@259:   match e in Phoas.exp _ t return wf ts e -> DeBruijn.exp ts t with
adamc@259:     | Phoas.Var _ n => fun wf => DeBruijn.Var (makeVar wf)
adamc@259: 
adamc@259:     | Phoas.Const n => fun _ => DeBruijn.Const n
adamc@260:     | Phoas.Plus e1 e2 => fun wf =>
adamc@260:       DeBruijn.Plus (dbify e1 (proj1 wf)) (dbify e2 (proj2 wf))
adamc@259: 
adamc@260:     | Phoas.App _ _ e1 e2 => fun wf =>
adamc@260:       DeBruijn.App (dbify e1 (proj1 wf)) (dbify e2 (proj2 wf))
adamc@259:     | Phoas.Abs _ _ e1 => fun wf => DeBruijn.Abs (dbify (e1 (length ts)) wf)
adamc@259:   end.
adamc@259: 
adamc@260: (** We define the parametric translation [Dbify] by appealing to the well-formedness translation theorem [Wf_wf] that we proved earlier. *)
adamc@260: 
adamc@259: Definition Dbify t (E : Phoas.Exp t) (W : Wf E) : DeBruijn.exp nil t :=
adamc@259:   dbify (E _) (Wf_wf W).
adamc@259: 
adamc@260: (** To prove soundness, it is helpful to classify a set of contexts which depends on a de Bruijn index substitution. *)
adamc@260: 
adamc@260: Fixpoint makeG' ts (s : hlist typeDenote ts)
adamc@260:   : list { t : type & nat * typeDenote t }%type :=
adamc@259:   match s with
adamc@259:     | HNil => nil
adamc@259:     | HCons _ ts' v s' => existT _ _ (length ts', v) :: makeG' s'
adamc@259:   end.
adamc@259: 
adamc@260: (** We prove an analogous lemma to the one we proved connecting [makeG] and [lookup].  This time, we connect [makeG'] and [hget]. *)
adamc@260: 
adamc@259: Lemma In_makeG'_contra' : forall t v2 ts (s : hlist _ ts) n,
adamc@259:   In (existT _ t (n, v2)) (makeG' s)
adamc@259:   -> n >= length ts
adamc@259:   -> False.
adamc@259:   induction s; crush; eauto.
adamc@259: Qed.
adamc@259: 
adamc@259: Lemma In_makeG'_contra : forall t v2 ts (s : hlist _ ts),
adamc@259:   In (existT _ t (length ts, v2)) (makeG' s)
adamc@259:   -> False.
adamc@259:   intros; eapply In_makeG'_contra'; eauto.
adamc@259: Qed.
adamc@259: 
adamc@259: Hint Resolve In_makeG'_contra.
adamc@259: 
adamc@259: Lemma In_makeG' : forall t v1 v2 ts s (w : ts ## v1 = Some t),
adamc@259:   In (existT _ t (v1, v2)) (makeG' s)
adamc@259:   -> hget s (makeVar w) = v2.
adamc@259:   induction s; crush;
adamc@259:     match goal with
adamc@259:       | [ |- context[if ?E then _ else _] ] => destruct E; crush
adamc@259:     end;
adamc@259:     repeat match goal with
adamc@260:              | [ |- context[match ?pf with refl_equal => _ end] ] =>
adamc@260:                rewrite (UIP_refl _ _ pf)
adamc@259:            end; crush; elimtype False; eauto.
adamc@259: Qed.
adamc@259: 
adamc@259: Hint Resolve In_makeG'.
adamc@259: 
adamc@260: (** Now the main inductive lemma can be stated and proved simply. *)
adamc@260: 
adamc@259: Lemma dbify_sound : forall G t (e1 : Phoas.exp _ t) (e2 : Phoas.exp _ t),
adamc@259:   exp_equiv G e1 e2
adamc@259:   -> forall ts (w : wf ts e1) s,
adamc@259:     G = makeG' s
adamc@259:     -> DeBruijn.expDenote (dbify e1 w) s = Phoas.expDenote e2.
adamc@259:   induction 1; crush; ext_eq; crush.
adamc@259: Qed.
adamc@259: 
adamc@260: (** In the usual way, we wrap [dbify_sound] into the final soundness theorem, formally establishing the expressive equivalence of PHOAS and de Bruijn index terms. *)
adamc@260: 
adamc@259: Theorem Dbify_sound : forall t (E : Exp t) (W : Wf E),
adamc@259:   DeBruijn.expDenote (Dbify W) HNil = Phoas.ExpDenote E.
adamc@259:   unfold Dbify, Phoas.ExpDenote; intros; eapply dbify_sound; eauto.
adamc@259: Qed.