Что такое хороший способ определить конечную таблицу умножения в Isar?
Предположим, у меня есть бинарный оператор f :: "sT => sT => sT", Я хочу определить f так что он реализует таблицу умножения 4x4 для группы Кляйна четыре, показанную здесь, на вики:
http://en.wikipedia.org/wiki/Klein_four-group
Здесь все, что я пытаюсь сделать, это создать таблицу с 16 записями. Сначала я определяю четыре константы следующим образом:
consts
k_1::sT
k_a::sT
k_b::sT
k_ab::sT
Затем я определяю свою функцию для реализации 16 записей в таблице:
k_1 * k_1 = k_1
k_1 * k_a = k_a
...
k_ab * k_ab = k_1
Я не знаю, как делать нормальное программирование на Изаре, и я видел в списке пользователей Изабель, где было сказано, что (определенные) программирующие конструкции намеренно преуменьшены в языке.
На днях я пытался создать простую придуманную функцию и, найдя применение if, then, else в исходном файле я не смог найти ссылку на эти команды в isar-ref.pdf.
Глядя на учебники, я вижу definition для определения функций простым способом, и кроме этого, я вижу только информацию о рекурсивных и индуктивных функциях, которые требуют datatypeи моя ситуация более проста, чем это.
Если бы я оставил свои устройства, я бы попытался определить datatype для этих 4 констант, показанных выше, а затем создайте некоторые функции преобразования, чтобы я в конечном итоге с двоичным оператором f :: sT => sT => sT, Я немного повозился с попыткой использовать fun, но это не оказалось простой сделкой.
Я немного поэкспериментировал с fun а также inductive
ОБНОВЛЕНИЕ: я добавляю некоторый материал здесь в ответ на комментарий, говорящий мне, что Программирование и Доказательство - то, где я найду ответы. Кажется, я заблудился от идеального формата Stackru.
Я провел некоторые базовые эксперименты, в основном с fun, но также с inductive, Я отказался от индуктивного довольно быстро. Вот тип ошибки, которую я получил из простых примеров:
consts
k1::sT
inductive k4gI :: "sT => sT => sT" where
"k4gI k1 k1 = k1"
--"OUTPUT ERROR:"
--{*Proofs for inductive predicate(s) "k4gI"
Ill-formed introduction rule ""
((k4gI k1 k1) = k1)
Conclusion of introduction rule must be an inductive predicate
*}
Моя таблица умножения не индуктивная, поэтому я этого не видел inductive было то, что я должен тратить свое время в погоне.
"Сопоставление с образцом" кажется ключевой идеей, поэтому я экспериментировал с fun, Вот некоторый действительно испорченный код, пытающийся использовать fun только со стандартным типом функции:
consts
k1::sT
fun k4gF :: "sT => sT => sT" where
"k4gF k1 k1 = k1"
--"OUTPUT ERROR:"
--"Malformed definition:
Non-constructor pattern not allowed in sequential mode.
((k4gF k1 k1) = k1)"
Я получил такую ошибку, и я прочитал что-то вроде этого в Программирование и доказательство:
Msgstr "Рекурсивные функции определяются весело с помощью сопоставления с образцом по конструкторам типов данных.
Это все создает у новичка впечатление, что fun требует datatype, Как далеко его старший брат functionЯ не знаю об этом.
Кажется, здесь все, что мне нужно, это рекурсивная функция с 16 базовыми случаями, и это определило бы мою таблицу умножения.
Является function ответ?
При редактировании этого вопроса я вспомнил function из прошлого, и вот function на работе:
consts
k1::sT
function k4gF :: "sT => sT => sT" where
"k4gF k1 k1 = k1"
try
Результат try говорит мне, что это может быть доказано (Обновление: я думаю, что на самом деле оно говорит мне, что только 1 из шагов доказательства может быть доказан.):
Trying "solve_direct", "quickcheck", "try0", "sledgehammer", and "nitpick"...
Timestamp: 00:47:27.
solve_direct: (((k1, k1) = (k1, k1)) ⟹ (k1 = k1)) can be solved directly with
HOL.arg_cong: ((?x = ?y) ⟹ ((?f ?x) = (?f ?y))) [name "HOL.arg_cong", kind "lemma"]
HOL.refl: (?t = ?t) [name "HOL.refl"]
MFZ.HOL⇣'eq⇣'is⇣'reflexive: (?r = ?r) [name "MFZ.HOL⇣'eq⇣'is⇣'reflexive", kind "theorem"]
MFZ.HOL_eq_is_reflexive: (?r = ?r) [name "MFZ.HOL_eq_is_reflexive", kind "lemma"]
Product_Type.Pair_inject:
(⟦((?a, ?b) = (?a', ?b')); (⟦(?a = ?a'); (?b = ?b')⟧ ⟹ ?R)⟧ ⟹ ?R)
[name "Product_Type.Pair_inject", kind "lemma"]
Я не знаю, что это значит. Я знаю только о function из-за попытки доказать несостоятельность. Я только знаю, что это не так сильно жаловаться. При использовании function вот так я определяю свою таблицу умножения, тогда я счастлив.
Тем не менее, будучи аргументным типом, я не узнал о function в учебнике. Я узнал об этом несколько месяцев назад в справочном руководстве и до сих пор не знаю, как им пользоваться.
у меня есть function который я доказываю autoК счастью, функция, вероятно, не очень хорошая. Это добавляет к functionТайна Там есть информация о function в определении рекурсивных функций в Изабель /HOL и сравнивает fun а также function,
Тем не менее, я не видел ни одного примера fun или же function который не использует рекурсивный тип данных, такой как nat или же 'a list, Может быть, я выглядел недостаточно усердно.
Извините за то, что я многословен, и это не закончилось как прямой вопрос, но нет никакого учебного пособия с Изабель, которое переносит человека непосредственно от А до Б.
2 ответа
Более или менее удобный синтаксис для определения "конечной" функции - это синтаксис обновления функции: для функции f, f(x := y) представляет функцию %z. if z = x then y else f z, Если вы хотите обновить более одного значения, разделите их запятыми: f(x1 := y1, x2 := y2),
Так, например, функция, которая является дополнением для 0, 1 и undefined иначе может быть записано как:
undefined (0 := undefined(0 := 0, 1 := 1),
1 := undefined(0 := 1, 1 := 2))
Другая возможность определить конечную функцию - сгенерировать ее из списка пар; например с map_of, С f xs y z = the (map_of xs (y,z))тогда указанная выше функция может быть записана как
f [((0,0),0), ((0,1),1), ((1,0),1), ((1,1),1)]
(На самом деле, это не совсем та же функция, так как она может вести себя по-разному за пределами определенного домена).
Ниже я не придерживаюсь формата "только ответь на вопрос", но я отвечаю на свой вопрос, и поэтому все, что я скажу, будет интересно оригинальному постеру.
(2-е обновление начинается)
Это должно быть моим последним обновлением. Чтобы быть довольным "несложными методами", это помогает уметь сравнивать, чтобы увидеть, что "низкотехнологичный" способ может быть лучшим.
Я, наконец, прекратил попытки заставить мой основной тип работать с новым типом, и я просто сделал меня из четырех групп Кляйна из datatype вот так, где доказательство ассоциативности находится в конце:
datatype AT4k = e4kt | a4kt | b4kt | c4kt
fun AOP4k :: "AT4k => AT4k => AT4k" where
"AOP4k e4kt y = y"
| "AOP4k x e4kt = x"
| "AOP4k a4kt a4kt = e4kt"
| "AOP4k a4kt b4kt = c4kt"
| "AOP4k a4kt c4kt = b4kt"
| "AOP4k b4kt a4kt = c4kt"
| "AOP4k b4kt b4kt = e4kt"
| "AOP4k b4kt c4kt = a4kt"
| "AOP4k c4kt a4kt = b4kt"
| "AOP4k c4kt b4kt = a4kt"
| "AOP4k c4kt c4kt = e4kt"
notation
AOP4k ("AOP4k") and
AOP4k (infixl "*" 70)
theorem k4o_assoc2:
"(x * y) * z = x * (y * z)"
by(smt AOP4k.simps(1) AOP4k.simps(10) AOP4k.simps(11) AOP4k.simps(12)
AOP4k.simps(13) AOP4k.simps(2) AOP4k.simps(3) AOP4k.simps(4) AOP4k.simps(5)
AOP4k.simps(6) AOP4k.simps(7) AOP4k.simps(8) AOP4k.simps(9) AT4k.exhaust)
Следствием этого является то, что я теперь доволен своим if-then-else функция умножения. Зачем? Поскольку if-then-else функция очень способствует simp магия. Это сопоставление с образцом само по себе не приносит никакой магии, не говоря уже о том, что мне все равно придется выработать часть принудительного подтипирования.
Вот if-then-else функция для таблицы умножения 4x4:
definition AO4k :: "sT => sT => sT" where
"AO4k x y =
(if x = e4k then y else
(if y = e4k then x else
(if x = y then e4k else
(if x = a4k y = c4k then b4k else
(if x = b4k y = c4k then a4k else
(if x = c4k y = a4k then b4k else
(if x = c4k y = b4k then a4k else
c4k)))))))"
Из-за одного вложенного if-then-else Скажите, когда я бегу auto, он производит 64 гола. Я сделал 16 simp правила, по одному на каждое значение в таблице умножения, поэтому, когда я запускаю авто, со всеми остальными simp правила, auto Доказательство занимает около 90 мс.
Низкие технологии - это путь иногда; это что-то вроде RISC против CISC.
Небольшая вещь, такая как таблица умножения, может быть важна для тестирования, но она не может быть полезной, если она замедлит мой THY, потому что она находится в каком-то большом цикле, который завершается вечно.
(Конец второго обновления)
(Начало обновления)
(ОБНОВЛЕНИЕ: мой вопрос выше относится к категории "Как мне выполнить базовое программирование на Изабель, как и с другими языками программирования?". Здесь я перехожу к некоторым конкретным вопросам, но стараюсь оставить свои комментарии о вызове для новичка. кто пытается изучать Изабель, когда документы находятся на среднем уровне, по крайней мере, по моему мнению, они есть.
Тем не менее, мой вопрос заключается в том, что мне нужно case утверждение, которое является очень основной особенностью многих, многих языков программирования.
В поисках case В сегодняшнем заявлении я подумала, что попала в золото после еще одного поиска в документах, на этот раз в Изабель - помощнике по проверке логики высшего порядка.
На странице 5 это документирует case заявление, но на странице 18 разъясняется, что это хорошо только для datatype и я, кажется, подтверждаю это ошибкой, подобной этой:
definition k4oC :: "kT => kT => kT" (infixl "**" 70) where
"k4oC x y = (case x y of k1 k1 => k1)"
--{*Error in case expression:
Not a datatype constructor: "i130429a.k1"
In clause
((k1 k1) ⇒ k1)*}
Это пример того, что человеку, как эксперту, так и новичку, нужен учебник для ознакомления с основными функциями программирования Изабель.
Если вы говорите: "Есть учебники, которые делают это". Я говорю: "Нет, нет, по моему мнению".
В учебниках подчеркиваются важные, изощренные черты Изабель, которые отделяют ее от толпы.
Это комментарий, но он предназначен для того, чтобы увязать вопрос "Как я могу выучить Изабель?" И с чем связан мой первоначальный вопрос выше.
То, как вы изучаете Изабель, не будучи аспирантом в Кембридже, TUM или NICTA, заключается в том, что вы боретесь от 6 до 12 месяцев или более. Если в течение этого времени вы не откажетесь, вы можете быть на уровне, который позволит вам оценить доступные инструкции среднего уровня. Опыт может отличаться.
Для меня 3 книги, которые выведут меня на следующий уровень доказывания, отучая меня от auto а также metis, когда я найду время, чтобы пройти их,
- Изабель - помощник по проверке логики высшего порядка
- Программирование и проверка в Изабель /HOL
- Изабель /Isar --- универсальная среда для удобочитаемых документов
Если кто-то скажет: "Вы злоупотребили форматом ответов Stackru, участвуя в многословных комментариях и мнениях".
Я говорю: "Ну, я попросил хороший способ сделать немного базового программирования в Изабель, где я надеялся на что-то более сложное, чем большой if-then-else заявление. Никто не предоставил ничего похожего на то, что я просил. На самом деле, я предоставил функцию сопоставления с образцом, и то, что мне нужно было сделать, даже близко не документировано. Сопоставление с образцом является простой концепцией, но не обязательно в Изабель, из-за требований к доказательству для рекурсивных функций. (Если есть простой способ сделать это, чтобы заменить мой if-then-else функция ниже, или даже case Заявление кстати, я бы наверняка хотел узнать.)
Сказав это, я склонен взять на себя некоторые свободы, и на данный момент у этой страницы всего 36 просмотров в любом случае, из которых, вероятно, по крайней мере 10 из моего браузера.
Изабель /HOL - мощный язык. Я не жалуюсь. Это только звучит так.)
(Конец обновления)
Это может многое значить, просто чтобы знать, что что-то является истинным или ложным, в этом случае говорят, что function может работать с неиндуктивными типами. Тем не менее, как я в конечном итоге с помощью function ниже не является результатом того, что я видел в каком-либо одном документе Изабель, и мне был нужен этот бывший вопрос SO о принудительном подтипировании:
Что такое подтип Изабель /HOL? Какие команды Isar создают подтипы?
В итоге у меня есть два способа заполнения части таблицы умножения 2х2. Здесь я ссылаюсь на теорию: как ASCII, дружественный A_i130429a.thy, jEdit, дружественный i130429a.thy, PDF и папку.
Два способа:
- Неуклюжий, но быстрый и
simpдружелюбныйif-then-elseпуть. Определение занимает 0 мс, а доказательство занимает 155 мс. - Способ сопоставления с образцом с использованием
function, Здесь я мог бы долго публично думать об этом, но не буду. Я знаю, что я буду использовать то, что я узнал здесь, но это определенно не элегантное решение для простой функции таблицы умножения, и далеко не очевидно, что человеку придется делать все это, чтобы создать базовую функцию, которая использует сопоставление с образцом, Конечно, возможно я не должен делать все это. Определение занимает 391 мс, а доказательство - 317 мс.
Что касается необходимости прибегать к использованию if-then-else либо Isabelle/HOL не богата функциональными возможностями, когда речь идет об основных операторах программирования, либо эти основные операторы не документированы. if-then-else заявление даже не в индексе справочника Изара. Я думаю: "Если это не задокументировано, может быть, есть хороший, недокументированный case заявление, как у Хаскелла ". Тем не менее, я бы взял Изабель над Хаскеллом в любой день.
Ниже я объясню различные разделы A_i130429a.thy. Это вроде тривиально, но не полностью, так как я не видел пример, который научил бы меня, как это сделать.
Я начинаю с типа и четырех констант, которые остаются неопределенными.
typedecl kT
consts
k1::kT
ka::kT
kb::kT
kab::kT
Следует отметить, что константы остаются неопределенными. То, что я оставляю многое неопределенным, является частью того, почему у меня возникают проблемы с поиском хороших примеров в документах и источниках, которые я могу использовать в качестве шаблонов для себя.
Я делаю тест, чтобы попытаться разумно использовать function на неиндуктивном типе данных, но это не работает. Со мной if-then-else Функция, после того, как я выясню, что я не ограничиваю свой домен функции, я вижу, что проблема с этой функцией была также с доменом. function k4f0 хочет x быть k1 или же ka для каждого x что, очевидно, не соответствует действительности.
function k4f0 :: "kT => kT" where
"k4f0 k1 = k1"
| "k4f0 ka = ka"
apply(auto)
apply(atomize_elim)
--"goal (1 subgoal):
1. (!! (x::sT). ((x = k1) | (x = ka)))"
Я сдаюсь и определяю мне некрасивую функцию с if-then-else,
definition k4o :: "kT => kT => kT" (infixl "**" 70) where
"k4o x y =
(if x = k1 & y = k1 then k1 else
(if x = k1 & y = ka then ka else
(if x = ka & y = k1 then ka else
(if x = ka & y = ka then k1 else (k1)
))))"
declare k4o_def [simp add]
Трудная часть становится попытка доказать ассоциативность моей функции k4o, Но это только потому, что я не ограничиваю домен. Я включил в утверждение, и auto магия пинает, fastforce магия есть и быстрее, поэтому я использую ее.
abbreviation k4g :: "kT set" where
"k4g == {k1, ka}"
theorem
"(x \<in> k4g & y \<in> k4g & z \<in> k4g) --> (x ** y) ** z = x ** (y ** z)"
by(fastforce)(*155ms*)
Волшебство делает меня счастливым, и тогда у меня появляется мотивация попытаться сделать это с function и сопоставление с образцом. Из-за недавнего ответа SO на принудительное подтипирование, связанного с вышеупомянутым, я выясняю, как исправить домен с помощью typedef, Я не думаю, что это идеальное решение, но я определенно чему-то научился.
typedef kTD = "{x::kT. x = k1 | x = ka}"
by(auto)
declare [[coercion_enabled]]
declare [[coercion Abs_kTD]]
function k4f :: "kTD => kTD => kT" (infixl "***" 70) where
"k4f k1 k1 = k1"
| "k4f k1 ka = ka"
| "k4f ka k1 = ka"
| "k4f ka ka = k1"
by((auto),(*391ms*)
(atomize_elim),
(metis (lifting, full_types) Abs_kTD_cases mem_Collect_eq),
(metis (lifting, full_types) Rep_kTD_cases Rep_kTD_inverse mem_Collect_eq),
(metis (lifting, full_types) Rep_kTD_cases Rep_kTD_inverse mem_Collect_eq),
(metis (lifting, full_types) Rep_kTD_cases Rep_kTD_inverse mem_Collect_eq),
(metis (lifting, full_types) Rep_kTD_cases Rep_kTD_inverse mem_Collect_eq))
termination
by(metis "termination" wf_measure)
theorem
"(x *** y) *** z = x *** (y *** z)"
by(smt
Abs_kTD_cases
k4f.simps(1)
k4f.simps(2)
k4f.simps(3)
k4f.simps(4)
mem_Collect_eq)(*317ms*)