EWD: Процессы Подстановки

Привет, Хабр! Представляю вашему вниманию перевод статьи Substitution Processes (1962 год) авторства Эдсгера Дейкстры. Разделение на параграфы не оригинальное.

Введение

Машина определяет (по самой своей структуре) язык, а именно: свой язык ввода — и напротив, семантическое определение языка задаёт машину, способную понимать его. Другими словами, машина и язык — это две стороны одной и той же медали. Я собираюсь описать такую медаль. Я оставляю на вас решение того, какой же из этих двух аспектов предмета моего разговора, на ваш взгляд, самый важный, так как сам считаю этот выбор довольно смешным. Язык, наброски которого я собираюсь вам предоставить, является непозволительно трудным для человека, а машина, которую я собираюсь описать, является порочно неэффективной.

Поэтому, если моя ментальная конструкция, тем не менее, имеет право на существование, его оправдание должно быть найдено в других качествах. Найти их в моей машине можно, по моему мнению и суждению, по крайней мере в её исключительной простоте и элегантности, в единообразии способов, которыми она выполняет довольно разные (на первый взгляд) операции; оправдание моего языка — это его ясность и необычайно высокая степень двусмысленности, вытекающая из строгой последовательной интерпретации и явного указания в программе выполняемых операций, хотя обычно выполнение всех операций подразумевается (и из этого проистекают некоторые недоразумения). Если кто-то захочет, он может считать мои машину и язык придуманными в образовательных целях.

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

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

Числа и арифметика

Моя машина управляет (и управляема) единицами информации, которые я называю словами. Без потери общности я могу ограничится конечным числом разных слов, каждое из которых представлено одинаковым количеством бит.

Машина различает разные типы слов, например числа, операторы, переменные и разделители. Сейчас мы остановимся на первых из них: «словах-числах» и «словах-операторах».

Нормальная арифметическая операция, например сложение или умножение двух чисел, содержит два числовых слова в качестве входных данных и одно слово, также представляющее из себя число, в качестве вывода. Правила, ставящие в соответствие числовым значениям числовые слова (например, полученные из битов), воплощаются в работе арифметического устройства, которое имеет привычное свойство того, что эти же правила применяются как к вводу, так и к выходу: выход арифметического устройства можно снова ввести в него в последующих стадиях работы. Поскольку мы предполагаем, что свойства арифметического устройства постоянны во времени, мы можем сказать, что числовые слова имеют «фиксированное значение». Поскольку фиксированная интерпретация числовых слов связана с постоянными свойствами арифметического устройства, не удивительно, что мы будем обозначать основные арифметические операции операторными словами («+», «-», «*», «/», и т. д.), смысл которых также можно считать фиксированным.

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

Рассмотрим выражение, которое обычно записывается как:

	5  +  39 / (7  +  2 * 3)  -  6

в обычной постфиксной нотации (также известной под названием «Обратная Польская Нотация») это приведет к следующей последовательности чисел и операторов (соседние элементы в этой последовательности для читаемого представления на бумаге разделены пробелами):

	5 39 7 2 3 * + / + 6 -

Хорошо известен механизм, специально разработанный для последовательного вычисления подобных выражения — это то, что я предпочитаю назвать «стек». (Это устройство было изобретено и обобщено независимо многими людьми, из-за чего известно сейчас под большим разнообразием имен, таких как «push down list», «nesting store», «cellar», «last-in-first-out-memory» и т. д.) Если мы рассмотрим приведенную выше последовательность чисел и операторов как строку слов, представляющую часть программы, машина читает эту строку слово за словом слева направо. Если она встречает числовое слово, это число (т. е. копия этого числового слова) добавляется на вершину стека, если она встречает операторное слово, соответствующая операция выполняется на вершине стека. В иллюстрации, приведённой ниже в строках указаны последовательные состояния верхней части стека, а сама вершина находятся в правой части строки:

	...	5
	...	5	39
	...	5	39	7
	...	5	39	7	2
	...	5	39	7	2	3
	...	5	39	7	6
	...	5	39	13
	...	5	3
	...	8
	...	8	6
	...	2

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

Вычисления и подстановки

Как ясно показано в приведенном выше примере, машина начинает с копирования текста программы слова за словом в верхнюю часть стека. Рано или поздно это нужно прервать, иначе наша машина будет просто копирующей машиной. В вышеупомянутой системе процесс копирования прерывается появлением произвольного оператора в тексте программы. Таким образом, функция оператора является двойной: во-первых, он показывает, что копирование должно прерваться, потому что сейчас нужно выполнить операцию, во-вторых, он задает эту операцию. Я предлагаю отделить эти две совершенно разные функции: отныне арифметические операторы в основном обрабатываются точно так же, как обрабатываются числа, т. е. Слово оператора также копируется в стек. Каждый раз, когда процесс копирования должен быть прерван, я укажу это в программе явно путем вставки специального слова, введенного с этого момента и обозначаемого «E» (от «Evaluate» — вычислить). Теперь моя машина имеет следующий вид: она читает текст программы слово за словом слева направо, где под «чтением» понимается следующее: если прочитанное слово не равно «E», его копия добавляется в стек, если это слово равно «E», оно не копируется, а вместо этого происходит выполнение операции, обозначенной (первоначально) верхним словом стека.

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

	5 39 7 2 3 * E + E / E + E 6 - E

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

	...	5
	...	5	39
	...	5	39	7
	...	5	39	7	2
	...	5	39	7	2	3
	...	5	39	7	2	3	* 
	...	5	39	7	6
	...	5	39	7	6   +
	...	5	39	13
	...	5	39	13	/
	...	5	3
	...	5	3	+
	...	8
	...	8	6
	...	8	6	–
	...	2

Как показано выше, машина выполняет операцию, обозначенную верхним словом стека, когда она считывает слово «E» в тексте программы. Мы ограничимся такими программами, что в момент после считывания слова «E» верхнее слово стека действительно является операторным словом (а не, например, числовым словом). Кроме того, мы ограничимся случаем, когда слова расположенные непосредственно за оператором соответствуют любым требованиям, выдвигаемым этим оператором. (Например, в случае двоичных арифметических операций, описанных выше, два слова непосредственно за оператором должны быть числами.)

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

Вычисления с переменными

Мы рассматриваем замену выражения или подвыражения на его численное значение как «подстановку», и мы явно указываем, когда эти подстановки должны выполняться, хотя это излишне — «3 + 4» всегда будет равным «7», независимо от того, когда мы выполним это сложение.

Однако, ситуация радикально меняется, как только переменные (в контрасте с постоянными числами) вступают в дело. (Ниже мы будем обозначать переменные малыми буквами, резервируя заглавные буквы для «специальных слов», таких как «Е» и другие, которые будут введены позднее.) Предположим, что нам нужно вычислить значение выражения:

	x + 4

в момент, когда значение переменной х равно 3. Это означает, что в приведенном выше выражении мы должны подставить вместо «х» его числовое значение в момент вычисления; только после этого мы можем выполнить арифметическую замену («3 + 4» заменить на «7»). Из чего-то, зависящего от «x» (т. е. выражения «x + 4»), мы получаем результат (т. е. «7»), не зависящий от будущих изменений «x», так как мы заменили «x» на его значение при выполнении подстановки. Мы создали «мгновенный снимок» переменной «x». Очевидно, я настаиваю на том, чтобы явным образом указывать, когда нужно создать этот мгновенный снимок переменной «x» (которая меняется во времени!).

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

	x + 4

теперь имеет следующий вид:

	x E 4 + E

и, в соответствии с вышеприведенными предположениями, последовательность состояний стека такова:

	...	x
	...	3
	...	3	4
	...	3	4	+
	...	7

Наша машина предлагает нам описать тот факт, что «значение переменной x равно 3» в несколько других формулировках, а именно: что состояние процесса выполнения программы таково, что чтение слова «E» в тот момент, когда верхнее слово стека есть «x», приводит к замене этого верхнего слова на числовое слово «3». Таким образом, переменная в верхней части стека рассматривается как оператор этой переменной, который в процессе вычисления заменяется чем-то, зависящим от состояния процесса выполнения программы в этот момент; такой «оператор-переменная» выполняется без установки особых требований к лежащим непосредственно за ним словам стека. (Сходство между операторами и переменными будет дополнительно подчеркнуто нашим следующим примером.)

Промежуточные вычисления

Все слова, прочитанные в тексте программы, добавляются в стек, за исключением слова «E», которое заставляет машину выполнять подстановку. По причинам, которые будут объяснены ниже, мы хотели бы также иметь возможность добавить слово «E» в стек. Однако рамки для этого расширения уже присутствуют. Введем специальный оператор, обозначаемый словом «P» (от «Postponement» — отсрочка), который выполняется в ходе вычислений путём фиксированной подстановки, т. е. он заменяется словом «Е». Мы проиллюстрируем использование оператора «P» в следующем примере.

В этом примере мы имеем три переменные с именами «x», «y» и «plinus» (от «plus-minus» — плюс-минус). Предположим, что состояние процесса выполнения программы таково, что чтение «plinus E» генерирует слово «+» на вершине стека. При чтении текста:

	x P E y P E plinus E P E

верхняя часть стека будет иметь последовательность состояний:

	...	x
	...	x	P
	...	x	E
	...	x	E	y
	...	x	E	y	P
	...	x	E	y	E
	...	x	E	y	E	plinus
	...	x	E	y	E	+
	...	x	E	y	E	+	P
	...	x	E	y	E	+	E

и верхняя часть стека, таким образом, содержит строку слов, которая, будучи прочитанна как часть программы, выполнит вычисление выражения «x + y». Если бы значение переменной «plinus» было бы «-», мы бы сгенерировали выражение «x - y» (т. е. строку слов, которая, будучи в качестве части программы, выполнит вычисление этого выражения).

То, что мы произвели, есть промежуточное вычисление выражения «x plinus y», результатом которого снова является выражением. В наших предыдущих примерах окончательное действие со стеком всегда оставляло одно число. Число является тривиальным примером выражения, потому порождение не только чисел, но и более общих выражений в виде промежуточных результатов, является очевидным продолжением обычной практики.

Изменения переменных

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

Для присвоения значения одному слову, как в «x := 3», мы могли бы написать в нашей программе:

	3 x := E

результирующее в состояния верхушки стека:

	...	3
	...	3	x
	...	3	x	:=

Во время выполнения оператора присваивания «:=» машина исследует лежащее непосредственно за ним слово. Это должна быть переменная, к которой должно быть применено присвоение; следующее за ним слово присваивается этой переменной (подробнее об этом ниже), а три слова вверху стека (которые сейчас обрабатываются) удаляются из стека. До последующего присвоения (т. е. нового присвоения переменной «x») вычисление этой переменной приведет к замене верхнего слова стека словом «3».

Строковые присвоения

С точностью до положения левой и правой стороны это близко аналогичному утверждению присваивания, используемому в ALGOL 60. Однако, нам мало присвоения значения только из одного слова, нам необходимо присвоение значения из строки слов, и поэтому мы должны иметь возможность указывать, насколько глубоко в стек вытягивается присваиваемое значение. Самый простой способ сделать это — вставить в стек маркер, например, специальное слово «Т» (от «Terminal» — конец) после последнего слова присваиваемого значения. Кроме того, мы вводим другой оператор присваивания «:-» (называемый «присвоением строки» ​​в отличие от «присвоения слова», представленного в предыдущем абзаце). Во время выполнения этого оператора машина исследует верхнюю часть стека в нисходящем направлении. Первое слово (сразу под оператором «:-») должно быть переменной, которой должно быть присвоено значение. После этого машина продолжает свое пословное исследование вниз, пока оно не встретит специальный маркер «Т»: слова, переданные таким образом, образуют вместе строку, которая воспринимается как присваиваемое значение.

Самый простой способ добавить «Т» в стек — просто вставить слово «Т» в нужное место в программе, под управлением которой заполняется стек. Однако так мы делать не будем; по причинам, которые будут объяснены позже, нам нужна возможность генерировать «Т» поверх стека под управлением программы, которая сама не содержит этого слова. Мы можем сделать это с помощью того же трюка, который позволил нам создать «E» поверх стека. Введем новый оператор, обозначаемый словом «S» (скажем, от «Separator» — разделитель, или просто потому, что «S» предшествует «T» в алфавите), который в ходе выполнения заменяется словом «T», и мы установим правило, что это единственный способ добавления слов «Т» в стек.

Используя всё это, у нас есть альтернативная запись оператора присваивания «x := 3», а именно:

	S E 3 x :- E

дающее последовательность состояний верхней части стека:

	...	S
	...	T
	...	T	3
	...	T	3	x
	...	T	3	x	:-

Результат этого эквивалентен предыдущей форме, использовавшей присвоение слов «:=».

Сохранения промежуточных вычислений в строки

Давайте используем более мощное присвоение в примере, который является расширением одного из наших ранних, а именно: того, что описывает промежуточное вычисление выражения «x plinus y». Результатом этого промежуточного вычисления было выражение, зависящее от переменных «x» и «y», и, предположим, что мы хотим назвать это выражение «z». Для этого напишем в программе:

	S E x P E y P E plinus E P E z :- E

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

	...	T	x	E	y	E	+	E	z	:-

и после выполнения этого оператора вышеуказанные слова будут удалены из стека, включая слово «T» включительно. До последующего присвоения вычисление переменной «z» будет означать выполнение («чтение») назначенной ему строки. В ходе вычисления переменной «z» машина должна иметь доступ к первому слову этой строки; однако, когда она начинает читать эту строку, она также должна знать где последнее слово этой строки. Мы предполагаем, что оператор присваивания учитывает это, добавляя снова маркер конца, и для этой цели мы можем использовать одно и то же слово «Т». В ходе вычисления переменной «z» назначенная ей строка будет считана частью программы слева направо до тех пор, пока не будет встречен маркер конца «T». Новая ситуация, связанная с последним присвоением, может быть легко представлена:

	z → x E y E + E T

Точно так же наши предыдущие задания:

	3 x := E

	S E 3 x :- E

будут способствовать возникновению ситуации, представляемой так:

	x → 3 T

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

Замечания к текущим наработкам

О двойственности присвоений и считываний

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

Наконец, стек зарезервирован для «анонимных промежуточных результатов», тогда как читаемый текст, в принципе и по крайней мере, всегда «назван», потому что мы создаем его, присваивая его переменной.

О рекурсии

Внимательный читатель заметил, что наряду с представлением значения переменной мы молчаливо ввели еще два изменения в нашей машине.

Первая — появление слова «Т» в тексте программы и «немедленная реакция» машины на него — относительно проста. По нашим договорённостям, слово «Т», прочитанное в тексте, не копируется в верх стека! Вместо этого оно заставляет машину продолжать чтение до того слова-переменной, что стоит сразу перед оператором «E», который вызвал это вычисление рассматриваемой переменной. Другими словами, он действует как «return» (возврат) в конце закрытой подпрограммы.

Но вычисление переменной может потребовать вычислений других переменных (включая саму себя): практическое определение вычисления переменной в основном является рекурсивным, а механизм, необходимо сопутствующий рекурсивному определению — это… еще один стек! Я называю этот второй стек «стеком активаций» в отличие от первого, который я называю «анонимным стеком». Одной из функций стека активаций является контроль процесса чтения. Когда начинается вычисление переменной, стек активаций заполняется, а когда считывается соответствующее слово «Т», оно уменьшается до прежнего размера. (В обычной терминологии машинной структуры: стек активаций содержит стек значений счетчика заказов, его верхний элемент — по определению счетчик текущего заказа; в той же терминологии его старые элементы действуют как стек, содержащий адреса возврата.)

Замечание. Мы могли бы попытаться объединить наши два стека в один. Это слияние происходит совершенно естественным образом, если они должны расширяться и сжиматься синхронно друг с другом. В общем, однако, это не так, и попытка объединить эти два стека в один даст весьма неестественную конструкцию.

Понятие идентификатора

Мы будем использовать стек активаций для еще одной цели, чтобы удовлетворить очень фундаментальную потребность, а именно: создание новых переменных. Выше я использовал специальные слова («x», «y», «plinus» и т. д.) для обозначения переменных, и я тщательно избегал использовать термин «идентификатор». Я использовал термин «переменная» в обозначении единственного и уникального объекта, существующего в течение некоторого периода времени и способного последовательно принимать разные значения. Это понятие переменной следует тщательно отличать от «идентификатора», используемого в ALGOL 60, потому что один и тот же идентификатор может использоваться для указания на множество объектов, на большое количество различных переменных.

Прежде всего, мы заметим тот факт, что один и тот же идентификатор может играть разные роли благодаря тому, что он встречается в более чем одном объявлении. Затем лексикографическим правилом можно определить, какое из этих объявлений в каком случае применять, для всех использований указанного идентификатора. Эта форма многократного использования одного и того же идентификатора может быть удалена простым процессом переименования.

Но есть гораздо более тонкий случай «многократного использования одного и того же идентификатора», а именно: как только определенный блок возникает в одной или нескольких вложенных активациях (как в случае рекурсивной процедуры). Другими словами: один и тот же идентификатор иногда ссылается на эту переменную, иногда на другую.

Использование идентификаторов

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

Для удобства (точнее: удобства для машины, а не для гипотетического пользователя) я намерен использовать те же идентификаторы для локальных переменных каждой активации. (То, что я называю «активацией», близко аналогичным блоку или процедуре, используемым ALGOL 60.) Я использую для этой цели специальные идентификационные слова «L0», «L1», «L2» и т. д.

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

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

Процедуры

Теперь мы можем рассмотреть более сложный пример. Пусть значения переменных «x», «y» и «complus» (от «complex-plus» — комплексный плюс) будут представлены следующим образом:

	x → 10 23 T

	y → 5 -2 T

	complus → L0 E := E
		L1 E := E
		L2 E := E
		L1 E E + E
		L1 E E L0 E E + E
		T

если мы сейчас прочтем текст:

	S E x E y E complus E z :- E

конечный результат будет заключаться в том, что мы можем представить новое значение «z»:

	z → 15 21 T

и то, что мы сделали, можно интерпретировать как сложение двух комплексных чисел.

В терминологии ALGOL: «complus» — это процедура с четырьмя численными параметрами, все вызываемые по значению. Простая структура процесса позволяет первым из них оставаться анонимным даже в теле процедуры. Кроме того, это своего рода «процедура с типом», то есть принимающая и возвращающая, синтаксически говоря, одно значение некоего типа вместо двух примитивов.

Замечание о произвольности примитивов

Позвольте мне закончить тривиальным примером. Предположим, что мы хотим написать «plus» вместо «+». Присвоение:

	S E + P E plus :- E

приводит к возникновению ситуации:

	plus → + E T

тогда выражения:

	x E y E plus E

	x E y E + E

полностью эквивалентны. Этот пример включен, чтобы как можно яснее показать произвольность наших примитивов.

Заключение

Я полностью осознаю, что приведённые тут наработки определенно неполные. Особо важно введение условного оператора и некоторого эквивалента «goto», если уж вы захотите создать полноценную систему из этого. На данный момент я не разбираю их, и я делаю это по двум причинам. Во-первых, ради краткости, а во-вторых, потому что я еще не решил: я знаю несколько возможных способов, но ни один из них меня полностью не удовлетворяет.

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

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

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

Наконец, язык, описанный в этом отчете (или язык, разработанный аналогичным образом), может оказаться подходящим средством для формализации семантического определения алгебраического языка. Отсутствие такого строгого семантического определения является одним из признанных недостатков официального «Отчета об Алгоритмическом Языке ALGOL 60» и, увидев огромную проблему, вызванную этим дефектом, я искренне надеюсь, что этот отчет поможет избежать этой ошибки в следующий раз, когда будет разрабатываться алгоритмический язык.

Выражение признательности

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