Entries:
Comments:
Posts:

Loading User Information from Channel 9

Something went wrong getting user information from Channel 9

Latest Achievement:

Loading User Information from MSDN

Something went wrong getting user information from MSDN

Visual Studio Achievements

Latest Achievement:

Loading Visual Studio Achievements

Something went wrong getting the Visual Studio Achievements

Rustan Leino

Rustan Leino leino Rustan Leino

Niner since 2007

Rustan Leino is a designer of programming languages and program verification tools. He is a Principal Researcher at Microsoft Research.
  • The Verification Corner - Loop Termination

    @iman.saleh:  We just recently released the Visual Studio 2010 mode for Dafny, see http://boogie.codeplex.com, click "How to install and build the sources" and then scroll down to "Visual Studio integration".

      Rustan

  • The Verification Corner: Loop Invariants

    No, the Spec# verifier ignores issues of overflow.  Checks for arithmetic overflow can be added to the verifier, at the cost of additional specification overhead for users.  In some other languages we use for verification, like Dafny, the integers are unbounded, so there will never be any overflows.

  • The Verification Corner - Loop Termination

    In your particular examples, there is minimum decrease.  In the first example (with x = x/2), every iteration decreases x by at least 0.5 (since the loop body is entered only if x>1).  In the second example, there is not a single constant that will work for every run of the program.  However, the minimum decrease can be computed from the values that x and n have just before the loop begins.  For example, let X denote the initial value of x and suppose the initial value of n is 1; then, it will take about e^X iterations before the 1/n terms add up to X, where e is the base of the natural logarithm and I'm using ^ to denote exponentiation; so, each iteration will decrease x by at least 1 / e^X.

     

    What you are getting at, though, is correct, namely that what is necessary and sufficient for the loop to terminate is that the successive iterations can be mapped to strictly decreasing values in some well-founded order.

  • The Verification Corner: Loop Invariants

    In Tony Hoare's classic 1969 paper, the triples were written P{S}Q.  Sometime later (I'm not sure when), the common notation switched to {P}S{Q}.  I think (but I'm not certain) that the reason for the switch was to make the assertions P and Q look as if they were comments, like in the syntax of the Pascal programming language.

  • The Verification Corner: Loop Invariants

    I suppose you're referring to the mention of "it is December" in the video, while it was actually released here in January.  But you can make wishes any time of year. Smiley

  • The Verification Corner: Loop Invariants

    Thanks!

     

    CodeContracts could in principle be used to do the same thing.  However, we have more engineering to do for CodeContracts to support this particular example.  While CodeContracts does support pre- and postconditions, it has no direct support for writing loop invariants, which play a central role in this episode of Verification Corner.  As a more technical point, the static-checking tools for CodeContracts don't have the support for non-linear arithmetic (that is, multiplication of a variable with itself or with another variable) that is required to reason about the computation of cubes.

     

    For now, the best you can do in CodeContracts is to use an Assert just inside the loop body to express the loop invariant and then rely on run-time checking.  Still, you may find that doing that improves your ability to reason about what's going on in the loop.