Могут ли функции Haskell быть доказаны / проверены на модели / проверены со свойствами корректности?

Question

Продолжая идеи: Существуют ли какие-либо доказуемые языки реального мира?

Я не знаю о вас, но мне надоело писать код, которыйЯ не могу гарантировать.

Задав вышеупомянутый вопрос и получив феноменальный ответ (Спасибо всем!), Я решил сузить свой поиск доказуемого, прагматичного подхода к Haskell .Я выбрал Haskell, потому что он действительно полезен (для него написано много web frameworks , это хороший тест) AND Iя думаю, что это достаточно строго, функционально , что это может быть доказуемо или, по крайней мере, разрешить тестирование инвариантов.

Вот что я хочу (и не смоглинайти)

Мне нужна структура, которая может посмотреть на функцию Haskell, добавить ее, написанную в псевдокоде:

add(a, b):
    return a + b

- и проверить, сохраняются ли определенные инварианты в каждом состоянии выполнения.Я бы предпочел какое-то формальное доказательство, однако я бы согласился на что-то вроде средства проверки моделей.
В этом примере неизменным будут значения, заданные a и b возвращаемое значение всегда равно сумме a + b .

Это простой пример, но я не думаю, что такая структура невозможна.Конечно, будет верхний предел сложности функции, которую можно протестировать (10 строковых входов в функцию, безусловно, займут много времени!), Но это будет способствовать более тщательному проектированию функций и ничем не отличается от использования других формальныхметоды.Представьте себе использование Z или B, когда вы определяете переменные / наборы, вы чертовски уверены, что задаете переменным наименьший возможный диапазон.Если ваш INT никогда не будет выше 100, обязательно инициализируйте его как таковой!Подобные методы и правильная декомпозиция проблемы должны, как мне кажется, обеспечить удовлетворительную проверку чисто функционального языка, такого как Haskell.

Я пока еще не очень разбираюсь в формальных методах или Haskell.Дайте мне знать, если моя идея правильная, или, может быть, вы думаете, что haskell не подходит?Если вы предлагаете другой язык, убедитесь, что он прошел тест "has-a-web-framework", и прочитайте оригинальный вопрос : -)

Answer 1

Ну, несколько вещей для начала, так как вы выбираете маршрут на Haskell:

• Вы знакомы с перепиской Карри-Ховарда ? На этом основании существуют системы, используемые для проверок, проверенных машиной, которые во многих отношениях являются просто функциональными языками программирования с очень мощными системами типов.

• Вы знакомы с областями абстрактной математики, которые предоставляют полезные понятия для анализа кода на Haskell? Многочисленные ароматы алгебры и некоторые элементы теории категорий часто встречаются.

• Имейте в виду, что Haskell, как и все языки, полные по Тьюрингу, всегда имеет возможность нетерминирования. В общем, гораздо сложнее доказать, что что-то будет всегда истинным, чем доказать, что что-то будет правдой или будет зависеть от непостоянного значения.

Если вы серьезно хотите получить доказательство , а не просто тестирование , вот о чем нужно помнить. Основное правило таково: недопустимые состояния приводят к ошибкам компилятора. Во-первых, не допускайте кодирования недопустимых данных, а затем пусть средство проверки типов сделает за вас утомительную работу.

Если вы хотите пойти еще дальше, если память служит мне помощником по проверке Coq имеет функцию "извлечения в Haskell", которая позволит вам доказать произвольные свойства критических функций, а затем превратить доказательства в Haskell код.

Для того, чтобы делать причудливые системные вещи непосредственно в Haskell, Олег Киселев - Великий Мастер . На его сайте вы можете найти примеры таких хитростей, как полиморфные типы более высокого ранга для кодирования статических доказательств проверки границ массивов .

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

Еще один шаг, который вы можете предпринять, используя легковесные проверки и хитрые системные трюки, - это использовать тот факт, что Haskell хорошо работает в качестве основного языка для встраивания доменных языков ; сначала создайте тщательно ограниченный подъязык (в идеале тот, который не является полным по Тьюрингу), о котором вы можете легче доказать полезные свойства, а затем используйте программы в этом DSL, чтобы обеспечить ключевые элементы основной функциональности вашей общей программы. Например, вы можете доказать, что функция с двумя аргументами является ассоциативной, чтобы оправдать параллельное сокращение коллекции элементов, использующих эту функцию (поскольку порядок применения функции не имеет значения, только порядок аргументов).

---

О, последнее. Несколько советов о том, как избежать ловушек, которые есть в Haskell, которые могут саботировать код, который в противном случае был бы безопасен по конструкции: ваши заклятые враги здесь общая рекурсия , IO монада и частичные функции :

• Последнее относительно легко избежать: не пишите их и не используйте их. Убедитесь, что каждый набор шаблонов соответствует каждому возможному случаю, и никогда не используйте error или undefined. Единственная сложность - избегать стандартных библиотечных функций, которые могут вызвать ошибки. Некоторые из них явно небезопасны, например fromJust :: Maybe a -> a или head :: [a] -> a, но другие могут быть более тонкими. Если вы обнаружите, что пишете функцию, которая действительно ничего не может сделать с некоторыми входными значениями, то вы разрешаете кодировать недопустимые состояния в соответствии с типом ввода и должны сначала это исправить.

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

• Слова мудрым: Обоснованная рекурсия и Производительная базовая экскурсия . Всегда следите за тем, чтобы рекурсивные функции либо переходили из некоторой начальной точки в известный базовый случай, либо генерировали ряд элементов по требованию. В чистом коде самый простой способ сделать это - либо рекурсивно свернуть конечную структуру данных (например, вместо непосредственного вызова функции при увеличении счетчика до некоторого максимума, создать список, содержащий диапазон значений счетчика, и сложить его ) или рекурсивно генерировать ленивую структуру данных (например, список прогрессивных приближений к некоторому значению), при этом тщательно никогда не смешивая их напрямую (например, не просто «найти первый элемент в потоке, удовлетворяющий некоторому условию»; это может не произойти); Вместо этого возьмите значения из потока до некоторой максимальной глубины, затем найдите конечный список, обрабатывая необнаруженный случай соответствующим образом).

• Объединяя два последних элемента, для частей, в которых вы действительно нуждаетесь IO, с общей рекурсией, попробуйте собрать программу как инкрементные компоненты, а затем сконцентрируйте все неудобные биты в одной функции "драйвера". Например, вы могли бы написать цикл обработки событий GUI с чистой функцией, такой как mainLoop :: UIState -> Events -> UIState, выходным тестом, таким как quitMessage :: Events -> Bool, функцией для получения ожидающих событий getEvents :: IO Events и функцией обновления updateUI :: UIState -> IO (), а затем фактически запустить эту вещь. с обобщенной функцией типа runLoopIO :: (b -> a -> b) -> b -> IO a -> (b -> IO ()) -> IO (). Это сохраняет сложные части по-настоящему чистыми, позволяя запускать всю программу со сценарием событий и проверять результирующее состояние пользовательского интерфейса, в то же время изолируя неудобные рекурсивные части ввода-вывода в единую абстрактную функцию, которую легко понять и которая зачастую неизбежно будет правильной. параметричность .

Answer 2

Вероятно, самое близкое к тому, что вы просите - это Haskabelle , инструмент, который поставляется с помощником по проверке Isabelle , который может переводить файлы Haskell в теории Изабель и позволяет вам доказатьо нихНасколько я понимаю, этот инструмент разработан в рамках проекта HOL - ML - Haskell, и страница документации содержит некоторую информацию о теории.

Я не очень знаком с этим проектоми я не очень много знаю о том, что было сделано с этим.Но я знаю, Брайан Хаффман играл с этими вещами, проверял его бумаги и беседы, они должны содержать соответствующие вещи.

Answer 3

Я не уверен, действительно ли то, что вы просите, сделает вас счастливыми. : -)

Проверка модели на языке общего назначения практически невозможна, поскольку модели должны быть предметно-специфичными для практического использования. Из-за теоремы Гёделя о неполноте просто не существует способа автоматического поиска доказательств в достаточно выразительной логике.

Это означает, что вы должны написать доказательства , что ставит вопрос о том, стоит ли затраченное время затраченного времени. Конечно, усилия создают нечто очень ценное, а именно, гарантию того, что ваша программа верна. Вопрос не в том, нужно ли это иметь, а в том, слишком ли дорого обходится потраченное время. Суть доказательств в том, что, хотя у вас может быть "интуитивное" понимание того, что ваша программа правильна , часто очень 1011 * трудно формализовать это понимание в качестве доказательства. Проблема с интуитивным пониманием заключается в том, что он очень подвержен случайным ошибкам (опечаткам и прочим глупым ошибкам). Это основная дилемма написания правильных программ.

Таким образом, исследование правильности программы заключается в том, чтобы упростить формализацию доказательств и автоматическую проверку их правильности. Программирование является неотъемлемой частью «легкости формализации»; очень важно писать программы в стиле, который легко обдумать. В настоящее время мы имеем следующий спектр:

• Императивный язык, такой как C, C ++, Fortran, Python: здесь очень трудно что-либо формализовать. Модульные тесты и общие рассуждения - единственный способ получить хоть какую-то уверенность. Статическая типизация ловит только тривиальные ошибки (что гораздо лучше, чем не ловить их!).

• Чисто функциональные языки, такие как Haskell, ML: система выразительных типов помогает отлавливать нетривиальные ошибки и ошибки. Я бы сказал, что доказательство правильности вручную полезно для фрагментов примерно до 200 строк. (Например, я сделал доказательство для моего операционного пакета .) Quickcheck тестирование - дешевая замена формализованным доказательствам.

• Языки с независимой типизацией и помощники по проверке, такие как Agda, Epigram, Coq: Доказательство правильности целых программ возможно благодаря автоматической помощи с формализацией и обнаружением доказательств. Тем не менее, бремя все еще остается высоким.

На мой взгляд, в настоящее время лучше всего писать правильные программы чисто функциональное программирование . Если жизнь зависит от правильности вашей программы, вам лучше подняться на уровень выше и использовать помощника по проверке.

Answer 4

Звучит так, как вы хотите ESC / Haskell: http://research.microsoft.com/en-us/um/people/simonpj/papers/verify/index.htm

О, и теперь у Agda есть веб-фреймворк (как минимум, подтверждение концепции): http://www.reddit.com/r/haskell/comments/d8dck/lemmachine_a_web_framework_in_agda/

Answer 5

Вы смотрели на quickcheck?Он может предложить некоторые вещи, которые вам нужны.

http://www.haskell.org/haskellwiki/Introduction_to_QuickCheck

Answer 6

Взгляните на Zeno .Цитируя вики-страницу:

Zeno - это автоматизированная система проверки свойств программы на Haskell;разработанный в Имперском колледже Лондона Уильямом Соннексом, Софией Дроссопулу и Сьюзен Айзенбах.Он направлен на решение общей проблемы равенства между двумя терминами Haskell для любого входного значения.

Многие инструменты проверки программ, доступные сегодня, имеют разновидность проверки моделей;в состоянии очень быстро пройти очень большое, но ограниченное пространство поиска.Они хорошо подходят для задач с большим описанием, но без рекурсивных типов данных.Zeno, с другой стороны, предназначен для индуктивного доказательства свойств в бесконечном пространстве поиска, но только с небольшими и простыми характеристиками.

Answer 7

Ваш, казалось бы, простой пример, добавить (a, b), на самом деле трудно проверить - с плавающей запятой, переполнением, недостаточным заполнением, прерываниями, проверен ли компилятор, проверено аппаратное обеспечение и т. Д.

Habit - это упрощенный диалект языка Haskell, который позволяет проверять свойства программы.

Hume - это язык с 5 уровнями, каждый из которых более ограничен и поэтому его легче проверить:

Full Hume
  Full recursion
PR−Hume
  Primitive Recursive functions
Template−Hume
  Predefined higher−order functions
  Inductive data structures
  Inductive  Non−recursive first−order functions
FSM−Hume
  Non−recursive data structures
HW−Hume
  No functions
  Non−recursive data structures

Конечно, самый популярный сегодня метод доказательства свойств программы - это модульное тестирование, которое предоставляет сильные теоремы, но эти теоремы слишком специфичны. «Виды, считающиеся вредными», Пирс, слайд 66

Answer 8

Конечно, формально можно доказать некоторые свойства программ на Haskell.Я должен был сделать это на экзамене по FP: учитывая два выражения, докажите, что они обозначают одну и ту же функцию.В общем, сделать это невозможно, поскольку Haskell завершен по Тьюрингу, поэтому любой механический испытатель должен быть либо помощником по проверке (полуавтоматический с руководством пользователя), либо средством проверки модели.

Были попыткисм., например, P-logic: проверка свойств для программ на Haskell или Подтверждение корректности функциональных программ с использованием Mizar .Оба являются академическими работами, описывающими методы больше, чем реализации.

Answer 9

Вы можете использовать инструмент hs-to-coq, чтобы преобразовать Haskell в основном автоматически в Coq, а затем использовать всю мощь Coq Доказатель для проверки вашего кода на Haskell.См. Документы https://arxiv.org/abs/1803.06960 и https://arxiv.org/abs/1711.09286 для получения дополнительной информации.

Answer 10

Инструмент AProVE способен (по крайней мере) доказать завершение программ на Haskell, что является частью проверки правильности. Более подробную информацию можно найти в этой статье ( более короткая версия ).

Кроме того, вас могут заинтересовать Зависимые типы . Здесь система типов расширена и используется, чтобы сделать невозможными неправильные программы.