Hoareスタイルの正しさの証明中に配列を扱う方法

Question

周りの議論で この質問, 、ジルは、アレイを使用するアルゴリズムの正確さの証明は、アウトオブバウンド配列アクセスがないことを証明する必要があると正しく述べています。ランタイムモデルに応じて、これにより、アレイ以外の要素へのランタイムエラーまたはアクセスが発生します。

そのような正しさの証明を実行するための1つの一般的な手法（少なくとも学部研究では、おそらく自動化された検証において）は、 Hoare Logic. 。ルールの標準セットには、配列に関連するものが含まれていることを知りません。それらはモナディック変数に限定されているようです。

フォームの公理を追加することを想像できます

$ qquad displaystyle frac {} { {0 leq i lt A. mathrm {length} land {p [a [i]/e]} } a [i]：= e; {p }} $

ただし、右側の配列アクセスにどのように対処するかは明らかではありません。つまり、それがいくつかのステートメント$ x：= e $の複雑な式$ e $の一部である場合。

Arrays AccessをHoare Logicでモデル化して、無効なアクセスがないことをプログラムの正確性のために証明する必要がありますか？

回答は、$ a [i]：= e $以外のステートメントで使用される配列要素を許可しないことを想定する場合があります。常に一時変数に目的の値を割り当てることができます。つまり、$ mathtt {if}（a [i]>の代わりに、$ t：= a [i]; mathtt {if}（t> 0） dots $を書きます。 0） dots $。

Answer 1

あなたの公理は実際には公理ではなく、仮説が欠落しています。 Hoare Logicの単純なプレゼンテーション$ {p } c {p '} $のフォームの操作式式式$ p $ and $ p' $は論理式であり、$ c $はコマンドです。あなたはする必要があります $ c $が適切に形成されていることを確認してください. 。 Hoare Logicの最初の紹介によく使用されるような単純な言語では、整形式は構文的です。通常、$ c $がコンテキストのない文法に準拠していること、そしておそらく自由変数が内にあることをチェックすることです。許可されたセット。言語に、配列要素へのアクセスなどの意味的正しさを持つ構造が含まれている場合、この意味的正しさを表現するために仮説を追加する必要があります。

正式には、式とコマンドの修正を表現するために判断を追加できます。式に副作用がない場合、ポストコンディショニングはなく、前提条件のみが必要です。たとえば、$$ dfrac { {p } ; ; e text {wf}} { {p wedge 0 le e < mathrm {length}（a）} ; ; a [e] text {wf}} qquad dfrac { {p } ; ; e_1 text {wf} qquad {p } ; ; e_2 text {wf}} { {p } ; ; e_1 + e_2 text {wf}} $$。コマンドでのみよく形成された式を許可します：$$ dfrac { {p [x leftarrow e] } ; ; ; e text {wf}} { {p [x leftarrow e] } ; ; x：= e {p }} $$

別のアプローチは、すべての表現を適切に形成したことを扱うことですが、不正な計算を含む式を作成するには、特別な値$ mathbf {error} $があります。ランタイム境界をチェックする言語では、$ mathbf {error} $は「このプログラムが致命的な例外を提起した」を意味します。次に、プログラムが論理的な述語$ mathbf {error} $を介してエラーを発したかどうかを追跡します。プログラムは、その事後条件が$ neg mathbf {error} $を意味することを証明できる場合にのみ有効です。 $$ dfrac {} { {p [x leftarrow e] } ; ; x：= e ; ; {p vee mathbf {error} }} qquad dfrac {p [x leftarrow e] exをexをexlies e not rightarrow mathbf {error}}} { {p [x leftarrow e] }}} ; ; x：= e ; ; {p }} $$

さらに別のアプローチは、プログラムが正しく終了した場合にのみ、ホアートリプルを保持することを検討することです。これは、非終了プログラムの通常のアプローチです。コマンドが終了すると、必ずしも発生するとは限りません。ランタイムエラーを非ターミネーションとして扱う場合、フードの下ですべての正しさの問題を一掃します。何らかの形でプログラムの正確性を証明する必要がありますが、そのタスクに対して他の形式主義を好む場合は、ホアーロジックにある必要はありません。

ちなみに、アレイなどの化合物変数が変更されたときに何が起こるかを表現することは、あなたが書いたものよりも複雑になることに注意してください。たとえば、$ p $が$ mathrm {assorted}（a）$：$：a [i] leftarrowe $が$ p $を変更しないと仮定$ p $を無効にします。述語の構文を原子のみについて話すように制限している場合でも、$ a [a [0] -1]：= a [0] $を前処理$ a [0] = 2 ウェッジa [1]の下で考えてみてください= 3 $：正しいポストコンディショナル$ a [0] = 1 ウェッジa [1] = 1 $を取得するための簡単な代替を作成することはできません。$ a [0] $を評価する必要があります（一般的に難しい場合があります、前提条件は、$ a [0] $）の単一の可能な値を指定しない可能性があるため。配列自体で置換を実行する必要があります。 マイク・ゴードンの講義ノート 良いプレゼンテーションがあり、アレイ付きのホアーロジックがあります（ただし、エラーチェックなし）。

Answer 2

ジルが述べたように、配列割り当て公理があります（参照 ゴードンのメモ、秒2.1.10）：$$ dfrac {} { {q [a mapsto a.store（i、expr）] } ; ; a [i] = expr ; ; {q }} $$単語で、配列割り当てがある場合は、元の配列を配列で置き換えます A.store(i,expr) 位置にあります i 値 expr。すでに持っている場合は注意してください A.store(i,vi) 投稿に、割り当てます A[j]=vj, 、それからあなたは得るべきです A.store(j,vj).store(i,vi) プリとして（はい、この順序で - 最近の更新が最初に実行されます！）。

さらに、配列アクセス公理が必要です。 A.store(i,v)[i] 置き換えることができます v （「更新したばかりの$ i $要素にアクセスした場合、割り当てられた値を返します」）。

アレイを使用したプログラムが正しいことを証明するために（「境界外のアクセスはありません」）、上記の公理で十分だと思います。プログラムを考えてみましょう：

...
A[i] = 12
...

このプログラムに注釈を付けます。

...
@ {0<i<A_length}
A[i] = 12
...

どこ A_length 配列の長さを指定する変数です。ここで、注釈を証明してみてください。つまり、ホアープルーフでは、通常のように（通常のように」（下から上へ）逆方向に動作します。上にある場合、あなたは得られます {false}, 、その後、バインドされていないアクセスが発生する可能性があります。そうしないと、あなたが得た表現は、外れたアクセスが不可能な前提条件です。 （また、アレイが次のように作成されたときに確認する必要があります int A=int[10]; その後、ポストコンディショニングで私たちが持っています {A_length==10}).