The tactic to prove the `step_pos` field in `Std.range` should be stronger than `decide`
Open
Nobody has claimed this yet.
bug
P-medium
- Dominant language
- Lean
- Stars
- 9.2k
- Forks
- 990
- Avg merge
- 1d 17h
- Merged PRs (30d)
- 175
Description
Description
Currently, using the syntax for Std.range, the step_pos field is always filled with decide tactic.
syntax:max "[" withoutPosition(":" term) "]" : term
syntax:max "[" withoutPosition(term ":" term) "]" : term
syntax:max "[" withoutPosition(":" term ":" term) "]" : term
syntax:max "[" withoutPosition(term ":" term ":" term) "]" : term
macro_rules
| `([ : $stop]) => `({ stop := $stop, step_pos := Nat.zero_lt_one : Range })
| `([ $start : $stop ]) => `({ start := $start, stop := $stop, step_pos := Nat.zero_lt_one : Range })
| `([ $start : $stop : $step ]) => `({ start := $start, stop := $stop, step := $step, step_pos := by decide : Range })
| `([ : $stop : $step ]) => `({ stop := $stop, step := $step, step_pos := by decide : Range })
Therefore, step_pos cannot be proved in the following cases
def eratosthenesAux (n : Nat) : Array Bool := Id.run do
let mut isPrime := Array.replicate (n + 1) true
isPrime := isPrime.set! 0 false
isPrime := isPrime.set! 1 false
for p in [2 : n + 1] do
if not isPrime[p]! then
continue
if p ^ 2 > n then
break
/- expected type must not contain free variables
0 < p
Use the '+revert' option to automatically cleanup and revert free variables.Lean 4
p : Nat -/
for q in [p * p : n : p] do
isPrime := isPrime.set! q false
return isPrime
Versions
v4.19.0-rc2
Additional Information
see Zulip: #lean4 > why Std.range has field step_pos?
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start by locating the Std.range syntax and its macro_rules, then reproduce the eratosthenesAux example from the issue. Investigate how the step_pos proof is generated for ranges with variable steps; done means the shown nested range can elaborate without the free-variable error while preserving the existing range syntax.
Written by the indexing model from the issue text.
Assessment
- Domain
- compilers
- Issue type
- Feature
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 38/100