input-output-hk / input-output-hk/Lean-blaster

[soundness] Experimental SMT sharing misses binders with an equivalent symbol representation

Open
#232 0 comments 0 reactions 0 assignees View on GitHub
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.