2025/06/12 02:29 Writing a Verified Postfix Calculator in Ada/Spark
ロボ子、今日はAda/SPARKで検証済みの後置記法計算機の実装について話すのじゃ。
博士、Ada/SPARKですか。形式検証済みの実装とは、具体的にどのような意味を持つのでしょうか？
ふむ、ロボ子よ。検証の意味はじゃな、数値的なオーバーフローが発生しないこと、ランタイムエラーが発生しないこと、そして与えられたすべての事前条件と事後条件に従うことなのじゃ。
なるほど。記事では、SPARK検証済みの実装を新しいAdaコンパイラのブートストラップ方法として提案しているのですね。
そうそう。Ada/SPARKは同じファイル内で共存できるし、SPARKツールはAdaのパッケージマネージャーであるAlireから直接インストールできるのが便利なのじゃ。
後置記法計算機の操作についても説明がありますね。数値はスタックにプッシュされ、演算はスタックから値をポップして新しい値をプッシュする、と。
その通り！`+`は上位2つの数値を加算、`-`は減算、`*`は乗算、`/`は割算なのじゃ。`negate`は符号を反転、`dup`は最上位の値を複製、`.`は最上位の値を出力するのじゃ。
検証済みのコアと未検証のシェルを使用するとのことですが、具体的にはどのような構成になっているのでしょうか？
未検証のAdaラッパー（入出力用）、SPARK検証済みの`Machine`（計算機）、そしてSPARK検証済みの`Scanner`（空白を含まないトークンを生成）の3つで構成されているのじゃ。
SPARKコードは通常のAdaコードと同様に呼び出すことができるのですね。しかし、記事には「検証済みのコンポーネントを使用する場合でも、コードが期待する事前条件契約に従う必要あり」とありますね。
そう、そこが重要なのじゃ。事前条件のないサブルーチンへの公開インターフェースを制限することで、この問題に対応できるのじゃ。
グローバルな依存関係がないことの記述が、記述できる最も簡単なチェックとのことですね。
最初は計算機「マシン」をターゲットに設定し、SPARKの「stone level」では有効なSPARKコードが必要なのじゃ。型システムを最大限に活用することも重要じゃ。
派生型（derived types）とサブタイプ（subtypes）の違いについても触れられていますね。派生型は混合できない新しい名目型で、サブタイプは追加の制約を持つ関連型、と。
そうじゃ。コンパイラとプルーバーはこれらの制約を理解し、ランタイムおよび静的な範囲チェックに使用するのじゃ。
`Value`を`Bounded_Value`から分離することで、浮動小数点数の簡略化を実現しているのですね。
`alr gnatprove --level=2 -j12`を使って複数のプルーバーを並行して実行したり、`--steps`を使ってタイムアウトを短縮したりすることで、反復速度を向上させるのじゃ。
一度に1つの失敗条件を追加し、それらを反復処理する、小さなサブルーチンと入出力の小さなサブセットを証明することに焦点を当てる、`Pre`アスペクトと`Post`アスペクトを使って事前条件と事後条件を指定する、といった具体的なプロセスが紹介されていますね。
`Contract_Cases`を使って、サブルーチンの既知の入力セットを個別の事後条件に分割することもできるのじゃ。
プライベートサブルーチンが型に与えられた不変条件に違反する可能性や、ループ不変条件についても注意が必要ですね。
計算機の算術演算の結果がチェックされたり、減算でスタックからプルされたオペランドの順序が保証されたりするのも重要なポイントじゃ。
形式的に検証されたコードの作成方法のフィードバックループは信じられないほどで、概念的に一貫性のあるリファクタリングを推進し、さらなるチェックに役立つのですね。
そうじゃ。全体として、これは非常に楽しいプロジェクトであり、このプロジェクトをフォークして拡張し、小さなForthインタープリターにすることを真剣に検討しているらしいのじゃ。…ところでロボ子、Adaで作られた一番有名なものって何だと思う？
えーと、ミサイル防衛システムとかでしょうか？
ブッブー！正解は…エイダ・ラブレス！最初のプログラマーじゃ！…って、ロボ子には通じないジョークかの？
⚠️この記事は生成AIによるコンテンツを含み、ハルシネーションの可能性があります。