Войти
В вычислениях процедурный параметр является параметр процедуры процедуры, которая сама по себе является процедурой.
Эта концепция представляет собой чрезвычайно мощный и универсальный инструмент программирования, поскольку он позволяет программистам изменять определенные шаги библиотечной процедуры произвольно сложными способами, не имея необходимости понимать или измените код этой процедуры.
Этот инструмент особенно эффективен и удобен для языков, которые поддерживают определения локальных функций, таких как Pascal и современный диалект GNU из С. Тем более, когда доступны закрытие функций. Такие же (и другие) функциональные возможности предоставляются объектами в объектно-ориентированных языках программирования, но по значительно более высокой цене.
Процедурные параметры в некоторой степени связаны с концепциями функции первого класса и анонимной функции, но отличаются от них. Эти две концепции больше связаны с тем, как определяются функции, а не с тем, как они используются.
На большинстве языков, которые предоставляют эту функцию, процедурный параметр f подпрограммы P может быть вызван внутри тела P, как если бы это была обычная процедура:
процедура P (f): return f (6,3) * f (2,1)
При вызове подпрограммы P, нужно дать ему один аргумент, который должен быть некоторой ранее определенной функцией, совместимой с тем, как P использует свой параметр f. Например, если мы определим
процедуру plus (x, y): return x + y
, тогда мы можем вызвать P (plus), и результат будет плюс (6,3) * плюс (2,1) = (6 + 3) * (2 + 1) = 27. С другой стороны, если мы определим
процедуру quot (u, v): return u / v
, тогда вызов P (quot) вернет quot (6,3) * quot (2,1) = (6/3) * (2/1) = 4. Наконец, если мы определим
процедуру evil (z) return 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:
procedure isort (a, b, prec, поменять местами): целое число i, j; i ← a; пока i ≤ b do j ← i; while j>a и prec (j, j − 1) do swap (j, j − 1); j ← j − 1; я ← я + 1;
Эта процедура может использоваться для сортировки элементов с x [a] по x [b] некоторого массива x произвольного типа в указанном пользователем порядке. Параметры Prec и swap должны быть двумя функциями, определенными с помощью, обе принимают два целых числа r, s между a и b. Функция prec должна возвращать true тогда и только тогда, когда данные, хранящиеся в x [r], должны предшествовать данным, хранящимся в x [s], в порядке, определяемом клиентом. Функция подкачки должна обменивать содержимое x [r] и x [s] и не возвращать никакого результата.
При правильном выборе функций prec и swap одну и ту же процедуру isort можно использовать для переупорядочивания массивов любого типа данных, хранимых на любом носителе и организованных в любую структуру данных, которая обеспечивает индексированный доступ к отдельным элементам массива.. (Обратите внимание, однако, что существуют алгоритмы сортировки, которые намного более эффективны, чем сортировка вставкой для больших массивов.)
Например, мы можем сортировать массив z из 20 чисел с плавающей запятой, от z [1] до z [20] в порядке возрастания путем вызова isort (1, 20, zprec, zswap), где функции zprec и zswap определены как
procedure zprec (r, s): return (z [r]Сортировка строк матрицы
В другом примере, пусть M будет целыми числами с 10 строками и 20 столбцами, с индексами, начинающимися с 1. Следующий код будет переставьте элементы в каждой строке так, чтобы все четные значения располагались перед всеми нечетными значениями:
integer i procedure 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 do isort (1, 20, eoprec, eoswap);Обратите внимание, что эффекты eoprec и eoswap зависят от номера строки i, но процедуре isort это не обязательно знать.
Процедура векторной сортировки
В следующем примере isort используется для определения процедуры vecsort, которая принимает целое число n и целочисленный вектор v с элементами от v [0] до v [n − 1] и сортирует их в порядке возрастания или убывания, в зависимости от того, является ли третий параметр incr true или false соответственно:
procedure vecsort (n, v, incr) : procedure vprec (r, s): if incr thenreturn 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 ≠ Λ doifB = Λ или (A ≠ Λ и B ≠ Λ и prec (A, B)) then 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 return iniФункция prec должна принимать адреса r, s двух записей, по одной из каждой последовательности, и вернуть true, если первая запись должна предшествовать другой в выходной последовательности. Функция nextA должна брать адрес записи из первой последовательности и возвращать адрес следующей записи в той же последовательности или Λ, если ее нет. Функция appendA должна добавить первую запись из последовательности A к выходной последовательности; его аргументы - это адрес A записи, которую нужно добавить, и адрес fin последней записи в выходном списке (или Λ, если этот список все еще пуст). Процедура appendA должна возвращать обновленный адрес последнего элемента выходного списка. Процедуры nextB и appendB аналогичны для другой входной последовательности.
Объединение связанных списков
Чтобы проиллюстрировать использование общей процедуры объединения, вот код для объединения двух простых связанных списков, начиная с узлов по адресам R, S Здесь мы предполагаем, что каждая запись x содержит целочисленное поле x.INFO и поле адреса x.NEXT, указывающее на следующий узел; где информационные поля в каждом списке расположены в порядке возрастания. Списки ввода разбираются слиянием, и их узлы используются для построения списка вывода.
процедура listmerge (R, S): процедура prec (r, s): return r.INFOСлияние векторов
Следующий код демонстрирует независимость общей процедуры слияния от фактического представления последовательностей. Он объединяет элементы двух обычных массивов от 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): if x = (U [m − 1]) тогдаreturn Λ else return x + 1 procedure nextV (x): if x = (V [n − 1]) then return Λ elsereturn x + 1 procedure append (x, fin) if fin = Λ тогда fin ← (W [0]) (* fin) ← (* x) return fin + 1 если m = 0, то U ← Λ если n = 0, затем V ← Λ return merge (U, V, prec, nextU, append, nextV, append)Пример: определенный интегралИнтегрирование в интервале
Следующая процедура вычисляет приблизительное целое
f (x) dx данной действительной функции f на заданном интервале [a, b] вещественной линии . Используемый числовой метод - это правило трапеции с заданным числом шагов n; действительные числа аппроксимируются числами с плавающей запятой.
процедура Intg (f, a, b, n): float t, x, s; целое число i ifb = a затемreturn 0 x ← a; s ← f (a) / 2; для i из 1 ton − 1 do t ← i / (n + 1); х ← (1 - t) * a + t * b; s ← s + f (x) s ← f (b) / 2 return (b - a) * s / nИнтегрирование по диску
Теперь рассмотрим задача интегрирования заданной функции g с двумя аргументами по кругу D с заданным центром (xc, yc) и заданным радиусом R. Эта проблема может быть сведена к двум вложенным интегралам с одной переменной заменой переменных
Следующий код реализует правую формулу :
процедуру DiskIntg (g, xc, yc, R, n) процедуру gring (z): процедура gpolar (t): float x, yx ← 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) return Intg (gring, 0, R, n)Thi Код s использует процедуру интеграции Intg на двух уровнях. Внешний уровень (последняя строка) использует Intg для вычисления интеграла gring (z) для z, изменяющегося от 0 до R. Внутренний уровень (предпоследняя строка) определяет gring (z) как линейный интеграл . из g (x, y) по окружности с центром (xc, yc) и радиусом z.
ИсторияПроцедурные параметры были изобретены математиком Алонзо Черчем как часть его лямбда-исчисления, еще до появления электронных компьютеров. модель вычисления.
Процедурные параметры как функция языка программирования были введены в АЛГОЛ 60. Фактически, АЛГОЛ 60 имел мощный механизм передачи параметров «вызов по имени », который мог упростить некоторые способы использования процедурных параметров; см. Устройство Дженсена.
. Процедурные параметры были важной особенностью языка программирования LISP, который также ввел концепцию закрытия функции или funarg. Язык программирования C позволяет передавать указатели на функции в качестве параметров, которые достигают той же цели, и часто используются как обратные вызовы в , управляемом событиями. программирование и как обработчики ошибок. Однако только несколько современных компиляторов C допускают определения вложенных функций, поэтому другие его применения относительно редки. Процедурные параметры также были предоставлены в Паскале вместе с определениями вложенных процедур; однако, поскольку стандартный Паскаль не допускал раздельной компиляции, эта функция также мало использовалась в этом языке.
См. Также
