Transcript Chapter 18c - McGraw Hill Higher Education

Programming Languages
2nd edition
Tucker and Noonan
Chapter 18
Program Correctness
To treat programming scientifically, it must be possible to specify the
required properties of programs precisely. Formality is certainly
not an end in itself. The importance of formal specifications must
ultimately rest in their utility - in whether or not they are used to
improve the quality of software or to reduce the cost of
producing and maintaining software.
J. Horning
Copyright © 2006 The McGraw-Hill Companies, Inc.
Contents
18.1 Axiomatic Semantics
18.2 Formal Methods Tools: JML
18.2.1 JML Exception Handling
18.3 Correctness of Object-Oriented Programs
18.3.1 Design by Contract
18.3.2 The Class Invariant
18.3.3 Correctness of a Queue Application
18.3.4 Final Observations
18.4 Correctness of Functional Programs
Copyright © 2006 The McGraw-Hill Companies, Inc.
Review JML
JML Expression
Meaning
requires p;
ensures p;
signals (E e) p;
p is a precondition for the call
p is a postcondition for the call
when exception e is raised by the call, p is
a postcondition
loop_invariant p;
p is a loop invariant
invariant p;
p is a class invariant
\result == e;
e is the result returned by the call
\old v
the value of v at entry to the call
(\product int x ; p(x); e(x))
the product of e(x) for all x that satisfy p(x)
(\sum int x ; p(x); e(x)) the sum of e(x) for all x that satisfy p(x)
p ==> q
pq
Copyright © 2006 The McGraw-Hill Companies, Inc.
18.3.1 Design by Contract
Obligations
Benefits
Client
(caller)
Arguments for each
The call delivers correct
method/constructor call result, and the object keeps
must satisfy its requires its integrity
clause
Class
(object)
Result for each call must Called method/constructor
satisfy both its ensures doesn’t need extra code to
clause and INV
check argument validity
Note: Blame can be assigned if obligations aren’t met!
Copyright © 2006 The McGraw-Hill Companies, Inc.
The contract for a Stack class
Obligations
Client
(caller)
Class
(object)
Benefits
Arguments for every call to Every call to
Stack(), push,
Stack(), push,
pop, top, isEmpty, and
pop, top, isEmpty,
and size
size
delivers a correct result,
must satisfy its requires
clause
and the object keeps its
integrity
Result from each call must
No method or
constructor needs extra
satisfy both its ensures
clause and the class invariant code to check argument
n == size()
validity
Copyright © 2006 The McGraw-Hill Companies, Inc.
18.3.2 The Class Invariant
A class C is formally specified if:
1. Every constructor and public method M in the class has
preconditions and postconditions, and
2. C has a special predicate called its class invariant INV
which, for every object o in C, argument x and call
o.M(x), must be true both before and after the call.
Note: During a call, INV may temporarily become false.
Why are we doing this???
i) Formal specifications provide a foundation for rigorous OO
system design (e.g., “design by contract”).
ii) They enable static and dynamic assertion checking of an
entire OO system.
iii) They enable formal correctness proof of an OO system.
Copyright © 2006 The McGraw-Hill Companies, Inc.
18.3.3 Correctness of a Stack Application
public class Stack {
private class Node { }
private Node theStack = null;
private int n = 0;
public void push(int v) { }
public int pop( ) {}
public int top() {}
public boolean isEmpty() {}
public int size() {}
}
Copyright © 2006 The McGraw-Hill Companies, Inc.
public constructor
C = Stack()
“helper” class
state variables
help define INV
public
methods M
Adding Class-Level Specifications
JML model variable
/*@ public model Node S;
private represents S <- theStack;
public invariant S == null || n == this.size();
@*/
class invariant INV
more JML
private /*@ spec_public @*/ Node theStack = null;
private /*@ spec_public @*/ int n = 0;
Notes: 1) JML model variables allow a specification to
distance itself from the class’s implementation details.
2) spec_public allows JML specifications to treat a Java
variable as public without forcing the code to do the same.
Copyright © 2006 The McGraw-Hill Companies, Inc.
Adding Method Specifications
/*@ requires n > 0;
ensures \result==\old(S).val &&
S==\old(S).next && n==\old(n)-1;
@*/
public /*@ pure @*/ int pop( ) {
int result = theStack.val;
theStack = theStack.next;
n = n-1;
return result;
}
Notes: 1) \old denotes the value of S at entry to pop.
2) The ensures clause specifies that pop removes
the top element and returns it.
Copyright © 2006 The McGraw-Hill Companies, Inc.
Similar specifications for push
//@ ensures S.next==\old(S) && S.val==v;
public /*@ pure @*/ void push(int v) {
theStack = new Node(v, theStack);
n = n+1;
}
Copyright © 2006 The McGraw-Hill Companies, Inc.
“Pure” methods
/*@ requires n > 0;
ensures \result==S.val && S == \old(S);
@*/
public /*@ pure @*/ int top() {
return theStack.val;
}
Note: A method is pure if:
1) it has no non-local side effects, and
2) it is provably non-looping.
Copyright © 2006 The McGraw-Hill Companies, Inc.
Test driving MyStack class
public class myStackTest {
public static void main(String[] args) {
MyStack s = new MyStack();
int val;
for (int i=0; i<args.length; i++)
s.push(Integer.parseInt(args[i]));
System.out.println("Stack size = " + s.size());
System.out.print("Stack contents =");
for (int i=1; i<=n; i++) {
System.out.print(" " + s.top( ));
s.pop( );
}
System.out.println( );
System.out.println("Is Stack empty? " + s.isEmpty( ));
}
}
Copyright © 2006 The McGraw-Hill Companies, Inc.
Contract test 1: normal run
% jmlrac myStackTest 4 5 6
Stack size = 3
Stack contents = 6 5 4
Is Stack empty? true
%
Copyright © 2006 The McGraw-Hill Companies, Inc.
Contract test 2: postcondition violation
Exception in thread "main"
org.jmlspecs.jmlrac.runtime.JMLNormalPostconditionError:
by method MyStack.top regarding specifications at
File "MyStack.java", line 31, character 26 when
'\old(S)' is MyStack$Node@5ff48b
'\result' is 5
'this' is MyStack@affc70
at MyStack.checkPost$top$MyStack(MyStack.java:999)
at MyStack.top(MyStack.java:1078)
at myStackTest.main(MyStackTest.java:15)
Note: blame is with the callee MyStack, since a postcondition
has been violated.
Copyright © 2006 The McGraw-Hill Companies, Inc.
Contract test 3: invariant error
Stack size = 3
Stack contents = 6
Exception in thread "main"
org.jmlspecs.jmlrac.runtime.JMLInvariantError:
by method MyStack.pop@post<File "MyStack.java", line 16,
character 17>
regarding specifications at
File "MyStack.java", line 11, character 30 when
'this' is MyStack@9664a1
at MyStack.checkInv$instance$MyStack(MyStack.java:102)
at MyStack.pop(MyStack.java:525)
at myStackTest.main(MyStackTest.java:21)
Note: blame is again with the callee MyStack, since an invariant
has been violated.
Copyright © 2006 The McGraw-Hill Companies, Inc.
Contract test 4: precondition violation
Stack size = 3
Stack contents = 6 5 4
Is Stack empty? true
Exception in thread "main"
org.jmlspecs.jmlrac.runtime.JMLEntryPreconditionError:
by method MyStack.pop regarding specifications at
File "MyStack.java", line 16, character 21 when
'this' is MyStack@9664a1
at MyStack.checkPre$pop$MyStack(MyStack.java:330)
at MyStack.pop(MyStack.java:479)
at myStackTest.main(MyStacktest.java:24)
Note: blame is with the caller MyQueueTest, since a precondition
has been violated.
Copyright © 2006 The McGraw-Hill Companies, Inc.
Class and System Correctness
So far, we have only done testing; what about formal verification?
1. A class C is (formally) correct if:
a. It is formally specified, and
b. For every object o and every constructor and public
method M in the class, the Hoare triple
{P  INV} o.M(x) {Q  INV }
is valid for every argument x.
2. A system is correct if all its classes are correct.

Copyright © 2006 The McGraw-Hill Companies, Inc.
Correctness of pop()
1
2
3
4
/*@ requires n > 0;
ensures \result==\old(S).val &&
S==\old(S).next && n==\old(n)-1;
@*/
public /*@ pure @*/ int pop( ) {
int result = theStack.val;
theStack = theStack.next;
n = n-1;
return result;
}
INV: n = size()
P  INV: n > 0  n = size()
Q  INV: result = old(S).val 
S = old(S).next 
n = size()
Copyright © 2006 The McGraw-Hill Companies, Inc.
A “loose” correctness proof for pop()
1. “Loose” because
a. We assume the validity of size(), and
b. We omit some details.
2. The assignments in pop(), together with P  INV,
ensure the validity of Q INV :
a. Steps 1 and 4 establish \result = \old(S).val
b. Step 2 establishes S = \old(S).next
c. Step 3 and our assumptionestablish n = size():
I.e., n =
\old(n) -1
and size() = \old(size()) -1
So, n = size(), since \old(n) = \old(size())
Copyright © 2006 The McGraw-Hill Companies, Inc.
18.3.4 Final Observations
1. Formal verification:
a. is an enormous task for large programs.
b. only proves that specifications and code agree.
c. only proves partial correctness (assumes termination).
2. Tools exist for:
a. Statically checking certain run-time properties of Java
programs (ESC/Java2)
b. formally verifying Ada programs (Spark)
3. Tools are being developed to help with formal verification
of Java programs (Diacron, LOOP)
4. What is the cost/benefit of formal methods?
Copyright © 2006 The McGraw-Hill Companies, Inc.