original

ПРОЦЕСИ ЗАМІЩЕННЯ

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

(Попередня публікація.)

Rekenafdeling
Stichting “Mathematisch Centrum”
2de Boerhaavestraat 49
AMSTERDAM
Нідерланди

ПРОЦЕСИ ЗАМІЩЕННЯ

Машина визначає (самою своєю структурою) мову, а саме свою вхідну мову: навпаки, семантичне визначення мови визначає машину, яка її розуміє. Іншими словами: машина і мова – це дві грані однієї і тієї ж монети. Я збираюся описати таку монету. Я залишаю вам повністю вирішувати, який із цих двох аспектів теми моєї доповіді ви вважаєте найважливішим, оскільки це досить смішно в обох аспектах. Мова, яку я збираюся намалювати, надзвичайно складна для людини, а машина, яку я збираюся описати, є збоченою і неефективною.

Тому, якщо моя ментальна конструкція все ж має право на існування, вона повинна виводити це з інших якостей. Моя машина отримує це, принаймні на мій смак і судження, з її надзвичайної простоти та елегантності, з однорідного способу, яким вона виконує свої (на перший погляд) досить різні операції; виправданням моєї мови є її чіткість і надзвичайно високий ступінь однозначності, що випливає з суворої послідовної інтерпретації та явного вказівки в програмі на виконання операцій, які зазвичай неявно розуміються (і тому схильні до непорозуміння). Якщо хтось захоче це зробити, він може вважати мою машину та мою мову задуманими з метою роз’яснення. 

Перш ніж розпочати свій опис, я хотів би попередити вас про два навмисних упущення. Система, яку я збираюся представити, є результатом ретельного вибору між великою кількістю «сусідніх можливостей». Я не буду пояснювати свої мотиви цих виборів, я навіть залишу свідомо відкинуті альтернативи без згадок. Інакше кажучи, я утримуюся від впровадження своєї системи хоча б у деяких аспектах як, скажімо, «місцевий оптимум». Оскільки це зменшує переконливість мого викладу, я особисто шкодую про цю помилку. Однак для стислості я мушу опустити ці мотиви.

Інше питання, яке я не торкаюся, це питання, як реалізувати цю систему за допомогою звичайної машини. Можна навіть поставити питання — як я це зробив, щоб перевірити, чи не думаю нісенітниць, — чи можна це взагалі реалізувати, як би грубо не було. Ви повинні повірити мені на слово, що це можна зробити. Я розробив метод реалізації до такої міри, який міг би переконати, на мою думку, самого підозрілого аудитора в такій можливості. Але я маю намір не показувати вам подробиці цієї реалізації, тому що мені довелося включити занадто багато довільних рішень, у яких, якщо їх згадувати, вони лише відволікали б увагу від основного. Зокрема, залишиться недоторканим питання розподілу сховища.

Моя машина оперує (і контролює) одиниці інформації, які я називаю «словами». Без втрати загальності я можу обмежитися кінцевою кількістю різних слів, кожне представлене однаковою кількістю бітів.

Машина розрізняє різні види слів, скажімо, числа, оператори, змінні та роздільники. Поки що ми обмежимося першим із них, «слів-число» та «слів-операторів».

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

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

Розглянемо вираз, який зазвичай записують як

      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» (від «Оцінити»). Тепер моя машина набуває такого вигляду. Він читає текст програми слово за словом, зліва направо. Під «читанням» мається на увазі наступне: якщо слово read не дорівнює «E», його копія додається до стека, якщо прочитане слово дорівнює «E», воно не копіюється, а замість цього виконується операція відбувається так, як зазначено (в основному) верхнім словом стека.читання» мається на увазі наступне: якщо слово read не дорівнює «E», його копія додається до стека, якщо слово read дорівнює «E», воно не копіюється, а натомість виконується операція як зазначено (в першу чергу) верхнім словом стеку.читання» мається на увазі наступне: якщо слово read не дорівнює «E», його копія додається до стека, якщо слово read дорівнює «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” в тексті програми. Ми обмежимося такими програмами, що в такий момент верхнє слово стеку дійсно є словом оператора (а не, наприклад, числовим словом). Крім того, ми обмежимося випадком, коли слова стека, що знаходяться безпосередньо в основі, відповідають будь-яким вимогам, які може встановити виконання оператора зверху. (Наприклад, у випадку двійкових арифметичних операцій, проілюстрованих вище, два слова, що лежать безпосередньо в основі, мають бути числами.)

Іншими словами: якщо операнд арифметичної операції виявляється виразом, ми підставляємо цей вираз його числовим значенням до того, як операція буде викликана в дію, апелюючи таким чином до того, що, в першу чергу, арифметичні операції визначаються лише тоді, коли подається числові операнди.

Ми розглядаємо заміну (під)виразу його числовим значенням як «підстановку», і ми чітко вказуємо, коли ці заміни мають бути виконані, хоча, кажучи лінгвістично, це досить багато: «3 + 4» завжди буде рівним до “7”, незалежно від того, коли ми виконуємо це додавання.

Однак ця ситуація докорінно змінюється, як тільки змінні — на відміну від постійних чисел — беруться до уваги. (Далі ми будемо позначати змінні малими літерами, залишивши великі літери для «особливих слів», таких як «E» та інших, які будуть введені нижче.) Припустимо, що нам потрібно обчислити значення виразу

     ”   х + 4 “

у момент, коли значення змінної x дорівнює 3. Це означає, що у наведеному вище виразі ми повинні замінити ” x ” на його числове значення в цей момент; тільки після цього ми можемо виконати арифметичну заміну (“3+4” замінюється на “7”). Беручи під увагу те , в залежності від ї (тобто вираз «  х +4″) ми створюємо результат ( а саме “7») , який, завдяки тому , що ми замінюють х його поточної вартості, проводиться в залежать від майбутнього історія x . Ми зафіксували «миттєву картинку» змінної x .Очевидно, я наполягаю на тому, щоб чітко вказати, коли це миттєве зображення змінноїx (який змінюється в часі!) потрібно взяти.

Зараз ми збираємося збирати перші плоди нашої праці, бо механізм цього явного вказівки вже запроваджено. Частина програми, що приписує оцінку виразу

     ”   х + 4 “

тепер приймає такий вигляд:

     ”   x    E 4 + E “

і за наведеного вище припущення наступні зображення стека є

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

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

Усі слова, прочитані в тексті, додаються до стека, за винятком слова “E”, яке змушує машина виконувати заміну. Щоб пояснити нижче, ми хотіли б також мати можливість додати слово “E” до стека. Однак структура для цього розширення вже є. Ми вводимо спеціальний оператор, позначений словом «P» (від «Відкладення»), який впливає на оцінку на фіксовану заміну, vis. його заміна словом «Е». Ми проілюструємо використання оператора «P» у наступному прикладі.

У цьому прикладі ми маємо три змінні з іменами ” x “, ” y ” і ” plinus “. Припустимо, що стан процесу такий, що читання « 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
…. .    х    Е    у    Й plinus
…..    х    Е    у    Е +
…..    х    Е    у    Е + Р
…..    х    Е    у    Е + Е

і верх стека, таким чином, містить рядок слів, які, коли читаються як частина програми, виконають оцінку виразу ” x + y “. Якби значення змінної ” plinus ” було б “–”, ми б згенерували (рядок слів, що відповідає) вираз ” x – y “.

Те, що ми зробили, зводиться до часткової оцінки виразу « x plinus y », результатом знову є вираз. У наших попередніх прикладах остаточне додавання до стека завжди складалося з одного числа. Але число є тривіальним прикладом виразу, тому генерування не тільки чисел, а й більш загальних виразів як проміжних результатів є очевидним розширенням звичайної практики.

До цих пір ми описували генерацію слів на вершині стека, але не описували те, що ми збираємося робити з цими словами. Крім того, ми припустили, що стосовно даної змінної процес може перебувати в такому стані, що оцінка цієї змінної призведе до попередньо визначеної заміни, але як це визначення має відбуватися, не згадується вище. Ці два прогалини в нашій картині будуть заповнені введенням операторів присвоєння.

Для присвоєння значення одному слову, як у ” x := 3 “, ми могли б написати в нашій програмі

      ” 3   x   := E “

в результаті у стопку зображень:

….. 3
….. 3    х
….. 3    х    :=

Після оцінки оператора присвоєння “:=” машина досліджує безпосередньо основне слово. Це має бути змінна, якій має відбутися присвоєння; наступне базове слово призначається цій змінній (процес, про який докладніше нижче), а три слова вгорі стека (які зараз оброблені) видаляються зі стека. До подальшого повідомлення — тобто нове присвоєння змінній « x » — оцінка цієї змінної призведе до заміни верхнього слова стеку словом «3».

Але для заміни лівої та правої сторони це дуже схоже на оператор присвоєння, відомий в ALGOL 60. Але нам потрібно більше, оскільки, загалом, присвоєне значення буде складатися не з одного слова, а з рядок слів, і тому ми повинні мати засіб, щоб вказати, наскільки глибоко в стеку поширюється призначене значення. Найпростіший спосіб зробити це – вставити в стек маркер, сказати спеціальне слово “T” (від “Terminal”) у нижній частині призначеного значення. Крім того, ми вводимо інший оператор присвоєння «:-» (так званий «призначення рядка» на відміну від «призначення слова», введеного в попередньому абзаці). Після оцінки цього оператора машина досліджує верх стопки в напрямку вниз.Перше слово (відразу під оператором “:-“) має бути змінною, якій потрібно призначити значення. Після цього машина продовжує дослідження слово за словом у напрямку вниз, поки не зустріне спеціальний маркер «T»: слова, передані таким чином, утворюють разом рядок, який діє як присвоєне значення.

Найпростішим способом додати “T” до стека було б просто вставити слово “T” у потрібне місце в програмі, під керуванням якої стек заповнюється. Однак така домовленість не підійде; з причин, які будуть пояснені пізніше, нам потрібна можливість генерувати “T” у верхній частині стека під керуванням програми, яка сама не містить цього слова. Ми можемо зробити це за допомогою того самого трюку, який дозволив нам створити букву «E» у верхній частині стека. Ми вводимо новий оператор, позначений словом “S” (скажімо, від “Роздільник” або тому, що він стоїть перед “T” в алфавіті), який при оцінці замінюється словом “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    :-

і після виконання цього завдання вищезазначені слова будуть вилучені зі стека, слово «Т» включно. До подальшого повідомлення оцінка змінної ” z ” означатиме виконання (“читання”) рядка, призначеного їй. Отже, після оцінки змінної ” z ” машина повинна мати доступ до першого слова цього рядка; однак, коли він починає читати цей рядок, він повинен виявити останнє слово цього рядка. Ми пропонуємо, щоб оператор присвоєння переконався в цьому, знову додавши маркер кінця, і для цієї мети ми можемо використовувати те саме слово “T”. Після оцінки змінної ” z” рядок, призначений для нього, буде читатися як частина програми зліва направо, поки не зустрінеться кінцевий маркер “T”. Нову ситуацію, що виникає в результаті останнього присвоєння, можна зручно представити так:

      ”    z    →    x    E    y    E + E T ” .

Точно так само наші попередні завдання

      ” 3    x    := E ” або ” S E 3    x    :- E “

обидва призведе до ситуації, яку представляють

      ”    x    → 3 T ” .

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

Крім того, ми хотіли б звернути увагу на певну форму подвійності між завданням, з одного боку, і читанням тексту, з іншого. Коли машина зчитує фрагмент тексту програми, верхня частина стека заповнюється під контролем цього програмного тексту. У присвоєнні «читабельний текст» створюється під керуванням вмісту стека. Подвійність також можна проілюструвати, беручи до уваги вимоги до доступності. Слова в стеку повинні бути доступні лише в напрямку зверху вниз. Однак якщо оператор присвоєння перетворює верхню частину стека в текст, який можна читати, то послідовні слова стають доступними в іншому напрямку.

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

Уважний читач помітив, що, поряд із представленням значення змінної, ми мовчки ввели ще дві складності в нашу машину.

По-перше, наявність слова «T» у тексті програми та «негайна реакція» машини на нього є відносно простим. Як ми описували організацію, слово «T», коли читається в тексті, не копіюється вгору стека! Натомість це змушує машину продовжувати читання з першого слова, наступного в рядку після “E”, що викликало оцінку відповідної змінної. Іншими словами, він діє як «Повернення» в кінці закритої підпрограми.

Але оцінка змінної може вимагати оцінки інших змінних (навіть для оцінки її самої): прагматичне визначення оцінки змінної в основному є рекурсивним, а механізми, необхідні для виконання рекурсивного визначення, є… … ще одна стопка! Я називаю цей другий стек «стеком активацій», на відміну від першого, який я називаю «анонімним стеком». Однією з функцій стека активацій є контроль процесу читання. Коли починається оцінка змінної, стек активацій розширюється, коли читається відповідне слово “T”, воно зменшується до свого попереднього розміру. (У звичайній термінології машинної структури: стек активацій містить стек «значень лічильника замовлень», його верхній елемент за визначенням є «поточний лічильник замовлень»; за тією ж термінологією його старі елементи діють як стек, що містить «адреси повернення».)

Примітка . Ми могли б спробувати об’єднати наші два стека в один. Це злиття проявилося б цілком природним чином, якщо вони будуть розширюватися і стискатися «в фазі» один з одним. Загалом, однак, це не так, і спроба об’єднати два стека в один дасть дуже неприродну конструкцію.

Ми будемо використовувати стек активацій для ще однієї мети, щоб задовольнити дуже фундаментальну потребу, а саме. створення нових змінних. У наведеному вище я використовував спеціальні слова (” x “, ” y “, ” plinus ” тощо) для позначення змінних і ретельно уникав використання терміну “ідентифікатор”. Я використовував термін “змінна” у зв’язку з одним, унікальним об’єктом, який існує протягом певного періоду часу і здатний набирати різні значення послідовно. Цю концепцію змінної слід ретельно відрізняти від «ідентифікатора», який використовується в ALGOL 60, оскільки один і той самий ідентифікатор може використовуватися для вказівки на безліч об’єктів, на велику кількість різних змінних.

Перш за все, ми зустрічаємо той факт, що один і той самий ідентифікатор може грати різні ролі завдяки тому, що він зустрічається в більш ніж одній декларації. Потім лексикографічне правило вказує нам, яке з цих декларацій застосовується всюди, де може використовуватися відповідний ідентифікатор. Цю форму багаторазового використання одного і того ж ідентифікатора можна було б видалити за допомогою простого процесу перейменування.

Але є набагато більш тонкий випадок «множинного використання одного й того самого ідентифікатора», а саме. як тільки певний блок виникає в одній або кількох вкладених активаціях (як у випадку рекурсивної процедури). Іншими словами: один і той самий ідентифікатор потім посилається іноді на цю змінну, іноді на іншу.

Фактично: ідентифікатор позначає змінну, і щоб чітко вказати, для якої змінної він позначається, я маю намір чітко позначити момент, коли змінна повинна бути замінена ідентифікатором.

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

Якщо машина починає оцінку змінної, стек активацій збільшується на один елемент. На початку цей пункт також містить примітку, що до цього моменту в цій активації не було введено жодних локальних змінних.

Якщо машина читає слово “E” в той момент, коли верхня частина анонімного стеку містить одне із слів ідентифікатора (скажімо, “L2”), то вона досліджує верхній елемент стеку активацій. Якщо цей ідентифікатор має бути оцінений під час поточної активації вперше, машина створює для нього нову змінну (і може дати цій змінній порожнє значення) і робить у наймолодшому елементі стека активацій примітку до цього ефект. Потім він замінює верхнє слово анонімного стеку змінною, щойно створеною для нього. При наступній оцінці того самого ідентифікатора в той момент, коли та сама активація все ще (або знову) є поточною,машина знаходить у верхньому елементі стека активацій записку, залишену там під час першого оцінювання цього ідентифікатора, і верхнє слово стеку замінюється тією ж змінною.

Тепер ми можемо показати більш складний приклад. Нехай значення змінних ” x “, ” y ” і ” complus ” мають вигляд :

 ”    x    → 10 23 T “

 ”    y    → 5 –2 T “

”    complus    → L0 E := E

                L1 E := E

                L2 E := E

                L1 E E + E

                L2 E E L0 E E + E

                Т “.

Якщо ми зараз прочитаємо текст

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

чистий ефект буде полягати в тому, що ми можемо представити нове значення ” z ” за допомогою:

      ”    z    → 15 21 T “

і те, що ми зробили, можна інтерпретувати як додавання двох комплексних чисел.

У термінології ALGOL: “complus” – це процедура з чотирма числовими параметрами, які викликаються за значенням. Проста структура процесу дозволяє першому з них залишатися анонімним навіть у тілі процедури. Крім того, це свого роду «процедура типу», будь то така, яка, синтаксично кажучи, займає місце двох первинних.

Дозвольте закінчити тривіальним прикладом. Припустимо, що ми хочемо написати «плюс» замість «+». Після виконання завдання

       ” S E + P E плюс :- E “

що породжує ситуацію

       ” плюс → + E T “

вирази

      ”    x    E    y    E плюс E”

та

      ”    x    E    y    E + E”

є повністю еквівалентними. Цей приклад наведено, щоб якомога чіткіше показати довільність наших примітивів.

Висновок .

Я повністю усвідомлюю, що ескіз точно неповний. Особливо умовна реакція та деякий еквівалент оператору go to повинні бути включені, якщо хтось бажає створити з цього систему. На даний момент я залишаю їх і роблю це з двох причин. По-перше, для стислості, а по-друге, тому що я ще не визначився: я знаю кілька можливих способів, але жоден з них мене повністю не задовольняє.

З деякими версіями цих засобів я зробив трохи більш складні програми. Вони показали мені як силу, так і слабкість моєї мови, її сила — її гнучкість і однозначність, її слабкість — те, що розумне використання її виявилося набагато вище, принаймні, моїх можливостей.

Якщо все-таки я вимагаю уваги для цього проекту, я не роблю цього лише тому, що він зачаровує мене, а може й інших. Цей звіт є конденсацією моїх медитацій після того, як ми завершили впровадження ALGOL 60. Ця реалізація була задумана з високою швидкістю, і основним виправданням численних рішень, прийнятих у ці неспокійні місяці, було визнання того, що наші задумані конструкції приведуть до нашої мети. і виконував би роботу, так чи інакше. Однак машина, описана в цьому звіті, являє собою крайній безперервний спектр можливих реалізацій алгоритмічної мови, яка (як у випадку з ALGOL 60) забезпечує рекурсивність. У цій якості особисто для мене дуже зрозуміло:це дуже допомогло мені оцінити різні (спочатку відключені) прийоми, які ми інтуїтивно включили, і це чітко показало нам ряд альтернативних рішень. Тому виправдовується надія, що конструкція перекладача та конструювання машин у майбутньому виграють від цих міркувань.

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

Нарешті, мова, описана в цій доповіді (або мова, розроблена за аналогічним принципом), може виявитися підходящим засобом для формалізації семантичного визначення алгебраїчної мови. Відсутність такого суворого семантичного визначення є одним із визнаних недоліків офіційного «Звіту про алгоритмічну мову ALGOL 60», і, бачачи величезну кількість проблем, викликаних цим дефектом, я щиро сподіваюся, що цей звіт сприятиме намагатися уникнути цієї помилки наступного разу, коли буде розроблена алгоритмічна мова.

Подяки .

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

Транскрипція Кена Дайка.
Остання редакція на Пн, 17 грудня 2007 р .