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

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

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

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

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

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

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

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

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

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

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

процедура  quot ( u , v ): возврат  u / v

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

процедура  зло ( z ) возвращает 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 наконец-то будет выполнен, записи активации , в которых находятся его переменные окружения, могут оказаться произвольно глубоко в стеке. Это так называемая проблема downwards funarg .

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

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

процедура  isort ( a , b , prec , swap ): integer  i , j ; i ← a ; пока  i ≤ b  do  j ← i ; пока  j > a  и  prec ( j , j −1) do  swap ( j , j −1); j ← j −1; i ← i +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 ): return ( z [ r ] < z [ s ]);процедура  zswap ( r , s ): float  t ; t ← z [ r ]; z [ r ] ← z [ s ]; z [ s ] ← t

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

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

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

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

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

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

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

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

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

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

процедура  merge ( A , B , prec , nextA , appendA , nextB , appendB ): адрес  ini , fin , t  ini ← Λ; fin ← Λ пока  A ≠ Λ или B ≠ Λ сделать  если  B = Λ или ( A ≠ Λ и  B ≠ Λ и  prec ( A , B )) тогда  t ← nextA ( A ) fin ← appendA( A , fin ); если  ini = Λ тогда  ini ← fin  A ← t  иначе  t ← nextB ( B ) fin ← appendB ( B , fin ); если  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 , которое указывает на следующий узел; где поля info расположены в порядке возрастания в каждом списке. Входные списки разбираются слиянием, и их узлы используются для построения выходного списка.

процедура  listmerge ( R , S ): процедура  prec ( r , s ): возврат  r . ИНФОРМАЦИЯ < s . ИНФОРМАЦИЯ процедура  следующая ( x ): возврат  x . ДАЛЕЕ процедура  добавления ( x , fin ) если  fin ≠ Λ , то  fin.NEXT ← x x.NEXT ← Λ вернуть x    обратное  слияние ( R , S , prec , next , append , next , append )

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

Следующий код иллюстрирует независимость процедуры слияния generic от фактического представления последовательностей. Он объединяет элементы двух обычных массивов 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 ) процедура  nextU ( x ): если  x = &( U [ m −1]) , то  вернуть Λ , иначе  вернуть  x + 1 процедура  nextV ( x ): если  x = &( V [ n −1]) , то  вернуть Λ , иначе  вернуть  x + 1 процедура  добавления ( x , fin ) если  fin = Λ тогда  fin ← &( W [0]) (* fin ) ← (* x ) вернуть  fin + 1  если  m = 0, то U ← Λ, если  n = 0, то V ← Λ вернуть  merge ( U , V , prec , nextU , append , nextV , append )

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

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

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

процедура  Intg ( f , a , b , n ): float  t , x , s ; целое число  i  если  b = a  то  вернуть 0 x ← a ; s ← f ( a ) / 2; для i от 1 до  n −1 сделать  t ← i /( n +1); x ← (1− t ) * a + t * b ; s ← s + f ( x ) s ← f ( b ) / 2 вернуть ( b − a ) * s / n

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

Рассмотрим теперь задачу интегрирования заданной функции , с двумя аргументами, по кругу с заданным центром ( ) и заданным радиусом . Эту задачу можно свести к двум вложенным одномерным интегралам заменой переменных $г$ $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 ( t ) return  g ( x , y ) целое число  m ← раунд ( n * z / R ) вернуть  z * Intg ( gpolar , 0, 2*π, m ) вернуть  Intg ( gring , 0, R , n )

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

История

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

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

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