Устройство Дженсена - Jensen's device

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

Описание

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

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

 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]))

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

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

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

GPS

Другой пример - GPS (General Problem Solver), описанный в конфиденциальной информации DE Knuth и JN Merner в ALGOL 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)связано с угловым регистром в спецификации семантики оператора for АЛГОЛА 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)

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

использованная литература

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