input-output-hk / input-output-hk/Lean-blaster
[optimization] Symbolic list tails block append and drop reduction
- Dominant language
- Lean
- Stars
- 57
- Forks
- 11
- Avg merge
- 1d 5h
- Merged PRs (30d)
- 10
Description
The latest beta's list optimizer requires fully concrete list spines for append and drop. It leaves these elementary identities unresolved when the tail is symbolic:
```lean
import Tests.Utils
#testOptimize ["AppendSymbolicTail"]
(∀ xs : List Nat, [1, 2] ++ xs = 1 :: 2 :: xs) ===> True
#testOptimize ["DropSymbolicTail"]
(∀ xs : List Nat, (1 :: 2 :: xs).drop 2 = xs) ===> True
```
Both tests fail on beta `bafdd4f7` and on the review stack through #230; the corresponding identities have kernel proofs by `rfl`. This is an optimizer coverage gap, not a soundness failure. Existing #101 concerns `List.any`/`List.elem` and does not handle these cases.
Consume only the known constructor prefix, retain the unknown tail, and rebuild a residual append/drop only when needed. Dropping a small literal index should inspect at most that many constructors. Include empty-list identities, partial prefixes, zero indices, indices beyond the known prefix and falsified near-misses in `Issue.lean`.
Contributor guide
No contributing guide indexed for this repository
Research direction
Start with the list optimizer entry points that handle append and drop, then run the supplied #testOptimize cases after importing Tests.Utils. Add Issue.lean coverage for empty lists, partial prefixes, zero and oversized indices, residual symbolic tails, and falsified near-misses. Done means the stated identities optimize to True without rewriting unknown tails incorrectly.
Written by the indexing model from the issue text.
Assessment
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 70/100