Будут ли доказательства правильности кода когда-либо распространяться? [закрыто]

14

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

Casebash
источник

Ответы:

8

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

Также может быть полезно программирование для заключения контрактов. См. Microsoft Code Contracts

Jonas
источник
6
Извините - я не так много делал в "реальном мире" Haskell, но я сделал достаточно обучающих упражнений на несколько жизней. Тот факт, что он компилируется, не означает, что это сработает. По сравнению с, например, Ada (выбранным потому, что это строго императивный язык со статической типизацией), я бы сказал, что Haskell немного проще, но в основном потому, что он более лаконичен (меньше цикломатическая сложность). Имея дело с монадой IO, есть неприятности, которые могут сделать Haskell более трудным, чтобы понять правильно - это просто достаточно отличается от императивного стиля, что есть вещи, которые он не может сделать так естественно.
Steve314
На "не могу сделать как обычно", рассмотрим цикл "while". Да, вы можете свернуть свое собственное - но условие while должно быть внутри монады, потому что оно должно реагировать на побочные эффекты тела цикла. Это не только означает, что вы получили разрешение вызывать побочные эффекты в условиях while, но также затрудняет использование этого цикла while. Конечный результат - обычно проще использовать рекурсию даже в коде монада ввода-вывода - и это означает, что вы должны структурировать вещи определенным образом.
Steve314
14

Все, кроме самых тривиальных программ

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

Здесь я нашел хорошую статью на эту тему:

http://www.encyclopedia.com/doc/1O11-programcorrectnessproof.html

Док Браун
источник
Правильно - для любого программного проекта существует переход от неформального описания проблемы к формальному (обычно сегодня в форме программы), и это не проходит.
Дэвид Торнли
astree.ens.fr См. Промышленное применение Astrée здесь
zw324
@ZiyaoWei: такие инструменты полезны, но они находят только некоторые формальные ошибки, не более того. Если однострочная программа, подобная программе, printf("1")правильна или нет (например, потому что требовалось «вывести одинаково распределенное случайное число от 1 до 6»), такой статический анализатор не может решить.
Док Браун
10

Проблема с формальными доказательствами состоит в том, что это только отодвигает проблему на шаг назад.

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

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

Мейсон Уилер
источник
2
Также .. «Остерегайтесь ошибок в приведенном выше коде; я только доказал, что это правильно, а не пробовал». - Дональд Кнут
Брендан
8

Формальная проверка прошла долгий путь, но обычно отраслевые / широко используемые инструменты отстают от последних исследований. Вот некоторые недавние усилия в этом направлении:

Spec # http://research.microsoft.com/en-us/projects/specsharp/ Это расширение C #, которое поддерживает контракты кода (предварительные / последующие условия и инварианты) и может использовать эти контракты для выполнения различных типов статического анализа. ,

Подобные проекты существуют для других языков, таких как JML для Java, и Eiffel имеет это в значительной степени встроенный.

Если пойти еще дальше, такие проекты, как slam и blast, могут быть использованы для проверки определенных поведенческих свойств с минимальной аннотацией / вмешательством программиста, но все еще не могут справиться со всей общностью современных языков (такие вещи, как целочисленное переполнение / арифметика указателей не моделируются).

Я полагаю, что в будущем мы увидим гораздо больше этих методов, используемых на практике. Основным препятствием является то, что программные инварианты трудно вывести без ручных аннотаций, и программисты обычно не хотят предоставлять эти аннотации, потому что это слишком утомительно / требует много времени.

Лучина
источник
4

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

Fishtoaster
источник
Рассмотрим экономический аргумент: возможно, разработчикам лучше тратить время на доказательства правильности, чем терять деньги из-за ошибок программного обеспечения.
Андрес Ф.
Я согласен с fishtoaster, если только он не станет намного менее ресурсоемким, большая часть обычного программного обеспечения для бизнеса просто не будет иметь затрат / выгод для поддержки этого уровня правильности. В приложении LOB для целевой аудитории иногда наиболее выгодным с точки зрения затрат отчетом об ошибках для бизнеса является добавление в документы строки с надписью «не делайте этого»
Bill
3

Некоторые инструменты формальных методов (например, Frama-C для критически важного программного обеспечения для встроенного C) можно рассматривать как (своего рода) предоставление или, по крайней мере, проверку (правильности) доказательства данного программного обеспечения. (Frama-C проверяет, что программа в некотором смысле подчиняется своей формализованной спецификации и соблюдает явно аннотированные инварианты в программе).

В некоторых секторах возможны такие формальные методы, например, как DO-178C для критически важного программного обеспечения в гражданской авиации. Поэтому в некоторых случаях такие подходы возможны и полезны.

Конечно, разработка менее глючного программного обеспечения очень затратна. Но подход формального метода имеет смысл для некоторого программного обеспечения. Если вы пессимистичны, вы можете подумать, что ошибка перенесена из кода в его формальную спецификацию (которая может иметь некоторые «ошибки», потому что формализация предполагаемого поведения программного обеспечения сложна и подвержена ошибкам).

Василий Старынкевич
источник
3

Я наткнулся на этот вопрос и думаю, что эта ссылка может быть интересной:

Промышленные применения Astrée

Доказательство отсутствия RTE в системе, используемой Airbus с более чем 130 тыс. Строк кода в 2003 году, не кажется плохим, и мне интересно, кто-нибудь скажет, что это не реальный мир.

zw324
источник
2

Нет. Общая пословица для этого: «Теоретически, теория и практика одинаковы. На практике нет».

Один очень простой пример: опечатки.

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

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

Izkata
источник
3
Неправильно. Никакие модульные тесты никогда не смогут охватить весь диапазон возможных параметров. Представьте себе «модульное тестирование» компилятора таким образом, убедившись, что семантика изменений не проходит.
SK-logic
3
модульное тестирование - это не святой Грааль ...
Рифал
1
@Winston Ewert, есть проверенные компиляторы (и многие другие проверенные ассемблеры). И аппаратное обеспечение формально проверяется гораздо чаще, чем программное обеспечение. Смотрите здесь: gallium.inria.fr/~xleroy/publi/compiler-certif.pdf
SK-logic
1
@ SK-logic, да, есть игрушечные компиляторы, проверенные для академических целей. Но что на самом деле используют компиляторы? Я подозреваю, что большинство компиляторов проверяются с использованием различных форм автоматического тестирования, и почти никаких формальных корректных доказательств не делается.
Уинстон Эверт
1
@Winston Ewert, доказательства правильности практичны и широко используются в реальной жизни. Что не очень практично, так это большинство современных основных языков. Я надеюсь, что они все вымрут, поэтому ценность доказательств правильности увеличится в будущем.
SK-logic
1

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

Paddyslacker
источник
8
Проблема остановки говорит о том, что мы не можем определить, останавливается ли какая-либо произвольная программа. Эти программы могут делать странные вещи, например, проверять каждое целое число, чтобы определить, является ли оно простым числом Мерсенна. Мы не делаем это в обычных программах!
Casebash
1
@ Casebash, вопрос в том, есть ли полезное подмножество программ, для которых можно решить проблему остановки. Это ни в коем случае не ясно, в любом случае. Т.е. можем ли мы ограничить наши программы, чтобы мы не могли делать такие вещи, как тестирование каждого целого числа, не нарушая нашу способность выполнять полезные задачи?
Уинстон Эверт
1

Это уже используется всеми. Каждый раз, когда вы используете проверку типов вашего языка программирования, вы в основном делаете математическое доказательство правильности вашей программы. Это работает уже очень хорошо - просто нужно выбрать правильные типы для каждой функции и структуры данных, которые вы используете. Чем точнее тип, тем лучше будет проверка. Существующие типы, доступные в языках программирования, уже имеют достаточно мощные инструменты для описания практически любого возможного поведения. Это работает на всех доступных языках. C ++ и статические языки просто выполняют проверки во время компиляции, в то время как более динамические языки, такие как python, делают это при запуске программы. Проверка все еще существует на всех этих языках. (например, c ++ уже поддерживает проверку побочных эффектов так же, как это делает haskell,

ТР1
источник
Немного о побочных эффектах в C ++, вы имеете в виду константность?
Уинстон Эверт
да, const + const функция-член. Если все ваши функции-члены являются константными, все данные в объектах не могут быть изменены.
tp1
Они все еще могут быть изменены, если вы используете mutableили const_cast. Я, конечно, вижу связь, которую вы там делаете, но вкус двух подходов мне кажется довольно разным.
Уинстон Эверт
Ну, вот почему вы должны выбрать его использовать - всегда есть способы обойти это. Но важный момент - как заставить компиляторы проверять наличие проблем в этой области.
tp1