コンピュータサイエンスにおいて、プログラミング言語が関数を第一級市民として扱う場合、その言語は第一級関数を持っていると言われます。これは、言語が関数を他の関数への引数として渡すこと、他の関数からの値として返すこと、変数に代入すること、またはデータ構造に格納することをサポートすることを意味します。[ 1 ]一部のプログラミング言語理論家は、匿名関数（関数リテラル）のサポートも要求しています。[ 2 ]第一級関数を持つ言語では、関数の名前は特別な地位を持たず、関数型を持つ通常の変数のように扱われます。[ 3 ]この用語は、1960年代半ばにクリストファー・ストラチーによって「第一級市民としての関数」という文脈で造られました。 [ 4 ]
関数型プログラミングスタイルでは、高階関数の使用が標準的な手法であり、第一級関数は必須です。高階関数の簡単な例としては、関数とリストを引数として受け取り、リストの各メンバーに関数を適用して生成されたリストを返すmap関数があります。言語がmap をサポートするには、関数を引数として渡すことをサポートしている必要があります。
関数を引数として渡したり、結果として返したりする際には、特にネストされた関数や無名関数で導入された非ローカル変数がある場合に、実装上の特定の困難があります。 歴史的に、これらはfunarg 問題と呼ばれていました。この名前は関数の引数に由来しています。 [ 5 ]初期の命令型言語では、関数を結果の型としてサポートしないか ( ALGOL 60、Pascal など)、ネストされた関数と非ローカル変数を省略する ( Cなど) ことによって、これらの問題を回避していました。初期の関数型言語Lisp は動的スコープのアプローチを採用しており、非ローカル変数は、関数が定義された場所ではなく、関数が実行された時点でのその変数の最も近い定義を参照します。Schemeでは、レキシカルスコープのファーストクラス関数の適切なサポートが導入され、関数への参照を裸の関数ポインタではなくクロージャとして処理する必要があり[ 4 ]、その結果、ガベージコレクションが必要になります。
概念
このセクションでは、第一級関数を持つ関数型言語（Haskell ）と、関数が第二級オブジェクトである命令型言語（ C） で、特定のプログラミングイディオムがどのように扱われるかを比較します
高階関数: 関数を引数として渡す
関数が第一級オブジェクトである言語では、関数は他の値と同様に他の関数に引数として渡すことができます（関数が別の関数を引数として取ることを高階関数と呼びます）。Haskell言語では、以下のようになります。
map :: ( a -> b ) -> [ a ] -> [ b ] map f [] = [] map f ( x : xs ) = f x : map 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 = 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 ; }クロージャ;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 ) { a * x + bを返します; }void main () { int l [] = { 1 , 2 , 3 , 4 , 5 }; int a = 3 ; int b = 1 ;クロージャclosure = { f , a , b }; map ( & closure , l , 5 ); }また、mapは環境外の2つの を参照する関数に特化されている点にも注意してくださいint。これはより一般的な設定も可能ですが、より多くの定型コードが必要になります。がネストされた関数fであった場合、それでも同じ問題が発生するため、C言語では がサポートされていません。[ 6 ]
高階関数: 結果として関数を返す
関数を返すとき、実際にはそのクロージャを返しています。Cの例では、クロージャによってキャプチャされたローカル変数は、クロージャを構築した関数から戻るとスコープ外になります。後からクロージャを強制的に返すと、未定義の動作が発生し、スタックが破損する可能性があります。これは上向き関数引数問題として知られています。
変数に関数を割り当てる
関数を変数に割り当てて、それを（グローバル）データ構造内に格納すると、関数を返す場合と同じ問題が発生する可能性があります。
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やAppleのC、C++、Objective-C拡張であるBlocksなど、言語の後継版でのみサポートされることが多いです。C++11では匿名関数とクロージャのサポートが追加されましたが、ガベージコレクションを行わない言語であるため、関数内の非ローカル変数を結果として返す場合には特別な注意が必要です（下記参照）。
| 言語 | 高階関数 | ネストされた関数 | 非局所変数 | 注釈 | ||||
|---|---|---|---|---|---|---|---|---|
| 議論 | 結果 | 名前付き | 匿名 | クロージャ | 部分適用 | |||
| アルゴルファミリー | アルゴル60 | はい | いいえ | はい | いいえ | 下向き | いいえ | 関数型を持ちます。 |
| アルゴル68 | はい | はい[ 8 ] | はい | はい | 下向き[ 9 ] | いいえ | ||
| パスカル | はい | いいえ | はい | いいえ | 下向き | いいえ | ||
| エイダ | はい | いいえ | はい | いいえ | 下向き | いいえ | ||
| オベロン | はい | 非ネストのみ | はい | いいえ | 下向き | いいえ | ||
| デルファイ | はい | はい | はい | 2009 | 2009 | いいえ | ||
| Cファミリー | C | はい | はい | GNU Cでは可能 | Clang(ブロック)では可能 | Clang(ブロック)では可能 | いいえ | 関数ポインタを持ちます。 |
| C++ | はい | はい | C++11 [ 10 ] | C++11 [ 11 ] | C++11 [ 11 ] | C++11 | 関数ポインタ、関数オブジェクトを持ちます。（下記も参照してください。） 明示的な部分適用は で可能です | |
| C# | はい | はい | 7 | 2.0 / 3.0 | 2.0 | 3.0 | デリゲート（2.0）とラムダ式（3.0） があります | |
| Objective-C | はい | はい | 匿名の使用 | 2.0 + ブロック[ 12 ] | 2.0+ブロック | いいえ | 関数ポインタを持ちます。 | |
| Java | はい | はい | 匿名の使用 | Java 8 | Java 8 | はい | 匿名内部クラスを持ちます。 | |
| ゴー | はい | はい | 匿名の使用 | はい | はい | はい[ 13 ] | ||
| リンボ | はい | はい | はい | はい | はい | いいえ | ||
| ニュースキーク | はい | はい | はい | はい | はい | いいえ | ||
| Rust | はい | はい | はい | はい | はい | はい[ 14 ] | ||
| 関数型言語 | Lisp | 構文 | 構文 | はい | はい | Common Lisp | いいえ | （下記参照） |
| Scheme | はい | はい | はい | はい | はい | SRFI 26 [ 15 ] | ||
| Julia | はい | はい | はい | はい | はい | はい | ||
| Clojure | はい | はい | はい | はい | はい | はい | ||
| ML | はい | はい | はい | はい | はい | はい | ||
| Haskell | はい | はい | はい | はい | はい | はい | ||
| jq | はい | いいえ | はい | 式のみ | 下向き | いいえ | ||
| Scala | はい | はい | はい | はい | はい | はい | ||
| Erlang | はい | はい | はい | はい | はい | はい | ||
| Elixir | はい | はい | はい | はい | はい | はい | ||
| F# | はい | はい | はい | はい | はい | はい | ||
| OCaml | はい | はい | はい | はい | はい | はい | ||
| スクリプト言語 | Io | はい | はい | はい | はい | はい | いいえ | |
| JavaScript | はい | はい | はい | はい | はい | ECMAScript 5 | ES3のユーザーランドコードで部分的な適用が可能[ 16 ] | |
| Lua | はい | はい | はい | はい | はい | はい[ 17 ] | ||
| PHP | はい | はい | 匿名の使用 | 5.3 | 5.3 | いいえ | ユーザーランドコードによる部分的な適用が可能です。 | |
| Perl | はい | はい | 6 | はい | はい | 6 [ 18 ] | ||
| Python | はい | はい | はい | 式のみ | はい | 2.5 [ 19 ] | （下記参照） | |
| Ruby | 構文 | 構文 | スコープなし | はい | はい | 1.9 | （下記参照） | |
| その他の言語 | Fortran | はい | はい | はい | いいえ | いいえ | いいえ | |
| メイプル | はい | はい | はい | はい | はい | いいえ | ||
| マセマティカ | はい | はい | はい | はい | はい | いいえ | ||
| MATLAB | はい | はい | はい | はい[ 20 ] | はい | はい | 新しい関数の自動生成により部分的な適用が可能。[ 21 ] | |
| Smalltalk | はい | はい | はい | はい | はい | 部分的 | ライブラリを通じて部分的な適用が可能です | |
| Swift | はい | はい | はい | はい | はい | はい | ||
- 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以降、およびoperator.methodcallerバージョン2.6以降では、明示的な部分適用が可能です- Ruby
- Rubyの通常の「関数」（実際にはメソッド）の識別子は、値として使用したり、渡したりすることはできません。ファーストクラスデータとして使用するには、まず関数
MethodまたはProcオブジェクトに取得する必要があります。このような関数オブジェクトを呼び出す構文は、通常のメソッドを呼び出す構文とは異なります - ネストされたメソッド定義では、実際にはスコープはネストされません。
- を使用した明示的なカリー化
[1]。
参照
注記
- ^アベルソン、ハロルド、サスマン、ジェラルド・ジェイ(1984).コンピュータプログラムの構造と解釈. MITプレス.高階手続きによる抽象化の定式化. ISBN 0-262-01077-12021年9月21日にオリジナルからアーカイブ。2021年9月27日閲覧
- ^プログラミング言語語用論、マイケル・リー・スコット著、セクション11.2「関数型プログラミング」。
- ^ロベルト・エルサリムシィ;ルイス・エンリケ・デ・フィゲイレド。ワルデマール・セレス (2005)。「Lua 5.0の実装」。ユニバーサルコンピュータサイエンスジャーナル。11 (7): 1159–1176。土井: 10.3217/jucs-011-07-1159。
- ^ a b Burstall, Rod; Strachey, Christopher (2000). 「プログラミング言語を理解する」(PDF) . Higher-Order and Symbolic Computation . 13 (52): 11– 49. doi : 10.1023/A:1010052305354 . S2CID 1989590. 2010年2月16日時点のオリジナルよりアーカイブ。
{{cite journal}}: CS1 maint: bot: 元のURLステータス不明（リンク）（2010年2月16日にも - ^ Joel Moses .「LISPにおけるFUNCTIONの機能、あるいはFUNARG問題を環境問題と呼ぶべき理由」 MIT AIメモ199、1970年。
- ^「ネストされた関数を、その関数を終了した後にそのアドレス経由で呼び出そうとすると、大変なことになります。」( GNU コンパイラコレクション: ネストされた関数)
- ^ Andrew W. Appel (1995).「継続のための内包的等価性 ;=)」 .
- ^ Tanenbaum, AS (1977). 「PASCALとAlgol 68の比較」 .コンピュータジャーナル. 21 (4): 319. doi : 10.1093/comjnl/21.4.316 .
- ^ 「Pythonの歴史: Pythonの「関数型」機能の起源」 2009年4月21日。
- ^ラムダ/クロージャを使用したネストされた関数
- ^ a b Doc No. 1968 : V Samko; J Willcock, J Järvi, D Gregor, A Lumsdaine (2006年2月26日) C++のラムダ式とクロージャ
- ^ 「Mac Dev Center: Blocks Programming Topics: Introduction」 。2009年8月31日時点のオリジナルよりアーカイブ。
- ^ 「Go で部分適用できる 2 つの例」。
- ^ "partial_application" . Docs.rs. 2020年11月3日閲覧。
- ^ 「SRFI 26: カリー化なしでパラメータを特殊化するための表記法」。
- ^ 「John Resig - JavaScript での部分適用」。
- ^ Katz, Ian (2010年7月23日). 「Lua Code for Curry (Currying Functions)」 . 2018年11月6日時点のオリジナルよりアーカイブ。
- ^ 「ブログ | Perlgeek.de :: カリー化」。
- ^ 「Python 2.5 の新機能 - Python 3.10.0 ドキュメント」。
- ^ 「匿名関数 - MATLAB & Simulink - MathWorks 英国」。
- ^ MATLABにおける部分関数評価
- ^ ZetaLispのクロージャArchived 2012-03-19 at the Wayback Machine
参考文献
- レオニダス・フェガラス著「関数型言語と高階関数」 CSE5317/CSE4305：コンパイラの設計と構築、テキサス大学アーリントン校
外部リンク
- Rosetta Codeのファーストクラス関数
- 高階関数 2019年11月12日アーカイブ、 Wayback Machine at IBM developerWorks
