9 - Advanced Techniques

Summary

In this chapter we examine some advanced techniques for proving properties of Spark programs. Although the approaches we describe here will not be needed for the development of many programs, you may find them useful or even necessary for handling larger, realistic applications.

Ghost Entities

Ghost entities make it easier to express assertions about a program. The essential property of ghost entities is that they have no effect on the execution behavior of a valid program. Thus, a valid program that includes ghost entities will execute the same with or without them.

9.1.1 Ghost Functions

In applications where you are trying to prove strong statements about the correctness of your programs, the expressions you need to write in assertions become very complex. To help manage that complexity, it is desirable to factor certain subexpressions into separate functions, both to document them and to facilitate reuse of them in multiple assertions.

Functions that you create for verification purposes only are called ghost functions. The essential property of ghost functions is that they do not normally play any role in the execution of your program. Ghost functions may only be called from assertions such as preconditions, postconditions, and loop invariants. They may not be called from the ordinary, non-assertive portions of your program.

As an example consider the specification of a package Sorted_Arrays that contains subprograms for creating and processing sorted arrays of integers:

Notice that the postcondition of Sort and the precondition of Binary_Search both use the same quantified expression to assert that the array being processed is sorted. Although the expression is not exceptionally unwieldy in this case, it is still somewhat obscure and hard to read. Having it duplicated on two subprograms also hurts the package's maintainability.

Our second version of this specification introduces a ghost function to abstract and simplify the pre- and postconditions on the other subprograms. We use the Boolean aspect Ghost to indicate that the function Is_Sorted is included only for verification purposes.

The postcondition on Sort and the precondition on Binary_Search use the Is_Sorted function rather than the lengthier quantified predicates. They are now clearer and easier to maintain.

The function Is_Sorted is decorated with a postcondition that explains its effect.