muro-lang.dev / docs

CSHRL

In brief: examples/cshrl/ is CSHRL in Muro. The artifact’s parameterised modules are files whose environment is a list of param entries. Each environment supplies them by declaring the names, and proves its theorems in the same file. Its run definitions are an agent that plans with the Finder and acts in the environment, emitted as an Elixir Stream.

Layout

File Artifact
lib/core.muro CSHRL.Core: solve, value, action-value, CoindHomo
lib/successor.muro SuccessorCore: CoinductiveHomomorphism, HeadCompatible, both directions
lib/successor_sum.muro SuccessorCoreWithArithmetic: partial-sum, SubsumesSuccessorReturn, SuccessorArgmaxSubsumed
lib/finder.muro EnvironmentClass.FiniteDeterministicMDP: best-trace, find-ranking, find-policy, ranks, preserves-head; the successor Finder
lib/agent.muro The agent: episode and successor-episode
envs/two_state.muro TwoState: CoindHomo ranks for the Finder’s ranking, policy go
envs/optimal.muro The return theorem: agent goes, and its reward stream dominates every other policy
envs/binary_sacrifice.muro BinarySacrifice
envs/skill_investment.muro SkillInvestment
lib/placement.muro A binary placement: hit copies the reach recurrence, and a reach-family ranking is a CoindHomo. It does not call the Finder
lib/synth.muro A predicate program: eval, propagation, vs-shrinks, sufficient-cegis
envs/synth_bit.muro Two carriers, one feature, one representative
envs/maze_auto.muro A corridor with no declared feature. trace checks CoindHomo for the reward of go
envs/maze_auto_e2e.muro The three-cell maze with no declared feature. trace checks CoindHomo for Fwd
envs/placement.muro Two rows on a board, no declared feature. trace checks CoindHomo for the comparison of the rows
envs/nested_bit.muro A bit under two constructors, no declared feature. trace checks CoindHomo for the constructor of that bit
envs/list_cover.muro Two lists of Nat, no declared feature. trace checks CoindHomo for the reward of go
envs/nested_bin.muro A constructor under a recursive child, no declared feature. trace checks CoindHomo for that constructor
envs/reachable_bin.muro The same two trees, with no all-states. init is the start. trace checks CoindHomo for that constructor
envs/reachable_fork.muro Three trees, with no all-states. move and stay reach different states. trace checks CoindHomo for (feat ctor-is-p0-bin-bin)
envs/queens4.muro Four rows, no declared feature. Depth 0 and 1 are empty. Size 4 enumerates a survivor. trace checks CoindHomo
envs/queens8.muro Eight rows, no declared feature. The sized search checks CoindHomo by the placement class lemma, outside mix test
envs/class_probe.muro Four queens supplying the placement hypotheses, so the class library checks
std/ Bool, Nat order and maxN, List, Stream with Dom

A library file does not check on its own: mix muro.check examples/cshrl/lib/core.muro refuses with param State is supplied by a file that imports this one. Check an environment instead:

mix muro.check examples/cshrl/envs/skill_investment.muro

The environment as params

core.muro opens with the artifact’s module parameters, in its order:

param State : spec Type
param Action : spec Type
param Reward : spec Type
param step : run Π (s : State) → Π (a : Action) → State × Reward
param le : spec Π (r : Reward) → Π (q : Reward) → Type
param max : run Π (r : Reward) → Π (q : Reward) → Reward
param bottom : run Reward
param all-actions : run List Action

The Finder adds leb, default-action and horizon. successor_sum.muro adds add, le-refl and add-mono as evidence, so partial-sum is a ghost: it appears in statements and is never emitted. An environment declares data State, def step, and the rest. Each declaration has the mode of its param (see Params).

Correspondence

  • Dom R le x y is _≤ₛ_, a declared ν family (Streams). A proof is an unfold of the head obligation and a proof at the tails.
  • CoindHomo rank is the artifact’s preserves field, for a given rank. The record bundles the ranking with that field. Here the ranking is the argument, so “the Finder’s ranking is a CoindHomo” is CoindHomo ranks.
  • action-value s a is the tabulation of action-at s a. The artifact defines its head and tail by copatterns. The tail here is value (next s a) up to dom-shift, which coindHomo-successor uses.
  • trace-action is written with fst and snd of step s a, so that ranks reduces to a cons and preserves-head is fst p, as in the artifact.
  • best-trace and trace-action are mutual. best-trace descends on k, and trace-action passes its k unchanged to best-trace, which is defined first (Terms).

The environments

TwoState. From start, go reaches goal, whose reward is 1. direct-preserves : CoindHomo ranks and test-start : find-policy start horizon ≡ go. Optimality of that policy is envs/optimal.muro, below.

BinarySacrifice. go-trap earns 1 now and 0 forever. go-paradise earns 0 now and 1 forever. sacrifice-homomorphism is a CoinductiveHomomorphism ranking go-paradise above go-trap. coindHomo-forward-impossible and coindHomo-reverse-impossible refute every CoindHomo that ranks them in either direction. paradise-subsumes is SuccessorArgmaxSubsumed at start: the successor return of go-paradise dominates at every horizon. finder-takes-trap and successor-finder-takes-paradise hold by refl.

SkillInvestment. train moves from novice to apprentice to expert to master and earns 0 each time. work earns 1, 2 or 3 and stays put. Master earns 5. value novice is 1, 2, 3, 5, 5, …. skill-homomorphism ranks train above work below master. Three impossibilities refute a CoindHomo ranking work at or below train at novice, apprentice and expert. The Finder works and the successor Finder trains.

Queens. Four rows, and no declared feature. The cover is the safe boards and dead. Depth 0 and depth 1 name no predicate. reaches-pos holds when an action pays a positive reward now or within the horizon. The search then enumerates by size. otherp is the disjunction of that test at the other actions, and it is one constructor. selfp and otherp are a muro extension, not in the paper’s grammar. The survivor for each action is size 4, and the book checks CoindHomo. policy is eval of that predicate. Eight rows is the same dynamics. The search reads 76 features and keeps one size-4 program per action, (orp (feat reaches-pos-cN) (notp (otherp reaches-pos cN))). The book checks CoindHomo by the class lemma in lib/placement.muro. The proof does not use the Finder. The paper proves that class-level homomorphism for the Finder’s ranking. Muro proves it for the synthesized predicate, from solve and step, in its own checker. envs/class_probe.muro supplies the four-queens hypotheses and checks the library. The eight-queens search took 2114 seconds and is not part of mix test.

The agents

episode-with policy s unfolds from s: at each state it asks the policy for an action, emits the action and its reward, and continues from the state it reaches. episode plans with find-policy x horizon and successor-episode with find-successor-policy x horizon. From the starting states:

Environment episode successor-episode
BinarySacrifice go_trap 1, then 0 forever go_paradise 0, then 1 forever
SkillInvestment work 1 forever train 0 three times, then 5 forever

In trap both actions return to trap. The Finder’s sort is stable, so the tie goes to go-paradise, emitted as go_paradise, the first action in all-actions.

The return theorem

envs/optimal.muro is one agent and one step. agent goes from either state. returns policy s is the stream of rewards from following policy at s.

def agent-optimal : evidence Π (+ policy : State → Action) → Π (+ s : State) →
    Dom Nat Le (returns policy s) (returns agent s)

+ is there because the policy and the state are read now and again at the successors. The proof is dominates, an unfold. The head is the reward now: go earns 1, and every reward this step pays is 0 or 1. The tail is dominates at both successors, the state policy reached and the state agent reached.

CoindHomo ranks is a property of a ranking of actions. find-policy start horizon ≡ go is the Finder’s choice at start. agent-optimal is the statement that this agent’s return dominates every other policy.

In BinarySacrifice the stream of go-trap is 1, 0, 0, … and the stream of go-paradise is 0, 1, 1, …. Each is strictly ahead at a position where the other is behind, so Dom holds in neither direction. No policy’s return dominates every other policy there.

Predicate programs

lib/synth.muro is the CEGIS theory for a Boolean program over features. The environment supplies the carrier, the features, and eval-feature. PredProg is a feature test (feat), a conjunction (andp), a disjunction (orp), a negation (notp), or a constant (truep, falsep). eval reads a carrier. propagation says a program agrees on feature-equivalent carriers. refine keeps the programs that match an observation, and vs-shrinks says the version space never grows. consistent-correct says a program that matches an observation is kept. cegis-survivors-consistent says every survivor of refine-all agrees with every observation it saw. refine-commutes and replay-redundant say the order of observations does not matter, and repeating one that was already seen changes nothing.

sufficient-cegis is the claim that makes a finite cover enough. If FeatureRespects target and Covers reps, every survivor of refinement on the representative observations (r, target r) matches the target on every carrier. Those lemmas are evidence about the run policy, and the emitters erase them.

envs/synth_bit.muro is that claim on two carriers. Both make the one feature true, so on represents off, and the target is constantly true. One observation is enough. bit-policy is the run eval truep. It is the deployed policy, and bit-policy-matches is sufficient-cegis at that exact run: the policy matches the target on both carriers.

mix muro.synth runs that search on a checked environment and calls the environment’s emitted step. The smallest program that matches every observation is the policy the result book deploys, and eval runs it. A score does not decide who survives. When the environment defines the homomorphism, the same book checks that evidence on this step. The page is Synthesis.

mix muro.check examples/cshrl/envs/synth_bit.muro

What is proved

agent-optimal and the ranking theorems above are what mix muro.check accepts. Dom is a declared ν family, and that shape is in ⊢ (Limits): the unfold is a derivation of the pair instantiated at the seed, and uncons of that pair is the head and the proof at the tails. Unfolding the definition opens it onto the family λ, and uncons of the pair instantiated at the seed is a derivation at the family goal (fam-def-uncons, Limits). The guard on the recursive call is the checker’s shape, argued there. The descent of the mutual blocks in finder.muro is the checker’s measure, argued, not an Agda theorem. The library has none of the artifact’s appendices or stochastic environment classes.

Source on GitHub · fetched from murolang/muro manual/