ファーストクラスの機能

コンピュータサイエンスでは、プログラミング言語が関数を第一級市民として扱う場合、そのプログラミング言語は第一級関数を持っていると言われます。これは、その言語が関数を他の関数に引数として渡すこと、他の関数から値として返すこと、変数に割り当てること、またはデータ構造に格納することをサポートすることを意味します。^[1]プログラミング言語理論家の中には、匿名関数（関数リテラル）のサポートも必要とする人もいます。^[2]第一級関数を持つ言語では、関数の名前は特別なステータスを持っておらず、関数型を持つ通常の変数のように扱われます。^[3]この用語は、 1960年代半ばに「第一級市民としての関数」の文脈でクリストファー・ストラチーによって造られました。^[4]

関数型プログラミングスタイルでは、高階関数の使用が標準的な手法であるため、ファーストクラス関数は必須です。高階関数の簡単な例としては、関数とリストを引数として受け取り、リストの各メンバーに関数を適用して形成されたリストを返すmap関数があります。言語がmap をサポートするには、関数を引数として渡すことをサポートする必要があります。

関数を引数として渡したり、結果として返したりする際には、特にネストされた関数や無名関数で導入された非ローカル変数がある場合に、実装上の特定の困難があります。歴史的に、これらはfunarg 問題と呼ばれていました。この名前は「関数引数」に由来しています。 ^[5]初期の命令型言語では、関数を結果の型としてサポートしないか ( ALGOL 60、Pascalなど)、ネストされた関数と非ローカル変数を省略するか ( Cなど) のいずれかによって、これらの問題を回避していました。初期の関数型言語Lisp は動的スコープのアプローチを採用しており、非ローカル変数は、関数が定義された場所ではなく、関数が実行された時点でのその変数の最も近い定義を参照します。Schemeでは、レキシカルスコープのファーストクラス関数の適切なサポートが導入され、関数への参照を裸の関数ポインタではなくクロージャとして処理する必要があり、^[4]ガベージコレクションが必要に なります。

このセクションでは、第一級関数を持つ関数型言語 ( Haskell ) と、関数が第二級オブジェクトである命令型言語 ( C ) で特定のプログラミングイディオムがどのように処理されるかを比較します。

関数が第一級市民である言語では、関数は他の値と同じように他の関数に引数として渡すことができます (別の関数を引数として受け取る関数は高階関数と呼ばれます)。Haskell 言語では次のようになります。

マップ:: ( a -> b ) -> [ a ] -> [ b ]マップf [] = []マップf ( x : xs ) = f x :マップf xs        
        
         

関数が第一級でない言語でも、関数ポインタやデリゲートなどの機能を使用することで、高階関数を記述できる場合がよくあります。C 言語では次のようになります。

void map ( int ( * f )( int ), int x [], size_t n ) { for ( int i = 0 ; i < n ; i ++ ) x [ i ] = f ( x [ i ] ); }       
            
          

2 つのアプローチには、ファーストクラス関数のサポートとは直接関係のない相違点がいくつかあります。Haskell のサンプルはリストを操作しますが、C のサンプルは配列を操作します。どちらもそれぞれの言語で最も自然な複合データ構造であり、C のサンプルをリンクリスト で操作すると、不必要に複雑になります。これは、C 関数が追加のパラメーター (配列のサイズを指定する) を必要とするという事実にも当てはまります。C 関数は配列をその場で更新し、値を返しませんが、Haskell のデータ構造は永続的です(新しいリストが返され、古いリストはそのまま残ります)。Haskell のサンプルは再帰を使用してリストを走査しますが、C のサンプルは反復 を使用します。これも、両方の言語でこの関数を表現する最も自然な方法ですが、Haskell のサンプルはfoldで、C のサンプルは再帰で簡単に表現できます。最後に、Haskell の関数には多態型がありますが、これは C ではサポートされていないため、すべての型変数を型定数 に固定しましたint。

匿名関数をサポートする言語では、このような関数を高階関数の引数として渡すことができます。

main = map ( \ x -> 3 * x + 1 ) [ 1 , 2 , 3 , 4 , 5 ]              

匿名関数をサポートしていない言語では、代わりに名前にバインドする必要があります。

int f ( int x ) {戻り値3 * x + 1 ; }   
         


int main () { int list [] = { 1 , 2 , 3 , 4 , 5 }; map ( f , list , 5 ); }  
           
      

匿名関数またはネストされた関数を作成すると、関数の本体外の変数（非ローカル変数と呼ばれる）を参照することが自然になります。

main = map ( \ x -> a * x + b ) [ 1 , 2 , 3 , 4 , 5 ]でa = 3 b = 1とします。     
             
                     

関数が単なる関数ポインターで表現されている場合、関数本体の外側にある値をどのように関数に渡すべきかを知ることはできず、そのためクロージャを手動で構築する必要があります。したがって、ここでは「ファーストクラス」関数について語ることはできません。

typedef struct { int ( * f )( int , int , int ); int a ; int b ; } closure_t ;  
       
     
     
 

void map ( closure_t * closure 、int x []、size_t n ) { for ( int i = 0 ; i < n ; ++ i ) x [ i ] = ( closure -> f )( closure -> a 、closure -> b 、x [ i ] ) ; }       
            
            


int f ( int a 、int b 、int x ) { a * x + bを返します。}       
         


void main () { int l [] = { 1 , 2 , 3 , 4 , 5 }; int a = 3 ; int b = 1 ; closure_t closure = { f , a , b }; map ( & closure , l , 5 ); }  
           
       
       
         
      

mapまた、 は環境外の2 つの を参照する関数に特化していることにも注意してくださいint。 これはより一般的に設定できますが、より多くの定型コード が必要になります。がネストされた関数fであった場合、同じ問題が発生するため、C ではサポートされていません。^[6]

関数を返すとき、実際にはそのクロージャを返します。C の例では、クロージャによってキャプチャされたローカル変数は、クロージャを構築する関数から戻るとスコープ外になります。後でクロージャを強制すると、未定義の動作が発生し、スタックが破損する可能性があります。これは、上向きの funarg 問題として知られています。

関数を変数に割り当てて(グローバル) データ構造内に格納すると、関数を返す場合と同じ問題が発生する可能性があります。

f :: [[整数] -> [整数]] f = let a = 3 b = 1 in [ map ( \ x -> a * x + b ), map ( \ x -> b * x + a )]    
     
          
                     

ほとんどのリテラルと値の等価性をテストすることができるので、プログラミング言語が関数の等価性のテストをサポートできるかどうかを尋ねるのは自然なことです。さらに調べてみると、この質問はより難しく、関数の等価性のいくつかのタイプを区別する必要があります。^[7]

外延的等式

2 つの関数fとg は、すべての入力 (∀ x . f ( x ) = g ( x )) に対して出力が一致する場合、外延的に等しいと見なされます。この等式の定義では、たとえば、挿入ソートやマージソートなどの安定したソートアルゴリズムの任意の 2 つの実装は等しいと見なされます。外延的等式の決定は一般に決定不可能であり、有限ドメインの関数の場合でも多くの場合は扱いにくいです。このため、プログラミング言語では関数の等式を外延的等式として実装していません。

内包的等価性

内包的等価性の下では、2 つの関数fとg は同じ「内部構造」を持つ場合、等しいとみなされます。この種の等価性は、関数本体のソース コード(Interpreted Lisp 1.5 など) またはコンパイル言語のオブジェクト コードを比較することによって、インタープリタ型言語で実装できます。内包的等価性は、外延的等価性を意味します (関数が決定論的であり、プログラム カウンターや可変グローバル変数などの隠れた入力がないと仮定します)。

参照の等価性

外延的等価性と内包的等価性を実装するのは非現実的であるため、関数の等価性をテストするほとんどの言語では参照等価性を使用します。すべての関数またはクロージャには一意の識別子 (通常は関数本体またはクロージャのアドレス) が割り当てられ、識別子の等価性に基づいて等価性が決定されます。別々に定義されていても、それ以外は同一の関数定義は、等しくないと見なされます。参照等価性は、内包的等価性と外延的等価性を意味します。参照等価性は参照の透明性を損なうため、Haskell などの純粋言語ではサポートされていません。

型理論では、型Aの値を受け取り、型Bの値を返す関数の型は、A → BまたはB ^Aと記述されることがあります。カリー・ハワード対応では、関数の型は論理的含意に関連し、ラムダ抽象化は仮説的仮定の解消に対応し、関数適用はモーダスポネンス推論規則に対応します。プログラミング関数の通常のケースの他に、型理論では、第一級関数を使用して連想配列や同様のデータ構造をモデル化します。

プログラミングの圏論的説明では、第一級関数の利用可能性は閉圏仮定に対応します。たとえば、単純型付けされたラムダ計算は、デカルトの閉圏の内部言語に対応します。

Erlang、Scheme、ML、Haskell、F#、Scalaなどの関数型プログラミング言語はすべて、ファーストクラス関数を備えています。最も初期の関数型言語の 1 つであるLispが設計された当時は、ファーストクラス関数のすべての側面が適切に理解されていなかったため、関数は動的スコープになりました。後のSchemeおよびCommon Lisp方言には、レキシカル スコープのファーストクラス関数があります。

Perl、Python、PHP、Lua、Tcl /Tk、JavaScript、Ioなどの多くのスクリプト言語には、ファーストクラス関数があります。

命令型言語の場合、Algol と、その子孫である Pascal、従来の C ファミリ、および最新のガベージ コレクション バリアントを区別する必要があります。Algol ファミリでは、ネストされた関数と高階関数を引数として使用できますが、結果として関数を返す高階関数は使用できません (これを許可する Algol 68 を除く)。その理由は、ネストされた関数が結果として返された場合に非ローカル変数を処理する方法が不明であったためです (このような場合、Algol 68 では実行時エラーが発生します)。

C ファミリでは、関数を引数として渡すことも、関数を結果として返すこともできましたが、ネストされた関数をサポートしないことで問題を回避しました (gcc コンパイラでは拡張機能としてネストされた関数が許可されます)。関数を返すことの有用性は、主にトップレベル関数ではなく、非ローカル変数をキャプチャしたネストされた関数を返す機能にあるため、これらの言語は一般にファーストクラス関数を備えているとは見なされていません。

現代の命令型言語は、多くの場合、ガベージ コレクションをサポートしており、ファーストクラス関数の実装が可能です。ファーストクラス関数は、多くの場合、C# 2.0 や、C、C++、Objective-C に対する Apple の Blocks 拡張など、言語の後のリビジョンでのみサポートされています。C++11 では、匿名関数とクロージャのサポートが言語に追加されましたが、この言語はガベージ コレクションが行われないため、結果として返される関数内の非ローカル変数には特別な注意が必要です (以下を参照)。

C++

C++11 のクロージャは、コピー構築、参照 (有効期間を延長しない)、またはムーブ構築(変数はクロージャと同じ期間有効) によって非ローカル変数をキャプチャできます。最初のオプションは、クロージャが返される場合は安全ですが、コピーが必要であり、元の変数 (クロージャが呼び出された時点では存在しない可能性があります) を変更するために使用することはできません。2 番目のオプションは、コストのかかるコピーを回避し、元の変数を変更できるようにしますが、クロージャが返される場合は安全ではありません (ぶら下がり参照を参照)。3 番目のオプションは、クロージャが返される場合は安全ですが、コピーは必要ありませんが、元の変数を変更するために使用することもできません。

ジャワ

Java 8のクロージャは、final または「事実上 final」の非ローカル変数のみをキャプチャできます。Java の関数型はクラスとして表されます。匿名関数は、コンテキストから推論された型を取ります。メソッド参照は制限されています。詳細については、「匿名関数 § Java の制限」を参照してください。

リスプ

語彙スコープ付きLispバリアントはクロージャをサポートします。動的スコープ付きバリアントはクロージャをサポートせず、クロージャを作成するための特別な構造を必要としません。^[22]

Common Lispでは、関数名前空間内の関数の識別子は、ファーストクラスの値への参照として使用できません。関数を値として取得するには、特別な演算子を使用functionする必要があります(function foo)。関数オブジェクトに評価されます。#'foo省略表記として存在します。このような関数オブジェクトを適用するには、関数を使用する必要がありますfuncall。(funcall #'foo bar baz)

パイソン

functools.partialバージョン 2.5 以降、およびバージョン 2.6 以降では、明示的な部分適用が可能ですoperator.methodcaller。

ルビー

Ruby の通常の「関数」(実際にはメソッド) の識別子は、値として使用したり、渡したりすることはできません。ファーストクラスのデータとして使用するには、まず または オブジェクトに取得する必要がありますMethod。Procこのような関数オブジェクトを呼び出す構文は、通常のメソッドを呼び出す構文とは異なります。

ネストされたメソッド定義は、実際にはスコープをネストしません。

を使用した明示的なカリー化[1]。

• 機能の非化
• 評価
• ファーストクラスのメッセージ
• カッパ計算– 第一級関数を除外する形式論
• 男か少年かのテスト
• 部分適用

• Leonidas Fegaras。「関数型言語と高階関数」。CSE5317/CSE4305: コンパイラの設計と構築。テキサス大学アーリントン校。

• Rosetta Code上のファーストクラス関数。
• 高階関数 2019年11月12日アーカイブ、Wayback Machine at IBM developerWorks