Compare commits

...

4 Commits

Author SHA1 Message Date
Leonardo de Moura
b71b2bdc92 chore: simplify
zetaDelta should be set by using a `post` visitor
2026-01-03 20:17:34 -08:00
Leonardo de Moura
260ad050cd chore: cleanup 2026-01-03 20:17:34 -08:00
Leonardo de Moura
6e73add87f chore: simplify Sym.simp 2026-01-03 20:17:34 -08:00
Leonardo de Moura
790ae76d33 feat: check Sym.simp thresholds
This PR ensures `Sym.simp` checks thresholds: maximum recursion depth
and maximum number of steps.

It also invokes `checkSystem`.
2026-01-03 20:17:34 -08:00
4 changed files with 11 additions and 16 deletions

View File

@@ -130,7 +130,7 @@ def getKey (e : Expr) : Key :=
| .lit v => .lit v
| .const declName _ => .const declName e.getAppNumArgs
| .fvar fvarId => .fvar fvarId e.getAppNumArgs
| .forallE _ _ _ _ => .arrow
| .forallE .. => .arrow
| _ => .other
/-- Push `e` arguments/children into the `todo` stack. -/

View File

@@ -25,20 +25,12 @@ def simpLet (_ : Expr) : SimpM Result := do
-- **TODO**
return .rfl
def simpFVar (_ : Expr) : SimpM Result := do
-- **TODO**
return .rfl
def simpMVar (_ : Expr) : SimpM Result := do
-- **TODO**
return .rfl
def simpApp (e : Expr) : SimpM Result := do
congrArgs e
def simpStep : Simproc := fun e => do
match e with
| .lit _ | .sort _ | .bvar _ | .const .. => return .rfl
| .lit _ | .sort _ | .bvar _ | .const .. | .fvar _ | .mvar _ => return .rfl
| .proj .. =>
reportIssue! "unexpected kernel projection term during simplification{indentExpr e}\npre-process and fold them as projection applications"
return .rfl
@@ -50,8 +42,6 @@ def simpStep : Simproc := fun e => do
| .lam .. => simpLambda e
| .forallE .. => simpForall e
| .letE .. => simpLet e
| .fvar .. => simpFVar e
| .mvar .. => simpMVar e
| .app .. => simpApp e
abbrev cacheResult (e : Expr) (r : Result) : SimpM Result := do
@@ -59,11 +49,16 @@ abbrev cacheResult (e : Expr) (r : Result) : SimpM Result := do
return r
@[export lean_sym_simp]
def simpImpl (e₁ : Expr) : SimpM Result := do
if ( get).numSteps >= ( getConfig).maxSteps then
def simpImpl (e₁ : Expr) : SimpM Result := withIncRecDepth do
let numSteps := ( get).numSteps
if numSteps >= ( getConfig).maxSteps then
throwError "`simp` failed: maximum number of steps exceeded"
if let some result := ( getCache).find? { expr := e₁ } then
return result
let numSteps := numSteps + 1
if numSteps % 1000 == 0 then
checkSystem "simp"
modify fun s => { s with numSteps }
match ( pre e₁) with
| .step e₂ h₁ => cacheResult e₁ ( mkEqTransResult e₁ e₂ h₁ ( simp e₂))
| .rfl =>

View File

@@ -100,8 +100,6 @@ invalidating the cache and causing O(2^n) behavior on conditional trees.
/-- Configuration options for the structural simplifier. -/
structure Config where
/-- If `true`, unfold let-bindings (zeta reduction) during simplification. -/
zetaDelta : Bool := true
/-- Maximum number of steps that can be performed by the simplifier. -/
maxSteps : Nat := 0
-- **TODO**: many are still missing

View File

@@ -101,6 +101,8 @@ def benchManyRewrites (n : Nat) : MetaM Unit := do
let proofSize getProofSize r
IO.println s!"many_rewrites_{n}: {timeMs}ms, proof_size={proofSize}"
set_option maxRecDepth 100000
/-! ## Run all benchmarks -/
def runAllBenchmarks : MetaM Unit := do
IO.println "=== Simplifier Stress Tests ==="