О чем умолчал Мур. (Дейкстра, 1962).

Перейти вниз

О чем умолчал Мур. (Дейкстра, 1962).

Сообщение автор Gudleifr в Вт Авг 29, 2017 2:17 pm

Книга Мура 1970 года - ТЕМА #3, АБЗАЦ #222 - так и не ответила на самый главный для меня вопрос: откуда взялись идеи, лежащие в основе устройства FORTH? Некоторых компьютерных баек тех времен и здравых (и местами замечательных) идей хватило только на первые две главы. В третьей главе, вдруг, откуда ни возьмись, является FORTH сразу во всей своей красе. Сам Мур, понимая, что здесь у него образовался пробел, долго извиняется необходимостью забежать вперед и зациклить изложение. Однако, и после этого продолжает всерьез обсуждать только частности, хотя, иногда, и изящно реализованные. Автор, правда, еще в некоторых местах пытается рассуждать задним числом, но довольно бессвязно.
***

ПОПЫТКА УНИФИКАЦИИ ПОНЯТИЙ, ОТНОСЯЩИХСЯ К ПОСЛЕДОВАТЕЛЬНОМУ ВЫПОЛНЕНИЮ ПРОГРАММЫ
Е.W.Dijkstra.
An attempt to unify the constituent concepts of serial program execution.
Symbol languages in data processing.
Proceedings of the Symposium in Rome, 1962, p.237.
Gordon and Breach, 1962.
Переводчик Т.А.Шаргина.

Машина самой своей структурой определяет язык, а именно свой входной язык; наоборот, семантическое определение языка определяет машину, которая понимает его. Другими словами, машина и язык являются двумя сторонами одной медали. Я предоставляю читателю самому решить, какой из этих двух аспектов, составляющих содержание моей статьи, он считает наиболее важным. Язык, набросок которого мы собираемся дать, чрезвычайно труден для пользователя-человека, а машина, которую мы собираемся описать, чрезвычайно неэффективна.
Поэтому если предложенная здесь воображаемая конструкция все же имеет право на существование, то этим она обязана другим своим качествам. Эта машина получает такое право, по-моему, благодаря крайней простоте и изяществу, единообразию, с которым она выполняет довольно различные (на первый взгляд) операции. Оправданием для нашего языка является его гибкость и необычно высокая степень определенности (недвусмысленности), достигаемая благодаря строго последовательной интерпретации и тому, что в программе есть явные указания о выполнении операций, которые обычно неявно подразумеваются (и поэтому часто понимаются превратно). Читатель может считать, что наша машина и язык задуманы для уяснения смысла алгоритмов.
Прежде чем начать свое описание, мне хотелось бы предупредить читателя о том, что мы намеренно оставляем в стороне два вопроса. Система, которую мы собираемся предложить, является результатом тщательного отбора из большого числа возможностей. Мы не будем приводить мотивы, которыми руководствовались во время этого отбора; более того, даже не будем упоминать о сознательно отвергнутых альтернативах. Другими словами, мы не собираемся представлять читателю свою систему как некий "локальный оптимум". Поскольку это ослабляет силу убеждения статьи, мы сожалеем об этом, но для краткости должны опустить мотивировки.
Другой вопрос, которым мы оставляем в стороне, это вопрос о реализации этой системы с помощью обычной машины. Читатель может задать вопрос (как сделал я с целью убедиться, что то, о чем я думаю, не является чепухой), может ли она быть реализована вообще, хотя бы в общих чертах. Следует положиться на мое слово, что это может быть сделано. Нами разработан метод реализации столь детально, что знакомство с ним могло бы убедить в возможности такой реализации самого придирчивого читателя. Однако мы не хотим знакомить читателя с деталями этой реализации, так как нам пришлось принять при ее разработке слишком много субъективных решений, которые, если упомянуть о них, отвлекут пониманне от существа дела. В частности, остается незатронутым вопрос о распределении памяти.
Моя машина оперирует (и управление ею осуществляется) с единицами информации, которые я называю "словами". Не теряя общности, можно ограничить себя определенным числом различных слов; эти слова состоят из одинакового числа двоичных разрядов. Машина умеет различать слова различного вида, например числа, операции, переменные и разделители. Пока мы ограничимся словами первых двух типов, а именно "словами-числами" и "словами-операциями".
Обычная арифметическая операция, скажем сложение или умножение двух чисел, имеет два слова-числа на входе и одно слово, также изображающее число, на выходе. Правила, согласно которым численное значение сопоставляется со словом-числом (т.е. извлекается из двоичных разрядов слова-числа), воплощены в арифметическом устройстве. Оно обладает обычным свойством, заключающимся и том, что как к вводимой, так и к выводимой информации применимы одинаковые правила: информация, полученная на выходе арифметического устройства, может быть введена в него снова на некоторой более поздней стадии процесса. Так как мы предполагаем, что свойства арифметического устройства не изменяются со временем, можно сказать, что слова-числа имеют фиксированное значение. Наряду с тем, что свойства арифметического устройства неизменны, интерпретация слова-числа также неизменна, поэтому не будет удивительным, если мы обозначим основные арифметические операции словами-операциями (+, -, *, / и т.д.), значения которых также могут рассматриваться как постоянные.
Работой машины управляет программа, которая состоит, вообще говоря, из цепочки слов. Пока ограничимся теми кусками программы, в которых описывается вычисление арифметических выражений.
Рассмотрим выражение, имеющее в обычной форме записи следующий вид:

Код:
5 + 39 / (7 + 2 * 3) - 6

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

Код:
5 39 7 2 3 * + / + 6 -

Устройство, специально изобретенное для того, чтобы с его помощью можно было последовательно вычислять такие выражения, я называю "стеком". Это устройство было изобретено и введено в употребление многими людьми независимо друг от друга, поэтому оно называется по-разному в литературе (например, "продвигающийся вниз список", "гнездовая память", "погреб", "память, из которой записанное последним выбирается первым", и т.д.). Будем считать, что приведенная последовательность чисел и операций является цепочкой слов, представляющей собой кусок программы; машина будет читать такую цепочку слово за словом слева направо. Если машина читает слово-число, это число (т.е. копия этого слова-числа) засылается в верхнюю ячейку стека, если машина читает слово-операцию, рассматриваемая операция выполняется над числами, находящимися в двух самых верхних ячейках стека. В приводимой иллюстрации последовательные строки представляют собой последовательные картины верхних ячеек стека, причем верхняя ячейка стека расположена справа:

Код:
..... 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 - вычислить).
Моя машина принимает теперь следующий вид. Она читает текст программы слово за словом слева направо. Под "чтением" понимается следующее: если прочитанное слово не равно Е, копия этого слова записывается в стек; если прочитанное слово равно Е, оно в стек не переписывается, а вместо этого выполняется операция, а какая именно - определено (вообще говоря) самым верхним словом стека.
В соответствии с этими правилами программа вычисления выражения, приведенного в предыдущем примере, будет теперь состоять из следующей цепочки слов:

Код:
5 39 7 2 3 * E + E / E + E 6 - Е

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

Код:
..... 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

Как сказано раньше, машина выполняет операцию, определенную верхним словом стека, в момент, когда она читает слово Е из программного текста. Мы ограничимся программами, для которых в такой момент верхнее слово в стеке действительно является словом-операцией (а не словом-числом, например). Мы также ограничимся случаем, когда слова в стеке, идущие сразу же за верхним словом, удовлетворяют всем требованиям, которые должны быть выполнены для того, чтобы могла быть выполнена операция, находящаяся в верхней ячейке стека. (Например, в рассмотренном случае арифметических операций над двоичными числами два слова, идущие сразу же за верхним словом, должны быть числами).
Другими словами, если операнд арифметической операции является выражением, мы подставляем численное значение этого выражении прежде, чем выполнять операцию; тем самым мы учитываем, что арифметические операции, вообще говоря, определены лишь тогда, когда имеются числовые операнды.
Мы рассматриваем замену выражения (или подвыражения) его числовым значением как "подстановку" и указываем, когда эти подстановки должны быть выполнены, хотя с точки зрения лингвистики это излишне: 3 + 4 будет всегда равно 7 независимо от того, когда мы выполняем это сложение.
Однако положение коренным образом меняется, как только мы переходим к рассмотрению переменных. (Будем обозначать переменные строчными буквами; заглавные буквы резервируются для "специальных слов", таких, как E, и других, которые будут введены позже). Допустим, что нам нужно вычислить значение выражения

Код:
x + 4

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

Код:
x + 4

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

Код:
x E 4 + E

При сделанных нами предположениях последовательные состояния стека будут следующими:

Код:
..... x
 ..... 3
 ..... 3 4
 ..... 3 4 +
 ..... 7

Наша машина побуждает нас описать факт, что "значение переменной x = 3", другими словами, а именно: состояние процесса таково, что чтение слова E в момент, когда верхнее слово в стеке есть x, вызывает замещение этого верхнего слова словом-числом 3. Таким образом, переменная, находящаяся в верхней ячейке стека, рассматривается как переменная операция, которая при вычислении замещается чем-то зависящим от состояния процесса в этот момент; в этом случае мы имеем операцию, выполнение которой не накладывает никаких специальных требований на слова в стеке, идущие сразу же вслед за ней. (Сходство между операциями и переменными будет хорошо видно в приводимом ниже примере).
Машина засылает в стек все слова текста, которые она читает, за исключением слова E, которое заставляет машину выполнять подстановку. По причине, о которой мы скажем дальше, нам хотелось бы также иметь возможность засылать в стек слово Е. Фундамент для этого уже заложен. Мы вводим специальную операцию, обозначаемую словом P (от слова Postponement - отсрочка), которая выполняет при вычислении специальную подстановку, а именно подстановку вместо себя слова E. Мы покажем, как используется операция P в приводимом примере.
В этом примере имеются три переменные: x, y и plinus. Предположим, состояние процесса таково, что после того, как машина прочитала слово plinus, чтение идущего далее слова E вызывает замещение слова plinus в верхней ячейке стека словом +.
По мере чтения текста

Код:
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.
С точностью до перестановки левой и правой частей то, что мы получили, совершенно аналогично оператору присваивания в АЛГОЛе 60. Однако нам этого недостаточно, так как, вообще говоря, присваиваемое значение будет состоять не из одного слова, а нз цепочки слов; поэтому мы должны иметь средства для указания о том, насколько глубоко простирается в глубь стека присваиваемое значение. Самый простой способ - это заслать в стек перед присваиваемым значением какой-нибудь маркер, скажем специальное слово T (от слова Terminal - конечный). Кроме того, мы вводим другую операцию присваивания :- (называемую "присваивание цепочки" в противоположность "присваиванию слова", о котором шла речь в предыдущем абзаце). Во время выполнения этой операции машина исследует верхнюю часть стека в направлении сверху вниз. Первое слово в стеке (идущее сразу же после операции :-) должно быть переменной, которой присваивается значение. После нахождения этого слова машина продолжает исследовать в стеке слово за словом в направлении сверху вниз ло тех пор, пока ей не встретится специальный маркер T; слова, пройденные во время этого исследования, составляют цепочку, которая берется в качестве присваиваемого значения.
Самый простой способ заслать T в стек - это просто вставить слово T в соответствующее место программы, управляющей заполнением стека. Однако мы этого делать не будем. По причинам, которые будут объяснены позже, нам нужно иметь возможность получать T в верхней ячейке стека с помощью программы, не содержащей T. Мы можем сделать это с помощью того же приема, который позволил нам получать Е в верхней ячейке стека. Мы вводим новую операцию, обозначаемую словом S (скажем, от слова разделитель (separator) или потому, что S в алфавите предшествует T); во время вычисления слово S замещается словом T, и мы будем считать, что это единственный способ, с помощью которого слова T засылаются в стек.
Учитывая сказанное, мы можем записать оператор присваивания х := 3 другим способом, а именно:

Код:
S Е 3 x :- Е

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

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

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

Код:
S E x P E y P E plinus E P E z :- Е

Перед чтением последнего Е стек будет иметь следующий вид (при тех же предположениях относительно значения plinus):

Код:
..... T x E y E + E z :-

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

Код:
z -> x Е y Е + Е Т

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

Код:
3 x := E или S E 3 x :- E

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

Код:
x -> 3 T

Наиболее поражающей стороной такого написания является то, что при таком написании обычное различие между "числами" и "командами" полностью исчезает. Значение переменной определяется как кусок программы, вычисление этой переменной означает выполнение этого куска программы.
Кроме того, нам хотелось бы обратить внимание читателя на некоторую двойственность присваивания, с одной стороны, и чтения текста, с другой. Когда машина читает кусок программного текста, верхняя часть стека заполняется под управлением этого программного текста. При присваивании под управлением содержимого стека возникает "читабельный" текст. Двойственность проявляется также в вопросе о доступности слов в стеке. Слова в стеке должны быть доступны в направлении сверху вниз. Однако, если оператор присваивания превращает содержимое верхней части стека в читабельный текст, последовательность слов становится доступной в другом направлении.
И, наконец, стек резервируется для безымянных промежуточных результатов, а читабельный текст (по крайней мере в принципе) всегда имеет "наименование", так как мы получаем его, присваивая его переменной.
Внимательный читатель заметит, что для представления значения переменной мы молчаливо ввели в нашу машину еще два усложнения. Первое заключается в том, что в программном тексте встречается слово T, и машина знает, как с ним обращаться; это усложнение относительно простое. Из описания вычисления переменной следует, что слово T, прочитанное из текста, наверх стека не переписывается. Вместо этого оно заставляет машину продолжать чтение, начиная со слова, первого в цепочке после слова E, вызвавшего вычисление данной переменной. Другими словами, оно играет роль "возврата" в конце обособленной подпрограммы.
Однако для вычисления переменной может потребоваться вычислить другие переменные (даже вычислить себя): прагматическое определение вычисления переменной является в своей основе рекурсивным; устройство, необходимое для того, чтобы следовать рекурсивному определению,- это... другой стек! Я называю этот второй стек стеком активаций в противоположность первому "безымянному" стеку. Одна из функций стека активаций состоит в том, чтобы управлять процессом чтения. Когда начинается вычисление переменной, стек активаций расширяется, когда читается соответствующее T, он сокращается до своего предыдущего объема. (Используя обычную машинную терминологию, можно сказать, что стек активаций содержит стек "значений счетчика команд", причем его верхний элемент является по определению счетчиком, указывающим на команду, выполняемую в настоящее время. Используя ту же терминологию, скажем, что предыдущие элементы стека активаций играют роль стека, содержащего адреса возвратов).
Замечание. Мы могли попытаться объединить наши два стека в один. Это объединение было бы естественным, если бы эти два стека расширялись и сокращались синхронно. В общем случае, однако, это не так, и попытка объединить два стека в одни привела бы к довольно неестественной конструкции.
Мы будем использовать стек активаций еше для другой важной цели - для получения новых переменных. Раньше для обозначения переменных мы использовали специальные слова (х, у, plinus и т.д.) и тщательно избегали использования термина "идентификатор". Я использовал термин "переменная" по отношению к единичному единственному в своем роде объекту, существующему в течение некоторого периода времени и могущему последовательно принимать различные значения. Следует различать это понятие переменной и понятие "идентификатора" в АЛГОЛе 60, так как один и тот же идентификатор может быть использован для обозначения множества объектов, для обозначения большого числа различных переменных.
Прежде всего мы обнаруживаем следующее: один и тот же идентификатор может играть различную роль из-за того, что он встречается более чем в одном описании. В этом случае лексикографическое правило говорит нам, какое из этих описаний применяется везде, где используется данный идентификатор. Этот случай многократного использования одного и того же идентификатора можно обойти с помощью простого процесса переименовывания.
Однако имеется более тонкий случай "многократного использования одного и того же идентификатора", а именно когда некоторый блок находится в одной или в нескольких вложенных активациях (как в случае рекурсивной процедуры). В подобных случаях один и тот же идентификатор отсылает иногда к одной переменной, иногда к другой.
По существу идентификатор употребляется для обозначения переменной и для того, чтобы указать, какую переменную он обозначает, я намереваюсь явно указывать момент, когда переменная должна быть подставлена вместо идентификатора.
Для удобства (машины, а не гипотетического пользователя) мы намерены использовать для локализованных переменных каждой активации одни и те же идентификаторы. (То, что мы называем "активаця", совершенно аналогично блоку или телу процедуры в АЛГОЛе 60). Мы используем для этого специальные слова-идентификаторы L0, L1, L2 и т.д.
Когда машина начинает вычислять переменную, стек активаций увеличивается на одну запись. Вначале эта запись содержит отметку о том, что пока в нашей активации нет ни одной локализованной переменной.
Если машина читает слово E в момент, когда в верхней ячейке безымянного стека находится одно из слов-идентификаторов (скажем, L2), то она исследует верхнюю запись стека активаций. Если наш идентификатор должен быть вычислен в данной активации впервые, машина вырабатывает для этого идентификатора новую переменную (и может не дать этой переменной никакого значения) и делает в самой последней по времени записи стека активаций отметку об этом. Затем она заменяет верхнее слово безымянного стека только что полученной переменной. При следующем вычислении того же самого идентификатора в момент, когда все еще (или снова) рассматривается та же самая активация, машина находит в верхней записи стека активаций отметку, сделанную при первом вычислении данного идентификатора, н верхнее слово безымянного стека заменяется той же самой переменной.
Теперь приведем более сложный пример. Пусть значения переменных х, у и complus будут следующими:

Код:
x -> 10 23 T
 y ->  5 -2 T
 complus -> L0 E := Е
 L1 E := E
 L2 E := E
 L1 E E + E
 L2 E E L0 E E + E
 T

В результате чтения текста

Код:
S Е x Е y E complus E z :- E

новое значение z будет следующим:

Код:
z -> 15 21 T

и то, что мы сделали, можно интерпретировать как сложение двух комплексных чисел.
В терминологии АЛГОЛа complus есть процедура с четырьмя числовыми параметрами-значениями (by value). Простая структура процесса позволяет первому из этих четырех параметров остаться безымянным даже в теле процедуры. К тому же это один из видов процедуры-функции - процедуры, которая, синтаксически говоря, заменяет два первичных выражения.
Закончим тривиальным примером. Предположим, что мы хотим написать plus вместо +. После присваивания

Код:
S Е + P Е plus :- Е

которое дает

Код:
plus -> + E T

выражения

Код:
x E y E plus E

и

Код:
x E y E + E

совершенно эквивалентны. Этот пример включен для того, чтобы показать возможно яснее произвольность наших первичных символов.
ЗАКЛЮЧЕНИЕ. Мы отдаем себе полный отчет в том, что набросок системы явно не завершен. Чтобы сделать законченную систему, прежде всего следует добавить реакцию на условие и некий эквивалент оператора перехода. Пока я оставляю все это в стороне по двум причинам: во-первых, для краткости и, во-вторых, потому, что мы не приняли еще окончательного решения - нам известно несколько возможных путей, но ни один из них полностью не удовлетворяет нас.
Экспериментируя, я написал более сложные программы. Они показали как силу, так и слабость языка; силой языка является его гибкость и недвусмысленность; слабость заключается в том, что, как говорит разум, его использование лежит за пределами наших сил.
Если все-таки я прошу обратить внимание на этот проект, то делаю это не только потому, что он нравится мне и может с таким же успехом понравиться другим. Это сообщение является конденсацией моих размышлений после того, как мы завершили нашу реализацию АЛГОЛа 60. Мы обдумали эту реализацию очень быстро, и главным оправданием для многочисленных решений, принятых в те месяцы, было сознание, что задуманная нами конструкция так или иначе приведет к цели и будет работать. Однако машина, описанная в данном сообщении, представляет собой крайность и непрерывном спектре возможмых реализаций алгоритмического языка, который (как в случае АЛГОЛа 60) допускает рекурсивность. Благодаря этому своему качеству она очень полезна для меня лично, так как раскрывает существо дела: она очень помогла при оценке различных (первоначально не связанных) приемов, которые мы использовали интуитивно, и ясно указала нам на число возможных решений. Поэтому есть все основания надеяться, что при конструировании транслятора и проектировании машины можно будет извлечь пользу из наших соображений.
Кроме того, машина, о которой говорится в статье, до такой степени неэффективна, что каждая реализация фактического алгоритмического языка, вероятно, может рассматриваться как ее оптимизация, возможная благодаря некоторым ограничениям языка.
Может оказаться полезным сравнивать предлагаемый язык с нашим языком; во время процесса конструирования языка он может помочь своевременно обнаружить "дорогие детали".
Включать или нет такую "дорогую деталь" в проектируемый язык - это дело автора языка; независимо от этого нужно хорошо представлять себе "стоимость" таких деталей.
В заключение скажем, что язык, описанный в сообщении (или язык аналогичный этому), является удобным средством для формализации семантического определения алгебраического языка. Отсутствие такого строгого семантического определения является одним из признанных недостатков официального "Сообщения об алгоритмическом языке АЛГОЛ 60", и, зная, сколько затруднений вызывается этим дефектом, надеюсь, что данное сообщение внесет свой вклад в усилия, направленные на то, чтобы избежать этой ошибки в следующий раз, когда будет изобретаться новый алгоритмический язык.


Последний раз редактировалось: Gudleifr (Чт Мар 08, 2018 1:34 pm), всего редактировалось 6 раз(а)
avatar
Gudleifr
Admin

Сообщения : 944
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: О чем умолчал Мур. (Дейкстра, 1962).

Сообщение автор Gudleifr в Пт Сен 01, 2017 10:31 am

Интересно почитать отклики на эту статью. Роднит их всех одно: "Не читал, но не одобряю":
Работа Дейкстры интересна тем, что полностью посвящена формализации стекового промежуточного представления. Однако, с практической точки зрения его исследования не сообщают нам чего-то нового. Например, он рассуждает о "словах" разных типов, помещающихся в ячейки памяти единого размера. Но такая аппаратная система на момент написания статьи уже существовала, только в B5000 "слова" назывались "слогами", а размер их был 12 бит. Да и в целом в архитектуре B5000 воплотилось многое из того, о чем Дейкстра лишь довольно туманно рассуждал.
С точки зрения теории, работа Дейкстры явно не доведена до логического завершения. Действительно, заманчиво использовать стековую машину (о дуализме языка и машины Дейкстра хорошо сказал в начале своего текста) для вывода операционной семантики формализуемого языка программирования. Вот пример формальной семантики для языка <...> Думаю, если бы придуманный (и продуманный!) стековый язык использовался в таком же духе для описания формальной семантики подмножества Алгол, то работа Дейкстры от этого бы сильно выиграла.
В первоисточнике An attempt to unify the constituent concepts of serial program execution Дейкстра пишет об обратной польской записи, стеке. Ну так в то время прорабатывалась теория компиляции, и многие авторы писали на эту тему. Стек и обратная польская запись активно использовались при промежуточном представлении программы при компиляции с языков высокого уровня (Дейсктра пишет об Алголе) в машинный код. И никто (в том числе и Дейкстра) не предлагал сделать эту промежуточное представление (постфиксную нотацию) языком высокого уровня. Читайте внимательно статью. Дейкстра писал компиляторы с Алгола, но не создавал языков программирования с описанной в его статье нотацией. И, конечно же, Дейкстра ничего не пишет в 1962 году о Форте и Муре.
А если еще добавить факт, что Дейкстра долгое время был почетным сотрудником в фирме Burroughs, становится понятно, для кого на самом деле была написана упомянутая выше статья о стековых вычислениях. Ну а народная молва быстро дополнила недостающие детали, и вот вам - Товарищ   Сталин   разработал  положение о постоянно действующих факторах товарищ Дейкстра придумал столь нужный народу Forth.

Мне это напомнило мнение о А.П.Чехове одного из современных "писателей":
Чехов был человеком крайне недалекого ума, вряд ли стоит всерьез воспринимать его высказывания.
Если не понимаете, почему я так о нем отзываюсь - загуглите, как Чехов за копейки продал права на свои произведения, которые были написаны и будут написаны в течение двадцати последующих лет, книгоиздателю Адольфу Марксу, потому что ему в жопе зудело дачу достроить... А в итоге тех денег все равно на достройку не хватило.
avatar
Gudleifr
Admin

Сообщения : 944
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Вернуться к началу


 
Права доступа к этому форуму:
Вы не можете отвечать на сообщения