Устройство Дженсена

Устройство Дженсена представляет собой метод компьютерного программирования, использующий вызов по имени . Его разработал датский ученый-компьютерщик Йорн Йенсен , который работал с Питером Науром в Regnecentralen . Они работали над компилятором GIER ALGOL , одной из первых правильных реализаций ALGOL 60 . Алгол 60 использовал вызов по имени. Во время своей речи на премии Тьюринга Наур упоминает свою работу с Дженсеном над GIER ALGOL.

Описание

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

Классическим примером устройства Дженсена является процедура, вычисляющая сумму ряда: $\textstyle \sum _{k=\ell }^{u}a_{k}$:

 real procedure Sum(k, l, u, ak)
      value l, u;
      integer k, l, u;
      real ak;
      comment k and ak are passed by name;
   begin
      real s;
      s := 0;
      for k := l step 1 until u do
         s := s + ak;
      Sum := s
   end;

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

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

 Sum(i, 1, 100, V[i]).

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

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

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

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

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

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

GPS

Другим примером является GPS (общее средство решения проблем), описанное в секретной книге Д. Е. Кнута и Дж. Н. Мернера «АЛГОЛ 60» .

real procedure GPS(I, N, Z, V); real I, N, Z, V;
   begin for I := 1 step 1 until N do Z := V; GPS := 1 end;

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

I := GPS(I, if I=0 then -1.0 else I, P, if I=1 then 1.0 else
   if GPS(A, I, Z, if A=1 then 1.0 else
      if entier(A)×(entier(I)÷entier(A))=entier(I) ∧ A<I
      then 0.0 else Z) = Z then
      (if P<m then P+1 else I×GPS(A, 1.0, I, -1.0)) else P)

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

Критика

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

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

procedure swap(a, b)
  integer a, b;
  begin
    integer temp;
    temp := a;
    a := b;
    b := temp;
  end;

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

 temp := i;
 i := A[i];
 A[i] := temp;

Проблема в том, что второе назначение меняется. i, поэтому A[i] в третьем присваивании, вероятно, будет не тот же элемент массива, что и в начале. Если бы, с другой стороны, процедура была закодирована наоборот (с b сохранением в temp вместо a ), тогда результатом было бы желаемое действие, если только оно не было вызвано как swap(A[i],i). (Более безопасный swap() сделал бы temp1 := a; temp2 := b; a := temp2; b := temp1;.)

См. также

• Стек вызовов , кадр стека, статическая ссылка и отображение (закрытие, включая ссылку на среду)
• Устройство Даффа
• Проблема Funarg : как передавать и возвращать функции как значения
• Тест мужчины или мальчика , тест окружающей среды

Внешние ссылки

• Стандартная семантика без хранения для блочной структуры в стиле ALGOL и вызова по имени