import Determinize.Spec.Frontend/-!# Front-end syntax`Surface` is what the parser produces, with names and surface-only constructs; `elaborate`resolves it to an `Input`. The rest of the file lists the sites of a program and decides`Expr.Sitewise`, so that `Input.Matches` can be evaluated.-/namespace Determinize.Frontendopen Spec.Paperinductive Surface where | var (name : String) | number (value : Rat) | unit | nil | bool (value : Bool) | lam (name : String) (body : Surface) | fix (function argument : String) (body : Surface) | letE (name : String) (value body : Surface) | matchList (head tail : String) (scrutinee nilCase consCase : Surface) | matchSum (leftName rightName : String) (scrutinee left right : Surface) | ite (condition thenBranch elseBranch : Surface) | neg (body : Surface) | fst (body : Surface) | snd (body : Surface) | inl (body : Surface) | inr (body : Surface) | app (fn arg : Surface) | pair (left right : Surface) | cons (head tail : Surface) | add (left right : Surface) | sub (left right : Surface) | mul (left right : Surface) | div (left right : Surface) | lt (left right : Surface) | le (left right : Surface) | uniform (affinity : Option Affinity) (lower upper : Surface) | gaussian (affinity : Option Affinity) (mean variance : Surface) | poisson (affinity : Option Affinity) (rate : Surface) | exponential (affinity : Option Affinity) (rate : Surface) | bernoulli (affinity : Option Affinity) (probability : Surface) | beta (affinity : Option Affinity) (alpha betaArg : Surface) | gamma (affinity : Option Affinity) (shape rate : Surface) | discrete (affinity : Option Affinity) (weights : List Surface) | discreteRemainder (affinity : Option Affinity) (probabilities : Surface) | flip (affinity : Option Affinity) (probability : Surface) | observe (condition : Surface)deriving Reprend Determinize.Frontendnamespace Determinize.Spec.Paper.Expr/-- The sites of a program, in syntax order. -/def sites {Literal Site : Type} : Expr Literal Site → List Site | .bvar _ | .reject | .unit | .bool _ | .real _ | .nil => [] | .lam a | .fix a | .fst a | .snd a | .inl a | .inr a | .neg a => a.sites | .app a b | .pair a b | .cons a b | .letE a b | .add a b | .mul a b | .div a b | .lt a b => a.sites ++ b.sites | .matchSum a b c | .matchList a b c | .ite a b c => a.sites ++ b.sites ++ c.sites | .poisson s a | .discrete s a | .bernoulli s a | .exponential s a => s :: a.sites | .uniform s a b | .gaussian s a b | .beta s a b | .gamma s a b => s :: (a.sites ++ b.sites)/-- `Sitewise` for a Boolean relation between sites. -/def checkSitewise {Literal Site Site' : Type} [DecidableEq Literal] (r : Site → Site' → Bool) : Expr Literal Site → Expr Literal Site' → Bool | .bvar index, .bvar index' => index == index' | .bool value, .bool value' => value == value' | .real value, .real value' => decide (value = value') | .reject, .reject | .unit, .unit | .nil, .nil => true | .lam a, .lam a' | .fix a, .fix a' | .fst a, .fst a' | .snd a, .snd a' | .inl a, .inl a' | .inr a, .inr a' | .neg a, .neg a' => checkSitewise r a a' | .app a b, .app a' b' | .pair a b, .pair a' b' | .cons a b, .cons a' b' | .letE a b, .letE a' b' | .add a b, .add a' b' | .mul a b, .mul a' b' | .div a b, .div a' b' | .lt a b, .lt a' b' => checkSitewise r a a' && checkSitewise r b b' | .matchSum a b c, .matchSum a' b' c' | .matchList a b c, .matchList a' b' c' | .ite a b c, .ite a' b' c' => checkSitewise r a a' && checkSitewise r b b' && checkSitewise r c c' | .poisson s a, .poisson s' a' | .discrete s a, .discrete s' a' | .bernoulli s a, .bernoulli s' a' | .exponential s a, .exponential s' a' => r s s' && checkSitewise r a a' | .uniform s a b, .uniform s' a' b' | .gaussian s a b, .gaussian s' a' b' | .beta s a b, .beta s' a' b' | .gamma s a b, .gamma s' a' b' => r s s' && checkSitewise r a a' && checkSitewise r b b' | _, _ => falsetheorem checkSitewise_iff {Literal Site Site' : Type} [DecidableEq Literal] (R : Site → Site' → Prop) [∀ s s', Decidable (R s s')] (e : Expr Literal Site) (e' : Expr Literal Site') : checkSitewise (fun s s' ↦ decide (R s s')) e e' = true ↔ Sitewise R e e' := by induction e generalizing e' <;> cases e' <;> simp [checkSitewise, Sitewise, Bool.and_eq_true, and_assoc, *]instance {Literal Site Site' : Type} [DecidableEq Literal] (R : Site → Site' → Prop) [∀ s s', Decidable (R s s')] (e : Expr Literal Site) (e' : Expr Literal Site') : Decidable (Sitewise R e e') := decidable_of_iff _ (checkSitewise_iff R e e')end Determinize.Spec.Paper.Exprnamespace Determinize.Spec.Paperinstance (input : Input) (program : Annotated) : Decidable (input.Matches program) := inferInstanceAs (Decidable (Expr.Sitewise _ input program))end Determinize.Spec.Paper