ファーストクラス関数

コンピュータサイエンスにおいて、プログラミング言語が関数を第一級市民として扱う場合、その言語は第一級関数を持つと言われます。これは、言語が関数を他の関数への引数として渡すこと、他の関数から値として返すこと、変数に代入すること、またはデータ構造に格納することをサポートすることを意味します。[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など）を比較することで、またはコンパイル型言語ではオブジェクトコードを比較することで実装できます。内包的等価性は、外延的等価性を意味します（関数が決定論的であり、プログラムカウンタや可変グローバル変数などの隠れた入力を持たないと仮定した場合）。
参照の等価性
外延的等価性と内包的等価性を実装することが非現実的であることから、関数の等価性判定をサポートするほとんどの言語は参照等価性を採用しています。すべての関数またはクロージャには一意の識別子（通常は関数本体またはクロージャのアドレス）が割り当てられ、識別子の等価性に基づいて等価性が判定されます。別々に定義されていても、それ以外は同一の関数定義が2つ存在する場合、それらは等しくないとみなされます。参照等価性は、内包的等価性と外延的等価性を意味します。参照等価性は参照の透明性を損なうため、Haskellなどの純粋言語ではサポートされていません。

型理論

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

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

言語サポート

Erlang、Scheme、ML、Haskell、F#、Scalaなどの関数型プログラミング言語はすべて、第一級関数を備えています。初期の関数型言語の一つである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]いいえ
パスカルはいいいえはいいいえ下向きいいえ
エイダはいいいえはいいいえ下向きいいえ
オベロンはい非ネストのみはいいいえ下向きいいえ
デルファイはいはいはい20092009いいえ
CファミリーCはいはいGNU CではそうClang(ブロック)でははいClang(ブロック)でははいいいえ関数ポインタを持ちます。
C++はいはいC++11 [10]C++11 [11]C++11 [11]C++11関数ポインタ、関数オブジェクトを持ちます。（下記も参照してください。）

明示的な部分適用は で可能ですstd::bind。

C#はいはい72.0 / 3.02.03.0デリゲート(2.0) とラムダ式 (3.0)があります。
Objective-Cはいはい匿名の使用2.0 +ブロック[12]2.0 + ブロックいいえ関数ポインタを持ちます。
ジャワはいはい匿名の使用Java 8Java 8はい匿名内部クラスを持ちます。
行くはいはい匿名の使用はいはいはい[13]
リンボはいはいはいはいはいいいえ
ニュースクウィークはいはいはいはいはいいいえ
さびはいはいはいはいはいはい[14]
関数型言語Lisp構文構文はいはいコモンリスプいいえ（以下を参照してください）
スキームはいはいはいはいはいSRFI 26 [15]
ジュリアはいはいはいはいはいはい
クロージュアはいはいはいはいはいはい
MLはいはいはいはいはいはい
ハスケルはいはいはいはいはいはい
jqはいいいえはい表現のみ下向きいいえ
スカラはいはいはいはいはいはい
アーランはいはいはいはいはいはい
エリクサーはいはいはいはいはいはい
F#はいはいはいはいはいはい
OCamlはいはいはいはいはいはい
スクリプト言語イオはいはいはいはいはいいいえ
JavaScriptはいはいはいはいはいECMAScript 5ES3のユーザーランドコードで部分的な適用が可能[16]
ルアはいはいはいはいはいはい[17]
PHPはいはい匿名の使用5.35.3いいえユーザーランドコードによる部分的な適用が可能です。
パールはいはい6はいはい6 [18]
パイソンはいはいはい表現のみはい2.5 [19]（以下を参照してください）
ルビー構文構文スコープなしはいはい1.9（以下を参照してください）
その他の言語フォートランはいはいはいいいえいいえいいえ
メープルはいはいはいはいはいいいえ
マセマティカはいはいはいはいはいいいえ
MATLABはいはいはいはい[20]はいはい新しい関数の自動生成により部分的な適用が可能。[21]
雑談はいはいはいはいはい部分的ライブラリを通じて部分的な適用が可能です。
迅速はいはいはいはいはいはい
C++
C++11 のクロージャは、コピー構築、参照構築（生存期間の延長なし）、またはムーブ構築（変数はクロージャと同じ期間存続する）によって非ローカル変数をキャプチャできます。最初のオプションは、クロージャが返される場合は安全ですが、コピーが必要であり、元の変数（クロージャが呼び出された時点では既に存在しない可能性があります）の変更には使用できません。2番目のオプションは、コストのかかるコピーを回避し、元の変数の変更を可能にしますが、クロージャが返される場合は安全ではありません（ダングリング参照を参照）。3番目のオプションは、クロージャが返される場合は安全ですが、コピーは不要ですが、元の変数の変更にも使用できません。
ジャワ
Java 8のクロージャは、finalまたは「事実上final」の非ローカル変数のみをキャプチャできます。Javaの関数型はクラスとして表現されます。匿名関数はコンテキストから推論された型を取ります。メソッド参照には制限があります。詳細については、「匿名関数 § Javaの制限事項」を参照してください。
Lisp
語彙スコープの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]。

参照

注記

  1. ^ アベルソン、ハロルド、サスマン、ジェラルド・ジェイ(1984). コンピュータプログラムの構造と解釈. MIT Press. 高階手続きによる抽象化の定式化. ISBN 0-262-01077-1. 2021年9月21日時点のオリジナルよりアーカイブ。2021年9月27日閲覧。
  2. ^ プログラミング言語用法、Michael Lee Scott 著、セクション 11.2「関数型プログラミング」。
  3. ^ ロベルト・エルサリムシィ;ルイス・エンリケ・デ・フィゲイレド。ワルデマール・セレス (2005)。 「Lua 5.0の実装」。ユニバーサルコンピュータサイエンスジャーナル。11 (7): 1159–1176。土井: 10.3217/jucs-011-07-1159。
  4. ^ ab Burstall, Rod; Strachey, Christopher (2000). 「プログラミング言語を理解する」(PDF) .高階および記号計算. 13 (52): 11– 49. doi :10.1023/A:1010052305354. S2CID  1989590. 2010年2月16日時点のオリジナルよりアーカイブ。{{cite journal}}: CS1 maint: bot: original URL status unknown (link)（2010年2月16日にも
  5. ^ Joel Moses . 「LISPにおけるFUNCTIONの機能、あるいはFUNARG問題を環境問題と呼ぶべき理由」MIT AIメモ199、1970年。
  6. ^ 「ネストされた関数を、その関数を終了させた後にそのアドレス経由で呼び出そうとすると、大変なことになります。」(GNU コンパイラコレクション: ネストされた関数)
  7. ^ Andrew W. Appel (1995). 「継続のための内包的等価性 ;=)」.
  8. ^ Tanenbaum, AS (1977). 「PASCALとAlgol 68の比較」.コンピュータジャーナル. 21 (4): 319. doi : 10.1093/comjnl/21.4.316 .
  9. ^ 「Pythonの歴史：Pythonの「関数型」機能の起源」2009年4月21日。
  10. ^ ラムダ/クロージャを使用したネストされた関数
  11. ^ ab Doc No. 1968: V Samko; J Willcock, J Järvi, D Gregor, A Lumsdaine (2006年2月26日) C++のラムダ式とクロージャ
  12. ^ 「Mac Dev Center: Blocksプログラミングトピック: はじめに」。2009年8月31日時点のオリジナルよりアーカイブ。
  13. ^ 「Go で部分適用できる 2 つの例」。
  14. ^ "partial_application". Docs.rs. 2020年11月3日閲覧。
  15. ^ 「SRFI 26: カリー化なしでパラメータを特殊化するための表記法」。
  16. ^ 「John Resig - JavaScript での部分適用」。
  17. ^ Katz, Ian (2010年7月23日). 「Lua Code for Curry (Currying Functions)」. 2018年11月6日時点のオリジナルよりアーカイブ。
  18. ^ 「ブログ | Perlgeek.de :: カリー化」。
  19. ^ 「Python 2.5 の新機能 - Python 3.10.0 ドキュメント」。
  20. ^ 「匿名関数 - MATLAB & Simulink - MathWorks 英国」。
  21. ^ MATLABにおける部分関数評価
  22. ^ ZetaLispのクロージャ Archived 2012-03-19 at the Wayback Machine

参考文献

  • レオニダス・フェガラス. 「関数型言語と高階関数」. CSE5317/CSE4305: コンパイラの設計と構築. テキサス大学アーリントン校.
Retrieved from "https://en.wikipedia.org/w/index.php?title=First-class_function&oldid=1309184326"