#|
Copyright (C) 1994 by Robert S. Boyer and J Strother Moore.  All Rights
Reserved.
This script is hereby placed in the public domain, and therefore unlimited
editing and redistribution is permitted.
NO WARRANTY
Robert S. Boyer and J Strother Moore PROVIDE ABSOLUTELY NO WARRANTY.  THE
EVENT SCRIPT IS PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESS
OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, ANY IMPLIED WARRANTIES OF
MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.  THE ENTIRE RISK AS TO
THE QUALITY AND PERFORMANCE OF THE SCRIPT IS WITH YOU.  SHOULD THE SCRIPT
PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR OR
CORRECTION.
IN NO EVENT WILL Robert S. Boyer or J Strother Moore BE LIABLE TO YOU FOR ANY
DAMAGES, ANY LOST PROFITS, LOST MONIES, OR OTHER SPECIAL, INCIDENTAL OR
CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THIS SCRIPT
(INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE
OR LOSSES SUSTAINED BY THIRD PARTIES), EVEN IF YOU HAVE ADVISED US OF THE
POSSIBILITY OF SUCH DAMAGES, OR FOR ANY CLAIM BY ANY OTHER PARTY.
|#
; This is the list of verification conditions for a FORTRAN square
; root program.  For the details of the algorithm, see the comment at
; the end of the file.  Boyer and Moore.
; This list of events has been further edited, for processing by
; DO-FILE, by (1) inserting the following NOTE-LIB, (2) commenting out
; each FORTRAN-COMMENT and following the comment with the
; corresponding macroexpansion, and (3) by commenting out each
; (COMMENT ...).

Event: Start with the library "fortran" using the compiled version.

; (FORTRAN-COMMENT FORTRAN)

Axiom: fortran t Event: Introduce the function symbol i$0 of 0 arguments.

Event: Introduce the function symbol isqrt$1 of 0 arguments.

Event: Introduce the function symbol isqrt$2 of 0 arguments.

Definition: sq (i) = (i ∗ i)

Axiom: input-conditions

 '*1*true

Definition: global-hyps = ((i$0 ∈ N)

∧ ((i$0 < least-inexpressible-positive-integer) ∧ znumberp (i$0)))

Theorem: plus-1 (1 + x) = (1 + x)

Theorem: difference-2 ((1 + (1 + x)) − 2) = fix (x)

Theorem: quotient-by-2 ((a ÷ 2) + (a ÷ 2)) ≮ (a − 1)

Theorem: main-trick sq (1 + ((j + k) ÷ 2)) ≮ ((j ∗ k) + j )

Theorem: lessp-remainder2 ((x mod y) < y) = (y ≄ 0)

Theorem: remainder-quotient-elim ((y ≄ 0) ∧ (x ∈ N)) → (((x mod y) + (y ∗ (x ÷ y))) = x)

Theorem: sq-add1-non-zero sq (1 + x) ≠ 0

Event: Disable sq.

Theorem: main (j ≄ 0) → (i < sq (1 + ((j + (i ÷ j )) ÷ 2)))

Event: Enable sq.

Theorem: lessp-times-cancellation-restated-for-linear (i ≮ j ) → ((a ∗ i) ≮ (a ∗ j )) Theorem: multiply-thru-by-divisor (a < (b ∗ c)) → (((a ÷ b) < c) = t) Theorem: times-greaterp-zero ((x ≄ 0) ∧ (y ≄ 0)) → (0 < (x ∗ y)) Theorem: quotient-shrinks i ≮ (i ÷ j ) Theorem: quotient-shrinks-fast i ≮ (2 ∗ (i ÷ 2)) Theorem: quotient-by-1 (i ÷ 1) = fix (i)

; (FORTRAN-COMMENT INPUT)

Axiom: input t

; (FORTRAN-COMMENT LOGICAL-IF-T)

Axiom: logical-if-t t Theorem: stop (¬ zlessp (i$0, '0)) ∨ (¬ global-hyps)

#| (COMMENT INPUT T) |#

Event: Undo back through the event named ‘logical-if-t’.

; (FORTRAN-COMMENT LOGICAL-IF-F)

Axiom: logical-if-f t

; (FORTRAN-COMMENT LOGICAL-IF-T)

Axiom: logical-if-t t Theorem: input-cond-of-zquotient (zgreaterp (i$0, '1) ∧ global-hyps) → ((¬ zeqp ('2, '0)) ∧ expressible-znumberp (zquotient (i$0, '2)))

#| (COMMENT INPUT F T) |#

Axiom: assignment isqrt$1 = zquotient (i$0, '2)

Theorem: lp (zgreaterp (i$0, '1) ∧ global-hyps) → ((('0 < isqrt$1)

∧ ((i$0 ≮ ('2 ∗ isqrt$1))

∧ ((isqrt$1 ∈ N) ∧ (i$0 < sq (1 + isqrt$1))))) ∧ lex (cons (isqrt$1, 'nil), cons (i$0, 'nil)))

#| (COMMENT INPUT F T) |#

Event: Undo back through the event named ‘logical-if-t’.

; (FORTRAN-COMMENT LOGICAL-IF-F1)

Axiom: logical-if-f1 t

Axiom: assignment isqrt$1 = i$0

Theorem: output ((¬ zgreaterp (i$0, '1)) ∧ global-hyps) → (znumberp (isqrt$1)

∧ (zgreatereqp (isqrt$1, '0) ∧ ((i$0 ≮ sq (isqrt$1))

∧ (i$0 < sq ('1 + isqrt$1)))))

#| (COMMENT INPUT F F) |#

Event: Undo back through the event named ‘input’.

Axiom: paths-from-lp

 '*1*true

Definition: path-hyps = (global-hyps

∧ (('0 < isqrt$1)

∧ ((i$0 ≮ ('2 ∗ isqrt$1))

∧ ((isqrt$1 ∈ N) ∧ (i$0 < sq (1 + isqrt$1))))))

Theorem: definedness path-hyps → znumberp (isqrt$1)

#| (COMMENT LP) |#

Theorem: input-cond-of-zquotient path-hyps → ((¬ zeqp (isqrt$1, '0))

∧ expressible-znumberp (zquotient (i$0, isqrt$1)))

#| (COMMENT LP) |#
; (FORTRAN-COMMENT LOGICAL-IF-T)

Axiom: logical-if-t t

Theorem: output1 (zgreatereqp (zquotient (i$0, isqrt$1), isqrt$1) ∧ path-hyps) → (znumberp (isqrt$1)

∧ (zgreatereqp (isqrt$1, '0) ∧ ((i$0 ≮ sq (isqrt$1))

∧ (i$0 < sq ('1 + isqrt$1)))))

#| (COMMENT LP T) |#

Event: Undo back through the event named ‘logical-if-t’.

; (FORTRAN-COMMENT LOGICAL-IF-F2)

Axiom: logical-if-f2 t

Theorem: input-cond-of-zquotient1 ((¬ zgreatereqp (zquotient (i$0, isqrt$1), isqrt$1)) ∧ path-hyps) → ((¬ zeqp (isqrt$1, '0))

∧ expressible-znumberp (zquotient (i$0, isqrt$1)))

#| (COMMENT LP F) |#

Theorem: input-cond-of-zplus ((¬ zgreatereqp (zquotient (i$0, isqrt$1), isqrt$1)) ∧ path-hyps) → expressible-znumberp (zplus (isqrt$1, zquotient (i$0, isqrt$1)))

#| (COMMENT LP F) |#

Theorem: input-cond-of-zquotient2 ((¬ zgreatereqp (zquotient (i$0, isqrt$1), isqrt$1)) ∧ path-hyps) → ((¬ zeqp ('2, '0))

∧ expressible-znumberp (zquotient (zplus (isqrt$1,

zquotient (i$0, isqrt$1)), '2)))

#| (COMMENT LP F) |#

Axiom: assignment1 isqrt$2 = zquotient (zplus (isqrt$1, zquotient (i$0, isqrt$1)), '2)

Event: Disable sq.

Theorem: lp1 ((¬ zgreatereqp (zquotient (i$0, isqrt$1), isqrt$1)) ∧ path-hyps) → ((('0 < isqrt$2)

∧ ((i$0 ≮ ('2 ∗ isqrt$2))

∧ ((isqrt$2 ∈ N) ∧ (i$0 < sq (1 + isqrt$2))))) ∧ lex (cons (isqrt$2, 'nil), cons (isqrt$1, 'nil)))

#| (COMMENT LP F) |#

Event: Undo back through the event named ‘paths-from-lp’.

Event: Undo back through the event named ‘fortran’.

#|

The correctness of the program depends upon the following events:

@BEGIN(GROUP)
@BEGIN(VERBATIM)
        Definition.
        (SQ I)
           =
        (TIMES I I)
@END(VERBATIM)
@END(GROUP)
@BEGIN(GROUP)
@BEGIN(VERBATIM)
        (FORTRAN-COMMENT ISQRT-STUFF)
@END(VERBATIM)
@END(GROUP)

Specification for routine ISQRT
The input assertion:
        (AND (NUMBERP (I STATE))
             (LESSP (I STATE)
                    (LEAST-INEXPRESSIBLE-POSITIVE-INTEGER)))

The output assertion:
        (AND (ZGREATEREQP ANS 0)
             (NOT (LESSP (I STATE) (SQ ANS)))
             (LESSP (I STATE) (SQ (PLUS 1 ANS))))

      END
      INTEGER FUNCTION ISQRT(I)
      INTEGER I
C     CALCULATE THE SQUARE ROOT OF I USING THE NEWTON METHOD.
      IF ((I .LT. 0)) STOP
      IF ((I .GT. 1)) GOTO 100
      ISQRT = I
      RETURN
C     ISQRT TAKES ON INCREASINGLY SMALLER VALUES AND CONVERGES TO THE SQ
C     UARE ROOT OF I. THE FIRST APPROXIMATION IS ONE HALF I, WHICH IS NO
C     T LESS THAN THE SQUARE ROOT OF I WHEN 1 IS LESS THAN I.
100   ISQRT = (I / 2)
200   CONTINUE
C     ASSERTION LP
      IF (((I / ISQRT) .GE. ISQRT)) RETURN
      ISQRT = ((ISQRT + (I / ISQRT)) / 2)
C     XXX SQ-REWRITE-OFF-AGAIN
      GOTO 200
      END

The XXX at ISQRT-STUFF.
@BEGIN(GROUP)
@BEGIN(VERBATIM)
        Theorem.  PLUS-1 (rewrite):
        (EQUAL (PLUS 1 X) (ADD1 X))
@END(VERBATIM)
@END(GROUP)
@BEGIN(GROUP)
@BEGIN(VERBATIM)
        Theorem.  DIFFERENCE-2 (rewrite):
        (EQUAL (DIFFERENCE (ADD1 (ADD1 X)) 2)
               (FIX X))
@END(VERBATIM)
@END(GROUP)
@BEGIN(GROUP)
@BEGIN(VERBATIM)
        Theorem.  QUOTIENT-BY-2 (rewrite):
        (NOT (LESSP (PLUS (QUOTIENT A 2) (QUOTIENT A 2))
                    (SUB1 A)))
@END(VERBATIM)

@END(GROUP)
@BEGIN(GROUP)
@BEGIN(VERBATIM)
        Theorem.  MAIN-TRICK (rewrite):
        (NOT (LESSP (SQ (ADD1 (QUOTIENT (PLUS J K) 2)))
                    (PLUS (TIMES J K) J)))
        Hint:  Induct as for (LESSP J K).
@END(VERBATIM)
@END(GROUP)
@BEGIN(GROUP)
@BEGIN(VERBATIM)
        Theorem.  LESSP-REMAINDER2 (rewrite and generalize):
        (EQUAL (LESSP (REMAINDER X Y) Y)
               (NOT (ZEROP Y)))
@END(VERBATIM)
@END(GROUP)
@BEGIN(GROUP)
@BEGIN(VERBATIM)
        Theorem.  REMAINDER-QUOTIENT-ELIM (elimination):
        (IMPLIES (AND (NOT (ZEROP Y)) (NUMBERP X))
                 (EQUAL (PLUS (REMAINDER X Y)
                              (TIMES Y (QUOTIENT X Y)))
                        X))
@END(VERBATIM)
@END(GROUP)
@BEGIN(GROUP)
@BEGIN(VERBATIM)
        Theorem.  SQ-ADD1-NON-ZERO (rewrite):
        (NOT (EQUAL (SQ (ADD1 X)) 0))
@END(VERBATIM)
@END(GROUP)
@BEGIN(GROUP)
@BEGIN(VERBATIM)
        Enable SQ.
@END(VERBATIM)
@END(GROUP)
@BEGIN(GROUP)
@BEGIN(VERBATIM)

        Theorem.  MAIN (rewrite):
        (IMPLIES (NOT (ZEROP J))
                 (LESSP I
                        (SQ (ADD1 (QUOTIENT (PLUS J (QUOTIENT I J))
                                            2)))))
@END(VERBATIM)
@END(GROUP)
@BEGIN(GROUP)
@BEGIN(VERBATIM)
        Disable SQ.
@END(VERBATIM)
@END(GROUP)
@BEGIN(GROUP)
@BEGIN(VERBATIM)
        Theorem.  LESSP-TIMES-CANCELLATION-RESTATED-FOR-LINEAR (rewrite):
        (IMPLIES (NOT (LESSP I J))
                 (NOT (LESSP (TIMES A I) (TIMES A J))))
@END(VERBATIM)
@END(GROUP)
@BEGIN(GROUP)
@BEGIN(VERBATIM)
        Theorem.  MULTIPLY-THRU-BY-DIVISOR (rewrite):
        (IMPLIES (LESSP A (TIMES B C))
                 (EQUAL (LESSP (QUOTIENT A B) C) T))
@END(VERBATIM)
@END(GROUP)
@BEGIN(GROUP)
@BEGIN(VERBATIM)
        Theorem.  TIMES-GREATERP-ZERO (rewrite):
        (IMPLIES (AND (NOT (ZEROP X)) (NOT (ZEROP Y)))
                 (LESSP 0 (TIMES X Y)))
@END(VERBATIM)
@END(GROUP)
@BEGIN(GROUP)
@BEGIN(VERBATIM)
        Theorem.  QUOTIENT-SHRINKS (rewrite):
        (NOT (LESSP I (QUOTIENT I J)))
@END(VERBATIM)
@END(GROUP)

@BEGIN(GROUP)
@BEGIN(VERBATIM)
        Theorem.  QUOTIENT-SHRINKS-FAST (rewrite):
        (NOT (LESSP I (TIMES 2 (QUOTIENT I 2))))
@END(VERBATIM)
@END(GROUP)
@BEGIN(GROUP)
@BEGIN(VERBATIM)
        Theorem.  QUOTIENT-BY-1 (rewrite):
        (EQUAL (QUOTIENT I 1) (FIX I))
@END(VERBATIM)
@END(GROUP)

Hints for routine ISQRT

The input clock:
        (LIST (I (START)))
The invariant and clock named LP.
        (AND (LESSP 0 (ISQRT STATE))
             (NOT (LESSP (I STATE)
                         (TIMES 2 (ISQRT STATE))))
             (NUMBERP (ISQRT STATE))
             (LESSP (I STATE)
                    (SQ (ADD1 (ISQRT STATE)))))
        (LIST (ISQRT STATE))
The XXX named SQ-REWRITE-OFF-AGAIN:
@BEGIN(GROUP)
@BEGIN(VERBATIM)
        Enable SQ.
@END(VERBATIM)
@END(GROUP)
|#

Index

assignment, 4 assignment1, 6

definedness, 5 difference-2, 2

expressible-znumberp, 4–6

fortran, 1

global-hyps, 2–5

i$0, 2–6 input, 3 input-cond-of-zplus, 6 input-cond-of-zquotient, 4, 5 input-cond-of-zquotient1, 5 input-cond-of-zquotient2, 6 input-conditions, 2 isqrt$1, 2, 4–6 isqrt$2, 2, 6

least-inexpressible-positive-inte

ger, 2 lessp-remainder2, 2 lessp-times-cancellation-restate

d-for-linear, 3 lex, 4, 6 logical-if-f, 3 logical-if-f1, 4 logical-if-f2, 5 logical-if-t, 3, 5 lp, 4 lp1, 6

main, 2 main-trick, 2 multiply-thru-by-divisor, 3

output, 4 output1, 5

path-hyps, 5, 6 paths-from-lp, 4 plus-1, 2

quotient-by-1, 3 quotient-by-2, 2 quotient-shrinks, 3 quotient-shrinks-fast, 3

remainder-quotient-elim, 2

sq, 2, 4–6

sq-add1-non-zero, 2

stop, 3

times-greaterp-zero, 3

zeqp, 4–6

zgreatereqp, 4–6 zgreaterp, 4 zlessp, 3 znumberp, 2, 4, 5 zplus, 6 zquotient, 4–6