第一級関数

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

関数型プログラミングスタイルでは、高階関数の使用が標準的な手法であり、第一級関数は不可欠です。高階関数の簡単な例として、map関数があります。map関数は、関数とリストを引数として受け取り、リストの各要素に関数を適用して生成されたリストを返します。map関数をサポートする言語は、関数を引数として渡す機能をサポートしている必要があります。

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

このセクションでは、関数が第一級である関数型言語（ Haskell）と、関数が第二級である命令型言語（C ）で、特定のプログラミングイディオムがどのように扱われるかを比較します。

map :: ( a -> b ) -> [ a ] -> [ b ] map f [] = [] map f ( x : xs ) = f x : map f xs

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

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

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

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

typedef struct { int ( * f )( int , int , int ); int a ; int b ; } Closure ;void map ( Closure * 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 ) { return a * x + b ; }void main () { int l [] = { 1 , 2 , 3 , 4 , 5 }; int a = 3 ; int b = 1 ; Closure closure = { f , a , b }; map ( & closure , l , 5 ); }

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

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

プログラミングの圏論的説明において、第一級関数の利用可能性は閉圏の仮定に対応する。例えば、単純型付きラムダ計算は、デカルト閉圏の内部言語に対応する。

Erlang、Scheme、ML、Haskell、F#、Scalaなどの関数型プログラミング言語は、いずれも第一級関数を備えています。初期の関数型言語の一つであるLispが設計された当時は、第一級関数のすべての側面が十分に理解されていなかったため、関数は動的スコープで定義されていました。後のSchemeやCommon Lispの方言では、字句スコープの第一級関数が採用されています。

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

命令型言語においては、Algolと、Pascal、伝統的なC言語ファミリー、そして現代のガベージコレクションを採用した派生言語といった、Algolの派生言語とを区別する必要がある。Algolファミリーは、関数を引数として受け取るネストされた関数や高階関数は許容しているが、関数を結果として返す高階関数は許容していない（ただし、Algol 68は例外で、これは許容している）。その理由は、ネストされた関数が結果として返された場合に、非ローカル変数をどのように扱うべきかが不明であったためである（そして、Algol 68では、そのような場合に実行時エラーが発生する）。

C言語系では、関数を引数として渡すことも、関数を結果として返すこともできましたが、ネストされた関数をサポートしないことで問題を回避していました。（gccコンパイラは拡張機能としてネストされた関数をサポートしています。）関数を返すことの有用性は、主にトップレベル関数ではなく、非ローカル変数をキャプチャしたネストされた関数を返すことができる点にあるため、これらの言語は一般的に第一級関数を持つ言語とはみなされていません。

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

C++

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

Java

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

Lisp

字句スコープのLispバリアントはクロージャをサポートします。動的スコープのバリアントはクロージャをサポートしないか、クロージャを作成するための特別な構造が必要です。^{[ 22 ]}

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

Python

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

ルビー

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

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

明示的なカリー化。

• 機能喪失
• 評価
• 一流のメッセージ
• カッパ計算– 第一級関数を除外する形式体系
• 男性か少年かのテスト
• 部分適用

• レオニダス・フェガラス。「関数型言語と高階関数」。CSE5317/CSE4305：コンパイラの設計と構築。テキサス大学アーリントン校。

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