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

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

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

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

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

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

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

procedure P(f):
    return f(6,3) * f(2,1)

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

procedure plus(x, y):
    return 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. Наконец, если мы определим

procedure 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, swap):
    integer i, j;
    i ← a;
    while i ≤ b do
        j ← i;
        while j > a and 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 определены как

procedure zprec(r, s):
    return (z[r] < z[s]);

procedure zswap(r, s):
    float t;
    t ← z[r];
    z[r] ← z[s];
    z[s] ← t

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

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

integer i
procedure eoprec(r, s):
    return (M[i, r] mod 2) < (M[i, s] mod 2);

procedure eoswap(r, s):
    integer t;
    t ← M[i,r];
    M[i,r] ← M[i,s];
    M[i,s] ← t;

for i from 1 to 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 then
            return v[r] < v[s];
        else
            return v[r] > v[s];

    procedure vswap(r, s):
        integer 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 , которые будут описаны позже.

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

procedure listmerge(R, S):

    procedure prec(r, s):
        return r.INFO < s.INFO

    procedure next(x):
        return x.NEXT

    procedure append(x, fin)
        if fin ≠ Λ then fin.NEXT ← x
        x.NEXT ← Λ
        return x
     
    return merge(R, S, prec, next, append, next, append)

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

Следующий код иллюстрирует независимость общей процедуры слияния от фактического представления последовательностей. Он объединяет элементы двух обычных массивов чисел от 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 .

procedure arraymerge(U, m, V, n, W):

    procedure prec(r, s):
        return (*r) > (*s)

    procedure nextU(x):
        if x = &(U[m−1]) then return Λ else return x + 1

    procedure nextV(x):
        if x = &(V[n−1]) then return Λ else return x + 1

    procedure append(x, fin)
        if fin = Λ then fin ← &(W[0])
        (*fin) ← (*x)
        return fin + 1
        
    if m = 0 then U ← Λ
    if n = 0 then V ← Λ
    return merge(U, V, prec, nextU, append, nextV, append)

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

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

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

procedure Intg(f, a, b, n):
    float t, x, s; integer i
    if b = a then return 0
    x ← a; s ← f(a) / 2;
    for i from 1 to n−1 do
        t ← i/(n+1); x ← (1−t) * a + t * b;
        s ← s + f(x)
    s ← f(b) / 2
    return (b − a) * 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

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

procedure DiskIntg(g, xc, yc, R, n)

    procedure gring(z):

        procedure gpolar(t):
            float x, y
            x ← xc + z * cos(t)
            y ← yc + z * sin(t)
            return g(x, y)

        integer m ← round(n*z/R)
        return z * Intg(gpolar, 0, 2*π, m)

    return 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 допускают определения вложенных функций, поэтому другие их применения относительно редки. Процедурные параметры также были предоставлены в Паскале вместе с определениями вложенных процедур; однако, поскольку стандартный Паскаль не допускал раздельной компиляции, эта функция также мало использовалась в этом языке.

См. также