Imp: Simple Imperative Programs

In this chapter, we take a more serious look at how to use Coq to study other things. 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.

       Z ::= X;;
       Y ::= 1;;
       WHILE ~(Z = 0) DO
         Y ::= Y * Z;;
         Z ::= Z - 1
       END

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

These two definitions specify the abstract syntax of arithmetic and boolean expressions.

In this chapter, we'll mostly elide the translation from the concrete syntax that a programmer would actually write to these abstract syntax trees -- the process that, for example, would translate the string "1 + 2 * 3" to the AST APlus (ANum 1) (AMult (ANum 2) (ANum 3)) For comparison, here's a conventional BNF (Backus-Naur Form) grammar defining the same abstract syntax:

    a ::= nat
        | a + a
        | a - a
        | a * a

    b ::= true
        | false
        | a = a
        | a <= a
        | ~ b
        | b && b

Compared to the Coq version above...

• The BNF is more informal -- for example, it gives some suggestions about the surface syntax of expressions (like the fact that the addition operation is written with an infix +) while leaving other aspects of lexical analysis and parsing (like the relative precedence of +, -, and *, the use of parens to group subexpressions, etc.) unspecified. Some additional information -- and human intelligence -- would be required to turn this description into a formal definition, e.g., for implementing a compiler.
  The Coq version consistently omits all this information and concentrates on the abstract syntax only.
• Conversely, the BNF version is lighter and easier to read. Its informality makes it flexible, a big advantage in situations like discussions at the blackboard, where conveying general ideas is more important than getting every detail nailed down precisely.
  Indeed, there are dozens of BNF-like notations and people switch freely among them, usually without bothering to say which kind of BNF they're using because there is no need to: a rough-and-ready informal understanding is all that's important.

It's good to be comfortable with both sorts of notations: informal ones for communicating between humans and formal ones for carrying out implementations and proofs.

Evaluation

Evaluating an arithmetic expression produces a number.

Similarly, evaluating a boolean expression yields a boolean.

Optimization (i.e., a first compiler pass)

We haven't defined very much yet, but we can already get some mileage out of the definitions. Suppose we define a function that takes an arithmetic expression and slightly simplifies it, changing every occurrence of 0 + e (i.e., (APlus (ANum 0) e) into just e.

To make sure our optimization is doing the right thing we can test it on some examples and see if the output looks OK.

But if we want to be sure the optimization is correct -- i.e., that evaluating an optimized expression gives the same result as the original -- we should prove it.

Evaluation as a Relation

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

Instead, we've chosen to leave the hypotheses anonymous, just giving their types. This style gives us less control over the names that Coq chooses during proofs involving aevalR, but it makes the definition itself quite a bit lighter.

It will be convenient to have an infix notation for aevalR. We'll write e \\ n to mean that arithmetic expression e evaluates to value n.

In fact, Coq provides a way to use this notation in the definition of aevalR itself. This reduces confusion by avoiding situations where we're working on a proof involving statements in the form e \\ n but we have to refer back to a definition written using the form aevalR e n. We do this by first "reserving" the notation, then giving the definition together with a declaration of what the notation means.

Inference Rule Notation

In informal discussions, it is convenient to write the rules for aevalR and similar relations in the more readable graphical form of inference rules, where the premises above the line justify the conclusion below the line (we have already seen them in the IndProp chapter). For example, the constructor E_APlus...

      | E_APlus : forall (e1 e2: aexp) (n1 n2: nat),
          aevalR e1 n1 ->
          aevalR e2 n2 ->
          aevalR (APlus e1 e2) (n1 + n2)

...would be written like this as an inference rule:

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

Formally, there is nothing deep about inference rules: they are just implications. You can read the rule name on the right as the name of the constructor and read each of the linebreaks between the premises above the line (as well as the line itself) as ->. All the variables mentioned in the rule (e1, n1, etc.) are implicitly bound by universal quantifiers at the beginning. (Such variables are often called metavariables to distinguish them from the variables of the language we are defining. At the moment, our arithmetic expressions don't include variables, but we'll soon be adding them.) The whole collection of rules is understood as being wrapped in an Inductive declaration. In informal prose, this is either elided or else indicated by saying something like "Let aevalR be the smallest relation closed under the following rules...". For example, \\ is the smallest relation closed under these rules:

                             -----------                               (E_ANum)
                             ANum n \\ n

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

                               e1 \\ n1
                               e2 \\ n2
                        ---------------------                        (E_AMinus)
                        AMinus e1 e2 \\ n1-n2

                               e1 \\ n1
                               e2 \\ n2
                         --------------------                         (E_AMult)
                         AMult e1 e2 \\ n1*n2

Equivalence of the Definitions

It is straightforward to prove that the relational and functional definitions of evaluation agree:

Computational vs. Relational Definitions

For the definitions of evaluation for arithmetic and boolean expressions, the choice of whether to use functional or relational definitions is mainly a matter of taste: either way works. However, there are circumstances where relational definitions of evaluation work much better than functional ones.

For example, suppose that we wanted to extend the arithmetic operations with division:

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.

Or suppose 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 probability distribution for the results, 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...

At this point you maybe wondering: which style should I use by default? In the examples we've just seen, relational definitions turned out to be more useful 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 real 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" from Gallina 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

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 define state as a function type from strings, which represent variables, to nats. This machine state (or just state) represents the current values of all variables at some point in the execution of a program. For simplicity, we assume that the state is defined for all variables, even though any given program is only going to mention a finite number of them. The state captures all of the information stored in memory. For Imp programs, because each variable stores a natural number, we can represent the state as a mapping from strings to nat, and will use 0 as default value in the store. For more complex programming languages, the state might have more structure.

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:

The definition of bexps is unchanged (except that it now refers to the new aexps):

Notations

To make Imp programs easier to read and write, we introduce some notations and implicit coercions. You do not need to understand exactly what these declarations do. 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, but it is important to recognize that we are defining new intepretations for some familiar operators like +, -, *, =., [<=], etc.

One downside of these coercions is that they can make it a little harder for humans to calculate the types of expressions. If you get confused, try doing Set Printing Coercions to see exactly what is going on.

Evaluation

The arith and boolean evaluators are extended to handle variables in the obvious way, taking a state as an extra argument:

An empty state returns 0 for all variables.

We can write a definition for extending a state with a new binding.

Now we can add a notation for a "singleton state" with just one variable bound to a value.

And extending an existing state with a new variable.

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.

     c ::= SKIP | x ::= a | c ;; c | TEST b THEN c ELSE c FI
         | WHILE b DO c END

(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 TEST to avoid conflicting with the if and IF notations from the standard library.) For example, here's factorial in Imp:

     Z ::= X;;
     Y ::= 1;;
     WHILE ~(Z = 0) DO
       Y ::= Y * Z;;
       Z ::= Z - 1
     END

When this command terminates, the variable Y will contain the factorial of the initial value of X. Here is the formal definition of the abstract syntax of commands:

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

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

Desugaring notations

Coq offers a rich set of features to manage the increasing complexity of the objects we work with, such as coercions and notations. However, their heavy usage can make for quite overwhelming syntax. It is often instructive to "turn off" those features to get a more elementary picture of things, using the following commands:

• Unset Printing Notations (undo with Set Printing Notations)
• Set Printing Coercions (undo with Unset Printing Coercions)
• Set Printing All (undo with Unset Printing All)

These commands can also be used in the middle of a proof, to elaborate the current goal and context.

The Locate command

Finding notations

When faced with unknown notation, use Locate with a string containing one of its symbols to see its possible interpretations.

Finding identifiers

When used with an identifier, the command Locate prints the full path to every value in scope with the same name. This is useful to troubleshoot problems due to variable shadowing.

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. The Open Scope declaration is needed to be able to use the notations in match patterns.

In a traditional functional programming language like OCaml or Haskell we could add the WHILE case as follows:

        Fixpoint ceval_fun (st : state) (c : com) : state :=
          match c with
            ...
            | WHILE b DO c END =>
                if (beval st b)
                  then ceval_fun st (c ;; WHILE b DO c END)
                  else st
          end.

Coq doesn't accept such a definition ("Error: Cannot guess decreasing argument of fix") because the function we want to define is not guaranteed to terminate. Indeed, it doesn't always terminate: for example, the full version of the ceval_fun function applied to the loop program above would never terminate. Since Coq is not just a functional programming language but also a consistent logic, any potentially non-terminating function needs to be rejected. Here is an (invalid!) program showing what would go wrong if Coq allowed non-terminating recursive functions:

         Fixpoint loop_false (n : nat) : False := loop_false n.

That is, propositions like False would become provable (loop_false 0 would be a proof of False), which would be a disaster for Coq's logical consistency. Thus, because it doesn't terminate on all inputs, of ceval_fun cannot be written in Coq -- at least not without additional tricks and workarounds.

Evaluation as a Relation

Here's another 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. This is an important change. Besides freeing us from awkward workarounds, it gives us a lot more flexibility in the definition. For example, if we add nondeterministic features like any to the language, we want the definition of evaluation to be nondeterministic -- i.e., not only will it not be total, it will not even be a function! We'll use the notation st =[ c ]=> st' for the ceval relation: st =[ c ]=> 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)
                           st =[ SKIP ]=> st

                           aeval st a1 = n
                   --------------------------------                     (E_Ass)
                   st =[ x := a1 ]=> (x !-> n ; st)

                           st  =[ c1 ]=> st'
                           st' =[ c2 ]=> st''
                         ---------------------                            (E_Seq)
                         st =[ c1;;c2 ]=> st''

                          beval st b1 = true
                           st =[ c1 ]=> st'
                ---------------------------------------                (E_IfTrue)
                st =[ TEST b1 THEN c1 ELSE c2 FI ]=> st'

                         beval st b1 = false
                           st =[ c2 ]=> st'
                ---------------------------------------               (E_IfFalse)
                st =[ TEST b1 THEN c1 ELSE c2 FI ]=> st'

                         beval st b = false
                    -----------------------------                  (E_WhileFalse)
                    st =[ WHILE b DO c END ]=> st

                          beval st b = true
                           st =[ c ]=> st'
                  st' =[ WHILE b DO c END ]=> st''
                  --------------------------------                  (E_WhileTrue)
                  st  =[ WHILE b DO c END ]=> st''

Here is the formal definition. Make sure you understand how it corresponds to the inference rules.

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. This will also significantly impact the structure of proofs about evaluation.

Determinism of Evaluation

Changing from a computational to a relational definition of evaluation is a good move because it frees us from the artificial requirement that evaluation should be a total function. But it also raises a question: Is the second definition of evaluation really a partial function? Or is it possible that, beginning from the same state st, we could evaluate some command c in different ways to reach two different output states st' and st''? In fact, this cannot happen: ceval is a partial function. (We will prove this in class!).