muro-lang.dev / docs
Synthesis
mix muro.synth path.muro searches a version space of predicate programs against one checked environment. The search calls that book’s emitted step. A program that misses an observation is dropped. The smallest program that matches every observation is the policy the result book deploys, and eval runs it. A score breaks a tie between programs of equal size. It does not decide who survives. The checker sees that policy. When the environment defines the homomorphism the oracle asks for, the same book defines rank from the surviving predicate and the evidence for that ranking, and the checker sees the evidence on the same step. It does not see the search. Exit 0 is that checked book. A policy whose environment does not define the homomorphism is not exit 0.
mix muro.synth path.muro
mix muro.synth path.muro --on traces
mix muro.synth path.muro --oracle trace
mix muro.synth path.muro --oracle successor --depth 0
mix muro.synth path.muro --out out.muro --fuel 2000
muro synth path.muro
--on selects the procedure. traces is the version-space search on this page, and it is the only procedure. A book that defines step selects traces when --on is omitted. The observations are the ones step supports. A book with no step and no observations is refused, and the message does not name a flag. An unknown --on value is refused, and the message lists the accepted values. The candidates, their order, and the book are the ones this search already writes.
The predicate theory is CSHRL. examples/cshrl/envs/synth_bit.muro is the one-bit book: eval of truep is the deployed policy.
The environment
The book must already check. It defines State, Action, step, all-actions, horizon, and leb. step is the dynamics the search, the sweep, and the policy check all call. all-states, when the book defines it, is the cover, in the order written, and a state named twice is that state once, at its first occurrence. Otherwise the cover is the nullary constructors of State, closed under step. A State whose constructors take arguments is a term. When the book does not define all-states and that type has at most 32 inhabitants, the cover is the enumeration. More than 32 inhabitants is not that list. The book then declares all-states, or the environment is refused: State has more than 32 inhabitants; declare all-states. A constructor argument with no finite enumeration and no all-states is refused: State constructors take arguments; declare all-states. That refusal does not apply when a field of State is State. A back-edge under List or a product, with no all-states, is still that refusal. An inductive State may refer to itself. A finite non-empty all-states is then the cover, and two values are compared by matching constructors and recursing on a field of that same datatype. When the book does not define all-states, init is where the cover starts. init is run State, or run List State. The cover is the states reached from those states under step of every action in all-actions, in the order the walk meets them, and a state named twice is that state once, at its first occurrence. A cover of 256 states is accepted. A successor that would exceed 256 states refuses the environment: reachable states are not finite within 256; declare all-states. The states met before that successor are not a cover, and the book is not given a ranking of that prefix. A book that does not define init, and an init whose list is empty, are refused: a recursive State declares no initial state. A value init returns that is not a State is refused: init has a value that is not a State. A value step returns that is not a State is refused: step has a value that is not a State. A successor that is a State and is not in the set the walk closed is refused: step left the reachable cover. A declared all-states stays the cover, including when the book also defines init. init, when the book defines it, is a public run. A family of datatypes that refer to one another is refused: State is mutually inductive. Wrapper recursion is that same refusal: a Box that holds a State, and a State that holds a Box, is mutually inductive, even when only one constructor of State mentions Box.
data Box : Type where
box : Π (s : State) → Box
data State : Type where
wrap : Π (b : Box) → State
A recursive occurrence under List or a product is part of the value and is not that comparison. The certificate is refused: State recursion under List/product cannot be certified. A field of type List State is also not strictly positive, and the book is refused before the environment is opened. State has parameters and State has indices are refused from the declaration. A function field is refused: State has a function field. An erased constructor argument is refused: State has an erased constructor argument. A linear field opens, and the certificate is refused: State has a linear field. The certificate splits on every inhabitant of a finite State. When State is not that enumeration and the book defines a finite non-empty all-states, the same certificate ranges over the cover, provided step of every action in all-actions stays inside it and the terms can be split. The split follows the constructors, fields, lists, and Nats of those terms, and a field whose type is the datatype being split is that datatype again. A product that does not recurse to State is opened with let. A state outside the cover has an empty ranking, so the homomorphism does not order it. A cover that step leaves, and an empty all-states, leave the policy book without a ranking. The reachable cover of a State with a field of type State is ranked by that same certificate when the walk closes and the terms can be split.
A decoded Nat is a host integer, and spell is still the Peano term. step and eval-feature receive every Nat in the state as that integer, the value emitted Elixir matches on. leb compares the reward step returns. Covers in the earlier environment books use the numeral 0.
Features are ordinary definitions. There is no new keyword. The search builds tests from step, one per action: the reward is positive, the action returns to this state, and the successor is absorbing. A state is absorbing when every action stays there. A test that is true at every state on the cover, or false at every one, is dropped. A test with the same truth vector as an earlier test is dropped. data Feature, when the book declares it, names hints, and eval-feature reads one hint at a carrier. The two declarations come together or not at all. A book that defines neither is an environment. The version space is the two constants, the tests step supports, and the hints that remain. Carrier is that state type when the book defines it. A state name is not a feature by being a constructor of State. Depth does not add a template. When the survivor reads a discovered test, the policy book defines that test as a run over step. On a finite list of inhabitants the comparison is an exhaustive match. Otherwise it walks constructors, fields, lists, and Nats, and a field of the datatype being compared is a recursive call of that walk. is-self-loop and leads-terminal are omitted when that comparison is not a run. When the survivor reads no discovered test, and the environment declared no Feature, the policy book declares one constructor that is always false, under a name the environment does not already use.
The tests from step are has-pos-reward and is-self-loop (CSHRL.Synthesis.DynFeatureTemplate) and leads-terminal (CSHRL.Synthesis.AutoFeatureNat). When State has a field, the same pipeline reads the term: which constructor built it, whether two fields are equal, whether a field is a closed Nat, and, on a list or on the fields of one constructor, vals-eq, spread-eq, pair-any, and len-is (CSHRL.Synthesis.FeatureTemplate). A pair-any on one pair of positions drops the vals-eq and the spread-eq of that pair. The first pass opens one field. Resolving a name the path has already opened does not spend a step. The walk continues up to three fields. An atomic constructor is not walked, so those tests are not added there. A bare Nat is not a threshold on a state index. state-is, a factorization, and a one-hot state are not tests. The paper’s account is §Feature Discovery (sec:ftl). An empty version space is still searched one predicate depth further, as in CSHRL.Synthesis.CSHRLLoop. A missing test of a nested field is not that deepening. When two carriers agree on every test and the two values differ, the search enumerates paths up to three fields and searches again, and then adds tests at the subterm where they differ.
Two actions are one predicate: prefer the first action of all-actions, else the second. More than two actions are one predicate per action, chained in all-actions order, and the last else is default-action. An action named twice in all-actions is that action once, at its first occurrence. When default-action is omitted, the default is the last element of the list as written. The report follows that chain. The default is the preferred action only when every arm is false. A name that exists with the wrong mode, or the wrong type, is not an environment. step is Π (s : State) → Π (a : Action) → State × Reward, all-actions is List Action, horizon is Nat, and leb compares that reward. Those definitions, and all-states, default-action, and eval-feature when the book defines them, are public run terms. run internal is refused. An argument the search passes is not erased. A Carrier the book defines converts to State.
Oracles
--oracle selects the labels. The default is trace.
trace compares Finder traces out to horizon. Prefer the first action when the second action’s trace is below it, including when the two traces are equal. When the order compares neither of the first differing rewards with the other, the pair is not ranked. trace asks for CoindHomo.
successor compares successor values, pointwise, on a finite prefix, and asks for CoinductiveHomomorphism. It claims CoindHomo only when the immediate rewards respect the same ranking. coind-homo compares action values, pointwise, on the same kind of prefix, and asks for CoindHomo. A first reward that is smaller does not make the rest of the stream smaller. A pair the oracle cannot order stops the run, including a pair of actions that both lose to a third. A successor value or an action value is that same refusal when the rewards at a state have no maximum. The report names the carrier and the two actions. It does not invent a ranking.
The loop
--depth is the initial depth. Depth 0 is the constants and the feature tests. A negation, a conjunction, or a disjunction needs a greater depth. An empty version space is searched one depth further.
When the search started at depth 0 and a later depth was searched and was empty too, and every reward on the cover is a closed Nat, the search adds reaches-pos, one test per action. The test holds when the action’s reward is positive, or when some continuation within horizon pays a positive reward. A closed Nat is at least zero, so a positive continuation is strictly above the all-zero continuation. At horizon 0 the test is has-pos-reward, and the duplicate is dropped. A constant test is dropped. A run that stops at depth 0 does not add the test, because depth 1 was not searched. A survivor found at depth 0 or depth 1 is unchanged.
The search then enumerates by size, up to 18 constructors. A signature is the value of a predicate on the cover. One signature keeps the smallest program. The programs are the constants and the feature tests, their negations, a conjunction or a disjunction of two of those, the same with the right-hand test negated, and a left-associated conjunction or disjunction of feature tests. One further layer negates such a chain and joins it on the right of one test. A stem is an action-indexed test that survived: has-pos-reward, is-self-loop, leads-terminal, or reaches-pos. For each action that still has a column, the walk adds two atoms. selfp is that column. otherp is the disjunction of the same stem at every other action. An action whose test the cover filter dropped has no column, and that column is false. With one action, otherp is false. Each is one constructor, so the size does not grow with the number of actions. A family that lists an action with no column, or a column with no signature, refuses the walk. That action is not dropped. Negation and pairing treat them as atoms. A subset is still a subset of feature tests, because a quantifier is already one constructor for the whole action set. A book that uses either constructor defines Stem, stem-at, and other-at, and eval calls those runs. The book declares every column of each stem a survivor quantifies over, so stem-at at an action no survivor names reads its column. A column the plan did not declare refuses the book. The checker reduces that term. selfp and otherp are a muro extension of the PredProg grammar. The CSHRL paper’s grammar has feature tests, the constants, negation, conjunction, and disjunction. It has no action quantifier. A subset whose binomial coefficient is above 100000000 is not built, and the report says so. That budget admits a subset of nine features out of thirty-six, and a subset of eight out of forty. A wider subset is still skipped. The observations keep a program or drop it. The report names how many programs were considered, how many signatures were distinct, and how many new signatures each size added. The walk stops when the number of programs considered reaches 1000000. It also stops when a sample of the current growth, :erlang.memory(:total) minus the total at the start of the walk, is above 512 MiB. The sample is taken between candidates, before the next candidate is inserted. It is a soft bound on that current growth, not a hard cap on the peak: the candidate just inserted can take the total past the bound, and a later sample reads the total after collection, not the high-water mark. The report then names considered budget or memory budget, and it does not deploy a predicate. The report’s size is the last size that counted a program. The walk records that size only after the program is counted, so a budget that lands on the last program of a size names that size, and sizes has no row for the next size. When that size added a signature, it is the last row of sizes. A walk that stops before counting a program reports size 0 and an empty sizes. The same size is recorded when the search checks. It is how far enumeration went, not the size of the survivor. considered is the programs counted, distinct is the signatures, and truncated is whether a subset was skipped for the binomial budget.
The policy book defines a test it reads as a run over step and horizon. When the cover is finite and closed under step, and a match can split it, the book tabulates dyn-best-pos for every cover state and every horizon up to the environment’s. The table is a match. The checker does not trust the fill. Soundness inside the table is an inductive family of refls. dyn-best-pos at horizon 0 agrees with false. At the next horizon it agrees with one step of dyn-any, and that step reads the table at the smaller horizon. The chain ends at horizon 0. A wrong cell fails at the first horizon where it disagrees with that step. That cell is its own dyn-reach-holds evidence, and the refusal names the cell. Each cell is one top-level refl: one definition for every cover state and every horizon from 0 through the environment’s horizon, so a large closed cover checks on the order of the cover times the horizon. The evidence is not a chunked dyn-reach-agrees tree of comparisons with ≡ true. The table is not shown to be sound by one comparison with the recurrence unfolded out to the horizon. A horizon past the reachability table, and a state off the cover, fall back to the *-rec recurrence: dyn-known calls dyn-any-rec. That block is dyn-best-rec, dyn-one-rec, and dyn-any-rec, and it does not call the table. The search’s own memo of the recursion is not this table, and the checker never reads it. A cover that is not closed, that the match cannot split, or that has more than 100000 states, keeps the three recursive runs and emits no table. policy is eval of the predicate that remains.
The size of a program is the number of predicate constructors. A constant or a feature test is one. A negation is one plus its body. A conjunction or a disjunction is one plus both parts. selfp stem a is one. otherp stem a is one, and the columns of the other actions are not counted again. The feature’s name, the stem, and the action are not constructors. The smallest survivor is the program the book names survivor. policy is eval of that program:
def survivor : run PredProg := truep
def policy : run Π (+ s : State) → Action :=
λ (+ s : State) →
(match eval survivor s motive (λ _ → Action) | true => go | false => stay)
The equations hold-<state> are the observations the survivor matched. They are evidence. The emitters erase them. The policy does not case-split on the state names. rank reads eval of the survivor. It is Unit when the two actions are the same or the predicate prefers the second, and Empty otherwise. The preference is eval of the survivor, the same predicate the book deploys. On a finite State, solve s n is the best immediate reward among the states reached in n steps. Each component is one of a finite set of closed Nat rewards, so the vector of those values repeats. The book characterises solve at each state as a constant, or as a finite prefix and then a constant or a repeating tail. The evidence inducts on n. The homomorphism of the ranking rewrites those equations: CoindHomo for trace and coind-homo, and CoinductiveHomomorphism for successor. The evidence is a case split over the states and the actions. It is erased. On a finite enumeration the split has one arm per inhabitant. On a declared cover the arms are the terms of the cover, and a state outside it is an empty ranking. A state that pays nothing now is ranked when its stream is below the stream of a state it can reach. A successor ranking claims CoindHomo only when the immediate rewards respect the same order. A set of rewards with no maximum, or a reward that is not a closed Nat, leaves the policy book without a ranking.
examples/cshrl/envs/two_state.muro with trace checks CoindHomo. The survivor is truep, and at start it prefers go. Hiding go from the oracle does not check a CoindHomo for go. examples/cshrl/envs/binary_sacrifice.muro with successor checks CoinductiveHomomorphism for a survivor that prefers go-paradise, and the book does not claim CoindHomo. The same environment with coind-homo reports that the oracle cannot label the pair and writes nothing. trace on that environment separates start from the sinks and does not check CoindHomo: the homomorphism is not derivable at start. A book that contains only the policy is not exit 0. examples/cshrl/envs/maze_auto.muro declares no Feature. trace checks CoindHomo for (feat has-pos-reward-go), which prefers stay at west and go at east. examples/cshrl/envs/maze_auto_e2e.muro is the three-cell maze and declares no Feature. trace checks CoindHomo for truep, which prefers Fwd at P0, P1, and P2. solve P0 0 is 0 and solve P0 (suc n) is suc 0. solve P1 and solve P2 are suc 0 at every n. examples/cshrl/envs/placement.muro declares no Feature. The state is two rows. trace checks CoindHomo for (feat pair-any-0-1), which prefers move when the rows are equal or adjacent and stay when they are two apart. The tests from step do not separate those boards. examples/cshrl/envs/nested_bit.muro declares no Feature. The bit sits under two constructors. The first pass does not separate the two states. A test of that bit does, and trace checks CoindHomo for (feat ctor-is-p0-0-on), which prefers move at on and stay at off. examples/cshrl/envs/list_cover.muro declares no Feature. The state is a list of Nat. The cover is the empty list and the singleton 0. trace checks CoindHomo for (feat has-pos-reward-go), which prefers stay at the empty list and go at the singleton. examples/cshrl/envs/tree_cover.muro declares no Feature. The state is a binary tree of Nat. The cover is tip 0 and bin (tip 0) (tip 0). trace checks CoindHomo for (feat has-pos-reward-go), which prefers stay at the tip and go at the bin. examples/cshrl/envs/nested_bin.muro declares no Feature. The cover is bin (bin (tip 0) (tip 0)) (tip 0) and bin (bin (bin (tip 0) (tip 0)) (tip 0)) (tip 0). The first pass does not separate those trees. trace checks CoindHomo for (feat ctor-is-p0-0-bin-bin-bin), which prefers stay at the first and move at the second. examples/cshrl/envs/reachable_bin.muro declares no Feature and no all-states. init is the first of those trees, and step reaches the second. The cover has those two states. The first pass does not separate them. trace checks CoindHomo for (feat ctor-is-p0-0-bin-bin-bin), which prefers stay at the first and move at the second. examples/cshrl/envs/reachable_fork.muro declares no Feature and no all-states. init is bin (tip 0) (tip 0). move reaches bin (bin (tip 0) (tip 0)) (tip 0) and stay reaches bin (tip 0) (bin (tip 0) (tip 0)). The cover is those three trees. A walk of one action misses the other. trace checks CoindHomo for (feat ctor-is-p0-bin-bin), which prefers stay at the first, move at the second, and stay at the third. examples/cshrl/envs/tip_suc.muro declares no Feature. The state is a tip of Nat. The cover is tip 0 and tip (suc 0). step matches the Nat. trace checks CoindHomo for (feat has-pos-reward-go), which prefers stay at tip 0 and go at tip (suc 0).
PredProg and eval are compiled into the checker. They use the environment’s Bool, true, and false. The policy book does not import a second Bool or leb. An environment that already declares PredProg, eval, or the Boolean helpers, when those declarations have the types the policy uses, is left as written. A name the book already uses, including one that would spell the same Elixir function, is given a fresh name. A policy book can be read again as an environment.
The fuel bound and the round bound stop a search that is not shrinking. They are operational. They are not sufficient-cegis. A sweep of the cover is not that theorem.
When the features separate the observations and no predicate matches them, the report is an empty version space. It names the predicate depth that was searched, or the predicate size when reaches-pos was installed. A sized walk that stops because the considered budget or the memory budget is reached names that bound instead: considered budget or memory budget. The report names the templates and the path depth. The command exits 1 and writes no book.
Queens
examples/cshrl/envs/queens4.muro is four rows and declares no feature. ongoing carries the columns chosen so far. dead stays at reward 0. solved carries a finished board and stays at reward 100. An action appends its column. Two entries that share a column, or whose columns differ by the distance between their rows, go to dead. A safe board of length 4 is solved. The horizon is 4. The cover is the 17 safe boards and dead, 18 states, and step stays inside it.
The search is the ranking loop above. The deployed term is eval of the predicate the checker accepted. On this cover the constant-false tests are dropped, and vals-eq, spread-eq, and pair-any are false on every safe board and on every successor: an attack is dead, and the columns are gone. The templates that remain are has-pos-reward, is-self-loop, leads-terminal, ctor-is, and len-is. (ongoing (cons (suc 0) nil)) and (ongoing (cons (suc (suc 0)) nil)) differ on leads-terminal-c0 and leads-terminal-c3. No predicate at depth 0 or depth 1 matches the observations. Depth 0 has 16 programs and keeps none. Depth 1 has 1056 programs and keeps none. From (ongoing nil), c0 and c3 lead to safe boards whose every continuation pays 0, while c1 and c2 reach 100 inside the horizon. One step of step does not separate those actions.
The empty space installs reaches-pos and enumerates by size. 8138 programs are considered and 454 signatures are distinct. Size 4 is the first size that matches every action. One program is kept for each action. The survivor for c0 is (orp (feat has-pos-reward-c0) (notp (otherp reaches-pos c0))). The survivor for c1 is (orp (feat reaches-pos-c1) (notp (otherp reaches-pos c1))). The survivor for c2 is (orp (feat reaches-pos-c2) (notp (otherp reaches-pos c2))). The survivor for c3 is (orp (feat has-pos-reward-c0) (notp (otherp reaches-pos c3))). otherp at reaches-pos is the disjunction of that test at the other actions. The book checks CoindHomo. policy is eval of those four predicates, in all-actions order, else c0. It prefers c1 at (ongoing nil), c3 at (ongoing (cons (suc 0) nil)), and c0 at (ongoing (cons (suc (suc 0)) nil)) and at dead. The book does not define find-policy. Opening the book took 187 ms, the reachability table took 106 ms, and the enumeration took 448 ms. The certificate check took 9860 ms. The book is 167389 bytes. Peak resident set size on that run was 388349952 bytes. The ranking is a CoindHomo by the class lemma in examples/cshrl/lib/placement.muro. The 18-state agreement table stays in the book. The proof does not use the Finder.
On the bare lists of the safe boards, the structural templates number 23: 18 pairwise and 5 lengths. Eighteen stay false on every safe board. Reduction leaves the six pair-any tests, with the longer index outside: 0-1, 0-2, 1-2, 0-3, 1-3, 2-3. The length test that holds on every finished board and fails on every shorter open board is len-is-4. Those counts are a reading of the templates. They are not a predicate the checker accepted.
examples/cshrl/envs/queens8.muro is the same dynamics at eight rows. The horizon is 8. The cover is every safe board and dead, 2058 states, and it is closed. mix muro.check accepts the environment. The search installs 76 features: the dynamics tests, eight reaches-pos tests, and 40 closed Nats in the board. Enumeration by size starts from that set, with size bound 18. The subset budget admits a subset of five features here, because C(76, 6) is 218618940. A subset is still a subset of feature tests. otherp reads the other seven actions as one constructor, so an eight-wide disjunction is not the only way to name the other actions. The sized search keeps one size-4 program for each action, (orp (feat reaches-pos-cN) (notp (otherp reaches-pos cN))) for c0 through c7. policy is eval of those predicates, in all-actions order, else c0. The book checks CoindHomo. The certificate is the class lemma, not a split over the 2058 states, and a cover this large does not emit the per-state agreement table. The proof does not use the Finder. On the bare lists of the safe boards the structural templates number 93, 84 stay false on every safe board, and reduction leaves 28 pair-any tests. The length test that holds on every finished board and fails on every shorter open board is len-is-8. Opening the book took 232402 ms, the reachability table took 501114 ms, and the enumeration took 29139 ms. 71492 programs were considered and 20958 signatures are distinct. The certificate check took 7717 ms. The book is 244700 bytes. Peak resident set size on that run was 719929344 bytes. The whole run took 2114 seconds. nice mix muro.synth examples/cshrl/envs/queens8.muro repeats the search. It is not part of mix test.
The paper’s Demo 2 enumerates 23 templates for 4-queens, keeps 18 that stay false on every safe board, and reduces them to six pair-any tests, with len-is 4 as the solved test. Demo 6 does the same for 8-queens: 93 templates, 84 after that filter, 28 pair-any tests, and len-is 8. The solutions named there are [1, 3, 0, 2] and [0, 4, 7, 5, 2, 6, 1, 3]. The paper proves the class-level homomorphism for the Finder’s ranking, in CombinatorialPlacementMDP and WithTraceBridge. Muro proves that the synthesized predicate is optimal, in its own checker. The hypotheses are the placement ones: solve on dead is 0, solve on solved is the solved reward, that reward is above 0, and a board that is still 0 at the horizon stays 0 at every later depth. step is the class placement. Each survivor is discharged by a truth table on its reach atoms: the predicate holds only when that action reaches the solved reward, or no action does. The proof does not use the Finder, and it does not rank by trace order. A survivor outside that family still has the cover split. reaches-pos is the reach recurrence. It is not the Finder, and a trace that pays a smaller positive reward sooner is not the same order. selfp and otherp are not in the paper’s PredProg grammar. They are a muro extension, and the queens survivors use otherp. The pair index on the bare lists is walked with the longer index outside. The 8-queens synthesis is not part of mix test.
A failed check that produced a bit drops the candidate the checker refused and checks the next survivor. A failed homomorphism is that same refusal: the report names the carrier, the bit the survivor predicted, the bit the oracle required, the action pair, and how many times that carrier was fed back. That candidate is not selected again. When the refusal removes every survivor and a greater depth is still allowed, the search continues there, with the same observations. A policy book that does not check, and a check that names no obligation, drop that candidate and the search tries the next one. A check that names an obligation and produced no bit does not drop a candidate and does not deepen. The bit is the one in that obligation’s diagnostic. A later obligation does not supply it, and out of fuel stays unknown. After the round bound the report names the counterexample. It does not emit a ranking that failed to check.
When two carriers on the cover agree on every discovered test and every hint, and the oracle disagrees, no program in the version space can match both. If the two values differ as terms, the search enumerates paths up to three fields, filters again, and searches again. If they still agree, it adds tests at the subterm where they differ and searches again. Each invention round separates that pair, and the number of those rounds is at most the size of the cover. If the new tests still do not separate the pair, the report names the two carriers, the templates that were installed, and the path depth that was reached. The predicate depth is not raised in order to invent a template.
Paths into a term
A path starts at the root. The next step is a field of the constructor that built the value. A nested field is the same walk one step further. The bound is the number of fields opened. It is three. Resolving a name that the path has already opened does not spend a step. The walk continues up to that bound. The first pass opens one field. When two carriers agree on every test and the two values differ, a later pass enumerates every path again, up to that bound, and then stops. A single deepen can open several fields before search resumes. A difference past the bound, and a difference inside a list element, is still read at the subterm where the two values differ.
At each path the tests generalise the structural templates the paper states for List ℕ. The constructor tag is ctor-is. The name is the path, each constructor guard from the root, and the tag. A test with no guard keeps the path and the tag. On a list, vals-eq, spread-eq, pair-any, and len-is stay the tests of positions and length, at that list. A list element is not a field step. On a Nat at a path, nat-is is that closed value. A relevant field records its quantity and its binder name. The quantity is the telescope’s grade, the same at every value of that constructor, so a test of it would be constant or a duplicate of ctor-is, and it is not emitted. A use count is not a reading of the value: the binder name does not occur in the term. A test that is true at every state on the cover, or false at every one, is dropped. A test with the same truth vector as an earlier test is dropped. A pair-any on one pair of positions drops the vals-eq and the spread-eq of that pair. The tests are read from the schema of the environment that is open. A test does not name a fixture, a state, or one book.
examples/cshrl/envs/nested_bin.muro is the nested case. The two trees agree one field deep. ctor-is of bin two fields down separates them, and the book checks CoindHomo.
When the book declares a finite non-empty all-states and step of every action in all-actions stays inside it, the certificate ranks that cover. A state outside the cover has an empty ranking. That is the ranking already checked for an open structured state such as a list of Nat. A recursive term with such a cover uses that same certificate. When the book does not define all-states and a field of State is State, the cover is the states reached from init, and the same certificate ranks that cover. The walk that builds it is not a proof that every inhabitant was found. It is the closure of init under step. A cover of 256 states is accepted. A successor that would exceed 256 states is refused. The checker sees the cover the walk returned, and it sees the evidence for the surviving predicate. No prefix of a set that does not close is certified.
examples/cshrl/envs/reachable_bin.muro is that case. The two trees agree one field deep. ctor-is of bin two fields down separates them, and the book checks CoindHomo. examples/cshrl/envs/reachable_fork.muro is three trees. move and stay reach different states. ctor-is of bin one field down separates them, and the book checks CoindHomo for (feat ctor-is-p0-bin-bin).
The paper’s structural templates are specified for List ℕ, and indexed by positions in that list. A path into an inductive term is the index here. The paper filters for a feature that is false on every alive sample, and for one that is true on every solved sample and false on every other. The cover is one set, so a test that is true at every state, or false at every one, is dropped, and a duplicate truth vector is dropped. There is no alive/solved split. The paper’s quantity of a binder, and the number of times a variable is used, are not tests. The grade does not vary with the value, and a use count is not a general reading of an open schema. Accepting an inductive term as State, and comparing two values by recursion on a direct field, extends the paper’s account. A mutual family is refused, because a field is smaller only when its type is the datatype being matched. Wrapper recursion through another datatype is that refusal. A recursive occurrence under List or a product is stored and decoded, and it is not compared. The certificate is refused: State recursion under List/product cannot be certified. A let on the pair parses, and rank of the bound pair does not convert in the evidence. A field of type List State is not strictly positive. The comparison is not indexed by a fuel bound. Parameters, indices, a function field, and an erased constructor argument are refused when the environment is opened. A linear field is refused for the certificate and for the equality run. Two values also have no equality run when a field recurses under List or a product, or is linear or erased. A product that does not recurse is compared with let. The inhabitants of a recursive type are not listed. The cover is all-states when the book defines it. When a field of State is State and the book does not, the cover is the states reached from init. That closure is computed in Elixir. It is not an Agda theorem. The checker then accepts or refuses the certificate on the cover the walk returned. A bound of 256 states is operational. A cover of that many states is accepted. A successor that would exceed it is refused, and a larger finite set is not certified by a prefix; the book declares all-states. The paper’s finite set is the set the environment gives. A cover computed as the closure of init is not in that account. The certificate is the synthesized predicate, checked as CoindHomo or CoinductiveHomomorphism. It is not the Finder’s ranking. The quantity of a binder, and the number of times a variable is used, are still not tests. A closed suc inside a state is a host integer, and step receives the Peano term. An erased constructor argument is omitted from the value, and that datatype is not given an equality run. state-is, a factorization, and a one-hot state stay out. lam is not an environment. Nothing in the cover depends on a particular term language: init is one state, or a list of them, step is the book’s dynamics, and a path test reads whatever constructors the schema has.
Flags and exit codes
| Flag | Meaning |
|---|---|
--on NAME |
The procedure. traces is the version-space search on the book’s step and the observations that step supports. It is the only accepted value. A book that defines step selects traces when the flag is omitted. A book with no step and no observations is refused, and the message does not name a flag. An unknown value is refused, and the message lists the accepted values. |
--oracle NAME |
trace (the default), successor, or coind-homo. |
--depth N |
Initial predicate depth. Default 0. An empty space is searched one depth further. |
--out out.muro |
Write the policy book here. The path must not already exist. A path that is present when the book is written is the same refusal, and the file is not replaced. A write that fails removes the partial file. Without this flag the book is printed on standard output and nothing is written. That book’s environment import is relative to the current directory. |
--fuel N |
Fuel for the environment and for the policy book. Default Muro.Check.default_fuel/0 (2000). out of fuel is not acceptance. |
--json |
Print the report as one JSON object on standard error. The object records the version-space sizes and the counterexamples. A sized search records considered, distinct, truncated, sizes, and size whether the search checks or stops. considered is the number of programs counted. distinct is the number of signatures. truncated is whether a subset was skipped because its binomial coefficient passed the subset budget. sizes lists each size that added a signature, as the size and how many signatures it added. size is the last size that counted a program, or 0 when the walk stopped before any program. It is how far enumeration went, not the size of the survivor. When the search stops at the considered budget or the memory budget, the object also names that stop. It is not a certificate. |
| Exit | Meaning |
|---|---|
| 0 |
The output book checks and contains the homomorphism for the synthesized ranking, on the step the search called. trace and coind-homo check CoindHomo. successor checks CoinductiveHomomorphism. |
| 1 | The report names an empty version space, a counterexample, a homomorphism that is not derivable, an oracle that cannot label a pair, features that cannot separate two carriers, or a policy whose environment does not define the homomorphism. A book that typechecks and does not contain that evidence is this exit. |
| 2 |
The book does not check, it does not follow the environment convention, it has no step and no observations to synthesize against, --on is not an accepted value, the oracle name is unknown, --out already exists, or a policy book or a temporary book cannot be written. The diagnostic is the one the command returned. |
Source on GitHub
· fetched from murolang/muro manual/