手続きパラメータ

コンピューティングにおいて、手続き型パラメータとは、それ自体が手続きである 手続きのパラメータです。

この概念は、非常に強力で多用途なプログラミングツールです。プログラマーは、その手順のコードを理解したり変更したりすることなく、ライブラリ手順の特定の手順を任意の複雑な方法で変更できるためです。

このツールは、 PascalやCの最新のGNU 方言など、ローカル関数定義をサポートする言語で特に効果的で便利です。関数クロージャが使用できる場合は、さらに効果的です。同じ機能 (およびそれ以上の機能) は、オブジェクト指向プログラミング言語のオブジェクトによって提供されますが、コストが大幅に高くなります。

手続き型パラメータは、ファーストクラス関数や匿名関数の概念と多少関連していますが、それらとは異なります。これら 2 つの概念は、関数の使用方法ではなく、関数の定義方法に関係しています。

この機能を提供するほとんどの言語では、サブルーチンPの手続き型パラメータf は、通常の手続きであるかのように Pの本体内で呼び出すことができます。

手順 P ( f ):
     f (6,3) * f (2,1)
を返す 

サブルーチンP を呼び出すときは、 P がパラメータf を使用する方法と互換性のある、事前に定義された関数を引数として与えなければなりません。たとえば、次のように定義すると、

手順 plus ( 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 を 返します。最後に、

手順 evil ( z )
    戻り値z + 100

そうすると、呼び出しP ( evil ) はあまり意味をなさなくなり、エラーとしてフラグが立てられる可能性があります。

この機能を持つプログラミング言語の中には、各手続きパラメータfの完全な型宣言を許可または要求するものがあり、これには引数の数と型、および結果の型（ある場合）が含まれます。たとえば、Cプログラミング言語では、上記の例は次のように記述できます。

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

原則として、 Pが呼び出されたときに引数として渡される実際の関数actf は、プロシージャ パラメータfの宣言された型と型互換性がなければなりません。これは通常、actfとf が同じ型の結果を返し、同じ数の引数を持ち、対応する引数が同じ型を持つ必要があることを意味します。ただし、上記のplusとquot の例で示されているように、引数の名前は同じである必要はありません。ただし、一部のプログラミング言語では、この点に関してより制限が厳しかったり、より自由であったりする場合があります。

手続き型パラメータを許可する言語では、スコープ規則は通常、手続き型パラメータがネイティブスコープ内で実行されるように定義されます。より正確には、関数actf がPの引数としてその手続き型パラメータfとして渡され、その後f がPの本体内から呼び出されるとします。actf が実行されている間、 actfはその定義の環境を参照します。^{[例が必要]}

これらのスコープ規則の実装は簡単ではありません。actfが最終的に実行されるまでに、環境変数が存在するアクティベーション レコードは、スタック内で任意の深さになる可能性があります。これは、いわゆる下向き funarg 問題です。

手続き型パラメータの概念は、例を挙げて説明するのが最も分かりやすいでしょう。典型的な応用例は、2 つの整数パラメータa、bと 2 つの手続き型パラメータprec、swap を取る挿入ソート アルゴリズムの次の汎用実装です。

手順 isort ( a , b , prec , swap ):
    整数 i、j ;
     i ← a ;
     i ≤ bの場合は j ← iを実行し、
         j > aかつprec ( j、j −1)の場合はswap ( j、j −1 ) を実行します。
             j ← j −1 ;
         i ← i +1 ;
 
           
            

この手順は、任意の型の配列xの要素x [ a ] からx [ b ] までを、ユーザーが指定した順序で並べ替えるために使用できます。パラメータprecとswap は、クライアントによって定義される2 つの関数で、どちらもaとb の間の2 つの整数rとsを受け取ります。prec関数は、クライアントによって定義された順序で、 x [ r ] に格納されているデータがx [ s ]に格納されているデータよりも前になる場合にのみtrueを返します。swap関数は、x [ r ] とx [ s ]の内容を交換し、結果を返しません。

prec関数とswap 関数を適切に選択することで、同じisortプロシージャを使用して、任意のデータ タイプの配列を並べ替えることができます。配列は任意の媒体に格納され、個々の配列要素へのインデックス アクセスを提供する任意のデータ構造に編成されます。(ただし、大規模な配列の場合、挿入ソートよりもはるかに効率的な ソート アルゴリズムがあることに注意してください。)

例えば、20個の浮動小数点数z [1]からz [20]の配列zを昇順にソートするには、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 を使用して、整数nと要素v [0] からv [ n −1] までの整数ベクトルv を受け取り、3 番目のパラメーターincrがtrueかfalse かに応じて、それぞれ昇順または降順で並べ替えるプロシージャ vecsort を定義します。

手順 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 );

ネストされた関数定義を使用して、vecsortに渡されるパラメーターincrに応じて効果が異なる関数vprec を取得していることに注意してください。標準 C のように、ネストされた関数定義を許可しない言語では、この効果を得るにはかなり複雑なコードやスレッドセーフでないコードが必要になります。

次の例は、手続き型パラメータを使用して、具体的な実装とは独立して抽象データ構造を処理する方法を示しています。問題は、レコードの順序付けられた 2 つのシーケンスを 1 つのソートされたシーケンスにマージすることです。レコードの性質と順序付け基準はクライアントが選択できます。次の実装では、各レコードをメモリ アドレスで参照できることと、有効なレコードのアドレスではない「ヌル アドレス」Λ があることのみを想定しています。クライアントは、各シーケンスの最初のレコードのアドレスA、Bと、後で説明する 関数prec、next、およびappend を提供する必要があります。

手順 merge ( A、B、prec、nextA、appendA、nextB、appendB ):
    アドレス ini、fin、t 
    ini ← Λ; fin ← Λ
     while  A ≠ Λ または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 は、各シーケンスから 1 つずつ、2 つのレコードのアドレスrとsを受け取り、出力シーケンスで最初のレコードが他のレコードより前に来る場合はtrueを返します。関数nextAは、最初のシーケンスからレコードのアドレスを受け取り、同じシーケンス内の次のレコードのアドレスを返すか、レコードがない場合は Λ を返します。関数appendA は、シーケンスAの最初のレコードを出力シーケンスに追加します。その引数は、追加するレコードのアドレスAと、出力リストの最後のレコードのアドレスfin (リストがまだ空の場合は Λ) です。プロシージャappendA は、出力リストの最後の要素の更新されたアドレスを返します。プロシージャnextBとappendB は、他の入力シーケンスについても同様です。

汎用マージ手順の使用方法を説明するために、アドレスR、Sのノードから始まる2 つの単純なリンク リストをマージするコードを次に示します。ここでは、各レコードxに整数フィールドx . INFOと次のノードを指すアドレス フィールドx . NEXTが含まれていると想定します。情報フィールドは各リスト内で昇順になっています。入力リストはマージによって解体され、そのノードを使用して出力リストが作成されます。

手順 listmerge ( R , S ):

    手順 prec ( r , s )
         : r.INFO < s.INFOを返す ​​

    手順 next ( x ):
         xを返します 。NEXT

    手順 append ( x , fin )
         if  fin ≠ Λ then  fin . NEXT ← x 
        x . NEXT ← Λ
         return  x
     
     マージを返す( R、S、prec、next、append、next、append )

次のコードは、汎用マージ手順がシーケンスの実際の表現から独立していることを示しています。このコードは、浮動小数点数の 2 つの通常の配列U [0] からU [ m −1] およびV [0] からV [ n −1] の要素を降順でマージします。入力配列は変更されず、マージされた値のシーケンスは 3 番目のベクトルW [0] からW [ m + n −1] に格納されます。C プログラミング言語と同様に、式 "& V " は変数Vのアドレスを生成し、 "* p " はpの値がアドレスである変数を生成し、 "&( X [ i ])" は任意の配列Xおよび任意の整数iに対して "&( X [0]) + 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を返す   

    手順 append ( x , fin )
         if  fin = Λ then  fin ← &( W [0])
        (* fin ) ← (* x )
         fin + 1を返す 
        
     m = 0の場合、 U ← Λ
     n = 0の場合、  V ← Λ
     merge ( U、V、prec、nextU、append、nextV、append )
を返します。 

次の手順では、実数値関数fの近似積分 f ( x ) d x を、実数直線上の指定された区間 [ a , b ]上で計算します。使用される数値計算法は、ステップ数nが指定された台形則です。実数は浮動小数点数で近似されます。 ${\displaystyle \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   
        

ここで、与えられた中心（）と半径 を持つ円板上で、2つの引数を持つ与えられた関数 を積分する問題を考えてみましょう。この問題は、変数変換によって2つのネストされた1変数積分に簡約できます。 ${\displaystyle g}$${\displaystyle D}$${\displaystyle xc,yc}$${\displaystyle R}$

${\displaystyle \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 )
            戻り値 g ( x , y )

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

    戻り値 Intg ( gring , 0, R , n )

このコードは、積分手順Intg を2 つのレベルで使用します。外側のレベル (最後の行) では、Intg を使用して、 0 から まで変化するの積分を計算します。内側のレベル (最後から 2 番目の行) では、 を中心、半径の円上の の線積分として定義します。 ${\displaystyle gring(z)}$${\displaystyle z}$${\displaystyle R}$${\displaystyle gring(z)}$${\displaystyle g(x,y)}$${\displaystyle (xc,yc)}$${\displaystyle z}$

手続き型パラメータは、電子計算機の時代以前に、数学者 アロンゾ・チャーチによって、ラムダ計算の計算モデルの一部として発明されました。

プログラミング言語機能としての手続き型パラメータは、ALGOL 60によって導入されました。実際、ALGOL 60 には、手続き型パラメータの使用を簡素化できる強力な「名前による呼び出し」パラメータ受け渡しメカニズムがありました。Jensenのデバイスを参照してください。

手続き型パラメータはLISP プログラミング言語の重要な機能であり、関数クロージャまたはfunargの概念も導入しました。Cプログラミング言語では、関数ポインタをパラメータとして渡すことができ、同じ目的を達成します。これは、イベント駆動型プログラミングのコールバックやエラー ハンドラとしてよく使用されます。ただし、ネストされた関数定義を許可する最新の C コンパイラはごくわずかであるため、その他の用途は比較的まれです。手続き型パラメータは、ネストされたプロシージャ定義とともに Pascal でも提供されていましたが、標準の Pascal では個別のコンパイルが許可されなかったため、この機能はその言語でもほとんど使用されませんでした。

• 関数ポインタ
• 関数型プログラミング
• フナルグ問題
• デザインパターン（コンピュータサイエンス）