In the final chaper of Logical Foundations (Software Foundations, volume 1), we began applying the mathematical tools developed in the first part of the course to studying the theory of a small programming language, Imp.

• We defined a type of abstract syntax trees for Imp, together with an evaluation relation (a partial function on states) that specifies the operational semantics of programs.
  The language we defined, though small, captures some of the key features of full-blown languages like C, C++, and Java, including the fundamental notion of mutable state and some common control structures.
• We proved a number of metatheoretic properties -- "meta" in the sense that they are properties of the language as a whole, rather than of particular programs in the language. These included:
  • determinism of evaluation
  • equivalence of some different ways of writing down the definitions (e.g., functional and relational definitions of arithmetic expression evaluation)
  • guaranteed termination of certain classes of programs
  • correctness (in the sense of preserving meaning) of a number of useful program transformations
  • behavioral equivalence of programs (in the Equiv chapter).

If we stopped here, we would already have something useful: a set of tools for defining and discussing programming languages and language features that are mathematically precise, flexible, and easy to work with, applied to a set of key properties. All of these properties are things that language designers, compiler writers, and users might care about knowing. Indeed, many of them are so fundamental to our understanding of the programming languages we deal with that we might not consciously recognize them as "theorems." But properties that seem intuitively obvious can sometimes be quite subtle (sometimes also subtly wrong!). We'll return to the theme of metatheoretic properties of whole languages later in this volume when we discuss types and type soundness. In this chapter, though, we turn to a different set of issues. Our goal in this chapter is to carry out some simple examples of program verification -- i.e., to use the precise definition of Imp to prove formally that particular programs satisfy particular specifications of their behavior. We'll develop a reasoning system called Floyd-Hoare Logic -- often shortened to just Hoare Logic -- in which each of the syntactic constructs of Imp is equipped with a generic "proof rule" that can be used to reason compositionally about the correctness of programs involving this construct. Hoare Logic originated in the 1960s, and it continues to be the subject of intensive research right up to the present day. It lies at the core of a multitude of tools that are being used in academia and industry to specify and verify real software systems. Hoare Logic combines two beautiful ideas: a natural way of writing down specifications of programs, and a structured proof technique for proving that programs are correct with respect to such specifications -- where by "structured" we mean that the structure of proofs directly mirrors the structure of the programs that they are about.

Assertions

An assertion is a logical claim about the state of a program's memory -- formally, a property of states.

For example,

• fun st ⇒ st X = 3 holds for states st in which value of X is 3,
• fun st ⇒ True hold for all states, and
• fun st ⇒ False holds for no states.

Exercise: 1 star, standard, optional (assertions)

Paraphrase the following assertions in English (or your favorite natural language).

This way of writing assertions can be a little bit heavy, for two reasons: (1) every single assertion that we ever write is going to begin with fun st ⇒ ; and (2) this state st is the only one that we ever use to look up variables in assertions (we will never need to talk about two different memory states at the same time). For discussing examples informally, we'll adopt some simplifying conventions: we'll drop the initial fun st ⇒, and we'll write just X to mean st X. Thus, instead of writing
      fun st ⇒ st X = m we'll write just
      X = m. This example also illustrates a convention that we'll use throughout the Hoare Logic chapters: in informal assertions, capital letters like X, Y, and Z are Imp variables, while lowercase letters like x, y, m, and n are ordinary Coq variables (of type nat). This is why, when translating from informal to formal, we replace X with st X but leave m alone. Given two assertions P and Q, we say that P implies Q, written P ->> Q, if, whenever P holds in some state st, Q also holds.

(The hoare_spec_scope annotation here tells Coq that this notation is not global but is intended to be used in particular contexts. The Open Scope tells Coq that this file is one such context.) We'll also want the "iff" variant of implication between assertions:

Notations for Assertions

The convention described above can be implemented in Coq with a little syntax magic, using coercions and annotation scopes, much as we did with %imp in Imp, to automatically lift aexps, numbers, and Props into Assertions when they appear in the %assertion scope or when Coq knows that the type of an expression is Assertion. There is no need to understand the details of how these notation hacks work. (We barely understand some of it ourselves!)

One small limitation of this approach is that we don't have an automatic way to coerce function applications that appear within an assertion to make appropriate use of the state. Instead, we use an explicit ap operator to lift the function.

Hoare Triples, Informally

A Hoare triple is a claim about the state before and after executing a command. The standard notation is
      {P} c {Q} meaning:

• If command c begins execution in a state satisfying assertion P,
• and if c eventually terminates in some final state,
• then that final state will satisfy the assertion Q.

Assertion P is called the precondition of the triple, and Q is the postcondition. Because single braces are already used for other things in Coq, we'll write Hoare triples with double braces:
       {{P}} c {{Q}} For example,

• {{X = 0}} X := X + 1 {{X = 1}} is a valid Hoare triple, stating that command X := X + 1 will transform a state in which X = 0 to a state in which X = 1.
• ∀ m, {{X = m}} X := X + 1 {{X = m + 1}} is a proposition stating that the Hoare triple {{X = m}} X := X + 1 {{X = m + 1}} is valid for any choice of m. Note that m in the two assertions and the command in the middle is a reference to the Coq variable m, which is bound outside the Hoare triple.

Exercise: 1 star, standard, optional (triples)

Paraphrase the following in English.
     1) {{True}} c {{X = 5}}

     2) ∀ m, {{X = m}} c {{X = m + 5)}}

     3) {{X ≤ Y}} c {{Y ≤ X}}

     4) {{True}} c {{False}}

     5) ∀ m,
          {{X = m}}
          c
          {{Y = real_fact m}}

     6) ∀ m,
          {{X = m}}
          c
          {{(Z × Z) ≤ m ∧ ¬(((S Z) × (S Z)) ≤ m)}}

Exercise: 1 star, standard, optional (valid_triples)

Which of the following Hoare triples are valid -- i.e., the claimed relation between P, c, and Q is true?
   1) {{True}} X := 5 {{X = 5}}

   2) {{X = 2}} X := X + 1 {{X = 3}}

   3) {{True}} X := 5; Y := 0 {{X = 5}}

   4) {{X = 2 ∧ X = 3}} X := 5 {{X = 0}}

   5) {{True}} skip {{False}}

   6) {{False}} skip {{True}}

   7) {{True}} while true do skip end {{False}}

   8) {{X = 0}}
        while X = 0 do X := X + 1 end
      {{X = 1}}

   9) {{X = 1}}
        while X ≠ 0 do X := X + 1 end
      {{X = 100}}

Hoare Triples, Formally

We can formalize valid Hoare triples in Coq as follows:

Exercise: 1 star, standard (hoare_post_true)

Prove that if Q holds in every state, then any triple with Q as its postcondition is valid.

Exercise: 1 star, standard (hoare_pre_false)

Prove that if P holds in no state, then any triple with P as its precondition is valid.

Proof Rules

The goal of Hoare logic is to provide a compositional method for proving the validity of specific Hoare triples. That is, we want the structure of a program's correctness proof to mirror the structure of the program itself. To this end, in the sections below, we'll introduce a rule for reasoning about each of the different syntactic forms of commands in Imp -- one for assignment, one for sequencing, one for conditionals, etc. -- plus a couple of "structural" rules for gluing things together. We will then be able to prove programs correct using these proof rules, without ever unfolding the definition of valid_hoare_triple.

Skip

Since skip doesn't change the state, it preserves any assertion P:

	(hoare_skip)
{{ P }} skip {{ P }}

Sequencing

If command c₁ takes any state where P holds to a state where Q holds, and if c₂ takes any state where Q holds to one where R holds, then doing c₁ followed by c₂ will take any state where P holds to one where R holds:

{{ P }} c1 {{ Q }}
{{ Q }} c2 {{ R }}	(hoare_seq)
{{ P }} c1;c2 {{ R }}

Note that, in the formal rule hoare_seq, the premises are given in backwards order (c₂ before c₁). This matches the natural flow of information in many of the situations where we'll use the rule, since the natural way to construct a Hoare-logic proof is to begin at the end of the program (with the final postcondition) and push postconditions backwards through commands until we reach the beginning.

Assignment

The rule for assignment is the most fundamental of the Hoare logic proof rules. Here's how it works. Consider this incomplete Hoare triple:
       {{ ??? }} X := Y {{ X = 1 }} We want to assign Y to X and finish in a state where X is 1. What could the precondition be? One possibility is Y = 1, because if Y is already 1 then assigning it to X causes X to be 1. That leads to a valid Hoare triple:
       {{ Y = 1 }} X := Y {{ X = 1 }} It may seem as though coming up with that precondition must have taken some clever thought. But there is a mechanical way we could have done it: if we take the postcondition X = 1 and in it replace X with Y---that is, replace the left-hand side of the assignment statement with the right-hand side---we get the precondition, Y = 1. That same idea works in more complicated cases. For example:
       {{ ??? }} X := X + Y {{ X = 1 }} If we replace the X in X = 1 with X + Y, we get X + Y = 1. That again leads to a valid Hoare triple:
       {{ X + Y = 1 }} X := X + Y {{ X = 1 }} Why does this technique work? The postcondition identifies some property P that we want to hold of the variable X being assigned. In this case, P is "equals 1". To complete the triple and make it valid, we need to identify a precondition that guarantees that property will hold of X. Such a precondition must ensure that the same property holds of whatever is being assigned to X. So, in the example, we need "equals 1" to hold of X + Y. That's exactly what the technique guarantees. In general, the postcondition could be some arbitrary assertion Q, and the right-hand side of the assignment could be some arbitrary arithmetic expression a:
       {{ ??? }} X := a {{ Q }} The precondition would then be Q, but with any occurrences of X in it replaced by a. Let's introduce a notation for this idea of replacing occurrences: Define Q [X ⊢> a] to mean "Q where a is substituted in place of X". This yields the Hoare logic rule for assignment:
      {{ Q [X ⊢> a] }} X := a {{ Q }} One way of reading this rule is: If you want statement X := a to terminate in a state that satisfies assertion Q, then it suffices to start in a state that also satisfies Q, except where a is substituted for every occurrence of X. To many people, this rule seems "backwards" at first, because it proceeds from the postcondition to the precondition. Actually it makes good sense to go in this direction: the postcondition is often what is more important, because it characterizes what we can assume afer running the code. Nonetheless, it's also possible to formulate a "forward" assignment rule. We'll do that later in some exercises. Here are some valid instances of the assignment rule:
      {{ (X ≤ 5) [X ⊢> X + 1] }} (that is, X + 1 ≤ 5)
        X := X + 1
      {{ X ≤ 5 }}

      {{ (X = 3) [X ⊢> 3] }} (that is, 3 = 3)
        X := 3
      {{ X = 3 }}

      {{ (0 ≤ X ∧ X ≤ 5) [X ⊢> 3] (that is, 0 ≤ 3 ∧ 3 ≤ 5)
        X := 3
      {{ 0 ≤ X ∧ X ≤ 5 }} To formalize the rule, we must first formalize the idea of "substituting an expression for an Imp variable in an assertion", which we refer to as assertion substitution, or assertion_sub. That is, intuitively, given a proposition P, a variable X, and an arithmetic expression a, we want to derive another proposition P' that is just the same as P except that P' should mention a wherever P mentions X. This operation is related to the idea of substituting Imp expressions for Imp variables that we saw in Equiv (subst_aexp and friends). The difference is that, here, P is an arbitrary Coq assertion, so we can't directly "edit" its text. However, we can achieve the same effect by evaluating P in an updated state:

That is, P [X ⊢> a] stands for an assertion -- let's call it P' -- that is just like P except that, wherever P looks up the variable X in the current state, P' instead uses the value of the expression a. To see how this works, let's calculate what happens with a couple of examples. First, suppose P' is (X ≤ 5) [X ⊢> 3] -- that is, more formally, P' is the Coq expression
    fun st ⇒
      (fun st' ⇒ st' X ≤ 5)
      (X !-> aeval st 3 ; st), which simplifies to
    fun st ⇒
      (fun st' ⇒ st' X ≤ 5)
      (X !-> 3 ; st) and further simplifies to
    fun st ⇒
      ((X !-> 3 ; st) X) ≤ 5 and finally to
    fun st ⇒
      3 ≤ 5. That is, P' is the assertion that 3 is less than or equal to 5 (as expected). For a more interesting example, suppose P' is (X ≤ 5) [X ⊢> X + 1]. Formally, P' is the Coq expression
    fun st ⇒
      (fun st' ⇒ st' X ≤ 5)
      (X !-> aeval st (X + 1) ; st), which simplifies to
    fun st ⇒
      (X !-> aeval st (X + 1) ; st) X ≤ 5 and further simplifies to
    fun st ⇒
      (aeval st (X + 1)) ≤ 5. That is, P' is the assertion that X + 1 is at most 5. Now, using the substitution operation we've just defined, we can give the precise proof rule for assignment:

	(hoare_asgn)
{{Q [X ⊢> a]}} X := a {{Q}}

We can prove formally that this rule is indeed valid.

Here's a first formal proof using this rule.

Of course, what we'd probably prefer is to prove this simpler triple:
      {{X < 4}} X := X + 1 {{X < 5}} We will see how to do so in the next section. Complete these Hoare triples by providing an appropriate precondition using ∃, then prove then with apply hoare_asgn. If you find that tactic doesn't suffice, double check that you have completed the triple properly.

Exercise: 2 stars, standard (hoare_asgn_examples1)

Exercise: 2 stars, standard (hoare_asgn_examples2)

Exercise: 2 stars, standard, especially useful (hoare_asgn_wrong)

The assignment rule looks backward to almost everyone the first time they see it. If it still seems puzzling to you, it may help to think a little about alternative "forward" rules. Here is a seemingly natural one:

	(hoare_asgn_wrong)
{{ True }} X := a {{ X = a }}

Give a counterexample showing that this rule is incorrect and use it to complete the proof below, showing that it is really a counterexample. (Hint: The rule universally quantifies over the arithmetic expression a, and your counterexample needs to exhibit an a for which the rule doesn't work.)

Exercise: 3 stars, advanced (hoare_asgn_fwd)

By using a parameter m (a Coq number) to remember the original value of X we can define a Hoare rule for assignment that does, intuitively, "work forwards" rather than backwards.

	(hoare_asgn_fwd)
{{fun st => P st /\ st X = m}}
X := a
{{fun st => P (X !-> m ; st) /\ st X = aeval (X !-> m ; st) a }}

Note that we need to write out the postcondition in "desugared" form, because it needs to talk about two different states: we use the original value of X to reconstruct the state st' before the assignment took place. (Also note that this rule is more complicated than hoare_asgn!) Prove that this rule is correct.

Exercise: 2 stars, advanced (hoare_asgn_fwd_exists)

Another way to define a forward rule for assignment is to existentially quantify over the previous value of the assigned variable. Prove that it is correct.

	(hoare_asgn_fwd_exists)
{{fun st => P st}}
X := a
{{fun st => exists m, P (X !-> m ; st) /\
st X = aeval (X !-> m ; st) a }}

Consequence

Sometimes the preconditions and postconditions we get from the Hoare rules won't quite be the ones we want in the particular situation at hand -- they may be logically equivalent but have a different syntactic form that fails to unify with the goal we are trying to prove, or they actually may be logically weaker (for preconditions) or stronger (for postconditions) than what we need. For instance,
      {{(X = 3) [X ⊢> 3]}} X := 3 {{X = 3}}, follows directly from the assignment rule, but
      {{True}} X := 3 {{X = 3}} does not. This triple is valid, but it is not an instance of hoare_asgn because True and (X = 3) [X ⊢> 3] are not syntactically equal assertions. However, they are logically equivalent, so if one triple is valid, then the other must certainly be as well. We can capture this observation with the following rule:

{{P'}} c {{Q}}
P <<->> P'	(hoare_consequence_pre_equiv)
{{P}} c {{Q}}

Taking this line of thought a bit further, we can see that strengthening the precondition or weakening the postcondition of a valid triple always produces another valid triple. This observation is captured by two Rules of Consequence.

{{P'}} c {{Q}}
P ->> P'	(hoare_consequence_pre)
{{P}} c {{Q}}

{{P}} c {{Q'}}
Q' ->> Q	(hoare_consequence_post)
{{P}} c {{Q}}

Here are the formal versions:

For example, we can use the first consequence rule like this:
    {{ True }} ->>
    {{ (X = 1) [X ⊢> 1] }}
      X := 1
    {{ X = 1 }} Or, formally...

Exercise: 1 star, standard (assertion_sub_example1)

We can also use it to prove the example mentioned earlier.
    {{ X < 4 }} ->>
    {{ (X < 5)[X ⊢> X + 1] }}
      X := X + 1
    {{ X < 5 }} Or, formally ...

Give a formal proof for the addition example in the lecture.

Exercise: 2 stars, standard (hoare_add_consecutively)

Finally, here is a combined rule of consequence that allows us to vary both the precondition and the postcondition.

{{P'}} c {{Q'}}
P ->> P'
Q' ->> Q	(hoare_consequence)
{{P}} c {{Q}}