leanprover / leanprover/lean4

The compiler tries to generate code for `let rec`s inside a proof

Open
#7,878 5 comments 7 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

bug P-low
Dominant language
Lean
Stars
9.2k
Forks
990
Avg merge
1d 17h
Merged PRs (30d)
175

Description

Prerequisites

Please put an X between the brackets as you perform the following steps:

Description

Declaring a non-computable function within a proof with let rec ends up with an error that the function should be marked noncomputable, but:

  1. There is no place to mark a let rec as noncomputable.
  2. There is no point making a let rec computable anyway, since we're inside a proof.
Context

This came up in APAP when doing a measure theoretic argument requiring to define a simple function recursively.

Steps to Reproduce
noncomputable def foo (n : Nat) : Nat := n

-- Uncomment the next line to fix
-- noncomputable section

example : True := by
  -- Always works fine
  let bar : Nat → Nat := foo
  -- Works iff `noncomputable section` is uncommented
  let rec baz : Nat → Nat
  | 0 => 0
  | n + 1 => foo n + 1
  /-
  failed to compile definition, compiler IR check failed at '_example.baz'. Error: depends on declaration 'foo', which has no executable code; consider marking definition as 'noncomputable'
  -/
  trivial

Expected behavior: The let rec works

Actual behavior: The let rec doesn't work

Additional information

If a variant of #2719 were implemented for noncomputable, then we could work around this issue by using noncomputable let rec instead of let rec.

Versions

Lean 4.18.0
Target: x86_64-unknown-linux-gnu

Impact

Add 👍 to issues you consider important. If others are impacted by this issue, please ask them to add 👍 to it.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with the minimal reproducer in the issue and inspect the compiler path that emits _example.baz and performs the compiler IR check. Confirm the behavior for a recursive let inside a proof, then verify that the example compiles without requiring a noncomputable section.

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
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.