adamc@105: (* Copyright (c) 2008, Adam Chlipala
adamc@105:  * 
adamc@105:  * This work is licensed under a
adamc@105:  * Creative Commons Attribution-Noncommercial-No Derivative Works 3.0
adamc@105:  * Unported License.
adamc@105:  * The license text is available at:
adamc@105:  *   http://creativecommons.org/licenses/by-nc-nd/3.0/
adamc@105:  *)
adamc@105: 
adamc@105: (* begin hide *)
adamc@111: Require Import Arith List.
adamc@105: 
adamc@105: Require Import Tactics.
adamc@105: 
adamc@105: Set Implicit Arguments.
adamc@105: (* end hide *)
adamc@105: 
adamc@105: 
adamc@105: (** %\chapter{Dependent Data Structures}% *)
adamc@105: 
adamc@106: (** Our red-black tree example from the last chapter illustrated how dependent types enable static enforcement of data structure invariants.  To find interesting uses of dependent data structures, however, we need not look to the favorite examples of data structures and algorithms textbooks.  More basic examples like length-indexed and heterogeneous lists come up again and again as the building blocks of dependent programs.  There is a surprisingly large design space for this class of data structure, and we will spend this chapter exploring it. *)
adamc@105: 
adamc@105: 
adamc@106: (** * More Length-Indexed Lists *)
adamc@106: 
adamc@106: (** We begin with a deeper look at the length-indexed lists that began the last chapter. *)
adamc@105: 
adamc@105: Section ilist.
adamc@105:   Variable A : Set.
adamc@105: 
adamc@105:   Inductive ilist : nat -> Set :=
adamc@105:   | Nil : ilist O
adamc@105:   | Cons : forall n, A -> ilist n -> ilist (S n).
adamc@105: 
adamc@106:   (** We might like to have a certified function for selecting an element of an [ilist] by position.  We could do this using subset types and explicit manipulation of proofs, but dependent types let us do it more directly.  It is helpful to define a type family [index], where [index n] is isomorphic to [{m : nat | m < n}].  Such a type family is also often called [Fin] or similar, standing for "finite." *)
adamc@106: 
adamc@113:   (* EX: Define a function [get] for extracting an [ilist] element by position. *)
adamc@113: 
adamc@113: (* begin thide *)
adamc@105:   Inductive index : nat -> Set :=
adamc@105:   | First : forall n, index (S n)
adamc@105:   | Next : forall n, index n -> index (S n).
adamc@105: 
adamc@106:   (** [index] essentially makes a more richly-typed copy of the natural numbers.  Every element is a [First] iterated through applying [Next] a number of times that indicates which number is being selected.
adamc@106: 
adamc@106:      Now it is easy to pick a [Prop]-free type for a selection function.  As usual, our first implementation attempt will not convince the type checker, and we will attack the deficiencies one at a time.
adamc@106: 
adamc@106:      [[
adamc@106:   Fixpoint get n (ls : ilist n) {struct ls} : index n -> A :=
adamc@106:     match ls in ilist n return index n -> A with
adamc@106:       | Nil => fun idx => ?
adamc@106:       | Cons _ x ls' => fun idx =>
adamc@106:         match idx with
adamc@106:           | First _ => x
adamc@106:           | Next _ idx' => get ls' idx'
adamc@106:         end
adamc@106:     end.
adamc@106: 
adamc@106:     We apply the usual wisdom of delaying arguments in [Fixpoint]s so that they may be included in [return] clauses.  This still leaves us with a quandary in each of the [match] cases.  First, we need to figure out how to take advantage of the contradiction in the [Nil] case.  Every [index] has a type of the form [S n], which cannot unify with the [O] value that we learn for [n] in the [Nil] case.  The solution we adopt is another case of [match]-within-[return].
adamc@106: 
adamc@106:     [[
adamc@106:   Fixpoint get n (ls : ilist n) {struct ls} : index n -> A :=
adamc@106:     match ls in ilist n return index n -> A with
adamc@106:       | Nil => fun idx =>
adamc@106:         match idx in index n' return (match n' with
adamc@106:                                         | O => A
adamc@106:                                         | S _ => unit
adamc@106:                                       end) with
adamc@106:           | First _ => tt
adamc@106:           | Next _ _ => tt
adamc@106:         end
adamc@106:       | Cons _ x ls' => fun idx =>
adamc@106:         match idx with
adamc@106:           | First _ => x
adamc@106:           | Next _ idx' => get ls' idx'
adamc@106:         end
adamc@106:     end.
adamc@106: 
adamc@106:     Now the first [match] case type-checks, and we see that the problem with the [Cons] case is that the pattern-bound variable [idx'] does not have an apparent type compatible with [ls'].  We need to use [match] annotations to make the relationship explicit.  Unfortunately, the usual trick of postponing argument binding will not help us here.  We need to match on both [ls] and [idx]; one or the other must be matched first.  To get around this, we apply a trick that we will call "the convoy pattern," introducing a new function and applying it immediately, to satisfy the type checker.
adamc@106: 
adamc@106:     [[
adamc@106:   Fixpoint get n (ls : ilist n) {struct ls} : index n -> A :=
adamc@106:     match ls in ilist n return index n -> A with
adamc@106:       | Nil => fun idx =>
adamc@106:         match idx in index n' return (match n' with
adamc@106:                                         | O => A
adamc@106:                                         | S _ => unit
adamc@106:                                       end) with
adamc@106:           | First _ => tt
adamc@106:           | Next _ _ => tt
adamc@106:         end
adamc@106:       | Cons _ x ls' => fun idx =>
adamc@106:         match idx in index n' return ilist (pred n') -> A with
adamc@106:           | First _ => fun _ => x
adamc@106:           | Next _ idx' => fun ls' => get ls' idx'
adamc@106:         end ls'
adamc@106:     end.
adamc@106: 
adamc@106:     There is just one problem left with this implementation.  Though we know that the local [ls'] in the [Next] case is equal to the original [ls'], the type-checker is not satisfied that the recursive call to [get] does not introduce non-termination.  We solve the problem by convoy-binding the partial application of [get] to [ls'], rather than [ls'] by itself. *)
adamc@106: 
adamc@105:   Fixpoint get n (ls : ilist n) {struct ls} : index n -> A :=
adamc@105:     match ls in ilist n return index n -> A with
adamc@105:       | Nil => fun idx =>
adamc@105:         match idx in index n' return (match n' with
adamc@105:                                         | O => A
adamc@105:                                         | S _ => unit
adamc@105:                                       end) with
adamc@105:           | First _ => tt
adamc@105:           | Next _ _ => tt
adamc@105:         end
adamc@105:       | Cons _ x ls' => fun idx =>
adamc@105:         match idx in index n' return (index (pred n') -> A) -> A with
adamc@105:           | First _ => fun _ => x
adamc@105:           | Next _ idx' => fun get_ls' => get_ls' idx'
adamc@105:         end (get ls')
adamc@105:     end.
adamc@113: (* end thide *)
adamc@105: End ilist.
adamc@105: 
adamc@105: Implicit Arguments Nil [A].
adamc@113: (* begin thide *)
adamc@108: Implicit Arguments First [n].
adamc@113: (* end thide *)
adamc@105: 
adamc@108: (** A few examples show how to make use of these definitions. *)
adamc@108: 
adamc@108: Check Cons 0 (Cons 1 (Cons 2 Nil)).
adamc@108: (** [[
adamc@108: 
adamc@108: Cons 0 (Cons 1 (Cons 2 Nil))
adamc@108:      : ilist nat 3
adamc@108: ]] *)
adamc@113: (* begin thide *)
adamc@108: Eval simpl in get (Cons 0 (Cons 1 (Cons 2 Nil))) First.
adamc@108: (** [[
adamc@108: 
adamc@108:      = 0
adamc@108:      : nat
adamc@108: ]] *)
adamc@108: Eval simpl in get (Cons 0 (Cons 1 (Cons 2 Nil))) (Next First).
adamc@108: (** [[
adamc@108: 
adamc@108:      = 1
adamc@108:      : nat
adamc@108: ]] *)
adamc@108: Eval simpl in get (Cons 0 (Cons 1 (Cons 2 Nil))) (Next (Next First)).
adamc@108: (** [[
adamc@108: 
adamc@108:      = 2
adamc@108:      : nat
adamc@108: ]] *)
adamc@113: (* end thide *)
adamc@108: 
adamc@108: (** Our [get] function is also quite easy to reason about.  We show how with a short example about an analogue to the list [map] function. *)
adamc@107: 
adamc@105: Section ilist_map.
adamc@105:   Variables A B : Set.
adamc@105:   Variable f : A -> B.
adamc@105: 
adamc@105:   Fixpoint imap n (ls : ilist A n) {struct ls} : ilist B n :=
adamc@105:     match ls in ilist _ n return ilist B n with
adamc@105:       | Nil => Nil
adamc@105:       | Cons _ x ls' => Cons (f x) (imap ls')
adamc@105:     end.
adamc@105: 
adamc@107:   (** It is easy to prove that [get] "distributes over" [imap] calls.  The only tricky bit is remembering to use the [dep_destruct] tactic in place of plain [destruct] when faced with a baffling tactic error message. *)
adamc@107: 
adamc@107:   Theorem get_imap : forall n (idx : index n) (ls : ilist A n),
adamc@105:     get (imap ls) idx = f (get ls idx).
adamc@113: (* begin thide *)
adamc@107:     induction ls; dep_destruct idx; crush.
adamc@105:   Qed.
adamc@113: (* end thide *)
adamc@105: End ilist_map.
adamc@107: 
adamc@107: 
adamc@107: (** * Heterogeneous Lists *)
adamc@107: 
adamc@107: (** Programmers who move to statically-typed functional languages from "scripting languages" often complain about the requirement that every element of a list have the same type.  With fancy type systems, we can partially lift this requirement.  We can index a list type with a "type-level" list that explains what type each element of the list should have.  This has been done in a variety of ways in Haskell using type classes, and it we can do it much more cleanly and directly in Coq. *)
adamc@107: 
adamc@107: Section hlist.
adamc@107:   Variable A : Type.
adamc@107:   Variable B : A -> Type.
adamc@107: 
adamc@113:   (* EX: Define a type [hlist] indexed by a [list A], where the type of each element is determined by running [B] on the corresponding element of the index list. *)
adamc@113: 
adamc@107:   (** We parameterize our heterogeneous lists by a type [A] and an [A]-indexed type [B]. *)
adamc@107: 
adamc@113: (* begin thide *)
adamc@107:   Inductive hlist : list A -> Type :=
adamc@107:   | MNil : hlist nil
adamc@107:   | MCons : forall (x : A) (ls : list A), B x -> hlist ls -> hlist (x :: ls).
adamc@107: 
adamc@107:   (** We can implement a variant of the last section's [get] function for [hlist]s.  To get the dependent typing to work out, we will need to index our element selectors by the types of data that they point to. *)
adamc@107: 
adamc@113: (* end thide *)
adamc@113:   (* EX: Define an analogue to [get] for [hlist]s. *)
adamc@113: 
adamc@113: (* begin thide *)
adamc@107:   Variable elm : A.
adamc@107: 
adamc@107:   Inductive member : list A -> Type :=
adamc@107:   | MFirst : forall ls, member (elm :: ls)
adamc@107:   | MNext : forall x ls, member ls -> member (x :: ls).
adamc@107: 
adamc@107:   (** Because the element [elm] that we are "searching for" in a list does not change across the constructors of [member], we simplify our definitions by making [elm] a local variable.  In the definition of [member], we say that [elm] is found in any list that begins with [elm], and, if removing the first element of a list leaves [elm] present, then [elm] is present in the original list, too.  The form looks much like a predicate for list membership, but we purposely define [member] in [Type] so that we may decompose its values to guide computations.
adamc@107: 
adamc@107:      We can use [member] to adapt our definition of [get] to [hlists].  The same basic [match] tricks apply.  In the [MCons] case, we form a two-element convoy, passing both the data element [x] and the recursor for the sublist [mls'] to the result of the inner [match].  We did not need to do that in [get]'s definition because the types of list elements were not dependent there. *)
adamc@107: 
adamc@107:   Fixpoint hget ls (mls : hlist ls) {struct mls} : member ls -> B elm :=
adamc@107:     match mls in hlist ls return member ls -> B elm with
adamc@107:       | MNil => fun mem =>
adamc@107:         match mem in member ls' return (match ls' with
adamc@107:                                           | nil => B elm
adamc@107:                                           | _ :: _ => unit
adamc@107:                                         end) with
adamc@107:           | MFirst _ => tt
adamc@107:           | MNext _ _ _ => tt
adamc@107:         end
adamc@107:       | MCons _ _ x mls' => fun mem =>
adamc@107:         match mem in member ls' return (match ls' with
adamc@107:                                           | nil => Empty_set
adamc@107:                                           | x' :: ls'' =>
adamc@107:                                             B x' -> (member ls'' -> B elm) -> B elm
adamc@107:                                         end) with
adamc@107:           | MFirst _ => fun x _ => x
adamc@107:           | MNext _ _ mem' => fun _ get_mls' => get_mls' mem'
adamc@107:         end x (hget mls')
adamc@107:     end.
adamc@113: (* end thide *)
adamc@107: End hlist.
adamc@108: 
adamc@113: (* begin thide *)
adamc@108: Implicit Arguments MNil [A B].
adamc@108: Implicit Arguments MCons [A B x ls].
adamc@108: 
adamc@108: Implicit Arguments MFirst [A elm ls].
adamc@108: Implicit Arguments MNext [A elm x ls].
adamc@113: (* end thide *)
adamc@108: 
adamc@108: (** By putting the parameters [A] and [B] in [Type], we allow some very higher-order uses.  For instance, one use of [hlist] is for the simple heterogeneous lists that we referred to earlier. *)
adamc@108: 
adamc@108: Definition someTypes : list Set := nat :: bool :: nil.
adamc@108: 
adamc@113: (* begin thide *)
adamc@113: 
adamc@108: Example someValues : hlist (fun T : Set => T) someTypes :=
adamc@108:   MCons 5 (MCons true MNil).
adamc@108: 
adamc@108: Eval simpl in hget someValues MFirst.
adamc@108: (** [[
adamc@108: 
adamc@108:      = 5
adamc@108:      : (fun T : Set => T) nat
adamc@108: ]] *)
adamc@108: Eval simpl in hget someValues (MNext MFirst).
adamc@108: (** [[
adamc@108: 
adamc@108:      = true
adamc@108:      : (fun T : Set => T) bool
adamc@108: ]] *)
adamc@108: 
adamc@108: (** We can also build indexed lists of pairs in this way. *)
adamc@108: 
adamc@108: Example somePairs : hlist (fun T : Set => T * T)%type someTypes :=
adamc@108:   MCons (1, 2) (MCons (true, false) MNil).
adamc@108: 
adamc@113: (* end thide *)
adamc@113: 
adamc@113: 
adamc@108: (** ** A Lambda Calculus Interpreter *)
adamc@108: 
adamc@108: (** Heterogeneous lists are very useful in implementing interpreters for functional programming languages.  Using the types and operations we have already defined, it is trivial to write an interpreter for simply-typed lambda calculus.  Our interpreter can alternatively be thought of as a denotational semantics.
adamc@108: 
adamc@108:    We start with an algebraic datatype for types. *)
adamc@108: 
adamc@108: Inductive type : Set :=
adamc@108: | Unit : type
adamc@108: | Arrow : type -> type -> type.
adamc@108: 
adamc@108: (** Now we can define a type family for expressions.  An [exp ts t] will stand for an expression that has type [t] and whose free variables have types in the list [ts].  We effectively use the de Bruijn variable representation, which we will discuss in more detail in later chapters.  Variables are represented as [member] values; that is, a variable is more or less a constructive proof that a particular type is found in the type environment. *)
adamc@108: 
adamc@108: Inductive exp : list type -> type -> Set :=
adamc@108: | Const : forall ts, exp ts Unit
adamc@108: 
adamc@113: (* begin thide *)
adamc@108: | Var : forall ts t, member t ts -> exp ts t
adamc@108: | App : forall ts dom ran, exp ts (Arrow dom ran) -> exp ts dom -> exp ts ran
adamc@108: | Abs : forall ts dom ran, exp (dom :: ts) ran -> exp ts (Arrow dom ran).
adamc@113: (* end thide *)
adamc@108: 
adamc@108: Implicit Arguments Const [ts].
adamc@108: 
adamc@108: (** We write a simple recursive function to translate [type]s into [Set]s. *)
adamc@108: 
adamc@108: Fixpoint typeDenote (t : type) : Set :=
adamc@108:   match t with
adamc@108:     | Unit => unit
adamc@108:     | Arrow t1 t2 => typeDenote t1 -> typeDenote t2
adamc@108:   end.
adamc@108: 
adamc@108: (** Now it is straightforward to write an expression interpreter.  The type of the function, [expDenote], tells us that we translate expressions into functions from properly-typed environments to final values.  An environment for a free variable list [ts] is simply a [hlist typeDenote ts].  That is, for each free variable, the heterogeneous list that is the environment must have a value of the variable's associated type.  We use [hget] to implement the [Var] case, and we use [MCons] to extend the environment in the [Abs] case. *)
adamc@108: 
adamc@113: (* EX: Define an interpreter for [exp]s. *)
adamc@113: 
adamc@113: (* begin thide *)
adamc@108: Fixpoint expDenote ts t (e : exp ts t) {struct e} : hlist typeDenote ts -> typeDenote t :=
adamc@108:   match e in exp ts t return hlist typeDenote ts -> typeDenote t with
adamc@108:     | Const _ => fun _ => tt
adamc@108: 
adamc@108:     | Var _ _ mem => fun s => hget s mem
adamc@108:     | App _ _ _ e1 e2 => fun s => (expDenote e1 s) (expDenote e2 s)
adamc@108:     | Abs _ _ _ e' => fun s => fun x => expDenote e' (MCons x s)
adamc@108:   end.
adamc@108: 
adamc@108: (** Like for previous examples, our interpreter is easy to run with [simpl]. *)
adamc@108: 
adamc@108: Eval simpl in expDenote Const MNil.
adamc@108: (** [[
adamc@108: 
adamc@108:     = tt
adamc@108:      : typeDenote Unit
adamc@108: ]] *)
adamc@108: Eval simpl in expDenote (Abs (dom := Unit) (Var MFirst)) MNil.
adamc@108: (** [[
adamc@108: 
adamc@108:      = fun x : unit => x
adamc@108:      : typeDenote (Arrow Unit Unit)
adamc@108: ]] *)
adamc@108: Eval simpl in expDenote (Abs (dom := Unit)
adamc@108:   (Abs (dom := Unit) (Var (MNext MFirst)))) MNil.
adamc@108: (** [[
adamc@108: 
adamc@108:      = fun x _ : unit => x
adamc@108:      : typeDenote (Arrow Unit (Arrow Unit Unit))
adamc@108: ]] *)
adamc@108: Eval simpl in expDenote (Abs (dom := Unit) (Abs (dom := Unit) (Var MFirst))) MNil.
adamc@108: (** [[
adamc@108: 
adamc@108:      = fun _ x0 : unit => x0
adamc@108:      : typeDenote (Arrow Unit (Arrow Unit Unit))
adamc@108: ]] *)
adamc@108: Eval simpl in expDenote (App (Abs (Var MFirst)) Const) MNil.
adamc@108: (** [[
adamc@108: 
adamc@108:      = tt
adamc@108:      : typeDenote Unit
adamc@108: ]] *)
adamc@108: 
adamc@113: (* end thide *)
adamc@113: 
adamc@108: (** We are starting to develop the tools behind dependent typing's amazing advantage over alternative approaches in several important areas.  Here, we have implemented complete syntax, typing rules, and evaluation semantics for simply-typed lambda calculus without even needing to define a syntactic substitution operation.  We did it all without a single line of proof, and our implementation is manifestly executable.  In a later chapter, we will meet other, more common approaches to language formalization.  Such approaches often state and prove explicit theorems about type safety of languages.  In the above example, we got type safety, termination, and other meta-theorems for free, by reduction to CIC, which we know has those properties. *)
adamc@108: 
adamc@108: 
adamc@109: (** * Recursive Type Definitions *)
adamc@109: 
adamc@109: (** There is another style of datatype definition that leads to much simpler definitions of the [get] and [hget] definitions above.  Because Coq supports "type-level computation," we can redo our inductive definitions as %\textit{%#<i>#recursive#</i>#%}% definitions. *)
adamc@109: 
adamc@113: (* EX: Come up with an alternate [ilist] definition that makes it easier to write [get]. *)
adamc@113: 
adamc@109: Section filist.
adamc@109:   Variable A : Set.
adamc@109: 
adamc@113: (* begin thide *)
adamc@109:   Fixpoint filist (n : nat) : Set :=
adamc@109:     match n with
adamc@109:       | O => unit
adamc@109:       | S n' => A * filist n'
adamc@109:     end%type.
adamc@109: 
adamc@109:   (** We say that a list of length 0 has no contents, and a list of length [S n'] is a pair of a data value and a list of length [n']. *)
adamc@109: 
adamc@109:   Fixpoint findex (n : nat) : Set :=
adamc@109:     match n with
adamc@109:       | O => Empty_set
adamc@109:       | S n' => option (findex n')
adamc@109:     end.
adamc@109: 
adamc@109:   (** We express that there are no index values when [n = O], by defining such indices as type [Empty_set]; and we express that, at [n = S n'], there is a choice between picking the first element of the list (represented as [None]) or choosing a later element (represented by [Some idx], where [idx] is an index into the list tail). *)
adamc@109: 
adamc@109:   Fixpoint fget (n : nat) : filist n -> findex n -> A :=
adamc@109:     match n return filist n -> findex n -> A with
adamc@109:       | O => fun _ idx => match idx with end
adamc@109:       | S n' => fun ls idx =>
adamc@109:         match idx with
adamc@109:           | None => fst ls
adamc@109:           | Some idx' => fget n' (snd ls) idx'
adamc@109:         end
adamc@109:     end.
adamc@109: 
adamc@109:   (** Our new [get] implementation needs only one dependent [match], which just copies the stated return type of the function.  Our choices of data structure implementations lead to just the right typing behavior for this new definition to work out. *)
adamc@113: (* end thide *)
adamc@109: End filist.
adamc@109: 
adamc@109: (** Heterogeneous lists are a little trickier to define with recursion, but we then reap similar benefits in simplicity of use. *)
adamc@109: 
adamc@113: (* EX: Come up with an alternate [hlist] definition that makes it easier to write [hget]. *)
adamc@113: 
adamc@109: Section fhlist.
adamc@109:   Variable A : Type.
adamc@109:   Variable B : A -> Type.
adamc@109: 
adamc@113: (* begin thide *)
adamc@109:   Fixpoint fhlist (ls : list A) : Type :=
adamc@109:     match ls with
adamc@109:       | nil => unit
adamc@109:       | x :: ls' => B x * fhlist ls'
adamc@109:     end%type.
adamc@109: 
adamc@109:   (** The definition of [fhlist] follows the definition of [filist], with the added wrinkle of dependently-typed data elements. *)
adamc@109: 
adamc@109:   Variable elm : A.
adamc@109: 
adamc@109:   Fixpoint fmember (ls : list A) : Type :=
adamc@109:     match ls with
adamc@109:       | nil => Empty_set
adamc@109:       | x :: ls' => (x = elm) + fmember ls'
adamc@109:     end%type.
adamc@109: 
adamc@109:   (** The definition of [fmember] follows the definition of [findex].  Empty lists have no members, and member types for nonempty lists are built by adding one new option to the type of members of the list tail.  While for [index] we needed no new information associated with the option that we add, here we need to know that the head of the list equals the element we are searching for.  We express that with a sum type whose left branch is the appropriate equality proposition.  Since we define [fmember] to live in [Type], we can insert [Prop] types as needed, because [Prop] is a subtype of [Type].
adamc@109: 
adamc@109:      We know all of the tricks needed to write a first attempt at a [get] function for [fhlist]s.
adamc@109: 
adamc@109:      [[
adamc@109: 
adamc@109:   Fixpoint fhget (ls : list A) : fhlist ls -> fmember ls -> B elm :=
adamc@109:     match ls return fhlist ls -> fmember ls -> B elm with
adamc@109:       | nil => fun _ idx => match idx with end
adamc@109:       | _ :: ls' => fun mls idx =>
adamc@109:         match idx with
adamc@109:           | inl _ => fst mls
adamc@109:           | inr idx' => fhget ls' (snd mls) idx'
adamc@109:         end
adamc@109:     end.
adamc@109: 
adamc@109:     Only one problem remains.  The expression [fst mls] is not known to have the proper type.  To demonstrate that it does, we need to use the proof available in the [inl] case of the inner [match]. *)
adamc@109: 
adamc@109:   Fixpoint fhget (ls : list A) : fhlist ls -> fmember ls -> B elm :=
adamc@109:     match ls return fhlist ls -> fmember ls -> B elm with
adamc@109:       | nil => fun _ idx => match idx with end
adamc@109:       | _ :: ls' => fun mls idx =>
adamc@109:         match idx with
adamc@109:           | inl pf => match pf with
adamc@109:                         | refl_equal => fst mls
adamc@109:                       end
adamc@109:           | inr idx' => fhget ls' (snd mls) idx'
adamc@109:         end
adamc@109:     end.
adamc@109: 
adamc@109:   (** By pattern-matching on the equality proof [pf], we make that equality known to the type-checker.  Exactly why this works can be seen by studying the definition of equality. *)
adamc@109: 
adamc@109:   Print eq.
adamc@109:   (** [[
adamc@109: 
adamc@109: Inductive eq (A : Type) (x : A) : A -> Prop :=  refl_equal : x = x
adamc@109: ]]
adamc@109: 
adamc@109: In a proposition [x = y], we see that [x] is a parameter and [y] is a regular argument.  The type of the constructor [refl_equal] shows that [y] can only ever be instantiated to [x].  Thus, within a pattern-match with [refl_equal], occurrences of [y] can be replaced with occurrences of [x] for typing purposes.  All examples of similar dependent pattern matching that we have seen before require explicit annotations, but Coq implements a special case of annotation inference for matches on equality proofs. *)
adamc@113: (* end thide *)
adamc@109: End fhlist.
adamc@110: 
adamc@111: Implicit Arguments fhget [A B elm ls].
adamc@111: 
adamc@110: 
adamc@110: (** * Data Structures as Index Functions *)
adamc@110: 
adamc@110: (** Indexed lists can be useful in defining other inductive types with constructors that take variable numbers of arguments.  In this section, we consider parameterized trees with arbitrary branching factor. *)
adamc@110: 
adamc@110: Section tree.
adamc@110:   Variable A : Set.
adamc@110: 
adamc@110:   Inductive tree : Set :=
adamc@110:   | Leaf : A -> tree
adamc@110:   | Node : forall n, ilist tree n -> tree.
adamc@110: End tree.
adamc@110: 
adamc@110: (** Every [Node] of a [tree] has a natural number argument, which gives the number of child trees in the second argument, typed with [ilist].  We can define two operations on trees of naturals: summing their elements and incrementing their elements.  It is useful to define a generic fold function on [ilist]s first. *)
adamc@110: 
adamc@110: Section ifoldr.
adamc@110:   Variables A B : Set.
adamc@110:   Variable f : A -> B -> B.
adamc@110:   Variable i : B.
adamc@110: 
adamc@110:   Fixpoint ifoldr n (ls : ilist A n) {struct ls} : B :=
adamc@110:     match ls with
adamc@110:       | Nil => i
adamc@110:       | Cons _ x ls' => f x (ifoldr ls')
adamc@110:     end.
adamc@110: End ifoldr.
adamc@110: 
adamc@110: Fixpoint sum (t : tree nat) : nat :=
adamc@110:   match t with
adamc@110:     | Leaf n => n
adamc@110:     | Node _ ls => ifoldr (fun t' n => sum t' + n) O ls
adamc@110:   end.
adamc@110: 
adamc@110: Fixpoint inc (t : tree nat) : tree nat :=
adamc@110:   match t with
adamc@110:     | Leaf n => Leaf (S n)
adamc@110:     | Node _ ls => Node (imap inc ls)
adamc@110:   end.
adamc@110: 
adamc@110: (** Now we might like to prove that [inc] does not decrease a tree's [sum]. *)
adamc@110: 
adamc@110: Theorem sum_inc : forall t, sum (inc t) >= sum t.
adamc@113: (* begin thide *)
adamc@110:   induction t; crush.
adamc@110:   (** [[
adamc@110: 
adamc@110:   n : nat
adamc@110:   i : ilist (tree nat) n
adamc@110:   ============================
adamc@110:    ifoldr (fun (t' : tree nat) (n0 : nat) => sum t' + n0) 0 (imap inc i) >=
adamc@110:    ifoldr (fun (t' : tree nat) (n0 : nat) => sum t' + n0) 0 i
adamc@110:    ]]
adamc@110: 
adamc@110:    We are left with a single subgoal which does not seem provable directly.  This is the same problem that we met in Chapter 3 with other nested inductive types. *)
adamc@110: 
adamc@110:   Check tree_ind.
adamc@110:   (** [[
adamc@110: 
adamc@110: tree_ind
adamc@110:      : forall (A : Set) (P : tree A -> Prop),
adamc@110:        (forall a : A, P (Leaf a)) ->
adamc@110:        (forall (n : nat) (i : ilist (tree A) n), P (Node i)) ->
adamc@110:        forall t : tree A, P t
adamc@110: ]]
adamc@110: 
adamc@110: The automatically-generated induction principle is too weak.  For the [Node] case, it gives us no inductive hypothesis.  We could write our own induction principle, as we did in Chapter 3, but there is an easier way, if we are willing to alter the definition of [tree]. *)
adamc@110: Abort.
adamc@110: 
adamc@110: Reset tree.
adamc@110: 
adamc@110: (** First, let us try using our recursive definition of [ilist]s instead of the inductive version. *)
adamc@110: 
adamc@110: Section tree.
adamc@110:   Variable A : Set.
adamc@110: 
adamc@110:   (** [[
adamc@110: 
adamc@110:   Inductive tree : Set :=
adamc@110:   | Leaf : A -> tree
adamc@110:   | Node : forall n, filist tree n -> tree.
adamc@110: 
adamc@110: [[
adamc@110: 
adamc@110: Error: Non strictly positive occurrence of "tree" in
adamc@110:  "forall n : nat, filist tree n -> tree"
adamc@110: ]]
adamc@110: 
adamc@110:   The special-case rule for nested datatypes only works with nested uses of other inductive types, which could be replaced with uses of new mutually-inductive types.  We defined [filist] recursively, so it may not be used for nested recursion.
adamc@110: 
adamc@110:   Our final solution uses yet another of the inductive definition techniques introduced in Chapter 3, reflexive types.  Instead of merely using [index] to get elements out of [ilist], we can %\textit{%#<i>#define#</i>#%}% [ilist] in terms of [index].  For the reasons outlined above, it turns out to be easier to work with [findex] in place of [index]. *)
adamc@110: 
adamc@110:   Inductive tree : Set :=
adamc@110:   | Leaf : A -> tree
adamc@110:   | Node : forall n, (findex n -> tree) -> tree.
adamc@110: 
adamc@110:   (** A [Node] is indexed by a natural number [n], and the node's [n] children are represented as a function from [findex n] to trees, which is isomorphic to the [ilist]-based representation that we used above. *)
adamc@110: End tree.
adamc@110: 
adamc@110: Implicit Arguments Node [A n].
adamc@110: 
adamc@110: (** We can redefine [sum] and [inc] for our new [tree] type.  Again, it is useful to define a generic fold function first.  This time, it takes in a function whose range is some [findex] type, and it folds another function over the results of calling the first function at every possible [findex] value. *)
adamc@110: 
adamc@110: Section rifoldr.
adamc@110:   Variables A B : Set.
adamc@110:   Variable f : A -> B -> B.
adamc@110:   Variable i : B.
adamc@110: 
adamc@110:   Fixpoint rifoldr (n : nat) : (findex n -> A) -> B :=
adamc@110:     match n return (findex n -> A) -> B with
adamc@110:       | O => fun _ => i
adamc@110:       | S n' => fun get => f (get None) (rifoldr n' (fun idx => get (Some idx)))
adamc@110:     end.
adamc@110: End rifoldr.
adamc@110: 
adamc@110: Implicit Arguments rifoldr [A B n].
adamc@110: 
adamc@110: Fixpoint sum (t : tree nat) : nat :=
adamc@110:   match t with
adamc@110:     | Leaf n => n
adamc@110:     | Node _ f => rifoldr plus O (fun idx => sum (f idx))
adamc@110:   end.
adamc@110: 
adamc@110: Fixpoint inc (t : tree nat) : tree nat :=
adamc@110:   match t with
adamc@110:     | Leaf n => Leaf (S n)
adamc@110:     | Node _ f => Node (fun idx => inc (f idx))
adamc@110:   end.
adamc@110: 
adamc@110: (** Now we are ready to prove the theorem where we got stuck before.  We will not need to define any new induction principle, but it %\textit{%#<i>#will#</i>#%}% be helpful to prove some lemmas. *)
adamc@110: 
adamc@110: Lemma plus_ge : forall x1 y1 x2 y2,
adamc@110:   x1 >= x2
adamc@110:   -> y1 >= y2
adamc@110:   -> x1 + y1 >= x2 + y2.
adamc@110:   crush.
adamc@110: Qed.
adamc@110: 
adamc@110: Lemma sum_inc' : forall n (f1 f2 : findex n -> nat),
adamc@110:   (forall idx, f1 idx >= f2 idx)
adamc@110:   -> rifoldr plus 0 f1 >= rifoldr plus 0 f2.
adamc@110:   Hint Resolve plus_ge.
adamc@110: 
adamc@110:   induction n; crush.
adamc@110: Qed.
adamc@110: 
adamc@110: Theorem sum_inc : forall t, sum (inc t) >= sum t.
adamc@110:   Hint Resolve sum_inc'.
adamc@110: 
adamc@110:   induction t; crush.
adamc@110: Qed.
adamc@110: 
adamc@113: (* end thide *)
adamc@113: 
adamc@110: (** Even if Coq would generate complete induction principles automatically for nested inductive definitions like the one we started with, there would still be advantages to using this style of reflexive encoding.  We see one of those advantages in the definition of [inc], where we did not need to use any kind of auxiliary function.  In general, reflexive encodings often admit direct implementations of operations that would require recursion if performed with more traditional inductive data structures. *)
adamc@111: 
adamc@111: (** ** Another Interpreter Example *)
adamc@111: 
adamc@112: (** We develop another example of variable-arity constructors, in the form of optimization of a small expression language with a construct like Scheme's %\texttt{%#<tt>#cond#</tt>#%}%.  Each of our conditional expressions takes a list of pairs of boolean tests and bodies.  The value of the conditional comes from the body of the first test in the list to evaluate to [true].  To simplify the interpreter we will write, we force each conditional to include a final, default case. *)
adamc@112: 
adamc@112: Inductive type' : Type := Nat | Bool.
adamc@111: 
adamc@111: Inductive exp' : type' -> Type :=
adamc@112: | NConst : nat -> exp' Nat
adamc@112: | Plus : exp' Nat -> exp' Nat -> exp' Nat
adamc@112: | Eq : exp' Nat -> exp' Nat -> exp' Bool
adamc@111: 
adamc@112: | BConst : bool -> exp' Bool
adamc@113: (* begin thide *)
adamc@112: | Cond : forall n t, (findex n -> exp' Bool)
adamc@111:   -> (findex n -> exp' t) -> exp' t -> exp' t.
adamc@113: (* end thide *)
adamc@111: 
adamc@112: (** A [Cond] is parameterized by a natural [n], which tells us how many cases this conditional has.  The test expressions are represented with a function of type [findex n -> exp' Bool], and the bodies are represented with a function of type [findex n -> exp' t], where [t] is the overall type.  The final [exp' t] argument is the default case.
adamc@112: 
adamc@112: We start implementing our interpreter with a standard type denotation function. *)
adamc@112: 
adamc@111: Definition type'Denote (t : type') : Set :=
adamc@111:   match t with
adamc@112:     | Nat => nat
adamc@112:     | Bool => bool
adamc@111:   end.
adamc@111: 
adamc@112: (** To implement the expression interpreter, it is useful to have the following function that implements the functionality of [Cond] without involving any syntax. *)
adamc@112: 
adamc@113: (* begin thide *)
adamc@111: Section cond.
adamc@111:   Variable A : Set.
adamc@111:   Variable default : A.
adamc@111: 
adamc@111:   Fixpoint cond (n : nat) : (findex n -> bool) -> (findex n -> A) -> A :=
adamc@111:     match n return (findex n -> bool) -> (findex n -> A) -> A with
adamc@111:       | O => fun _ _ => default
adamc@111:       | S n' => fun tests bodies =>
adamc@111:         if tests None
adamc@111:           then bodies None
adamc@111:           else cond n'
adamc@111:             (fun idx => tests (Some idx))
adamc@111:             (fun idx => bodies (Some idx))
adamc@111:     end.
adamc@111: End cond.
adamc@111: 
adamc@111: Implicit Arguments cond [A n].
adamc@113: (* end thide *)
adamc@111: 
adamc@112: (** Now the expression interpreter is straightforward to write. *)
adamc@112: 
adamc@111: Fixpoint exp'Denote t (e : exp' t) {struct e} : type'Denote t :=
adamc@111:   match e in exp' t return type'Denote t with
adamc@111:     | NConst n =>
adamc@111:       n
adamc@111:     | Plus e1 e2 =>
adamc@111:       exp'Denote e1 + exp'Denote e2
adamc@111:     | Eq e1 e2 =>
adamc@111:       if eq_nat_dec (exp'Denote e1) (exp'Denote e2) then true else false
adamc@111: 
adamc@111:     | BConst b =>
adamc@111:       b
adamc@111:     | Cond _ _ tests bodies default =>
adamc@113: (* begin thide *)
adamc@111:       cond
adamc@111:       (exp'Denote default)
adamc@111:       (fun idx => exp'Denote (tests idx))
adamc@111:       (fun idx => exp'Denote (bodies idx))
adamc@113: (* end thide *)
adamc@111:   end.
adamc@111: 
adamc@112: (** We will implement a constant-folding function that optimizes conditionals, removing cases with known-[false] tests and cases that come after known-[true] tests.  A function [cfoldCond] implements the heart of this logic.  The convoy pattern is used again near the end of the implementation. *)
adamc@112: 
adamc@113: (* begin thide *)
adamc@111: Section cfoldCond.
adamc@111:   Variable t : type'.
adamc@111:   Variable default : exp' t.
adamc@111: 
adamc@112:   Fixpoint cfoldCond (n : nat)
adamc@112:     : (findex n -> exp' Bool) -> (findex n -> exp' t) -> exp' t :=
adamc@112:     match n return (findex n -> exp' Bool) -> (findex n -> exp' t) -> exp' t with
adamc@111:       | O => fun _ _ => default
adamc@111:       | S n' => fun tests bodies =>
adamc@111:         match tests None with
adamc@111:           | BConst true => bodies None
adamc@111:           | BConst false => cfoldCond n'
adamc@111:             (fun idx => tests (Some idx))
adamc@111:             (fun idx => bodies (Some idx))
adamc@111:           | _ =>
adamc@111:             let e := cfoldCond n'
adamc@111:               (fun idx => tests (Some idx))
adamc@111:               (fun idx => bodies (Some idx)) in
adamc@112:             match e in exp' t return exp' t -> exp' t with
adamc@112:               | Cond n _ tests' bodies' default' => fun body =>
adamc@111:                 Cond
adamc@111:                 (S n)
adamc@111:                 (fun idx => match idx with
adamc@112:                               | None => tests None
adamc@111:                               | Some idx => tests' idx
adamc@111:                             end)
adamc@111:                 (fun idx => match idx with
adamc@111:                               | None => body
adamc@111:                               | Some idx => bodies' idx
adamc@111:                             end)
adamc@111:                 default'
adamc@112:               | e => fun body =>
adamc@111:                 Cond
adamc@111:                 1
adamc@112:                 (fun _ => tests None)
adamc@111:                 (fun _ => body)
adamc@111:                 e
adamc@112:             end (bodies None)
adamc@111:         end
adamc@111:     end.
adamc@111: End cfoldCond.
adamc@111: 
adamc@111: Implicit Arguments cfoldCond [t n].
adamc@113: (* end thide *)
adamc@111: 
adamc@112: (** Like for the interpreters, most of the action was in this helper function, and [cfold] itself is easy to write. *)
adamc@112: 
adamc@111: Fixpoint cfold t (e : exp' t) {struct e} : exp' t :=
adamc@111:   match e in exp' t return exp' t with
adamc@111:     | NConst n => NConst n
adamc@111:     | Plus e1 e2 =>
adamc@111:       let e1' := cfold e1 in
adamc@111:       let e2' := cfold e2 in
adamc@111:       match e1', e2' with
adamc@111:         | NConst n1, NConst n2 => NConst (n1 + n2)
adamc@111:         | _, _ => Plus e1' e2'
adamc@111:       end
adamc@111:     | Eq e1 e2 =>
adamc@111:       let e1' := cfold e1 in
adamc@111:       let e2' := cfold e2 in
adamc@111:       match e1', e2' with
adamc@111:         | NConst n1, NConst n2 => BConst (if eq_nat_dec n1 n2 then true else false)
adamc@111:         | _, _ => Eq e1' e2'
adamc@111:       end
adamc@111: 
adamc@111:     | BConst b => BConst b
adamc@111:     | Cond _ _ tests bodies default =>
adamc@113: (* begin thide *)
adamc@111:       cfoldCond
adamc@111:       (cfold default)
adamc@111:       (fun idx => cfold (tests idx))
adamc@111:       (fun idx => cfold (bodies idx))
adamc@113: (* end thide *)
adamc@111:   end.
adamc@111: 
adamc@113: (* begin thide *)
adamc@112: (** To prove our final correctness theorem, it is useful to know that [cfoldCond] preserves expression meanings.  This lemma formalizes that property.  The proof is a standard mostly-automated one, with the only wrinkle being a guided instantation of the quantifiers in the induction hypothesis. *)
adamc@112: 
adamc@111: Lemma cfoldCond_correct : forall t (default : exp' t)
adamc@112:   n (tests : findex n -> exp' Bool) (bodies : findex n -> exp' t),
adamc@111:   exp'Denote (cfoldCond default tests bodies)
adamc@111:   = exp'Denote (Cond n tests bodies default).
adamc@111:   induction n; crush;
adamc@111:     match goal with
adamc@111:       | [ IHn : forall tests bodies, _, tests : _ -> _, bodies : _ -> _ |- _ ] =>
adamc@111:         generalize (IHn (fun idx => tests (Some idx)) (fun idx => bodies (Some idx)));
adamc@111:           clear IHn; intro IHn
adamc@111:     end;
adamc@111:     repeat (match goal with
adamc@111:               | [ |- context[match ?E with
adamc@111:                                | NConst _ => _
adamc@111:                                | Plus _ _ => _
adamc@111:                                | Eq _ _ => _
adamc@111:                                | BConst _ => _
adamc@111:                                | Cond _ _ _ _ _ => _
adamc@111:                              end] ] => dep_destruct E
adamc@111:               | [ |- context[if ?B then _ else _] ] => destruct B
adamc@111:             end; crush).
adamc@111: Qed.
adamc@111: 
adamc@112: (** It is also useful to know that the result of a call to [cond] is not changed by substituting new tests and bodies functions, so long as the new functions have the same input-output behavior as the old.  It turns out that, in Coq, it is not possible to prove in general that functions related in this way are equal.  We treat this issue with our discussion of axioms in a later chapter.  For now, it suffices to prove that the particular function [cond] is %\textit{%#<i>#extensional#</i>#%}%; that is, it is unaffected by substitution of functions with input-output equivalents. *)
adamc@112: 
adamc@111: Lemma cond_ext : forall (A : Set) (default : A) n (tests tests' : findex n -> bool)
adamc@111:   (bodies bodies' : findex n -> A),
adamc@111:   (forall idx, tests idx = tests' idx)
adamc@111:   -> (forall idx, bodies idx = bodies' idx)
adamc@111:   -> cond default tests bodies
adamc@111:   = cond default tests' bodies'.
adamc@111:   induction n; crush;
adamc@111:     match goal with
adamc@111:       | [ |- context[if ?E then _ else _] ] => destruct E
adamc@111:     end; crush.
adamc@111: Qed.
adamc@111: 
adamc@112: (** Now the final theorem is easy to prove.  We add our two lemmas as hints and perform standard automation with pattern-matching of subterms to destruct. *)
adamc@113: (* end thide *)
adamc@112: 
adamc@111: Theorem cfold_correct : forall t (e : exp' t),
adamc@111:   exp'Denote (cfold e) = exp'Denote e.
adamc@113: (* begin thide *)
adamc@111:   Hint Rewrite cfoldCond_correct : cpdt.
adamc@111:   Hint Resolve cond_ext.
adamc@111: 
adamc@111:   induction e; crush;
adamc@111:     repeat (match goal with
adamc@111:               | [ |- context[cfold ?E] ] => dep_destruct (cfold E)
adamc@111:             end; crush).
adamc@111: Qed.
adamc@113: (* end thide *)
adamc@115: 
adamc@115: 
adamc@115: (** * Exercises *)
adamc@115: 
adamc@116: (** remove printing * *)
adamc@116: 
adamc@115: (** Some of the type family definitions from this chapter are duplicated in the [DepList] module of the book source.  Only the recursive versions of length-indexed and heterogeneous lists are included, and they are renamed without the [f] prefixes, e.g., [ilist] in place of [filist].
adamc@115: 
adamc@115: %\begin{enumerate}%#<ol>#
adamc@115: 
adamc@115: %\item%#<li># Define a tree analogue of [hlist].  That is, define a parameterized type of binary trees with data at their leaves, and define a type family [itree] indexed by trees.  The structure of an [itree] mirrors its index tree, with the type of each data element (which only occur at leaves) determined by applying a type function to the corresponding element of the index tree.  Define a type standing for all possible paths from the root of a tree to leaves and use it to implement a function [tget] for extracting an element of an [itree] by path.  Define a function [itmap2] for "mapping over two trees in parallel."  That is, [itmap2] takes in two [itree]s with the same index tree, and it forms a new [itree] with the same index by applying a binary function pointwise.
adamc@115: 
adamc@115:   Repeat this process so that you implement each definition for each of the three definition styles covered in this chapter: inductive, recursive, and reflexive.#</li>#
adamc@116: 
adamc@116: %\item%#<li># Write a dependently-typed interpreter for a simple programming language with ML-style pattern-matching.  The language is defined informally by this grammar:
adamc@116: 
adamc@116:   [[
adamc@116: t ::= bool | t + t
adamc@116: p ::= x | b | inl p | inr p
adamc@116: e ::= x | b | inl e | inr e | case e of [p => e]* | _ => e
adamc@116: ]]
adamc@116: 
adamc@116:   [x] stands for a variable, and [b] stands for a boolean constant.  The production for [case] expressions means that a pattern-match includes zero or more pairs of patterns and expressions, along with a default case.
adamc@116: 
adamc@117:   Your interpreter should be implemented in the style demonstrated in this chapter.  That is, your definition of expressions should use dependent types and de Bruijn indices to combine syntax and typing rules, such that the type of an expression tells the types of variables that are in scope.  You should implement a simple recursive function translating types [t] to [Set], and your interpreter should produce values in the image of this translation.#</li>#
adamc@116: 
adamc@115: #</ol>#%\end{enumerate}% *)