Бертран Мейер - Основы объектно-ориентированного программирования

Практический способ гарантии завершения циклического процесса состоит в связывании с итерационным процессом целочисленной величины - варианта цикла, обладающего следующими свойствами:

[x].Вариант всегда не отрицателен.

[x].Любое выполнение тела цикла уменьшает вариант.

Так как целочисленная неотрицательная величина не может уменьшаться бесконечно, то наличие варианта позволяет гарантировать завершение цикла. Вариант является верхней границей, максимальным числом применений body , приводящим точку в POST . В задаче нахождения максимума найти вариант просто: t.upper - i . Это выражение удовлетворяет обоим условиям:

[x].Предусловие программы требует положительности t.capacity ; другими словами, программа применима только к непустым массивам. Инвариант класса ARRAY задает: capacity = upper - lower + 1 . Отсюда следует, что свойство i <= t.upper будет выполняться после инициализации i значением t.lower .

[x].Любое выполнение тела цикла выполняет инструкцию i := i + 1 , уменьшая вариант на единицу.

В этом примере цикл является простым итерированием на последовательности целых чисел в конечном интервале, известный в языках программирования, как "цикл For" или "цикл DO", завершение которого не трудно проверить. Для более изощренных циклов число требуемых итераций определить не так просто, выявление завершения становится сложной задачей, единственным универсальным способом является нахождение варианта.

Нам понадобится еще одно понятие, преобразующее только что набросанную схему в программный текст, описывающий цикл. Мы нуждаемся в простом способе определения того, что текущая итерация достигла цели (постусловия) post . Поскольку итерация конструируется так, чтобы обеспечить выполнение INV , а POST является частью INV , то обычно можно найти условие exit такое, что элемент из INV принадлежит POST тогда и только тогда, когда выполняется exit . Другими словами, постусловие post и инвариант inv связаны соотношением:

post = inv and exit

так что мы можем остановить цикл, - чьи промежуточные состояния по построению удовлетворяют inv , - как только выполнится exit . В этом состоянии, следовательно, будет выполнено и post .

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

[x].Инвариант цикла inv - утверждение.

[x].Условие выхода exit , чья конъюнкция с inv дает желаемую цель.

[x].Вариант var - целочисленное выражение.

[x].Множество инструкций инициализации, которые всегда приводят к состоянию, в котором inv выполняется, а var становится неотрицательным.

[x].Множество инструкций body , которое (при условии, что оно начинается в состоянии, где var неотрицательно и выполняется inv ), сохраняет инвариант и уменьшает var , в то же время следя за тем, чтобы оно не стало меньше нуля.

[x].Синтаксис цикла честно комбинирует эти ингредиенты:

from

init

invariant

inv

variant

var

until

exit

loop

body

end

Предложения invariantи variantявляются возможными. Предложение fromпо синтаксису требуется, но инструкция init может быть пустой.

Эффект выполнения цикла можно описать так: вначале выполняется init , затем 0 или более раз выполняется тело цикла, которое перестает выполняться, как только exit принимает значение false .

В языках Pasal, C и других такой цикл называется "циклом while", в отличие от цикла типа " repeat ... until", в котором тело цикла выполняется, по меньшей мере, один раз. Здесь же тест является условием выхода, а не условием продолжения, и синтаксис цикла явно содержит фазу инициализации. Потому эквивалент записи нашего цикла на языке Pascal выглядит следующим образом: