import Tests.ReferenceExplorerimport Tests.Parsingimport Determinize.Checking.FiniteModelnamespace Determinize.Testsopen Frontend Checking Spec.Paper Spec.FiniteModel Determinize.Finiteprivate def duplicateLabels : Candidate := ⟨0, #[.eval (.real 3) [] [], .eval (.real 3) [] [], .deliver (.number 3) [], .deliver (.number 3) []], #[⟨.transient, #[⟨2, 1⟩]⟩, ⟨.transient, #[⟨3, 1⟩]⟩, ⟨.returned 3, #[⟨2, 1⟩]⟩, ⟨.returned 3, #[⟨3, 1⟩]⟩]⟩private def duplicateIndices (i : Fin duplicateLabels.states.size) (_ : Nat) : Nat := if i.val = 0 then 2 else 3private theorem duplicateReplay : duplicateLabels.IndexedReplayValid (.real 3) .source duplicateIndices := by decide +kernelexample : (duplicateLabels.graphModel (indexedReplay_valid _ _ _ _ duplicateReplay)).Matches (Subject.source.program (.real 3)) := Proof.FiniteModel.indexedReplay_matches _ _ duplicateReplayexample : ¬ duplicateLabels.IndexedReplayValid (.real 3) .source (fun _ _ ↦ 0) := by decide +kernelprivate def candidateFor (text : String) (subject : Subject := .source) : IO (Core × Candidate) := do let p ← IO.ofExcept (compile text) match ReferenceExplorer.explore p.source subject with | .complete candidate => return (p.source, candidate) | result => throw (IO.userError s!"expected complete graph: {reprStr result}")private def accepted (source : Core) (candidate : Candidate) (subject : Subject := .source) : Bool := (checkModel source subject candidate).isSomeprivate def indexedAccepted (source : Core) (candidate : Candidate) (subject : Subject := .source) : Bool := let indices := candidate.states.map fun state ↦ match step state with | .ok (.next _ outcomes) => (outcomes.map fun (outcome : Rat × State) ↦ (candidate.states.toList.findIdx? fun s ↦ decide (s = outcome.2)).getD 0).toArray | _ => #[] decide (candidate.IndexedReplayValid source subject (fun i k ↦ (indices[i.val]!)[k]!))private def setRow (candidate : Candidate) (i : Nat) (row : Row) : Candidate := {candidate with rows := candidate.rows.set! i row}def modelReplay : IO Unit := do for text in [ "0.1 + 0.2", "6/2", "if false then 1/0 else 7", "let x = 4 in (fun y => x + y) 3", "let f = rec f x => f x in f 0", "let f = rec f x => if flip(0.5) then 3 else f x in f 0", "discrete[G](0,0.25,0,0.75)", "discrete[E](*)", "let p = bernoulli[E](0.5) in discrete[E](p/2,0.25,*)", "let f = fun p => p :: 0.25 :: [] in discrete_list[E](f 0.25)", "bernoulli[G](0)", "bernoulli[G](1)", "let _ = observe(flip(0.5)) in 3", "match 2::[] with [] => 0 | x::xs => x", "let fact = rec f n => if n < 1 then 1 else n * f (n-1) in fact 4"] do let (source, candidate) ← candidateFor text check (accepted source candidate) s!"machine replay: {text}" check (indexedAccepted source candidate) s!"indexed machine replay: {text}" let divisionByZero : Candidate := ⟨0, #[ .eval (.div (.real 7) (.real 0)) [] [], .eval (.real 7) [] [.left .div (.real 0) []], .deliver (.number 7) [.left .div (.real 0) []], .eval (.real 0) [] [.right .div (.number 7)], .deliver (.number 0) [.right .div (.number 7)], .deliver (.number 0) []], (Array.range 5).map (fun i ↦ ⟨.transient, #[⟨i + 1, 1⟩]⟩) ++ #[⟨.returned 0, #[⟨5, 1⟩]⟩]⟩ check (!(accepted (.div (.real 7) (.real 0)) divisionByZero)) "certificate accepted a fabricated division-by-zero result" let (threeSource, three) ← candidateFor "3" let (sevenSource, seven) ← candidateFor "7" let some checkedThree := checkModel threeSource .source three | throw (IO.userError "expected checked model") let some checkedSeven := checkModel sevenSource .source seven | throw (IO.userError "expected checked model for seven") check (decide (∃ state, checkedThree.model.kind state = .returned 3)) "extracted reward three" check (decide (∃ state, checkedSeven.model.kind state = .returned 7)) "extracted reward seven" let (targetSource, target) ← candidateFor "uniform[E](0,3)" .determinized check (accepted targetSource target .determinized) "determinized mean replay" check (!(checkModelReplay targetSource .source target).isSome) "wrong subject" check (!(checkModelReplay (.real 7) .determinized target).isSome) "wrong source" let (coinSource, coin) ← candidateFor "bernoulli[G](0.25)" let some checkedCoin := checkModel coinSource .source coin | throw (IO.userError "expected checked coin model") check (checkedCoin.model.size == coin.states.size) "extracted model dimensions" let accepted := accepted coinSource let extra := coin.states.size let oneExtra : Candidate := { coin with states := coin.states.push .rejected rows := coin.rows.push ⟨.rejected, #[⟨extra, 1⟩]⟩ } check (accepted oneExtra) "unique unreachable state" let duplicate : Candidate := { oneExtra with states := oneExtra.states.push .rejected rows := oneExtra.rows.push ⟨.rejected, #[⟨extra + 1, 1⟩]⟩ } check (!accepted duplicate) "duplicate unreachable states" check (indexedAccepted coinSource duplicate) "duplicate state labels in indexed replay" for candidate in [coin, oneExtra, {coin with initial := 1}, {coin with rows := coin.rows.pop}, {coin with states := coin.states.pop, rows := coin.rows.pop}] do check (indexedAccepted coinSource candidate == accepted candidate) "indexed replay agrees with full replay" check (!indexedAccepted targetSource target .source) "indexed wrong subject" check (!indexedAccepted (.real 7) target .determinized) "indexed wrong source" let mut sampled := false let mut terminal := false for i in [:coin.rows.size] do let row := coin.rows[i]?.getD ⟨.rejected, #[]⟩ if row.edges.size == 2 then sampled := true let first := row.edges[0]?.getD ⟨0, 0⟩ let second := row.edges[1]?.getD ⟨0, 0⟩ for replacement in [ {row with edges := #[⟨first.target, 1⟩]}, {row with edges := #[⟨first.target, 1 / 2⟩, ⟨second.target, 1 / 2⟩]}, {row with edges := #[⟨first.target, first.probability⟩, ⟨first.target, second.probability⟩]}, {row with edges := #[⟨coin.states.size, 1⟩]}, {row with kind := .returned 99}] do check (!accepted (setRow coin i replacement)) "mutated sampled row" check (!indexedAccepted coinSource (setRow coin i replacement)) "indexed mutated sampled row" match row.kind with | .returned reward => terminal := true check (!accepted (setRow coin i {row with kind := .returned (reward + 1)})) "changed reward" check (!accepted (setRow coin i {row with edges := #[⟨0, 1⟩]})) "nonabsorbing terminal" check (!accepted (setRow coin i {row with kind := .rejected})) "changed outcome" | _ => pure () check (sampled && terminal) "mutation fixtures exercised" check (!accepted {coin with rows := coin.rows.pop}) "truncated rows" check (!accepted {coin with states := coin.states.pop, rows := coin.rows.pop}) "truncated graph" check (!accepted {coin with initial := coin.states.size}) "invalid initial index" check (!accepted {coin with initial := 1}) "wrong initial state" check (!accepted {coin with states := coin.states.set! 0 (.eval (.real 7) [] [])}) "changed initial expression" check (!accepted {coin with states := coin.states.set! 1 (.eval (.bvar 99) [] [])}) "malformed reachable state" let unusedFreeVariable : Core := .letE (.lam (.bvar 2)) (.real 3) match ReferenceExplorer.explore unusedFreeVariable .source with | .complete candidate => check (!(checkModel unusedFreeVariable .source candidate).isSome) "free variable in unused closure" | _ => throw (IO.userError "scope fixture must finish exploration") let broken : Candidate := ⟨0, #[.eval (.bvar 0) [] []], #[⟨.rejected, #[⟨0, 1⟩]⟩]⟩ check (!(checkModel (.bvar 0) .source broken).isSome) "stuck machine cannot be labeled rejected"#print axioms indexedStates_valid#print axioms indexedReplay_valid#print axioms Proof.FiniteModel.indexedReplay_matches#print axioms Proof.FiniteModel.replay_matches#print axioms checkModel#print axioms replay_reachable_covered#print axioms replay_reachable_no_failure#print axioms replay_successor_covered#print axioms replay_transition_weightend Determinize.Tests