Как устроено доказательство на Lean для программистов

Anatomy of a Lean proof for software engineers

Автор разбирает формальное доказательство на Lean для задачи из учебника Sipser: показать, что язык B, где нижняя строка битов равна сумме двух верхних, является регулярным. Вместо прямого построения DFA для B строится автомат для обратного языка B^R, читающий столбцы от младшего бита к старшему и запоминающий только перенос. Статья объясняет, как устроены спецификация, реализация и индуктивное доказательство в Lean, и почему это похоже на верификацию программ.

Хитрость в том, чтобы вспомнить, как вы складываете числа вручную: вы работаете от младшей значащей цифры к старшей. Единственное, что вы переносите из одного столбца в следующий, — это перенос.
  1. thom

    Всё это здорово, но, учитывая, что нас просят принять Lean-доказательства размером более 500 тысяч строк, которые проходят проверку, но в которых легко могут скрываться серьёзные семантические ошибки, какие у нас планы? Похоже, это уникально хрупкие программные артефакты, несмотря на отличные и надёжные обещания, данные средой исполнения.

  2. WalterGR

    Автор: в вашей статье отображается «[Contents]» там, где, предположительно, должно быть оглавление.

  3. fooker

    Пожалуйста, не пытайтесь понять Lean или системы доказательства теорем, предварительно не получив базового понимания задействованной логики. Эта статья в некотором роде пропускает это, что разумно, поскольку тема довольно сложная.

    Даже если вы написали большое количество математических доказательств, обычно вы не изучали язык или саму логику доказательств. И даже если вы опытный специалист по информатике, логика — это не просто AND, OR, NOT.

    Вот необходимое чтение, не стесняйтесь найти лучшие источники, но википедия тоже хороша.

    * Деревья доказательств — https://en.wikipedia.org/wiki/Method_of_analytic_tableaux

    * Конструктивная/интуиционистская логика — https://en.wikipedia.org/wiki/Intuitionistic_logic

    * Доказательства и типы — https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspon...

    * (Не)полнота — https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_...

    * Компактность — https://en.wikipedia.org/wiki/Compactness_theorem

  4. whattheheckheck

    интерфейс между спецификацией и доказательством не так ясен, так как часто приходится смотреть на доказательство, чтобы понять спецификацию. И если мы видим что-то странное в доказательстве, это хороший признак того, что что-то не так.

    Да, это как если я говорю, что что-то зелёное, откуда вы знаете, что мой зелёный — это ваш зелёный? Доказательство математически смоделированной системы никоим образом не привязано к символам, которые её реализуют, если только это не та же программа или вы не занимаетесь уточнением трассировки. И тогда нет способа доказать, что программа корректно выполняет бизнес-функцию, если только вы не запустите её. Весьма вычислительно несводимо, машина состояний для построения машин состояний.

  5. woggy

    Мне любопытно, могут ли люди использовать Lean в первую очередь как язык спецификаций программного обеспечения, не обязательно намереваясь доказывать всё.

    Можем ли мы использовать его для описания смысла и законов модулей, чтобы сделать дизайн точным и проверяемым, и чтобы это позволяло нам реализовывать тесты на основе свойств для этих законов в нашей реализации. Lean становится инструментом для более точного мышления о дизайне.

Ещё за этот день

2026-10-02