Мнение об “инвариантах цикла”, и они часто используются в промышленности?
Я вспоминал о своем первом годе обучения в колледже (пять лет назад), когда я сдал экзамен для размещения - из информатики вводного уровня. Был вопрос об инвариантах цикла, и я задавался вопросом, действительно ли инварианты цикла необходимы в этом случае или если вопросом был просто плохой пример... вопрос состоял в том, чтобы записать повторяющееся определение для функции факториала, и затем доказать, что функция была корректна.
Код, что я предусмотрел функцию факториала, был следующие:
public static int factorial(int x)
{
if ( x < 0 ){
throw new IllegalArgumentException("Parameter must be >= 0");
}else if ( x == 0 ){
return 1;
}else{
int result = 1;
for ( int i = 1; i <= x; i++ ){
result*=i;
}
return result;
}
}
Моим собственным доказательством правильности было доказательство случаями, и в каждом, что я утверждал, что это было корректно по определению (x! не определено для отрицательных величин, 0! 1 и x! 1*2*3...*x для положительного значения x). Преподаватель хотел, чтобы я доказал цикл с помощью инварианта цикла; однако, мой аргумент был то, что это было корректно "по определению", потому что определение "x!" для положительного целого числа x является "продуктом целых чисел от 1... x", и для цикла в выражении else является просто буквальный перевод этого определения. Действительно ли цикл является инвариантным действительно необходимый как доказательство правильности в этом случае? Насколько сложный цикл должен быть перед инвариантом цикла (и надлежащие условия инициализации и завершения) становятся необходимыми для доказательства правильности?
Кроме того, я задавался вопросом..., как часто такие формальные доказательства используются в промышленности? Я нашел, что приблизительно половина моих курсов является очень теоретической, и тяжелая доказательством и приблизительно половина очень реализация и тяжелый кодированием, без любого формального или теоретического материала. Сколько они перекрывают на практике? Если Вы действительно используете доказательства в промышленности при применении их (всегда, только если она является сложной, редко, никогда)?
Править
Если мы, сами, убеждены, что часть кода корректна, может убедить других (неофициально), что это корректно, и там существует модульные тесты, до какой степени формальные доказательства правильности необходимы?
4 ответа
в какой степени необходимы формальные доказательства правильности ?
Это зависит, конечно, но я думаю, что для программистов важно знать, как писать код, не подверженный ошибкам, где он имеет тенденцию быть правильным по конструкции.
Одним из примеров является концепция «упреждающего просмотра», например, при синтаксическом анализе, когда следующий токен ввода не «читается», затем «просматривается» и затем, возможно, «возвращается», если он есть не то, что требуется, а скорее «посмотрел» и затем, возможно, «принял», если это то, что требуется. Когда, например, вы пишете циклы для циклического перебора записей базы данных и извлечения промежуточных итогов, это простое изменение перспективы может привести к гораздо более простому и надежному коду.
Другой пример - дифференциальное исполнение , техника, на которую я наткнулся много лет назад. Похоже, что это позволяет инкрементно повторно выполнять любой алгоритм, чтобы постепенно обновлять его результаты. Я широко использую его в пользовательских интерфейсах, где содержимое может динамически изменяться. Долгое время я чувствовал, что это работает во всех случаях, но не мог быть уверен, пока наконец не доказал это , как показано внизу моей страницы в Википедии . После этого я знал, что, если я буду придерживаться некоторых простых ограничений, я могу положиться на его работу, независимо от того, сколько кода от этого зависит.
В то же время мы можем быть полностью уверены в правильности некоторого алгоритма, но нам очень трудно его формально доказать, потому что наши методы доказательства плохи. Рассмотрим скромную пузырьковую сортировку. Очевидно, это работает, но попробуйте доказать это формально, применив правила к исходному коду.Я сделал это, но это не легко. Я не пробовал более продвинутые алгоритмы сортировки.
Профессор хотел, чтобы я доказал цикл, используя инвариант цикла;
Ваш профессор хотел убедиться, что вы понимаете инварианты цикла, а не просто доказать что-то об очень простой функции.
Действительно ли инвариант цикла нужен как доказательство корректности в этом случае?
Ну, технически, нет. По этой причине вам также не нужно писать факториальную функцию: просто используйте библиотечную функцию! Но суть упражнения не в этом.
Насколько сложным должен быть цикл, прежде чем инвариант цикла (а также надлежащие условия инициализации и завершения) станет необходимым для доказательства правильности?
Я знаю некоторых умных людей, которые, вероятно, могут доказать примерно что угодно без инвариантов, и есть люди, которым нужно использовать их даже в таких тривиальных случаях, как приведенный выше. Это все равно, что спросить: «Насколько тяжелым должен быть камень, прежде чем вам понадобится тачка, чтобы его переместить?».
Вдобавок мне было интересно ... как часто такие формальные доказательства используются в отрасли?
Записываются явно? Вероятно, редко, если только вы не работаете в определенных отраслях . Но я все еще думаю о них при написании любого, кроме самого простого, цикла.
Это похоже на то, как я не рисую предложения в схемах, но это не значит, что я никогда не думаю о грамматике, особенно если я пишу какой-то действительно важный текст. Я могу сказать вам, каково предшественник моего местоимения, хотя я никогда не удосужился изложить этот факт на бумаге.
В последние годы «разработка, управляемая тестированием» под разными названиями была самым дальним, с чего большинство людей пытались рассуждать о своем коде. Это скорее похоже на очень осторожные и повторяемые эксперименты, а не на логические рассуждения. Наука против математики!
В таких языках, как Eiffel, в некоторых случаях используются предварительные условия, постусловия и инварианты цикла / класса, и предстоящая поддержка «контрактов» в .NET 4.0 может способствовать дальнейшей популяризации этих идей.
Лично я в наши дни довольно редко использую утверждения; когда я перебираю структуру, я обычно больше не пишу ее как цикл. Я пишу это как запрос, например Linq на C # или аналогичные вещи на других языках, таких как JS. Таким образом, меньше императивных манипуляций с состоянием, чтобы ошибиться (обычно их нет). И любое утверждение о результатах было бы излишним, поскольку оно просто переформулировало бы условия в запросе: в подходе запроса вы описываете желаемые результаты.
Это не означает, что я никогда не использую утверждения; но я предпочитаю использовать их вместе с модульным тестом, и только для очень сложных алгоритмов, которые выполняют сложную мутацию «на месте» коллекции; в таких случаях нет «встроенного» способа запросить желаемые результаты; Я должен написать алгоритм в обязательном порядке (возможно, потому что копирование всей структуры данных было бы ужасно дорого), поэтому я покрываю его утверждениями, чтобы помочь моему модульному тесту выявить внутренние проблемы.
Когда вы решаете сложные проблемы и пишете код, который будет повторно использоваться еще долго после того, как вы уйдете, вы (должны) пройти процесс доказательства правильность каждого расписания, которое вы пишете каждый день. Разработка через тестирование - это формализация этой идеи, но ее суть такова: вам нужно доказать хотя бы себе и, желательно, другим (проверка кода!), Что написанный вами код будет обрабатывать все возможные входные данные и пути в порядке, соответствующем.
Ссоримся ли мы из-за инвариантов кода? Нет. Оцениваем ли мы работы, прежде чем вы сможете зарегистрироваться? Вроде, как бы, что-то вроде. Если команде не нравится ваш код или ваше «доказательство», вы возвращаетесь к своему ящику, чтобы исправить его, пока он не пройдет проверку.