付録A. 構文リファレンス(EBNF)
CADLファイルはYAML 1.2文書 [Ben-Kiki+, 2021] である。本付録は CADL v0.3 のリファレンス文法を 2つの部分に分けて示す。文書の構造(A.2〜A.9)は,YAMLのマッピングと シーケンスの上のEBNFとして記述する。式の部分言語(A.1,A.10)は, 個々のYAML文字列スカラーの中に書かれる。
第5章と本付録は同じ構文を記述する。具象構文については本付録が規範的であり,
第5章は説明のための記述である。リファレンス実装
(cadl)は,この構文をそのまま
受理すべきものである。cadl 0.3における既知の相違は
A.12に示す。
この文法を試すには,リファレンス実装をインストールし(クイックスタートの経路 Bを参照),
cadl parse または cadl check を実行する。実行できるファイルは,
cadlリポジトリの examples/ ディレクトリにある。
記法。 文法にはISO/IEC 14977のEBNF [ISO/IEC 14977:1996] を用い,次の規約を置く。
"name:"のようにコロンで終わる終端記号は,YAMLマッピングのキーであり, その後に値が続く。1つのマッピングの中の項目は任意の順序で書いてよく, 各項目は高々1回だけ現れる。{ "-" , x }は,xを要素とするYAMLシーケンスである。ブロック形式と フロー形式([a, b])は等価である。- 非終端記号
kを用いたk , ":" , vは,キーを記述者が選ぶマッピングである。 textは任意のYAML文字列スカラー,numberは任意のYAML整数または 浮動小数点数,scalarは任意のYAMLスカラーである。これらの内容は それ以上解釈しない。any_charは任意の1文字である。stringの規則(A.1)はここから二重引用符を除くので, 文字列は次の"で終わる。(* string *)と注記した生成規則は,1つのYAML文字列スカラーの内容を記述する。
インデント,コメント,引用符,ブロック形式とフロー形式の選択はYAMLの規定に従い,
文法には示さない。[,],*,->,": " を含むスカラー(たとえば
"TAXI[*]" のようなアクター参照や "A -> B : msg" のようなステップ)は,
引用符で囲むことが望ましい。フローシーケンスの中では,YAMLが別の意味に
解釈するため,必ず引用符で囲まなければならない。sharing_entry(A.4)は,
どこに書く場合も,引用符で囲んだ文字列でなければならない。
本付録が定義しないキーは CADL v0.3 の一部ではない。処理系は,そのようなキーを 理由にファイルを拒否してはならない。リファレンス実装はそれらを無視する。
本文法は5.1.1節の設計レベルと検証レベルを対象とする。概要レベルの記述は, AIによる精緻化のための非形式的な入力であり,本文法に従う必要はない。
A.1 字句規則
これらの規則はスカラーの内部に適用する。
letter = "A" | … | "Z" | "a" | … | "z" ;
digit = "0" | … | "9" ;
identifier = ( letter | "_" ) , { letter | digit | "_" } ;
hyphen_name = identifier , { "-" , name_part } ;
name_part = ( letter | digit | "_" ) , { letter | digit | "_" } ;
actor_ref = identifier , [ "[" , index , "]" ] ; (* string *)
index = "*" | range_expr | int_literal | identifier ;
range_expr = int_literal , ".." , ( int_literal | identifier ) ;
string = '"' , { any_char - '"' } , '"' ;
int_literal = digit , { digit } ;
float_literal = int_literal , "." , [ int_literal ] , [ exponent ]
| "." , int_literal , [ exponent ]
| int_literal , exponent ;
exponent = ( "e" | "E" ) , [ "+" | "-" ] , int_literal ;
bool_literal = "true" | "false" ;
duration_lit = int_literal , ( "ms" | "s" | "min" | "h" ) ;
literal = string | int_literal | float_literal
| bool_literal | duration_lit ;
duration_lit は,整数の後に単位を続けたものである。2.5s は期間に当たらないので,同じ時間は 2500ms と書く。
string を区切るのは二重引用符だけであり,'k' は文字列でない。
identifier は,アクター,契約,プロトコル,運用モード(regime),メトリクスの名前に用いる。
hyphen_name は,拡張の名前とコード生成ターゲットの名前(たとえば sos-dsl,
unity-csharp)にだけ用いる。数値リテラルは符号を持たない。
識別子はASCIIに限る。文字列とコメントには任意のUnicode文字を使用できる。これが要求NFR-7(第4章)の求める内容である。cadl 0.3.9からは,リファレンス実装は,ASCIIの規則に違反するidや運用モードの名前をエラーとして報告する(A.12)。
A.2 トップレベル構造
cadl_file = "sos:" , sos_body ;
sos_body = "name:" , text ,
[ "type:" , sos_type ] ,
[ "version:" , scalar ] ,
[ "description:" , text ] ,
[ "extensions:" , { "-" , extension_decl } ] ,
[ "context:" , context_block ] ,
[ "actors:" , { "-" , actor_def } ] ,
[ "contracts:" , { "-" , contract_def } ] ,
[ "protocols:" , { "-" , protocol_def } ] ,
[ "algorithms:" , { algorithm_def } ] ,
[ "transitions:" , { "-" , transition_def } ] ,
[ "regimes:" , regimes_block ] , (* A.7.1 *)
[ "metrics:" , { "-" , metric_def } ] ,
[ "verification:" , { "-" , verify_def } ] ,
[ "codegen:" , { "-" , codegen_def } ] ,
[ "motivation:" , motivation_block ] ,
[ "model:" , model_block ] , (* 付録H *)
[ "amendment:" , amendment_block ] ; (* 付録K *)
sos_type = "Directed" | "Acknowledged" | "Collaborative" | "Virtual" ;
extension_decl = hyphen_name , ":" , scalar ;
1つのファイルは1つのSoS定義を含む。version: には,慣例として "1.0.0" のような
セマンティックバージョンの文字列を書く。
拡張点。 extensions: は,ファイルが依存する言語拡張を,名前とバージョンの組
(たとえば - sos-dsl: 0.1)として宣言する。次の8つの拡張を定義している。
最後のもの以外は,宣言できる名前を持つ。
- SoS-DSL拡張(付録E)。名前
sos-dsl,バージョン0.1として 宣言する。contract_def(A.4)にキーlifecycle:とmonitors:を追加する。 - 規範拡張(付録F)。名前
norms,バージョン0.1として宣言する。contract_def(A.4)にキーnorms:とcounts_as:を,契約の述語に有界の時相演算子を追加する。 この拡張を用いるファイルは,宣言しなければならない。 - エージェント統治拡張(付録G)。名前
agents,バージョン0.1として宣言する。normsを必要とし,actor_def(A.3)にキーagent:を,contract_def(A.4)にキーenforcement:とdelegations:を,禁止にon_denied:を追加する。 - 確率モデル拡張(付録H)。名前
stochastic,バージョン0.1として宣言する。sos_bodyにキーmodel:を追加する。 - 戦略モデル拡張(付録I)。名前
games,バージョン0.1として宣言する。stochasticを必要とし,model:にプレイヤー,プロファイル,利得,均衡問い合わせを追加する。 - 根拠付け拡張(付録J)。名前
grounding,バージョン0.1として宣言する。normsを必要とし,contract_def(A.4)にキーgrounding:を,規範にキーshares:とon_fulfilment:を,そのon_violation:にmagnitude:を追加する。gamesとともに用いるときは, 利得の項にキーsanction_of:とreward_of:を追加する。 - 改正拡張(付録K)。名前
amendment,バージョン0.1として宣言する。sos_bodyにキーamendment:(改正できるパラメータ,バージョンとその経過規定,判断の記録)を,metric_def(A.3)にキーschedule:とmeasure:を追加する。 - 動機拡張(付録C)。
motivation_blockを定義する。 v0.3ではextensions:に書く名前を持たず,motivation:ブロックを書くだけで用いる。
A.3 コンテキスト・アクター・メトリクス
context_block = [ "environment:" , { identifier , ":" , scalar } ] ,
[ "assumptions:" , { "-" , text } ] ;
actor_def = "id:" , actor_ref ,
"role:" , text ,
[ "autonomy:" , autonomy_level ] ,
[ "capabilities:" , { "-" , text } ] ,
[ "interface:" , interface_def ] ,
[ "agent:" , agent_binding ] ; (* 付録G *)
autonomy_level = "low" | "medium" | "high" ;
interface_def = [ "input:" , { "-" , text } ] ,
[ "output:" , { "-" , text } ] ;
metric_def = "id:" , identifier ,
[ "formula:" , predicate ] , (* string *)
[ "target:" , scalar ] ,
[ "schedule:" , { "-" , schedule_entry } ] , (* 付録K *)
[ "measure:" , measure_def ] ; (* 付録K *)
autonomy: の既定値は medium である。actor_def の id: の添字は,通常は範囲
("ROBOT[1..N]")であり,パラメータ化されたアクターの集合を宣言する。
range_expr の上限は整数または識別子である。N のような識別子は記号的な大きさであり,
v0.3にはこれを値に束縛する構文がない(リファレンス実装での扱いは
A.12を参照)。
environment: の値が文字列でないときはリテラル(A.1)として読み,
文字列のときはそのまま保持する。
A.4 コントラクト(制度層)
制度層は,ここで定義する contracts: と,actors:(A.3)および transitions:(A.7)からなる。
contract_def = "id:" , identifier ,
"parties:" , { "-" , actor_ref } ,
[ "assume:" , { "-" , predicate } ] ,
[ "guarantee:" , { "-" , predicate } ] ,
[ "authority:" , authority_block ] ,
[ "information:" , information_block ] ,
[ "responsibilities:" , { actor_ref , ":" , { "-" , text } } ] ,
[ "incentives:" , incentive_block ] ,
[ "violation:" , violation_block ] ,
[ "duration:" , scalar ] ,
[ "lifecycle:" , lifecycle_block ] , (* 付録E *)
[ "monitors:" , { "-" , monitor_def } ] , (* 付録E *)
[ "norms:" , { "-" , norm_def } ] , (* 付録F *)
[ "counts_as:" , { "-" , counts_as_def } ] , (* 付録F *)
[ "enforcement:" , enforcement_block ] , (* 付録G *)
[ "delegations:" , { "-" , delegation_def } ] , (* 付録G *)
[ "grounding:" , grounding_block ] ; (* 付録J *)
authority_block = [ "decision_scope:" , text ] ,
[ "decision_holder:" , actor_ref ] ,
[ "beta:" , number ] ,
[ "mode:" , text ] ;
information_block = [ "alpha:" , number ] ,
[ "views:" , { actor_ref , ":" , text } ] ,
[ "sharing:" , { "-" , sharing_entry } ] ;
sharing_entry = actor_ref , "->" , actor_ref , ":" , identifier ; (* string *)
incentive_block = [ "type:" , text ] ,
[ "lambda:" , number ] ,
[ "rules:" , { "-" , text } ] ;
violation_block = [ "detect:" , text ] ,
[ "action:" , text ] ,
[ "escalation:" , text ] ;
assume: と guarantee: の各要素は,predicate(A.10)を保持する文字列である。
alpha,beta,lambda は [0, 1] の範囲になければならない。parties: は
宣言済みのアクターを少なくとも1つ挙げなければならず,契約の中のアクター参照は
すべて actors: で宣言されたアクターを指さなければならない。duration: は
indefinite,duration_lit,またはイベントの記述のいずれかである。
sharing_entry は,引用符で囲んだ文字列として書かなければならない
(- "TAXI[*] -> CENTRAL : position")。引用符がないと,YAMLはこれを文字列ではなく,
項目が1つのマッピングとして読む。
A.5 プロトコル
protocol_def = "id:" , identifier ,
"trigger:" , text ,
[ "precondition:" , text ] ,
"steps:" , { "-" , step } ,
[ "timing:" , { identifier , ":" , scalar } ] ,
[ "fallback:" , { identifier , ":" , text } ] ,
[ "rollback:" , rollback_block ] ,
[ "postcondition:" , text ] ,
[ "safety_invariant:" , text ] ;
rollback_block = [ "condition:" , text ] ,
[ "action:" , text ] ;
step = message_step | compute_step | conditional_step
| parallel_step | barrier_step ;
message_step = actor_ref , "->" , actor_ref , ":" , step_expr ;
compute_step = actor_ref , ":" , step_expr ;
conditional_step = "if" , predicate , ":" , { "-" , step } ,
[ "else:" , { "-" , step } ] ;
parallel_step = "parallel:" , { "-" , step } ;
barrier_step = "barrier:" , predicate ;
step_expr = function_call | identifier ;
message_step と compute_step は,シーケンスの1要素である。引用符で囲んだ
文字列(- "A -> B : msg(x)",推奨)として書いても,引用符なしで書いてもよい。
後者の場合,YAMLはこれを項目が1つのマッピングとして読むが,両者は等価である。
conditional_step,parallel_step,barrier_step は,キーが if <predicate>,
parallel,barrier のマッピングである。timing: の代表的なキーは
max_response,max_total,checkpoint_interval であり,fallback: の
代表的なキーは on_timeout と on_failure である。
A.6 アルゴリズム
algorithm_def = identifier , ":" , algorithm_body ;
algorithm_body = [ "central:" , text ] ,
[ "local:" , text ] ;
algorithms: は,機能の名前(たとえば pathfinding)から,中央側とローカル側で
用いるアルゴリズムへのマッピングである。
A.7 遷移
transition_def = "from:" , identifier ,
"to:" , identifier ,
[ "condition:" , predicate ] , (* string *)
[ "protocol:" , identifier ] ,
[ "safety_invariant:" , predicate ] ; (* string *)
from: と to: は運用モードの名前である。運用モードは遷移の中で使うことで導入され,
別個の宣言はない。protocol: は protocols: で宣言したプロトコルを
指すことが望ましい。
A.7.1 モードへの束縛
cadl 0.3.32から,ブロック regimes: で,運用モードごとに,宣言されたパラメータの値と
有効な契約を指定できる。
regimes_block = { identifier , ":" , regime_binding } ;
regime_binding = [ "parameters:" , { param_ref , ":" , scalar } ] ,
[ "contracts:" , contracts_in_force ] ;
param_ref = identifier , "." , ( "alpha" | "beta" | "lambda" )
| "environment" , "." , identifier ;
contracts_in_force = "active:" , { "-" , identifier }
| "suspended:" , { "-" , identifier } ;
transitions:
- { from: DISTRIBUTED, to: CENTRALIZED, condition: "orders_in_window < 22",
safety_invariant: "robots_on_road == 0" }
- { from: CENTRALIZED, to: DISTRIBUTED, condition: "orders_in_window >= 26" }
regimes:
DISTRIBUTED:
contracts: { suspended: [BAY_ASSIGNMENT] }
CENTRALIZED:
parameters:
ROUTING.beta: 0.9 # 契約 ROUTING の authority.beta
environment.bays: 3 # context.environment のエントリ bays
contracts: { active: [ROUTING, BAY_ASSIGNMENT] }
param_ref は,ファイルが宣言している値を指す。C.alpha,C.beta,C.lambda は,
id: C の契約の information.alpha,authority.beta,incentives.lambda であり,
environment.X は context.environment のエントリ X である。これらは,確率モデル拡張の
パラメータのソースと同じである(付録HのH.3節)。
意味。 モード R でのパラメータの値は,R がそれに束縛する値があればその値,なければ
宣言された値である。契約がモード R で有効であるのは,R が active: を与えてその契約を挙げて
いる場合,R が suspended: を与えてその契約を挙げていない場合,R がどちらも与えていない場合
である。エントリのないモードでは,宣言された値がすべてそのまま使われ,すべての契約が有効である。
regimes: のないファイルは,どのモードもエントリを持たないファイルと同じに扱う。モードを
持たない(transitions: のない)ファイルでは,空の regimes: ブロックがあっても,すべての
契約が常に有効である。宣言された値そのものは変わらず,契約はそこに書かれた数を保持する。モード R から R' への遷移は,R の
束縛を R' の束縛に置き換える。置き換わる時点は,次の「実行」で定める。
実行。 cadl 0.3.33から,本付録は,システムの実行の各ステップがどのモードにあるかを
定める。この規則は,regimes: ブロックの有無にかかわらず,transitions: を持つすべての
ファイルに適用する。束縛(パラメータの値と有効な契約)は,ブロックを持つファイルにだけ適用し,
ブロックのないファイルでは,すべての契約が各ステップで有効である。ステップは,実行環境が契約を評価する単位である。生成されるPythonの実行環境の1周期,
生成されるSolidityの runMonitorCycle() の1回の呼び出し,生成されるRegoのポリシーの1回の
判定,規範拡張のトレースの1つの観測(付録FのF.5節)がこれにあたる。
- 各ステップでは,ちょうど1つのモードが現在のモードである。
- 実行は初期モードで始まる。初期モードは,
transitions:の順で最初のfrom:のうち, どの遷移のto:でもないものであり,そのようなものがなければ最初の遷移のfrom:である。 これはcadl regime-mapのモード図の初期状態と同じである。ホストは,実行を別のモードで 始めてもよい。ホストがモードを名指すまでは,実行は初期モードにある。 - ステップの評価が終わった後に,現在のモードからの遷移を
transitions:の順に調べ,condition:が成り立つ最初の遷移を選ぶ。評価できない条件(与えられていない値を読む条件)は 成り立たないものとし,実行は続く。その遷移のsafety_invariant:はこのときに検査する。 それが成り立てば遷移をとる。成り立たないとき,または評価できないときは遷移をとらず,モードは 変わらず,処理系はとらなかった遷移を報告する。不変条件を検査せずに遷移をとることはない。 1つのステップでとる遷移は高々1つである。遷移のprotocol:は,当事者が遷移をどう進めるかを 示す。そのメッセージは送られたステップに属し,モードの変更を遅らせない。 - 束縛はモードとともに,2つのステップの間で変わる。ステップの評価(
assume:とguarantee:の 項目,モニター,規範,ポリシー,生成されたコードが読むパラメータの値)は,すべてそのステップの 現在のモードの束縛を使い,ほかのモードの束縛は使わない。したがって,2つの契約が同じステップで ともに有効になるのは,両方を有効とするモードがある場合に限られる。 - ステップで有効でない契約は,そのステップでは評価しない。規範拡張については,契約が有効で ないあいだに契約インスタンスが何を観測するかを,F.5節の「有効でない契約」で定める。規範 インスタンスは状態を保ち,期限と時間演算子の区間は進まず,そのあいだに起きたことは数えない。
改正拡張のバージョンを持つ実行は,これらの規則を効力を持つバージョンと組み合わせる。cadl 0.3.35
からは,ステップの終わりに選んだモードの遷移を,次のステップで効力を持つバージョンより先に行い,
有効な契約は効力を持つバージョンの束縛で決まる
(付録KのK.11の「バージョンとモード」)。
述語はパラメータを名指しできない(A.10)。そのため,モードのパラメータの値が変えるのは, その値を書き出すコード(SolidityとRegoのターゲットの制度パラメータ,生成されるPythonの実行環境の パラメータ)と,各モードをそれぞれ1つの設計として評価する付録Hと付録Iのモデルだけである。
生成されるRegoのポリシーのように自身では遷移をとらない実行環境には,ホストが現在のモードを
与える。その場合,遷移をとり,その不変条件を検査するのは,2と3に従うホストである。
transitions: を持つファイルの空のブロック(regimes: {})は何も束縛しないが,そのファイルを
束縛を持つファイルにする。生成されるコードはモードを読む(たとえば,Regoの契約のポリシーは
input.regime を必要とする)。
静的規則。 処理系は,次の違反をエラーとして報告しなければならない。
- R-1
regimes:のキーは,ファイルのモード,すなわちtransitions:のfrom:またはto:で用いる名前である。transitions:のないファイルはモードを持たないので,エントリも 持てない。YAML 1.1 が真偽値またはnullとして読むモード名(yes,ON,null)は, 引用符で囲まなければならない。 - R-2 エントリは,
parameters:とcontracts:以外のキーを持たない。 - R-3
param_refは,宣言された契約のうちその値を書いているもののalpha,beta,lambda,またはcontext.environmentのエントリを指す。 - R-4
C.alpha,C.beta,C.lambdaの値は[0, 1]の数である。environment.Xの 値はエントリと同じ型を持つ。真偽値には真偽値,整数には整数,数には整数または数,文字列には 文字列である。スカラーでないエントリは束縛できない。 - R-5
contracts:はactive:とsuspended:のちょうど一方を持ち,その列は宣言された 契約を,それぞれ高々1回挙げる。 - R-6 1つのモードは,同じパラメータを高々1回束縛する(
ROUTING.betaと"ROUTING . beta"は同じパラメータである)。また,そのモードで有効でない契約のalpha,beta,lambdaを束縛しない。 - R-7
stochastic: 0.1を宣言したファイルでは,モードがソースに束縛した値は,そのfrom:を持つすべてのモデルパラメータの,そのモードの設計での値である。model.regimes:は, 同じモードでそのパラメータに同じ値を与えてもよいが,別の値を与えてはならない(H.6)。 R-1からR-6に違反するregimes:ブロックがあると,モデルの設計は定まらない。
IR。 cadl sim-ir は,3層IR(モジュール cadl.sim.ir)に次の2つを加える。
transitionsの各要素は,遷移がsafety_invariantを持つとき,その述語を書かれたとおりに 持つ(conditionと同じ扱い)。持たないときは,キーそのものがない。regimes:を持つファイルでは,トップレベルのキーregimesが加わる。これは,transitions:に最初に現れる順に,モードごとに1つの要素を持つ列である。
"regimes": [
{ "name": "DISTRIBUTED", "parameters": {},
"active_contracts": ["ROUTING", "FREE_PASSAGE"],
"suspended_contracts": ["BAY_ASSIGNMENT"] },
{ "name": "CENTRALIZED",
"parameters": { "ROUTING.beta": 0.9, "environment.bays": 3 },
"active_contracts": ["ROUTING", "BAY_ASSIGNMENT"],
"suspended_contracts": ["FREE_PASSAGE"] }
]
parameters は,モードが束縛する値を,スペースを含まない param_ref をキーとして持つ。そこにない
パラメータは宣言された値を持ち,その値はIRの契約(governance)または environment にある。
2つの契約の列は,すべての契約を宣言の順に挙げる。ブロックがR-1からR-6のいずれかに違反する
とき regimes は null である。model.regimes: との矛盾(R-7)は確率モデルだけに関わり,
そのときも regimes は出力される。ブロックのないファイルにはこのキーがなく,そのIRは,
safety_invariant を除いて cadl 0.3.31と同じである。
A.8 検証ブロック
verify_def = "id:" , identifier ,
"type:" , text ,
[ "target:" , verify_target ] ,
[ "property:" , text ] ,
[ "method:" , verify_method ] ,
[ "expr:" , predicate ] , (* string *)
[ "bound:" , int_literal ] ;
verify_target = identifier
| identifier , "->" , identifier ; (* FROM->TO *)
verify_method = "smt" | "model_check" | "simulation" | "proof" ;
type: は性質の種類を表し,たとえば consistency,deadlock,safety,
liveness を書く。target: は対象の契約,プロトコル,または遷移の名前である。すなわち,契約または
プロトコルの id,運用モードの名前,または2つの運用モードの間の遷移を表す FROM->TO を書く。
method: の既定値は smt である。宣言された手法を実装していない処理系は,
その項目を報告せずに読み飛ばすのではなく not_supported として報告しなければならず,
未知の手法はエラーとして報告しなければならない。宣言されたものを何も指さない target: は,
エラーとして報告することが望ましい。
A.9 コード生成ブロック
codegen_def = [ "target:" , hyphen_name ] ,
[ "output:" , text ] ,
[ "mappings:" , { identifier , ":" , text } ] ;
target: の既定値は python である。ターゲットの名前は
付録Dに一覧する。output: は出力先のパスであり,
mappings: はターゲットに固有の名前の対応を生成器に渡す。
A.10 式
predicate は,1つのYAML文字列スカラーの中に書く。
predicate = or_expr ;
or_expr = and_expr , { "OR" , and_expr } ;
and_expr = not_expr , { "AND" , not_expr } ;
not_expr = "NOT" , not_expr
| comparison ;
comparison = arith_expr , [ comp_op , arith_expr ]
| quantified_expr ;
comp_op = "==" | "!=" | "<=" | ">=" | "<" | ">" ;
quantified_expr = ( "for all" | "exists" ) , identifier , "in" ,
arith_expr , ":" , predicate ;
arith_expr = term , { ( "+" | "-" ) , term } ;
term = factor , { ( "*" | "/" ) , factor } ;
factor = "(" , predicate , ")"
| "-" , factor
| function_call
| member_access
| literal
| indexed_ref ;
function_call = identifier , "(" , [ arg_list ] , ")" ;
arg_list = arg , { "," , arg } ;
arg = predicate | comprehension ;
comprehension = predicate , "for" , identifier , "in" ,
( range_expr | arith_expr ) ;
member_access = indexed_ref , "." , identifier , { "." , identifier } ;
indexed_ref = identifier ,
[ "[" , ( "*" | range_expr | arith_expr ) , "]" ] ;
演算子の結合の強さは,弱いものから順に OR,AND,NOT,比較,+ -,
* /,単項の - である。数値リテラルの前の単項 - は負の数を表す
(permit_state == -2)。それ以外の因子の前では,-x の値は 0 - x の値と同じである。優先順位が等しい二項演算子は左結合である。比較は結合的でない
(a < b < c は述語ではない)。量化子の有効範囲は,右方向へ可能な限り広くとる。
トークンの間の空白は無視する。
comprehension は集約関数の引数であり,束縛された識別子の値ごとに,その predicate を
1回評価する。たとえば sum(ROBOT[i].goal_count for i in 1..N) や
sum(r.load for r in ROBOT[*]) である。
この付録は,量化子と内包表記の形を定めるが,集約関数の集合や,観測の上でのこれらの式の値は
定めない。規範拡張は,その動的意味論のためにこれらを定める。量化子と内包表記の定義域
(記号の境界を持ちうるアクターの集合,または範囲),束縛された識別子の意味,集約関数
sum,count,min,max,avg,およびメンバーがすべてはわかっていない定義域の上での
3値の値である(付録FのF.5節の「限量子と集約」)。
ROBOT[*].battery > 10 のように定義域の外で * または範囲を持つ indexed_ref は,
規範拡張が限量子または内包表記に書き換える略記である(付録FのF.5節の
「ワイルドカード参照と範囲参照」)。それを含む最小の比較がすべてのメンバーについて成り立つことを表し,
集約の引数の中ではメンバーを動く。
assume: または guarantee: の要素がこの文法に従わなくても,構文エラーには
ならない。その要素は不透明な述語として保持され,処理系はそれを変更せずに
引き渡し,形式検証の対象から除く。これにより,設計レベルでは自然言語による
条件を書くことができる。A.5のステップの式と条件についても同様である。
A.11 予約語
式の部分言語のキーワード。これらを識別子として用いてはならない。
AND OR NOT true false for all exists in
単独の for(内包表記を導入する)と all は予約語ではない。IN(大文字。モニターの
rule の中での集合への所属,付録E)と in(小文字。量化子と
内包表記の定義域)は,別のキーワードである。
構造のキー。認識されるブロックごとに示す。
| ブロック | キー |
|---|---|
| ファイル | sos |
sos | name type version description extensions context actors contracts protocols algorithms transitions regimes metrics verification codegen motivation model |
context | environment assumptions |
| アクター | id role autonomy capabilities interface(input output) |
| 契約 | id parties assume guarantee authority information responsibilities incentives violation duration lifecycle monitors norms counts_as enforcement delegations grounding |
| 規範(付録F) | id kind bearer counterparty trigger until content deadline on_violation(severity sanction reparation transition) effects(activate suspend resume discharge) on_amendment(transform) |
| counts-as規則(付録F) | when creates if |
| エージェント統治(付録G) | アクターの agent(kind protocol tools),契約の enforcement(default point)と delegations(norm to grant revoke max_depth until),禁止の on_denied(escalate_to timeout fallback notify) |
| 確率モデル(付録H) | model(kind parameters variables commands labels regimes rewards properties regime_maps)。各要素のキーはH.2に示す |
| 戦略モデル(付録I) | model(players profiles compliance payoffs equilibria),コマンドの owner,性質とモードマップの profile。各要素のキーはI.2に示す |
| 改正(付録K) | sos の amendment(previous effective transitional decisions layers parameters),メトリクスの schedule(from target decision),measure(window every aggregate runs across_runs description decision)。各項目のキーはK.3からK.5に示す |
| 根拠付け(付録J) | 契約の grounding(items tolerance),規範の shares,on_fulfilment(reward magnitude),on_violation(magnitude),利得の項の sanction_of reward_of |
authority | decision_scope decision_holder beta mode |
information | alpha views sharing |
incentives | type lambda rules |
violation | detect action escalation |
| プロトコル | id trigger precondition steps timing fallback rollback(condition action) postcondition safety_invariant |
| ステップ | if else parallel barrier |
| アルゴリズム | central local |
| 遷移 | from to condition protocol safety_invariant |
| モードへの束縛(A.7.1) | parameters contracts(active suspended) |
| メトリクス | id formula target |
| 検証 | id type target property method expr bound |
| コード生成 | target output mappings |
列挙値: Directed Acknowledged Collaborative Virtual(SoSの型),
low medium high(自律度),smt model_check simulation proof
(検証手法),ms s min h(時間の単位)。拡張のキーと値は
付録C,付録E,付録F,付録G,付録H,付録I,付録J,付録Kに示す。
A.12 リファレンス実装の状況(cadl 0.3)
リファレンス実装は,YAML 1.1のローダーでファイルを読み,寛容に振る舞う。
パーサが拒否するのは,sos: マッピングの欠落,不正なYAML,不正な type:,
および数値でない alpha,beta,lambda だけである。
cadl check は,これに加えて,idの重複,未宣言のアクター,重複して挙げられた当事者,
当事者のない契約,[0, 1] の範囲外のガバナンスパラメータ,Minor,Major,
Critical 以外の severity:,low,medium,high 以外の autonomy:,
識別子でないidや運用モードの名前,形式に合わない sharing: の要素,
および付録Eの規則L-1,L-2,L-3,L-5,M-1(cadl 0.3.11から),M-3への違反,および(cadl 0.3.12から)読み取れない deadline: と sampling: の値を
エラーとして報告する。assume: または guarantee: の
項目の中では,名前が添字付きである(ROBOT[i])か,メンバーアクセスの対象である
(ROBOT.battery)とき,添字の中に現れる場合も含めて,その名前はアクターへの参照と
みなされ,宣言されていなければならない。単独で現れる名前は状態変数とみなされ,
検査されない。condition:,safety_invariant:,formula:,expr:,モニターの
rule:,ライフサイクルの when:,およびメッセージイベントでない on: の述語については,未宣言のアクターの検査を行わない。それ以外の必須キーが
欠けている場合は,空の値で置き換える。cadl 0.3では,次の点で本付録と相違する(cadl 0.3.36で確認)。
- 式。
cadl0.3.36では,式はA.10とA.11に従う。既知の相違はない。cadl0.3.17までは,factorの単項-を受け付けなかった。それを使った項目は不透明な述語として保持し, ライフサイクルのon:とwhen:,モニターのrule:についてはcadl checkが警告を出した。 - 識別子。
cadl0.3.9からは,cadl checkは,アクター,契約,プロトコル,メトリクスのid, および運用モードの名前が,A.1の識別子でない場合(たとえば非ASCII文字やハイフンを含む場合), またはA.11の予約語か付録EのINである場合に,エラーとして報告する。cadl0.3.10からは,ライフサイクルの状態の名前,ライフサイクルの遷移とモニターのid, およびモニターの違反ラベルにも同じ検査が適用される。検証項目のidは検査されない。cadl0.3.12までは,これらの名前や運用モードの名前に引用符なしで書いたtrue/falseは YAMLが真偽値として読み,True/Falseという名前として受理されていた。 - 範囲。 上限が記号である範囲(
"TAXI[1..N]")は,書かれたとおりに保持される。Nをenvironment:から引くことはなく,添字が宣言された範囲に収まるかどうかも 検査されない。cadl sim-genがcountを出力するのは,両端が整数のときだけである。 - 型。 5.2.1節の型は検査されない。型構成子を用いて書いた値(たとえば
Range(1, 4))は, テキストのまま保持される。 - 寛容な形式。 パーサは,1つの文字列として書いた
parties:("[A, B]"), 負でない数値のdeadline:(小数でもよく,秒として読まれる),単位の前に空白を含む期間 (5 s,periodic( 500ms )),マッピング{kind: periodic, period_ms: <負でない整数>}または{kind: event}として書いたsampling:,および大文字と小文字を問わないmethod:も受理する。 これらの形式は本付録の一部ではない。 - ステップ。
cadl0.3.10からは,conditional_stepのelse:の分岐と,barrier_stepの条件が 保持される。したがって,else:の分岐に現れるアクターは検査され,どちらもシミュレータIRに 出力される。それより前のリリースは,これらを捨てていた。 - 契約。
cadl0.3.9からは,"SOURCE -> TARGET : item"の形式の文字列でないsharing:の要素, および項目が識別子で始まらない要素は,cadl checkでエラーとなる。それより前のリリースは, 引用符なしの要素を診断なしに捨てていた。"A -> B : report(period: 5s)"の引数のように, 項目が識別子で始まり,その後ろに別の文字列が続く要素は,警告を出したうえで受理され, 先頭の名前だけが保持される。この形式は本付録の一部ではない。cadl0.3.10からは,low,medium,high以外のautonomy:の値は,cadl checkで エラーとなる。それより前のリリースは,診断なしにmediumとして読んでいた。 - モード。
cadl0.3.32からは,cadl checkはA.7.1のR-1からR-7を適用する。束縛は, 各ツールがパラメータと契約を読むところで使われる。cadl sim-irはそれを書き出し(A.7.1),cadl sim-genはpythonとgoの設定(regimes)とunityの設定 (regimeBindings)に渡す。cadl verifyは,当事者を共有する契約の組をすべて検査する。 A.7.1のモードへの束縛のもとで両方が有効なモードがない組は,2つが矛盾する場合も含めて, それぞれが有効なモードを挙げたinfoとして報告する。cadl0.3.33からは,実行の各ステップが 1つのモードの束縛を持つ(A.7.1の「実行」)ので,2つが同じステップでともに有効になることは ないからである。この時点を定めていなかった0.3.32では,このような矛盾は警告(WARN)であった。 あるモードで両方が有効な組はこれまでどおり判定し,ソルバーが判定できない組はunknownの ままとする。モードを持たないファイルではすべての契約が有効なので,空のregimes:ブロックが あっても,すべての組をこれまでどおり判定する。cadl regime-mapは,cadl0.3.33から, 各モードの束縛をテキスト,DOT,JSONの出力に示す(JSONではキーregimesにIRと同じ形で示し, R-1からR-6に反するブロックではnullとする)。その解析は遷移だけを読み,束縛によって 変わらない。コード生成は,cadl0.3.33から束縛を適用する(付録Dの D.1節)。pythonターゲットは,モードの制御クラスを初期モードで始め,モードでない名前を 拒否し,遷移の安全不変条件を明示的に検査して,成り立たなければ遷移をとらない。制御クラスには メソッドparameters(),contract_active(),apply_bindings()を与え,現在のモードの値をctx.parametersに置き,契約のモニターをその契約が有効なモードでだけ実行する(0.3.32から)。 その規範のモニターとcadl norms-evalは,現在のモードをトレースから読む。トレースは, モードを名指すまでは初期モードにある(F.5節,F.10節)。solidityターゲットは,1つのステップを オーケストレータの1回の呼び出しとし,安全不変条件を同じように検査する。solidityとopaの ターゲットは,有効な契約と制度パラメータについて現在のモードを読む。cadl0.3.36からは,opaとsolidityの規範のモニター(D.5節),unity-csharpターゲット, 付録Gの境界ポリシー(cadl agents-decide,agent-rego,agent-cedar)も 現在のモードに従う。0.3.33から0.3.35までは,あるモードで有効でない契約についてこれらは拒否していた。cadl0.3.36からは,cadl agents-runと付録Gのゲートウェイも現在のモードに従う。トレースの行, またはゲートウェイのホストがモードを示す(G.13)。0.3.33から0.3.35までは,強制される契約を 有効としないモードがあるファイルを拒否した。0.3.32までは,生成されるunity-csharp,solidity,opaのコード, 規範のオンラインモニター,cadl regime-mapは束縛を使わず,Pythonのモードの制御クラスは 最初の遷移のfrom:で始まり,安全不変条件をassertで検査していた。SolidityのRegimeControllerは,アルファベット順で最初のモードで始まり,不変条件を検査せず,値を設定する 関数を持たず,だれでも呼べた。0.3.33からは,「実行」の規則(初期モード,明示的な検査, オーケストレータの1回の呼び出しを1つのステップとすること)を,遷移を持つすべてのファイルに 適用する。遷移のsafety_invariantは,cadl0.3.32からIRとシミュレータの設定に含まれる。0.3.31まではcadl checkが検査していたが,cadl sim-irは出力しなかった。 - 検証。
method:,expr:,bound:は読み込まれる。smt以外の手法はnot_supportedとして報告され(テキスト出力では[SKIP]と表示される),未知の手法は エラーとなる。宣言されたものを何も指さないtarget:は,どの手法についてもエラーとなる。smtの項目については,充足不能なexpr:はエラーとなり,A.10に適合しないexpr:はunknownとして報告され,検査されない。exprをモデルに対して証明することはしない。 6.3節の契約と遷移の検査は,項目の有無にかかわらず実行される。 - コード生成。
codegen:の項目は構文解析されるが,それに基づく処理は行われない。 ターゲットはコマンドラインで選択する(付録D)。cadl0.3.9からは,実装が出力できないtarget:を持つ項目(たとえばtarget: ros2)について,cadl check,cadl verify,cadl codegenが警告を出す。これは付録DのD.4節が 求める診断であり,ファイルは有効なままである。コマンドラインの-t ros2は拒否される。 - 拡張。
lifecycle:とmonitors:は,extensions:がsos-dslを宣言しているかどうかに かかわらず認識される。cadl0.3.9からは,cadl checkは,sos-dsl以外のextensions:の名前,0.1以外のsos-dslのバージョン,およびmotivation:ブロックについて,情報レベルの診断を出す。 この診断によってファイルが無効になることはない。これは,拡張を実装していない処理系に 付録Cが求めるものである。motivation:ブロックは解釈されないが,cadl sim-irは,このブロックを書かれたとおりにmotivation_blockというキーで引き渡す (付録CのC.6節)。ファイルにこのブロックがなければ,このキーは出力されない。cadlが付録Eそのものに対して満たしていない点は,E.4節に示す。cadl0.3.19からは,宣言された拡張normsのバージョン0.1を実装しており,この診断は出ない。cadlが付録Fのどこまでを実装しているかは,F.10節に示す。cadl0.3.20からは,agents0.1(付録GのG.13節)とstochastic0.1 (付録HのH.14節)についても同様である。また,cadl sim-irは キーstochastic_modelを出力する。この拡張を用いないファイルでは,その値はnullである。cadl0.3.22は,H.9の認証付きのモードマップ,G.5からG.8のランタイムと規則G-17からG-19, および生成したPythonコードでの規範のオンライン監視を追加する。それぞれの範囲は,上に挙げた 3つの節に示す。拡張games0.1 (付録IのI.14節)とgrounding0.1 (付録JのJ.11節)は,cadl0.3.23から 実装している(cadl game-check,cadl norms-indices)。それぞれの範囲は,挙げた2つの節に示す。 0.3.22までは,これらの名前には,未知の拡張に対する情報レベルの診断が出ていた。kind: smgを持つ モデルについて,cadl check0.3.22は,H.10とH.15が1つの情報レベルの診断を求めるところで,S-1とS-9の 誤りを報告する。また,付録Jのキーを,診断なしに無視する。拡張amendment0.1 (付録KのK.9節)は,cadl0.3.32から 実装している(cadl amend-diff)。0.3.31までは,この名前には未知の拡張に対する情報レベルの診断が出て おり,そのキーは無視されていた。
cadl の0.3.7より前のリリースは,これらの点のいくつかで異なっていた。その経緯は,cadlリポジトリの
CHANGELOGにある。