Appendix A. Syntax Reference (EBNF)
A CADL file is a YAML 1.2 document [Ben-Kiki+, 2021]. This appendix gives the reference grammar of CADL v0.3 in two parts: the structure of the document (A.2–A.9), written as EBNF over YAML mappings and sequences, and the expression sub-language (A.1, A.10) that is written inside individual YAML string scalars.
Chapter 5 and this appendix describe the same
syntax. This appendix is normative for the concrete syntax; Chapter 5 is
explanatory. The
reference implementation (cadl)
is expected to accept exactly this syntax; known deviations of cadl 0.3 are
listed in A.12.
To try the grammar, install the reference implementation (see
Path B of the Quick Start) and run cadl parse or cadl check; runnable
files are in the examples/ directory of the
cadl repository.
Notation. The grammar uses ISO/IEC 14977 EBNF [ISO/IEC 14977:1996] with the following conventions.
- A terminal ending in a colon, such as
"name:", is a key of a YAML mapping, followed by its value. The entries of one mapping may appear in any order, each at most once. { "-" , x }is a YAML sequence whose items arex. Block style and flow style ([a, b]) are equivalent.k , ":" , vwith a non-terminalkis a mapping whose keys are chosen by the author.textis any YAML string scalar,numberany YAML integer or float, andscalarany YAML scalar. Their content is not interpreted further.any_charis any single character. Thestringrule (A.1) excludes the double quotation mark from it, so a string ends at the next".- Productions marked
(* string *)describe the content of a single YAML string scalar.
Indentation, comments, quoting, and the choice between block and flow
style are governed by YAML and are not shown. A scalar that contains
[, ], *, ->, or ": " — for example an actor reference such as
"TAXI[*]" or a step such as "A -> B : msg" — SHOULD be quoted, and
MUST be quoted inside a flow sequence, where YAML would otherwise read
it differently. A sharing_entry (A.4) MUST be a quoted string
wherever it is written.
Keys that this appendix does not define are not part of CADL v0.3. A processor MUST NOT reject a file because of them; the reference implementation ignores them.
The grammar covers the design and verification levels of Section 5.1.1. An overview-level description is informal input for AI-assisted refinement and need not conform to it.
A.1 Lexical rules
These rules apply inside scalars.
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 ;
A duration_lit is an integer followed by its unit: 2.5s is not a
duration, and the same time is written 2500ms. A string is delimited
by double quotes only: 'k' is not a string.
identifier names actors, contracts, protocols, regimes, and metrics.
hyphen_name is used only for extension names and codegen target names
(for example sos-dsl, unity-csharp). Numeric literals are unsigned.
Identifiers are ASCII. Strings and comments may contain any Unicode
character, which is what requirement NFR-7
(Chapter 4) asks for. From cadl 0.3.9 the
reference implementation reports an id or regime name that violates the
ASCII rule as an error (A.12).
A.2 Top-level structure
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 ] , (* Appendix H *)
[ "amendment:" , amendment_block ] ; (* Appendix K *)
sos_type = "Directed" | "Acknowledged" | "Collaborative" | "Virtual" ;
extension_decl = hyphen_name , ":" , scalar ;
One file contains one SoS definition. version: is conventionally a
semantic version string such as "1.0.0".
Extension points. extensions: declares the language extensions a
file relies on, each as a name and a version (for example
- sos-dsl: 0.1). Eight extensions are defined; all but the last have a
name that can be declared:
- the SoS-DSL extension (Appendix E),
declared as
sos-dslwith version0.1, which adds the keyslifecycle:andmonitors:tocontract_def(A.4); - the norms extension (Appendix F), declared as
normswith version0.1, which adds the keysnorms:andcounts_as:tocontract_def(A.4) and bounded temporal operators to the predicates of a contract. A file that uses it MUST declare it; - the agent governance extension (Appendix G),
declared as
agentswith version0.1, which requiresnormsand adds the keyagent:toactor_def(A.3), the keysenforcement:anddelegations:tocontract_def(A.4), andon_denied:to a prohibition; - the stochastic model extension
(Appendix H), declared as
stochasticwith version0.1, which adds the keymodel:tosos_body; - the strategic model extension
(Appendix I), declared as
gameswith version0.1, which requiresstochasticand adds players, profiles, payoffs, and equilibrium queries tomodel:; - the grounding extension
(Appendix J), declared as
groundingwith version0.1, which requiresnormsand adds the keygrounding:tocontract_def(A.4), the keysshares:andon_fulfilment:to a norm andmagnitude:to itson_violation:, and, withgames, the keyssanction_of:andreward_of:to a payoff term; - the amendment extension
(Appendix K), declared as
amendmentwith version0.1, which adds the keyamendment:tosos_body(amendable parameters, the version and its transitional provisions, decision records) and the keysschedule:andmeasure:tometric_def(A.3); - the motivation extension (Appendix C),
which defines
motivation_block. It has noextensions:name in v0.3 and is used simply by writing amotivation:block.
A.3 Context, actors, metrics
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 ] ; (* Appendix G *)
autonomy_level = "low" | "medium" | "high" ;
interface_def = [ "input:" , { "-" , text } ] ,
[ "output:" , { "-" , text } ] ;
metric_def = "id:" , identifier ,
[ "formula:" , predicate ] , (* string *)
[ "target:" , scalar ] ,
[ "schedule:" , { "-" , schedule_entry } ] , (* Appendix K *)
[ "measure:" , measure_def ] ; (* Appendix K *)
autonomy: defaults to medium. In actor_def, the index of id: is
normally a range ("ROBOT[1..N]") and declares a parameterised set of
actors. The upper bound of a range_expr is an integer or an
identifier. An identifier such as N is a symbolic size; v0.3 has no
construct that binds it to a value (see
A.12 for what the reference
implementation does with it). A non-string value in environment: is read as a literal
(A.1); a string value is kept verbatim.
A.4 Contracts (Institution layer)
The Institution layer consists of contracts:, defined here, together
with actors: (A.3) and 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 ] , (* Appendix E *)
[ "monitors:" , { "-" , monitor_def } ] , (* Appendix E *)
[ "norms:" , { "-" , norm_def } ] , (* Appendix F *)
[ "counts_as:" , { "-" , counts_as_def } ] , (* Appendix F *)
[ "enforcement:" , enforcement_block ] , (* Appendix G *)
[ "delegations:" , { "-" , delegation_def } ] , (* Appendix G *)
[ "grounding:" , grounding_block ] ; (* Appendix 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 ] ;
Each item of assume: and guarantee: is a string holding a
predicate (A.10). alpha, beta, and lambda MUST lie in [0, 1].
parties: MUST name at least one declared actor, and every actor
reference in a contract MUST refer to an actor declared in actors:.
duration: is indefinite, a duration_lit, or an event description.
A sharing_entry MUST be written as a quoted string
(- "TAXI[*] -> CENTRAL : position"); unquoted, YAML reads it as a
one-entry mapping and not as a string.
A.5 Protocols
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 ;
A message_step or compute_step is one sequence item. It may be
written as a quoted string (- "A -> B : msg(x)", recommended) or
unquoted, in which case YAML reads it as a one-entry mapping; both forms
are equivalent. conditional_step, parallel_step, and barrier_step
are mappings whose key is if <predicate>, parallel, or barrier.
Typical keys of timing: are max_response, max_total, and
checkpoint_interval; typical keys of fallback: are on_timeout and
on_failure.
A.6 Algorithms
algorithm_def = identifier , ":" , algorithm_body ;
algorithm_body = [ "central:" , text ] ,
[ "local:" , text ] ;
algorithms: is a mapping from a function name (for example
pathfinding) to the algorithms used centrally and locally.
A.7 Transitions
transition_def = "from:" , identifier ,
"to:" , identifier ,
[ "condition:" , predicate ] , (* string *)
[ "protocol:" , identifier ] ,
[ "safety_invariant:" , predicate ] ; (* string *)
from: and to: name regimes. A regime is introduced by its use in a
transition; there is no separate declaration. protocol: SHOULD name a
protocol declared in protocols:.
A.7.1 Regime bindings
From cadl 0.3.32 the block regimes: binds, per regime, values of
declared parameters and the contracts in force.
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 # authority.beta of the contract ROUTING
environment.bays: 3 # the entry bays of context.environment
contracts: { active: [ROUTING, BAY_ASSIGNMENT] }
A param_ref names a value that the file declares: C.alpha,
C.beta, and C.lambda are information.alpha, authority.beta, and
incentives.lambda of the contract with id: C, and environment.X is
the entry X of context.environment. These are the sources of a
parameter of the stochastic model extension
(Appendix H, H.3).
Semantics. In a regime R, the value of a parameter is the value
that R binds to it, if any, and otherwise its declared value. A
contract is in force in R when R gives active: and lists it, when
R gives suspended: and does not list it, or when R gives neither.
A regime without an entry keeps every declared value and has every
contract in force; a file without regimes: behaves as one in which no
regime has an entry. A file without regimes (without transitions:)
has every contract in force at all times, even when it has an empty
regimes: block. The declared values themselves are not changed: the
contract keeps the number written in it. A transition from R to R'
replaces the bindings of R by those of R', at the point that "Runs"
below fixes.
Runs. From cadl 0.3.33 this appendix fixes in which regime a run
of the system is at each step. These rules apply to every file with
transitions:, with or without a regimes: block; the bindings
(parameter values and the contracts in force) apply only to a file with
the block, and without it every contract is in force at every step. A step is the unit at which a runtime
evaluates contracts: one cycle of the generated Python runtime, one call
of runMonitorCycle() of the generated Solidity, one decision of the
generated Rego policy, and one observation of a trace of the norms
extension (Appendix F, F.5).
- At every step exactly one regime is current.
- A run starts in the initial regime: the first
from:, in the order oftransitions:, that is not theto:of any transition, and otherwise thefrom:of the first transition. This is the initial state of the regime map ofcadl regime-map. A host MAY start a run in another regime; until it names one, the run is in the initial regime. - After the evaluations of a step, the transitions from the current
regime are considered in the order of
transitions:, and the first whosecondition:holds is selected; a condition that cannot be evaluated (it reads a value that is not given) does not hold, and the run goes on. Itssafety_invariant:is checked then: when it holds, the transition is taken; when it does not hold, or cannot be evaluated, the transition is not taken, the regime stays, and the processor reports the refused transition. A transition is never taken without its invariant. At most one transition is taken per step. Theprotocol:of a transition names how the parties carry it out; its messages belong to the steps at which they are sent and do not delay the change of regime. - The bindings change together with the regime, between two steps.
Every evaluation of a step (the
assume:andguarantee:items, the monitors, the norms, and the policies, and every parameter value that generated code reads) uses the bindings of the regime current at that step and of no other regime. Two contracts are therefore in force at the same step only if some regime has both in force. - A contract that is not in force at a step is not evaluated at it. For the norms extension, F.5 ("Contracts not in force") defines what a contract instance sees when its contract is not in force: its norm instances keep their states, their deadlines and the intervals of the temporal operators do not advance, and nothing that happens meanwhile counts.
A run with versions of the amendment extension combines these rules
with the versions in force: from cadl 0.3.35 the regime transition
chosen at the end of a step is taken before the versions that take
effect at the next step, and the contracts in force are those of the
bindings of the version in force
(Appendix K, K.11, "Versions and regimes").
A predicate cannot name a parameter (A.10), so the parameter values of a regime change only the code that writes them out (the institutional parameters of the Solidity and Rego targets, the parameters of the generated Python runtime) and the models of Appendices H and I, which evaluate each regime as a design of its own.
A runtime that does not take transitions itself, such as the generated
Rego policies, is told the current regime by its host; the host then
takes the transitions and checks their invariants as items 2 and 3 say.
An empty block (regimes: {}) in a file with transitions: binds
nothing, but makes the file one with bindings: the generated code reads
the regime (for example, a Rego contract policy then requires
input.regime).
Static rules. A processor MUST report the following as errors.
- R-1 A key of
regimes:is a regime of the file, a name used infrom:orto:oftransitions:. A file withouttransitions:has no regimes and therefore no entries. A regime name that YAML 1.1 reads as a boolean or null (yes,ON,null) MUST be quoted. - R-2 An entry has no keys other than
parameters:andcontracts:. - R-3 A
param_refnamesalpha,beta, orlambdaof a declared contract that writes that value, or an entry ofcontext.environment. - R-4 The value of
C.alpha,C.beta, orC.lambdais a number in[0, 1]. The value ofenvironment.Xhas the type of the entry: a boolean for a boolean, an integer for an integer, an integer or a number for a number, a string for a string; an entry that is not a scalar cannot be bound. - R-5
contracts:has exactly one ofactive:andsuspended:, and its list names declared contracts, each at most once. - R-6 A regime binds a parameter at most once (
ROUTING.betaand"ROUTING . beta"are the same parameter), and it does not bindalpha,beta, orlambdaof a contract that is not in force in it. - R-7 In a file that declares
stochastic: 0.1, the value that a regime binds to a source is the value, under the design of that regime, of every model parameter with thatfrom:.model.regimes:MAY give such a parameter the same value in the same regime and MUST NOT give it another one (H.6). Aregimes:block that breaks R-1 to R-6 leaves the designs of the model undefined.
IR. cadl sim-ir writes two additions to the three-layer IR
(module cadl.sim.ir):
- each entry of
transitionscarriessafety_invariant, the predicate as written (likecondition), when the transition has one; the key is absent otherwise; - a file with
regimes:gets the top-level keyregimes, a list with one entry per regime in order of first appearance intransitions::
"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 holds the values the regime binds, keyed by the
param_ref without spaces; a parameter that is absent has its declared
value, which the IR keeps in the contract (governance) or in
environment. The two contract lists are complete and in declaration
order. regimes is null when the block breaks one of R-1 to R-6; a
conflict with model.regimes: (R-7) concerns the stochastic model only,
and regimes is then written. The key is absent for a file without the
block, whose IR is the same as in cadl 0.3.31 apart from
safety_invariant.
A.8 Verification block
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: names the kind of property, for example consistency,
deadlock, safety, or liveness. target: names the contract,
protocol, or transition concerned: the id of a contract or protocol,
the name of a regime, or FROM->TO for the transition between two
regimes. method: defaults to smt. A
processor that does not implement a declared method MUST report the
entry as not_supported rather than skip it silently, and MUST report
an unknown method as an error. A target: that names nothing declared
SHOULD be reported as an error.
A.9 Codegen block
codegen_def = [ "target:" , hyphen_name ] ,
[ "output:" , text ] ,
[ "mappings:" , { identifier , ":" , text } ] ;
target: defaults to python. The target names are catalogued in
Appendix D. output: is the output path and
mappings: passes target-specific name mappings to the generator.
A.10 Expressions
A predicate is written inside one YAML string scalar.
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 ) , "]" ] ;
Operators bind, from loosest to tightest: OR, AND, NOT, comparison,
+ -, * /, unary -. A unary - in front of a numeric literal
gives a negative number (permit_state == -2); in front of any other
factor, -x has the value of 0 - x. Binary operators of equal precedence associate to the
left. A comparison is not associative (a < b < c is not a predicate).
A quantifier extends as far to the right as possible. White space
between tokens is ignored.
A comprehension is the argument of an aggregate function and
evaluates its predicate once for each value of the bound identifier,
for example sum(ROBOT[i].goal_count for i in 1..N) or
sum(r.load for r in ROBOT[*]).
This appendix fixes the form of quantifiers and comprehensions, not the
set of aggregate functions or the values of these expressions on
observations. The norms extension defines them for its dynamic
semantics: the domain of a quantifier or comprehension (a set of
actors, possibly with a symbolic bound, or a range), the meaning of the
bound identifier, the aggregate functions sum, count, min, max,
and avg, and three-valued values over domains whose members are not
all known (Appendix F, F.5, "Quantifiers and
aggregates"). An indexed_ref with * or a range outside a domain,
as in ROBOT[*].battery > 10, is shorthand that the norms extension
rewrites into a quantifier or a comprehension
(Appendix F, F.5, "Wildcard and range
references"): the smallest comparison that contains it holds for every
member, and in the argument of an aggregate it ranges over the members.
An item of assume: or guarantee: that does not conform to this
grammar is not a syntax error: it is retained as an opaque predicate,
which a processor carries through unchanged and excludes from formal
verification. This permits natural-language conditions at the design
level. The same applies to step expressions and conditions in A.5.
A.11 Reserved keywords
Keywords of the expression sub-language. They MUST NOT be used as identifiers.
AND OR NOT true false for all exists in
for on its own (it introduces a comprehension) and all are not
reserved. IN (upper case, set membership inside a monitor rule,
Appendix E) and in (lower case, quantifier
and comprehension domains) are distinct keywords.
Keys of the structure, by the block in which they are recognised.
| Block | Keys |
|---|---|
| file | sos |
sos | name type version description extensions context actors contracts protocols algorithms transitions regimes metrics verification codegen motivation model |
context | environment assumptions |
| actor | id role autonomy capabilities interface (input output) |
| contract | id parties assume guarantee authority information responsibilities incentives violation duration lifecycle monitors norms counts_as enforcement delegations grounding |
| norm (Appendix 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 rule (Appendix F) | when creates if |
| agent governance (Appendix G) | actor agent (kind protocol tools); contract enforcement (default point), delegations (norm to grant revoke max_depth until); prohibition on_denied (escalate_to timeout fallback notify) |
| stochastic model (Appendix H) | model (kind parameters variables commands labels regimes rewards properties regime_maps); the keys of each entry are listed in H.2 |
| strategic model (Appendix I) | model (players profiles compliance payoffs equilibria); command owner; property and regime map profile; the keys of each entry are listed in I.2 |
| amendment (Appendix K) | sos amendment (previous effective transitional decisions layers parameters); metric schedule (from target decision), measure (window every aggregate runs across_runs description decision); the keys of each entry are listed in K.3 to K.5 |
| grounding (Appendix J) | contract grounding (items tolerance); norm shares, on_fulfilment (reward magnitude), on_violation (magnitude); payoff term sanction_of reward_of |
authority | decision_scope decision_holder beta mode |
information | alpha views sharing |
incentives | type lambda rules |
violation | detect action escalation |
| protocol | id trigger precondition steps timing fallback rollback (condition action) postcondition safety_invariant |
| step | if else parallel barrier |
| algorithm | central local |
| transition | from to condition protocol safety_invariant |
| regime binding (A.7.1) | parameters contracts (active suspended) |
| metric | id formula target |
| verification | id type target property method expr bound |
| codegen | target output mappings |
Enumerated values: Directed Acknowledged Collaborative Virtual
(SoS type); low medium high (autonomy); smt model_check
simulation proof (verification method); ms s min h
(duration units). The keys and values of the extensions are listed in
Appendix C,
Appendix E,
Appendix F,
Appendix G,
Appendix H,
Appendix I,
Appendix J, and
Appendix K.
A.12 Reference implementation status (cadl 0.3)
The reference implementation reads the file with a YAML 1.1 loader and
is lenient: only a missing sos: mapping, invalid YAML, an invalid
type:, and an alpha, beta, or lambda that is not a number are
rejected by the parser. cadl check additionally reports duplicate
ids, undeclared actors, a party listed twice, a contract without
parties, governance parameters outside [0, 1], a severity:
other than Minor, Major, or Critical, an autonomy: other than
low, medium, or high, an id or regime name that
is not an identifier, a malformed sharing: entry, and a violation of
rules L-1, L-2, L-3, L-5, M-1 (from cadl 0.3.11), or M-3 of
Appendix E, and (from cadl 0.3.12) a deadline: or
sampling: value that cannot be read, as errors. In an item of
assume: or guarantee:, a name counts as an actor reference, and
must be declared, when it is indexed (ROBOT[i]) or is the object of a
member access (ROBOT.battery), including inside an index; a name
standing alone is taken as a state variable and is not checked. The
predicates of condition:, safety_invariant:, formula:, expr:,
monitor rule:, lifecycle when:, and an on: that is not a message
event are not checked for undeclared actors. Other
missing required keys are replaced by an empty value. cadl 0.3
deviates from this appendix as follows (checked against cadl 0.3.36).
- Expressions. Expressions follow A.10 and A.11 in
cadl0.3.36; no deviation is known. Up tocadl0.3.17 the unary-offactorwas not accepted: an item that used it was kept as an opaque predicate, and for a lifecycleon:orwhen:or a monitorrule:,cadl checkgave a warning. - Identifiers. From
cadl0.3.9,cadl checkreports as an error an actor, contract, protocol, or metric id, or a regime name, that is not an identifier of A.1 (for example one with non-ASCII characters or a hyphen) or that is a reserved word of A.11 or theINof Appendix E. Fromcadl0.3.10 the same check applies to the names of lifecycle states, the ids of lifecycle transitions and monitors, and the violation labels of monitors. The ids of verification entries are not checked. Up tocadl0.3.12 an unquotedtrueorfalseused as such a name or as a regime name was read by YAML as a boolean, becameTrue/False, and was accepted. - Ranges. A range with a symbolic bound (
"TAXI[1..N]") is kept as written.Nis not looked up inenvironment:, and an index is not checked against the declared range.cadl sim-genwrites acountonly when both bounds are integers. - Types. The types of Section 5.2.1 are not
checked. A value
written with a type constructor (for example
Range(1, 4)) is kept as text. - Lenient forms. The parser also accepts
parties:written as one string ("[A, B]"), a non-negative numericdeadline:, possibly fractional (read as seconds), a duration or period with a space before its unit (5 s,periodic( 500ms )),sampling:written as the mapping{kind: periodic, period_ms: <non-negative integer>}or{kind: event}, and amethod:in any letter case. These forms are not part of this appendix. - Steps. From
cadl0.3.10 theelse:branch of aconditional_stepand the condition of abarrier_stepare retained, so actors named in anelse:branch are checked and both reach the simulator IR; earlier releases discarded them. - Contracts. From
cadl0.3.9, asharing:entry that is not a string of the form"SOURCE -> TARGET : item", or whose item does not begin with an identifier, is an error incadl check; earlier releases dropped an unquoted entry without a diagnostic. An entry whose item begins with an identifier and continues with other text, such as the arguments in"A -> B : report(period: 5s)", is accepted with a warning and only the leading name is kept; this form is not part of this appendix. Fromcadl0.3.10 anautonomy:value other thanlow,medium, orhighis an error incadl check; earlier releases read it asmediumwithout a diagnostic. - Regimes. From
cadl0.3.32cadl checkapplies R-1 to R-7 of A.7.1, and the bindings are used where the tools read parameters and contracts:cadl sim-irwrites them (A.7.1) andcadl sim-genpasses them to thepythonandgoconfigurations (regimes) and to theunityconfiguration (regimeBindings).cadl verifychecks every pair of contracts that share a party. When no regime has both in force under the regime bindings of A.7.1, the pair is reported asinfowith the regimes of each, also when the two contradict each other: fromcadl0.3.33 every step of a run has the bindings of one regime (A.7.1, "Runs"), so the two are never in force at the same step. In 0.3.32, which left that step open, such a conflict was a warning (WARN). A pair that some regime has in force is judged as before, and a pair that the solver does not decide staysunknown. A file without regimes has every contract in force, so every pair is judged as before, even with an emptyregimes:block.cadl regime-mapshows, fromcadl0.3.33, the bindings of each regime in its text, DOT, and JSON outputs (JSON: the keyregimes, in the form of the IR,nullfor a block that breaks R-1 to R-6); its analysis reads only the transitions and is not changed by the bindings. The code generators apply the bindings fromcadl0.3.33 (Appendix D, D.1): thepythontarget starts the regime controller in the initial regime, rejects a name that is not a regime, checks the safety invariant of a transition explicitly and does not take the transition when it fails, gives the controller the methodsparameters(),contract_active(), andapply_bindings(), exposes the values of the current regime inctx.parameters, and runs the monitor of a contract only in the regimes in which it is in force (from 0.3.32); its norms monitor andcadl norms-evalread the current regime from the trace, which is in the initial regime until it names one (F.5, F.10). Thesoliditytarget makes one step one call of the orchestrator and checks the safety invariants in the same way; thesolidityandopatargets read the current regime for the contracts in force and the institutional parameters. Fromcadl0.3.36 the norms monitors of theopaandsoliditytargets (D.5), theunity-csharptarget, and the boundary policies of Appendix G (cadl agents-decide,agent-rego,agent-cedar) follow the current regime as well; in 0.3.33 to 0.3.35 they refused a contract that some regime does not have in force. Fromcadl0.3.36cadl agents-runand the gateways of Appendix G follow the current regime too: a trace line, or the host of a gateway, names it (G.13); in 0.3.33 to 0.3.35 they refused a file in which a regime does not have an enforced contract in force. Up to 0.3.32 the generatedunity-csharp,solidity, andopacode, the online monitor of the norms, andcadl regime-mapdid not use the bindings, the Python regime controller started in thefrom:of the first transition and checked the safety invariant withassert, and the SolidityRegimeControllerstarted in the first regime in alphabetical order, did not check the invariant, had no setters, and could be called by anyone. From 0.3.33 the rules of "Runs" (the initial regime, the explicit check, one step per call of the orchestrator) apply to every file with transitions. Thesafety_invariantof a transition is in the IR and the simulator configurations fromcadl0.3.32; up to 0.3.31cadl checkchecked it butcadl sim-irleft it out. - Verification.
method:,expr:, andbound:are read. Methods other thansmtare reported asnot_supported(shown as[SKIP]in text output), and an unknown method is an error. Atarget:that names nothing declared is an error for every method. For ansmtentry an unsatisfiableexpr:is an error, and anexpr:that does not conform to A.10 is reported asunknownand not checked;expris not proved against the model. The contract and transition checks of Section 6.3 run whether or not entries are present. - Codegen.
codegen:entries are parsed but not acted upon; the target is selected on the command line (Appendix D). Fromcadl0.3.9, an entry whosetarget:the implementation cannot emit (for exampletarget: ros2) gets a warning fromcadl check,cadl verify, andcadl codegen, which is the diagnostic that Appendix D, Section D.4 requires; the file remains valid. On the command line-t ros2is rejected. - Extensions.
lifecycle:andmonitors:are recognised whether or notextensions:declaressos-dsl. Fromcadl0.3.9,cadl checkemits an informational diagnostic, which never makes a file invalid, for anextensions:name other thansos-dsl, for a version ofsos-dslother than0.1, and for amotivation:block, as Appendix C asks of a processor that does not implement the extension. Themotivation:block is not interpreted, butcadl sim-irpasses it on as written under the keymotivation_block(Appendix C, Section C.6); the key is absent when the file has no such block. Wherecadlfalls short of Appendix E itself is stated in Section E.4. Fromcadl0.3.19 the declared extensionnormswith version0.1is implemented and gets no such diagnostic; whatcadlimplements of Appendix F is stated in Section F.10. Fromcadl0.3.20 the same holds foragents0.1 (Appendix G, G.13) andstochastic0.1 (Appendix H, H.14), andcadl sim-iremits the keystochastic_model, which isnullfor a file without that extension.cadl0.3.22 adds the certified regime maps of H.9, the runtime of G.5 to G.8 with the rules G-17 to G-19, and the online monitor of norms in the generated Python code; the three sections named above state what each covers. The extensionsgames0.1 (Appendix I, I.14) andgrounding0.1 (Appendix J, J.11) are implemented fromcadl0.3.23 (cadl game-check,cadl norms-indices); the two sections named state what each covers. Up to 0.3.22 their names got the informational diagnostic for an unknown extension; for a model withkind: smg,cadl check0.3.22 reports errors of S-1 and S-9 where H.10 and H.15 ask for one informational diagnostic, and it ignores the keys of Appendix J without a diagnostic. The extensionamendment0.1 (Appendix K, K.9) is implemented fromcadl0.3.32 (cadl amend-diff); up to 0.3.31 its name got the informational diagnostic for an unknown extension and its keys were ignored.
Releases of cadl before 0.3.7 differed in several of these points; the history
is in the
CHANGELOG
of the cadl repository.