input-output-hk / input-output-hk/Lean-blaster
[soundness] Experimental SMT sharing misses binders with an equivalent symbol representation
- Dominant language
- Lean
- Stars
- 57
- Forks
- 11
- Avg merge
- 1d 5h
- Merged PRs (30d)
- 10
Description
While auditing the existing experimental `perf/sharing-blowup` implementation for reuse on beta (#231), I found a binder-scope bug in `SmtTerm.shareLets` at `de819c39`. This code is not yet on `beta-lambda-cache-optimization`.
Minimal regression:
```lean
import Blaster.Smt.ShareLet
open Blaster.Smt
private def y : SmtTerm := .SmtIdent (.SimpleIdent (.NormalSymbol "y"))
private def add (a b : SmtTerm) : SmtTerm :=
.AppTerm (.SimpleIdent (.ReservedSymbol "+")) #[a, b]
private def term : SmtTerm :=
.ForallTerm #[(.ReservedSymbol "y", .SymbolSort (.ReservedSymbol "Int"))]
(.AppTerm (.SimpleIdent (.ReservedSymbol "="))
#[add (add y y) (add y y), .NumTerm 0])
#guard toString (term.shareLets (minSize := 1)) == toString term
```
The check fails: the repeated `y` expression is lifted outside the `forall`, leaving an unbound identifier (or referring to an unrelated global with that name). `NormalSymbol "y"` and `ReservedSymbol "y"` both print as the same SMT identifier, but the taint set compares the Lean constructors, so the occurrence is not recognized as bound.
The binder and occurrence sets must compare the actual SMT identifier spelling, consistently with fresh-name collision checks. Keep the conservative rule that expressions mentioning any internally bound symbol cannot be lifted to the root. Cover both constructor orientations and forall/exists/lambda/let scopes before enabling sharing in beta.
Contributor guide
No contributing guide indexed for this repository
Research direction
Start at SmtTerm.shareLets in de819c39 and reproduce the provided #guard regression in Blaster.Smt.ShareLet. Trace how binder and occurrence sets identify symbols, then cover both constructor orientations and forall, exists, lambda, and let scopes; done means the repeated expression is not lifted across an internal binder and the regression passes before beta sharing is enabled.
Written by the indexing model from the issue text.
Assessment
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Clearly specified
- Newbie friendliness
- 55/100