Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
sav08:proving_correctness_of_some_small_examples [2008/02/17 19:04] vkuncak |
sav08:proving_correctness_of_some_small_examples [2010/02/23 12:31] vkuncak |
||
---|---|---|---|
Line 1: | Line 1: | ||
====== Proving Correctness of Some Small Examples ====== | ====== Proving Correctness of Some Small Examples ====== | ||
- | In this demo we go through several examples and prove them correct using the [[Jahob system]]. | + | In this demo we go through several examples and prove them correct using the [[:Jahob system]]. |
==== A Recursive Function ==== | ==== A Recursive Function ==== | ||
Line 27: | Line 27: | ||
* [[Proof of first lecture01 example]] | * [[Proof of first lecture01 example]] | ||
- | === An Iterative Example | + | === An Iterative Example === |
<code> | <code> | ||
Line 46: | Line 46: | ||
* [[Notion of inductive loop invariant]] | * [[Notion of inductive loop invariant]] | ||
* What is and is not inductive loop invariant in this example | * What is and is not inductive loop invariant in this example | ||
+ | |||
+ | A verification condition formula for preserving an invariant: | ||
+ | |||
+ | ++++| | ||
+ | \[ | ||
+ | r = i * x \land i=i+1 \land r' = r + x \rightarrow r' = i' * x | ||
+ | \] | ||
+ | ++++ | ||
+ | * we will see methods to prove such invariants | ||
=== Transforming iterative version === | === Transforming iterative version === | ||
- | === Summary === | + | * changing initial condition |
+ | |||
+ | === Summary of these Small Examples === | ||
{{sav08:integerdemo.java.txt|Examples of Functions with Specifications}} | {{sav08:integerdemo.java.txt|Examples of Functions with Specifications}} | ||
- | For homework, you will have another such example. | + | === Some other Examples done in Jahob === |
+ | |||
+ | * http://javaverification.org/ | ||
+ | |||
+ | === Another System === | ||
+ | |||
+ | * [[http://research.microsoft.com/en-us/projects/vcc|VCC: A Verifier for Concurrent C]] | ||