$\mathtt{Prop}$ is very useful for program extraction because it allows us to delete parts of code that are useless. For example, to extract a sorting algorithm we would prove the statement "for every list $\ell$ there is a list $k$ such that $k$ is ordered and $k$ is a permutatiom of $\ell$". If we write this down in Coq and extract without using $\mathtt{Prop}$, we will get:
- "for all $\ell$ there is $k$" will give us a map
sort
which takes lists to lists,
- "such that $k$ is ordered" will give a funciton
verify
which runs through $k$ and checks that it is sorted, and
- "$k$ is a permutation of $\ell$" will give a permutation
pi
which takes $\ell$ to $k$. Note that pi
is not just a mapping, but also the inverse mapping together with programs verifying that the two maps really are inverses.
While the extra stuff is not totally useless, in many applications we want to get rid of it and keep just sort
. This can be accomplished if we use $\mathtt{Prop}$ to state "$k$ is ordered" and "$k$ is a permutation of $\ell$", but not "for all $\ell$ there is $k$".
In general, a common way to extract code is to consider a statement of the form $\forall x : A \,.\, \exists y : B \,.\, \phi(x, y)$ where $x$ is input, $y$ is output, and $\phi(x,y)$ explains what it means for $y$ to be a correct output. (In the above example $A$ and $B$ are the types of lists and $\phi(\ell, k)$ is "$k$ is ordered and $k$ is a permutation of $\ell$.") If $\phi$ is in $\mathtt{Prop}$ then extraction gives a map $f : A \to B$ such that $\phi(x, f(x))$ holds for all $x \in A$. If $\phi$ is in $\mathtt{Set}$ then we also get a function $g$ such that $g(x)$ is the proof that $\phi(x, f(x))$ holds, for all $x \in A$. Often the proof is computationally useless and we prefer to get rid of it, especially when it is nested deeply inside some other statement. $\mathtt{Prop}$ gives us the possibility to do so.
Added 2015-07-29: There is a question whether we could avoid $\mathsf{Prop}$ altogether by automatically optimizing away "useless extracted code". To some extent we can do that, for instance all code extracted from the negative fragment of logic (stuff built from the empty type, unit type, products) is useless as it just shuffles around the unit. But there are genuine design decisions one has to make when using $\mathsf{Prop}$. Here is a simpe example, where $\Sigma$ means that we are in $\mathsf{Type}$ and $\exists$ means we are in $\mathsf{Prop}$. If we extract from
$$\Pi_{n : \mathbb{N}} \Sigma_{b : \{0,1\}} \Sigma_{k : \mathbb{N}} \; n = 2 \cdot k + b$$
we will get a program which decomposes $n$ into its lowest bit $b$ and the remaining bits $k$, i.e., it computes everything. If we extract from
$$\Pi_{n : \mathbb{N}} \Sigma_{b : \{0,1\}} \exists_{k : \mathbb{N}} \; n = 2 \cdot k + b$$
then the program will only compute the lowest bit $b$. The machine cannot tell which is the correct one, the user has to tell it what they want.