В главе "Абстракция исполнения" я дал неформальные описания различных "машин", предназначенных для вычисления наибольшего общего делителя двух положительных (и не слишком больших) чисел. Одно описание было выражено с помощью фишки, передвигаемой по листу картона, другое — с помощью двух половинок фишки, каждая из которых двигалась вдоль своей оси, а последнее — с помощью двух регистров, каждый из которых мог содержать целое число (не превышающее некоторой границы). Физически эти три "машины" весьма различны, однако математически они очень сходны: основная часть доказательства их способности вычислять наибольший общий делитель совпадает для всех трех машин. Это объясняется тем, что они представляют всего лишь различные воплощения одного и того же набора "правил игры", и это именно тот набор правил, который ставляет сущность реального изобретения, известного как "алгоритм Евклида".

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

Такая формальная запись может обладать многочисленными преимуществами. Любой способ записи подразумевает, что всякий описываемый с его помощью предмет задается как конкретный представитель (часто бесконечного) класса объектов, которые могут быть описаны этим способом. Наш спсоб описания должен, разумеется, обеспечивать изящное и точное описание алгоритма Евклида, но когда мы этого достигнем, алгоритм Евклида окажется в действительности заданным, как представитель огромного класса всех видов алгоритмов. И в описаниях некоторых из этих других алгоритмов мы сможем найти более интересные применения нашего способа записи. В случае алгоритма Евклида есть основания утверждать, что он настолько прост, что можно обойтись его неформальным описанием. Сила формальной записи долзкна проявиться в таких достижениях, которых без нее мы никогда не смогли бы добиться!

Второе преимущество формального способа записи состоит в том, что он дает нам возможность изучать алгоритмы как математические объекты; при этом формальное описание алгоритма служит основой, позволяющей нам интеллектуально охватить этот алгоритм. Благодаря этому мы сумеем доказывать теоремы о классах алгоритмов, например пользуясь тем, что их описания обладают некоторым общим структурным свойством.

Наконец, такой способ записи позволит нам описывать алгоритмы настолько точно, что если будет задан описанный так алгоритм и заданы значения аргументов (вход), то не будет никаких сомнений относительно того, какими должны быть соответствующие ответы (выход). При этом можно считать, что вычисление выполняется автоматом, который, получив (формально описанный) алгоритм и аргументы, порождает ответы без дальнейшего вмешательства человека. Такие автоматы, способные обеспечивать взаимное воздействие алгоритма и аргумента, и в самом деле были построены. Они называются "автоматическими вычислителями". Алгоритмы, предназначенные для автоматического выполнения такими вычислителями, называются "программами", и с конца пятидесятых годов формальные способы, используемые для записи программ, называются "языками программирования". (Введение термина "язык" применительно к способам записи программ вызывает смешанные чувства. С одной стороны, оно оказалось весьма полезным, поскольку существующая теория лингвистики обеспечила естественную основу и устоявшуюся терминологию ("грамматика", "синтаксис", "семантика" и т. д.) для рассмотрений применительно к этой новой тематике. С другой стороны, необходимо отметить, что аналогия с (ныне именуемыми так) "естественными языками" часто оказывалась дезориентирующей, так как для естественных языков, неформальных по существу, источником как их слабости, так и их силы является присущая им неопределенность и неточность).

программированию на PL/I можно найти настойчивый совет избегать обращений к процедурам, насколько это возможно, "потому что они делают программу столь неэффективной". В свете того, что процедуры в языке PL/I являются одним из основных средств описания структуры, этот совет выглядит ужасно, настолько ужасно, что вряд ли можно называть упомянутый текст "учебным". Если вы убеждены в полезности понятия процедуры и соприкасаетесь с приложениями, где дополнительные затраты на аппарат процедур обходятся слишком дорого, то порицайте эти неподходящие приложения, а не возводите их на уровень стандартов. Равновесие и в самом деле надлежит восстановить!)