Рекомендация Дейкстры в отношении условий цикла
27 ноября 2012, 8:41
Автор: rgbeast
В книге "Дисциплина программирования" (1976) Э. Дейкстра рекомендует выбирать условие выхода из цикла как можно более слабым.
Чтобы не вводить формальный язык, применяемый в книге, опишу рассмотренный им пример на языке C. Пусть имеется цикл по i от k до n-1, часто записываемый в виде:
Дейкстра рекомендует ослабить условие i<n до i!=n, сделав цикл вида
Причина рекомендации в том, что наш цикл предполагает предусловие k<=n. Если k>n, выполнение цикла скорее всего не даст правильный ответ. Например, мы знаем k факториал и хотим вычислить n факториал.
Подобный цикл даст правильный ответ только при условии k<=n. Если k>n, традиционный цикл не будет выполняться, что сохранит значение k факториал и алгоритм, завершившись успешно, даст сбой. Вариант Дейкстры в случае нарушения предусловия зациклится и никогда не завершится, что позволит избежать ошибочного ответа всей программы.
Конечно, имеется в виду, что предусловие проверяется явно до цикла, но все же сам цикл как конструкция не должен по мнению Дейкстры допускать неправильного использования.
Какие сейчас существуют техники, чтобы цикл как конструкция при некорректных условиях не зацикливался, а выдавал ошибку? Это необходимо, если цена зацикливания так же велика, как и цена ошибки. Интересует не проверка до цикла, а именно конструкция цикла, автоматически включающая такую проверку.
Чтобы не вводить формальный язык, применяемый в книге, опишу рассмотренный им пример на языке 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);
}
for(i=k;i<n;i++) {
X*=(i+1);
}
Подобный цикл даст правильный ответ только при условии k<=n. Если k>n, традиционный цикл не будет выполняться, что сохранит значение k факториал и алгоритм, завершившись успешно, даст сбой. Вариант Дейкстры в случае нарушения предусловия зациклится и никогда не завершится, что позволит избежать ошибочного ответа всей программы.
Конечно, имеется в виду, что предусловие проверяется явно до цикла, но все же сам цикл как конструкция не должен по мнению Дейкстры допускать неправильного использования.
Какие сейчас существуют техники, чтобы цикл как конструкция при некорректных условиях не зацикливался, а выдавал ошибку? Это необходимо, если цена зацикливания так же велика, как и цена ошибки. Интересует не проверка до цикла, а именно конструкция цикла, автоматически включающая такую проверку.