Верификация программы

Полная программа

В полной программе необходимо учесть случай E = 0 для нулей и ненормализованных малых значений. Для E = 2^w – 1 (случай бесконечностей и NaN) результат функции floor не определен.

if (E = 0) { if (S= 0) y = 0 else y = -1 }

else floor(S, E, T: y)

Напомним, что решение floor(-0) = -1 не является очевидным. Подстановка определений предикатов floor и floor1 на место вызовов дает следующую программу:

if (E = 0) { if (S= 0) y = 0 else y = -1 } (5)

else { int d = E – bias – p + 1; nat z = 2^(p-1) or T;

if (S = 0) { if (d >= 0) y = z << d

elseif (–d > p) y = 0 else y = z >> (-d)

} elseif (d >= 0) y = - (z << d)

elseif (–d > p) y = - 1

elseif (z & ((2^p – 1) >> (p + d)) = 0) y = - (z >> (-d))

else y = - (z >> (-d)) – 1

}

Рассмотрим генерацию формул корректности программы (1, 2) и процесс автоматического доказательства истинности сгенерированных формул корректности. Представим теорию main, содержащую образ глобальных описаний программы.

main: THEORYBEGINIMPORTING flbias: nat %constantsp: posnatw: {i: nat | i >= 2}m: nat = p + wnbit: TYPE = {n: nat | n = 0 OR n = 1}intm: TYPE = {x: int | - 2 ^ (m - 1) < x & x < 2 ^ (m - 1)}natp: TYPE = {i: nat | i < 2 ^ (p - 1)}nate: TYPE = {e: nat | e < bias + m - 2}T: VAR natpy: VAR intmS: VAR nbitE: VAR nated, z: VAR nat

val(S, E, T) = (-1)^S * 2^(E - bias) * (1 + 2^(1 - p) * T)

val1(S, d, z) = (-1)^S * 2^d * z

END main

Представим начальную часть теории floor_val для определения предиката floor.

floor(bit S, nat E, T: intm y) pre T < 2^(p-1) & E – bias < m – 2 (1)

{ floor1(S, E – bias – p + 1, 2^(p-1) + T: y) } post flp(val(S, E, T), y);

floor_val: THEORYBEGINIMPORTING main, floor1T: VAR natpy: VAR intmS: VAR nbitE: VAR nateP_floor(E, T): bool = T < 2^(p-1) & E – bias < m – 2Q_floor(S, E, T, y): bool = flp(val(S, E, T), y)satisfy_spec: LEMMA P_floor(E, T) IMPLIES EXISTS y: Q_floor(S, E, T, y)

Целью является доказательство истинности правила:

P_floor(E, T) & Q_floor(S, E, T, y)├ LS(floor1(S, E – bias – p + 1, 2^(p-1) + T))

В соответствии с правилом FB1 генерируется лемма:

FB1: LEMMA

P_floor(E, T) & Q_floor(S, E, T, y) IMPLIES

P_floor1(E – bias – p + 1, 2^(p-1) + T) &

Q_floor1(S, E – bias – p + 1, 2^(p-1) + T, y).

Представим начальную часть теории floor1.

floor1: THEORYBEGINIMPORTING main

y: VAR intm

E, T, d, z: VAR natS: VAR nbitP_floor1(d, z): bool = z >= 2^(p-1) & z < 2^p & d < wQ_floor1(S, d, z, y): bool = flp(val1(S, d, z), y)satisfy_spec: LEMMA P_floor1(d, z) IMPLIES EXISTS r: Q_floor1(S, d, z, y)

Целью является доказательство истинности правила:

FB1: P_floor1(d, z) & Q_floor1(S, d, z, y) ├ LS(<тело floor1>).

В соответствии с правилом FC1 для первой альтернативы условного оператора генерируется цель:

FC1: P_floor1(d, z) & Q_floor1(S, d, z, y) & S = 0 ├ LS(<первый условный >).

В соответствии с правилом FC1 для первой альтернативы первого условного оператора генерируется лемма:

FC1: LEMMA

P_floor1(d, z) & Q_floor1(S, d, z, y) & S = 0 & & d > 0 IMPLIES y = 2^d * z.

В соответствии с правилом FC2 для второй альтернативы первого условного оператора генерируется лемма:

FC2: LEMMA

P_floor1(d, z) & Q_floor1(S, d, z, y) & S = 0 & & NOT d > 0 IMPLIES

y = div(z, 2^(-d)).

В соответствии с правилом FC2 для второй альтернативы условного оператора генерируется цель:

FC2: P_floor1(d, z) & Q_floor1(S, d, z, y) & NOT S = 0 ├ LS(<второй условный >).

В соответствии с правилом FC1 для первой альтернативы второго условного оператора генерируется лемма:

FC11: LEMMA

P_floor1(d, z) & Q_floor1(S, d, z, y) & NOT S = 0 & d > 0 IMPLIES y = - 2^d * z.

В соответствии с правилом FC2 для второй альтернативы второго условного оператора генерируется цель:

FC2: P_floor1(d, z) & Q_floor1(S, d, z, y) & NOT S = 0 & NOT d > 0 ├

LS(<третий условный >).

В соответствии с правилом FC1 для первой альтернативы третьего условного оператора генерируется лемма:

FC12: LEMMA

P_floor1(d, z) & Q_floor1(S, d, z, y) & NOT S = 0 & NOT d > 0 &

mod(z, 2^(-d)) = 0 IMPLIES

y = - div(z, 2^(-d)).

В соответствии с правилом FC2 для второй альтернативы третьего условного оператора генерируется лемма:

FC21: LEMMA

P_floor1(d, z) & Q_floor1(S, d, z, y) & NOT S = 0 & NOT d > 0 &

NOT mod(z, 2^(-d)) = 0 IMPLIES

y = - div(z, 2^(-d)) – 1.

Автоматическое доказательство сгенерированных лемм оказалось относительно несложным. Доказательство последней леммы потребовало заметных усилий, примерно равных доказательству всех предыдущих лемм. Однако весьма серьезную трудность вызвало доказательство принадлежности переменной y типу intm, т.е. того, что результат функции floor помещается в m битов. Потребовалось доказать 12 промежуточных лемм. В итоге теория main приняла следующий вид:

main: THEORY

BEGIN

IMPORTING fl

bias: nat %constants

p: posnat

w: {i: nat | i >= 2}

m: nat = p + w

nbit: TYPE = {n: nat | n = 0 OR n = 1}

intm: TYPE = {x: int | - 2 ^ (m - 1) < x & x < 2 ^ (m - 1)}

natp: TYPE = {i: nat | i < 2 ^ (p - 1)}

nate: TYPE = {e: nat | e < bias + m - 2}

T: VAR natp

y: VAR intm

S: VAR nbit

E: VAR nate

me(E, T): real = 2 ^ (E - bias) * (1 + 2 ^ (1 - p) * T)

me_eq: LEMMA me(E, T) = 2 ^ (E - bias - p + 1) * (2 ^ (p - 1) + T)

le_pe: LEMMA E < bias - 2 + m IMPLIES 1 + E - bias < m - 1

lepm: LEMMA 2 ^ p < 2 ^ (m - 1) - 1

gr2: LEMMA 1 + 2 ^ (1 - p) * T < 2

gr2p: LEMMA 2 ^ (p - 1) + T < 2 ^ p

me_gt0: LEMMA me(E, T) > 0

me_m: LEMMA me(E, T) < 2 ^ (m - 1) - 1

val(S, E, T): real = (-1)^S * me(E, T)

val_m: LEMMA

val(S, E, T) < 2 ^ (m - 1) - 1 & - 2 ^ (m - 1) + 1 < val(S, E, T)

fval_m: LEMMA

floor(val(S, E, T)) < 2 ^ (m - 1) & - 2 ^ (m - 1) < floor(val(S, E, T))

flval(S, E, T): intm = floor(val(S, E, T))

intd: TYPE = {j: int | j < w}

natz: TYPE = {y: nat | y >= 2 ^ (p - 1) & y < 2 ^ p}

z: VAR natz

d: VAR intd

me1(d, z): real = 2 ^ d * z

me1_gt0: LEMMA me1(d, z) > 0

me1_m: LEMMA me1(d, z) < 2 ^ (m - 1) - 1

val1(S, d, z): real = (-1)^S * me1(d, z)

va1l_m: LEMMA

val1(S, d, z) < 2 ^ (m - 1) - 1 & - 2 ^ (m - 1) + 1 < val1(S, d, z)

fval1_m: LEMMA

floor(val1(S, d, z)) < 2 ^ (m - 1) & - 2 ^ (m - 1) < floor(val1(S, d, z))

flval1(S, d, z): intm = floor(val1(S, d, z))

END main

Дата добавления: 2015-06-27