Устройство Дженсенса - Википедия - Jensens Device

Устройство Дженсена это метод компьютерного программирования, использующий позвонить по имени. Это было разработано Датский специалист в области информатики Йорн Йенсен, который работал с Питер Наур в Regnecentralen. Они работали над GIER АЛГОЛ компилятор, одна из первых правильных реализаций АЛГОЛ 60. АЛГОЛ 60 использовал вызов по имени.[1][2][3] Во время своей речи на Премии Тьюринга Наур упоминает о своей работе с Дженсеном над GIER ALGOL.

Описание

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

Классическим примером устройства Дженсена является процедура, вычисляющая сумму ряда, :[4][5][6]

 реальная процедура Сумма (k, l, u, ak) ценить л, у; целое число к, л, и; настоящий ак; комментарий k и ak передаются по имени; начинать      настоящий s; s: = 0; за k: = l шаг 1 до того как ты делать         s: = s + ak; Сумма: = s конец;

В процедуре индексная переменная k и срок суммирования ак передаются по имени. Вызов по имени позволяет процедуре изменять значение индексной переменной во время выполнения за петля. Вызов по имени также вызывает ак аргумент, который будет переоцениваться на каждой итерации цикла. Обычно ак будет зависеть от изменения (с побочным эффектом) k.

Например, код для вычисления суммы первых 100 членов реального массива V [] было бы:

 Сумма (i, 1, 100, V [i]).

Во время исполнения Сумма, фактический аргумент я будет увеличиваться на каждом шаге за цикл, и каждая оценка процедуры ак будет использовать текущее значение я для доступа к последовательным элементам массива V [i].

Устройство Дженсена является общим. Двойное суммирование может быть выполнено как:

 Sum (i, l, m, Sum (j, l, n, A [i, j]))

В Сумма function может использоваться для произвольных функций, просто используя соответствующие выражения. Если бы требовалась сумма целых чисел, выражение было бы просто Sum (i, 1,100, i);, если сумма квадратов целых чисел, то Сумма (я, 1,100, я * я);, и так далее.[7] Небольшое изменение было бы подходящим для начала численного интегрирования выражения методом, очень похожим на метод Сумма.

Оценка ак реализуется с помощью thunk, который по сути является подпрограммой с окружением. Преобразователь - это закрытие без аргументов. Каждый раз, когда процедуре требуется значение ее формального аргумента, она просто вызывает преобразователь. Преобразователь оценивает фактический аргумент в области действия вызывающего кода (а не в области действия процедуры).

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

GPS

Другой пример - GPS (General Problem Solver), описанный в D. E. Knuth и J. N. Merner. АЛГОЛ 60 конфиденциально.[8]

настоящий процедура GPS (I, N, Z, V); настоящий I, N, Z, V; начинать за I: = 1 шаг 1 до того как N делать Z: = V; GPS: = 1 конец;

Ниже приведен единственный оператор, который находит m-е простое число с помощью GPS.

I: = GPS (I, если I = 0 тогда -1.0 еще Я, П, если I = 1 тогда 1.0 еще   если GPS (A, I, Z, если А = 1 тогда 1.0 еще      если entier (A) × (entier (I) ÷ entier (A)) = entier (I) ∧ A тогда 0.0 еще Z) = Z тогда      (если P тогда П + 1 еще I × GPS (A, 1.0, I, -1.0)) еще П)

(Примечание: в исходной статье выражение в конце GPS (A, 1.0. I, 0.0), из-за углового случая в спецификации семантики АЛГОЛА 60-х за утверждение.)

Критика

Устройство Дженсена использует вызов по имени, но вызов по имени неуловим и имеет некоторые проблемы. Следовательно, вызов по имени недоступен на большинстве языков. Кнут отмечает, что АЛГОЛ 60 не может выражать приращение (n) процедура, увеличивающая свой аргумент на единицу; звонок приращение (A [i]) не выполняет ожидаемого действия, если я это функционал, который меняется при каждом доступе.[9] Кнут говорит: «Использование средств определения« макросов »для расширения языка вместо того, чтобы полагаться исключительно на процедуры для этой цели, приводит к более удовлетворительной работе программы».

Другие указывают на то, что процедура вызова по имени, меняющая местами аргумент, может иметь небольшие проблемы.[10] Очевидная процедура замены:

своп процедур (а, б) целое число a, b;  начинать    целочисленная температура;    темп: = а; а: = b; b: = темп; конец;

Процедура работает правильно для многих аргументов, но вызов своп (i, A [i]) проблематично. Использование правила копирования приводит к назначению:

 темп: = я; я: = А [я]; A [i]: = temp;

Проблема заключается во втором изменении задания я, Итак A [i] в третьем назначении, вероятно, не будет того же элемента массива, что и в начале. Если, с другой стороны, процедура должна быть закодирована наоборот (с б сохраняется в темп вместо а), то желаемое действие будет результатом, если оно не будет вызвано как своп (A [i], i)

Смотрите также

Рекомендации

  1. ^ Наур, Питер (2005). Видео лекции Питера Наура. ACM Awards. Дания: Ассоциация вычислительной техники. Получено 2020-09-11.
  2. ^ Дэвид (1 марта 2006 г.). «Пионер программного обеспечения Питер Наур получил премию Тьюринга ACM». Публичная политика ACM. Ассоциация вычислительной техники. Получено 2020-09-11.
  3. ^ "ACM: Стипендиаты: Питер Наур, почетный профессор Копенгагенского университета, цитирование". 2005. Архивировано с оригинал на 2008-02-12. Получено 2020-09-21.
  4. ^ МакЛеннан, Брюс Дж. (1987). Принципы языков программирования: проектирование, оценка и реализация (Второе изд.). Холт, Райнхарт и Уинстон. С. 141–142. ISBN  0-03-005163-0.
  5. ^ Дейкстра, Э. В. (Ноябрь 1961 г.). «Защита АЛГОЛА 60 (письмо в редакцию)». Коммуникации ACM. 4 (11): 502–503. Дои:10.1145/366813.366844.
  6. ^ Кнут, Д. Э. (Октябрь 1967). «Остающиеся проблемы в АЛГОЛе 60». Коммуникации ACM. 10 (10): 611–617. Дои:10.1145/363717.363743.
  7. ^ Сумма требует настоящий аргумент для термина, поэтому предполагается преобразование типа.
  8. ^ Дональд Э. Кнут и Джек Н. Мернер. 1961. АЛГОЛ 60 конфиденциально. Commun. ACM 4, 6 (июнь 1961 г.), 268-272. DOI = 10.1145 / 366573.366599 doi.acm.org
  9. ^ Кнут 1967, п. 613. Например, инкремент (A [инкремент (j)]) будет увеличиваться j дважды.
  10. ^ Макленнан 1987

внешняя ссылка