08eb78a5b2
This PR sets up the new integrated test/bench suite. It then migrates all benchmarks and some related tests to the new suite. There's also some documentation and some linting. For now, a lot of the old tests are left alone so this PR doesn't become even larger than it already is. Eventually, all tests should be migrated to the new suite though so there isn't a confusing mix of two systems.
80 lines
2 KiB
Text
80 lines
2 KiB
Text
inductive BinOp where
|
|
| plus
|
|
| times
|
|
|
|
inductive Expr where
|
|
| const : Nat → Expr
|
|
| binOp : BinOp → Expr → Expr → Expr
|
|
|
|
def BinOp.denote (op : BinOp) : Nat → Nat → Nat :=
|
|
match op with
|
|
| plus => Nat.add
|
|
| times => Nat.mul
|
|
|
|
def Expr.denote (e : Expr) : Nat :=
|
|
match e with
|
|
| const v => v
|
|
| binOp op a b => op.denote a.denote b.denote
|
|
|
|
/-- info: 42 -/
|
|
#guard_msgs in
|
|
#eval Expr.denote (Expr.const 42)
|
|
|
|
/-- info: 42 -/
|
|
#guard_msgs in
|
|
#eval Expr.denote (.const 42)
|
|
|
|
/-- info: 42 -/
|
|
#guard_msgs in
|
|
#eval Expr.denote <| .const 42
|
|
|
|
/-- info: 5 -/
|
|
#guard_msgs in
|
|
#eval Expr.denote <| .binOp .plus (.const 2) (.const 3)
|
|
|
|
/-- info: 6 -/
|
|
#guard_msgs in
|
|
#eval Expr.denote <| .binOp .times (.const 2) (.const 3)
|
|
|
|
#eval (.binOp .times (.binOp .plus (.const 4) (.const 2)) (.const 3) : Expr).denote
|
|
|
|
def e₁ : Expr := .binOp .times (.binOp .plus (.const 4) (.const 2)) (.const 3)
|
|
|
|
example : e₁.denote = 18 :=
|
|
rfl
|
|
|
|
inductive Instr where
|
|
| const : Nat → Instr
|
|
| binOp : BinOp → Instr
|
|
|
|
abbrev Prog := List Instr
|
|
abbrev Stack := List Nat
|
|
|
|
def Instr.denote (i : Instr) (s : Stack) : Option Stack :=
|
|
match i, s with
|
|
| const v, s => some (v :: s)
|
|
| binOp op, a::b::s' => some (op.denote a b :: s')
|
|
| _, _ => none
|
|
|
|
def Prog.denote (p : Prog) (s : Stack) : Option Stack :=
|
|
match p with
|
|
| [] => some s
|
|
| i :: (p' : Prog) =>
|
|
match i.denote s with
|
|
| none => none
|
|
| some s' => p'.denote s'
|
|
|
|
def Expr.compile (e : Expr) : Prog :=
|
|
match e with
|
|
| const v => [.const v]
|
|
| binOp op a b => b.compile ++ a.compile ++ [.binOp op]
|
|
|
|
theorem compile_correct' (e : Expr) (p : Prog) (s : Stack) : (e.compile ++ p : Prog).denote s = p.denote (e.denote :: s) := by
|
|
induction e generalizing p s with
|
|
| const => rfl
|
|
| binOp => simp [Expr.compile, Expr.denote, Prog.denote, Instr.denote, List.append_assoc, *]
|
|
|
|
theorem compile_correct (e : Expr) : e.compile.denote [] = some [e.denote] := by
|
|
have := compile_correct' e [] []
|
|
simp [Prog.denote] at this
|
|
assumption
|