adam@297: (* Copyright (c) 2008-2011, Adam Chlipala
adamc@158:  * 
adamc@158:  * This work is licensed under a
adamc@158:  * Creative Commons Attribution-Noncommercial-No Derivative Works 3.0
adamc@158:  * Unported License.
adamc@158:  * The license text is available at:
adamc@158:  *   http://creativecommons.org/licenses/by-nc-nd/3.0/
adamc@158:  *)
adamc@158: 
adamc@158: (* begin hide *)
adam@297: Require Import Eqdep String List FunctionalExtensionality.
adamc@158: 
adam@297: Require Import Tactics.
adamc@158: 
adamc@158: Set Implicit Arguments.
adamc@158: (* end hide *)
adamc@158: 
adamc@158: 
adamc@158: (** %\chapter{Higher-Order Abstract Syntax}% *)
adamc@158: 
adamc@252: (** In many cases, detailed reasoning about variable binders and substitution is a small annoyance; in other cases, it becomes the dominant cost of proving a theorem formally.  No matter which of these possibilities prevails, it is clear that it would be very pragmatic to find a way to avoid reasoning about variable identity or freshness.  A well-established alternative to first-order encodings is %\textit{%#<i>#higher-order abstract syntax#</i>#%}%, or HOAS.  In mechanized theorem-proving, HOAS is most closely associated with the LF meta logic and the tools based on it, including Twelf.
adamc@158: 
adamc@252: In this chapter, we will see that HOAS cannot be implemented directly in Coq.  However, a few very similar encodings are possible and are in fact very effective in some important domains. *)
adamc@158: 
adamc@252: 
adamc@252: (** * Classic HOAS *)
adamc@252: 
adam@292: (** The motto of HOAS is simple: represent object language binders using meta language binders.  Here, %``%#"#object language#"#%''% refers to the language being formalized, while the meta language is the language in which the formalization is done.  Our usual meta language, Coq's Gallina, contains the standard binding facilities of functional programming, making it a promising base for higher-order encodings.
adamc@252: 
adamc@252:    Recall the concrete encoding of basic untyped lambda calculus expressions. *)
adamc@252: 
adamc@252: Inductive uexp : Set :=
adamc@252: | UVar : string -> uexp
adamc@252: | UApp : uexp -> uexp -> uexp
adamc@252: | UAbs : string -> uexp -> uexp.
adamc@252: 
adamc@252: (** The explicit presence of variable names forces us to think about issues of freshness and variable capture.  The HOAS alternative would look like this. *)
adamc@252: 
adamc@252: Reset uexp.
adamc@252: 
adamc@252: (** [[
adamc@252: Inductive uexp : Set :=
adamc@252: | UApp : uexp -> uexp -> uexp
adamc@252: | UAbs : (uexp -> uexp) -> uexp.
adamc@252:  
adamc@252:   ]]
adamc@252: 
adamc@252:   We have avoided any mention of variables.  Instead, we encode the binding done by abstraction using the binding facilities associated with Gallina functions.  For instance, we might represent the term $\lambda x. \; x \; x$#<tt>\x. x x</tt># as [UAbs (fun x => UApp x x)].  Coq has built-in support for matching binders in anonymous [fun] expressions to their uses, so we avoid needing to implement our own binder-matching logic.
adamc@252: 
adamc@252:   This definition is not quite HOAS, because of the broad variety of functions that Coq would allow us to pass as arguments to [UAbs].  We can thus construct many [uexp]s that do not correspond to normal lambda terms.  These deviants are called %\textit{%#<i>#exotic terms#</i>#%}%.  In LF, functions may only be written in a very restrictive computational language, lacking, among other things, pattern matching and recursive function definitions.  Thus, thanks to a careful balancing act of design decisions, exotic terms are not possible with usual HOAS encodings in LF.
adamc@252: 
adamc@252:   Our definition of [uexp] has a more fundamental problem: it is invalid in Gallina.
adamc@252: 
adamc@252:   [[
adamc@252: Error: Non strictly positive occurrence of "uexp" in
adamc@252:  "(uexp -> uexp) -> uexp".
adamc@252:  
adamc@252:   ]]
adamc@252: 
adamc@252:   We have violated a rule that we considered before: an inductive type may not be defined in terms of functions over itself.  Way back in Chapter 3, we considered this example and the reasons why we should be glad that Coq rejects it.  Thus, we will need to use more cleverness to reap similar benefits.
adamc@252: 
adamc@252:   The root problem is that our expressions contain variables representing expressions of the same kind.  Many useful kinds of syntax involve no such cycles.  For instance, it is easy to use HOAS to encode standard first-order logic in Coq. *)
adamc@252: 
adamc@252: Inductive prop : Type :=
adamc@252: | Eq : forall T, T -> T -> prop
adamc@252: | Not : prop -> prop
adamc@252: | And : prop -> prop -> prop
adamc@252: | Or : prop -> prop -> prop
adamc@252: | Forall : forall T, (T -> prop) -> prop
adamc@252: | Exists : forall T, (T -> prop) -> prop.
adamc@252: 
adamc@252: Fixpoint propDenote (p : prop) : Prop :=
adamc@252:   match p with
adamc@252:     | Eq _ x y => x = y
adamc@252:     | Not p => ~ (propDenote p)
adamc@252:     | And p1 p2 => propDenote p1 /\ propDenote p2
adamc@252:     | Or p1 p2 => propDenote p1 \/ propDenote p2
adamc@252:     | Forall _ f => forall x, propDenote (f x)
adamc@252:     | Exists _ f => exists x, propDenote (f x)
adamc@252:   end.
adamc@252: 
adamc@252: (** Unfortunately, there are other recursive functions that we might like to write but cannot.  One simple example is a function to count the number of constructors used to build a [prop].  To look inside a [Forall] or [Exists], we need to look inside the quantifier's body, which is represented as a function.  In Gallina, as in most statically-typed functional languages, the only way to interact with a function is to call it.  We have no hope of doing that here; the domain of the function in question has an arbitary type [T], so [T] may even be uninhabited.  If we had a universal way of constructing values to look inside functions, we would have uncovered a consistency bug in Coq!
adamc@252: 
adamc@252:    We are still suffering from the possibility of writing exotic terms, such as this example: *)
adamc@252: 
adamc@252: Example true_prop := Eq 1 1.
adamc@252: Example false_prop := Not true_prop.
adamc@252: Example exotic_prop := Forall (fun b : bool => if b then true_prop else false_prop).
adamc@252: 
adamc@252: (** Thus, the idea of a uniform way of looking inside a binder to find another well-defined [prop] is hopelessly doomed.
adamc@252: 
adamc@252:    A clever HOAS variant called %\textit{%#<i>#weak HOAS#</i>#%}% manages to rule out exotic terms in Coq.  Here is a weak HOAS version of untyped lambda terms. *)
adamc@252: 
adamc@252: Parameter var : Set.
adamc@252: 
adamc@252: Inductive uexp : Set :=
adamc@252: | UVar : var -> uexp
adamc@252: | UApp : uexp -> uexp -> uexp
adamc@252: | UAbs : (var -> uexp) -> uexp.
adamc@252: 
adamc@252: (** We postulate the existence of some set [var] of variables, and variable nodes appear explicitly in our syntax.  A binder is represented as a function over %\textit{%#<i>#variables#</i>#%}%, rather than as a function over %\textit{%#<i>#expressions#</i>#%}%.  This breaks the cycle that led Coq to reject the literal HOAS definition.  It is easy to encode our previous example, $\lambda x. \; x \; x$#<tt>\x. x x</tt>#: *)
adamc@252: 
adamc@252: Example self_app := UAbs (fun x => UApp (UVar x) (UVar x)).
adamc@252: 
adamc@252: (** What about exotic terms?  The problems they caused earlier came from the fact that Gallina is expressive enough to allow us to perform case analysis on the types we used as the domains of binder functions.  With weak HOAS, we use an abstract type [var] as the domain.  Since we assume the existence of no functions for deconstructing [var]s, Coq's type soundness enforces that no Gallina term of type [uexp] can take different values depending on the value of a [var] available in the typing context, %\textit{%#<i>#except#</i>#%}% by incorporating those variables into a [uexp] value in a legal way.
adamc@252: 
adamc@252:    Weak HOAS retains the other disadvantage of our previous example: it is hard to write recursive functions that deconstruct terms.  As with the previous example, some functions %\textit{%#<i>#are#</i>#%}% implementable.  For instance, we can write a function to reverse the function and argument positions of every [UApp] node. *)
adamc@252: 
adamc@252: Fixpoint swap (e : uexp) : uexp :=
adamc@252:   match e with
adamc@252:     | UVar _ => e
adamc@252:     | UApp e1 e2 => UApp (swap e2) (swap e1)
adamc@252:     | UAbs e1 => UAbs (fun x => swap (e1 x))
adamc@252:   end.
adamc@252: 
adamc@252: (** However, it is still impossible to write a function to compute the size of an expression.  We would still need to manufacture a value of type [var] to peer under a binder, and that is impossible, because [var] is an abstract type. *)
adamc@252: 
adamc@252: 
adamc@252: (** * Parametric HOAS *)
adamc@158: 
adamc@253: (** In the context of Haskell, Washburn and Weirich introduced a technique called %\emph{%#<i>#parametric HOAS#</i>#%}%, or PHOAS.  By making a slight alteration in the spirit of weak HOAS, we arrive at an encoding that addresses all three of the complaints above: the encoding is legal in Coq, exotic terms are impossible, and it is possible to write any syntax-deconstructing function that we can write with first-order encodings.  The last of these advantages is not even present with HOAS in Twelf.  In a sense, we receive it in exchange for giving up a free implementation of capture-avoiding substitution.
adamc@253: 
adamc@253:    The first step is to change the weak HOAS type so that [var] is a variable inside a section, rather than a global parameter. *)
adamc@253: 
adamc@253: Reset uexp.
adamc@253: 
adamc@253: Section uexp.
adamc@253:   Variable var : Set.
adamc@253: 
adamc@253:   Inductive uexp : Set :=
adamc@253:   | UVar : var -> uexp
adamc@253:   | UApp : uexp -> uexp -> uexp
adamc@253:   | UAbs : (var -> uexp) -> uexp.
adamc@253: End uexp.
adamc@253: 
adamc@253: (** Next, we can encapsulate choices of [var] inside a polymorphic function type. *)
adamc@253: 
adamc@253: Definition Uexp := forall var, uexp var.
adamc@253: 
adamc@253: (** This type [Uexp] is our final, exotic-term-free representation of lambda terms.  Inside the body of a [Uexp] function, [var] values may not be deconstructed illegaly, for much the same reason as with weak HOAS.  We simply trade an abstract type for parametric polymorphism.
adamc@253: 
adamc@253:    Our running example $\lambda x. \; x \; x$#<tt>\x. x x</tt># is easily expressed: *)
adamc@253: 
adamc@253: Example self_app : Uexp := fun var => UAbs (var := var)
adamc@253:   (fun x : var => UApp (var := var) (UVar (var := var) x) (UVar (var := var) x)).
adamc@253: 
adamc@253: (** Including all mentions of [var] explicitly helps clarify what is happening here, but it is convenient to let Coq's local type inference fill in these occurrences for us. *)
adamc@253: 
adamc@253: Example self_app' : Uexp := fun _ => UAbs (fun x => UApp (UVar x) (UVar x)).
adamc@253: 
adamc@253: (** We can go further and apply the PHOAS technique to dependently-typed ASTs, where Gallina typing guarantees that only well-typed terms can be represented.  For the rest of this chapter, we consider the example of simply-typed lambda calculus with natural numbers and addition.  We start with a conventional definition of the type language. *)
adamc@253: 
adamc@158: Inductive type : Type :=
adamc@159: | Nat : type
adamc@158: | Arrow : type -> type -> type.
adamc@158: 
adamc@158: Infix "-->" := Arrow (right associativity, at level 60).
adamc@158: 
adamc@253: (** Our definition of the expression type follows the definition for untyped lambda calculus, with one important change.  Now our section variable [var] is not just a type.  Rather, it is a %\textit{%#<i>#function#</i>#%}% returning types.  The idea is that a variable of object language type [t] is represented by a [var t].  Note how this enables us to avoid indexing the [exp] type with a representation of typing contexts. *)
adamc@253: 
adamc@158: Section exp.
adamc@158:   Variable var : type -> Type.
adamc@158: 
adamc@158:   Inductive exp : type -> Type :=
adamc@159:   | Const' : nat -> exp Nat
adamc@159:   | Plus' : exp Nat -> exp Nat -> exp Nat
adamc@159: 
adamc@158:   | Var : forall t, var t -> exp t
adamc@158:   | App' : forall dom ran, exp (dom --> ran) -> exp dom -> exp ran
adamc@158:   | Abs' : forall dom ran, (var dom -> exp ran) -> exp (dom --> ran).
adamc@158: End exp.
adamc@158: 
adamc@158: Implicit Arguments Const' [var].
adamc@158: Implicit Arguments Var [var t].
adamc@158: Implicit Arguments Abs' [var dom ran].
adamc@158: 
adamc@253: (** Our final representation type wraps [exp] as before. *)
adamc@253: 
adamc@158: Definition Exp t := forall var, exp var t.
adamc@253: 
adamc@169: (* begin thide *)
adamc@253: 
adamc@253: (** We can define some smart constructors to make it easier to build [Exp]s without using polymorphism explicitly. *)
adamc@158: 
adamc@159: Definition Const (n : nat) : Exp Nat :=
adamc@159:   fun _ => Const' n.
adamc@159: Definition Plus (E1 E2 : Exp Nat) : Exp Nat :=
adamc@159:   fun _ => Plus' (E1 _) (E2 _).
adamc@158: Definition App dom ran (F : Exp (dom --> ran)) (X : Exp dom) : Exp ran :=
adamc@158:   fun _ => App' (F _) (X _).
adamc@253: 
adamc@253: (** A case for function abstraction is not as natural, but we can implement one candidate in terms of a type family [Exp1], such that [Exp1 free result] represents an expression of type [result] with one free variable of type [free]. *)
adamc@253: 
adamc@253: Definition Exp1 t1 t2 := forall var, var t1 -> exp var t2.
adamc@158: Definition Abs dom ran (B : Exp1 dom ran) : Exp (dom --> ran) :=
adamc@158:   fun _ => Abs' (B _).
adamc@169: (* end thide *)
adamc@169: 
adamc@169: (* EX: Define appropriate shorthands, so that these definitions type-check. *)
adamc@158: 
adamc@253: (** Now it is easy to encode a number of example programs. *)
adamc@253: 
adamc@253: Example zero := Const 0.
adamc@253: Example one := Const 1.
adamc@253: Example one_again := Plus zero one.
adamc@253: Example ident : Exp (Nat --> Nat) := Abs (fun _ X => Var X).
adamc@253: Example app_ident := App ident one_again.
adamc@253: Example app : Exp ((Nat --> Nat) --> Nat --> Nat) := fun _ =>
adamc@166:   Abs' (fun f => Abs' (fun x => App' (Var f) (Var x))).
adamc@253: Example app_ident' := App (App app ident) one_again.
adamc@166: 
adamc@169: (* EX: Define a function to count the number of variable occurrences in an [Exp]. *)
adamc@169: 
adamc@253: (** We can write syntax-deconstructing functions, such as [CountVars], which counts how many [Var] nodes appear in an [Exp].  First, we write a version [countVars] for [exp]s.  The main trick is to specialize [countVars] to work over expressions where [var] is instantiated as [fun _ => unit].  That is, every variable is just a value of type [unit], such that variables carry no information.  The important thing is that we have a value [tt] of type [unit] available, to use in descending into binders. *)
adamc@253: 
adamc@169: (* begin thide *)
adamc@222: Fixpoint countVars t (e : exp (fun _ => unit) t) : nat :=
adamc@166:   match e with
adamc@166:     | Const' _ => 0
adamc@166:     | Plus' e1 e2 => countVars e1 + countVars e2
adamc@166:     | Var _ _ => 1
adamc@166:     | App' _ _ e1 e2 => countVars e1 + countVars e2
adamc@166:     | Abs' _ _ e' => countVars (e' tt)
adamc@166:   end.
adamc@166: 
adamc@253: (** We turn [countVars] into [CountVars] with explicit instantiation of a polymorphic [Exp] value [E].  We can write an underscore for the paramter to [E], because local type inference is able to infer the proper value. *)
adamc@253: 
adamc@166: Definition CountVars t (E : Exp t) : nat := countVars (E _).
adamc@169: (* end thide *)
adamc@166: 
adamc@253: (** A few evaluations establish that [CountVars] behaves plausibly. *)
adamc@253: 
adamc@166: Eval compute in CountVars zero.
adamc@253: (** %\vspace{-.15in}% [[
adamc@253:      = 0
adamc@253:      : nat
adam@302:      ]]
adam@302:      *)
adamc@253: 
adamc@166: Eval compute in CountVars one.
adamc@253: (** %\vspace{-.15in}% [[
adamc@253:      = 0
adamc@253:      : nat
adam@302:      ]]
adam@302:      *)
adamc@253: 
adamc@166: Eval compute in CountVars one_again.
adamc@253: (** %\vspace{-.15in}% [[
adamc@253:      = 0
adamc@253:      : nat
adam@302:      ]]
adam@302:      *)
adamc@253: 
adamc@166: Eval compute in CountVars ident.
adamc@253: (** %\vspace{-.15in}% [[
adamc@253:      = 1
adamc@253:      : nat
adam@302:      ]]
adam@302:      *)
adamc@253: 
adamc@166: Eval compute in CountVars app_ident.
adamc@253: (** %\vspace{-.15in}% [[
adamc@253:      = 1
adamc@253:      : nat
adam@302:      ]]
adam@302:      *)
adamc@253: 
adamc@166: Eval compute in CountVars app.
adamc@253: (** %\vspace{-.15in}% [[
adamc@253:      = 2
adamc@253:      : nat
adam@302:      ]]
adam@302:      *)
adamc@253: 
adamc@166: Eval compute in CountVars app_ident'.
adamc@253: (** %\vspace{-.15in}% [[
adamc@253:      = 3
adamc@253:      : nat
adam@302:      ]]
adam@302:      *)
adamc@253: 
adamc@166: 
adamc@169: (* EX: Define a function to count the number of occurrences of a single distinguished variable. *)
adamc@169: 
adamc@253: (** We might want to go further and count occurrences of a single distinguished free variable in an expression.  In this case, it is useful to instantiate [var] as [fun _ => bool].  We will represent the distinguished variable with [true] and all other variables with [false]. *)
adamc@253: 
adamc@169: (* begin thide *)
adamc@222: Fixpoint countOne t (e : exp (fun _ => bool) t) : nat :=
adamc@166:   match e with
adamc@166:     | Const' _ => 0
adamc@166:     | Plus' e1 e2 => countOne e1 + countOne e2
adamc@166:     | Var _ true => 1
adamc@166:     | Var _ false => 0
adamc@166:     | App' _ _ e1 e2 => countOne e1 + countOne e2
adamc@166:     | Abs' _ _ e' => countOne (e' false)
adamc@166:   end.
adamc@166: 
adamc@253: (** We wrap [countOne] into [CountOne], which we type using the [Exp1] definition from before.  [CountOne] operates on an expression [E] with a single free variable.  We apply an instantiated [E] to [true] to mark this variable as the one [countOne] should look for.  [countOne] itself is careful to instantiate all other variables with [false]. *)
adamc@253: 
adamc@166: Definition CountOne t1 t2 (E : Exp1 t1 t2) : nat :=
adamc@166:   countOne (E _ true).
adamc@169: (* end thide *)
adamc@166: 
adamc@253: (** We can check the behavior of [CountOne] on a few examples. *)
adamc@253: 
adamc@253: Example ident1 : Exp1 Nat Nat := fun _ X => Var X.
adamc@253: Example add_self : Exp1 Nat Nat := fun _ X => Plus' (Var X) (Var X).
adamc@253: Example app_zero : Exp1 (Nat --> Nat) Nat := fun _ X => App' (Var X) (Const' 0).
adamc@253: Example app_ident1 : Exp1 Nat Nat := fun _ X =>
adamc@253:   App' (Abs' (fun Y => Var Y)) (Var X).
adamc@166: 
adamc@166: Eval compute in CountOne ident1.
adamc@253: (** %\vspace{-.15in}% [[
adamc@253:      = 1
adamc@253:      : nat
adam@302:      ]]
adam@302:      *)
adamc@253: 
adamc@166: Eval compute in CountOne add_self.
adamc@253: (** %\vspace{-.15in}% [[
adamc@253:      = 2
adamc@253:      : nat
adam@302:      ]]
adam@302:      *)
adamc@253: 
adamc@166: Eval compute in CountOne app_zero.
adamc@253: (** %\vspace{-.15in}% [[
adamc@253:      = 1
adamc@253:      : nat
adam@302:      ]]
adam@302:      *)
adamc@253: 
adamc@166: Eval compute in CountOne app_ident1.
adamc@253: (** %\vspace{-.15in}% [[
adamc@253:      = 1
adamc@253:      : nat
adam@302:      ]]
adam@302:      *)
adamc@253: 
adamc@166: 
adamc@169: (* EX: Define a function to pretty-print [Exp]s as strings. *)
adamc@169: 
adamc@253: (** The PHOAS encoding turns out to be just as general as the first-order encodings we saw previously.  To provide a taste of that generality, we implement a translation into concrete syntax, rendered in human-readable strings.  This is as easy as representing variables as strings. *)
adamc@253: 
adamc@169: (* begin thide *)
adamc@166: Section ToString.
adamc@166:   Open Scope string_scope.
adamc@166: 
adamc@166:   Fixpoint natToString (n : nat) : string :=
adamc@166:     match n with
adamc@166:       | O => "O"
adamc@166:       | S n' => "S(" ++ natToString n' ++ ")"
adamc@166:     end.
adamc@166: 
adamc@253:   (** Function [toString] takes an extra argument [cur], which holds the last variable name assigned to a binder.  We build new variable names by extending [cur] with primes.  The function returns a pair of the next available variable name and of the actual expression rendering. *)
adamc@253: 
adamc@222:   Fixpoint toString t (e : exp (fun _ => string) t) (cur : string) : string * string :=
adamc@166:     match e with
adamc@166:       | Const' n => (cur, natToString n)
adamc@166:       | Plus' e1 e2 =>
adamc@166:         let (cur', s1) := toString e1 cur in
adamc@166:         let (cur'', s2) := toString e2 cur' in
adamc@166:         (cur'', "(" ++ s1 ++ ") + (" ++ s2 ++ ")")
adamc@166:       | Var _ s => (cur, s)
adamc@166:       | App' _ _ e1 e2 =>
adamc@166:         let (cur', s1) := toString e1 cur in
adamc@166:         let (cur'', s2) := toString e2 cur' in
adamc@166:         (cur'', "(" ++ s1 ++ ") (" ++ s2 ++ ")")
adamc@166:       | Abs' _ _ e' =>
adamc@166:         let (cur', s) := toString (e' cur) (cur ++ "'") in
adamc@166:         (cur', "(\" ++ cur ++ ", " ++ s ++ ")")
adamc@166:     end.
adamc@166: 
adamc@166:   Definition ToString t (E : Exp t) : string := snd (toString (E _) "x").
adamc@166: End ToString.
adamc@169: (* end thide *)
adamc@166: 
adamc@166: Eval compute in ToString zero.
adamc@253: (** %\vspace{-.15in}% [[
adamc@253:      = "O"%string
adamc@253:      : string
adam@302:    ]]
adam@302:    *)
adamc@253: 
adamc@166: Eval compute in ToString one.
adamc@253: (** %\vspace{-.15in}% [[
adamc@253:      = "S(O)"%string
adamc@253:      : string
adam@302:    ]]
adam@302:    *)
adamc@253: 
adamc@166: Eval compute in ToString one_again.
adamc@253: (** %\vspace{-.15in}% [[
adamc@253:      = "(O) + (S(O))"%string
adamc@253:      : string
adam@302:    ]]
adam@302:    *)
adamc@253: 
adamc@166: Eval compute in ToString ident.
adamc@253: (** %\vspace{-.15in}% [[
adamc@253:      = "(\x, x)"%string
adamc@253:      : string
adam@302:    ]]
adam@302:    *)
adamc@253: 
adamc@166: Eval compute in ToString app_ident.
adamc@253: (** %\vspace{-.15in}% [[
adamc@253:      = "((\x, x)) ((O) + (S(O)))"%string
adamc@253:      : string
adam@302:    ]]
adam@302:    *)
adamc@253: 
adamc@166: Eval compute in ToString app.
adamc@253: (** %\vspace{-.15in}% [[
adamc@253:      = "(\x, (\x', (x) (x')))"%string
adamc@253:      : string
adam@302:    ]]
adam@302:    *)
adamc@253: 
adamc@166: Eval compute in ToString app_ident'.
adamc@253: (** %\vspace{-.15in}% [[
adamc@253:      = "(((\x, (\x', (x) (x')))) ((\x'', x''))) ((O) + (S(O)))"%string
adamc@253:      : string
adam@302:    ]]
adam@302:    *)
adamc@253: 
adamc@166: 
adamc@169: (* EX: Define a substitution function. *)
adamc@169: 
adamc@253: (** Our final example is crucial to using PHOAS to encode standard operational semantics.  We define capture-avoiding substitution, in terms of a function [flatten] which takes in an expression that represents variables as expressions.  [flatten] replaces every node [Var e] with [e]. *)
adamc@253: 
adamc@169: (* begin thide *)
adamc@158: Section flatten.
adamc@158:   Variable var : type -> Type.
adamc@158: 
adamc@222:   Fixpoint flatten t (e : exp (exp var) t) : exp var t :=
adamc@222:     match e with
adamc@159:       | Const' n => Const' n
adamc@159:       | Plus' e1 e2 => Plus' (flatten e1) (flatten e2)
adamc@158:       | Var _ e' => e'
adamc@158:       | App' _ _ e1 e2 => App' (flatten e1) (flatten e2)
adamc@158:       | Abs' _ _ e' => Abs' (fun x => flatten (e' (Var x)))
adamc@158:     end.
adamc@158: End flatten.
adamc@158: 
adamc@253: (** Flattening turns out to implement the heart of substitution.  We apply [E2], which has one free variable, to [E1], replacing the occurrences of the free variable by copies of [E1].  [flatten] takes care of removing the extra [Var] applications around these copies. *)
adamc@253: 
adamc@158: Definition Subst t1 t2 (E1 : Exp t1) (E2 : Exp1 t1 t2) : Exp t2 := fun _ =>
adamc@158:   flatten (E2 _ (E1 _)).
adamc@169: (* end thide *)
adamc@158: 
adamc@166: Eval compute in Subst one ident1.
adamc@253: (** %\vspace{-.15in}% [[
adamc@253:      = fun var : type -> Type => Const' 1
adamc@253:      : Exp Nat
adam@302:    ]]
adam@302:    *)
adamc@253: 
adamc@166: Eval compute in Subst one add_self.
adamc@253: (** %\vspace{-.15in}% [[
adamc@253:      = fun var : type -> Type => Plus' (Const' 1) (Const' 1)
adamc@253:      : Exp Nat
adam@302:    ]]
adam@302:    *)
adamc@253: 
adamc@166: Eval compute in Subst ident app_zero.
adamc@253: (** %\vspace{-.15in}% [[
adamc@253:      = fun var : type -> Type =>
adamc@253:        App' (Abs' (fun X : var Nat => Var X)) (Const' 0)
adamc@253:      : Exp Nat
adam@302:    ]]
adam@302:    *)
adamc@253: 
adamc@166: Eval compute in Subst one app_ident1.
adamc@253: (** %\vspace{-.15in}% [[
adamc@253:      = fun var : type -> Type =>
adamc@253:        App' (Abs' (fun x : var Nat => Var x)) (Const' 1)
adamc@253:      : Exp Nat
adam@302:    ]]
adam@302:    *)
adamc@166: 
adamc@158: 
adamc@158: (** * A Type Soundness Proof *)
adamc@158: 
adamc@254: (** With [Subst] defined, there are few surprises encountered in defining a standard small-step, call-by-value semantics for our object language.  We begin by classifying a subset of expressions as values. *)
adamc@158: 
adamc@158: Inductive Val : forall t, Exp t -> Prop :=
adamc@159: | VConst : forall n, Val (Const n)
adamc@158: | VAbs : forall dom ran (B : Exp1 dom ran), Val (Abs B).
adamc@158: 
adamc@158: Hint Constructors Val.
adamc@158: 
adamc@254: (** Since this language is more complicated than the one we considered in the chapter on first-order encodings, we will use explicit evaluation contexts to define the semantics.  A value of type [Ctx t u] is a context that yields an expression of type [u] when filled by an expression of type [t].  We have one context for each position of the [App] and [Plus] constructors. *)
adamc@254: 
adamc@162: Inductive Ctx : type -> type -> Type :=
adamc@162: | AppCong1 : forall (dom ran : type),
adamc@162:   Exp dom -> Ctx (dom --> ran) ran
adamc@162: | AppCong2 : forall (dom ran : type),
adamc@162:   Exp (dom --> ran) -> Ctx dom ran
adamc@162: | PlusCong1 : Exp Nat -> Ctx Nat Nat
adamc@162: | PlusCong2 : Exp Nat -> Ctx Nat Nat.
adamc@162: 
adamc@254: (** A judgment characterizes when contexts are valid, enforcing the standard call-by-value restriction that certain positions must hold values. *)
adamc@254: 
adamc@162: Inductive isCtx : forall t1 t2, Ctx t1 t2 -> Prop :=
adamc@162: | IsApp1 : forall dom ran (X : Exp dom), isCtx (AppCong1 ran X)
adamc@162: | IsApp2 : forall dom ran (F : Exp (dom --> ran)), Val F -> isCtx (AppCong2 F)
adamc@162: | IsPlus1 : forall E2, isCtx (PlusCong1 E2)
adamc@162: | IsPlus2 : forall E1, Val E1 -> isCtx (PlusCong2 E1).
adamc@162: 
adamc@254: (** A simple definition implements plugging a context with a specific expression. *)
adamc@254: 
adamc@162: Definition plug t1 t2 (C : Ctx t1 t2) : Exp t1 -> Exp t2 :=
adamc@222:   match C with
adamc@162:     | AppCong1 _ _ X => fun F => App F X
adamc@162:     | AppCong2 _ _ F => fun X => App F X
adamc@162:     | PlusCong1 E2 => fun E1 => Plus E1 E2
adamc@162:     | PlusCong2 E1 => fun E2 => Plus E1 E2
adamc@162:   end.
adamc@162: 
adamc@162: Infix "@" := plug (no associativity, at level 60).
adamc@162: 
adamc@254: (** Finally, we have the step relation itself, which combines our ingredients in the standard way.  In the congruence rule, we introduce the extra variable [E1] and its associated equality to make the rule easier for [eauto] to apply. *)
adamc@254: 
adam@292: (** printing ==> $\Rightarrow$ *)
adamc@254: Reserved Notation "E1 ==> E2" (no associativity, at level 90).
adamc@254: 
adamc@158: Inductive Step : forall t, Exp t -> Exp t -> Prop :=
adamc@158: | Beta : forall dom ran (B : Exp1 dom ran) (X : Exp dom),
adamc@160:   Val X
adamc@160:   -> App (Abs B) X ==> Subst X B
adamc@159: | Sum : forall n1 n2,
adamc@159:   Plus (Const n1) (Const n2) ==> Const (n1 + n2)
adamc@162: | Cong : forall t t' (C : Ctx t t') E E' E1,
adamc@162:   isCtx C
adamc@162:   -> E1 = C @ E
adamc@162:   -> E ==> E'
adamc@162:   -> E1 ==> C @ E'
adamc@159: 
adamc@158:   where "E1 ==> E2" := (Step E1 E2).
adamc@158: 
adamc@162: Hint Constructors isCtx Step.
adamc@158: 
adamc@169: (* EX: Prove type soundness. *)
adamc@169: 
adamc@254: (** To prove type soundness for this semantics, we need to overcome one crucial obstacle.  Standard proofs use induction on the structure of typing derivations.  Our encoding mixes typing derivations with expression syntax, so we want to induct over expression structure.  Our expressions are represented as functions, which do not, in general, admit induction in Coq.  However, because of our use of parametric polymorphism, we know that our expressions do, in fact, have inductive structure.  In particular, every closed value of [Exp] type must belong to the following relation. *)
adamc@254: 
adamc@169: (* begin thide *)
adamc@158: Inductive Closed : forall t, Exp t -> Prop :=
adamc@164: | CConst : forall n,
adamc@164:   Closed (Const n)
adamc@159: | CPlus : forall E1 E2,
adamc@159:   Closed E1
adamc@159:   -> Closed E2
adamc@159:   -> Closed (Plus E1 E2)
adamc@158: | CApp : forall dom ran (E1 : Exp (dom --> ran)) E2,
adamc@158:   Closed E1
adamc@158:   -> Closed E2
adamc@158:   -> Closed (App E1 E2)
adamc@158: | CAbs : forall dom ran (E1 : Exp1 dom ran),
adamc@158:   Closed (Abs E1).
adamc@158: 
adamc@254: (** How can we prove such a fact?  It probably cannot be established in Coq without axioms.  Rather, one would have to establish it metatheoretically, reasoning informally outside of Coq.  For now, we assert the fact as an axiom.  The later chapter on intensional transformations shows one approach to removing the need for an axiom. *)
adamc@254: 
adamc@158: Axiom closed : forall t (E : Exp t), Closed E.
adamc@158: 
adamc@254: (** The usual progress and preservation theorems are now very easy to prove.  In fact, preservation is implicit in our dependently-typed definition of [Step].  This is a huge win, because we avoid completely the theorem about substitution and typing that made up the bulk of each proof in the chapter on first-order encodings.  The progress theorem yields to a few lines of automation.
adamc@254: 
adamc@254:    We define a slight variant of [crush] which also looks for chances to use the theorem [inj_pair2] on hypotheses.  This theorem deals with an artifact of the way that [inversion] works on dependently-typed hypotheses. *)
adamc@254: 
adamc@160: Ltac my_crush' :=
adamc@167:   crush;
adamc@158:   repeat (match goal with
adamc@254:             | [ H : _ |- _ ] => generalize (inj_pair2 _ _ _ _ _ H); clear H
adamc@167:           end; crush).
adamc@160: 
adamc@162: Hint Extern 1 (_ = _ @ _) => simpl.
adamc@162: 
adamc@254: (** This is the point where we need to do induction over functions, in the form of expressions [E].  The judgment [Closed] provides the perfect framework; we induct over [Closed] derivations. *)
adamc@254: 
adamc@158: Lemma progress' : forall t (E : Exp t),
adamc@158:   Closed E
adamc@158:   -> Val E \/ exists E', E ==> E'.
adamc@158:   induction 1; crush;
adamc@159:     repeat match goal with
adamc@167:              | [ H : Val _ |- _ ] => inversion H; []; clear H; my_crush'
adamc@162:            end; eauto 6.
adamc@158: Qed.
adamc@158: 
adamc@254: (** Our final proof of progress makes one top-level use of the axiom [closed] that we asserted above. *)
adamc@254: 
adamc@158: Theorem progress : forall t (E : Exp t),
adamc@158:   Val E \/ exists E', E ==> E'.
adamc@158:   intros; apply progress'; apply closed.
adamc@158: Qed.
adamc@169: (* end thide *)
adamc@158: 
adamc@160: 
adamc@160: (** * Big-Step Semantics *)
adamc@160: 
adamc@254: (** Another standard exercise in operational semantics is proving the equivalence of small-step and big-step semantics.  We can carry out this exercise for our PHOAS lambda calculus.  Most of the steps are just as pleasant as in the previous section, but things get complicated near to the end.
adamc@254: 
adamc@254:    We must start by defining the big-step semantics itself.  The definition is completely standard. *)
adamc@254: 
adam@292: (** printing ===> $\Longrightarrow$ *)
adamc@160: Reserved Notation "E1 ===> E2" (no associativity, at level 90).
adamc@160: 
adamc@160: Inductive BigStep : forall t, Exp t -> Exp t -> Prop :=
adamc@160: | SConst : forall n,
adamc@160:   Const n ===> Const n
adamc@160: | SPlus : forall E1 E2 n1 n2,
adamc@160:   E1 ===> Const n1
adamc@160:   -> E2 ===> Const n2
adamc@160:   -> Plus E1 E2 ===> Const (n1 + n2)
adamc@160: 
adamc@160: | SApp : forall dom ran (E1 : Exp (dom --> ran)) E2 B V2 V,
adamc@160:   E1 ===> Abs B
adamc@160:   -> E2 ===> V2
adamc@160:   -> Subst V2 B ===> V
adamc@160:   -> App E1 E2 ===> V
adamc@160: | SAbs : forall dom ran (B : Exp1 dom ran),
adamc@160:   Abs B ===> Abs B
adamc@160: 
adamc@160:   where "E1 ===> E2" := (BigStep E1 E2).
adamc@160: 
adamc@160: Hint Constructors BigStep.
adamc@160: 
adamc@169: (* EX: Prove the equivalence of the small- and big-step semantics. *)
adamc@169: 
adamc@254: (** To prove a crucial intermediate lemma, we will want to name the transitive-reflexive closure of the small-step relation. *)
adamc@254: 
adamc@169: (* begin thide *)
adam@292: (** printing ==>* $\Rightarrow^*$ *)
adamc@160: Reserved Notation "E1 ==>* E2" (no associativity, at level 90).
adamc@160: 
adamc@160: Inductive MultiStep : forall t, Exp t -> Exp t -> Prop :=
adamc@160: | Done : forall t (E : Exp t), E ==>* E
adamc@160: | OneStep : forall t (E E' E'' : Exp t),
adamc@160:   E ==> E'
adamc@160:   -> E' ==>* E''
adamc@160:   -> E ==>* E''
adamc@160: 
adamc@160:   where "E1 ==>* E2" := (MultiStep E1 E2).
adamc@160: 
adamc@160: Hint Constructors MultiStep.
adamc@160: 
adamc@254: (** A few basic properties of evaluation and values admit easy proofs. *)
adamc@254: 
adamc@160: Theorem MultiStep_trans : forall t (E1 E2 E3 : Exp t),
adamc@160:   E1 ==>* E2
adamc@160:   -> E2 ==>* E3
adamc@160:   -> E1 ==>* E3.
adamc@160:   induction 1; eauto.
adamc@160: Qed.
adamc@160: 
adamc@160: Theorem Big_Val : forall t (E V : Exp t),
adamc@160:   E ===> V
adamc@160:   -> Val V.
adamc@160:   induction 1; crush.
adamc@160: Qed.
adamc@160: 
adamc@160: Theorem Val_Big : forall t (V : Exp t),
adamc@160:   Val V
adamc@160:   -> V ===> V.
adamc@160:   destruct 1; crush.
adamc@160: Qed.
adamc@160: 
adamc@160: Hint Resolve Big_Val Val_Big.
adamc@160: 
adamc@254: (** Another useful property deals with pushing multi-step evaluation inside of contexts. *)
adamc@254: 
adamc@162: Lemma Multi_Cong : forall t t' (C : Ctx t t'),
adamc@162:   isCtx C
adamc@162:   -> forall E E', E ==>* E'
adamc@162:     -> C @ E ==>* C @ E'.
adamc@160:   induction 2; crush; eauto.
adamc@160: Qed.
adamc@160: 
adamc@162: Lemma Multi_Cong' : forall t t' (C : Ctx t t') E1 E2 E E',
adamc@162:   isCtx C
adamc@162:   -> E1 = C @ E
adamc@162:   -> E2 = C @ E'
adamc@162:   -> E ==>* E'
adamc@162:   -> E1 ==>* E2.
adamc@162:   crush; apply Multi_Cong; auto.
adamc@162: Qed.
adamc@162: 
adamc@162: Hint Resolve Multi_Cong'.
adamc@162: 
adamc@254: (** Unrestricted use of transitivity of [==>*] can lead to very large [eauto] search spaces, which has very inconvenient efficiency consequences.  Instead, we define a special tactic [mtrans] that tries applying transitivity with a particular intermediate expression. *)
adamc@254: 
adamc@162: Ltac mtrans E :=
adamc@162:   match goal with
adamc@162:     | [ |- E ==>* _ ] => fail 1
adamc@162:     | _ => apply MultiStep_trans with E; [ solve [ eauto ] | eauto ]
adamc@162:   end.
adamc@160: 
adamc@254: (** With [mtrans], we can give a reasonably short proof of one direction of the equivalence between big-step and small-step semantics.  We include proof cases specific to rules of the big-step semantics, since leaving the details to [eauto] would lead to a very slow proof script.  The use of [solve] in [mtrans]'s definition keeps us from going down unfruitful paths. *)
adamc@254: 
adamc@160: Theorem Big_Multi : forall t (E V : Exp t),
adamc@160:   E ===> V
adamc@160:   -> E ==>* V.
adamc@162:   induction 1; crush; eauto;
adamc@162:     repeat match goal with
adamc@162:              | [ n1 : _, E2 : _ |- _ ] => mtrans (Plus (Const n1) E2)
adamc@162:              | [ n1 : _, n2 : _ |- _ ] => mtrans (Plus (Const n1) (Const n2))
adamc@162:              | [ B : _, E2 : _ |- _ ] => mtrans (App (Abs B) E2)
adamc@162:            end.
adamc@160: Qed.
adamc@160: 
adamc@254: (** We are almost ready to prove the other direction of the equivalence.  First, we wrap an earlier lemma in a form that will work better with [eauto]. *)
adamc@254: 
adamc@160: Lemma Big_Val' : forall t (V1 V2 : Exp t),
adamc@160:   Val V2
adamc@160:   -> V1 = V2
adamc@160:   -> V1 ===> V2.
adamc@160:   crush.
adamc@160: Qed.
adamc@160: 
adamc@160: Hint Resolve Big_Val'.
adamc@160: 
adamc@254: (** Now we build some quite involved tactic support for reasoning about equalities over PHOAS terms.  First, we will call [equate_conj F G] to determine the consequences of an equality [F = G].  When [F = f e_1 ... e_n] and [G = f e'_1 ... e'_n], [equate_conj] will return a conjunction [e_1 = e'_1 /\ ... /\ e_n = e'_n].  We hardcode a pattern for each value of [n] from 1 to 5. *)
adamc@254: 
adamc@167: Ltac equate_conj F G :=
adamc@167:   match constr:(F, G) with
adamc@167:     | (_ ?x1, _ ?x2) => constr:(x1 = x2)
adamc@167:     | (_ ?x1 ?y1, _ ?x2 ?y2) => constr:(x1 = x2 /\ y1 = y2)
adamc@167:     | (_ ?x1 ?y1 ?z1, _ ?x2 ?y2 ?z2) => constr:(x1 = x2 /\ y1 = y2 /\ z1 = z2)
adamc@222:     | (_ ?x1 ?y1 ?z1 ?u1, _ ?x2 ?y2 ?z2 ?u2) =>
adamc@222:       constr:(x1 = x2 /\ y1 = y2 /\ z1 = z2 /\ u1 = u2)
adamc@222:     | (_ ?x1 ?y1 ?z1 ?u1 ?v1, _ ?x2 ?y2 ?z2 ?u2 ?v2) =>
adamc@222:       constr:(x1 = x2 /\ y1 = y2 /\ z1 = z2 /\ u1 = u2 /\ v1 = v2)
adamc@167:   end.
adamc@167: 
adamc@254: (** The main tactic is [my_crush], which generalizes our earlier [my_crush'] by performing inversion on hypotheses that equate PHOAS terms.  Coq's built-in [inversion] is only designed to be useful on equalities over inductive types.  PHOAS terms are functions, so [inversion] is not very helpful on them.  To perform the equivalent of [discriminate], we instantiate the terms with [var] as [fun _ => unit] and then appeal to normal [discriminate].  This eliminates some contradictory cases.  To perform the equivalent of [injection], we must consider all possible [var] instantiations.  Some fairly intricate logic strings together these elements.  The details are not worth discussing, since our conclusion will be that one should avoid dealing with proofs of facts like this one. *)
adamc@254: 
adamc@167: Ltac my_crush :=
adamc@167:   my_crush';
adamc@167:   repeat (match goal with
adamc@167:             | [ H : ?F = ?G |- _ ] =>
adamc@167:               (let H' := fresh "H'" in
adamc@167:                 assert (H' : F (fun _ => unit) = G (fun _ => unit)); [ congruence
adamc@167:                   | discriminate || injection H'; clear H' ];
adamc@167:                 my_crush';
adamc@167:                 repeat match goal with
adamc@167:                          | [ H : context[fun _ => unit] |- _ ] => clear H
adamc@167:                        end;
adamc@167:                 match type of H with
adamc@167:                   | ?F = ?G =>
adamc@167:                     let ec := equate_conj F G in
adamc@167:                       let var := fresh "var" in
adam@297:                         assert ec; [ intuition; unfold Exp; extensionality var;
adam@297:                             assert (H' : F var = G var); try congruence;
adam@297:                               match type of H' with
adam@297:                                 | ?X = ?Y =>
adam@297:                                   let X := eval hnf in X in
adam@297:                                     let Y := eval hnf in Y in
adam@297:                                       change (X = Y) in H'
adam@297:                               end; injection H'; my_crush'; tauto
adamc@167:                           | intuition; subst ]
adamc@167:                 end);
adamc@167:               clear H
adamc@167:           end; my_crush');
adamc@167:   my_crush'.
adamc@167: 
adamc@254: (** With that complicated tactic available, the proof of the main lemma is straightforward. *)
adamc@254: 
adamc@160: Lemma Multi_Big' : forall t (E E' : Exp t),
adamc@160:   E ==> E'
adamc@160:   -> forall E'', E' ===> E''
adamc@160:     -> E ===> E''.
adamc@160:   induction 1; crush; eauto;
adamc@160:     match goal with
adamc@160:       | [ H : _ ===> _ |- _ ] => inversion H; my_crush; eauto
adamc@162:     end;
adamc@162:     match goal with
adamc@162:       | [ H : isCtx _ |- _ ] => inversion H; my_crush; eauto
adamc@160:     end.
adamc@160: Qed.
adamc@160: 
adamc@160: Hint Resolve Multi_Big'.
adamc@160: 
adamc@254: (** The other direction of the overall equivalence follows as an easy corollary. *)
adamc@254: 
adamc@160: Theorem Multi_Big : forall t (E V : Exp t),
adamc@160:   E ==>* V
adamc@160:   -> Val V
adamc@160:   -> E ===> V.
adamc@160:   induction 1; crush; eauto.
adamc@160: Qed.
adamc@169: (* end thide *)
adamc@254: 
adamc@254: (** The lesson here is that working directly with PHOAS terms can easily lead to extremely intricate proofs.  It is usually a better idea to stick to inductive proofs about %\textit{%#<i>#instantiated#</i>#%}% PHOAS terms; in the case of this example, that means proofs about [exp] instead of [Exp].  Such results can usually be wrapped into results about [Exp] without further induction.  Different theorems demand different variants of this underlying advice, and we will consider several of them in the chapters to come. *)