3

合金初心者です。

私は、Alloy で制約を作成し、モデルが制約に従って有効であることをアナライザーにチェックさせるのが本当に好きです。

しかし、「これらの制約の定義は単なる頭の体操ですか? それとも、より良いソフトウェアの構築に役立つでしょうか?」</p>

具体例を挙げてみましょう。電子メール クライアントのアドレス帳のモデルでは、アドレス帳に新しいエントリを追加するために次の制約を定義できます。

新しいブック b' のアドレス マッピングは、古いブック b のアドレス マッピングと同じですが、名前からアドレスへのリンクが追加されています。この制約は Alloy では次のように表されます: b'.addr = b.addr + n->a

それは美しいです。

しかし、追加操作がコードに実装されている場合、その関連性を確認するのに苦労しています。たとえば、Common Lisp でadd操作を実装しました。

(defun add (b n a)
   "Add a new entry, (n a), to address book b"
   (adjoin (list n a) b :key #'first))

つまり、「これはaddという名前の関数の定義で、3 つのパラメーターbn、およびa (本、名前、住所) を持ちます。Common Lisp の set 関数adjoinを使用して、リスト ( na ) をbに追加します。"</p>

その関数は、単純な追加関数を正しく実装しているようです。Alloy で定義した拘束はどうすればよいですか? 制約を表現する追加のコードを作成する必要がありますか? 擬似コード: [1]

(defun add (b n a)
   "Add a new entry, (n a), to address book b"
   (adjoin (list n a) b :key #'first)
   Check that nothing has changed in the
   address book except that it now has
   a n->a mapping)

このようなコードを書くのは大変な作業のように思えますが、明らかなメリットはありません。

私の質問は次のとおりです: コードで Alloy モデルを実装する場合、Alloy で定義されている制約をどうすればよいですか?

また、Alloy モデルをコードに変換する方法を説明するチュートリアルはありますか? コードで Alloy 制約定義がどのように使用されるかの説明が含まれていますか?

ありがとうございました。

[1] 注: Common Lisp には Screamer という制約プログラミング用の言語拡張があることを認識しています。

4

1 に答える 1

4

この質問は、Alloy のようないくつかのモデリング言語の目標と機能についての小さな誤解から生じており、形式的手法、検証、およびソフトウェア モデリングの基本的な側面のいくつかに触れていると思います。物事をより明確にするバックグラウンド ストーリーを取得するためのおそらく良いリソースには、Calculus of Computation のような本や、あなたが言及したAlloy に関する本が含まれます。

コンストレイントは、Alloy モデリング言語の第一級市民です。考え方は、制約は、モデル化 (およびプロパティのチェック) したいコードのセマンティクスを反映するというものです。したがって、ある観点からは、Alloy プログラムはコード自体を表し、追加のコードを (関数型言語などで) 記述したり、宣言された制約をコードと混合したりする必要はありません。ただし、Alloy プログラムを直接実行することはできません。むしろ、そのようなプログラム (つまり、一連の制約) に従ってモデルを作成するためにのみ使用できます。

より具体的には、Alloy 制約b'.addr = b.addr + n->aは、適切な解釈の下で、実際に Lisp での追加操作の動作をキャプチャする可能性があるため、制約に関連するいくつかのプロパティを確認することは、それらのプロパティが Lisp で特定の操作を保持するかどうかを確認することに対応します。これは、ソフトウェアのモデリングと検証のための Alloy の標準的な (そしてほぼ間違いなく意図された) 使用方法です。(さらに、Alloy は、特定の種類のサイバー物理システム [1] のように、プログラムへの明確なマッピングを持たないシステムをモデル化するために頻繁に使用されます。) これはもちろん、Alloy で記述したモデルが正しくモデル化しなければならないことを伴うことに注意してください。プロパティのチェックを意味のあるものにするために、(そのセマンティクスに関して)目前のプログラム。

前述のように、Alloy 自体は実行可能コード (Common Lisp で記述された、指定されたものなど) を生成できません。ただし、Alloy と、Alloy が生成するモデルを使用して、コードのフラグメントまたはテスト ケースを生成する複数のアプローチがあります。さらに、Alloy* [2] と呼ばれる Alloy の拡張機能を使用すると、Alloy* 内でより高次の制約を解決する可能性が追加され (関係に対する定量化)、プログラムの生成に使用できます。操作を実行し、さまざまな入力を受け入れる実際のコード (モデルに応じて add 関数と同様)。繰り返しになりますが、そのようなプログラムは Alloy モデルで表され、これらのモデルを目的のプログラミング言語のプログラムに変換する (追加の作業を行う) 必要があります。

そうは言っても、一部の(検証)システムでは、実際に仕様をコードと混在させることができることに注意してください。仕様は次のようになります。実行されるコードと同じ方法で記述されます(検証/合成フレームワークLeon [3]のように) ); または、(実行可能なコードの言語とは) 異なる言語で書かれている一方で、仕様は他の手段 (Dafny [4] の注釈など) によってコードにバインドされています。

[1] カン、ウンスク他 「水処理システムのモデルベースのセキュリティ分析」。スマート サイバー フィジカル システムのためのソフトウェア エンジニアリングに関する第 2 回国際ワークショップの議事録。ACM、2016 年。

[2] Milicevic、Aleksandar、他。「Alloy*: 汎用の高次リレーショナル制約ソルバー。」第 37 回ソフトウェア エンジニアリング国際会議議事録 - 第 1 巻。IEEE Press、2015 年。

[3]ブラン、レジス他 「Leon検証システムの概要: 再帰関数への翻訳による検証.」第 4 回 Scala ワークショップの議事録。ACM、2013年。

[4] Leino、K. Rustan M.「Dafny: 機能の正しさのための自動プログラム検証ツール」。人工知能と推論をプログラミングするための論理に関する国際会議。スプリンガー ベルリン ハイデルベルク、2010 年。

于 2016-09-06T23:47:10.173 に答える