webew
Войти » Регистрация
 
С/C++
Алгоритмы

Рекомендация Дейкстры в отношении условий цикла

27 ноября 2012, 4:41
Автор: rgbeast
В книге "Дисциплина программирования" (1976) Э. Дейкстра рекомендует выбирать условие выхода из цикла как можно более слабым.

Чтобы не вводить формальный язык, применяемый в книге, опишу рассмотренный им пример на языке C. Пусть имеется цикл по i от k до n-1, часто записываемый в виде:
for(i=k;i<n;i++) {
 ...
}

Дейкстра рекомендует ослабить условие i<n до i!=n, сделав цикл вида
for(i=k;i!=n;i++) {
 ...
}

Причина рекомендации в том, что наш цикл предполагает предусловие k<=n. Если k>n, выполнение цикла скорее всего не даст правильный ответ. Например, мы знаем k факториал и хотим вычислить n факториал.
X = factorial(k);
for(i=k;i<n;i++) {
 X*=(i+1);
}

Подобный цикл даст правильный ответ только при условии k<=n. Если k>n, традиционный цикл не будет выполняться, что сохранит значение k факториал и алгоритм, завершившись успешно, даст сбой. Вариант Дейкстры в случае нарушения предусловия зациклится и никогда не завершится, что позволит избежать ошибочного ответа всей программы.

Конечно, имеется в виду, что предусловие проверяется явно до цикла, но все же сам цикл как конструкция не должен по мнению Дейкстры допускать неправильного использования.

Какие сейчас существуют техники, чтобы цикл как конструкция при некорректных условиях не зацикливался, а выдавал ошибку? Это необходимо, если цена зацикливания так же велика, как и цена ошибки. Интересует не проверка до цикла, а именно конструкция цикла, автоматически включающая такую проверку.
Добавить комментарий
Отображение комментариев: Древовидное | Плоское

1234ru

ну в любом случае как-то нужно понять, что происходит ошибка. Сам цикл своими средствами это не умеет.
То, что не убивает нас, делает нас инвалидами.
27.11.2012, 18:12
Ответить
NO USERPIC

rgbeast

Может быть цикл можно сразу писать в таком виде (вписать в него такую конструкцию), чтобы умел отследить ошибку. Отделенный от цикла if всегда будет потенциальным источником ошибок, так как его нужно синхронно изменять при изменении цикла.
27.11.2012, 18:58
Ответить

deadka

Что тут можно сказать...

В c++ действительно такая рекомендация есть. К примеру, хотя бы по тому, что, в случае переобпределённых
операторов и контейнеров, != будет гораздо быстрее работать. Представим ситуацию с односвязным линейным списком - реализация оператора < будет работать исключительно долго в отличии от !=. Да только к языку C это отношения не имеет.

Кроме того, есть ассерты - самый в общем случае хороший способ отладки. После цикла assert(i==n); - и вуаля.

Цитата:
Вариант Дейкстры в случае нарушения предусловия зациклится и никогда не завершится, что позволит избежать ошибочного ответа всей программы.


Если говорить про этот цикл - здесь рано или поздно произойдёт обнуление (в случае unsigned переменной) или переход в минус. Если создать short int, присвоить ему 32767 и прибавить один - произойдёт не то, чего мы ждём.
Так что здесь из цикла мы все равно вывалимся - просто с задержкой. И будет ошибочный ответ программы.
Рекомендация Дейкстры сработала бы в случае, если бы у нас итератор цикла мог принимать значение "бесконечность", а в языке C - не так. Вернее в случае float бесконечность есть, но сравнивать флоаты на прямое равенство, как известно, не стоит :).

Вместо ассерта после цикла стоит воткнуть ассерт перед циклом (ну или исключение кидать)
assert(k<=n);
Через more, через less мы бредем в страну чудес...
27.11.2012, 19:24
Ответить
NO USERPIC

rgbeast

Дейкстра писать не про какой-то конкретный язык, а вообще, поэтому средства языка можно приспосабливать под правильное программирование. Получается, что все циклы правильно писать так
for(assert(k<=n),i=k;i!=n;i++) {
}
27.11.2012, 19:43
Ответить

deadka

Типа того, единственно, что со стилистической т.з. я бы вытащил ассерт за пределы цикла, чтобы не смешивать отладку и функционал. Собраться оно и так соберется (даже с ключом -DNDEBUG ), и работать будет и так, конечно.
Через more, через less мы бредем в страну чудес...
27.11.2012, 20:15
Ответить
NO USERPIC

rgbeast

Мне кажется вопрос имеет отношение к сути рекомендации Дейкстры. Если вытащить assert наружу, то в процессе работы над программой он может идти не прямо перед циклом, а быть отделенным какими-то командами или потом может стать заменен проверкой другого типа. Кроме того, он может рассогласоваться с самим циклам, а для некоторых циклов программист забудет его написать. Если не говорить напрямую про C++, а иметь в виду предполагаемый язык, то для достижения алгоритмической достоверности лучше, чтобы предусловие было частью конструкции цикла и обязать программистов во всех циклах его указывать.
27.11.2012, 21:17
Ответить

1234ru

rgbeast
Может быть цикл можно сразу писать в таком виде (вписать в него такую конструкцию), чтобы умел отследить ошибку. Отделенный от цикла if всегда будет потенциальным источником ошибок, так как его нужно синхронно изменять при изменении цикла.


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


Другими словами, ты хочешь if (в широком понимании) вписать внутрь определения цикла.
Похоже, это и есть реализация обсуждаемой рекомендации.
То, что не убивает нас, делает нас инвалидами.
28.11.2012, 16:13
Ответить
Добавить комментарий
Отображение комментариев: Древовидное | Плоское
© 2008—2017 webew.ru, связаться: x собака webew.ru
Сайт использует Flede и соответствует стандартам WAI-WCAG 1.0 на уровне A.
Rambler's Top100

Реклама: