Процедурный параметр

В вычислениях — процедурный параметр это параметр процедуры , которая сама является процедурой.

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

особенно эффективен и удобен в языках, поддерживающих функций , таких как Паскаль и современный диалект GNU C. локальные определения Этот инструмент Это тем более актуально, когда замыкания функций доступны . Ту же функциональность (и даже больше) предоставляют объекты в объектно-ориентированных языках программирования , но за значительно более высокую цену.

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

Основная концепция

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

процедура   P  (  f  ):     вернуть   f  (6,3) *  f  (2,1)

При вызове подпрограммы P необходимо передать ей один аргумент, который должен быть некоторой ранее определенной функцией, совместимой с тем, как P использует свой параметр f . Например, если мы определим

процедура   плюс  (  x  ,  y  ):     вернуть   х  +  у

тогда мы можем вызвать P ( plus ), и результат будет плюс (6,3) * плюс (2,1) = (6 + 3) * (2 + 1) = 27. С другой стороны, если мы определим

procedure  quot ( u ,  v ):     return  u / v

тогда вызов P ( quot ) вернет quot (6,3)* quot (2,1) = (6/3)*(2/1) = 4. Наконец, если мы определим

процедура   зла  (  z  )     вернуть  г + 100

тогда вызов P ( evil ) не будет иметь особого смысла и может быть помечен как ошибка.

Синтаксические детали

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

int   P  (  int   (  *  f  ) (  int   a  ,   int   b  ))   {      return   f  (  6  ,  3  )   *   f  (  2  ,  1  );  }

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

Обзор

В языках, допускающих использование процедурных параметров, правила области действия обычно определяются таким образом, что процедурные параметры выполняются в своей собственной области видимости. Точнее, предположим, что функция actf передается в качестве аргумента P в качестве ее процедурного параметра f ; и затем f вызывается изнутри тела P . Пока actf выполняется, он видит среду своего определения. ^{[ нужен пример ]}

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

Пример: универсальная сортировка вставкой

Понятие процедурного параметра лучше всего объяснить на примерах. Типичным применением является следующая общая реализация алгоритма сортировки вставками , которая принимает два целочисленных параметра a , b и два процедурных параметра prec , swap :

процедура   isort  (  a  ,  b  ,  prec  ,  swap  ):     целое число   я  ,  j  ;     я  ←  а  ;     пока   я  ≤  b   делаю          j  ←  i  ;         пока   j  >  a   и   prec  (  j  ,  j  −1)  выполняют              обмен  (  j  ,  j  −1);             j  ←  j  −1;         я  ←  я  +1;

Эту процедуру можно использовать для сортировки элементов от x [ a ] до x [ b ] некоторого массива x произвольного типа в заданном пользователем порядке. Параметры prec и swap должны быть двумя функциями , определяемыми клиентом , каждая из которых принимает два целых числа r , s между a и b . Функция prec должна возвращать true тогда и только тогда, когда данные, хранящиеся в x [ r ], должны предшествовать данным, хранящимся в x [ s ], в порядке, определенном клиентом. Функция swap должна обменивать содержимое x [ r ] и x [ s ] и не возвращать результата.

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

Сортировка чисел с плавающей запятой

Например, мы можем отсортировать массив z из 20 чисел с плавающей запятой, от z [1] до z [20] в порядке возрастания, вызвав isort (1, 20, zprec , zswap ), где функции zprec и zswap определяются как

процедура   zprec  (  r  ,  s  ):     возврат  (  z  [  r  ] <  z  [  s  ]); процедура   zswap  (  r  ,  s  ):     плавать   т  ;     т  ←  z  [  р  ];     z  [  р  ] ←  z  [  s  ];     z  [  s  ] ←  т

Сортировка строк матрицы

В качестве другого примера, пусть M — матрица целых чисел с 10 строками и 20 столбцами с индексами, начинающимися с 1. Следующий код переупорядочит элементы в каждой строке так, чтобы все четные значения предшествовали всем нечетным значениям:

целое число  я процедура   eoprec  (  r  ,  s  ):     return  (  M  [  i  ,  r  ]  mod  2) < (  M  [  i  ,  s  ]  mod  2); процедура   eoswap  (  r  ,  s  ):     целое число   т  ;     т  ←  M  [  я  ,  р  ];     М  [  я  ,  р  ] ←  М  [  я  ,  с  ];     M  [  я  ,  s  ] ←  т  ; для   i  от 1  до  10  делаем      isort  (1, 20, eoprec, eoswap);

Обратите внимание, что эффекты eoprec и eoswap зависят от номера строки i , но процедуре isort не обязательно это знать.

Процедура векторной сортировки

В следующем примере isort используется для определения процедуры vecsort , которая принимает целое число n и целочисленный вектор v с элементами от v [0] до v [ n −1] и сортирует их либо в порядке возрастания, либо в порядке убывания, в зависимости от того, является ли третий параметр incr имеет значение true или false соответственно:

процедура   vecsort  (  n  ,  v  ,  incr  ):     процедура   vprec  (  r  ,  s  ):         если   incr   , то              верните   v  [  r  ] <  v  [  s  ];         иначе              верните   v  [  r  ] >  v  [  s  ];     процедура   vswap  (  r  ,  s  ):         целое число   т  ;         т  ←  v  [  р  ];         v  [  р  ] ←  v  [  s  ];         v  [  s  ] ←  t      isort  (0,  n  −1,  vprec  ,  vswap  );

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

Пример: объединение двух последовательностей

Следующий пример иллюстрирует использование процедурных параметров для обработки абстрактных структур данных независимо от их конкретной реализации. Проблема состоит в том, чтобы объединить две упорядоченные последовательности записей в одну отсортированную последовательность, где характер записей и критерий упорядочения может выбирать клиент. Следующая реализация предполагает только, что на каждую запись можно ссылаться по адресу памяти и существует «нулевой адрес» Λ, который не является адресом какой-либо действительной записи. Клиент должен предоставить адреса A , B первых записей в каждой последовательности и функции prec , next и Append , которые будут описаны позже.

 процедур  слияние  (  A  ,  B  ,  prec  ,  nextA  ,  AppendA  ,  nextB  ,  AppendB  ):     адрес   ini  ,  fin  ,  t      ini  ← Λ;  плавник  ← Λ     в то время как   A  ≠ Λ или  B  ≠ Λ  ,          если   B  = Λ  или  (  A  ≠ Λ  и   B  ≠ Λ  и   prec  (  A  ,  B  ))  то              t  ←  nextA  (  A  )             плавник  ← присоединитьA(  A  ,  плавник  );  если   ini  = Λ  , то   ini  ←  fin              A  ←  t          else              t  ←  nextB  (  B  )             плавник  ←  присоединитьB  (  B  ,  плавник  );  если   ini  = Λ  , то   ini  ←  fin              B  ←  t      вернуть   ini

Функция prec должна принимать адреса r , s двух записей, по одной из каждой последовательности, и возвращать true, если первая запись должна идти раньше другой в выходной последовательности. Функция nextA должна взять адрес записи из первой последовательности и вернуть адрес следующей записи в той же последовательности или Λ, если ее нет. Функция AppendA должна добавить первую запись из последовательности A в выходную последовательность; его аргументами являются адрес A добавляемой записи и адрес fin последней записи выходного списка (или Λ, если этот список еще пуст). Процедура AppendA должна вернуть обновленный адрес последнего элемента выходного списка. Процедуры nextB и AppendB аналогичны для другой входной последовательности.

Объединение связанных списков

Чтобы проиллюстрировать использование общей процедуры слияния, вот код объединения двух простых списков , начиная с узлов по адресам R , S. связанных Здесь мы предполагаем, что каждая запись x содержит целочисленное поле x . INFO и поле адреса x . NEXT , указывающий на следующий узел; где информационные поля расположены в порядке возрастания в каждом списке. Входные списки разбираются при слиянии, а их узлы используются для построения выходного списка.

 процедур  слияние списка  (  R  ,  S  ):     процедура   prec  (  r  ,  s  ):         вернуть   р  .  ИНФОРМАЦИЯ  <  с  .  ИНФО      процедура   следующая  (  x  ):         вернуть   х  .  СЛЕДУЮЩАЯ      процедура   добавления  (  x  ,  fin  )         если   fin  ≠ Λ,  то   fin  .  СЛЕДУЮЩИЙ  ←  x          x  .  СЛЕДУЮЩИЙ  ← Λ         return   x           return   merge  (  R  ,  S  ,  prec  ,  следующий  ,  добавление  ,  следующий  ,  добавление  )

Объединение векторов

Следующий код иллюстрирует независимость общей процедуры слияния от фактического представления последовательностей. Он объединяет элементы двух обычных массивов чисел от U [0] до U [ m -1] и от V [0] до V [ n с плавающей запятой -1] в порядке убывания. Входные массивы не изменяются, а объединенная последовательность значений сохраняется в третьем векторе от W [0] до W [ m + n -1]. Как и в языке программирования C, мы предполагаем, что выражение «& V » дает адрес переменной V , «* p » дает переменную, адрес которой равен значению p , и что «&( X [ i ])» эквивалентно "&( X [0]) + i " для любого массива X и любого целого числа i .

процедура   arraymerge  (  U  ,  m  ,  V  ,  n  ,  W  ):     процедура   prec  (  r  ,  s  ):         вернуть  (*  r  ) > (*  s  )     процедура   следующаяU  (  x  ):         если   x  = &(  U  [  m  −1])  , то   вернуть  Λ  , иначе   вернуть   x  + 1     процедура   nextV  (  x  ):         если   x  = &(  V  [  n  −1])  , то   вернуть  Λ  , иначе   вернуть   x  + 1     процедура   добавления  (  x  ,  fin  )         если   fin  = Λ  , то   fin  ← &(  W  [0])        (*  плавник  ) ← (*  x  )         обратный   плавник  + 1             если   m  = 0, то  U  ← Λ     если   n  = 0, то  V  ← Λ     возврат   слияния  (  U  ,  V  ,  prec  ,  nextU  ,  добавление  ,  nextV  ,  добавление  )

Пример: Определенный интеграл

Интегрирование по интервалу

Следующая процедура вычисляет приблизительный интеграл $\textstyle \int _{a}^{b}$ f ( x ) d x данной действительнозначной функции f в заданном интервале [ a , b ] действительной прямой . В качестве численного метода используется правило трапеций с заданным числом n шагов ; действительные числа аппроксимируются числами с плавающей запятой.

процедура   Intg  (  f  ,  a  ,  b  ,  n  ):     плавать   т  ,  х  ,  с  ;  целое число   i,      если   b  =  a   , то   вернуть  0     х  ←  а  ;  s  ←  ж  (  а  ) / 2;     для  i  от  1  до   n  −1  do          t  ←  i  /(  n  +1);  Икс  ← (1−  т  ) *  а  +  т  *  б  ;         s  ←  s  +  ж  (  Икс  )     s  ←  ж  (  б  ) / 2     возврат  (  б  -  а  ) *  s  /  n

Интеграция через диск

Рассмотрим теперь задачу интегрирования заданной функции $g$ , с двумя аргументами, по диску $D$ с заданным центром ( $xc,yc$ ) и заданный радиус $R$ . Эту задачу можно свести к двум вложенным интегралам с одной переменной путем замены переменных

\int \!\int _{D}g(x,y)\,\mathrm {d} x\,\mathrm {d} y=\int _{0}^{R}z\left(\int _{0}^{2\pi }g({\mathit {xc}}+z\cos t,{\mathit {yc}}+z\sin t)\,\mathrm {d} t\right)\,\mathrm {d} z

Следующий код реализует формулу в правой части :

процедура   DiskIntg  (  g  ,  xc  ,  yc  ,  R  ,  n  )     процедура   gring  (  z  ):         процедура   gpolar  (  t  ):             float   x  ,  y              x  ←  xc  +  z  *  cos  (  t  )             y  ←  yc  +  z  *  sin  (  т  )             вернуть   г  (  х  ,  у  )         целое число   м  ←  круглый  (  n  *  z  /  R  )         вернуть   z  *  Intg  (  gpolar  , 0, 2*π,  m  )     вернуть   Intg  (  gring  , 0,  R  ,  n  )

Этот код использует процедуру интегрирования Intg на двух уровнях. Внешний уровень (последняя строка) использует Intg для вычисления интеграла от $gring(z)$ для $z$ варьируется от 0 до $R$ . Внутренний уровень (предпоследняя строка) определяет $gring(z)$ как линейный интеграл от $g(x,y)$ по кругу с центром $(xc,yc)$ и радиус $z$ .

История

Процедурные параметры были изобретены до эпохи электронных компьютеров математиком Алонзо Чёрчем как часть его лямбда- модели вычислений исчисления.

Процедурные параметры как особенность языка программирования были представлены в АЛГОЛЕ 60 . Фактически, АЛГОЛ 60 имел мощный механизм передачи параметров « вызова по имени », который мог упростить некоторые виды использования процедурных параметров; см. Устройство Дженсена .

Процедурные параметры были важной особенностью языка программирования LISP , который также ввел концепцию закрытия функции или funarg . Язык программирования C позволяет указатели на функции передавать в качестве параметров, которые выполняют одну и ту же задачу, и часто используются в качестве обратных вызовов в программировании, управляемом событиями , и в качестве обработчиков ошибок. Однако лишь немногие современные компиляторы C допускают определения вложенных функций, поэтому другие их применения относительно редки. Процедурные параметры также были предоставлены в Паскале вместе с определениями вложенных процедур; однако, поскольку стандартный Паскаль не допускал раздельной компиляции, эта функция также мало использовалась в этом языке.

См. также