In this chapter, we'll take a more serious look at how to use Coq to study interesting things outside of itself. Our case study is a simple imperative programming language called Imp, embodying a tiny core fragment of conventional mainstream languages such as C and Java. Here is a familiar mathematical function written in Imp. This chapter looks at how to define the syntax and semantics of Imp; further chapters in Programming Language Foundations (Software Foundations, volume 2) develop a theory of program equivalence and introduce Hoare Logic, a widely used logic for reasoning about imperative programs.

Arithmetic and Boolean Expressions

We'll present Imp in three parts: first a core language of arithmetic and boolean expressions, then an extension of these expressions with variables, and finally a language of commands including assignment, conditions, sequencing, and loops.

Syntax

Abstract syntax trees for arithmetic and boolean expressions:

For comparison, here's a conventional BNF (Backus-Naur Form) grammar defining the same abstract syntax:

Evaluation

Evaluating an arithmetic expression produces a number.

Similarly, evaluating a boolean expression yields a boolean.

Optimization

Coq Automation

That last proof was getting a little repetitive. Time to learn a few more Coq tricks...

Tacticals

Tacticals is Coq's term for tactics that take other tactics as arguments — "higher-order tactics," if you will.

The try Tactical

If T is a tactic, then try T is a tactic that is just like T except that, if T fails, try T successfully does nothing at all (instead of failing).

The ; Tactical (Simple Form)

In its most common form, the ; tactical takes two tactics as arguments. The compound tactic T;T' first performs T and then performs T' on each subgoal generated by T. For example:

We can simplify this proof using the ; tactical:

Using try and ; together, we can get rid of the repetition in the proof that was bothering us a little while ago.

This proof can be further improved by removing the trivial first case (for e = ANum n).

The repeat Tactical

The repeat tactical takes another tactic and keeps applying this tactic until it fails. Here is an example showing that 8 is in a long list using repeat.

Defining New Tactic Notations

Coq also provides several ways of "programming" tactic scripts:

• Tactic Notation: syntax extension for tactics (good for simple macros)
• Ltac: scripting language for tactics (good for more sophisticated proof engineering)
• OCaml tactic scripting API (only for wizards)

An example Tactic Notation:

The omega Tactic

The omega tactic implements a decision procedure for a subset of first-order logic called Presburger arithmetic. It is based on the Omega algorithm invented by William Pugh [Pugh 1991]. If the goal is a universally quantified formula made out of

• numeric constants, addition (+ and S), subtraction (- and pred), and multiplication by constants (this is what makes it Presburger arithmetic),
• equality (= and ≠) and ordering (≤), and
• the logical connectives ∧, ∨, ¬, and →,

then invoking omega will either solve the goal or fail, meaning that the goal is actually false. (If the goal is not of this form, omega will also fail.)

A Few More Handy Tactics

Finally, here are some miscellaneous tactics that you may find convenient.

• clear H: Delete hypothesis H from the context.
• subst x: Find an assumption x = e or e = x in the context, replace x with e throughout the context and current goal, and clear the assumption.
• subst: Substitute away all assumptions of the form x = e or e = x.
• rename... into...: Change the name of a hypothesis in the proof context. For example, if the context includes a variable named x, then rename x into y will change all occurrences of x to y.
• assumption: Try to find a hypothesis H in the context that exactly matches the goal; if one is found, behave like exact H.
• contradiction: Try to find a hypothesis H in the current context that is logically equivalent to False. If one is found, solve the goal.
• constructor: Try to find a constructor c (from some Inductive definition in the current environment) that can be applied to solve the current goal. If one is found, behave like apply c.

We'll see examples as we go along.

Evaluation as a Relation

We have presented aeval and beval as functions defined by Fixpoints. Another way to think about evaluation — one that we will see is often more flexible — is as a relation between expressions and their values. This leads naturally to Inductive definitions like the following one for arithmetic expressions...

A standard notation for "evaluates to":

If we "reserve" the notation in advance, we can even use it in the definition:

Inference Rule Notation

For example, the constructor E_APlus... ...would be written like this as an inference rule:

e1 \\ n1
e2 \\ n2	(E_APlus)
APlus e1 e2 \\ n1+n2

There is nothing very deep going on here:

• rule name corresponds to a constructor name
• above the line are premises
• below the line is conclusion
• metavariables like e₁ and n₁ are implicitly universally quantified
• the whole collection of rules is implicitly wrapped in an Inductive (sometimes we write this slightly more explicitly, as "...closed under these rules...")

Computational vs. Relational Definitions

We have seen that we can use either relations or functions to give a semantics expression for evaluation, with different tradeoffs. But in general, relational semantics (being lower level and more flexible) are sometimes the only reasonable option...

Adding division

For example, suppose that we wanted to extend the arithmetic operations by considering also a division operation:

Extending the definition of aeval to handle this new operation would not be straightforward (what should we return as the result of ADiv (ANum 5) (ANum 0)?). But extending aevalR is straightforward.

Adding division, relationally

Adding Nondeterminism

Suppose, instead, that we want to extend the arithmetic operations by a nondeterministic number generator any that, when evaluated, may yield any number. (Note that this is not the same as making a probabilistic choice among all possible numbers — we're not specifying any particular distribution of results, but just saying what results are possible.)

Again, extending aeval would be tricky, since now evaluation is not a deterministic function from expressions to numbers, but extending aevalR is no problem...

Adding nondeterminism, relationally

Tradeoffs

At this point you maybe wondering: which style should I use by default? The examples above show that relational definitions are fundamentally more powerful than functional ones. For situations like these, where the thing being defined is not easy to express as a function, or indeed where it is not a function, there is no choice. But what about when both styles are workable? One point in favor of relational definitions is that they can be more elegant and easier to understand. Another is that Coq automatically generates nice inversion and induction principles from Inductive definitions.

On the other hand, functional definitions can often be more convenient:

• Functions are by definition deterministic and defined on all arguments; for a relation we have to show these properties explicitly if we need them.
• With functions we can also take advantage of Coq's computation mechanism to simplify expressions during proofs.

Furthermore, functions can be directly "extracted" to executable code in OCaml or Haskell.

Ultimately, the choice often comes down to either the specifics of a particular situation or simply a question of taste. Indeed, in large Coq developments it is common to see a definition given in both functional and relational styles, plus a lemma stating that the two coincide, allowing further proofs to switch from one point of view to the other at will.

Expressions With Variables

Let's turn our attention back to defining Imp. The next thing we need to do is to enrich our arithmetic and boolean expressions with variables. To keep things simple, we'll assume that all variables are global and that they only hold numbers.

States

Since we'll want to look variables up to find out their current values, we'll reuse maps from the Maps chapter, with strings as the type of variables in Imp. A machine state (or just state) represents the current values of all variables at some point in the execution of a program.

Syntax

We can add variables to the arithmetic expressions we had before by simply adding one more constructor:

Defining a few variable names as notational shorthands will make examples easier to read:

Notations

To make Imp programs easier to read and write, we introduce some notations and implicit coercions. You do not need to understand what these declarations do in detail to follow this chapter. Briefly, though, the Coercion declaration in Coq stipulates that a function (or constructor) can be implicitly used by the type system to coerce a value of the input type to a value of the output type. For instance, the coercion declaration for AId allows us to use plain strings when an aexp is expected; the string will implicitly be wrapped with AId.

The notations below are declared in specific notation scopes, in order to avoid conflicts with other interpretations of the same symbols. Again, it is not necessary to understand the details.

We can now write 3 + (X * 2) instead of APlus 3 (AMult X 2), and true && !(X ≤ 4) instead of BAnd true (BNot (BLe X 4)).

Evaluation

Now we need to add an st parameter to both evaluation functions:

We specialize our notation for total maps to the specific case of states, i.e. using { --> 0 } as empty state.

Commands

Now we are ready define the syntax and behavior of Imp commands (sometimes called statements).

Syntax

Informally, commands c are described by the following BNF grammar. (We choose this slightly awkward concrete syntax for the sake of being able to define Imp syntax using Coq's Notation mechanism. In particular, we use IFB to avoid conflicting with the if notation from the standard library.)

For example, here's factorial in Imp: When this command terminates, the variable Y will contain the factorial of the initial value of X.

As for expressions, we can use a few Notation declarations to make reading and writing Imp programs more convenient.

Imp Factorial in Coq

For example, here is the factorial function again, written as a formal definition to Coq:

More Examples

Assignment:

Loops

An infinite loop:

Evaluating Commands

Next we need to define what it means to evaluate an Imp command. The fact that WHILE loops don't necessarily terminate makes defining an evaluation function tricky...

Evaluation as a Function (Failed Attempt)

Here's an attempt at defining an evaluation function for commands, omitting the WHILE case.

Evaluation as a Relation

Here's a better way: define ceval as a relation rather than a function — i.e., define it in Prop instead of Type, as we did for aevalR above. We'll use the notation c / st \\ st' for the ceval relation: c / st \\ st' means that executing program c in a starting state st results in an ending state st'. This can be pronounced "c takes state st to st'".

Operational Semantics

Here is an informal definition of evaluation, presented as inference rules for readability:

	(E_Skip)
SKIP / st \\ st

aeval st a1 = n	(E_Ass)
x := a1 / st \\ st & { x --> n }

c1 / st \\ st'
c2 / st' \\ st''	(E_Seq)
c1;;c2 / st \\ st''

beval st b1 = true
c1 / st \\ st'	(E_IfTrue)
IF b1 THEN c1 ELSE c2 FI / st \\ st'

beval st b1 = false
c2 / st \\ st'	(E_IfFalse)
IF b1 THEN c1 ELSE c2 FI / st \\ st'

beval st b = false	(E_WhileFalse)
WHILE b DO c END / st \\ st

beval st b = true
c / st \\ st'
WHILE b DO c END / st' \\ st''	(E_WhileTrue)
WHILE b DO c END / st \\ st''

The cost of defining evaluation as a relation instead of a function is that we now need to construct proofs that some program evaluates to some result state, rather than just letting Coq's computation mechanism do it for us.

Determinism of Evaluation (Optional)