КаталогИндекс раздела


    

О понимании программ

Эдсгер В. Дейкстра

On Understanding Programs (EWD264)

По многим причинам я установил требование, что если мы хотим иметь возможность надежно конструировать действительно большие программы, нам нужна такая дисциплина, чтобы интеллектуальные затраты E (измеряемые в каком-то общем смысле), необходимые для понимания программы, не росли быстрее, чем пропорционально длине программы L (измеряемой также в общем смысле), и что если наилучшее, чего мы можем достичь, является рост E пропорционально, скажем, L2, то нам лучше всего признать поражение. Я опасаюсь, что большинство программ пишется в таком стиле, что функциональная зависимость более похожа на экспоненциальный рост: E = eL.

Теперь я предлагаю на рассмотрение читателя пример, показывающий, как одна и та же программа может пониматься двумя разными способами: при одном способе E растет пропорционально L, при другом оно растет экспоненциально (даже хуже).

Я выражаю E в количестве необходимых "шагов рассуждения".

Давайте рассмотрим "протяженную" программу в форме

  "S1; S2; ...; SN" (1)

т.е., соответствующие вычисления являются временной последовательностью выполнений от S1 до SN в таком порядке. Если известен эффект от выполнения каждого отдельного оператора Si, то мои соглашения об измерениях устанавливают, что потребуется N шагов для понимания программы (1), т.е., для установления, что кумулятивный эффект N успешных действий удовлетворяет требованиям, предъявляемым к вычислениям, выполняемым программой (1).

В случае программы в форме

  "if B then S1 else S2" (2)

где, опять-таки, эффект выполнения операторов S1 и S2 известен, мои соглашения об измерениях устанавливают, что потребуется 2 шага для понимания программы (2), а именно, один шаг для случая B и один шаг для случая не B.

Рассмотрим теперь программу в форме

  "if B1 then S11 else S12  
   if B2 then S21 else S22  
            .  
            .  
            .  
   if BN then SN1 else SN2" (3)

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

    "if Bi then Si1 else Si2"

эквивалентен эффекту выполнения абстрактного оператора Si. Имея N таких операторов выбора, нам потребуется 2N шагов, чтобы привести программу (3) к форме программы (1); понимание получившейся формы потребует еще N шагов, итого имеем 3N шагов рассуждений.

Если мы не вводим абстрактного оператора Si, но попытаемся понять программу (3) непосредственно, в терминах выполнения операторов Sij, каждое такое вычисление каждое такое вычисление будет иметь кумулятивный эффект выполнения N таких операторов и, таким образом, требовать N шагов для его понимания. Попытка понять алгоритм в терминах Sij, однако, предполагает, что мы должны рассмотреть 2N различных процедур в программе, и это приведет к N*2N шагам рассуждений!

Если теперь читатель возразит, что второй путь понимания программы (3) крайне глупый, то я считаю, что он находится именно на той позиции, на которой я и хотел его видеть, более полного согласия быть не может. Дело в том, что любая попытка усовершенствовать второй метод приводит к тому, что метод становится больше похож на первый: вы обнаружите, что вы ввели абстрактные операторы Si (или какие-то их комбинации)!

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

Эдсгер В. Дейкстра
Технологический университет
ЭЙНДХОВЕН
Нидерланды


КаталогИндекс раздела