関数型プログラミング

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

コンピュータサイエンス関数型プログラミングは、あるプログラミングパラダイムプログラムをすることによって構築される適用及び構成 機能を。これは宣言型プログラミングパラダイムであり、関数定義はプログラムの実行状態を更新する一連の命令ステートメントはなく、を他の値にマップする式のツリーです

関数型プログラミングでは、関数は次のように扱われるファーストクラスの市民、彼らは(ローカルを含む名前にバインドすることができることを意味し、識別子)として渡された引数、および返されただけで、他のように、他の機能からのデータ型の缶。これにより、プログラムを宣言型構成可能なスタイルで記述でき、小さな関数がモジュール方式で組み合わされます。

関数型プログラミングは、純粋関数型プログラミング、すべての関数を決定論的数学関数、または純粋関数として扱う関数型プログラミングのサブセットと同義として扱われることがあります。純粋関数が特定の引数を指定して呼び出されると、常に同じ結果が返され、可変状態やその他の副作用の影響を受けることはありません。これは、命令型プログラミングで一般的な不純な手順とは対照的です。、副作用(プログラムの状態の変更やユーザーからの入力の取得など)が発生する可能性があります。純粋関数型プログラミングの支持者は、副作用を制限することにより、プログラムのバグが少なくなり、デバッグテストが容易になりフォーマル検証により適していると主張しています[1] [2]

関数型プログラミングのルーツは関数のみに基づく正式な計算システムであるラムダ計算から発展した学界にあります。関数型プログラミングは歴史的に命令型プログラミングほど人気が​​ありませんでしたが、Common LispScheme[3] [4] [5] [6] ClojureWolfram Language[7]など、多くの関数型言語が今日、業界や教育で使用されています[8]ラケット[9] Erlang[10] [11] [12] Elixir[13] OCaml[14] [15] Haskell [16] [17]およびF# [18] [19]関数型プログラミングは、WebのJavaScript [20] 統計のR [21] [22] 財務分析のJ K Qなど、特定のドメインで成功を収めている一部の言語にとっても重要です。そして、のXQuery / XSLTのためのXML [23] [24] SQLLex / Yaccなどのドメイン固有の宣言型言語可変値を許可しないなど、関数型プログラミングのいくつかの要素を使用します[25]さらに、他の多くのプログラミング言語は、関数型スタイルでのプログラミングをサポートしているか、C ++ 11C#[26] Kotlin[27] Perl[28] PHP[29 ]などの関数型プログラミングの機能を実装しています。] Python[30] Go[31] Rust[32] Raku[33] Scala[34]およびJava(Java 8以降)[35]

歴史

ラムダ計算によって1930年代に開発された、アロンゾ・チャーチは、ある形式的なシステム計算から構築された機能のアプリケーション。 1937年、アランチューリングは、ラムダ計算とチューリングマシンが同等の計算モデルであることを証明し[36]、ラムダ計算がチューリング完全であることを示しました。ラムダ計算は、すべての関数型プログラミング言語の基礎を形成します。同等の理論的製剤、結合論理は、によって開発されたモージズ・ションフィンケルハスケル・カリー1920年代と1930年代に。[37]

チャーチは後に、より弱いシステムである単純型付きラムダ計算を開発しました。これは、すべての項に割り当てることによってラムダ計算を拡張しました[38]これは、静的に型付けされた関数型プログラミングの基礎を形成します。

最初の関数型プログラミング言語であるLISPは、1950年代後半にマサチューセッツ工科大学(MIT)ジョンマッカーシーによってIBM700 / 7000シリーズの科学コンピューター用に開発されました[39] LISP関数は、Churchのラムダ表記を使用して定義され、再帰関数を許可するためにラベル構造で拡張されました[40] Lispは最初に関数型プログラミングの多くのパラダイム機能を導入しましたが、初期のLispはマルチパラダイム言語であり、新しいパラダイムが進化するにつれて多数のプログラミングスタイルのサポートが組み込まれました。SchemeClojureなどの後の方言、およびDylanJuliaなどの派生物は、きれいに機能するコアの周りでLispを単純化および合理化しようとしましたが、Common Lispは、置き換えられた多数の古い方言のパラダイム機能を保持および更新するように設計されました。[41]

1956年の情報処理言語(IPL)は、最初のコンピューターベースの関数型プログラミング言語として引用されることがあります。[42]これはシンボルのリストを操作するためのアセンブリスタイルの言語です。関数を引数として受け入れる関数に相当するジェネレーターの概念があり、アセンブリレベルの言語であるため、コードをデータにすることができるため、IPLは高階関数を持っていると見なすことができます。ただし、変更リストの構造と同様の必須機能に大きく依存しています。

Kenneth E. Iversonは、1962年の著書A Programming LanguageISBN 9780471430148で説明されているように、1960年代初頭にAPL開発しました。 APLは、ジョン・バッカスFPに大きな影響を与えました。 1990年代初頭、アイバーソンとロジャーホイJを作成しました。 1990年代半ば、以前にアイバーソンと協力していたアーサーホイットニーKを作成しました。これは、その子孫であるQとともに金融業界で商業的に使用されています。  

John Backusは、1977年のチューリング賞の講演「プログラミングをフォンノイマンスタイルから解放できるか?関数型スタイルとそのプログラムの代数」でFP発表しました[43]彼は、関数型プログラムを、「プログラムの代数」を可能にする「フォームの組み合わせ」によって階層的に構築されるものとして定義しています。現代語では、これは関数型プログラムが構成性原則に従うことを意味します[引用が必要] Backusの論文は、関数型プログラミングの研究を普及させましたが、関数型プログラミングに現在関連付けられているラムダ計算スタイルではなく、関数レベルプログラミングを強調していました。

1973言語MLをして作成したロビン・ミルナーエジンバラ大学、およびデビッド・ターナーは、言語の開発SASLをセントアンドリュース大学。また、1970年代のエジンバラでは、BurstallとDarlingtonが関数型言語NPLを開発しました[44] NPLはクリーネの再帰方程式に基づいており、プログラム変換に関する研究で最初に導入されました。[45] Burstall、MacQueen、およびSannellaは、MLからのポリモーフィック型チェックを組み込んで、言語Hopeを生成しました[46]MLは最終的にいくつかの方言に発展し、その中で最も一般的なものは現在OCamlStandardMLです。

1970年代に、ガイL.スティールジェラルドジェイサスマンは、ラムダペーパーと1985年の教科書「計算機プログラムの構造と解釈」に記載されているように、スキームを開発しましたSchemeは、字句スコープを使用し、関数型プログラミングを促進する機能である末尾呼び出しの最適化を必要とするlispの最初の方言でした

1980年代に、PerMartin-Löf直観主義型理論構成的型理論とも呼ばれます)を開発しました。これは、関数型プログラムを依存型として表される構成的証明に関連付けました。これは、インタラクティブな定理証明への新しいアプローチにつながり、その後の関数型プログラミング言語の開発に影響を与えました。[要出典]

David Turnerによって開発された怠惰な関数型言語であるMirandaは、1985年に最初に登場し、Haskellに強い影響を与えましたミランダがプロプライエタリであるため、Haskellは1987年に関数型プログラミング研究のオープンスタンダードを形成するためのコンセンサスから始めました実装リリースは1990年から継続されています。

最近では、CSGジオメトリフレームワーク上に構築されOpenSCAD言語のパラメトリックCADの礼儀などのニッチでの使用が見出されましたが、値の再割り当てに対する制限(すべての値は定数として扱われます)により、関数型プログラミングに慣れていないユーザーの間で混乱が生じています。概念として。[47]

関数型プログラミングは、商業環境で引き続き使用されています。[48] [49] [50]

コンセプト

多くの概念とパラダイムは関数型プログラミングに固有であり、一般に命令型プログラミングオブジェクト指向プログラミングを含む)とは無関係です。ただし、プログラミング言語は多くの場合、いくつかのプログラミングパラダイムに対応しているため、「ほとんど必須の」言語を使用するプログラマーは、これらの概念のいくつかを利用している可能性があります。[51]

一流以上の高階関数

高階関数は、他の関数を引数として受け取るか、結果として返すことができる関数です。微積分では、高階関数の例は微分演算子です 関数の導関数を返します

高階関数は、高階関数と第一級関数の両方が関数を引数として、および他の関数の結果として許可するという点で、第一級関数と密接に関連しています。この2つの違いは微妙です。「高階」は他の関数で動作する関数の数学的概念を表し、「ファーストクラス」は使用に制限のないプログラミング言語エンティティのコンピュータサイエンス用語です(したがって、最初の-クラス関数は、他の関数への引数やその戻り値など、数値などの他のファーストクラスエンティティが表示できるプログラム内の任意の場所に表示できます。

高階関数は、部分適用またはカリー化を可能にします。これは、関数を引数に1つずつ適用し、各アプリケーションが次の引数を受け入れる新しい関数を返す手法です。これにより、プログラマーは、たとえば、自然数1に部分的に適用される加算演算子として後継関数簡潔に表現できます

純粋関数

純粋関数(または式)には副作用(メモリまたはI / O)はありませんこれは、純粋関数にはいくつかの有用なプロパティがあり、その多くを使用してコードを最適化できることを意味します。

  • 純粋な式の結果を使用しない場合は、他の式に影響を与えることなく削除できます。
  • 副作用を引き起こさない引数を使用して純粋関数を呼び出すと、結果はその引数リストに関して一定になります(参照透過性またはべきと呼ばれることもあります)。つまり、同じ引数を使用して純粋関数を再度呼び出すと、同じ結果が返されます。(これにより、メモ化などのキャッシュの最適化が可能になります。)
  • 2つの純粋な式の間にデータの依存関係がない場合は、順序を逆にするか、並行して実行し相互に干渉することはできません(つまり、純粋な式の評価はスレッドセーフです)。
  • 言語全体で副作用が許容されない場合は、任意の評価戦略を使用できます。これにより、コンパイラーは、プログラム内の式の評価を並べ替えたり、組み合わせたりすることができます(たとえば、森林破壊を使用)。

命令型プログラミング言語のほとんどのコンパイラは純粋関数を検出し、純粋関数呼び出しに対して共通部分式除去を実行しますが、通常この情報を公開しないプリコンパイル済みライブラリに対してこれを常に実行できるとは限らないため、これらの外部関数を含む最適化が妨げられます。gccなどの一部のコンパイラーは、プログラマーが外部関数を純粋として明示的にマークするためのキーワードを追加して、そのような最適化を可能にします。Fortran 95では、関数を純粋に指定することもできます[52] C ++ 11はconstexpr、同様のセマンティクスを持つキーワードを追加しました

再帰

関数型言語での反復(ループ)は通常、再帰を介して実行されます再帰関数はそれ自体を呼び出し、基本ケースに到達するまで操作を繰り返します。一般に、再帰ではスタックを維持する必要があります。スタックは、再帰の深さに比例してスペースを消費します。これにより、命令型ループの代わりに再帰を使用すると非常にコストがかかる可能性があります。しかし、として知られている再帰の特殊な形式末尾再帰は、命令型言語で反復を実装するために使用されるのと同じコードにコンパイラで認識し、最適化することができます。末尾再帰の最適化は、プログラムを継続渡しスタイルに変換することで実装できます。他のアプローチの中でも、コンパイル中。

Schemeの言語の標準は、彼らがアクティブな末尾再帰の無制限数を可能にしなければならないという意味、正しい末尾再帰をサポートするために実装する必要があります。[53] [54]適切な末尾再帰は、単なる最適化ではありません。これは、再帰を使用してループを表現できることをユーザーに保証する言語機能であり、そうすることでスペースを確保できます。[55]さらに、その名前に反して、末尾再帰だけでなく、すべての末尾呼び出しを説明します。通常、適切な末尾再帰はコードを命令ループに変換することで実装されますが、実装では他の方法で実装される場合があります。たとえば、CHICKENは意図的にスタックを維持し、スタックをオーバーフローさせます。ただし、これが発生すると、ガベージコレクターはスペースを要求し[56]、末尾再帰をループに変えなくても、無制限の数のアクティブな末尾呼び出しを許可します。

再帰の共通のパターンが有する、高次関数を用いて抽象化することができるcatamorphisms及びanamorphisms(または「折り目」および「展開」)最も明らかな例です。このような再帰スキームは、命令型言語のループなどの組み込みの制御構造に類似した役割を果たします

ほとんどの汎用関数型プログラミング言語は無制限の再帰を許可チューリング完全であるため、停止問題を 決定不能にし方程式の推論の不健全さを引き起こす可能性があり、一般に言語の型システムによって表現されるロジック矛盾導入する必要があります。などのいくつかの特別な目的の言語コックは唯一可能十分な根拠再帰ており強く正規非終端計算のみと呼ばれる値の無限ストリームで表すことができる(CODATA)。結果として、これらの言語はチューリング完全ではなく、特定の関数を表現することは不可能ですが、無制限の再帰によって生じる問題を回避しながら、幅広いクラスの興味深い計算を表現できます。他のいくつかの制約がある十分に根拠のある再帰に限定された関数型プログラミングは、全関数型プログラミングと呼ばれます[57]

厳密な評価と非厳密な評価

関数型言語は、彼らが使用しているかどうかによって分類することができ、厳密な(熱心)または非厳密(遅延)式が評価されているとき、関数の引数がどのように処理されるかを参照して、評価概念を。技術的な違いは、失敗した計算または発散した計算を含む式表示的意味論にあります。厳密な評価の下では、失敗したサブタームを含むタームの評価は失敗します。たとえば、次の式は次のとおりです。

印刷長さ([2 + 1、3 * 2、1 / 0、5-4])

リストの3番目の要素がゼロで除算されているため、厳密な評価では失敗します。遅延評価では、長さ関数は値4(つまり、リスト内のアイテムの数)を返します。これは、評価がリストを構成する用語を評価しようとしないためです。簡単に言うと、厳密な評価では、関数を呼び出す前に、常に関数の引数を完全に評価します。遅延評価は、関数呼び出し自体を評価するために値が必要でない限り、関数の引数を評価しません。

関数型言語での遅延評価の通常の実装戦略は、グラフ還元です。[58]遅延評価は、MirandaCleanHaskellなどのいくつかの純粋関数型言語でデフォルトで使用されます

Hughes 1984、データストリームのプロデューサーとコンシューマーの独立した実装を容易にすることにより、関心の分離を通じてプログラムのモジュール性を改善するメカニズムとして遅延評価を主張しています。[2] Launchbury 1993は、特にプログラムのストレージ要件の分析において遅延評価がもたらすいくつかの問題を説明し、そのような分析を支援するための操作的意味論提案しています。[59] Harper 2009は、言語の型システムを使用してそれらを区別し、同じ言語で厳密評価と遅延評価の両方を含めることを提案しています。[60]

型システム

特に1970年代Hindley–Milner型推論開発されて以来、関数型プログラミング言語は型付きラムダ計算を使用する傾向があり、コンパイル時にすべての無効なプログラムを拒否し、すべての有効なラムダ計算を受け入れる型なしラムダ計算とは対照的に、誤検出エラーのリスクがあります。プログラムはコンパイル時に、Lispとそのバリアント(Schemeなどで使用されるフォールスネガティブエラーのリスクがありますが、情報が有効なプログラムを拒否しないのに十分な場合、実行時にすべての無効なプログラムを拒否します。代数的データ型の使用複雑なデータ構造の操作を便利にします。強力なコンパイル時の型チェックが存在することで、テスト駆動開発などの他の信頼性手法がなくてもプログラムの信頼性が高まります。一方、型推論により、ほとんどの場合、コンパイラに型を手動で宣言する必要がなくなります。

CoqAgdaCayenneEpigramなどの一部の研究指向の関数型言語は、直観主義型理論に基づいておりを用語に依存させることができます。このような型は依存型と呼ばれます。これらの型システムには決定可能な型推論がなく、理解してプログラミングするのが困難です。[61] [62] [63] [64]しかし、依存型は高階述語論理で任意の命題を表現できます。カリー・ハワード同形性により、これらの言語で適切に入力されたプログラムは、正式な数学的証明を作成する手段になります。コンパイラはそこから認定コードを生成できます。これらの言語は主に学術研究(形式化された数学を含むに関心がありますが、工学でも使用され始めています。Compcertは、Coqで記述され、フォーマル検証されCプログラミング言語のサブセット用コンパイラです[65]

一般化代数的データ型(GADT)と呼ばれる限定された形式の依存型は、その不便さのほとんどを回避しながら、依存型プログラミングの利点のいくつかを提供する方法で実装できます。[66] GADTのはで利用可能なグラスゴーHaskellのコンパイラでは、OCamlの[67]とにスカラ[68]とJavaやC#などの他の言語への追加として提案されています。[69]

参照透過性

関数型プログラムには代入ステートメントがありません。つまり、関数型プログラムの変数の値は、一度定義されると変更されることはありません。これにより、実行の任意の時点で任意の変数を実際の値に置き換えることができるため、副作用の可能性が排除されます。したがって、関数型プログラムは参照透過性です。[70]

C代入ステートメントを考えてみましょうx = x * 10。これにより、変数に割り当てられた値が変更されますx。の初期値がでxあった1xする10、変数の2つの連続した評価は100それぞれとを生成ます。明らかに、またはのx = x * 10いずれかに置き換える、プログラムに異なる意味が与えられるため、式参照透過性ではありません。実際、代入ステートメントは参照透過性ではありません。 10100

さて、のような他の関数を考えている、それは暗黙的に入力xを変更するので、そのような持っていませんので、透明な副作用を関数型プログラムはこのタイプの関数のみを使用するため、参照透過性があります。 int plusone(int x) {return x+1;}

データ構造

純粋関数型データ構造は、多くの場合、命令型のデータ構造とは異なる方法で表されます。[71]たとえば、アクセス時間と更新時間が一定配列は、ほとんどの命令型言語の基本コンポーネントであり、ハッシュテーブルバイナリヒープなどの多くの命令型データ構造は配列に基づいています。配列は、純粋に機能的な実装を認めるが、対数アクセスと更新時間を持っているマップまたはランダムアクセスリストに置き換えることができます。純粋関数型データ構造には永続性があります、以前のバージョンのデータ構造を変更せずに保持するプロパティ。Clojureでは、永続的なデータ構造が、命令型の対応物の機能的な代替手段として使用されます。たとえば、永続的なベクトルは、部分的な更新にツリーを使用します。insertメソッドを呼び出すと、すべてではありませんが一部のノードが作成されます。[72]

命令型プログラミングとの比較

関数型プログラミングは命令型プログラミングとは大きく異なります最も重要な違いは、関数型プログラミングが、状態とI / Oを実装するための命令型プログラミングで使用される副作用を回避するという事実に起因します。純粋関数型プログラミングは、副作用を完全に防ぎ、参照透過性を提供します。

高階関数は、古い命令型プログラミングではめったに使用されません。従来の命令型プログラムでは、ループを使用してリストをトラバースおよび変更する場合があります。一方、関数型プログラムは、関数とリストを受け取り、各リストアイテムに関数を適用することによって新しいリストを生成して返す、高階の「マップ」関数を使用する可能性があります。

命令型プログラミングと関数型プログラミング

次の2つの例(JavaScript記述)は同じ効果を実現します。配列内のすべての偶数に10を掛けてすべて加算し、最終的な合計を変数「result」に格納します。

従来の命令ループ:

CONST  numList  =  [ 1  2  3  4  5  6  7  8  9  10 ]。
聞かせて 結果 =  0 ;
  iは =  0 ;  I  <  numList 長さ;  I ++  {
  場合 numList [ I ]   2  ===  0  {
    結果 + =  numList [ i ]  *  10 ; 
  } 
}

高階関数を使用した関数型プログラミング:

CONST 結果 =  [ 1  2  3  4  5  6  7  8  9  10 ] 
               フィルタn  =>  n   2  ===  0 
               マップa  =>  a  *  10 
               削減((a  b  =>  a  +  b );

状態のシミュレーション

多くの場合、州で最も自然に実装されているように見えるタスク(たとえば、銀行口座の残高の維持)があります。純粋関数型プログラミングは、これらのタスクと、ユーザー入力の受け入れや画面への印刷などのI / Oタスクを別の方法で実行します。

純粋関数型プログラミング言語Haskellは、から派生したモナドを使用してそれらを実装します。モナドは、純度を失うことなく、命令型の方法で可変状態(およびI / Oなどの他の副作用)を使用した計算のモデリングを含む(ただしこれらに限定されない)特定のタイプの計算パターンを抽象化する方法を提供します。適切なテンプレートと例があれば、既存のモナドはプログラムに簡単に適用できますが、多くの学生は、新しいモナドを定義するように求められた場合など、概念的に理解するのが難しいと感じています(特定の種類のライブラリで必要になる場合があります)。[73]

関数型言語は、不変の状態を渡すことによって状態をシミュレートします。これは、関数にパラメーターの1つとして状態を受け入れさせ、古い状態を変更せずに、結果とともに新しい状態を返すようにすることで実行できます。[74]

不純な関数型言語には通常、可変状態を管理するためのより直接的な方法が含まれています。たとえば、Clojureは、純粋関数を現在の状態に適用することで更新できるマネージド参照を使用します。この種のアプローチは、計算を表現するための好ましい方法として純粋関数の使用を促進しながら、可変性を可能にします。[要出典]

プログラムの副作用を追跡するためにホーア論理一意性などの代替方法が開発されました。いくつかの現代の研究言語は、副作用の存在を明確にするためにエフェクトシステム使用しています[要出典]

効率の問題

関数型プログラミング言語は、通常CPascalなどの命令型言語よりもCPUとメモリの使用効率が低くなります[75] これは、配列のようないくつかの可変データ構造が、現在のハードウェアを使用して非常に単純な実装をしているという事実に関連しています。フラット配列は、深くパイプライン化されたCPUを使用して非常に効率的にアクセスでき、キャッシュを介して効率的にプリフェッチされます(複雑なポインター追跡は不要です)。)、またはSIMD命令で処理されます。また、同等に効率的な汎用の不変の対応物を作成することも容易ではありません。純粋関数型言語の場合、最悪の場合の速度低下は、使用されるメモリセルの数の対数です。これは、可変メモリは、対数アクセス時間を持つ純粋関数型データ構造(平衡ツリーなど)で表すことができるためです。[76]しかしながら、そのような減速は普遍的ではない。Computer Language Benchmarks Gameによる、集中的な数値計算を実行するプログラムの場合、OCamlCleanなどの関数型言語はCよりもわずかに遅いだけです。[77]大きな行列と多次元を処理するプログラムの場合データベース配列関数型言語(JKなど)は、速度を最適化して設計されました。

多くの場合、データの不変性は、コンパイラーが命令型言語では安全ではない仮定を行うことを可能にすることで実行効率につながる可能性があり、したがってインライン展開の機会が増えます。[78]

遅延評価は、漸近的であってもプログラムを高速化する可能性がありますが、最大でも一定の要因で速度を低下させる可能性があります(ただし、不適切に使用するとメモリリークが発生する可能性があります)。 Launchbury 1993 [59]は、遅延評価からのメモリリークに関連する理論上の問題について説明しています 2008 [79]は、それらを分析および修正するためのいくつかの実用的なアドバイスを提供します。ただし、逆参照されたコードとデータを広範囲に使用する遅延評価の最も一般的な実装は、深いパイプラインとマルチレベルキャッシュ(キャッシュミスが数百サイクルかかる可能性がある)を備えた最新のプロセッサではパフォーマンスが低下します[要出典]

非関数型言語での関数型プログラミング

従来は関数型言語とは見なされていなかった言語で、関数型プログラミングスタイルを使用することができます。[80]たとえば、D [81]Fortran95 [52]はどちらも純粋関数を明示的にサポートしています。

JavaScriptLua[82] PythonGo [83]は、最初からファーストクラスの関数持っていました。[84] Pythonは、1994年にlambda」、「map」、「reduce」、「filter」をサポートし、Python 2.2ではクロージャをサポートしていました[85]、Python3は「reduce」をfunctools標準ライブラリモジュールに委任しました。[86]ファーストクラスの関数は、PHP 5.3、Visual Basic 9C# 3.0、C ++ 11などの他の主流言語に導入されています。とKotlin[27] [要出典]

ではPHP匿名クラス閉鎖およびラムダが完全にサポートされています。機能的なスタイルでのプログラミングを支援するために、不変のデータ構造用のライブラリと言語拡張が開発されています。

Java匿名クラスは時々シミュレートするために使用することができ、クロージャ[87]ただし、匿名クラスは機能が制限されているため、クロージャの適切な代替とは限りません[88] Java 8は、一部の無名クラスの代わりとしてラムダ式をサポートしています。[89]

C# 匿名クラスがあるため、必要ありません閉鎖とラムダが完全にサポートされています。不変のデータ構造用のライブラリと言語拡張機能は、C#の機能スタイルでのプログラミングを支援するために開発されています。

多くのオブジェクト指向の デザインパターンは、関数型プログラミングの用語で表現できます。たとえば、戦略パターンは単に高階関数の使用を指示し、ビジターパターンは大まかにカタモルフィズムまたはフォールドに対応します。

同様に、関数型プログラミングからの不変データのアイデアは、命令型プログラミング言語[90]、たとえば不変配列であるPythonのタプルやJavaScriptのObject.freeze()に含まれていることがよくあります。[91]

アプリケーション

スプレッドシート

スプレッドシートは、純粋なゼロ次の厳密な評価の関数型プログラミングシステムの形式と見なすことができます[92]ただし、スプレッドシートは一般に高階関数とコードの再利用が不足しており、一部の実装では再帰も不足しています。高階で再利用可能な機能を可能にするために、スプレッドシートプログラム用にいくつかの拡張機能が開発されましたが、これまでのところ、本質的に主に学術的なものです。[93]

アカデミア

関数型プログラミングは、プログラミング言語理論の分野で活発に研究されている分野ですいくつかあります査読を含む機能のプログラミングに焦点を当てた出版会場、関数プログラミングに関する国際会議関数プログラミングのジャーナル、および関数型プログラミングの動向シンポジウムが

業界

関数型プログラミングは、さまざまな産業用アプリケーションで使用されています。たとえば、1980年代後半にスウェーデンのエリクソンによって開発されたErlangはもともとフォールトトレラントな通信システムを実装するために使用されていましたが[11]、その後NortelFacebookなどの企業でさまざまなアプリケーションを構築するために人気がありました。ÉlectricitédeFranceおよびWhatsApp[10] [12] [94] [95] [96]スキームLispの方言 は、初期のAppleMacintoshコンピュータでのいくつかのアプリケーションの基礎として使用され[3] [4]シミュレーションソフトウェアのトレーニング[5]望遠鏡の制御などの問題に適用されてきました[6] 1990年代半ばに導入されたOCamlは、財務分析、[14] ドライバー検証、産業用ロボットプログラミング、組み込みソフトウェアの静的分析などの分野で商用利用されています[15] Haskellは、当初は研究言語として意図されていましたが、[17]また、航空宇宙システム、ハードウェア設計、Webプログラミングなどの分野で、さまざまな企業から適用されています。[16] [17]

業界で使用されている他の関数型プログラミング言語には、Scala[97] F#[18] [19] Wolfram Language[7] Lisp[98] Standard ML[99] [100]Clojureなどがあります。[101]

機能的な「プラットフォーム」は、リスク分析のための金融で人気があります(特に大規模な投資銀行で)。リスク要因は、相互依存グラフ(カテゴリ)を形成する関数としてコード化され、グレブナー基底の最適化とは異なり包括的資本分析やレビューなどの規制コンプライアンスのために、市場シフトの相関関係を測定します財務におけるOCAMLまたはCAMLのバリエーションの使用を考えると、これらのシステムは、カテゴリ別の抽象マシンまたはCAMに関連していると見なされることがあります。実際、関数型プログラミングは圏論の影響を強く受けています

教育

多くの大学は、学部のコンピュータサイエンスの学位の一部として関数型プログラミングを教えているか、教えてきました[102] [103] [104] [105]プログラミングの入門書として使用する人もいれば、[105]命令型プログラミングを教えた後に教える人もいます。[104] [106]

コンピュータサイエンス以外では、関数型プログラミングは、問題解決、代数、幾何学の概念を教える方法として使用されています。[107] それはまた、古典力学の構造と解釈において古典力学を教えるためのツールとしても使用されてきました

も参照してください

参考文献

  1. ^ ヒューダック、ポール(1989年9月)。「関数型プログラミング言語の概念、進化、および応用」(PDF)ACMコンピューティング調査21(3):359–411。土井10.1145 /72551.72554S2CID 207637854  
  2. ^ a b ヒューズ、ジョン(1984)。「関数型プログラミングが重要な理由」
  3. ^ a b クリンガー、ウィル(1987)。「マルチタスクとMacScheme」MacTech3(12)2008年8月28日取得
  4. ^ a b Hartheimer、Anne(1987)。「MacScheme + Toolsmithでのテキストエディタのプログラミング」MacTech3(1)。2011年6月29日にオリジナルからアーカイブされまし2008年8月28日取得
  5. ^ a b キッド、エリック。スキームにおけるテロ対応訓練CUFP2007 2009年8月26日取得
  6. ^ a b Cleis、Richard。宇宙でのスキームCUFP2006 2009年8月26日取得
  7. ^ a b 「Wolfram言語ガイド:関数型プログラミング」2015 2015年8月24日取得
  8. ^ 「関数型プログラミング言語と手続き型プログラミング言語」応用数学科コロラド大学。2007年11月13日にオリジナルからアーカイブされまし
  9. ^ 「未知の2の状態ベースのスクリプティング」(PDF)2012年12月15日にオリジナル(PDF)からアーカイブされまし取り出さ2011-08-08に
  10. ^ a b 「製品開発にErlangを使用しているのは誰ですか?」Erlangに関するよくある質問2018427日取得
  11. ^ a b アームストロング、ジョー(2007年6月)。Erlangの歴史プログラミング言語の歴史に関する第3回ACMSIGPLAN会議。カリフォルニア州サンディエゴ。土井10.1145 /1238844.1238850
  12. ^ a b ラーソン、ジム(2009年3月)。「並行プログラミングのためのErlang」ACMの通信52(3):48 DOI10.1145 / 1467247.1467263S2CID 524392 
  13. ^ 「Elixirプログラミング言語」2021-02-14を取得
  14. ^ a b ミンスキー、ヤロン; 週、スティーブン(2008年7月)。「CamlTrading—ウォール街での関数型プログラミングの経験」機能プログラミングジャーナル18(4):553–564。土井10.1017 / S095679680800676XS2CID 30955392 2008年8月27日取得 
  15. ^ a b リロイ、ザビエル。産業におけるCamlのいくつかの使用法(PDF)CUFP2007 2009年8月26日取得
  16. ^ B 「業界ではハスケル」HaskellWiki 2009年8月26日取得Haskellは、航空宇宙や防衛から金融、Webスタートアップ、ハードウェア設計会社、芝刈り機メーカーまで、商業的にさまざまな用途に使用されています。
  17. ^ a b c ヒューダック、ポール; ヒューズ、J。; ジョーンズ、SP; ワドラー、P。(2007年6月)。Haskellの歴史:クラスで怠惰であることプログラミング言語の歴史に関する第3回ACMSIGPLAN会議。カリフォルニア州サンディエゴ。土井10.1145 /1238844.1238856 2013年9月26日取得
  18. ^ a b マンセル、ハワード(2008)。F#の定量的ファイナンスCUFP2008 2009年8月29日取得
  19. ^ a b Peake、Alex(2009)。F#の最初の実質的な基幹業務アプリケーションCUFP 2009年アーカイブ2009-10-17に2009年8月29日取得
  20. ^ コメント、2017年6月27日Matt Banz Feed 603up2。「JavaScriptでの関数型プログラミング入門」Opensource.com 2021-01-09を取得
  21. ^ 「useR!2006の会議スケジュールには、Rの商用利用に関する論文が含まれています」R-project.org。2006-06-08 20116月20日取得
  22. ^ チェンバーズ、ジョンM.(1998)。データを使用したプログラミング:S言語のガイドシュプリンガーバーラグ。pp。67–70。ISBN 978-0-387-98503-9
  23. ^ Novatchev、Dimitre。「関数型プログラミング言語XSLT—例による証明」2006年5月27日取得
  24. ^ メルツ、デビッド。「XMLプログラミングパラダイム(パート4):XML処理にアプローチする関数型プログラミング」IBMdeveloperWorks 2006年5月27日取得
  25. ^ チェンバリン、ドナルドD。; ボイス、レイモンドF.(1974)。「SEQUEL:構造化された英語のクエリ言語」。1974 ACM SIGFIDETの議事録:249–264。
  26. ^ C#と関数型プログラミング-サイモン・ペインター- NDCオスロ2020年からアーカイブ、オリジナルの2021年10月30日には、取得した2021年10月23日を
  27. ^ B 「関数型プログラミング- Kotlinプログラミング言語」Kotlin 20195月1取得
  28. ^ Dominus、Mark J.(2005)。高次のPerlモーガンカウフマンISBN 978-1-55860-701-9
  29. ^ Holywell、Simon(2014)。PHPでの関数型プログラミングphp [アーキテクチャ]。ISBN 9781940111056
  30. ^ The Cain Gang Ltd. 「Pythonメタクラス:誰?なぜ?いつ?」(PDF)2009年5月30日にオリジナル(PDF)からアーカイブされまし検索された27年6月2009年
  31. ^ 「GopherCon2020:DylanMeeus-Goを使用した関数型プログラミング」YouTube.com
  32. ^ 「関数型言語の機能:イテレータとクロージャ-Rustプログラミング言語」doc.rust-lang.org 2021-01-09を取得
  33. ^ Vanderbauwhede、Wim。「関数型プログラミングによるよりクリーンなコード」2020年9月11日にオリジナルからアーカイブされまし2020年10月6日取得
  34. ^ 「効果的なScala」ScalaWiki 2012年2月21日取得効果的なScala。
  35. ^ 「Java8(Java 1.8とも呼ばれます)以降のパッケージjava.util.functionのドキュメント」2021616日取得
  36. ^ チューリング、AM(1937)。「計算可能性とλ定義可能性」。シンボリックロジックのジャーナルケンブリッジ大学出版局。2(4):153–163。土井10.2307 / 2268280JSTOR 2268280 
  37. ^ ハスケルブルックスカリー; ロベール・フェイ(1958)。コンビネータ論理North-Holland PublishingCompany 2013年2月10日取得
  38. ^ 教会、A。(1940)。「型の単純な理論の定式化」。Journal of SymbolicLogic5(2):56–68。土井10.2307 / 2266170JSTOR 2266170 
  39. ^ マッカーシー、ジョン(1978年6月)。Lispの歴史(PDF)プログラミング言語の歴史カリフォルニア州ロサンゼルス。pp。173–185。土井10.1145 /800025.808387
  40. ^ ジョンマッカーシー(1960)。「S式の再帰関数とその機械による計算、パートI」(PDF)ACMの通信ACMニューヨーク、ニューヨーク、米国。3(4):184–195。土井10.1145 /367177.367199S2CID 1489409  
  41. ^ ガイL.スティール; リチャードP.ガブリエル(1996年2月)。Lispの進化(PDF)ACM / SIGPLANのプログラミング言語の第2の歴史pp。233–330。土井10.1145 /234286.1057818ISBN  978-0-201-89502-5S2CID  47047140
  42. ^ ハーバート・A・サイモンの回想録(1991)、私の人生のモデルpp.189-190 ISBN 0-465-04640-1は、彼、アル・ニューエル、クリフ・ショーは「...一般的に両親であると判断されている」と主張しています。 PrincipiaMathematicaの定理を自動的に証明するプログラムであるLogicTheoristを作成するための人工知能[フィールド]の。これを達成するために、彼らは、遡及的に見て、関数型プログラミングを組み込む言語とパラダイムを発明しなければなりませんでした。 
  43. ^ Backus、J。(1978)。「プログラミングをフォンノイマンスタイルから解放することはできますか?:機能スタイルとそのプログラムの代数」ACMの通信21(8):613–641。土井10.1145 /359576.359579
  44. ^ RMバーストール。関数型プログラミング言語の設計上の考慮事項。招待論文、Proc。Infotech State of the ArtConf。「TheSoftwareRevolution」、コペンハーゲン、45–57(1977)
  45. ^ RMバーストールとJ.ダーリントン。再帰的プログラムを開発するための変換システム。Journal of the Association for Computing Machinery 24(1):44–67(1977)
  46. ^ RM Burstall、DB MacQueen、DTSannella。希望:実験的な応用言語。手順 1980 LISP Conference、スタンフォード、136–143(1980)。
  47. ^ 「assign()の検出を簡単にします!」OpenSCAD
  48. ^ ピーターブライト(2018年3月13日)。「開発者は流行の新しい言語が大好きですが、関数型プログラミングでより多くを稼ぎます」ArsTechnica
  49. ^ ジョンレナード(2017年1月24日)。「関数型プログラミングのステルスな台頭」コンピューティング。
  50. ^ Leo Cheung(2017年5月9日)。「関数型プログラミングはあなたのスタートアップにとってより良いですか?」InfoWorld
  51. ^ 噴水、ディック。「関数型プログラミングは時代の到来」BYTE.com(1994年8月)アーカイブされたオリジナルの2006年8月27日に2006年8月31日取得
  52. ^ a b "ISO / IEC JTC 1 / SC 22 / WG5 / N2137"国際標準化機構。2017年7月6日。 Cite journal requires |journal= (help)
  53. ^ 「アルゴリズム言語スキームに関する改訂^ 6レポート」R6rs.org 2013年3月21日取得
  54. ^ 「アルゴリズム言語スキームに関する改訂^ 6レポート-理論的根拠」R6rs.org 2013年3月21日取得
  55. ^ クリンガー、ウィリアム(1998)。「適切な末尾再帰とスペース効率」。プログラミング言語の設計と実装に関するACMSIGPLAN1998会議の議事録-PLDI'98pp。174–185。土井10.1145 /277650.277719ISBN 0897919874S2CID  16812984
  56. ^ ベイカー、ヘンリー(1994)。「CONSはその議論をCONSすべきではない、パートII:MTAのチェイニー」
  57. ^ ターナー、DA(2004-07-28)。「トータル関数型プログラミング」ユニバーサルコンピュータサイエンスジャーナル10(7):751〜768。土井10.3217 / jucs-010-07-0751
  58. ^ 関数型プログラミング言語の実装サイモンペイトンジョーンズ、プレンティスホール発行、1987年
  59. ^ a b ジョン・ラウンチベリー(1993)。「遅延評価のための自然な意味論」。CiteSeerX 10.1.1.35.2016  Cite journal requires |journal= (help)
  60. ^ ロバートW.ハーパー(2009)。プログラミング言語の実用的な基礎(PDF)2016年4月7日にオリジナル(PDF)からアーカイブされまし
  61. ^ Huet、GérardP。(1973)。「三次論理における統一の決定不可能性」。情報と管理22(3):257–267。土井10.1016 / s0019-9958(73)90301-x
  62. ^ ジェラール・ヒュエット(1976年9月)。Resolution d'Equations dans des Langages d'Ordre 1,2、...ω(Ph.D。)(フランス語)。パリ大学VII。
  63. ^ Huet、Gérard(2002)。「30年後の高階統一」(PDF)カレニョでは、V。; ムニョス、C。; タハール、S。(編)。議事録、第15回国際会議TPHOLLNCS。2410スプリンガー。pp。3–12。
  64. ^ ウェルズ、JB(1993)。「2次ラムダ計算における類型性と型チェックは同等であり、決定不可能です」。技術。担当者93-011CiteSeerX 10.1.1.31.3590 
  65. ^ リロイ、ザビエル(2018年9月17日)。「Compcert検証済みコンパイラ」
  66. ^ ペイトン・ジョーンズ、サイモン; Vytiniotis、Dimitrios; ワイリッヒ、ステファニー; ジェフリーウォッシュバーン(2006年4月)。「GADTの単純な統合ベースの型推論」ICFP 2006:50–61。
  67. ^ 「OCamlマニュアル」caml.inria.fr 2021-03-08を取得
  68. ^ 「代数的データ型」Scalaドキュメント2021-03-08を取得
  69. ^ ケネディ、アンドリュー; ルッソ、クラウディオ(2005年10月)。一般化された代数的データ型とオブジェクト指向プログラミング(PDF)OOPSLAカリフォルニア州サンディエゴ。ISBN  97815959303162006年12月29日にオリジナル (PDF)からアーカイブされまし 引用元
  70. ^ ヒューズ、ジョン。「関数型プログラミングが重要な理由」(PDF)チャルマース工科大学
  71. ^ Chris Okasakiによる純粋関数型データ構造ケンブリッジ大学出版局、1998年、 ISBN 0-521-66350-4 
  72. ^ L'orange、Jean Niklas 「polymatheia-Clojureの永続的なベクトルを理解する、pt.1」ポリマテイア20181113日取得
  73. ^ Newbern、J。「モナドのすべて:Haskellにおけるモナドプログラミングの理論と実践への包括的なガイド」2008年2月14日取得
  74. ^ 「カメを見る13の方法」楽しさと利益のためのfF#20181113日取得
  75. ^ Paulson、Larry C.(1996年6月28日)。働くプログラマーのためのMLケンブリッジ大学出版局。ISBN 978-0-521-56543-12013年2月10日取得
  76. ^ スピワック、ダニエル(2008年8月26日)。「Scalaでの永続的なベクトルの実装」コードコミット
  77. ^ 「どのプログラムが最速ですか?|コンピュータ言語ベンチマークゲーム」ベンチマークゲーム.alioth.debian.org。アーカイブされたオリジナルの2013年5月20日に20116月20日取得
  78. ^ Igor Pechtchanski; Vivek Sarkar(2005)。「不変性仕様とその応用」。並行性と計算:実践と経験17(5–6):639–662。土井10.1002 /cpe.853S2CID 34527406 
  79. ^ 「第25章。プロファイリングと最適化」Book.realworldhaskell.org 20116月20日取得
  80. ^ ハーテル、ピーター; ヘンク・ミュラー; ヒューグレイザー(2004年3月)。「ファンクショナルCエクスペリエンス」(PDF)機能プログラミングジャーナル14(2):129–135。土井10.1017 / S0956796803004817S2CID 32346900  ; デビッドメルツ。「Pythonでの関数型プログラミング、パート3」IBMdeveloperWorks2007年10月16日にオリジナルからアーカイブされまし取得した2006年9月17日をパート1パート2
  81. ^ 「関数—Dプログラミング言語2.0」デジタル火星。2012年12月30日。
  82. ^ 「Lua非公式FAQ(uFAQ)」
  83. ^ 「Goの第一級関数-Goプログラミング言語」golang.org 2021-01-04を取得
  84. ^ アイク、ブレンダン(2008年4月3日)。「人気」
  85. ^ ヴァンロッサム、グイド(2009-04-21)。「Pythonの「機能的」機能の起源」2012年9月27日取得
  86. ^ 「functools—呼び出し可能なオブジェクトに対する高階関数と操作」Pythonソフトウェアファウンデーション。2011-07-31 2011年7月31日取得
  87. ^ Skarsaune、Martin(2008)。SICS Java Port Projectは、SmalltalkからJavaへのラージオブジェクト指向システムの自動翻訳です
  88. ^ ゴスリング、ジェームズ。「クロージャ」James Gosling:JavaRoadでオラクル。アーカイブされたオリジナルの2013年4月14日に検索された11 5月2013
  89. ^ ウィリアムズ、マイケル(2013年4月8日)。「JavaSE8Lambdaクイックスタート」
  90. ^ Bloch, Joshua (2008). "Item 15: Minimize Mutability". Effective Java (Second ed.). Addison-Wesley. ISBN 978-0321356680.
  91. ^ "Object.freeze() - JavaScript | MDN". developer.mozilla.org. Retrieved 2021-01-04. The Object.freeze() method freezes an object. A frozen object can no longer be changed; freezing an object prevents new properties from being added to it, existing properties from being removed, prevents changing the enumerability, configurability, or writability of existing properties, and prevents the values of existing properties from being changed. In addition, freezing an object also prevents its prototype from being changed. freeze() returns the same object that was passed in.
  92. ^ Wakeling, David (2007). "Spreadsheet functional programming" (PDF). Journal of Functional Programming. 17 (1): 131–143. doi:10.1017/S0956796806006186. ISSN 0956-7968. S2CID 29429059.
  93. ^ Peyton Jones, Simon; Burnett, Margaret; Blackwell, Alan (March 2003). "Improving the world's most popular functional language: user-defined functions in Excel". Archived from the original on 2005-10-16.
  94. ^ Piro, Christopher (2009). Functional Programming at Facebook. CUFP 2009. Archived from the original on 2009-10-17. Retrieved 2009-08-29.
  95. ^ "Sim-Diasca: a large-scale discrete event concurrent simulation engine in Erlang". November 2011.
  96. ^ 1 million is so 2011 // WhatsApp blog, 2012-01-06: "the last important piece of our infrastracture is Erlang"
  97. ^ Momtahan, Lee (2009). Scala at EDF Trading: Implementing a Domain-Specific Language for Derivative Pricing with Scala. CUFP 2009. Archived from the original on 2009-10-17. Retrieved 2009-08-29.
  98. ^ Graham, Paul (2003). "Beating the Averages". Retrieved 2009-08-29.
  99. ^ Sims, Steve (2006). Building a Startup with Standard ML (PDF). CUFP 2006. Retrieved 2009-08-29.
  100. ^ Laurikari, Ville (2007). Functional Programming in Communications Security. CUFP 2007. Retrieved 2009-08-29.
  101. ^ Lorimer, R. J. (19 January 2009). "Live Production Clojure Application Announced". InfoQ.
  102. ^ "Functional Programming: 2019-2020". University of Oxford Department of Computer Science. Retrieved 28 April 2020.
  103. ^ "Programming I (Haskell)". Imperial College London Department of Computing. Retrieved 28 April 2020.
  104. ^ a b "Computer Science BSc - Modules". Retrieved 28 April 2020.
  105. ^ a b Abelson, Hal; Sussman, Gerald Jay (1985). "Preface to the Second Edition". Structure and Interpretation of Computer Programs (2 ed.). MIT Press.
  106. ^ John DeNero (Fall 2019). "Computer Science 61A, Berkeley". Department of Electrical Engineering and Computer Sciences, Berkeley. Retrieved 2020-08-14.
  107. ^ Emmanuel Schanzer of Bootstrap interviewed on the TV show Triangulation on the TWiT.tv network

Further reading

External links

Listen to this article (28 minutes)
Spoken Wikipedia icon
This audio file was created from a revision of this article dated 25 August 2011 (2011-08-25), and does not reflect subsequent edits.