openlang

partial def: #eval выдаёт 111, а rfl и decide падают. Есть ли проверяемый путь без ofReduceBool?

У меня небольшой аудит-инструмент, toolchain leanprover/lean4:v4.15.0. Счётчик шагов — partial def, потому что доказательства завершения ни у кого нет:

partial def collatzSteps (n : Nat) (acc : Nat := 0) : Nat :=
  if n ≤ 1 then acc
  else if n % 2 == 0 then collatzSteps (n / 2) (acc + 1)
  else collatzSteps (3 * n + 1) (acc + 1)

def withinBudget (n : Nat) : Bool :=
  decide (collatzSteps n ≤ budget)

lake build проходит чисто, и #eval Audit.collatzSteps 27 выдаёт 111. Но в отдельном файле:

example : collatzSteps 6 = 8 := by rfl
theorem w27 : withinBudget 27 = true := by decide

Оба варианта отклоняются. В сообщении сказано, что терм не редуцируется до ожидаемого значения. Я подозревал аргумент по умолчанию и экземпляр Inhabited. Явное указание acc и добавление экземпляра ничего не изменили.

native_decide принимает оба, но тогда #print axioms показывает Lean.ofReduceBool, а это мне не подходит.

Два вопроса:

  1. Почему скомпилированный код может это вычислить, а ядро и decide — нет?
  2. Есть ли способ получить факт об этой функции, проверенный ядром, без её переписывания, например с fuel?
Переведено с английскогоПоказать оригинал

Разговор продолжается 2

Следуя доводам
  1. Ссылка на ответ

    У меня partial def компилируется в opaque-константу, так что ядру нечего разворачивать. Поэтому rfl и decide падают, хотя #eval запускает скомпилированный код. Кажется, в reference manual об этом что-то есть: https://lean-lang.org/doc/reference/latest/

    Может, написать версию с fuel, доказать факты про неё, а потом повесить @[extern], чтобы в скомпилированном коде использовалась быстрая? Вы это пробовали?

    Переведено с английскогоПоказать оригинал

Другие стороны того же вопроса

  1. -race сообщает DATA RACE, хотя ack — это приём из небуферизованного канала. Виноват time.After?

    Может ли быть, что race detector здесь ошибается, или я неправильно понимаю, что мне даёт ack? Это pushgate, небольшой сервис…

    Ответы 4Последняя активность go
  2. Несовпадение HMAC только на одном вебхуке (с акцентами в имени)

    Написал небольшой чекер на Node (чистый JS, без сборки): он переигрывает сохранённые доставки вебхуков и проверяет HMAC-SHA25…

    Ответы 7Последняя активность typescriptjavascript
  3. memset перед free проходит с флагами по умолчанию, падает с OPT=-O2

    Делаю небольшое хранилище учётных данных на C, называется vault, собираю в WSL. vault_release() должна затирать секрет и пото…

    Ответы 6Последняя активность c