В вычислениях процедурный параметр — это параметр процедуры , которая сама является процедурой.
Эта концепция является чрезвычайно мощным и универсальным инструментом программирования , поскольку она позволяет программистам изменять определенные этапы библиотечной процедуры сколь угодно сложными способами без необходимости понимать или изменять код этой процедуры.
Этот инструмент особенно эффективен и удобен в языках, поддерживающих локальные определения функций , таких как Паскаль и современный диалект GNU C. Это тем более актуально, когда доступны замыкания функций . Ту же функциональность (и даже больше) предоставляют объекты в объектно-ориентированных языках программирования , но за значительно более высокую цену.
Процедурные параметры в некоторой степени связаны с понятиями функции первого класса и анонимной функции , но отличаются от них. Эти две концепции больше связаны с тем, как определяются функции, а не с тем, как они используются.
В большинстве языков, предоставляющих эту возможность, процедурный параметр f подпрограммы P можно вызывать внутри тела P , как если бы это была обычная процедура:
процедура P ( f ): вернуть f (6,3) * f (2,1)
При вызове подпрограммы P необходимо передать ей один аргумент, который должен быть некоторой ранее определенной функцией, совместимой с тем, как P использует свой параметр f . Например, если мы определим
процедура плюс ( x , y ): вернуть x + y
тогда мы можем вызвать P ( plus ), и результат будет плюс (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 записи активации , в которых находятся переменные среды, могут находиться в стеке сколь угодно глубоко. Это так называемая проблема нисходящей функции .
Понятие процедурного параметра лучше всего объяснить на примерах. Типичным применением является следующая общая реализация алгоритма сортировки вставками , которая принимает два целочисленных параметра a , b и два процедурных параметра prec , swap :
процедура isort ( a , b , prec , swap ): целое число i , 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 ): return ( z [ r ] < z [ s ]);процедура zswap ( r , s ): float t ; т ← z [ р ]; z [ р ] ← z [ s ]; z [ s ] ← т
В качестве другого примера, пусть M — матрица целых чисел с 10 строками и 20 столбцами с индексами, начинающимися с 1. Следующий код переупорядочит элементы в каждой строке так, чтобы все четные значения предшествовали всем нечетным значениям:
целое число i процедура eoprec ( r , s ): return ( M [ i , r ] mod 2) < ( M [ i , s ] mod 2);процедура eoswap ( r , s ): целое число t ; т ← 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 ): целое число t ; т ← v [ р ]; v [ р ] ← v [ s ]; v [ s ] ← т 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 ← Λ; fin ← Λ, в то время как A ≠ Λ или B ≠ Λ , если B = Λ или ( A ≠ Λ и B ≠ Λ и prec ( A , B )) то t ← nextA ( A ) fin ← AppendA( A , fin ); если ini = Λ , то ini ← fin A ← t else 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 , указывающий на следующий узел; где информационные поля расположены в порядке возрастания в каждом списке. Входные списки разбираются при слиянии, а их узлы используются для построения выходного списка.
слияние списка процедур ( R , S ): процедура prec ( r , s ): вернуть r . ИНФОРМАЦИЯ < с . ИНФОРМАЦИЯ следующая процедура ( x ): вернуть x . СЛЕДУЮЩИЙ процедура добавления ( x , fin ) если fin ≠ Λ , то fin . СЛЕДУЮЩИЙ ← x x . СЛЕДУЮЩИЙ ← Λ вернуть x возврат слияния ( 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 ): return (* r ) > (* s ) процедура nextU ( 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 ← Λ return merge ( U , V , prec , nextU , добавление , следующийV , добавление )
Следующая процедура вычисляет приблизительный интеграл f ( x ) d x данной действительной функции f на заданном интервале [ a , b ] действительной линии . В качестве численного метода используется правило трапеций с заданным числом шагов n ; действительные числа аппроксимируются числами с плавающей запятой.
процедура Intg ( f , a , b , n ): float t , x , s ; целое число i, если b = a, то вернуть 0 x ← a ; s ← ж ( а ) / 2; для i от 1 до n −1 do t ← i /( n +1); Икс ← (1− т ) * а + т * б ; s ← s + f ( x ) s ← f ( b ) / 2 return ( b - a ) * s / n
Рассмотрим теперь задачу интегрирования заданной функции с двумя аргументами по диску с заданным центром ( ) и заданным радиусом . Эту задачу можно свести к двум вложенным интегралам с одной переменной путем замены переменных
Следующий код реализует формулу в правой части :
процедура 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 ← round ( n * z / R ) return z * Intg ( gpolar , 0, 2*π, m ) вернуть Intg ( gring , 0, R , n )
Этот код использует процедуру интегрирования Intg на двух уровнях. Внешний уровень (последняя строка) использует Intg для вычисления интеграла от 0 до . Внутренний уровень (предпоследняя линия) определяется как интеграл от линии по кругу с центром и радиусом .
Процедурные параметры были изобретены до эпохи электронных компьютеров математиком Алонзо Чёрчем как часть его модели вычислений лямбда- исчисления.
Процедурные параметры как особенность языка программирования были представлены в АЛГОЛе 60 . Фактически, АЛГОЛ 60 имел мощный механизм передачи параметров « вызова по имени », который мог упростить некоторые виды использования процедурных параметров; см. Устройство Дженсена .
Процедурные параметры были важной особенностью языка программирования LISP , который также ввел концепцию закрытия функции или funarg . Язык программирования C позволяет передавать указатели на функции в качестве параметров, которые выполняют одну и ту же задачу, и часто используются в качестве обратных вызовов в программировании, управляемом событиями , а также в качестве обработчиков ошибок. Однако лишь немногие современные компиляторы C допускают определения вложенных функций, поэтому другие их применения относительно редки. Процедурные параметры также были предоставлены в Паскале вместе с определениями вложенных процедур; однако, поскольку стандартный Паскаль не допускал раздельной компиляции, эта функция также мало использовалась в этом языке.
