付録F. 規範拡張(norms 0.1)
本付録は,CADLの規範拡張を規定する。この拡張は,
付録A.4の生成規則
contract_def に2つのキー norms: と counts_as: を追加し,契約の一部の述語に
有界の時相演算子を追加する。これにより,コア言語では assume:,guarantee:,
responsibilities: のテキストとして書くしかなかった義務・許可・禁止・権能を,負担者,期限,
時間に沿った状態,違反時の帰結を持つ対象として書けるようになる。
コア言語(第5章,付録A)は, これらのブロックを必須としない。 本拡張を実装していないCADL準拠の処理系は,新しいキーを理由にファイルを 拒否してはならない。新しいキーを構文上は受理し,情報レベルの診断を出すことが望ましい。
本拡張のバージョンは,コア言語とは独立に管理する。拡張の名前は norms であり,
本付録はバージョン 0.1 を記述する。F.4の時相演算子は一部の述語の読み方を変えるため,
本拡張を用いるファイルは,付録A.2の
extensions: キーでそのことを宣言しなければならない。宣言せずに用いた場合に処理系がどう扱うかは
F.11で述べる。
sos:
...
extensions:
- norms: 0.1
本拡張は,SoS-DSL拡張(付録E)と併用しても,単独で用いてもよい。
契約が lifecycle: ブロックも持つ場合,規範は違反時に契約インスタンスをライフサイクルの状態へ
移すことができる(F.3)。
F.1 動機
9.6節の研究方向は,コア言語に欠けている次の4点を挙げている。本拡張のバージョン0.1は, そのそれぞれに対応する最小限の機能を定める。
- 規範が第一級でない。
"delivery_time <= 300s"のような保証は,何が成り立つべきかを述べるが, 誰がそれを成り立たせるのか,いつからいつまでか,成り立たなかったときにどうなるかを述べない。 Symboleoのような義務論理に基づく契約言語は,義務と権能をライフサイクルを持つ対象として扱う [Sharifi+, 2020]。CADLの契約はそうではなかった。 - 述語に時間がない。
assume:とguarantee:は状態述語である。期限は,SoS-DSL拡張の ライフサイクル遷移にしかない。 - プロトコルと契約がつながっていない。 プロトコルのメッセージが契約上の行為とみなされる (counts as)ことを述べる手段がない。制度は,このようにして他の事実から制度的事実を作り出す [Boella & van der Torre, KR 2004]。
- 改正が動作中の規範に及ばない。 SoSの運用中に契約を改正する場合(ハンズオン教材の Course D のように),すでに発効している義務がどうなるかを 述べる手段がない。
norms 0.1が定める範囲は意図して小さくしている。語彙と静的・動的意味論を定めることで,設計時の検査 (モデル検査器への変換。F.12)と実行時の監視を,言語を変えずに処理系が追加できるようにする。 制度パラメータα,β,λには,規範に関する形式的な意味を与えない(F.7)。契約の規範とパラメータを 結び付ける最初の定めは,根拠付け拡張(付録J)が与える。
F.2 概念
| 概念 | norms 0.1での意味 |
|---|---|
| 規範(norm) | 契約に宣言する,1人の負担者の義務・許可・禁止・権能。 |
| 義務(obligation) | 負担者は,その content を実現しなければならない(述語を真にする,または事象を起こす)。deadline: があればその期限までに。 |
| 禁止(prohibition) | 負担者は,規範が発効している間(deadline: があればその期間内),その content を実現してはならない。 |
| 許可(permission) | 負担者は,その content を実現してよい。許可は違反されることがなく,許されていることを記録する。 |
| 権能(power) | 負担者は,契約の他の規範の状態を変える制度上の行為(その content)を行うことができる(effects:)。権能は履行も違反もされない。 |
| 制度的事象(institutional event) | counts_as: 規則がメッセージや条件から作る,契約の名前付きの事象。たとえば「このメッセージは再割当てとみなす」。 |
| 契約インスタンス | 付録Eと同じく,契約の1回の実行。いつ始まりいつ終わるかはF.5で述べる。 |
| 規範インスタンス | 1つの契約インスタンスにおける規範。バージョン0.1では,各規範は1つの契約インスタンスにつきちょうど1つのインスタンスを持つ。ROBOT[i] の i のような添字は契約インスタンスが束縛する。 |
| 判定(verdict) | これまでに観測したトレース上での,規範インスタンスまたは時相的な保証の値。pending,fulfilled,violated,excused のいずれか(F.5)。 |
F.3 構文(A.4へのEBNFの追加)
文法は付録Aの記法に従う。identifier,actor_ref,
duration_lit,predicate,text は付録Aで,message_event と severity は
付録EのE.3節で定義している。contract_def に2つの省略可能なキーを追加する。
contract_def = ... ,
[ "norms:" , { "-" , norm_def } ] ,
[ "counts_as:" , { "-" , counts_as_def } ] ;
norm_def = "id:" , identifier ,
"kind:" , norm_kind ,
"bearer:" , actor_ref ,
[ "counterparty:" , actor_ref ] ,
[ "trigger:" , norm_event ] ,
[ "until:" , norm_event ] ,
"content:" , norm_content ,
[ "deadline:" , duration_lit ] ,
[ "on_violation:" , norm_violation ] ,
[ "effects:" , power_effects ] ,
[ "on_amendment:" , amendment_policy ] ;
norm_kind = "obligation" | "permission" | "prohibition" | "power" ;
norm_event = message_event | identifier | predicate ; (* string *)
norm_content = message_event | identifier | tpredicate ; (* string *)
norm_violation = [ "severity:" , severity ] ,
[ "sanction:" , text ] ,
[ "reparation:" , identifier ] ,
[ "transition:" , identifier ] ;
power_effects = [ "activate:" , { "-" , identifier } ] ,
[ "suspend:" , { "-" , identifier } ] ,
[ "resume:" , { "-" , identifier } ] ,
[ "discharge:" , { "-" , identifier } ] ;
amendment_policy = "carry_over" | "discharge"
| ( "transform:" , identifier ) ;
counts_as_def = "when:" , ( message_event | predicate ) ,
"creates:" , identifier ,
[ "if:" , predicate ] ;
norm_event と norm_content は次のように読む。A -> B : m の形の文字列は message_event である。
1つの識別子だけからなる文字列は,契約が counts_as: でその名前の制度的事象を宣言していれば
その事象を名指し,そうでなければ述語(状態変数,N-8)である。それ以外の文字列は述語
(norm_event)または tpredicate(norm_content)である。より大きな述語の中に現れる
制度的事象の名前(reassignment AND x > 0)は,事象ではなく状態変数である。[,],*,->,
": " を含む値は,付録Aのすべてのスカラーと同じく,引用符で囲むことが
望ましく,フロー形式のシーケンスの中では囲まなければならない。
message_event S -> R : m は,名前 m を持ち,送信者が S に一致し,受信者が R に
一致するメッセージを含む観測で起こる。m を引数付きで書いたときは,それらがメッセージの
引数と等しくなければならない。アクター参照は,message_event が現れるどの場所でも,すなわち
trigger:,until:,content:,counts_as: 規則の when: で,メッセージの具体的な
アクターに次のように一致する。
| 参照 | 一致するもの |
|---|---|
A | 添字なしで宣言したアクター A。添字付きの要素 A[k] には一致しない |
A[3] | 要素 A[3] |
A[*] | 宣言した集合 A のすべての要素 |
A[1..3] | 要素 A[1] から A[3] まで。上限が記号であるとき(A[1..N])は,集合のすべての要素 |
A[i] | 契約インスタンスが i を v に束縛しているときは,要素 A[v]。i に値を束縛していないときは,集合のすべての要素(処理系は警告することが望ましい) |
A を範囲付きで宣言しており,k がその整数の上下限の内にあるとき,A[k] は集合 A の
要素である。A[1..3] と宣言した集合は A[7] を含まない。宣言した上限が記号であるとき
(A[1..N])は,下限以上のすべての添字が要素であり,A[0] は要素でない。宣言していないアクター,
または集合の上下限の外にあるアクターは,どの参照にも一致しない。
これらの述語では,付録EのE.4節の予約識別子を
rule と同じく用いることができる。now,request,および契約が lifecycle: ブロックを持つ場合の
state である。E.3の所属判定 x IN [a, b] も用いることができる。
on_violation: の reparation: は,この規範が違反されたときに発効する同じ契約の別の規範
(反義務(contrary-to-duty)の規範)を名指し,sanction: は制裁をテキストで述べ,
transition: は契約の lifecycle: ブロック(付録E)の状態を名指す。
契約インスタンスは,ライフサイクル遷移の on_violation.transition と同じく,その状態へ移る。
severity: の既定値は Major,on_amendment: の既定値は carry_over である。
counterparty: は規範の相手方となる当事者を名指す。バージョン0.1では参考情報であり,
意味論には影響しない。
キー until: と,F.4の時相演算子 until(...) は別のものであり,同じ規範の中に両方現れてよい。
F.4 時相述語
tpredicate は,付録AのA.10節の predicate のうち,
function_call が書ける位置に次の3つの有界の時相演算子を書けるものである。
演算子は関数呼び出しの形で書くため,A.10の式の文法は変わらない。本拡張はこの3つの名前に意味を与える。
tpredicate = predicate ; (* 以下の呼び出しが時相的な意味を持つ *)
temporal_call = "within" , "(" , duration_lit , "," , tpredicate , ")"
| "throughout" , "(" , duration_lit , "," , tpredicate , ")"
| "until" , "(" , tpredicate , "," , tpredicate , "," , duration_lit , ")" ;
| 演算子 | 時刻 t で成り立つ条件 | 計量時相論理 |
|---|---|---|
within(d, p) | [t, t + d] のある時刻で p が成り立つ | F[0,d] p |
throughout(d, p) | [t, t + d] のすべての時刻で p が成り立つ | G[0,d] p |
until(p, q, d) | [t, t + d] のある時刻 t′ で q が成り立ち,[t, t′) のすべての時刻で p が成り立つ | p U[0,d] q |
演算子は時刻付きトレースの上で評価する。これは観測の列であり,各観測は観測量のスナップショットと
単調非減少の時刻印からなる。付録Eのモニターに渡されるものと同じである。
「ある時刻」「すべての時刻」は,時刻印がその区間に入る観測の上を動く(点ごとの意味論)。
観測を1つも含まない区間では,within は偽,throughout は真になる。d は0より大きい
duration_lit でなければならない。演算子は入れ子にしてよい。
書ける位置。 本拡張を宣言すると,時相演算子は,契約の assume: と guarantee: の項目,
および規範の content: にだけ書ける。バージョン0.1では,ファイルのそれ以外の述語や条件には
書いてはならない(N-10)。たとえば,規範の trigger: と until:,counts_as: 規則の when: と
if:,モニターの rule:,ライフサイクルの when: と on:,condition:,safety_invariant:,
formula:,expr:,プロトコルの条件である。事象と条件は1つの観測の時点で評価するため,そこに未来を参照する演算子を
書くと,後になるまで真偽が決まらないからである。
評価する時点。 assume: または guarantee: の tpredicate は,契約インスタンスが始まる時刻に
評価する。そこでの within(300s, p) は「契約インスタンスの開始から300秒以内に p」を意味する。
不変条件を述べるには throughout を用いて書く。content: の tpredicate は,規範の発動後の
観測の時刻に評価する(F.5)。時相演算子を含まない述語は,コア言語での意味を保つ。
値が分かる時点。 時刻 t での演算子の値は,t より後の観測に依存することがある。値は,それを 定める最初の観測で決まる。それまで値は決まらず,決まった値は変わらない。
被演算子が時相演算子を含まない演算子については,規則は次のとおりである。within(d, p) が真に,
throughout(d, p) が偽に決まるのは,[t, t + d] の中のそれを示す観測である。until(p, q, d) は,
q が成り立つ観測で真に決まり,q が成り立つより前に p が成り立たなくなった観測で偽に決まる。
それ以外の場合,値は,時刻印が t + d より後である最初の観測で決まる。このとき区間は終わっており,
within と until は偽,throughout は真である。ただし,区間の中の観測で被演算子が未定義(F.5)で
あり,その被演算子に値があれば結果が変わりえた場合,値は未定義である。until(p, q, d) では,
これに当たるのは,q が未定義であった場合と,q が成り立った観測より前の観測で p が未定義で
あった場合だけである。q が一度も成り立たなかったときは,p が未定義であっても関係がなく,
値は偽である。同様に,q が未定義であった観測より後に p が成り立たなくなっても,until は
偽とは決まらず,値は未定義である。したがって,
区間の終わりは,時刻 t + d そのものではなく,その後の最初の観測で分かる。その観測は,どの量も
変えなくてよい(F.5)。
被演算子が時相演算子を含む演算子は,それが依存する被演算子の値が決まったときに決まる。被演算子の
値は,それぞれの観測で,同じ規則によって決まる。これは t + d より後になることがある。時刻 t での
within(2s, throughout(5s, p)) は,[t, t + 2s] の観測での throughout(5s, p) の値を必要とする。
p が成り立ち続ける場合,その値は5秒より後の観測で初めて決まる。したがって,この演算子は,
t + 7s より後の観測まで決まらないことがある。一般に,時刻 t での tpredicate の値は,
遅くとも,入れ子になった演算子の時間の和の最大値を t に加えた時刻より後の最初の観測で決まる。
norms: 0.1 を宣言していないファイルは,コア言語と同じく,within,throughout,until を
ふつうの関数名として読む。
F.5 動的意味論
契約インスタンス
規範は契約インスタンスごとに判定する。契約が lifecycle: ブロックを持つ場合,契約インスタンスは
付録EのE.5節のものである。ホストアプリケーションがインスタンスを生成し,
インスタンスは終端状態に達したときに終わる。契約が lifecycle: ブロックを持たない場合,
ホストアプリケーションは同じようにして,状態を持たない契約インスタンスを生成し,終わらせる。
ホストがない場合は,1つのインスタンスが最初の観測で始まり,最後の観測で終わる。
契約インスタンスがまだ動作している間に止まったトレースは前半部分であり,インスタンスは終わっておらず,
何も確定させない。
システムの動作中に観測を1つずつ受け取る処理系は,ある観測を処理する時点では,それが最後の観測で あるかどうかを判断できない。そのような処理系には,インスタンスの終了を,その観測の後に別に通知する。 規範は,そのとき,最後に受け取った観測で,その時刻印を用いて,その観測の段階6と同じように 確定させる(下の6)。契約インスタンスが終わった後に届いた観測は,そのインスタンスの一部ではなく, インスタンスに影響しない。
観測は,何も変えなくてよい。時刻印だけを含む観測も,他の観測と同じ観測であり,その時点で述語を評価し,
期限を調べる。過ぎた期限と区間の終わりは,観測と観測の間ではなく,観測の時点で検出する(下の2と3,F.4)。
したがって,動作中のシステムを監視する処理系は,発効中の規範の期限が過ぎた後,早いうちに観測を
行うことが望ましい。観測がなければ,違反は次の観測まで起こらず,violated か excused かも
そのときまで決まらない。
述語は,各観測で,真,偽,未定義の3つの値のいずれかを取る。未定義とは,まだ値を持たない量を
参照している場合である。AND,OR,NOT はクリーネの3値論理に従う。未定義の述語は,成り立ちも
破れもしない。事象や条件はそれによって起こらず,仮定や保証はそれによって決まらない。
「真になる」とは,現在の観測で真であり,かつインスタンスの直前の観測で真でなかった(または直前の
観測がない)ことをいう。lifecycle: ブロックを持つ契約では,述語の中の state は,現在の観測の
遷移が起こる前のライフサイクルの状態である。
load > 5 の load や ROBOT[i].status == Delivered の Delivered のように,述語の中に単独で
書かれた名前は,観測量か記号値のいずれかである。観測量である名前の集合は,契約インスタンスごとに
固定する。この集合は,インスタンスの開始時に処理系に与える。記録したトレースについては,
インスタンスのいずれかの観測で値を持つ名前の集合である。この集合に属する名前は,インスタンスの
すべての観測で量であり,最初の値より前の観測では未定義であって,記号値ではない。単独で書かれた
それ以外の名前は,すべて記号値である。記号値は,==,!=,IN によって文字列の値と比べることだけが
できる。それ以外の使い方をする述語は未定義である。
算術(+,-,*,/)は数に対してだけ定める。文字列,真理値,リスト,オブジェクト,記号値の被演算子と0による除算は,
その観測で式を未定義にする。被演算子が量であれば,これはその値から初めて分かるので,処理系は評価の
警告として報告する。被演算子が文字列や真理値のリテラルであるとき,または除数がリテラルの 0 である
ときは,式が値を持つことはない。規範や counts_as: の規則の中では,これを誤りとする(N-16)。
述語と観測の数は,書かれたとおりの正確な十進数である。0.1 は10分の1であり,時刻印
1700000000.123 はちょうどその秒数である。算術(+,-,*,/,avg)は有理数で正確に行うので,
0.1 + 0.2 == 0.3 は成り立つ。時刻印,F.4の区間の端,期限は,許容誤差なしで正確に比べる。期限の
時刻ちょうどの内容は期限内であり(下の項目2),その1マイクロ秒後の内容は期限内でない。処理系は,有効桁が400を超える数,小数点以下が400桁を
超える数,絶対値が1.7976931348623157 × 10308(有限の倍精度浮動小数点数の最大値)を超える数を
拒否してよい(MAY)。有限の倍精度浮動小数点数はすべてこの範囲に入る。その場合は,その観測を誤りとする。
そのようなリテラルを含む述語は評価しない。規範や counts_as: の規則の中では誤りとする(N-16)。
限量子と集約
限量述語 exists x in D: p と for all x in D: p,および集約関数の引数である内包表記
f(e for x in D)(付録AのA.10節)は,
観測の時点で定義域 D の上で評価する。定義域は,宣言したアクターの集合を A,A[*],
A[lo..hi] のいずれかで名指す。内包表記の定義域は,整数の範囲 lo..hi でもよい。
それ以外の定義域を持つ述語は評価しない(F.10)。規範や counts_as: の規則の中では誤りとする(N-16)。
変数 x は,定義域のメンバーの添字を値に取る。p または e の中では,x で添字付けした
アクター参照(A[x]。A[x+1] のような添字式の中も含む)はその添字のメンバーを表す。
A のメンバー(F.3)でない添字はどのメンバーも表さず,その量は,トレースが何を与えても
未定義である。x.q はそのメンバーの量 q を表す(sum(r.load for r in ROBOT[*]) の r.load)。
単独の x は整数の添字であり,j != k は j と k が異なるメンバーであることをいう。
p または e の中では,x は,契約インスタンスが束縛する同名の添字,同名の観測量,
および外側の限量子や内包表記の同名の変数を隠す。集合の宣言の記号の境界は隠さない。
A[1..N] と宣言した集合の境界 N は,限量子や内包表記が N という名前の変数を持つときも,
すべての限量子と内包表記の外側で読む(N-14)。
閉じた定義域と開いた定義域。 集合のメンバーはF.3のとおりであり,範囲 A[lo..hi] は
その境界の内側のメンバーだけを残す。すべての境界が整数であれば,定義域は閉じており,
ちょうどそれらのメンバーからなる。記号の境界(A[1..N] と宣言した集合,A[2..N],1..N の
N)は,契約インスタンスがその名前を整数に束縛するとき,またはその名前が観測量であって
その観測での値が整数であるとき,その観測で値を持つ。記号の境界を持つ定義域も,そのような
境界がすべて値を持ち,かつ,集合の宣言の記号の境界については,その値を超える添字のメンバーが
その観測またはそれより前に名指されていないときは,閉じている。F.3は,境界がどんな値を持っても,
下限以上のすべての添字をメンバーとするので,値を超えて名指されたメンバーがあれば定義域は
開いたままである。そのとき処理系は警告することが望ましい。そうでなければ定義域は開いており,
メンバーの数はわからない。開いた定義域の,ある観測での
既知のメンバーとは,集合のメンバーのうち整数の境界の内側にあり,契約インスタンスが
その観測またはそれより前に名指したものである。名指すとは,値の名前に現れること
(A[3].delivery),メッセージの送信者または受信者であること,および,契約の規範か
counts_as: 規則が A[i] と書く添字 i を k に束縛することである。現在より後の観測は
決して用いない。したがって,開いた定義域が,後で観測したものによって閉じることはない。
トレースが与える境界はいくらでも大きくなりうるので,処理系は,閉じた定義域について列挙する メンバーの数を制限してよい。そのとき,制限より多くのメンバーを持つ閉じた定義域は,その既知の メンバーによって,開いた定義域として評価する。下の議論によりこれは健全であり,閉じた定義域が 決めるはずの値が未定義になりうるだけである。そうする処理系は,集合と大きさを示して警告する ことが望ましい。
値。 閉じた定義域では,限量子はクリーネの3値論理に従う。exists x in D: p は,
あるメンバーで p が真なら真,すべてのメンバーで p が偽なら偽,それ以外は未定義である。
for all x in D: p は,あるメンバーで p が偽なら偽,すべてのメンバーで p が真なら真,
それ以外は未定義である。空の定義域では,exists は偽,for all は真である。開いた定義域では,
既知のメンバーだけが値を決める。exists は,既知のあるメンバーで p が真なら真であり,
for all は,既知のあるメンバーで p が偽なら偽である。それ以外の値は未定義である。
既知のすべてのメンバーで p が同じ値を持つときも,既知のメンバーがないときも同じである。
p が時相演算子(F.4)を含むときは,まだ値を決めうるメンバーについて p が決まっていない間,
値は決まらない。
開いた定義域についてのこの規則は健全である。既知のメンバーをその観測での値のまま含み,
さらに任意のメンバーを任意の値(未定義でもよい)で含む閉じた定義域を考える。そのような定義域は,
それまでに名指されたすべてのメンバーを含むので,境界が後にどんな値を取っても,開いた定義域の
あり得る完成形である。p が真となる
メンバーはその定義域でも exists を真にし,p が偽となるメンバーは for all を偽にする。
クリーネの論理では,真の被演算子を持つ選言は真であり,偽の被演算子を持つ連言は偽であって,
ほかの被演算子によらないからである。したがって,開いた定義域で真または偽である値は,
そのようなすべての閉じた定義域での値である。この規則はまた最も強い。既知のメンバーが
値を決めないとき,p が真となる(または偽となる)メンバーを加えると値が変わる。未定義は,
F.5が値を持たない量を参照する述語に与える値である。特に,開いた定義域の上の exists は
決して偽にならず,for all は決して真にならない。content: がそのような exists である禁止は,
既知のメンバーがそれを示したときに違反となり,そうでなければ,未定義の内容一般と同じく,
違反とならない。
集約。 内包表記の集約関数のうち,規範拡張は sum,count,min,max,avg を
評価する。count(p for x in D) は p が真となるメンバーの数である。p の値は,真であるか0以外の数で
あるときに真と数え,文字列の値や記号値はその数を未定義にする。ほかの関数は e の値を
取り,その値は数である。空の定義域の sum と count は0である。集約は,開いた定義域の上で,
あるメンバーで e(count では p)が未定義であるとき,e の値が数でないとき,
および空の定義域の上の min,max,avg では未定義である。そのような値を比べる述語は,
下の比較を除いて未定義である。ほかの関数と,内包表記の中の時相演算子は評価しない(F.10)。
規範や counts_as: の規則の中では誤りとする(N-16)。
比較の中の単調な集約。 定義域にメンバーを加えても,count は減らず,max は減らず,min は
増えない。そこで,op が <,<=,>,>=,==,!= のいずれかである比較 a op b または
b op a で,a が内包表記の count,max,min の呼び出しであり,b が限量子も内包表記も
含まない(したがって値が定義域によらない)ものは,可能であれば,その観測で既知のメンバーから
値を決める。未定義である要素と,開いた定義域ではまだ既知でないメンバーは,どの値も取り得るとする。
このとき,集約の値は次の区間にある。値の種類が誤っている要素(数でない e の値,count では
文字列の値や記号値である p の値)は,上に述べたとおり,引き続き集約と比較を未定義にする。
| 集約 | 区間 |
|---|---|
count | p が真であるメンバーの数 t から t + u まで。u は p が未定義であるメンバーの数である。開いた定義域では上端がない |
max | e の定義された値の最大値以上で,上端がない |
min | e の定義された値の最小値以下で,下端がない |
比較は,区間のすべての値(count ではすべての整数)で成り立つとき真,どの値でも成り立たないとき偽,
それ以外は未定義である。e の定義された値を持たない max と min は,これまでどおり未定義である。
たとえば,ROBOT[1..N] の開いた定義域の上で,count(ROBOT[j].delivery == 7 for j in ROBOT) >= 2 は,
既知のロボットのうち2台の配送が7になった時点で真であり,max(ROBOT[j].load for j in ROBOT) <= 10 は,
既知のロボットの負荷が10を超えた時点で偽である。count(...) == 2 は,開いた定義域の上では真に
ならない。メンバーがさらに1つ加わるかもしれないからである。要素がすべて定義された閉じた定義域では,
区間は厳密な値であり,何も変わらない。この規則は,上の限量子についての議論によって健全である。
定義域の完成形は既知の要素をすべて保つので,その値は開いた定義域の区間の中にある。集約を含む
それ以外の比較は,上の規則のままである。もう一方の被演算子が限量子または集約を持つ比較,
算術の中の比較(count(...) + 1 >= 2),および sum と avg のすべての比較である。sum と
avg は単調でない。さらに加わるメンバーや,未定義である要素の値は,それらをどちらの向きにも
動かし得る。すべての値が非負であるか有界であることがわかっていれば別であるが,言語はそれを
宣言しない。
ある観測での定義域とその既知のメンバーは,その観測までの観測だけによる。したがって, 限量述語と集約の値についても,下の判定の性質が保たれる。ある観測の後の判定は,その観測までの トレースの判定である。定義域が開いているためにある観測で未定義である述語は,メンバーが 名指されるか境界が値を持つと,後の観測で値を持つことがある。前の観測での値は未定義のまま である。
ワイルドカード参照と範囲参照
述語の中で,限量子と内包表記の定義域の外にあるワイルドカード参照 A[*] と
範囲参照 A[lo..hi] は,その参照を定義域とし,A のメンバー(範囲参照では範囲内の
メンバー)を動く限量子または内包表記の略記である。アクター名と,書かれたとおりの添字
(*,または同じ上下限)が同じである2つの参照は,同じグループに属する。A[*] と A[*] は
同じグループに属し,A[*] と A[1..3] は属さない。述語は次の2段階で書き換える。
- 集約の引数。
sum,count,min,max,avgの呼び出しf(e)で,ただ1つの 引数eが内包表記でないものを考える。内側の呼び出しから先に書き換える。この呼び出しは,eの中の参照のうち,さらに内側の集約の呼び出しの中にないものを束縛する。それらが 定義域Dの1つのグループをなすとき,f(e)はf(e' for x in D)を表す。ここでe'は,eの中のそのグループの参照をすべてA[x]で置き換えたものであり,xはほかのどこにも 現れない変数である。2つ以上のグループをなすときは,その呼び出しは評価しない(F.10)。 規範やcounts_as:の規則の中では誤りとする(N-16)。 どのメンバーを組み合わせるかは,内包表記で書く。 - 比較。 そのほかの参照は,それを含む最小の比較(
==,!=,<,<=,>,>=,IN)が 束縛する。どの比較にも含まれない参照は,次のうちそれを含む最小のものが束縛する。AND,OR,NOTの被演算子,限量子の述語,時相演算子の述語の引数,述語全体である。 束縛する部分sがグループG1,…,Gnを持つとき(各グループの最初の参照が書かれた順),sはfor all x1 in D1: ... for all xn in Dn: s'を表す。ここでs'は,sの中のGiの 参照をすべてA[xi]で置き換えたものである。
したがって,1つの比較の中では,同じグループの参照はすべて同じメンバーを表す。比較は すべてのメンバーについて成り立つ必要があり,グループが複数あるときは,それらのメンバーの すべての組み合わせについて成り立つ必要がある。異なる比較は,それぞれ独立に限量する。
| 述語 | 表すもの |
|---|---|
ROBOT[*].battery > 10 | for all j in ROBOT[*]: ROBOT[j].battery > 10 |
ROBOT[*].x > ROBOT[*].y | for all j in ROBOT[*]: ROBOT[j].x > ROBOT[j].y |
ROBOT[*].x == BASE[*].y | for all j in ROBOT[*]: for all k in BASE[*]: ROBOT[j].x == BASE[k].y |
NOT ROBOT[*].stopped | NOT (for all j in ROBOT[*]: ROBOT[j].stopped) |
ROBOT[*].x > 0 OR ROBOT[*].y > 0 | (for all j in ROBOT[*]: ROBOT[j].x > 0) OR (for all k in ROBOT[*]: ROBOT[k].y > 0) |
within(5s, ROBOT[1..3].ready) | within(5s, for all j in ROBOT[1..3]: ROBOT[j].ready) |
count(ROBOT[*].status == Collision) >= 2 | count(ROBOT[j].status == Collision for j in ROBOT[*]) >= 2 |
sum(ROBOT[*].load) > BASE[*].limit | for all k in BASE[*]: sum(ROBOT[j].load for j in ROBOT[*]) > BASE[k].limit |
書き換えた述語は,上と同じように評価する。したがって,開いた定義域の規則,処理系が列挙する
メンバーの数の上限,その観測までの観測だけによることは,変わらずに当てはまる。参照を束縛する
部分を比較とするのは,NOT,AND,OR と時相演算子が,ほかの場所と同じように
真理値を組み合わせるためである。NOT ROBOT[*].stopped は,停止していないロボットがあるとき
真であり,within(d, p) は,区間の各観測で p の定義域を読む。どのロボットも停止していない
ことは,限量子を用いて for all j in ROBOT[*]: NOT ROBOT[j].stopped と書く。著者の意図と
異なる可能性のある場合は,N-15が示す。そのうち3つは,1つの比較の中では1つのグループが1つの
メンバーを表すという規則から生じる。ROBOT[*].pos != ROBOT[*].pos は各ロボットを自分自身と比べ,
決して真にならない(位置が互いに異なることは
for all j in ROBOT[*]: for all k in ROBOT[*]: j == k OR ROBOT[j].pos != ROBOT[k].pos と書く)。
count(ROBOT[*].delivery == ROBOT[*].delivery) は配送を持つすべてのロボットを数える。
within(5s, ROBOT[*].status == Delivered) は,区間の1つの観測ですべてのロボットが配送済みである
ことを求める(各ロボットがそれぞれ5秒以内に配送することは
for all j in ROBOT[*]: within(5s, ROBOT[j].status == Delivered) と書く)。
メッセージ事象の参照はF.3のとおりに一致させ,書き換えない。規範の trigger:,until:,content:,
counts_as: の規則の when:,委任(付録G)の until: にある message_event について,
メッセージの引数の中のワイルドカード参照と範囲参照は誤りとする(N-16)。付録Gの fallback: など,
ほかのメッセージ事象はこの規則の対象外である。
この小節より前のバージョンでは,これらの参照は述語の中で値を持たず(付録AのA.10節),
リファレンス実装でこれを読む構成要素の読み方はそれぞれ異なる(F.10)。上の書き換えは,
本付録の以前のバージョンがその意味として示した限量子の形と,例の中の count(A[*]...) の
使い方に合う。
規範インスタンス
規範インスタンスは,次の6つの状態のいずれかにある。
| 状態 | 意味 |
|---|---|
inactive | まだ発効していない。 |
active | 発効中。義務または禁止が判定されている。 |
suspended | 一時的に発効していない(権能による)。期限と期間の時計は止まる。 |
fulfilled | 内容が期限内に実現された義務,または内容が起こらないまま期間が終わった禁止。 |
violated | 内容が実現されないまま期限が過ぎた義務,または内容が起こった禁止。 |
discharged | 履行も違反もされずに終わった。until:,権能,契約インスタンスの終了,または改正(F.6)による。 |
fulfilled,violated,discharged は最終状態である。バージョン0.1では,規範インスタンスは
1つの契約インスタンスにつき高々1回判定される。規範インスタンスが inactive でないときに
起こった発動条件は無視し,禁止は最初の違反だけを報告する。
-
発動。 規範インスタンスは
inactiveで始まり,次のときにactiveになる。- その
trigger:が起こったとき(メッセージが送られる,制度的事象が作られる,または述語が真になる)。 trigger:を持たず,他の規範のreparation:にも権能のactivate:の効果にも名指されていない 規範については,契約インスタンスが始まったとき。- それが修復する規範が違反されたとき(
reparation:),または権能がそれを発効させたとき(activate:)。
発動時刻は,規範が発効した観測の時刻印である。
- その
-
義務。 発効中の義務は,発動時刻以降の観測のうち,その
contentが起こる(メッセージまたは 制度的事象)か成り立つ(その観測の時点で評価したtpredicate)最初の観測でfulfilledになる。 発動時刻からsuspendedの間の時間を除いて測ったdeadline:が,そうならないまま過ぎるとviolatedになる。ちょうど期限の時刻の内容は期限内とし,義務がsuspendedである間の内容は数えない。 違反は,期限の後の最初の観測で起こる。内容が時相演算子を含むtpredicateである場合,ある観測での値は後になって決まることがある。義務は値が決まるまでpendingにとどまり, 期限までの観測だけを数える。 -
禁止。 発効中の禁止は,その
contentが起こるか成り立つ最初の観測でviolatedになる。 発動時刻からsuspendedの間の時間を除いて測ったdeadline:の期間が終わるとfulfilledになる。 ちょうど期間の終わりの時刻の内容は違反とする。停止中の禁止は判定しない。 -
許可と権能。 解除されるまで
activeにとどまる。 -
解除。
activeまたはsuspendedの規範インスタンスは,期限にかかわらず,そのuntil:が 起こったとき,または権能がそれを解除したときにdischargedになる。 -
契約インスタンスの終了。 契約インスタンスが終わると,最終状態でないすべての規範インスタンスを 確定させる。
deadline:のない発効中または停止中の義務はviolatedに,期限がまだ過ぎていない 義務はdischargedに,禁止はfulfilledに,inactiveのものを含むそれ以外の規範インスタンスはdischargedになる。例外が2つある。インスタンスが終わる観測で発効し,その観測の段階4で 最終状態にならなかった規範インスタンスは,発効の後に観測がないためdischargedになる。 内容のtpredicateの値がまだ決まっていない 義務または禁止は,そのままの状態にとどまり,判定はpendingである。この確定によって生じた違反は, その重大度とともに報告するが,インスタンスが終わっているため,reparation:とtransition:は 適用しない。 -
権能。 メッセージから作られた制度的事象は,そのメッセージの送信者が行ったものとする。 述語から作られた制度的事象には行為者がいない。発効中の権能の負担者がその
content(制度的事象, または負担者が送るメッセージ)を行うと,effects:が同じ契約インスタンスの規範インスタンスに 適用される。activateは未発効の規範を発効させ,suspendは発効中の規範を停止し,resumeは 停止中の規範を発効に戻し,dischargeは発効中または停止中の規範をdischargedにする。 他の状態にある規範への効果は何もしない。行為者の対応する権能が発効していないときにその行為が 行われた場合,効果は適用されない(制度的事象そのものは他の規範に対して存在する)。規範を監視する 処理系は,その行為を権限のない行為として記録することが望ましい。 -
違反。 規範インスタンスが
violatedになると,そのon_violation:が適用される。 指定のseverity:(既定値Major)で,規範のidをラベルとする違反が報告され,reparation:の規範が発動し,transition:があり,かつ契約インスタンスがまだ終端状態に なければ,契約インスタンスはその状態へ移る。
Counts-as
counts_as: 規則は,その when: が起こり(メッセージが送られるか,述語が真になる),
その観測で if: の条件(あれば)が成り立つと,契約インスタンスにその制度的事象を作る。
制度的事象は契約インスタンスに局所的である。制度的事象は事象としてのみ存在し,規範を発動させ,
終わらせ,履行させることができ,権能の内容になる。
1つの観測の中での順序
1つの観測に含まれる1つのメッセージが,制度的事象を作り,ある規範を発動させ,別の規範を履行させ,
ライフサイクル遷移を起こすことがある。処理系は次の順に,それぞれ直前の段階が残した状態に対して適用する。
段階1の前に,契約の assume: の項目,次に guarantee: の項目を評価する。したがって,ある観測で
破れた仮定は,その観測での違反を免責する。また,インスタンスの最初の観測では,それより前に,
インスタンスの開始時に発効する規範を発効させる。
counts_as:規則の制度的事象を作る。- 権能の効果を適用する(7)。権能は宣言の順に,1つの権能の中では
activate,suspend,resume,dischargeの順に適用する。権能が発効しているかどうかは,この段階の初めに決める。 - 発動条件が起こった規範を発動させる(1)。
- 発効中の規範を判定する。各規範について,過ぎた期限,内容,
until:の順に調べる(2,3,5)。 したがって,同じ観測では,期限切れによる違反が解除より先になり,内容がuntil:より先になる。 段階3で発動した規範もこの段階で判定するため,発動時刻の内容も数える。 on_violation:を適用する(8)。ここで発動した修復の規範は,次の観測で初めて判定する。- 付録Eのライフサイクル遷移を起こし,契約インスタンスが終わっていれば その規範を確定させる(6)。
有効でない契約
regimes: を持つファイル(付録AのA.7.1節)は,
モードごとに有効な契約を定め,各観測は1つのモードに属する(A.7.1節の「実行」)。cadl
0.3.33から,契約がいくつかの観測で有効でないとき,その契約インスタンスを次のように判定する。
契約は,それを有効としないモードの最初の観測の時刻に有効でなくなり,その後でそれを有効とする
モードの最初の観測の時刻に再び有効になる。観測での契約の時計は,その時刻印から,それより前に
契約が有効でなかった時間を引いたものである。契約が有効でない観測での時計は,有効でなくなった
ときの時計である。
契約インスタンスは,観測の射影に対して,この節の残りの規定で判定する。
- 射影は,契約が有効である観測を,その順に並べたものである。
- 射影の各観測は,報告するすべてのものと
nowについては自身の時刻印を保つ。期限(下の2と3),suspendedであった時間,時間演算子の区間(F.4)は,時計で測る。 - 観測される量とライフサイクルの状態は,すべての観測から得る。射影に含まれない観測で与えられた 値や状態は,値が変わるまで保たれるのと同じく,射影の次の観測から見える。
- 射影に含まれない観測で送られたメッセージは見えない。そのメッセージによって発動,履行,違反が 起こることはなく,制度的事象も作られず,権能も行使されない。
- 契約が有効でない観測で契約インスタンスが終わるとき(ホストが知らせる終了,終端状態,記録された
トレースの最後の観測),その観測は射影に含まれる。ただし,そこでは6の確定だけを,契約が有効で
なくなったときの時計で行う。項目は評価せず,ほかの手順も行わない。したがって,契約が有効で
なくなる前に期限が過ぎた義務は,そこで
violatedになる。
契約が有効でないあいだ,規範インスタンスは状態を保つ。権能が停止させた規範インスタンスと同じく,
期限と期間の時計は止まり,内容は数えない。権能による停止と異なり,active のインスタンスは
active のままであり,契約が再び有効になれば,権能はそれを停止または再開できる。インスタンスは
射影の最初の観測で始まる。その観測が,契約が有効でないあいだにインスタンスを終えるときは,
インスタンスの開始時に発効する規範を,確定の前にそこで発効させる。モードを名指さない観測は,
その前の観測のモードに属し,モードを名指す最初の観測より前の観測は初期モード(A.7.1節の
「実行」)に属する。したがって,モードを名指さない観測は,初期モードが契約を有効とするとき,
および契約が常に有効である regimes: のないファイルでは,cadl 0.3.33より前と同じく判定される。
判定
これまでに観測した有限のトレース上での,規範インスタンス,または時相演算子を含む保証の判定は, 次の4つの値のいずれかである。
| 判定 | 規範インスタンス | 契約の保証 |
|---|---|---|
pending | inactive,active,suspended | 観測した前半部分では決まらない |
fulfilled | fulfilled または discharged | 前半部分のどの続きでも成り立つ |
violated | 契約の仮定が1つも破れていない間に violated になった | どの続きでも成り立たず,その時点で仮定が1つも破れていなかった |
excused | 契約の仮定が破れた観測以降に violated になった | 仮定が破れた観測以降に成り立たなくなった |
仮定は,その値が偽になる最初の観測で破れる(時相演算子を含む項目では,値が偽に決まる観測である。F.4)。
値がまだ決まらない仮定や,値が未定義の仮定は破れていない。時相演算子を含まない assume: または guarantee: の項目は状態述語であり,すべての観測で
評価する。偽である最初の観測で破れ,契約インスタンスが終わるまで破れなかった保証は fulfilled になる。
状態述語と時相演算子が混ざった項目は tpredicate であり,インスタンスの開始時に1回評価する。
仮定がいったん破れると,同じ契約インスタンスの以後の違反はすべて excused になる。保証や規範が
excused になるのは,仮定が破れたときではなく,それ自身が破れたときである。解除された許可や
権能の判定は fulfilled とする。F.2の意味で履行されたわけではない。期限切れによる違反が
violated か excused かは,期限の時刻ではなく,違反が起こる観測で判定する。トレースが終わっても,
pending の判定は pending のままである。期限や区間の終わりより前に止まったトレースは,
それを決めない。区間がまだ終わっていない時相的な項目は,契約インスタンスが終わっても決まらない。
観測量の集合を契約インスタンスごとに固定すれば(上の「契約インスタンス」を参照),ある観測の後の
判定は,その観測までのトレースを,同じ集合のもとで前半部分として読んだときの判定である。判定は
それより後の観測に依存せず,pending 以外の判定は後から変わらない。したがって,処理系は,
システムの動作中に観測ごとに判定を計算してよい。量の集合が同じであれば,その判定は,記録した
トレースを読む処理系の判定と同じである。
量の名前を与えられず,観測から名前を得る処理系は,名前を,最初の値が届くまで記号値として読む。 そのような名前を最初の値より前に使う述語については,この処理系は上と異なる判定を与えてよい。 許される違いはこれだけである。このような処理系には,名前を与えることが望ましい。違いが生じるのは, その名前を文字列の値と比べる場合だけである。記号値のそれ以外の使い方は未定義であり,値のない量も 未定義だからである。
excused は,「負担者が果たさなかった」ことと「契約が仮定するものを負担者が与えられなかった」ことを
区別する。これは,義務論理に基づく実行時検証で責任を割り当てる基礎である
[Kharraz+, ICTAC 2023]。仮定を考慮することで,監視できる性質も増える
[Henzinger & Saraç, RV 2020]。バージョン0.1は,仮定のこの弱い読み方を
用いる。仮定が成り立たなくなった後もしばらく保証が成り立たなければならないという
5.4.1節の強い読み方は,バージョン0.1の判定では表さない。
excused となった規範も,その on_violation: は発動する。契約インスタンスへの帰結は
責任の所在に依存しないためである。報告される違反は,判定 excused を伴う。
F.6 改正
改正とは,契約インスタンスの動作中に,契約の定義を同じ id を持つ新しいバージョンで置き換えることである。
バージョンをどう作り,承認し,発効させるかはnorms 0.1の範囲外である。ハンズオン教材の
Course D はその手続きの1つを示している。新しいバージョンは,ある観測で,
その観測で他の何を評価するよりも前に発効する(仮定と保証の評価,およびF.5の段階1よりも前)。
したがって,改正によって発効した規範は,その同じ観測で判定する。規範インスタンスは次のように扱う。
active または suspended の規範インスタンスは,古いバージョンの規範の on_amendment: に従う。
on_amendment: | 効果 |
|---|---|
carry_over(既定値) | インスタンスは,新しいバージョンの同じ id の規範のもとで続く。状態と,期限に対してすでに経過した時間を保つ。新しいバージョンにその id の規範がない場合,またはその規範の kind が異なる場合は,代わりに discharged になる。内容が変わる場合,インスタンスはこの観測以降,新しい内容で判定し,判定待ちの候補(段階4がまだ判定していない候補。F.5。インスタンスの停止中に内容が決まったものを含む)を捨てる。内容が変わらない場合は候補を保つ。経過した時間がすでに新しい期限を超えている場合(ちょうど等しい場合は超えていない),期間は終わっている。判定待ちの候補を持たないインスタンスの状態は,新しいバージョンの発効時に,段階1より前に決まる。義務は,停止中のものも含めて violated になり,禁止は,停止中のものも含めて fulfilled になる。判定待ちの候補を持つインスタンスは効力を保ち,新しい候補を持たない。段階4がその候補を判定したときにインスタンスを決める。停止中のインスタンスでは,この判定は再開の後に行う。内容が成り立つ候補があれば義務は履行され,禁止は違反となる。成り立つ候補がなければ,義務は violated に,禁止は fulfilled になる。したがって,判定待ちの候補が新しい期間の中にあれば,判定は,インスタンスの開始時から新しいバージョンを適用した場合と同じになる。新しい期間の外にある候補も数える。その候補は古いバージョンのもとで生じたからである。判定待ちの候補を持つ停止中のインスタンスが再開されないまま契約インスタンスが終わると,そのインスタンスは pending のまま終わる(F.5)。 |
discharge | インスタンスは discharged になる。 |
transform: X | インスタンスは discharged になり,新しいバージョンの規範 X が inactive であればそれを発動させる。経過した時間は期限に算入する(義務と禁止の場合。許可と権能では時間は影響しない)。X が inactive でなければ,それ以上は何もしない。 |
表の各項目は,古いバージョンが規範を宣言している順に,新しい規範を発効させる前に適用する。
transform: の対象 X が新しいバージョンにない場合,インスタンスは discharged になるだけである。
inactive の規範インスタンスは,新しいバージョンの同じ id の規範の定義を引き継ぎ,新しいバージョンにその規範が
なければ取り除かれる。新しい定義が trigger: を持たなくても,改正によって発効することはない。
古いバージョンにその id の規範がないものを新しい規範という。新しい規範は inactive から始まり,
trigger: を持たず,修復や発動の対象でもなければ,ただちに発効する(F.5の1)。最終状態のインスタンス
(fulfilled,violated,discharged)は影響を受けず,その id は同じ契約インスタンスの中で
再び使わない。最終状態のインスタンスと同じ id を持つ新しいバージョンの規範には,新しいインスタンスを
作らない。特に,違反は,それが起きたバージョンのもとでの違反のままである。改正の後に起きた違反には,
新しいバージョンの on_violation: を用いる。
新しいバージョンの counts_as: 規則は,その発効時から適用する。両方のバージョンでテキストが同じ assume: または
guarantee: の項目は,その値を保って続く。新しい項目はこの観測から評価する(tpredicate はこの観測で
評価する)。取り除かれた項目は,それまでの判定を保つ。改正の前に破れた仮定は,以後の違反を
引き続き免責する。契約が lifecycle: ブロックを持つ場合,インスタンスの現在の状態は新しいバージョンの状態で
なければならない。そうでなければ,そのインスタンスに改正を適用できない。モード遷移(A.7)は
改正ではない。モード遷移によって規範が変わることはなく,モード遷移は,どの契約を有効とするかを通じてだけ契約インスタンスに作用する
(F.5節の「有効でない契約」)。cadl 0.3.32までは,この段落は,バージョン0.1ではモード遷移は
規範インスタンスに影響しないとしていた。
改正を適用する処理系は,新しいバージョンが発効する前に,引き継がれる規範のうち content または
deadline: が変わるものをすべて報告することが望ましい。
F.7 静的意味論
規範拡張を扱う処理系は,既存の検査に加えて,次の検査をしなければならない。
- N-1. 規範の
idは識別子でなければならず,予約語(付録EのINを 含む)であってはならず,契約の中で一意でなければならない。creates:の名前は識別子でなければならず, 同じ契約の規範のidと同じであってはならない(YAML 1.1のローダーでは,引用符のないyes,no,on,offは名前ではなく真偽値になる。A.12を参照)。 - N-2.
kind:はobligation,permission,prohibition,powerのいずれかでなければならない。 - N-3.
bearer:とcounterparty:は,宣言済みの1つのアクターを,添字なしで,整数の添字付きで (ROBOT[1]),または契約インスタンスが束縛する添字付きで(ROBOT[i])名指さなければならない。ワイルドカードや範囲(ROBOT[*],ROBOT[1..3])は許されない。契約の当事者を名指すことが望ましい。 - N-4.
deadline:はduration_litでなければならず,義務または禁止にだけ書ける。on_violation:も義務または禁止にだけ書ける。 - N-5.
effects:は権能にだけ書け,権能は少なくとも1つの効果を持たなければならない。effects:の各名前は,権能自身以外の,同じ契約の規範のidでなければならない。 - N-6.
on_violation.reparationは,trigger:を持たない,同じ契約の義務または禁止を 名指さなければならない。どの規範からreparation:をたどっても,その規範に戻ってはならない。 - N-7.
on_violation.transitionは,同じ契約のlifecycle.statesにある状態を名指さなければ ならない。したがって,その契約はlifecycle:ブロック(付録E)を 持たなければならない。 - N-8.
trigger:,until:,content:の全体として用いた識別子が,契約の制度的事象ではなく 規範のidであるときは,誤りの可能性が高いため,処理系は警告することが望ましい。 - N-9. 規範または
counts_as:規則のmessage_eventでは,送信者と受信者は宣言済みのアクターを 名指さなければならない。権能の内容は,それを作るすべてのcounts_as:規則がmessage_eventから 作る制度的事象,または送信者が負担者であるmessage_eventでなければならない。内容がmessage_eventである義務または禁止では, 送信者は負担者であることが望ましい。 - N-10. 時相演算子はF.4の引数を持たなければならず,その期間は0より大きい
duration_litでなければならず,F.4が許す位置の外に現れてはならない。 - N-11.
on_amendment:は,carry_over,discharge,または識別子Xを持つ{ transform: X }でなければならない(Xが新しいバージョンに存在するかは,そのバージョンに対してしか検査できない)。 - N-12. 同じ契約の許可と禁止が,同じ
bearer:と,テキストとして同一のcontent:を持つ ときは,両者が衝突するため,処理系は警告することが望ましい。 - N-13. 禁止の
trigger:がmessage_eventであり,トリガのすべての発生が内容の発生でも あるとき,処理系は警告することが望ましい。内容が,同じメッセージ名を持ち,内容が引数を持つ ときは同じ値の引数を持ち,トリガのアクター参照が一致するすべてのアクターに一致するアクター参照を 持つmessage_eventである場合(R[1..3]と宣言した集合についてのD -> R[i] : goとD -> R[1..3] : go),または,内容が,if:のないcounts_as:規則がそのようなメッセージから 作る制度的事象である場合である。この検査は最善の努力であり,そのような禁止をすべて見つける わけではない(たとえば,トリガのメッセージが真にする述語を内容とするもの)。そのような禁止は,それを発効させる観測で違反となる (F.5の段階4)。これが意図であることはまれである。2回目の発生の禁止は,状態についての 限量述語(F.5の「限量子と集約」)か,それより前の事象をトリガとしuntil:で区切った禁止で 書く。 - N-14. 限量子または内包表記の変数が,宣言した集合の記号の境界の名前を持つとき
(
S[1..N]についてのfor all N in S: ...),処理系は警告することが望ましい。境界は 限量子の中でも自分の値を保つ(F.5)が,読み手はそれを予期しないかもしれない。 - N-15. 述語のワイルドカード参照または範囲参照(F.5の「ワイルドカード参照と範囲参照」)が
NOTの下で束縛されるとき(NOT A[*].x > 3は,x <= 3であるメンバーがあれば真である), 2つ目のグループを持つ比較が束縛するとき(比較はメンバーのすべての組み合わせについて成り立つ 必要がある),そのグループがORの両方の被演算子で束縛されるとき(各被演算子はそれぞれ 独立に限量する),そのグループが1つの比較の両辺に現れるとき(集約の引数の中も含む。各メンバーを 自分自身と比べる),within,throughout,untilの述語の引数の中で束縛されるとき(すべての メンバーを1つの観測で見る),およびassume:またはguarantee:の項目で集約の引数が2つ以上の グループを持つとき(評価しない。規範やcounts_as:の規則の中ではN-16の誤りとする), 処理系は警告することが望ましい。警告では,著者が意図したと思われる限量子の形を示すことが望ましい。 - N-16. 規範の
trigger:,until:,content:,counts_as:の規則のwhen:, 委任(付録GのG-12)のuntil:のうちmessage_eventでも制度的事象でも ないもの,およびcounts_as:の規則のif:は, 付録AのA.10節の述語(content:ではtpredicate)であり, F.5が評価するものでなければならない(MUST)。その中の関数呼び出しは,N-10が許す場所での F.4の時相演算子か,内包表記または参照が1つのグループをなす引数のsum,count,min,max,avgでなければならない。限量子と内包表記の定義域はF.5が挙げるものでなければならず, それが名指す集合は集合(A[lo..hi])として宣言されていなければならない。ワイルドカード参照と 範囲参照の集合,および限量子や内包表記の変数を添字に使うアクター参照(Q[j])も同じである。 宣言されていない名前や単一のアクターはメンバーを持たないので,そのような述語は値を持つことがない。 整数の範囲を動く変数をx.qと書いてはならない。+,-,*,/の被演算子に文字列や真理値の リテラルを書いてはならず,/の除数にリテラルの0を書いてはならない。正確な数の範囲(F.5)の 外の数を拒否する処理系は,これらの述語の中のそのようなリテラルを誤りとして報告しなければならない。 これらの場所のmessage_eventのメッセージは,識別子か,そのような式を引数とする呼び出しで なければならず,引数はワイルドカード参照も範囲参照も含まない。N-16を満たさない規範や規則は評価できないので, 誤りとする。よくある誤りは次の2つである。2.5sはduration_lit(A.1)に当たらないので, 同じ時間は2500msと書く。'k'はstringに当たらないので,"k"と書く。
コアの検査との関係
6.3節の無矛盾性検査(SMTソルバーによる assume: と guarantee: の
充足可能性の検査)は状態述語に適用する。時相演算子を含む assume: または guarantee: の項目は
状態述語ではない。規範拡張を扱う処理系のうち時相述語を変換しないものは,そのような項目をSMT検査から外し,
外したことを報告しなければならない。演算子を解釈されない関数として扱ってはならない。
制度パラメータとの関係(参考)
5.4.2節のパラメータには,バージョン0.1では規範に関する形式的な意味を 与えない。後のバージョンで明確にする予定の読み方(9.6節のRD-6.1)は次のとおりである。 意思決定の集中度βは,契約の権能を誰が持つかを表す。情報共有度αは,他の当事者がどの発動条件と 内容を観測できるかを表す。インセンティブ強度λは,違反された規範の制裁の大きさを調整する。
根拠付け拡張(付録J,grounding 0.1)は,本付録を変えずに,
この読み方に関係する指標を定義する。βについては,契約の権能の集中である。αについては,宣言した
情報項目の共有である(発動条件と内容の観測可能性ではない)。λについては,戦略モデルがλを掛ける
制裁の数値の大きさと,制裁または報酬を伴う規範の数である。
F.8 例
次の契約は,付録EのE.6節の配送契約を簡略にし,規範を加えたものである。
cadl リポジトリの examples/norms_robot_delivery.cadl
から取り,一部を省略している。
sos:
name: "RobotDeliveryNorms"
extensions:
- sos-dsl: 0.1
- norms: 0.1
# アクター DISPATCHER,ROBOT[1..N],CUSTOMER[1..M] は付録Eと同じ
contracts:
- id: DELIVERY_SLA
parties: [DISPATCHER, "ROBOT[*]", "CUSTOMER[*]"]
assume:
- "throughout(300s, DISPATCHER.is_operational == true)"
guarantee:
- "within(300s, ROBOT[i].status == Delivered)"
lifecycle:
states: [Proposed, Assigned, Delivering, Completed, Violated]
initial: Proposed
terminal: [Completed, Violated]
transitions:
- { id: assign, from: Proposed, to: Assigned, on: "DISPATCHER -> ROBOT[i] : route_assignment" }
- { id: start, from: Assigned, to: Delivering, on: "ROBOT[i].status == InTransit" }
- { id: complete, from: Delivering, to: Completed, on: "ROBOT[i].status == Delivered" }
counts_as:
- when: "DISPATCHER -> ROBOT[i] : replan_command"
creates: reassignment
norms:
- id: acknowledge
kind: obligation
bearer: "ROBOT[i]"
counterparty: DISPATCHER
trigger: "DISPATCHER -> ROBOT[i] : route_assignment"
content: "ROBOT[i] -> DISPATCHER : ack(accepted)"
deadline: 5s
on_violation:
severity: Major
reparation: report_failure
- id: report_failure
kind: obligation
bearer: "ROBOT[i]"
counterparty: DISPATCHER
content: "ROBOT[i] -> DISPATCHER : failure_report"
deadline: 2s
on_violation:
severity: Critical
transition: Violated
- id: no_low_battery_driving
kind: prohibition
bearer: "ROBOT[i]"
content: "ROBOT[i].battery < 10 AND ROBOT[i].status == InTransit"
on_violation:
severity: Critical
sanction: "removed from the dispatch pool for one period"
- id: may_return_to_charge
kind: permission
bearer: "ROBOT[i]"
content: "ROBOT[i] -> DISPATCHER : charging_request"
- id: reassign
kind: power
bearer: DISPATCHER
content: reassignment
effects:
discharge: [acknowledge, report_failure]
on_amendment: discharge
acknowledge は経路の割当てで発動し,5秒以内に果たさなければならない。これが違反されると,
ロボットは2秒以内に故障を報告しなければならない(反義務の義務 report_failure。それまでは
inactive のままである)。これも果たせないと,契約インスタンスは Violated へ移る。
no_low_battery_driving,may_return_to_charge,reassign は発動条件を持たず,契約インスタンスの
開始時から発効している。配車係の replan_command は配車係が行う reassignment とみなされ,
権能 reassign が発効している間は,2つの義務をどちらも解除する。各規範は契約インスタンスごとに
1回しか判定されないため,同じインスタンスで後から経路の割当てがあっても新しい義務は生じない。
保証は,ロボットが契約インスタンスの開始から300秒以内に配送することを述べる。遅れた配送より前に
配車係が動作を止めた場合,その配送は violated ではなく excused になる。
F.9 中間表現(IR)への追加
シミュレータIR(E.7)の institution.contracts の各契約に,norms と counts_as の
2つのフィールドを追加する。E.7と同じく,IRはデータクラスをそのまま直列化したものであり,
入れ子のブロックを平らにする。
{
"norms": [
{ "id": "acknowledge",
"kind": "obligation",
"bearer": "ROBOT[i]",
"counterparty": "DISPATCHER",
"trigger": "DISPATCHER -> ROBOT[i] : route_assignment",
"until": null,
"content": "ROBOT[i] -> DISPATCHER : ack(accepted)",
"deadline_ms": 5000,
"on_violation_severity": "Major",
"on_violation_sanction": null,
"on_violation_reparation": "report_failure",
"on_violation_transition": null,
"effects_activate": [],
"effects_suspend": [],
"effects_resume": [],
"effects_discharge": [],
"on_amendment": "carry_over",
"transform_to": null }
],
"counts_as": [
{ "when": "DISPATCHER -> ROBOT[i] : replan_command",
"creates": "reassignment",
"if": null }
]
}
trigger,until,content,when,if は,E.7の規則と同じくテキストのまま保持する。
キー if は,直列化したIRでは if と書く。ホスト言語によっては,データクラスのフィールドにこの名前を付けられない。
on_violation_severity は,on_violation: ブロック全体を省略したときは null,
severity: なしでブロックがあるときは Major である。on_amendment は常に値を持ち,carry_over,discharge,
transform のいずれかである。transform_to は transform: の対象であり,それ以外のときは null である。
norms と counts_as は,それらを持たない契約では空のリストである。
F.10 リファレンス実装の状況
リファレンス実装(cadl 0.3)は,cadl 0.3.19からnorms 0.1を次のように実装する。
cadlはnorms:,counts_as:,およびF.4の時相演算子を構文解析し,cadl checkで 規則N-1からN-16を適用し(N-8,N-12からN-15,およびN-3とN-9の「望ましい」は警告とする。 N-13とN-14はcadl0.3.23から,N-15はcadl0.3.24から,N-16はcadl0.3.30から), 両ブロックをF.9のIRへ変換する。小数の期間に対するN-4とN-16の誤りは書き方(2.5sは2500ms)を示し, 一重引用符の文字列に対するN-16の誤りは二重引用符を使うように示す。cadl verifyのSMT検査は,時相演算子を含むassume:とguarantee:の項目を外し, それぞれを検査しなかったものとして報告する(F.7)。cadl codegenは,同じ項目をすべてのターゲットの 契約のコードから外し,コードにコメントを残して警告を出す。時相演算子はターゲットの言語へ変換しない。 Pythonターゲットは,これらの項目を別のモジュールで監視する。cadl0.3.25からは,OPAとSolidityの ターゲットも監視する(下記)。- 規範の数値の
deadline:は秒として読む。これは,A.12が ライフサイクルの期限について述べる寛容な形式である。cadl checkは,F.4に挙げた位置で時相演算子を探す。 テキストであるviolation.detect,incentives.rules,プロトコルのtrigger:,context.assumptionsの中は探さない。 cadl0.3.20からは,cadl norms-evalが,記録したトレース(JSON Lines。1行に1つの観測。形式はcadlリポジトリのREADMEに示す)から,1つの契約インスタンスについて,F.5の規範の状態,判定,違反, 制度的事象,権限のない行為を計算し,トレースが名指すF.6の改正を適用する。ライフサイクルの状態は トレースから取り,ライフサイクルの状態機械は実行しない。違反が求めるtransition:は報告するだけで, 適用しない。cadl0.3.21までは,メッセージ事象のアクター参照を広く一致させすぎていた。A[1..2]のような範囲がA[k]という名前のすべてのアクターに一致し,A[*]と束縛のないA[i]が,宣言した集合の外のアクターにも一致していた。cadl0.3.22は,F.3の表に 従って一致させる。trigger:,until:,content:,counts_as:規則でそのような参照を用いる ファイルについて計算した判定は,計算し直すことが望ましい。このリリースは,上限が記号である 集合の下限も調べる。トレースの時刻は,絶対値が253以下の有限の数であり,エポック秒も エポックミリ秒も受け付ける。トレースのメッセージのアクターと名前は,書かれたとおりに読む。 0.3.21がROBOT[2]と読んでいたROBOT[ 2 ]は,トレースの誤りである。これは意図した変更である。 記録したトレースの中で1つのアクターに2つの綴りがあると,名前を比較する検査が無効になるからである。また,契約インスタンスの 終了後の観測を完全に無視する。0.3.21までは,観測量の名前(F.5)をそれらの観測からも取っていたため, 終了後の観測が判定を変えることがあった。cadl0.3.22までは,限量子または集約を含む規範や 項目を評価しなかった。cadl0.3.23からは,F.5(「限量子と集約」)の定めるとおりに評価する。閉じた定義域の メンバーは10 000個まで列挙し,それより大きい定義域は警告を出して開いた定義域として評価する。cadl0.3.23までは,限量子や内包表記の定義域の外のワイルドカード参照や範囲参照 (ROBOT[*].battery > 10)を含む規範や項目を評価しなかった。cadl0.3.24からは,契約を 読むときにそのような述語をF.5(「ワイルドカード参照と範囲参照」)の定めるとおりに書き換え, その結果を限量子と集約のコードで評価する。導入する変数には,述語に書けない名前を付ける。 そのような参照を持たないファイルの結果は変わらない。同じリリースから,F.5のcount,max,minの比較(「比較の中の単調な集約」)を既知のメンバーから決める。0.3.23までは,開いた 定義域の上と,要素が未定義であるときには未定義であった。 時相演算子と内包表記のsum,count,min,max,avg以外の関数呼び出し,2つ以上の グループの参照を持つ集約の引数,メッセージ事象の引数の中のワイルドカード参照や範囲参照, 定義域がアクターの集合でも範囲でもない限量子や内包表記,整数の範囲を動く変数xについてのx.q,内包表記の中の時相演算子のいずれかを含むものは評価しない。そのようなassume:やguarantee:の項目はpendingのままにし,その理由を報告に示す。cadl0.3.29までは,そのような 規範やcounts-as規則,および述語として読めないもの(until(p, q, 2.5s)やx == 'k'など)も 評価しなかった。規範は警告とともにinactiveのままであり,cadl checkは述語でないテキストを, 時相演算子を含まないときに限り警告として報告した。宣言した集合でない名前を定義域とする限量子, 集約,ワイルドカードはcadl checkを通り,常に未定義であった。形の正しくないメッセージ事象は 発生しなかった。cadl0.3.30からはこれらをN-16の誤りとし,検査していないファイルを与えられた場合も,cadl norms-eval,F.10と付録Dのモニタ,norms-check,付録Gのランタイムは,そのような規範,規則, 委任のuntil:と,期間でないdeadline:を持つ規範を拒否する。0.3.29までは,そのような期限を 期限なしとして読み,ランタイムはそのような委任のuntil:を警告するだけで,委任を終わらせなかった。cadl norms-diffは,ファイルの2つのバージョンを比べ,F.6が各契約の規範に何をするかを報告する。 引き継がれる規範のうちcontentまたはdeadline:が変わるものと,新しいバージョンにないtransform:の対象を含む。cadl0.3.27からは,テストがcadl norms-diffと,改正の時点でcadl norms-evalが行うことを比較する。 バージョンの組は,規範を持つ同梱の例から作る。古いバージョンにはランダムなon_amendment:を与え, 新しいバージョンは,古いバージョンの期限(整数でないものを含む)と内容を変え,内容を時間的なものにし, 種類を変え,規範を追加し(修復の対象としての追加を含む),規範を取り除き,規範を停止または再開する権能を 加えたものとする。トレースは,F.12のモデルの環境の選択をランダムに選んで作る。改正より前の観測は古い バージョンのモデルから,改正の観測とそれ以後の観測は新しいバージョンのモデルから取り,改正はランダムな 観測で行う。各規範インスタンスについて,新しいバージョンが発効した直後の状態と,期限に対して経過した時間を,norms-diffの所見と,改正の前の状態および判定待ちの候補だけから予測し,norms-evalと比較する。 予測する状態は,経過時間を保った引継ぎ,経過時間が新しい期限を超えたための違反または履行,判定待ちの 候補による効力の維持,解除,古い規範の経過時間をともなう変換,削除,追加(ただちに発効するもの,またはinactiveのもの)である。判定待ちの候補が期限を過ぎたインスタンスの効力を保つ場合は,その後の決定を, 内容だけから計算した候補の値と照合する。手で書いた8つの組により,F.6の表のうち現れにくい行も毎回の 実行で現れる。3 000個のランダムな組で差異はなく,2つのコマンドのいずれかに入れた16個の誤りはすべて 検出される。F.12のモデルに入れた2つの誤りも,改正の後も続く経路で検出される。この比較とそのレビューで, 0.3.26のnorms-eval,Pythonのモニター,F.12のモデルに2つの欠陥が見つかった。第1に,引き継がれた 禁止のうち,経過時間が新しい期限を超えたものを,その観測の段階4までactiveのままにしていた。 そのため,同じ観測の権能がその禁止を停止できた。また,停止中の禁止は停止中のままであった。F.6では, そのような禁止は新しいバージョンの発効時にfulfilledになる。第2に,期限を過ぎた義務を,時間的な内容の 判定待ちの候補がまだ義務を履行しうる場合にも,改正の時点で違反としていた。0.3.27は,F.6が述べる 規則を適用する。判定待ちの候補を持たない期限切れのインスタンスは改正の時点で決まり,候補を持つものは その候補で決まる。予測のために,0.3.27からのnorms-diffは,on_amendment:がdischargeである規範,transform:の対象の種類,短くなった期限が義務と禁止に与える効果も報告し,期限を厳密に比較する。 0.3.26までは期限をミリ秒に丸めて比較していたので,norms-evalが区別する2つの数値の期限を等しいと 報告することがあった。cadl0.3.22からは,cadl codegen -t pythonが,norms: 0.1を宣言したファイルに対して, 生成するパッケージにモジュールnorms_monitor.pyを出力する (付録DのD.1節)。このモジュールは,システムの動作中に 1つの契約インスタンスを監視する。ホストはインスタンスに対してモニターを作り,観測を1つずつ渡す。 モニターは,その観測で状態または判定が変わった規範インスタンス,保証,仮定を,時刻と理由とともに返す。 ホストはインスタンスの終了を通知し,現在の判定を問い合わせることができる。モジュールは,cadl norms-evalの評価コードをそのまま写したものと,ファイルの契約をデータにしたものを含む。 実行時にcadlを必要とせず,記録したトレースに対してはcadl norms-evalと同じ結果を与える。 このコマンドと同じく,ライフサイクルの状態は観測から取り,transition:は報告するだけで適用しない。 観測を1つずつ受け取る処理系についてF.4とF.5が述べる点は,次のように扱う。過ぎた期限と区間の 終わりは,次の観測で検出する。モニターは,時間が経過するだけで決まるものについて,それが確実に決まる最も早い 時刻印をホストに知らせる(期限の時刻ちょうどの内容は期限内であるため,期限または区間の終わりより わずかに後である)。アクターを付けずに書かれた量の名前は ホストが指定する。指定のない名前は,最初の値が届くまで記号値として読む。これはF.5が許す違いである (cadl norms-evalは,名前を,トレースの中のインスタンスの観測から取る)。インスタンスの終了後の 観測は何の効果も持たず,その数を警告に示す。形式の誤った観測と,改正を適用できない観測は拒否し, モニターは元のままである。インスタンスの観測は,モニターを捨てるまで保持する。改正(F.6)は, 新しいバージョンから生成したモニターのデータをホストが与えた場合に適用する。モニターはCADLファイルを読めない。cadl codegenは,モジュールを書き出す前に,それがコンパイルできること,および使う名前がすべて その中で定義されていることを検査し,そうでなければ生成を拒否する。cadl0.3.25からは,cadl codegen -t opaと-t solidityが,norms: 0.1を宣言したファイルの 契約ごとに規範のモニターを出力する (付録DのD.5節)。 Regoのモニターはステップ関数である。直前の状態と1つの観測から,モニターの次の状態(ホストが保存する JSONオブジェクト)と変化を計算する。Solidityのモニターは状態を保存するコントラクトであり,観測の 時刻を引数として受け取る。どちらもcadl norms-evalと同じくF.5の1つの観測の順序に従い,観測を 1つずつ受け取る処理系についてF.4とF.5が述べる点はPythonのモニターと同じように扱う。述語の限量子, 集約,ワイルドカード参照と範囲参照,式である添字,改正は評価しない。規範,counts-as規則,assume:の項目でこれらのいずれかを使う契約にはモニターを生成せず,その構文を示す警告を出す。 そのようなguarantee:の項目は警告を出して外す。Solidityのモニターはさらに,*,/,小数点以下が 6桁を超えるリテラル,時相演算子の中の時相演算子,デプロイ時のコード(creation code)がEIP-3860の上限を超えるモニターを 拒否する。また,時相演算子の中で読むアクターを付けない名前を最初の観測より後に既知にする観測を 拒否する。cadl0.3.26からは,時相演算子を1つ含む規範の内容をその演算子(NOTの下では双対の演算子)に 帰着させ,1つの内容に含まれる2つの時相演算子,NOT until(...),比較の中の時相演算子を拒否する。また, 時相的な内容の候補をまとめて判定するので,観測のガスは区間の中の観測の数とともには増えない。cadl0.3.28からは,NOTの下,比較の中,INの中にある1つの時相演算子を含む内容も判定する (NOT until(...)はD.5のreleaseで判定する。未定義の値があってもuntilと双対になることをD.5で示す)。 時相演算子を2つ含む内容は,その候補をセグメント木にして判定し,3つ以上含む内容は拒否する。cadl0.3.29からは,1つの内容に含まれる4つまでの時相演算子を判定する(セグメント木の節点は, 演算子が3つまでは1つの語,4つでは5つの語である)。また,withinまたはthroughoutの被演算子が, 時相演算子を含まない被演算子に対するwithinまたはthroughout,あるいはその否定である内容も判定する。 内側の演算子を観測ごとに決め,決まった値を観測の順に外側の演算子に渡す。これがF.5と等しいことはD.5で示す。cadl0.3.31からは,1つの内容に含まれる5つの時相演算子(節点は25の語)と,このような入れ子の任意の段数 (within(5s, throughout(3s, NOT within(1s, p))))も判定する。各段は,決まった値を観測の順に,等しい値の 範囲ごとに1つ外側の段に渡す。cadl0.3.32からは,拒否していた内容,すなわち1つの内容に含まれる6つ以上の 時相演算子,入れ子の中のuntil,そのほかの時相演算子を含む被演算子(within(5s, throughout(2s, p) AND r))を 観測ごとに判定する。各時相演算子は各観測での被演算子の値と自身の値を持ち,観測はそれが決めうるものだけを 読み直す(D.5)。規範の内容の外にある時相演算子の中の時相演算子は拒否する。 このとき本体のコントラクトの実行時コードは,EIP-170の上限まで7 × 103バイト以上の余裕を持つ。Regoのモニターは,結果が十進数になるとは限らない/を拒否する。どちらも数と時刻を F.5のとおり正確に計算し,制限を満たす入力ではcadl norms-evalと一致する。制限はD.5に 挙げる。cadl0.3.26からは,cadl norms-eval,Pythonのモニター,cadl agents-run,Regoのモニターは F.5の範囲を超える数を拒否し(行番号を示すトレースの誤り),数で書いたdeadline:を正確に扱う。リファレンス実装は,観測ごとに両方のモニターをcadl norms-evalと比べる。 SolidityのモニターはEVMで実行して比べる。- Unity C#のターゲットは規範を監視しない。
cadl0.3.26からは,数と時刻をF.5のとおり正確に扱う。cadl0.3.25までは,cadl norms-eval, Pythonのモニター,cadl agents-runは二進の浮動小数点数で計算し,時刻を10-9秒の 許容誤差で比べていた。そのため0.1 + 0.2 == 0.3は成り立たず,観測から浮動小数点数の間隔 (エポック秒の付近で約2.4 × 10-7秒)以内にある期限は,期限内と期限後を取り違えて判定することが あった。サンプルのトレースとcadlのテストのトレースは,どちらでも同じ判定になる。cadl0.3.25からは,cadl norms-checkがF.12を実装する。1つの契約インスタンスのモデルを作り (--bindings,--members,--step,--horizon。cadl0.3.26からは,算術のための--domain,複数のインスタンスのための--instanceと--instances,改正のための--versionも), PRISM 4.11(PATH上のprism。明示的エンジンで, 戦略を出力させる)で問いを実行し,すべての証拠をcadl norms-evalのエンジンで評価する。--timeoutは,PRISMのすべての実行に使う時間の合計を制限する(既定は600秒)。PRISMがなければ, 何も検査しなかったことを報告して終了ステータス0で終わり,モデルと性質は書き出せる(--export)。--require-checkerを指定すると,PRISMがないことを誤りとする。Stormは使わない。変換は, 生成したPRISMのテキストを,それが使う部分を読む解釈器で実行し,cadl norms-evalと照合して試験している。 実行する経路は,環境の選択のランダムな経路と,小さな契約について観測が2個以下(複数のインスタンスと 改正では1個)のすべての経路である。比べるのは,各観測での各規範の状態である。また,すべてのJSONの型の ランダムな値が,モデルのいずれかのクラスに入ることを確かめている。解釈器はPRISMのシミュレータが生成した経路と比べ, PRISMの答えは到達可能な状態についての明示的な不動点計算と比べている。cadl0.3.28からは,cadl norms-checkは,複数のインスタンスの それぞれの開始を環境に選ばせる(既定は--starts any。--starts togetherはそれまでのモデルを使う)。 また,複数のインスタンスと組み合わせた改正を変換し,--domainのない線形の算術,sum,avgを 線形の配置の面によって,有限小数の点を持つ面のそれぞれから有限小数の点を厳密に1つ取って変換し,それ以外の算術で--domainがないときは,リテラルから求めた定義域を 仮定して報告し,それに依存する指摘に印を付ける。0.3.28は,互いに大小を比べる4個以上の量を引き続き拒否する。 いずれも,上と同じくcadl norms-evalと照合している。それぞれの開始を持つインスタンスは,ランダムな 経路と,選択が2つの場合に,観測が3個以下のすべての経路(開始と終了のすべての順序。長い実行では4個以下)で調べる。2つの インスタンスの改正は,バージョンが2個と3個の場合について,改正の後に始まるインスタンスを含む ランダムな経路で調べる。線形の算術は,ランダムな経路,多くが超平面の上にある有限小数の格子の値, 2つの量の格子のすべての点,少数の点しか達しない面の点で調べる。大きい係数や,2と5以外の素因数を持つ 係数を持つランダムな線形の述語は,総当たりで求めた有限小数の点と照合する。変換に意図的に誤りを入れると,これらの 試験は次のように検出した。開始では6個のうち5個(残りの1個は,どのインスタンスも動かない観測を許す もので,どのトレースも変えない),複数のインスタンスの改正では6個のすべて,拒否では2個のすべて, 算術では10個のすべて,面の有限小数の点の探索に上限を戻したものでは3個のすべてである。レビューにより, この探索の最初のバージョンが上限で探索をやめ,有限小数の点を持つ面を落としていたことがわかった。 現在の探索は厳密である。例はnorms_check_starts.cadl,norms_check_amend_v1.cadlとnorms_check_amend_v2.cadl,norms_check_linear.cadlである。cadl0.3.29のcadl norms-checkは,互いに大小を比べる4個の量からなる まとまりを,型とパターンによって変換する(F.12)。ほかのリテラルを持たない4個の量の値の組は26035個であり, 参照実装はそれを約2秒で作る。それらについての4個の述語を持つ契約は,選択が68,コマンドが272,到達可能な 状態が1626で,PRISMによる検査は約20秒である。互いに比べる5個以上の量からなるまとまりは,大小を比べる か等しさだけを調べるかによらず,型ごとのパターンの数と値の組の数を示して拒否する。これらの数は値の組を 作る前に計算するので,拒否は1秒以内に終わる。リストのパターンは,4個のリストの矛盾のないすべての パターン(355通りのうち331通りが直並列)と,4個と5個のランダムな入れ子のリストと照合している。値の組は, 入れ子のリストとオブジェクトを含むあらゆる型のランダムなJSONの値と照合している。数とテキストの リテラルを持つ4個の量については,密な数(1つの区間に4個),テキスト,オブジェクト,リストのそれぞれの すべての4個の組と,あらゆる型からなる小さな集合のすべての4個の組とも照合している。モデルは,ランダムな 経路と証拠によってcadl norms-evalと照合している。また,2個と3個の量のまとまりについて,型と パターンによる値の組をクラスの積と比べている。構成に14個の誤りを入れると,これらのテストはそのうち 13個を検出した。残りの1個はオブジェクトを2種類までに限るものであり,選択は変わらない。互いに比べられない リストが,異なるオブジェクトと同じ結果を与えるからである。cadl0.3.31からは,cadl norms-eval,Pythonの監視,エージェントのランタイムで,リストまたはオブジェ クトを被演算子とする算術は,上のとおり未定義である。0.3.30まではPythonの演算子を適用していた([1] + [1]は[1, 1],2 * [0]は[0, 0]であった)。cadl0.3.31からは,cadl norms-checkは,0.3.30が拒否したまとまり,すなわち互いに比べる5個以上の量, 与えられた定義域または仮定した定義域を持つ互いに大小を比べる4個以上の量,線形の算術を含む互いに大小を比 べる4個以上の量(面の点の制限の範囲で)を,消去によって変換する(F.12)。0.3.30が変換したまとまりの値の 組とモデルは変わらない。負荷の高い計算機で測ると,互いに大小を比べる5個,6個,8個,12個の量の鎖は1秒以 内である。8個の量の鎖についての4個の述語を持つ契約は選択が66で,PRISMによる検査は約12秒であり,証拠はす べて確認された。exists j in R: exists k in R: R[j].load < R[k].loadは,要素が6個なら約1秒,8個なら約 12秒である。線形の算術を含む互いに大小を比べる5個の量は約4秒である。max(r.load for r in R) > D.loadは,要素が5個なら約40秒であり,6個では拒否する。消去は,テストの契約と例のすべてのまとまりについて,ク ラス,型とパターンによる値の組,配置の点と比べている(リストを残す場合も比べている)。また,5個から12個 の量と6個の要素について,あらゆる型のランダムなJSONの値と比べ,対称性を使わない消去とも比べている。長い テストでは,互いに大小を比べる5個の量の型とパターンによるすべての値の組とも比べている。- ほかの構成要素は,定義域の外のワイルドカード参照をそれぞれの方法で読み,
cadl0.3.24は それらを変えない。cadl verifyは,A[*].qを,グループごとに1つの制約のない変数として読み, その変数を契約のすべてのassume:とguarantee:の項目で共有する。したがって,これもメンバーを 動かない。SolidityとOPAのターゲットの契約のコードと,Unity C#のターゲットの述語評価器は, 添字を落としてA[*].qを1つの量A.q(Unityでは契約インスタンスのスナップショットの量)として 読むので,メンバーを動かない。Pythonターゲットの契約のコードは,集合の名前Aをアクターの表で 引くが,表はメンバーをそれぞれの名前(A[1])で保持するので,参照は値を持たない。 Pythonターゲットは,count(ROBOT[*].status == Collision) >= 2のようなプロトコルの条件を コメントとして残し,cadl sim-genのシミュレータ生成器は述語をテキストとして写す。したがって, 付録Eのモニターとシミュレータの出力はcadl0.3.23と同じである。 cadl0.3.33から,cadl norms-evalとPythonターゲットの規範のモニターは,あるモードで有効で ない契約を,F.5節の「有効でない契約」のとおりに判定する。トレースの観測は,キーregimeで 現在のモードを名指す。このキーは,R-1からR-6を満たすregimes:ブロックを持つファイルでだけ 使え,その値はファイルのモードでなければならない。このキーを含まないトレースは,全体が初期モードに ある。regimes:のないファイルと,初期モードが契約を有効とする場合には,cadl0.3.32と同じ 結果を与える。regimes:のないファイルから生成されるモニターは,これまでと同じモジュールである。 結果のobservationsは射影の観測の数を数え,契約が有効でないあいだに終わったインスタンスのend_reasonはそのことを示す。モードを名指すトレースは,契約を改正(amend)できない。 初期モードが有効としない契約のトレースも,モードを名指さなくても,契約を改正できない。cadl norms-evalはそのトレースを拒否し,モニターはその観測を拒否する。モニターでは,契約が 有効でない観測は変化を返さず,in_forceは契約が有効かどうかを示し,next_deadlineとnext_checkは契約が再び有効になるまでNoneである。cadl0.3.36からは,RegoとSolidityの ターゲットの規範のモニターも同じようにモードに従う(Regoでは観測のキーregime,Solidityでは オーケストレータのsetRegime。付録DのD.5節)。 0.3.33から0.3.35までは,あるモードで有効でない契約についてこれらを生成しなかった。 ほかの契約については,パラメータを読む規範がないので,束縛は判定を何も変えない。cadl norms-check(F.12)は変わらず,契約をその時計で判定する。最後の有効な観測までの トレースの射影は,契約のトレースである。契約が有効でないあいだに終わるインスタンスは,有効で なくなったときの時計の時刻に,新しい値もメッセージもない観測をもう1つ置いて終わるインスタンスと 同じに確定する。ただし,そこで未確定の時相の内容はpendingのままである。したがって, 可能性の問いへの答えは射影についても成り立つ。必然性の問いは,これまでどおり,ホライズンまで 続くインスタンスを前提とし,ここではその時計で続くことを前提とする。付録Gの 決定関数と生成する境界方針は,cadl0.3.36から方針の入力から現在のモードを読む(G.10)。 付録Gの実行環境とゲートウェイもcadl0.3.36から現在のモードに従う。トレースの行のキーregimeをcadl norms-evalと同じく読み,各契約インスタンスをその契約の時計で判定する(G.13)。0.3.33から0.3.35までは, 強制される契約を有効としないモードがあるファイルを拒否した。cadl0.3.34から,cadl norms-evalとPythonターゲットの規範のモニターは, 付録KのK.11節の実行の バージョンを適用する。ファイルの後のバージョン(--version,またはそのモニターのモデル。モデルは,amendが参照するversionsとは別の引数run_versionsで与える)と,その効力の 発生時点の時間の基準を与えるか,観測がキーversionで効力を持つバージョンを名指すトレースを与えると, 経過規定が契約インスタンスを切り替える観測でそのインスタンスを改正し(F.6節),バージョンを保つときは 改正しない。cadl0.3.34までは,そのトレースはamendを持てず,モードを名指す実行と,初期モードが 契約を有効としない実行はバージョンを持てず,モニターは,amendを適用した後は,バージョンを名指す 観測を拒否した(0.3.35からは,下のとおりこの3つを扱う)。 後のバージョンも時間の基準もなく,このキーを含まないトレースは,改正拡張を宣言したファイルでも, これまでと同じに判定する。契約の経過規定がkeepまたはin_states:を持つswitchである バージョンへのamendは,これまでどおり適用し,警告を出す(cadl norms-evalでは標準エラー出力, モニターではamend_warnings,cadl agents-runでは警告の一覧)。cadl norms-checkは,cadl0.3.34と0.3.35では, 契約の経過規定がkeepまたはin_states:を持つswitchである後のバージョン(--version)を 拒否した。0.3.36からは,K.11のとおりにモデル化する(F.12)。RegoとSolidityのターゲットの規範の モニターは,previous:を持つバージョンに動いているインスタンスが切り替わる契約については生成しない (D.5節)。ただし,0.3.36から,実行のほかのバージョンとともに生成するモニターは除く。cadl0.3.35から,cadl norms-evalとPythonターゲットの規範のモニターは,モードを名指す実行と, バージョンがモードを束縛する実行にもバージョンを適用する (付録KのK.11節の「バージョンとモード」)。契約は 効力を持つバージョンの束縛によって有効になる。契約が有効でないあいだに効力を持つバージョンも,その 観測でインスタンスに及ぶ(keep,switch,待っているswitch)。切り替えによる改正だけが射影の 次の観測まで待ち,そこで契約の時計の上で適用する(K.11節の「バージョンとモード」の4.)。amendment:ブロックを持たないファイルの トレースもキーversionを持てる。ファイルのsos.versionは受け付け,それ以外の値は,切り替える 先のバージョンをファイルが宣言していないことを示すトレースの誤りである。バージョンのあるトレースはamendも持てる。1つの観測では,効力を持つバージョンを先に適用し,その後でamendを適用する。amendは待っている切り替えを取り消す(K.11節)。0.3.34まではそのようなトレースを拒否した。バージョンとモードの束縛を組み合わせるときは, 今も拒否する。cadl agents-runと ゲートウェイは,バージョンの効力の発生時点で執行点を切り替える(K.9節)。
F.11 後方互換性
本拡張を用いないCADL v0.3のファイルは引き続き有効であり,同じように読まれる。
norms: 0.1 を宣言せずに norms:,counts_as:,または時相演算子を用いるファイルは,
本付録に適合しない。規範拡張を扱う処理系は,そのようなファイルでは within,throughout,until を
ふつうの関数名として読み,norms: と counts_as: のブロックを解釈せず(検査もIRへの変換もしない),
宣言されていない拡張のキーとして報告することが望ましい。本拡張を実装していない処理系は,
そのようなファイルを拒否してはならない。ファイルごとに1つの情報レベルの診断を出すことが望ましい。
F.12 モデル検査器による設計時の検査
F.5は,1つの契約インスタンスの規範を1つのトレースについて判定する。本節は,1つの契約インスタンスの 規範を,PRISM言語 [Kwiatkowska+, CAV 2011] の有限のマルコフ決定過程(MDP)に 変換する方法を定める。このMDPの経路は,長さが上限以下であるそのインスタンスのトレースのすべてである。 モデル検査器は,トレースがまだない設計の段階で,すべての振る舞いについて次の問いに答える。規範はそもそも 違反されうるか。義務が発効するたびに,それを守る続きがあるか。2つの規範は衝突するか。権能は一度でも 行使されうるか。モデルは確率を持たない。選択はすべて環境の非決定的な選択であり,問いは定性的である。 同じ行為を義務づけ,かつ禁止する規範の検出は,規範的なマルチエージェントシステムで知られた問題である [Vasconcelos+, JAAMAS 2009]。SymboleoPCは,法的な契約の性質をモデル検査器 nuXmvで検査する [Parvizimosaed+, SoSyM 2025]。本節は,このような検査を 提供する処理系のためのものであり,F.1からF.11を変えない。
契約インスタンス
モデルは,1つの契約と1つの契約インスタンスについて作る。契約の添字変数(ROBOT[i] の i)は
固定した値を持ち,アクターの集合はそれぞれ固定した数nの要素 A[lo] から A[lo+n-1] を持つ。上限が
整数である集合では,nは宣言した大きさ以下である。メッセージ事象の中の A[*],A[lo..hi],束縛の
ない A[i] は,F.3の表で一致するインスタンスの要素を表す。上限が記号である集合(ROBOT[1..N])では,
インスタンスはNを要素の最後の添字に束縛する。Nを束縛したトレースと同じ扱いである。そのため,述語の中の
限量子,集約,ワイルドカード参照(F.5)は,閉じた定義域,すなわちインスタンスの要素を動く。上限が
整数である集合では,定義域は宣言した集合である。インスタンスのnを超える要素は,モデルではメッセージを
送らず,値も持たない。報告はそのことを示す。
複数の契約インスタンス
モデルは,同じ契約の複数のインスタンスをそれぞれの束縛とともに持つこともできる(リファレンス実装では,
繰り返し指定する --instance,または --instances N)。インスタンスは,観測(ステップと上限)と環境の選択
(すべてのインスタンスのメッセージ事象と,どのインスタンスでも同じ量)を共有する。各インスタンスは,
それぞれの規範インスタンスとその状態,制度的事象,仮定とその破れ(したがって判定 excused もインスタンス
ごと),開始,終了を持つ。
各インスタンスの開始は環境が選ぶ。各観測で,まだ始まっていないインスタンスは,順序によらず,その観測で
始まってよい。上限までに始まらなかったインスタンスは上限で始まる。最初の観測ではいずれかのインスタンスが
始まり,どの観測でも,始まっていて終わっていないインスタンスか,その観測で始まるインスタンスがある。
どのインスタンスも動かない観測は何も変えないので除く。これで失われるトレースはない。任意の終了の
読み方では,各インスタンスは開始以後のそれぞれの観測で終わり,上限まで続く読み方では,すべて上限で終わる。
インスタンスの状態は,開始の前と終了の後には変わらず,それらの観測はそのインスタンスに属さない(F.5)。
インスタンスの最初の観測は,F.5の意味でのインスタンスの開始である。発動条件がなく対象でもない規範はそこで
発効し,立ち上がりを事象とする述語はそこでは前の値を持たず,assume: の項目の区間はそこで始まる。
インスタンスのトレースは,開始から終了までの観測を,共有する観測の時刻とそのインスタンスの束縛とともに
並べたものであり,モデルはこれらのトレースのそれぞれについて,1つのインスタンスについてF.12が述べる
とおりに厳密である。上限は共有するので,観測sで始まるインスタンスの観測は高々H − s + 1個であり,報告はそのことを示す。
より大きい上限は,遅く始まるより長いインスタンスを扱う。インスタンスをまたぐ衝突には,異なる開始を必要とするものがある。たとえば,ある
インスタンスの修復が効力を持つ間に別のインスタンスが始まり,その修復が禁じることを義務づける場合である。
処理系は,代わりにすべてのインスタンスを最初の観測で始める読み方を用意してもよい(リファレンス実装
では --starts together)。この読み方はコマンドが少なくて済むが,異なる観測で始まるインスタンスの
トレースを含まない。報告は,どちらの読み方を使ったかを示す。問いは,すべてのインスタンスのすべての規範(インスタンスkの規範は
id@k と呼ぶ)について問い,衝突は,同じインスタンスまたは異なるインスタンスの義務と禁止のすべての組に
ついて問う。たとえば,あるインスタンスの規範の負担者が,別のインスタンスの規範が禁じることを義務づけられる
とき,インスタンスをまたぐ衝突が生じる。証拠は,同じ観測からなる,すべてのインスタンスのトレースを持ち,
それぞれをそのインスタンスの束縛でF.5により評価する。バージョン0.1ではインスタンスは4個までである。
n個のインスタンスの1つの観測での開始と終了は,コマンドの数を高々4n倍にする(各インスタンスは,
始まる,終わる,その両方,そのどちらでもない,のいずれかである)。ともに始まる読み方では2n倍である。
改正
モデルは,ファイルの後のバージョンも持てる(リファレンス実装では,繰り返し指定する
--version FILE)。環境は,各観測で,契約を次のバージョンに改正するかどうかを選ぶ。改正はバージョンごとに
高々1回,その順序で起こる。改正は,F.6の定めのとおり(norms-evalもそのように適用する),その観測の手順1の前に効力を持つ。
最終状態の規範インスタンスは影響を受けない。inactive のものは新しいバージョンの定義を取り,新しい
バージョンにそのidの規範がなければ取り除かれる。active または suspended のものは,その
on_amendment: に従う。discharge はそれを解除する。transform: X はそれを解除し,Xが inactive で
あれば,古い規範の経過時間とともにXを発効させる。carry_over は,状態と経過時間を新しい定義のもとで
保つ。新しいバージョンにそのidの規範がなければ解除し,判定を待つ候補は内容が変わらない場合にだけ保ち,
経過時間が新しい期限を超える義務は違反とし(修復は新しい定義のものである),経過時間が新しい期限を超える禁止は履行済みとする。ただし,いずれも判定待ちの候補がない場合に限る。候補がある場合は,その候補が段階4で決める。インスタンスがまだ持たない
新しいバージョンの規範は inactive になり,発動条件がなく対象でもなければ,ただちに発効する。同じ
テキストの assume: の項目は続き,新しい項目は改正の時点から評価し,それ以外の項目は閉じる。新しい
バージョンのcounts-as規則は,その時点から適用する。どのバージョンの規範idの変数も,すべてのバージョンで
共有し,それぞれのバージョンに足りる大きさ(最大の期限,区間,候補の数)を持つ。インスタンスが持たない
規範(まだ効力のないバージョンのもの,または取り除かれたもの)は,存在しない状態にある。モデルは,
amend の行が与えたバージョンをその順序で名指すトレースについて,1つのバージョンについてF.12が
述べるとおりに厳密である。次のものは理由とともに変換しない。アクターまたはライフサイクルが異なる
バージョン,バージョンの間で種類が変わる規範(F.6はそれを解除する),変換しない規範またはcounts-as規則を
持つバージョン。問いは,どのバージョンのすべての規範idについても
問う。改正を必要とする証拠は,amend の行でバージョンのファイルを名指す。改正は環境の選択の数を2倍にし,
コマンドの数をバージョンの数だけ掛ける。
複数のインスタンスでは,効力を持つバージョンを共有する。1回の改正は,その観測で動くすべてのインスタンス
(始まっていて終わっていないもの,またはその観測で始まるもの)で,同じ観測に効力を持つ。これは,それらの
インスタンスのトレースがどれもその観測に amend の行を持ち,norms-evalがそれを適用するのと同じである。
終わったインスタンスは改正しない。改正の後に始まるインスタンスは,その時点で効力を持つバージョンの
インスタンスである。そのインスタンスは,開始の時点でそのバージョンの規範と assume: の項目を持ち,その
トレースはそのバージョンのファイルで評価し,その amend の行はそれより後のバージョンだけを名指す。証拠は,
そのようなインスタンスごとに,それがどのファイルのインスタンスであるかを示す。どのインスタンスも同じ
バージョンの列を持ち,各バージョンはそのインスタンスの束縛で読む。モデルは,これらのトレースのそれぞれに
ついて,上に述べたとおりに厳密である。
実行のバージョン。 cadl 0.3.36から,後のバージョンでの契約の経過規定が keep または
in_states: を持つ switch であるとき,モデルは1つの観測ですべてのインスタンスを改正する代わりに,
付録KのK.11の実行の
バージョンに従う。モデルのファイルを含むすべてのファイルが amendment: ブロックとともに拡張を宣言し,
後のバージョンは previous: による列の順に与える。そうでないモデルは拒否する。効力を持つバージョンは
インスタンスの間で共有する。環境は,各観測で,次のバージョンが効力を持つかどうかを選ぶ。これは
バージョンごとに高々1回,その順序で起こり,時間の基準は使わない(どの効力発生時点もありうる)。
各インスタンスは自分のバージョンを持つ。モデルはインスタンスごとに,従うバージョン,in_states: を
持つ切り替えが待っているバージョン(初めはない),ライフサイクルの状態の類を持つ。類は終端状態でない
ライフサイクルの状態を分ける。バージョンのどの in_states: も2つの状態の両方を含むか両方を含まない
とき,それらは同じ類に属し,初期状態はその類を代表する(インスタンスの終わりは上のとおりに選ぶ)。
環境は,各観測で,観測の後のライフサイクルの状態の類もインスタンスごとに選ぶ。インスタンスは,最初の
観測で効力を持つバージョンに従う。その後の観測では,cadl norms-eval がK.11を適用するとおりに更新する。
観測の前の類を状態に含む待っている切り替えを先に行う。次に,そこで効力を持つバージョンは,待っている
切り替えを取り消し,その規定を適用する。keep はインスタンスをそのバージョンに保ち,switch は改正し,
in_states: を持つ switch はその状態がその類を含むときに改正し,含まないときは待つ。各改正は上に述べたF.6の改正であり,1つの観測で2つの改正が起こるときは順に行う。あるバージョンに
ない assume: の項目が後のバージョンに再び現れるとき,その項目は,それまでに真偽が決まっていれば続き,
決まっていなければ新たに始まる。F.6が真偽の決まらない項目を閉じるからである。証拠は,各観測で効力を
持つバージョン(version)と,in_states: があるときはそこで選んだ類の状態(state)を示し,amend の
行を持たない。したがって,同じファイルを与えた cadl norms-eval --version がそれを読む。変数とコマンドは,
バージョン,類,インスタンスとともに増える。コマンドの制限(「制限」)を超えるモデルは,その制限を示して
拒否する。cadl 0.3.36のテストでは,2つまたは3つのバージョンを持つ7つのモデル(インスタンスは1つまたは2つ)の
780のランダムな経路で,モデルを cadl norms-eval --version と比べ,差はない。cadl 0.3.34と0.3.35はそのようなバージョンを拒否した。
環境が選ぶもの
環境は,各観測で次の3つを選ぶ。
-
メッセージ。モデルのメッセージ事象は,変換した
trigger:,until:,義務・禁止・権能の内容, counts-as規則のwhen:に含まれるメッセージ事象が,インスタンスの中で表す具体的なメッセージ (送信者,受信者,名前,引数)である。これらのどれにも一致しないメッセージは,変換した規範の状態を 変えないので,モデルに含めない。環境はメッセージ事象の部分集合を選ぶ。1つの観測で,各メッセージ事象は 高々1回,決まった順序(モデルの順序)で起こる。 -
値。トレースは量にどのJSONの値も与えうる。値は,モデルのどの述語もnorms-evalの評価(F.5)で同じ値を 持つクラスに分ける。クラスは次のとおりである。
- 値なし,真,偽のそれぞれ。
- 数では,その量と比べる数のリテラルより小さい数,リテラルに等しい数,隣り合うリテラルの間の数, リテラルより大きい数。この区切りには0も加える(条件として使う数は,0でなければ真である)。 真理値のリテラルと比べる量では1も加える(大小の比較は真を1として扱う)。
- その量と比べるテキストのリテラルと値のない名前のそれぞれと,それ以外の1つのテキスト。
- ほかの量と比べない量では,リストとオブジェクト。リテラルはリストでもオブジェクトでもないので, リテラルとの比較はこれらを区別しない。そのため1つのクラスにする。
各クラスは1つの代表値で表す。モデルは,どの述語も 代表値についてnorms-evalの評価器で評価する。そのため,型の異なる値の比較(テキストと数,真理値と数)は, モデルでもトレースと同じ値になる。norms-evalが比べられない値の組では未定義,等しくないと比べる組では偽である。 環境は量ごとに1つのクラスを選ぶ。すべての述語に同じ3値の値を与えるクラスの組合せは,1つの選択とする。 量がリテラルとの比較と条件にだけ現れる場合(限量子の中や
countの要素の中も含む),それらの比較の すべてに同じ値を与える2つの値は,どの述語にも同じ値を与える。モデルはそれらの値のうち1つだけを持つ。 値をほかの方法で使う量(min,max,sum,avg,算術)は,クラスごとに1つの値を持つ。互いに比べる量(
A.x < B.y,A.x == B.y,max(...) < A.y)はまとまりを作る。まとまりのどの量も, まとまり全体のリテラルを持つ(A.x == B.y AND B.y > 3では,A.xもリテラル3を持つ)。k個の量からなる まとまりのクラスは,各リテラルのほかに,最小のリテラルより下,隣り合う2つのリテラルの間,最大のリテラル より上の各区間に,k個ずつの値を含む。テキスト(norms-evalと同じくPythonの文字列の順序で並べる), オブジェクト(等しいかどうかだけを比べ,大小はない)もk個ずつ含める。リストは辞書式に順序づけられるが, いつも比べられるわけではない。最初に異なる要素の種類が違う2つのリスト(数とテキストなど)は,大きくも 小さくもなく,その比較は未定義である。たとえば[1, "a"] < [1, 2]は未定義であり,[1] < [1, "a"]と[1] < [1, 2]は真である。等しさだけを調べる量には,異なるk個のリストを含める。互いに大小を比べる (<,<=,>,>=)量には,トレースのリストが取りうる対ごとの結果(等しい,小さい,大きい,比べられない) の組合せをすべて実現するリストを含める。2個の量では[],[0],["a"](4通り),3個の量では[],[0],[1],["a"],["b"],[{"d": 0}],[0, 0],[0, "a"](29通り)である。3個のリストの比較の結果は, 要素が最初に異なる高々2つの位置で決まる。そのため,長さ2以下で,それらの位置での結果を実現する要素を 持つリストで足りる。0,1,2,"a","b",2つのオブジェクト,nullからなる長さ2以下のすべてのリストを 列挙すると29通りの組合せが得られ,上の8個のリストはそのすべてを実現する。互いに大小を比べる量が4個 以上あるまとまりは,後で述べる型とパターンによって変換する。このような順序の中で文字U+0000を含むテキストの リテラルは変換しない。 数は厳密に計算する。トレースの値は整数または浮動小数点数なので,区間の中の値は,その区間の内側にある 整数または浮動小数点数とし,それがk個に満たない区間ではそのすべてを含める。この扱いは厳密である。トレースがまとまりの量に与える値v1, …, vk(すべて数とする)と, 共通のリテラルを小さい順に並べたc1 < … < cmを考える。各viは, あるリテラルに等しいか,ある区間の中にある。1つの区間の中にある異なる値は高々k個である。リテラルに等しい viはそのリテラルに移し,各区間の中の異なるviは,順序を保って,その区間の値の はじめのものに移す(区間はトレースの異なる値の数以上の値を持つ)。この対応は,まとまりの2つの量の比較 (順序と等しさ。同じ区間の中でも異なる区間の間でも)と,量とリテラルの比較のすべてを保つ。したがって, まとまりのどの述語も,移した値で同じ値を取る。テキストについても同じ議論が成り立つ。リストとオブジェクトはリテラルと比べず,その2つの比較は 対ごとの結果の組合せだけで決まり,クラスのリストとオブジェクトはその組合せを実現する。型の異なる値の比較は, 型の中での値によらない(大小の比較は真と偽を1と0として扱い,これらはどのまとまりのリテラルにも含まれる)。
述語のまとまりの量のクラスの組合せが50000を超えるとき,または互いに大小を比べる4個以上の量からなる まとまりがあるときは,量がリストを除いて同じクラスを持つ(与えた定義域も仮定した定義域も持たない)各まとまりの値の組を,型と パターンから作る。前段の最後に述べたことから,まとまりの値の組は,各量の型(値なし, 真,偽,数,テキスト,オブジェクト,リスト)と,型ごとにその型を持つ量のパターンで決まる。パターンは, 数とテキストでは,各量が等しいリテラルまたは各量が入る区間と,1つの区間に入る量の順序(等しいものを含む) である。それらの量は,この順序で,その区間の値のはじめのものを取る。これは上の対応と同じである。 オブジェクトではどれが等しいか,リストでは対ごとの結果の組合せがパターンである。モデルは,型とパターンの 選び方ごとに1つの値の組を持つ。上の対応で,リストとオブジェクトも同じパターンのものに移す。すると, トレースの値の組はこれらのどれかに移り,2つの量の比較と,量とリテラルの比較は,どれも値を変えない。 したがって,これらの値の組は,トレースが述語に与える値の組合せをすべて述語に与える。n個のリストの パターンは,等しいリストへの分割と,そのクラスの上の直並列の順序の組にちょうど一致する。直並列の順序とは, a < c,b < c,b < dであって,aとb,aとd,cとdがそれぞれ比べられないような4つのクラスa,b,c,dを 持たない順序をいう。トレースにこれ以外のパターンは現れない。空のリストは他のどのリストよりも小さい。 空でなく最初の要素が等しいリストは1つの部分を作り,そのパターンは2番目以降の要素からなるリストの パターンである。異なる部分の2つのリストの比較の結果は,最初の要素の比較の結果と同じである。最初の要素どうしは,数として (真と偽を含む),テキストとして,または同じ規則によりリストとして比べられるか,比べられない(種類が 異なる場合,オブジェクト,null)。そのため,最初の要素の順序は,全順序とリストの順序の非交和である。 直並列の順序は,非交和,一方の順序を他方の下に置くこと,順序の各要素を順序で置き換えることについて 閉じているので,リストの大きさ(入れ子のどの深さの要素も数えた要素の数)についての帰納法により, リストの順序は直並列である。逆に,そのようなパターンは すべて実現される。2個以上のクラスを持つパターンは,2つの小さいパターンの直列合成(一方の部分のどの リストも他方の部分のどのリストより小さい)か並列合成(どの2つも比べられない)であり,2つの部分を実現する リストの先頭に,直列合成では0と1を,並列合成では0と
"a"を加えたリストがそれを実現する。1個から5個の リストのパターンは,1,4,29,331,5262通りである。3個のリストの29通りは,上の8個のリストのものと 同じである。まとまりの値の組の数は,量の型の選び方についての,型ごとのパターンの数の積の和である。 処理系は,値の組を作る前に,この数を区間の大きさから計算する(区間に入る量の順序は,区間の値の数 以下のクラスを持つ弱順序である)。 リテラルが0と1(どのまとまりも持つ)だけの4個の量では,値の組は26035個である。クラスの積は,各量の リストでない29個のクラスだけでも294 = 707281個の組合せを持つ。数のリテラルが1つ増えると, 値の組は46285個になる。同じクラスを持ち互いに比べる5個以上の量からなるまとまりは,大小を比べるか 等しさだけを調べるかによらず,少なくとも424213個の値の組を持つ。これは制限の50000を超える (「制限」を参照)。このようなまとまりは,後で述べる消去によって変換する。クラスが異なる,互いに 大小を比べる4個以上の量と,後で述べる線形の算術を含むまとまりの中にある,互いに大小を比べる 4個以上の量も同じである。算術(
+,-,*,/),sum,avgは,どの積もリテラルの因数を持ち,どの除数もリテラルであるとき, 線形であるという(R.x * 0.5 - S.y / 4,sum(r.load for r in ROBOT) + 2 * D.r)。線形の算術では,量に 定義域はいらない。量を共有し,このような算術を含む述語のまとまりでは,定義域のない各量は,数(次に述べる 線形の配置の変数)であるか,数でないクラスの1つを取る。定義域を持つ量は,そのクラスを取る。この選び方 ごとに,ほかの値を固定すると,述語の中の比較と条件として使う数は,どれも変数の線形式の符号で決まる。 比較では,両辺の差が線形式である。ただし,minとmaxは定義された要素ごとに,countは取りうる個数ごとに 別の式を作る。+,-,リテラルの因数,min,maxで作った値は,これらの式の値から最小と最大をとる 操作だけで得られるので,その符号はそれらの式の符号で決まる。countの値は,その要素の式で決まる。したがって,どの 述語も,超平面「式 = 0」の配置の各面の上で1つの値を取る。面とは,どの式も決まった符号(負,0,正)を 取る点の集合である。そのため,面ごとに1つの点があればよい。点は柱状代数分解(cylindrical algebraic decomposition)で求める。最後の変数は,それを 含まない式を残し,それを含む2つの式ごとに,その変数についての根の差を加えて消去する。この射影の各セルの 点を,その点での式の根と,根の下,根の間,根の上の点によって,最後の変数の方向に延ばす。射影の1つのセル の上では根の順序が変わらないので,セルは面を細分し,どの面にも点が入る。トレースの値は整数または 浮動小数点数,すなわち有限小数であり,有限小数の点を持たない面もある(3 * x == 1)。有限小数の全体を D(10のべきを逆元として加えた整数)とする。面のアフィン包Hは,面の上で0になる式で決まる。処理系は, それらのうち独立な式の極大な組を整数の行 A x = b に直し,行列式が±1の整数の列の操作(拡張ユークリッドの 互除法)でAを A V = T に変形する。Tは最初のr列が下三角で対角成分が0でなく,それより後の列は0である。 x = V y とすると,Hの点では y1, …, yr がTで決まり,yr+1, … は自由である。 VとV-1は整数の行列なので,xがDnに属するのは,yがそうであるときに限る。したがって, HがDnの点を持つのは,決まったyiがすべてDに属するときに限り,そのときHのDnの 点は,Dnの点x0とVの後のn − r列からなるBにより,tをDn-rの上で動かした x0 + B t である。決まったyiがDに属さないものを含むとき,どのトレースもその面に達しないので, その面は除く。そうでなければ,Hの中で開いた面は,その点 p = x0 + B t* を含む。pで0でない 式fは,各tjが高々δ動くとき,高々 δ · Σj |(f B)j| しか変わらず,pで0の式は Hの上で0のままである。処理系は,そのようなどのfについても 10-k/2 · Σj |(f B)j| < |f(p)| となる最小のkを求め,t*を小数k桁に丸める。丸めた点はDnに属し,その面の中に ある。したがって,面を除くのは,その面がトレースの点を持たないときだけであり,探索の上限のために面を 落とすことはない。非常に薄い面の点は,norms-evalがトレースの数に許す桁数(400)より多くの桁を必要とする ことがある。その場合,その点を使う証拠は確認されなかったものとして報告し(リファレンス実装では終了ステータス3), 誤った答えを知らせずに与えることはない。この扱いは厳密である。トレースの値は,数でない値を同じにしたまま,ある1つの面の中にあり,その面の点はどの述語にも トレースの値と同じ値を与える。リテラルとの比較や2つの量の比較も線形式なので,このようなまとまりでは, リテラルの間の区間ごとに1つの点で足り,前述の区間ごとのk個の値は必要ない。報告は,数を配置から取る量を示す。線形でない算術(2つの量の積や商)は,有限の定義域を持つ量について変換する。CADLは規範の量の定義域を 宣言しないので,定義域は量ごとの整数の範囲lo..hiとして処理系に与える(リファレンス実装では
--domain)。そのような量は,定義域の整数と数でない値を取る。答えは,そのような量の数がすべて定義域の 整数であるトレースについて成り立ち,報告はその量と定義域を示す。定義域が与えられないときは,処理系は, 述語の数のリテラル(と0)のうち最小のものより1小さい整数から,最大のものより1大きい整数までを定義域と 仮定し,報告はこの定義域を仮定として述語とともに示す。答えは,そのようなトレースについてだけ成り立つ。 処理系は,仮定した定義域のもとでだけ成り立つ答えを,その仮定を示さずに与えてはならない。リファレンス 実装は,trigger:,until:,内容,またはそれが依存するcounts-as規則,修復,権能がそのような量を読む規範と, その規範についての指摘のすべてに印を付ける。消去。述語のまとまりの型とパターンによる値の組が50000を超えるとき,互いに大小を比べる4個以上の量のまと まりの量のクラスが同じでないために型とパターンによる値の組を使えないとき(与えられた定義域または仮定し た定義域を持つ量,比較が区別するクラスだけを持つ量,ほかのリテラルを持つ量があるとき),線形の算術を含 むまとまりで,互いに大小を比べる4個以上の量があるとき,またはクラスと面の点の組合せが50000を超えるとき は,処理系は,すべての値の組を作らずに述語の値の組合せを求める。モデルに要るのはこの組合せだけである。 すべての述語に同じ値を与える2つの値の組は1つの選択になる。ほかのリテラルを持たない互いに大小を比べる4 個の量の26035個の値の組は,それらについての4個の述語を持つ契約では34個の組合せになる。各述語は,葉(比 較,条件として使う量,
IN,集約)から,KleeneのAND,OR,NOTと,existsとfor allによって 作られている。existsとfor allは,定義域の要素についての選言と連言である(開いた定義域では未定義 の値を加える)。葉は少数の量を読み,上の議論により,その値はそれらの量のパターンだけで決まる。パターン とは,各量の型,各量が等しいリテラルまたは入る区間,同じまとまりに属し同じ種類の値を持つ2つの量の関係 (1つの区間の中の2つの数または2つのテキストの順序,2つのオブジェクトが等しいかどうか,2つのリストの比 較の結果。まとまりのどの比較も量の大小を比べないときは等しいかどうかだけ)である。処理系は,量を1つず つ,残りの葉が読む加えた量が少なくなるような順に加える。状態は,量をすべて加えた葉をその値で置き換え, Kleeneの論理の規則を適用した後の各述語の残りと,残りの葉がまだ読む加えた量のパターンの組である。残りと パターンが同じ状態は1つにまとめる。どの続きもそれらに同じ値を与えるからである。すべての量のどのパター ンも各段階でいずれかの状態を通るので,トレースが与える組合せはすべて求まる。これは2つの事実による。1つ は,葉の値がそれが読む量のパターンで決まることである。型の異なる値の比較は,順序が真を1,偽を0として比 べること(クラスはこれらを含む)を除いて型で決まり,算術は数についてだけ値を持つ(上を参照)からである。 もう1つは,限量子と集約の定義域の要素が量の値によらないことである。各状態は,そこに至る,それまでに加 えたすべての量のパターンも1つ持つ。新しい量は,状態が示すとおりにほかの量と並べ,残りの量とは矛盾しな いように並べる。このパターンはクラスの値で実現でき,述語の評価器がそれらの値について組合せを確かめるの で,求めた組合せはどれもトレースが与えるものである。数,テキスト,オブジェクトのパターンは,いつもこの ように組み合わせられる。リストのパターンはそうではない。リストp,q,r,sが p < q < r を満たし,sがpよ り大きくqともrとも比べられないとき,これらは直並列である。rより小さくpともqとも比べられない新しいリス トxを加えた組合せも,p,q,rについては直並列である。しかし,sとxの比較の結果をどう選んでも,5個のリス トは直並列にならない。保持したパターンを広げられないとき,処理系は量を加え直し,まとまりのすべての量を 加えるまで,そのまとまりの加えたリストをすべて状態に残す。まとまりが集合の要素の1つの項目だけを読み, どの要素も同じ種類,クラス,まとまりを持ち,どの述語も要素を集合全体(RまたはR[*])を動く限量子 と集約の変数を通してだけ使い,その変数どうしを==と!=だけで比べ,ほかの集合の添字には使わないと きは,要素をどう入れ替えても各述語の値は変わらない。そこで,加える順に並べた要素が整列している値の組だ けを加える。整列とは,要素が種類の順に並び,順序のある値は昇順で,等しい値は隣り合い,リストはどれも前 のリストより小さくない順に並ぶことである。どの値の組も,このような値の組の要素を入れ替えたものである。 線形の算術を含むまとまりでは,定義域のない量は上の配置の数でもありうる。そのような数を読む葉は,最後に, ほかの値を状態のとおりに固定し,それらの葉の一次式の配置の各面の1点で評価する。処理系は,求まる組合せ が変わらない限り,保持する状態を減らしてよい。リファレンス実装は,cadl0.3.32から,線形の算術を含ま ないまとまりで,上の消去が1つの段階で50000を超える状態を要するときにだけ,3つの方法によってこれを行う。 そのときは量を初めから加え直す。こうして,その制限の範囲のまとまりは,cadl0.3.31と同じ組合せと値の 組を得る。1つ目に,集合の要素の入れ替えは,要素を変数(その葉の限量 子と集約の変数,および外側の限量子が束縛する変数)を通してだけ使う葉を,束縛する要素を入れ替えた葉に 移す。入れ替えた値についてのその葉の値は,もとの葉の値と同じである。同じ段階の2つの状態がこのような入 れ替えで互いに移り,その入れ替えが,量をすべて加えた要素だけを動かし,パターンの量を同じ種類を持つパタ ーンの量に移し,残りをANDとORの被演算子の順序を除いて変えないとき,2つの状態は同じ組合せを与え るので,一方だけを保持する。すべての対の要素を添字の順に比べる述語はこれに当たる。2つ目に,段階を始め る前に,量を1つずつ,広げ方を1つずつ選んで加える試行を何回か行い,各試行の組合せをその値の組とともに保持 する。残りがまだ与えうる組合せがすべて求まっている状態は保持しない。残りが取りうる値は,被演算子の取り うる値からKleeneの表で抑え,2個以下の量を読む部分は,それらの量のすべてのパターンでの値を取る。3つ目に, 集合の要素を集合全体についての1つの項目のminとmaxだけを通して読む葉の値は,F.5により,どの種類 の要素(数,型の誤った値,欠けた値)が現れるかと,最小と最大の数で決まる。状態は,加えたすべての要素の 代わりに,現れる種類ごとに1つの要素と,最小と最大の数を持つ要素だけを保持し,この葉だけが読む要素を役 割で表す。葉は,各要素にこれらのいずれかの値を与えて評価する。1つの段階で制限を超える状態が要るとき, または数を読む葉が合わせて制限を超える面の点を要するとき,処理系はそのまとまりを拒否し,どの制限を超え たかと,制限をどこまで上げられるかを示す(「制限」を参照)。リファレンス実装は,既定の制限では,countを通して多くの量を読む葉でその値の1つが現れないもの(要素が6個のcount(r.load > D.load for r in R) >= 0), 多くの大小を比べる量にかかる線形の算術,6個以上の同じ要素をmaxと添字の両方を通して読む述語を,いま も拒否する。 -
終了。インスタンスがこの観測で終わるかどうか(F.5の手順6)。
lifecycle:のない契約で通知される 終了と,ライフサイクルの終端状態の両方を表す。
時間
観測は,ステップΔの倍数の時刻に起こる。観測nの時刻はnΔである。Δは,与えられるか,または変換した
期限,時相演算子,仮定の時間の最大公約数とする(どれもなければ1秒)。与えるΔは,それらのそれぞれを
割り切らなければならない。期限dはd/Δステップに,within,throughout,until の区間wはw/Δ
ステップになる。
観測がΔの倍数の時刻に,0からインスタンスの終了まで並ぶトレースについて,モデルは厳密である。 F.5が比べる時間(規範の発効中の時間と期限,観測と区間の終わり)はそのとき整数個のステップであり, ステップで比べた結果は秒で比べた結果と同じである。何も含まない観測も,ほかの観測と同じ観測である(F.5)。 モデルは,Δの2つの倍数の間の観測と,倍数を飛ばすトレースを扱わない。Δの倍数の時刻の間にある観測は, 過ぎた期限を早く検出しうる。また,その間だけ成り立つ値を見うる。そのようなトレースの性質を検査するには, より小さいΔが要る。
上限Hは,インスタンスの長さを制限する。インスタンスは遅くとも観測Hで終わる。既定では,変換した義務と 禁止についての和 H = 2 + Σ (d + w + 2) とする。dとwは,期限と内容の区間のステップ数(なければ0)である。 この値は,各規範を順に発効させ,判定し,その修復を発効させるのに足りる観測の数である。答えは,観測が H + 1個以下のインスタンスについてのものである。より大きいHは,より長いインスタンスを扱う。
状態と遷移
ある観測の後のモデルの状態は,次のものからなる。
- ステップの番号と,インスタンスが終わったかどうか。
- 変換した規範ごとに,その状態(F.5)。
dischargedは,発効していた規範と,インスタンスの終了時にinactiveだった規範に分ける。violatedは,判定violatedとexcusedに分ける。 - 変換した義務と禁止ごとに,その観測で発効したかどうかと,発効中の時間のステップ数(期限 + 1まで数える)。
- 内容が時相演算子である義務と禁止ごとに,判定を待つ候補。候補は経過ステップ数ごとに持ち,F.4がそれを
決めるのに必要な情報(未定義の値を見たか。
untilでは,前の部分が未定義だったかも)を伴う。また, 真または真でないと決まった候補が,規範の判定を待っているかどうか(suspendedの間は判定しない)。 - 真になることが事象である述語ごとに,前の観測でのその値。
- 時相演算子を含む仮定ごとにその状態と,仮定が破れたかどうか。
- 権能ごとに行使されたかどうかと,修復を持つ義務と禁止ごとに,修復が発効したかどうか。
モデルの1つの遷移は1つの観測である。F.5の手順を,その順序(「1つの観測の中での順序」)で,環境の選択に ついて,それぞれ前の手順の残した状態に適用する。インスタンスが終わった後,状態は変わらない。
変換するもの
変換は,次のものを変換する。メッセージ事象(引数はリテラルまたは名前),counts-as規則の制度的事象,
述語。述語は,量(A.q,A[k].q,i を束縛した A[i].q,集合の上を動く変数 r についての r.q,
限量子の変数 j についての A[j+1].q)とリテラルまたは内包表記の count との比較(==,!=,<,
<=,>,>=,IN),条件として使う量,AND,OR,NOT,限量子 exists と for all,集合または
範囲の上の内包表記の集約 count,min,max,2つの量の比較,算術,sum,avg(線形のものはすべての値に
ついて,それ以外は与えた定義域または仮定した定義域の上で),述語の中のワイルドカード参照と
範囲参照(F.5はこれらを限量子または内包表記として読む)から組み立てる。さらに,そのような述語の上の
有界の時相演算子1つからなる内容,期限,until:,if: を持つcounts-as規則,権能とその効果,修復,
これらの形の assume: の項目(判定 excused のため)を変換する。request のフィールド,now,state,ほかの演算子と組み合わせた時相演算子,
入れ子の時相演算子は変換しない。改正は前述のとおり変換する。そのような部分を持つ規範は,理由とともに「変換しない」と
報告する。そのような規範に振る舞いが依存する規範も同じである。変換しない規範の修復,変換しない権能の
効果の対象,変換しないcounts-as規則の事象を trigger:,内容,until: とする規範がこれに当たる。
assume: の項目を変換しないとき,トレースでは違反が excused になりうるが,モデルはそれを区別しない。
検査を通ったファイルには,F.10が判定できない規範はない(N-16)。cadl 0.3.29までは,そのような規範は
トレースと同じく,モデルでも inactive のままであった。
guarantee: の項目は規範の状態を変えないので,変換しない。
問い
問いは,モデルのラベルについてのPRISMの性質である。終了について2つの読み方を使う。「任意の終了」
(early_end=true)では,インスタンスはどの観測でも終わりうる。これを可能性の問いに使う。「上限まで続く
読み方」(early_end=false)では,インスタンスは上限まで続く。これを必然性の問いに使う。インスタンスを
早く終えると,義務は期限の前に解除される。そのため,任意の終了では,必然性の問いの答えが自明になる。
| 問い | 読み方 | 性質 | 答え |
|---|---|---|---|
| 規範nは発効しうるか | 任意の終了 | Pmax=? [ F "a_n" ] | 0より大きければ「はい」 |
| 違反されうるか | 任意の終了 | Pmax=? [ F "v_n" ] | 0より大きければ「はい」 |
| 履行されうるか | 任意の終了 | Pmax=? [ F "f_n" ] | 0より大きければ「はい」 |
| どのインスタンスでも違反されるか | 上限まで続く | Pmin=? [ F "v_n" ] | 1であれば「はい」 |
| 発効するたびに守れるか | 上限まで続く | Pmax=? [ F (!"end" & !(P<=0 [ X "j_n" ]) & P<=0 [ X ("j_n" & !"v_n" & !(P>=1 [ F "v_n" ])) ]) ] | 0より大きければ「いいえ」 |
| nとmは衝突するか | 上限まで続く | Pmax=? [ F (!"v_n" & !"v_m" & !(P<1 [ G !"v_n" ]) & !(P<1 [ G !"v_m" ]) & P>=1 [ F ("v_n" | "v_m") ]) ] | 0より大きければ「はい」 |
| 権能pは行使されうるか | 任意の終了 | Pmax=? [ F "x_p" ] | 0より大きければ「はい」 |
| nの修復は発効しうるか | 任意の終了 | Pmax=? [ F "r_n" ] | 0より大きければ「はい」 |
"a_n" はnが発効した後で成り立つ。"v_n" はnが違反されているとき(どちらの判定でも),"f_n" は
履行されているときに成り立つ。"j_n" は,nが発効した観測の後の状態で成り立つ(その観測の後のnの状態は
問わない)。"x_p" はpが行使された後で,"r_n" はnの修復が発効した後で,"end" はインスタンスが
終わった後で成り立つ。MDPでは,P>=1 [ F φ ] は選択のどの解決もφに到達することを,
!(P<1 [ G !φ ]) は選択のある解決がφを避け続けることを表す。P<=0 [ X φ ] は次の観測のどの選択も
φに至らないことを,!(P<=0 [ X φ ]) はある選択がφに至ることを表す。
ある観測の前の状態で,環境のある選択が規範を発効させ,規範を発効させる選択がどれも,その後のどの続きも 規範に違反する状態に至るとき,その発効は守れない。この問いは,発効させる観測の前の状態について問う。 その観測が環境の選択を含むからである。メッセージを発動条件とする期限0秒の義務は,同じ観測で内容が 起こりうるので守れる。期限0秒の修復は,次の観測で初めて判定される(F.5の手順5)ので守れない。 この問いを発効について問うのは,期限を持つ義務はどれも,負担者が何もしなければ,その後にどのような観測が続いても 違反される状態に至るからである。
2つの義務または禁止nとmは,次の状態に到達できるとき,衝突する。どちらも違反されておらず,それぞれ単独では まだ守れ,どの続きもどちらかに違反する状態である。たとえば,ある義務の内容をある禁止が禁じていて,両方が 発効しているとき,その義務と禁止は衝突する。衝突は修復を通じても生じうる。nを守ると第3の規範に違反し, その修復がmである場合である。
証拠
何かが可能であるという答えには,必ず証拠が付く。証拠は,リファレンス実装の形式のトレースであり,
Δの倍数ごとに1つの観測を持ち,F.5で評価すると主張どおりの判定になる。証拠は,Pmax の性質について
モデル検査器が与える戦略の経路であり,目標に達した後は,インスタンスが終わるまでメッセージも値もない
観測が続く。守れない発効の証拠は,発効させる観測の前の状態に達する。処理系は,その観測での環境の
選択のそれぞれについて,規範を発効させるかどうかをF.5で評価し,モデルと一致することを確かめる。
また,規範を発効させる選択のそれぞれについて,その後に上限までメッセージも値もない観測を続けると規範に
違反することを確かめる。発効させる選択のほかの続きもすべて規範に違反することは,モデル検査器の答えに
よる。証拠のトレースは,発効させる選択の1つを含む。その観測での選択が512を超えるとき,処理系はすべての選択の代わりに512個の標本を確かめてもよい。その場合は,標本で確かめたことを報告に書かなければならない。衝突には,衝突の状態から始まる2つの証拠がある。
一方はnを守ってmに違反し,他方はmを守ってnに違反する。どのインスタンスでも違反される規範については,
メッセージも値もないインスタンスを例として示す。処理系は,すべての証拠をF.5で評価し,主張どおりの判定に
ならない証拠を自らの誤りとして報告することが望ましい。
制限
バージョン0.1は,1000を超える観測の上限,16を超えるメッセージ事象,1つの観測について8192を超える
環境の選択,および述語の1つのまとまりについて50000を超えるクラスの組合せを持つ量を拒否する。
集合の要素についての述語は要素ごとに1つの量を読み,それらの量のクラスは掛け合わされる。量ごとのクラスがc,
要素がm個,要素ごとに読む量がq個であれば,1つのまとまりの組合せは最大でcm q個になる。
50000の制限はこの数を抑える。互いに比べる量のまとまりの値の組を型とパターンから作るときは,制限は,
その値の組の数と,述語のまとまりのほかの量のクラスの数の積を抑える。リファレンス実装は,ほかのリテラルを持たない
互いに大小を比べる4個の量の26035個の値の組を約2秒で作る。制限を超えるとき(5個の量の値の組は424213個であ
る)は,組合せを消去によって求め,制限は1つの段階の状態の数を抑える。状態と面の点の制限は,--max-states
(1から1000000)で設定しない限り50000である(cadl 0.3.32から,リファレンス実装は --max-states から取る。
最大1000000)。
リファレンス実装は,互いに大小を比べる5個から12個の量の鎖を1秒以内に加え,述語が同じように扱う集合の8個の
要素のすべての対を約12秒で加える。cadl 0.3.32からは,6個,7個,8個の要素のすべての対を添字の順に比べる
述語と,8個の要素についての max(r.load for r in R) > D.load を,どちらも1秒以内に加える(cadl 0.3.31
はどちらも要素が6個から拒否していた)。線
形の算術を含むまとまりでは,組合せは,数でないクラスの選び方ごと(消去では最後の状態ごと)の面の点の数の
和であり,同じ制限を適用する。
モデル検査器は到達可能な状態を明示的に調べる。遷移の数は,到達可能な状態の数と選択の数の積であり,
メッセージ事象と値のクラスとともに増える。検査の時間は,モデルのコマンドの数(環境の選択ごとに4つ)と
到達可能な状態の数とともに増える。メッセージ事象が12個(選択が4096,コマンドが16384)のインスタンスでは,
10分を超えた。処理系は,モデル検査器の時間とモデルを作る時間を制限し,制限を超えたときはそれを報告することが望ましい。
選択の数の制限は,複数のインスタンスの開始と終了,バージョンを掛けた後のコマンドの数で調べる。モデルのコマンドは
32768個までである。クラスの組合せが多すぎるために拒否するときは,その原因となる述語と量を示す。