純粋関数型プログラミング

コンピュータサイエンスにおいて、純粋関数型プログラミングは通常、すべての計算を数学関数の評価として扱うプログラミングパラダイム（コンピュータプログラムの構造と要素を構築するスタイル）を指します。

プログラム状態と可変オブジェクトは通常、プログラム実行の各ステップでプログラム状態を表す明示的な変数として、時相論理でモデル化されます。変数状態は状態変換関数の入力パラメータとして渡され、更新された状態が戻り値の一部として返されます。このスタイルは、プログラム式の 参照透過性を失うことなく状態の変更を処理します。

純粋関数型プログラミングは、関数パラダイム内の関数が、グローバルまたはローカルの状態に関係なく、引数のみに依存することを保証するものです。純粋関数型サブルーチンは、そのスコープに含まれる状態変数によって表される状態の変化のみを認識できます。

純粋関数型プログラミングと不純関数型プログラミングの正確な違いは議論の的となっている。Sabry が提案した純粋性の定義は、エラーや分岐が発生する戦略を無視して、一般的な評価戦略(名前による呼び出し、値による呼び出し、必要による呼び出し) はすべて同じ結果を生成するというものである。^[1]

プログラムが関数型であると言われるのは、通常、関数型プログラミングの概念、例えば第一級関数や高階関数などを使用しているときです。^[2]しかし、第一級関数は純粋に関数型である必要はありません。なぜなら、副作用として状態を更新する可変セルを使用する配列や入出力メソッドなど、命令型パラダイムの手法を使用している可能性があるからです。実際、関数型であるとされる最も古いプログラミング言語であるIPLとLisp [ ^{3] [4]}は、どちらも Sabry の定義によれば「不純な」関数型言語です。

純粋に機能的なプログラムで終了する各評価戦略は、同じ結果を返します。特に、積極的評価は遅延評価と同じ結果を返すため、プログラマーはプログラムが評価される順序を考慮する必要がありません。ただし、同じプログラムの遅延評価が停止している間に積極的評価が終了しない可能性は依然としてあります。これの利点は、遅延評価をはるかに簡単に実装できることです。すべての式はいつでも同じ結果を返すため (プログラムの状態に関係なく)、それらの評価を必要なだけ遅らせることができます。

純粋関数型言語では、計算間の依存関係はデータ依存関係のみであり、計算は決定論的です。したがって、並列プログラミングを行うには、プログラマは並列に計算する部分を指定するだけでよく、ランタイムはプロセッサへのタスクの分配、同期と通信の管理、ガベージの並列収集など、他のすべての詳細を処理できます。このプログラミングスタイルは、競合状態やデッドロックなどの一般的な問題を回避しますが、命令型言語よりも制御性が低くなります。^[5]

スピードアップを確実にするためには、タスクの粒度が大きすぎたり小さすぎたりしないように慎重に選択する必要があります。理論的には、実行時プロファイリングとコンパイル時分析を使用して、並列化を導入することでプログラムが高速化されるかどうかを判断し、純粋に機能的なプログラムを自動的に並列化することができます。実際には、これはあまり成功しておらず、完全に自動的な並列化は現実的ではありません。^[5]

純粋に関数的なデータ構造は永続的です。関数型プログラミングには永続性が必須です。永続性がなければ、同じ計算で異なる結果が返される可能性があります。関数型プログラミングでは永続的な非純粋に関数的なデータ構造を使用できますが、それらのデータ構造は純粋に関数的なプログラムでは使用できません。

純粋に関数的なデータ構造は、多くの場合、命令 型のデータ構造とは異なる方法で表現されます。^[6]たとえば、 定数時間のアクセスと更新を行う配列は、ほとんどの命令型言語の基本コンポーネントであり、ハッシュテーブルやバイナリヒープなどの多くの命令型データ構造は配列に基づいています。配列は、純粋に関数的な実装が可能なマップまたはランダムアクセスリストに置き換えることができますが、アクセスと更新の時間は対数的です。したがって、純粋に関数的なデータ構造は非関数型言語で使用できますが、特に永続性が要求されない場合は、最も効率的なツールではない可能性があります。

一般に、命令型プログラムを純粋に関数型のプログラムに変換するには、以前は可変だった構造が、それらを更新する関数から明示的に返されるようにする必要もあります。これは、ストア パッシング スタイルと呼ばれるプログラム構造です。

純粋関数型言語は、純粋関数型プログラミングのみを認める言語です。ただし、純粋関数型プログラムは、純粋関数型ではない言語でも記述できます。