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

[optimization] Symbolic list tails block append and drop reduction

Open
#233 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

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.