Карри-Говард для синтеза терминов в Изабель

Скажем, я доказал некоторые основные положения интуиционистской логики высказываний в Изабель /HOL:

theorem ‹(A ⟶ B) ⟶ ((B ⟶ C) ⟶ (A ⟶ C))›
proof -
  {
    assume ‹A ⟶ B›
    {
      assume ‹B ⟶ C›
      {
        assume ‹A›
        with ‹A ⟶ B› have ‹B› by (rule mp)
        with ‹B ⟶ C› have ‹C› by (rule mp)
      }
      hence ‹A ⟶ C› by (rule impI)
    }
    hence ‹(B ⟶ C) ⟶ (A ⟶ C)› by (rule impI)
  }
  thus ?thesis by (rule impI)
qed

Я знаю из соответствия Карри-Говарда, что предложение соответствует некоторому типу (a -> b) -> ((b -> c) -> (a -> c))и доказательство некоторому члену, все внутри некоторой теории типов (скажем, в λ-исчислении с простым типом). Из структуры доказательства я знаю, что соответствующий типизированный λ-член λf:a→b. λg:b→c. λx:a. f(g(x)),

Есть ли способ заставить Изабель построить это для меня?

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

Я также знаю, что HOL - это не то же самое, что теория зависимых типов, которая, как я понимаю, имеет более сильный вкус Карри-Ховарда. Я знаю, что сам HOL концептуально в некотором роде похож на полиморфное λ-исчисление, и я нашел несколько кратких заметок о том, как HOL является поверхностным кодированием логики в теории типов, но будет весьма полезен некоторый дополнительный контекст. Я едва смог собрать воедино, как все эти разные помощники по доказательству и связанные с ними основы связаны друг с другом, и, возможно, какой-то более исторический контекст тоже поможет. К сожалению, документация вокруг Изабель, Кок и т. Д. Кажется немного повсеместной; в частности, для Изабель, я, кажется, регулярно нахожу информацию, которая устарела на 20 лет.

0 ответов

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