コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

「関数型プログラミング」の版間の差分

出典: フリー百科事典『ウィキペディア（Wikipedia）』
履歴の双方向閲覧
← 古い編集
削除された内容 追加された内容
ビジュアルウィキテキスト
 
(24人の利用者による、間の98版が非表示)
1行目: 1行目:
{{独自研究|date=2014年4月}}
[[ファイル:Orange_lambda.svg|代替文=|境界|右|フレームなし|209x209px]]
{{プログラミング・パラダイム}}
{{プログラミング・パラダイム}}
'''関数型プログラミング'''（かんすうがたプログラミング、{{lang-en-short|functional programming}}）とは、[[関数 (数学)|数学的な意味での関数]]を主に使うプログラミングのスタイルである<ref name="名前なし-1">{{harvnb|本間|類地|逢坂|2017|p=3}}</ref>。 functional programming は、'''関数プログラミング'''（かんすうプログラミング）などと訳されることもある<ref name="名前なし-2">{{harvnb|本間|類地|逢坂|2017|p=2}}</ref>。


{{Visible anchor|'''関数型プログラミング言語'''|関数型言語|FP}}（{{lang-en-short|functional programming language}}）とは、関数型プログラミングを推奨している[[プログラミング言語]]である<ref name="名前なし-1"/>。略して'''関数型言語'''（{{lang-en-short|functional language}}）ともいう<ref name="名前なし-1"/>。
'''関数型言語'''（{{lang-en-short|''functional language''}}）は、'''関数型プログラミング'''のスタイルまたは[[プログラミングパラダイム|パラダイム]]を扱う[[プログラミング言語]]の総称である。関数型プログラミングは関数定義と関数適用を基礎にした[[宣言型プログラミング]]の一形態であり、関数は[[引数]]への適用から先行式の評価を後続式の適用につなげて終端の[[評価戦略|評価]]を導き出す[[式 (プログラミング)|式]]の[[ツリー構造]]として定義される。式の評価に伴う[[副作用 (プログラム)|副作用]]の発生には大きな注意が払われる。関数は引数ないし返り値として渡せる[[第一級オブジェクト]]として扱われる。


== 概要 ==
関数型プログラミングは[[数理論理学]]と代数系をルーツにし、[[ラムダ計算]]と[[コンビネータ論理]]を幹にして構築され、[[LISP]]言語が実装面の先駆になっている。関数の数学的な純粋性を指向したものは純粋関数型言語と個別に定義されている。[[命令型プログラミング]]言語では単に有用な構文スタイルとして扱われている事が多い。[[高階関数]]、[[第一級関数]]、[[カリー化]]、[[クロージャ]]、[[継続]]、[[イテレータ]]、[[ジェネレータ (プログラミング)|ジェネレータ]]、[[再帰]]、[[型推論]]、[[パターンマッチング]]、[[評価戦略|名前渡し]]、[[遅延評価]]、[[Cons (Lisp)|コンス]]、[[代数的データ型]]、[[ポリモーフィズム|型の多相]]、[[イミュータブル]]、[[モナド (プログラミング)|モナド]]などが{{誰範囲|date=2020年5月|関数型プログラミングの様式項目として挙げられる}}。


関数型プログラミングは、[[関数 (数学)|関数]]を主軸にしたプログラミングを行うスタイルである<ref name="名前なし-1"/>。ここでの関数は、数学的なものを指し、引数の値が定まれば結果も定まるという[[参照透過性]]を持つものである<ref name="名前なし-1"/>。
== 一般的な関数型スタイル ==
最も身近な関数型プログラミングとは、データ集合に対する反復作用であり、リスト処理などと呼ばれているものである。手続き型言語やオブジェクト指向言語において、いわゆる関数型と呼ばれる構文が多用されるのもリスト処理の分野である。関数型思想の原点は「[[LISP]]」であるが、その実用性を知らしめた最初の言語は[[表計算ソフト|表計算]]処理に効率性を発揮した「[[APL]]」であった。リストを走査して各要素を順々に取り出すプロセスと、各要素に作用するプロセスを別々の関数にまとめて、前者に後者を渡すようにした仕組みが一般に言われる関数型の基本例である。他の関数を引数として受け取る事ができる関数は'''[[高階関数]]'''と呼ばれ、引数として渡す事ができる関数は'''[[第一級関数]]'''と呼ばれる。この二つの機能が関数型の支柱である。そのようなスタイルとしての意味での関数型プログラミングにおける代表的な機能または構文には以下のようなものが挙げられる。


'''参照透過性'''とは、数学的な関数と同じように同じ値を返す式を与えたら必ず同じ値を返すような性質である<ref name="名前なし-1"/>。次の <code>square</code> 関数は、 <code>2</code> となるような式を与えれば必ず <code>4</code> を返し、 <code>3</code> となるような式を与えれば必ず <code>9</code> を返し、いかなる状況でも別の値を返すということはなく、これが参照透過性を持つ関数の一例となる<ref name="名前なし-1"/>。
'''ラムダ式''' / '''[[無名関数]]''' / '''[[クロージャ]]'''
: ラムダ式と無名関数は同じものである。無名関数は<code>引数→式</code>（例：<code>x→x+1</code>）の形式で表現され、与えられた引数を加工して結果値を返す働きをする。高階関数への引数として使われることが多い。無名関数の式内に外部データを含んだものはクロージャと呼ばれる。クロージャの結果値はその時の外部データの状態に左右される事になる。


<syntaxhighlight lang="python" >
'''map''' / '''filter''' / '''reduce'''
def square(n):
: リスト処理用の高階関数であり、対象リストと無名関数を引数にする。mapはリスト内の各要素を無名関数の結果値に置き換える高階関数である。filterはリスト内の各要素を無名関数の真偽判定値で真なら抽出し、その抽出要素のリストを生成する高階関数である。reduceはリスト内の各要素の総和の結果値を生成する高階関数である。reduceの無名関数は前要素までの総和と現要素の二引数を取る。総和の和は和に限らず無名関数内で好きな計算にできる。
return n ** 2
</syntaxhighlight>


次の <code>countup</code> 関数は、同じ <code>1</code> を渡しても、それまでに <code>countup</code> 関数がどのような引数で呼ばれていたかによって、返り値が <code>1</code>, <code>2</code>, <code>3</code>, ... と変化するため、引数の値だけで結果の値が定まらないような参照透過性のない関数であり、数学的な関数とはいえない<ref name="名前なし-1"/>。
'''名前渡し''' / '''[[遅延評価]]'''
: 引数を当てはめた無名関数（コードブロックまたはプロセス）を未計算のまま高階関数に渡せる仕組みを名前渡しという。予め組み立てた想定プロセスを全て高階関数に渡しておき、その高階関数側で必要になったプロセス結果値だけを求めるようにして計算量を減らすのが主な用途になる。引数確定時とは別タイミングで計算することを遅延評価という。遅延評価では高階関数側で無名関数の確定引数を設定し直したり、[[クロージャ]]ならばその時の計算タイミングの外部データ状態に従った結果値を得ることが可能になる。


<syntaxhighlight lang="python" >
'''[[型推論]]'''
counter = 0
: [[命令型プログラミング|命令型プログラミング言語]]での型推論は、ローカル変数の型宣言/型注釈を省略することで表現に幅を持たせるための[[糖衣構文]]に近い機能と考えてよい。[[テンプレート (プログラミング)|型テンプレート]]的な表現の幅である。[[プリミティブ型|リテラル]]（数値/実数/文字列）および文脈上で型が明確な[[インスタンス]]の初期代入は、同時に対象変数の型注釈になると再考されたことに基づいている。従来の{{仮リンク|明示的型付け|en|Manifest typing|label=}}（型宣言/型注釈の使用）と[[型推論]]の共存は、C言語世代プログラミングに対する一つのパラダイムシフトでもある。
def countup(n):
global counter
counter += n
return counter
</syntaxhighlight>


関数型プログラミングは、参照透過性を持つような数学的な関数を使って組み立てた'''式'''が主役となる<ref name="名前なし-1"/>。別の箇所に定義されている処理を利用することを、手続き型プログラミング言語では「関数を実行する」や「関数を呼び出す」などと表現するが、関数型プログラミング言語では「式を評価する」という表現も良く使われる<ref name="名前なし-3">{{harvnb|本間|類地|逢坂|2017|p=4}}</ref>。
== 特徴 ==
{{出典の明記| date = 2020年5月6日 (水) 02:29 (UTC)| section = 1}}
ここでは関数型プログラミング本来の考え方（[[プログラミングパラダイム|パラダイム]]）に基づいて説明する。[[文 (プログラミング)|ステートメント]]を基本文にする[[命令型プログラミング|命令型言語]]と、[[式 (プログラミング)|式]]を基本文にする関数型言語はどちらも最終的には[[命令型プログラミング|命令型パラダイム]]に沿った[[機械コード]]に落とし込まれる事になるが、双方の間にはプログラミングに対する考え方に比較的大きな隔たりがあると言える。


=== 式と関数 ===
=== 参照透過性 ===
関数型プログラムの基本文は[[式 (プログラミング)|式]]（''expression''）である。式は個体（''individual''）である値（''value''）と写像（''mapping''）である関数（''function''）の二つから構成される。関数の定義には[[演算子]]（''operator''）も含まれている。値は[[基本データ型]]（プリミティブ）と{{仮リンク|複合データ型（コンポジット）|en|Composite data type|label=}}および[[ラムダ計算]]で言われる変数（''variable''）を意味する。変数は[[束縛変数]]と[[自由変数と束縛変数|自由変数]]を指す。評価（''evaluation''）される前の式は、ラムダ計算で言われるネーム（''name''）と同義になる。ネームは数学上の数式または代数式に相当するものである。式内の変数部分が確定される前の式はラムダ抽象（''abstraction''）と同義になる。式内の変数部分を確定するのはラムダ適用（''application''）と同義になる。この式＝ネームが評価されると値になり、これはラムダ計算で言われる簡約（''reduction''）と同義になる。式は値と同一視されるのですなわち式と値は相互再帰の関係にある。式内の値は他の式の評価値である事があり、その式内にもまた他の値があるといった具合である。この解釈は[[高階論理|高階述語論理]]''と呼ばれる。高階述語論理＝[[高階関数]]の解釈下で引数または返り値として扱われる関数は[[第一級関数]]と呼ばれる。''


{{main|参照透過性}}
関数型プログラミングの関数は’’関数の型’’（''function type''）で分類される[[存在量化子|存在量]]の値である。プログラム的には式に引数を結び付ける機能であり、これは関数を引数に[[写像|適用]]する（''applying a function to an argument''）とされる。関数の式内の仮引数（''parameter''）箇所に渡された実引数（''argument''）が[[パターンマッチング]]手法で当てはめられ、先行（その時）または遅延（その後）タイミングで評価されて結果値が導出される。この仮引数箇所は束縛変数と呼ばれる。関数呼び出し時とは異なるタイミングで内容が決定される変数箇所は自由変数と呼ばれる。letとwhereで特定の式に向けて定義される変数は、その式への束縛変数になる。関数型での自由変数の意味合いは他の[[宣言型プログラミング|宣言型パラダイム]]とは異なっている。パターンマッチング手法は、関数にそれぞれ異なる引数パターン候補の[[選言]]列挙を可能にさせておりこれは[[多重定義|関数オーバーロード]]と同義の機能になる。[[パターンマッチング]]は非交和型による等価性（''equivalent''）区別と、それ以外の等値性（''equality''）区別では引数値の組み合わせ照合とそれにワイルドカードを用いた部分的総称化照合で行われ、更にそれに[[ガード (プログラミング)|ガード]]と呼ばれる値の比較照合と範囲照合を加えることもできる。渡される実引数によっては[[ボトム型]]になる関数もありこれは部分関数（''partial function''）と呼ばれる。ボトム型は式ないし関数の評価の失敗した終着点を意味する。演算子はデフォルトの式内容を持ち、その引数が単項演算子なら1個、二項演算子なら2個に限定された関数と同義である。


参照透過性とは、同じ値を与えたら返り値も必ず同じになるような性質である<ref name="名前なし-1"/>。参照透過性を持つことは、その関数が'''状態を持たない'''ことを保証する<ref name="名前なし-4">{{harvnb|本間|類地|逢坂|2017|p=5}}</ref>。状態を持たない数学的な関数は、並列処理を実現するのに適している<ref name="名前なし-4"/>。関数型プログラミング言語の内で、全ての関数が参照透過性を持つようなものを純粋関数型プログラミング言語という<ref name="名前なし-4"/>。
’’関数の型’’は「第1引数の型→第x引数の型→評価値の型」というように形式化されておりこれはカリー化（''currying''）と呼ばれる。例として関数funcの型を<code>func::A→B→C</code>とするとこの場合、A型値に適用されたfuncは<code>B→C</code>という’’関数の型の値’’を返す事になり、それをB型値に適用するとC型の評価値が返る事になる。左からの引数にひとつひとつ適用する形にして、<code>B→C</code>のような中間的な’’関数の型の値’’が導出されるようにする仕組みが関数の[[カリー化]]である。カリー化は写像の[[量化]]（''quantify''）を扱う[[二階述語論理]]の実装である。カリー化によって関数funcの型は<code>func::A→(B→C)</code>と読み替えられるようになり、この場合にAにのみ適用して<code>B→C</code>という’’関数の型の値’’のまま保留することは部分適用（''partial application''）と呼ばれる。またカリー化による重要概念に関数合成（''function composition''）がある。これは合成演算子<code>.</code>（専用の二項演算子）を関数<code>f::B→C</code>に適用すると<code>(＊→B)→(＊→C)</code>が導出され、それを関数<code>g::A→B</code>に適用すると<code>(A→B)→(A→C)</code>となり関数<code>f . g::A→C</code>が導出されるというものである。合成演算子の左側の[[定義域]]と右側の[[値域]]が同じ型の場合のみ合成できる。高階関数的な連結である<code>f (g A)</code>と働きかた的には同じであるが、[[パイプライン処理]]の方に該当する関数連結（関数チェーン）と、カリー化に則った関数合成は異なる概念である。カリー化による部分適用や合成演算子から導出された’’関数の型の値’’を任意の変数に束縛して扱うのはポイントフリースタイル（''point-free style''）と呼ばれる。ポイントフリースタイルの変数を値に適用すると、他の値が返されるか又は他の’’関数の型の値’’が返される事になる。引数を部分適用された演算子はセクションと呼ばれてポイントフリースタイルでよく用いられる。[[カリー化]]準拠の’’関数の型’’は[[型理論]]の指数型（''quotient type''）に分類されるものである。


=== 入出力 ===
関数は名前付きと名前無しの二通りある。名前無しの関数は専らラムダ抽象を模した構文で定義される。式内に自由変数を内包しない方は単に[[無名関数]]と呼ばれ、自由変数を内包する方はそれを囲い込むという意味で[[クロージャ]]と呼ばれる。自由変数は外部データへの接点になる。[[無名関数]]は引数をピュア[[写像|マッピング]]する純粋関数である。[[クロージャ]]の引数の[[写像|マッピング]]は式内の自由変数に影響され、またその自由変数に作用する事もあるという副作用要素を閉包した非純粋関数である。リスト処理時にリストの各要素への作用子として渡される無名関数またはクロージャは[[反復子|イテレータ]]と呼ばれる。同様にリスト処理時に渡されて各要素を参照しながらそれらの総和値または選別リストまたは更新リストを生成する方は[[ジェネレータ (プログラミング)|ジェネレータ]]と呼ばれる。これは[[イミュータブル]]重視時に多用される。関数の名前は、それに結び付けられた式または式ツリーの[[不動点]]の表現になる。自式の不動点を式内に置いて新たな引数と共に[[高階論理|高階述語論理]]の式として評価する手法は[[再帰]]と呼ばれる。関数の終端式での再帰は実引数の更新＋先端式へのアドレスジャンプと同等に見なせるのでもっぱらそちらに最適化されてこれは[[末尾再帰]]と呼ばれる。末尾再帰は論理性を損なわずにスタックフリーの無制限ループを可能にする実装概念として重視されている。


関数型プログラミングでは、数学的な関数を組み合わせて計算を表現するが、それだけではファイルの読み書きのような外界とのやり取りを要する処理を直接的に表現できない<ref name="名前なし-5">{{harvnb|本間|類地|逢坂|2017|p=6}}</ref>。このような外界とのやり取りを '''I/O (入出力)''' と呼ぶ<ref name="名前なし-5"/>。数学的な計算をするだけ、つまり <code>1 + 1</code> のようなプログラム内で完結する処理ならば、入出力を記述できなくても問題ないが、現実的なプログラムにおいてはそうでない<ref name="名前なし-5"/>。
=== 値とデータストラクチャ ===
関数型プログラミングの値（''value''）は型（''type''）で分類される[[定数 (プログラミング)|定数]]または[[全称量化子|全称量]]の[[変数 (プログラミング)|変数]]である。これは[[基本データ型]]（プリミティブ）と{{仮リンク|複合データ型（コンポジット）|en|Composite data type|label=}}のいずれかで表現される。プリミティブは数値、論理値、文字値、文字列を指す。様々なプリミティブを様々な形式で組み合わせたものがコンポジットであり、その例はC言語の[[構造体]]や[[共用体]]などである。その組み合わせ方に焦点を当てた用語が[[データ構造|データストラクチャ]]（''data structure''）である。データストラクチャという概念には[[再帰]]構造、[[アノテーション]]付き構造、[[ガード (プログラミング)|ガード]]付き構造、[[操作的意味論|操作的意味]]付き構造といった様々な暗黙情報を含められるので、コンポジットの具体的形式といった意味で用いられる。関数型言語で用いられるデータストラクチャの代表は[[代数的データ型]]と[[S式]]である。双方ともデータ構築子（''data constructor''）から構築される。まず、プリミティブがデータ構築子によってまとめられる。正確ではないがデータ構築子はC言語の構造体または共用体と同じものと見てよい。データ構築子は入れ子にできるので、データ構築子をまとめたデータ構築子も定義できる他、同名データ構築子を入れ子にした再帰構造も定義できる。プリミティブとデータ構築子を任意に組み合わせて代数的データ型やS式といったデータストラクチャが構築される。データストラクチャ内のプリミティブとデータ構築子の組み合わせ方はパターン（''pattern''）と呼ばれる。そのパターンが型になり、パターンの構築が型付けになり、パターンを[[量化]]（''quantify''）すると型付け値になり、これはターム（''term''）と呼ばれる。タームは冒頭の値（''value''）を指す。データ構築子のパターンの末端は必ずプリミティブになるので、パターン内の全てのプリミティブの値を決定することが量化になる。お互いのパターンがマッチするターム同士は等価（''equivalent''）とされる。この等価は同じ型と読み替えてもよい。等価性はあらゆる計算の可否（計算可能性）を決定する。計算とは関数適用または演算子適用を指し、それらが求める仮引数と実引数にするタームが等価であればその計算は成立する事になる。データストラクチャのパターンは基礎パターンに分解されて解釈される。基礎パターンは[[型理論]]に従って直積型、非交和型、ユニオン型、オプション型、帰納型、ユニット型などに分類されている。


非純粋な関数型プログラミング言語においては、式を評価すると同時に I/O が発生する関数を用意することで入出力を実現する<ref name="名前なし-5"/>。たとえば、 [[F Sharp|F# 言語]]では、<code>printfn "Hi."</code> が評価されると、 <code>()</code> という値が戻ってくると同時に、画面に <code>Hi.</code> と表示される I/O が発生する<ref name="名前なし-5"/>。
[[S式]]は[[二分木|二分木構造]]のデータストラクチャである。これはコンス（''cons''）と呼ばれる二項のデータ構築子の連結で形成される。コンスは二つの要素を持つ[[タプル]]であり、要素はプリミティブまたは他のコンスのどちらかである。S式はコンスを実行時に連結して任意のパターンを構築する[[動的型付け]]の値である。コンスは要素二つの[[直積集合|直積型]]（''product type''）であり、コンスの連結による要素の並びは[[線形リスト|リスト]]と呼ばれる。コンスの要素は形式化されていない[[非交和|非交和型]]（''sum type''）でもあり、要素の識別はプログラマ側の裁量に委ねられている。コンスの組み合わせによるパターンは任意の識別名に結び付けられる。


[[Haskell]] では、評価と同時に I/O が行われる関数は存在しない<ref name="名前なし-5"/>。たとえば、 <code>putStrLn "Hi."</code> という式が評価されると <code>IO ()</code> 型を持つ値が返されるが画面には何も表示されず、この値が Haskell の処理系によって解釈されて初めて画面に <code>Hi.</code> と表示される<ref name="名前なし-5"/>。 '''I/O アクション'''とは、ファイルの読み書きやディスプレイへの表示などのような I/O を表現する式のことである<ref name="名前なし-5"/><ref>{{harvnb|本間|類地|逢坂|2017|p=23}}</ref>。 <code>IO a</code> という型は、コンピュータへの指示を表す I/O アクションを表現している<ref name="名前なし-5"/><ref>{{harvnb|本間|類地|逢坂|2017|p=31}}</ref>。ここでの <code>IO</code> は[[モナド (プログラミング)|モナド]]と呼ばれるものの一つである<ref>{{harvnb|本間|類地|逢坂|2017|p=32}}</ref>。
[[代数的データ型]]は{{仮リンク|AND-OR木構造|en|And–or tree|label=}}のデータストラクチャである。これは[[直積集合|直積型]]（''product type''）または[[非交和|非交和型]]（''sum type''）を表現する多項のデータ構築子の組み合わせで形成される。データ構築子は任意個数の要素を持つものであり、要素はプリミティブまたは他のデータ構築子のどちらかである。代数的データ型はデータ構築子を事前に組成定義して任意のパターンを構築する[[静的型付け]]の値である。直積型は[[タプル]]または[[構造体|レコード]]のパターンを表わす。レコードは指定フィールド取得用関数を随伴させたものである。非交和型は[[列挙型]]または[[共用体|タグ共用体]]のパターンを表わす。前者は等値性（''equality''）で識別される非交和である。後者は等価性（''equivalent''）で識別される非交和であり、こちらはユニオン型（''union type''）とも呼ばれる。ユニット型（''unit type''）は空集合のパターンを表わし、実装面ではnilまたはvoidの表現になる。ユニット型とそうでない型の二択の非交和型はオプション型（''option type''）とされ、実装面ではMaybe値の表現になる。データ構築子を再帰的にネスティングするパターンは帰納型（''inductive type''）とされる。非交和型と帰納型とユニット型の組み合わせは[[連結リスト]]や[[二分木]]のパターンを表わす。データ構築子の組み合わせによるパターンは任意の型構築子（''type constructor''）に結び付けられて同時にそれが識別名義になる。データ構築子がパターンの表現に用いられるのに対して、型構築子はパターン内の要素（プリミティブないしデータ構築子）の多相化に用いられる。多相化はパターン内の要素を型変数（''type variable''）に置き換え、型構築子への型引数（''type parameter''）で要素の型を決定するという形で行われる。型構築子が必要とする型引数の個数および形態によるパターンは[[カインド (型理論)|カインド]]（''kind''）と呼ばれる。型構築子はカインドによって分類される。代数的データ型は識別名義と構成内容を分離して双方を自由に組み合わせるという意味でしばしば抽象化される。これは型構築子名に他の型構築子名を結び付ける仕組みで実現され、型シノニムまたは型エイリアスと呼ばれる。


[[Clean]] では、一意型を用いて入出力を表す。
=== 評価戦略 ===
関数型プログラミングの[[評価戦略]]（''evaluation strategy''）は、関数を値にする評価タイミングと、引数欄内関数の評価タイミング（''call-by-What''）の二つを定義している。関数を値にする評価タイミングは、正格評価（''strict evaluation''）と非正格評価（''non-strict evaluation''）の二つに大別されている。正格評価の関数は引数確定と同時に評価されて値になる。この評価タイミングに注目した方は[[先行評価]]（''eager evaluation''）と呼ばれる。引数確定と同時に[[ボトム型]]（評価失敗）が発生することも包括した呼称が正格評価である。非正格評価の関数は、引数確定されても未評価のまま保留状態にされる。後続式で改めて他の関数/演算子の引数にされた時に初めて評価されて値になり、または改めて変数に束縛された時に初めて評価されて値になる。この評価タイミングに注目した方は[[遅延評価]]（''lazy evaluation''）と呼ばれる。評価されるまでボトム型の発生が保留されることも包括した呼称が非正格評価である。これが遅延評価のデフォルトタイミングであるが、好きなタイミングで遅延評価できる無名関数/クロージャもあり、それは[[継続]]（''continuation''）と呼ばれる。その任意タイミングの評価値導出はcall/cc（現行継続呼出）と呼ばれる。遅延評価は必要以外の評価をスキップして処理を高速化するが、評価値と未評価関数の区別が難しくなるというジレンマがある。


=== 手法 ===
引数欄内関数の評価タイミング（''call-by-What''）には、値渡し（''call by value''）と名前渡し（''call by name''）がある。値渡しは先行評価に相当するものであり、関数の評価値が引数として渡される。名前渡しは遅延評価に相当するものであり、未評価のまま保留された関数が引数として渡される。なお、双方ともに引数確定されていない場合はただの第一級関数（関数の型の値）として渡されることになる。また名前渡しの亜流に必要渡し（''call by need''）があり、これは一度名前渡しされた関数＋引数はその評価値を[[メモ化]]されて、同じ関数＋引数が再度名前渡しされた時はそのメモ化評価値の方を渡すという仕組みである。必要渡しは純粋関数型言語で実装されている。


{{節スタブ|1=[[モナド (プログラミング)|モナド]]・[[永続データ構造]]|date=2021年3月}}
データストラクチャでも遅延評価の概念は扱われており、[[帰納]]、[[再帰]]、[[無限]]、[[極限]]といった代数表現の実装手段になっている。代数的データ型では[[共用体|タグ共用体]]、[[線形リスト|連結リスト]]、[[再帰データ型]]は遅延評価対象である。連結リストは無限リストと構造上同義であり遅延評価が無限性質の実装を可能にしている。


最初に解の集合となる候補を生成し、それらの要素に対して1つ（もしくは複数）の解にたどり着くまで関数の適用とフィルタリングを繰り返す手法は、関数型プログラミングでよく用いられるパターンである<ref name="名前なし-6">{{harvnb|Lipovača|2012|p=22}}</ref>。
=== 参照透過性 ===
[[参照透過性]]（''referential transparency''）とは、関数は同じ引数値に対する同じ評価値を恒久的に導出し、その評価過程において現行計算枠外の情報資源に一切の影響を及ぼさないというプロセス上の枠組みを意味する。現行計算枠外のいずれかの情報資源が変化するのと同時にいずれかの関数の評価過程も変化してしまう現象が[[副作用 (プログラム)|副作用]]（''side effect''）と呼ばれる。参照透過性＝副作用の排除でもある。副作用を持たない関数を純粋関数（''pure function''）と呼ぶ。副作用の代表例は値の再代入と入出力処理である。参照透過性が完全順守されたプログラムでは、あらゆる個体（値）と写像（関数）のつながりが初期宣言値まで遡れるようになる。宣言値からのあらゆる値をつなぐ写像の履歴の図表であるプロセス[[有向グラフ]]の解析と模型化は、[[プロセス代数]]と呼ばれ[[並行プログラミング]]などの支柱になる。関数型プログラミングの世界で値の再代入がタブーとされるのは、それが写像の履歴の改ざんになってプロセス有向グラフの整合性を崩壊させるからである。従ってある時点の値をただ書き留めておく[[束縛変数]]と、旧値の更新を新値の産出で代替した[[イミュータブル]]が重視される。ループは関数の[[再帰]]で表現され、分岐は[[選言]]パターンマッチングなどで表現される。参照透過性を維持しながら入出力処理を行うための機能には、派生構造型システム（''substructural type system''）と[[モナド (プログラミング)|モナド]]（''monad''）がある。


Haskell では、関数合成の二項演算子を使って'''ポイントフリースタイル'''で関数を定義することができる<ref name="名前なし-6"/>。関数をポイントフリースタイルで定義すると、データより関数に目が行くようになり、どのようにデータが移り変わっていくかではなく、どんな関数を合成して何になっているかということへ意識が向くため、定義が読みやすく簡潔になることがある<ref name="名前なし-6"/>。関数が複雑になりすぎると、ポイントフリースタイルでは逆に可読性が悪くなることもある<ref name="名前なし-6"/>。
参照透過性が保証されたプロセス[[有向グラフ]]は、{{仮リンク|プルーフアシスタント|en|Proof asistant|label=}}による[[正当性 (計算機科学)|プログラム正当性]]の[[形式的検証]]および[[数学的証明]]を可能にする。参照透過性を完全順守するには、各種入出力に伴う副作用の論理的排除も必要なので専用のランタイム環境上での動作が必須になる。ランタイム環境は「コンテキスト」を走行プログラムとの仲介にする。プログラムは専用IDを内包するコンテキストに作用するという形式で各種入出力を行う。コンテキストへの仮想的入出力は、ランタイム環境側によって実際に実行される。その入出力で変化したランタイム環境が反映された新生IDを内包するコンテキストがプログラム側に渡される。コンテキストIDが毎時ユニーク生成される仕組みは、派生構造型システムのライナ―型（''linear type''）と呼ばれる。コンテキストに対象値を注入する仕組みはアフィン型（''affine type''）、コンテキストから対象値を抽出する仕組みは関連型（''relevant type''）と呼ばれる。毎時ユニーク生成されるライナー型IDは、各種入出力に伴う副作用によって実際には変化しているランタイム環境の時系列状態を完全に抽象化して、それらを理論上各個照会可能にしているマッピングキーである。これによってランタイム環境の変化もプロセス有向グラフで論理的に辿れることになるので同時に参照透過性も維持されていることになる。派生構造型システムの実装例にユニークネス型（''uniqueness type''）がある。ライナー型、アフィン型、関連型を組み合わせての特にその応用コーディングは煩雑なボイラープレートコードになりがちだったので、それらを[[圏論]]視点の[[関手]]の合成といった仕組みでより平易かつ簡潔にした手法が[[モナド (プログラミング)|モナド]]である。


=== 型システム ===
=== 言語 ===
{{型システム}}
関数型プログラミングの[[型システム]]（''type system''）は、[[型付きラムダ計算|型付けラムダ計算]]準拠の[[型理論]]に基づいて構築されている。ここでは型システム上の対比に沿った形で記述する。関数型言語の二大系統の内、[[ML (プログラミング言語)|ML系]]は[[静的型付け]]ベースであり、[[LISP|LISP系]]は[[動的型付け]]ベースである。


関数型プログラミング言語とは、関数型プログラミングを推奨している[[プログラミング言語]]である<ref name="名前なし-1"/>。略して関数型言語ともいう<ref name="名前なし-1"/>。全ての関数が参照透過性を持つようなものを、特に{{仮リンク|純粋関数型プログラミング言語|en|purely functional programming language}}という<ref name="名前なし-4"/>。そうでないものを非純粋であるという<ref name="名前なし-5"/>。
'''静的型付け'''


関数型プログラミング言語の多くは、言語の設計において何らかの形で[[ラムダ計算]]が関わっている<ref name="名前なし-3"/>。ラムダ計算はコンピュータの計算をモデル化する体系の一つであり、記号の列を規則に基づいて変換していくことで計算が行われるものである<ref name="名前なし-3"/>。
関数型言語の静的型付けでは、性質や役割による[[セマンティクス|意味づけ]]によって値を分類する明示的型付け（''manifest typing''）よりも、計算可能性に基づく[[等価性]]によって値を分類する推論的型付け（''inferred typing''）が主流である。前者の意味づけとはプログラマによる型定義、型宣言、型注釈を指しており人間寄りの視点である。後者の等価性とは値を関数/演算子の引数にできるかどうかの判別を指し、値への関心がそこで計算可能かどうかに絞られているので計算機寄りの視点である。明示的型付けではソースコード上の型宣言と型注釈から値の型が特定されるのに対し、推論的型付けでは[[型推論]]機能で特定される。型推論とはソースコードの解析によって値それぞれの等価性を導き出す機能である。数値や文字列といったリテラルはそのまま特定され、変数などのシンボルはその扱われ方や、任意の[[等式]]を並べて定義した法則からの分析によって型（=等価性）が特定されるといった具合である。推論的型付けでは値への関心をその計算可能性に絞っているので、型宣言と型注釈は必要とされなくなる。例としてint型を型シノニムで金額型と数量型にした場合、明示的型付けではこの両者は区別されるが、推論的型付けでは区別されない。ソースコードの解析でどちらもint型準拠の等価と見られるからである。推論的型付けで値の意味づけ性も表現する場合は、データ構築子で値を包む[[ボックス化]]が用いられる。データ構築子（''data constructor''）は与えられた要素を直積または非交和でまとめるのと同時に[[型理論]]で言われる文脈（''context''）を各要素の等価性に上乗せ付加するものでもある。


{| class="wikitable sortable"
静的型付けにおける[[データ構造|データストラクチャ]]のパターン（型）はコンパイル前ないし実行前に全て事前形成される。その実装例である[[代数的データ型]]はデータ構築子の組み合わせでパターンを構築し、パラメトリック多相に基づいて[[ジェネリックプログラミング|総称化]]したパターン内の要素＝型変数を、型構築子への型引数の組み合わせで特定した。''Hindley–Milner''型体系はこのパラメトリック多相に対応した[[型推論]]機能を提供している。型構築子（''type constructor''）は必要とする型引数の個数によって分類され、これは[[カインド (型理論)|カインド]]（''kind''）と呼ばれる。カインドは総称記号である<code>＊</code>の写像で型構築子の型種を表現する。型引数を必要としない型構築子と必要な型引数を全て付与された型構築子はプロパータイプと呼ばれ<code>＊</code>と表現される。プロパータイプは[[全称量化子|全称量]]の型である。型引数を1個必要とするものは<code>＊→＊</code>になり、2個必要なら<code>＊→＊→＊</code>になる。これらは[[存在量化子|存在量]]の型になる。<code>＊→＊→＊</code>に型引数が1つ付与されると<code>＊→＊</code>になり更に1つ付与すると<code>＊</code>のプロパータイプになる。全称量の型付け値（ターム）は普通に扱えるが、存在量の型付け値はその一部分が抽象化（大抵は環境依存値と同義）されたままの特別な値と見なされて一定の制限下で扱われる。
|+ 関数型プログラミング言語
|-
! 名前
! 型付け
! 純粋性
! 評価戦略
! 理論的背景
|-
| [[Clean]]
| 静的型付け
| 純粋
| 遅延評価
|
|-
| [[Elm (プログラミング言語)|Elm]]
| 静的型付け
| 純粋
| 正格評価
|
|-
| [[Erlang]]
| 動的型付け
| 非純粋
| 正格評価
|
|-
| [[F Sharp|F#]]
| 静的型付け
| 非純粋
| 正格評価
|
|-
| [[Haskell]]<ref name="名前なし-2"/>
| 静的型付け<ref name="名前なし-2"/>
| 純粋<ref name="名前なし-2"/>
| 遅延評価<ref name="名前なし-2"/>
| 型付きラムダ計算<ref name="名前なし-3"/>
|-
| [[Idris (プログラミング言語)|Idris]]
| 静的型付け
| 純粋
| 正格評価
| 型付きラムダ計算
|-
| [[Lazy K]]
| 型なし
| 純粋
| 遅延評価
| コンビネータ論理
|-
| [[LISP|LISP 1.5]]<br>[[Scheme]]<br>[[Common Lisp]]<br>[[Clojure]]
| 動的型付け
| 非純粋
| 正格評価
| 型無しラムダ計算<ref name="名前なし-3"/>
|-
| [[LISP]]の各種方言<ref name="名前なし-3"/>
| 方言による
| 方言による
| 方言による
|
|-
| [[Miranda]]
| 静的型付け
| 純粋
| 遅延評価
|
|-
| [[ML (プログラミング言語)|ML]]<br>[[Standard ML]]<br>[[OCaml]]
| 静的型付け
| 非純粋
| 正格評価
|-
| [[Scala]]
| 静的型付け
| 非純粋
| 正格評価
|
|-
| [[Unlambda]]
| 型なし
| 非純粋
| 正格評価
| コンビネータ論理
|-
|[[Lean (証明アシスタント)|Lean]]
|静的型付け
|純粋
|正格評価
|型付きラムダ計算
|}


=== 手続き型プログラミングとの比較 ===
推論的型付け下の関数の扱いでは、人為的表記による意味づけを重視した記名的型付け（''nominal typing''）が取り入れられており、これで推論的型付けの枠組み内での[[多重定義|関数オーバーロード]]が表現されている。ここでの人為的表記による意味づけとは、型構築子/データ構築子/関数の型それぞれのパターン内の型変数に、[[型理論]]で言われる文脈（''context''）を付加することを指している。文脈の付加は制約（''constraint''）と呼ばれる。文脈の付加はアドホック多相と考えられており、代表的な実装例はそれと[[ジェネリックプログラミング]]を組み合わせた[[型クラス]]である。型クラスは、引数/計算値/評価値などを[[総称型]]化したジェネリック関数群を定義できる機能であり、同時に推論的型付けと共存する関数オーバーロードの実装と、特定の意味づけ型を扱うための関数モジュールを定義するための手段になっている。型クラスの定義構文では上述のジェネリック関数群が定義され、その型クラス名が文脈記号になる。型構築子の定義に文脈を付加すると、その型クラスのジェネリック関数群にその型構築子＝型を当てはめた関数群がコンパイル時に自動生成される（deriving）。また文脈を付加して当てはめ関数群を自動生成（instance）した上で、その型構築子＝型のための当てはめ関数も個別定義（where）できる構文もある。この双方がジェネリック関数の特有インスタンス化になる。明示的型付けでは型注釈を付けた引数パターンの列挙というシンプルな手段で関数オーバーロードを表現できるが、推論的型付けでは等価性に上乗せした文脈という二段階の手段が必要になる。記名的型付けと併せた推論的型付けでのオーバーローディング関数の選択決定は、始めに仮引数と実引数の型クラスのみに注目した照合が行われ、次にその型クラスの制約内での型推論照合が行われるという形になる。


[[C|C 言語]]や [[Java]] 、 [[JavaScript]] 、 [[Python]] 、 [[Ruby]] などの2017年現在に使われている言語の多くは、手続き型の文法を持っている<ref name="名前なし-7">{{harvnb|本間|類地|逢坂|2017|p=22}}</ref>。そのような言語では、文法として式 (expression) と文 (statement) を持つ<ref name="名前なし-7"/>。ここでの式は、計算を実行して結果を得るような処理を記述するための文法要素であり、加減乗除や関数呼び出しなどから構成されている<ref name="名前なし-7"/>。ここでの文は、何らかの動作を行うようにコンピュータへ指示するための文法要素であり、条件分岐の [[if文|if 文]]やループの [[for文|for 文]]と [[while文|while 文]]などから構成されている<ref name="名前なし-7"/>。手続き型の文法では、式で必要な計算を進め、その結果を元にして文でコンピュータ命令を行うという形で、プログラムを記述する<ref name="名前なし-7"/>。このように、[[手続き型言語]]で重要なのは文である<ref name="名前なし-7"/>。
'''動的型付け'''


それに対して、[[関数型言語]]で重要なのは式である<ref name="名前なし-7"/>。関数型言語のプログラムはたくさんの式で構成され、プログラムそのものも一つの式である<ref name="名前なし-7"/>。たとえば、 Haskell では、プログラムの処理の記述において文は使われず、外部の定義を取り込む import 宣言も処理の一部として扱えない<ref name="名前なし-7"/>。関数型言語におけるプログラムの実行とは、プログラムを表す式の計算を進めて、その結果として値 (value) を得ることである<ref name="名前なし-7"/>。式を計算することを、'''評価する''' (evaluate) という<ref name="名前なし-7"/>。
動的型付けにおける[[データ構造|データストラクチャ]]のパターン（型）はコンパイル前ないし実行前の事前形成に加えて、実行中の随時にも事後形成できる。その実装例である[[S式]]は、二項データ構築子（[[Cons (Lisp)|コンス]]）の実行時の連結で形式化されていないパターンを構築し、プログラマの裁量による任意の実行時チェックでパターンの意味づけと計算に用いるための等価性を判別するといったものである。パターンの組み合わせが明確に形式化されておらずその識別をプログラマの裁量に委ねており、またチェックタイミングも委ねられている事から、これは潜在的型付け（''latent typing''）と呼ばれている。潜在的型付けは動的型付けの原型的位置づけである。


手続き型言語ではコンピュータへの指示を文として上から順に並べて書くのに対して、関数型言語では数多く定義した細かい式を組み合わせてプログラムを作る<ref name="名前なし-7"/>。手続き型言語では文が重要であり、関数型言語では式が重要である<ref name="名前なし-8">{{harvnb|本間|類地|逢坂|2017|pp=22–23}}</ref>。
もう一つの実装例として動的なレコード（''record''）がある。この動的レコードは内部的には[[動的配列]]と同じものであり、配列の各スロットに任意の値の[[参照 (情報工学)|参照]]が納められて、そのスロットは[[構造体]]のフィールドと同じものになる。スロットは増設削減可能である。レコードのタグ名はそのまま型名になる。レコードを量化した値（[[インスタンス]]）には、システム側が別途用意する型情報が結び付けられており、変数への束縛ないし代入および関数/演算子への引数代入時に毎回自動的に型判別される。型情報と型判別タイミングが形式化されているのでこれは動的型付けとなる。動的型付けのインスタンスを関数の引数にすることは動的な[[多重定義|関数オーバーロード]]を自然表現し、これはオブジェクト指向に倣って[[多重ディスパッチ]]とも呼ばれる。レコード・フィールドのアクセスは、フィールド名関数をインスタンスに適用するという方法で行われる。オブジェクト指向の<code>instance.field</code>が関数型では<code>field instance</code>のようになる。同じフィールド名関数から得られる値の型は、適用するインスタンスの型構造による実行時多態になる。この仕組みは構造的型付け（''structural typing''）に沿ったものである。


式と文の違いとして、型が付いているかどうかというのがある<ref name="名前なし-8"/>。式は型を持つが、文は型を持たない<ref name="名前なし-8"/>。プログラム全てが式から構成されていて、強い静的型付けがされているのならば、プログラムの全体が細部まで型付けされることになる<ref name="名前なし-8"/>。このように細部まで型付けされているようなプログラムは堅固なものになる<ref name="名前なし-8"/>。
=== モナド ===
{{Quotation|''A monad is just a monoid in the category of endofunctors, what's the problem?''<br/>（モナドは自己関手の圏のただのモノイドだよ。何か問題でも？）|Philip Wadler}}[[モナド (プログラミング)|モナド]]（''monad''）の説明でよく引用されるこの文言はその特徴を明快に表したヒントと言われる。モナドは[[圏論]]由来の自己[[関手]]の合成の仕組みで[[参照透過性]]を維持しつつ、[[代数的構造]]由来の[[モノイド]]の仕組みで非純粋関数の連結体を平易に表現する機能である。非純粋関数の連結体がそのまま一連の[[副作用 (プログラム)|副作用]]内包プロセスになりそれを参照透過性の枠内で実行できる。モナドはプログラム的には、関数の量化を扱う[[二階述語論理]]の実装である[[カリー化]]の活用形態である関数合成と部分適用の応用手法であり、参照透過性欄で説明した派生構造型システムのライナー型の役割を[[圏 (数学)|圏]]に見立てたデータ構築子に持たせている。またデザインパターン的には、関数を引数値に適用する（''applying a function to an argument''）通常の関数とは正反対に、モナドでは値を関数に適用する（''applying a value to a function''）形態を取っており、値を同名関数に反復適用しての特殊な再帰を表現できる。モナドでは値に特殊な演算子を適用することでそれを関数に適用できるようにしている。

モナドの世界では、基本値から導出されるモナド値をモナド関数に次々と適用して状態遷移を表現する。モナド値（''monadic value''）とはMaybe値、例外発生、入出力環境、システムコール、クロージャ、継続といったあらゆる副作用プロセスを扱うためのオブジェクトである。モナド関数（''monadic function''）とはそのオブジェクトのメソッドと考えてよいものである。モナド値とモナド関数は合成演算子を通した表裏一体の存在であり、これがモノイドを指している。合成演算子をモナド値に適用したものをモナド関数に適用して導出されたモナド値を、また同じ手順でモナド関数に適用するといった繰り返しになる。これはモナド合成体（''monadic composition''）と呼ばれる。モナド値は<code>MA</code>のように型表現され、<code>A</code>は基本値、<code>M</code>は基本値を包むコンテキストまたはコンテナである。モナド関数は<code>(A→MB)</code>を基本とする関数の型の値であり、与えられた基本値からモナド値を操作して新たなモナド値を返す。モナド値は<code>MA</code>の型を基本とし、対象内容によって<code>M(A?)</code>、<code>M(A+E)</code>、<code>M(W×A)</code>、<code>E→MA</code>、<code>S→M(A×S)</code>、<code>(A→MR)→MR</code>といった型の値または関数の型の値にリフト（''lift''）される。これはモナド変換子（''monad transformer''）と呼ばれる。また、モナド値の<code>MA</code>の<code>M</code>を空データにして事実上の<code>A</code>にしモナド関数も事実上の<code>(A→B)</code>にした恒等モナド（''identity monad''）もあるがこれは全くの便宜目的である。モナド値は状態遷移の記録媒体であり、η自然変換演算子を基本値に適用することで導出される。基本値＋αから成るモナド値または基本値を包含するモナド値はデータ構築子として表現されて自己関手の圏の枠組みとなり、そのデータ構築子を束縛した型構築子への型引数でモナド値内の型決定がなされる。モナドは大まかに言うと以下の六つの要素から実装されている。

* モナドの文脈を付加された型構築子。一つの副作用内包プロセスを扱う関数群モジュールに見立てられる。
* 基本値＋αのコンテナであるモナド値＝データ構築子。圏に見立てられる。
* μ自然変換演算子（join）kleisli-star拡張演算子（bind）といった合成用の二項演算子。
*基本値とη自然変換演算子（return）とモナド値。モナド値＋二項演算子でモノイドに見立てられる。
* モナド関数。パターンマッチング分岐可能でモジュール内の操作を一手に扱う。自己関手内容に見立てられる。
*ファンクタ文脈からの持ち上げ演算子（fmap）は補助的機能。関手に見立てられる。

モナド値は付加モナドと自由モナド（Maybe/例外/有限リストモナドなど）以外では、実質的に存在量の値になるので普通の値のように扱うことは出来ない。ただし付加/自由モナドでも参照透過性を維持するためには存在量と同等に扱う必要が出てくる。<code>return</code>を基本値に適用してモナド値を表現することからモナド処理は始まる。基本値とは扱うモナドに合わせた任意の値である。そのモナド値は圏としてのユニークIDを持つことになる。ここで基本値を<code>A</code>としそのモナド値を<code>MA</code>とする。<code>MA</code>にbindを適用して<code>(A→MB)→MB</code>という写像を導出する。その写像は先の<code>MA</code>と同じ圏IDを備えたものになる。その写像をモナド関数<code>(A→MB)</code>に適用すると、そのモナド関数内では渡された<code>A</code>やその他の値などに<code>return</code>を適用して表現されるモナド値の圏IDは<code>MA</code>のもので共通化される。モナド関数内においての<code>return</code>は基本値をモナド値に代入する機能と見てよい。<code>return</code>は用途別関数にそれぞれラッピングされて使われるのが普通である。空引数からモナド値を表現する<code>return</code>もありこれはモナドプリミティブ（''monadic primitive''）と呼ばれ、この場合はモナド値の圏IDが暗黙引数になっている。モナド値はファイルハンドルのようなものと考えると分かりやすくなり、モナド値を直接引数にできる専用関数も存在する。モナド関数内ではモナド値から基本値を取り出す演算子が有効になる。それは<code>A←MA</code>のように表現されてコモナド（''comonad''）と呼ばれる機能になる。抽出した基本値からの処理の中で再度<code>return</code>が行われる。モナド関数は自己関手内容に見立てられているので、その中では<code>return</code>の繰り返しによる事実上の再代入処理が許されている。その論理的な辻褄合わせの要点になる<code>bind</code>の正当性および計算可能性を表現するためにファンクタ則とモナド則の等式がプログラム内で定義されている。ここでいわゆる圏論の知識が必要になるがその説明は先送りする。モナド関数はモナド値を返しそれに再度<code>bind</code>を適用できるのでこれがモノイドを意味している。モナド関数の外での<code>return</code>は毎時ユニークな圏IDのモナド値を表現するので同じ基本値でもその都度異なる圏が表現される事になり、これが[[自然変換]]（[[関手圏]]の[[射 (圏論)|射]]）演算子の呼称由来になっている。

モナドは'''ファンクタ'''（''functor''）の派生文脈にされることが多いが、これは<code>bind</code>を形成するクライスリ射と<code>join</code>の合成の持ち上げ（関手）に<code>fmap</code>が使われるからである。ファンクタ文脈は関数<code>fmap</code>を持つ。そのままファンクタの機能名で呼ばれることが多い<code>fmap</code>は、関数<code>(A→B)</code>から関数<code>(TA→TB)</code>を導出する関手＝関数である。この関数は<code>TA</code>に適用できて<code>TB</code>を導出できる。<code>T</code>は基本値を包むコンテキストまたはコンテナでありその代表例はリストである。基本値に対する作用をコンテキストで拡張解釈できるのがファンクタの利点である。例えば基本値への+1という作用をリストのコンテキストで拡張解釈するのはリストの全要素に+1するという意味になる。これはリストをそのまま計算対象にできる利便性に繋がる。ファンクタの派生文脈に'''アプリカティブ'''（''applicative''）がある。アプリカティブは、ファンクタのコンテキストに包まれた関数を「コンテキストに包まれた先頭引数→コンテキストに包まれた残り引数＆評価値」という1引数の関数に変換する演算子<code><*></code>を持つ。<code><*></code>は<code>F(A→B)</code>から<code>(FA→FB)</code>を導出する演算子である。<code>F</code>はコンテキスト、<code>(A→B)</code>は元の関数、<code>(FA→FB)</code>は1引数の関数である。この<code>B</code>は多相であり実際は値<code>＊</code>関数<code>(＊→＊)</code> 関数<code>(＊→＊→＊)</code>などになっている。アプリカティブは、2個以上の引数の関数をファンクタするための機能と考えてよい。2個以上の引数の関数は<code>fmap</code>でそのまま持ち上げられないのでアプリカティブ関手の<code>pure</code>が用いられる。これは<code>A→FA</code>と表現され<code>A</code>が関数、<code>F</code>がコンテキストである。<code>pure</code>によって好きな引数個数の関数をコンテキストで包み<code><*></code>をそれに適用して導出された関数を<code>FA</code>に適用できる。アプリカティブ関手<code>pure::A→FA</code>とモナドのη自然変換演算子<code>return::A→MA</code>は同じ働きに見えるが、前者は関数（関数の型の値）を純粋に持ち上げるだけの[[関手]]なのに対して、後者は持ち上げる関手を毎時垂直合成していく[[関手圏]]の[[射 (圏論)|射]]の[[自然変換]]であるという性質上の違いがある。


== 歴史 ==
== 歴史 ==
=== 1930年代 ===
1930年代に数学者[[アロンゾ・チャーチ]]によって発明された[[ラムダ計算]]は[[写像|関数適用]]を計算単位にした[[形式体系]]であり、1937年に数学者[[アラン・チューリング]]自身により[[チューリング完全]]の性質が明らかにされて、[[チューリングマシン]]と等価な[[計算模型]]である事が証明されている。この経緯からラムダ計算は関数型プログラミングの基底に据えられた。ラムダ計算と同等の[[計算理論]]に[[コンビネータ論理]]があり、1920年代から1930年代にかけて数学者[[ハスケル・カリー]]らによって発明されている。こちらは関数型プログラミングの原点である[[高階論理|高階述語論理]]式の基礎モデルにされた。チャーチはラムダ計算を拡張してその各タームに型を付与した[[型付きラムダ計算|型付けラムダ計算]]も考案しており、これは関数型プログラミングにおける[[型理論]]と[[型システム]]の源流になった。
関数型言語の開発において、[[アロンゾ・チャーチ]]が1932年<ref group="注釈">{{harv|Church|1932}}</ref>と1941年<ref group="注釈">{{harv|Church|1941}}</ref>に発表した[[ラムダ計算]]の研究ほど基本的で重要な影響を与えたものはない<ref name="名前なし-9">{{harvnb|Hudak|1989|p=363}}</ref>。ラムダ計算は、それが考え出された当時は[[プログラム (コンピュータ)|プログラム]]を実行するような[[コンピュータ]]が存在しなかったために[[プログラミング言語]]として見なされなかったにもかかわらず、今では最初の関数型言語とされている<ref name="名前なし-9"/>。1989年現在の関数型言語は、そのほとんどがラムダ計算に装飾を加えたものとして見なせる<ref name="名前なし-9"/>。


'''1950年代'''
=== 1960年代 ===
1960年に[[ジョン・マッカーシー]]等が発表した [[LISP]] は関数型言語の歴史において重要である<ref>{{harvnb|Hudak|1989|p=367}}</ref>。ラムダ計算は LISP の基礎であると言われるが、マッカーシー自身が1978年<ref group="注釈">{{harv|McCarthy|1978}}</ref>に説明したところによると、[[匿名関数]]を表現したいというのが最初にあって、その手段としてマッカーシーはチャーチのラムダ計算を選択したに過ぎない<ref>{{harvnb|Hudak|1989|pp=367–368}}</ref>。


歴史的に言えば、 [[LISP]] に続いて関数型プログラミングパラダイムへ刺激を与えたのは、1960年代半ばの{{仮リンク|ピーター・ランディン|en|Peter Landin}}の成果である<ref name="名前なし-10">{{harvnb|Hudak|1989|p=371}}</ref>。ランディンの成果は[[ハスケル・カリー]]と[[アロンゾ・チャーチ]]に大きな影響を受けていた<ref name="名前なし-10"/>。ランディンの初期の論文は、ラムダ計算と、機械および高級言語 ([[ALGOL 60]]) との関係について議論している<ref name="名前なし-10"/>。ランディンは、1964年<ref group="注釈">{{harv|Landin|1964}}</ref>に、 [[SECDマシン|SECD マシン]]と呼ばれる抽象的な機械を使って機械的に式を評価する方法を論じ、1965年<ref group="注釈">{{harv|Landin|1965}}</ref>に、ラムダ計算で ALGOL 60 の非自明なサブセットを形式化した<ref name="名前なし-10"/>。1966年<ref group="注釈">{{harv|Landin|1966}}</ref>にランディンが発表した [[ISWIM]]（If You See What I Mean の略）という言語（群）は、間違いなく、これらの研究の成果であり、[[構文]]や[[プログラム意味論|意味論]]において多くの重要なアイデアを含んでいた<ref name="名前なし-10"/>。 ISWIM は、ランディン本人によれば、「 LISP を、その名前にも表れた[[リスト (抽象データ型)|リスト]]へのこだわり、手作業のメモリ割り当て、ハードウェアに依存した教育方法、[[S式|重い括弧]]、伝統への妥協、から解放しようとする試みとして見ることができる」<ref name="名前なし-10"/>。関数型言語の歴史において ISWIM は次のような貢献を果たした<ref name="名前なし-11">{{harvnb|Hudak|1989|pp=371–372}}</ref>。
初の関数型プログラミング言語とされる「[[LISP]]」は、1958年に[[マサチューセッツ工科大学]]の計算機科学者[[ジョン・マッカーシー]]によって開発された。LISPの関数はラムダ計算の形式を元に定義され再帰可能に拡張されており、式のリスト化とその遅延評価および高階評価など幾つかの関数型的特徴を備えていた。LISPは数多くの”方言”を生み出しているが、その中でも「[[Scheme]]」「[[Dylan]]」「[[Racket]]」「[[Clojure]]」「Julia」は関数型の特徴を明確にした言語である。1956年に公開された「[[Information Processing Language]]」の方が先駆であるが、こちらはアセンブリベースの[[低水準言語]]なので前段階扱いである。IPLが備えていた[[ニーモニック・コード|ニーモニックコード]]のリストをオペランドにできるジェネレータ機能はLISPに影響を与えたと言われる。高階オペランド演算は高階関数と同じ働きをし、メモリ一括処理のストリング命令の効率を高めるなどした。


* 構文についての革新<ref name="名前なし-10"/>
'''1960年代'''
** 演算子を前置記法で記述するのをやめて中置記法を導入した<ref name="名前なし-10"/>。
** let 節と where 節を導入して、さらに、関数を順序なく同時に定義でき、相互再帰も可能なようにした<ref name="名前なし-10"/>。
** 宣言などを記述する構文に、インデントに基づいたオフサイドルールを使用した<ref name="名前なし-10"/>。
* 意味論についての革新<ref name="名前なし-11"/>
** 非常に小さいが表現力があるコア言語を使って、構文的に豊かな言語を定義するという戦略を導入した<ref name="名前なし-10"/>。
** 等式推論 (equational reasoning) を重視した<ref name="名前なし-10"/>。
** 関数によるプログラムを実行するための単純な抽象機械としての SECD マシンを導入した<ref name="名前なし-11"/>。


ランディンは「それをどうやって行うか」ではなく「それの望ましい結果とは何か」を表現することに重点を置いており、そして、 ISWIM の宣言的なプログラミング・スタイルは命令的なプログラミング・スタイルよりも優れているというランディンの主張は、今日まで関数型プログラミングの賛同者たちから支持されてきた<ref name="名前なし-12">{{harvnb|Hudak|1989|p=372}}</ref>。その一方で、関数型言語への関心が高まるまでは、さらに10年を要した<ref name="名前なし-12"/>。その理由の一つは、 ISWIM ライクな言語の実用的な実装がなかったことであり、実のところ、この状況は1980年代になるまで変わらなかった<ref name="名前なし-12"/>。
1964年に計算機科学者[[ケネス・アイバーソン]]が開発した「[[APL]]」は、計算タイプを定義された関数記号に各種配列データを適用する機能を中心にした言語であり、特に[[スプレッドシート]]処理に対する効率性が認められて、1960年代以降の商業分野と産業分野に積極導入された。APLは多次元配列などのデータ集合に対する関数適用の有用性を特に証明した言語になった。そのデータ集合処理を注目されたAPLからは「[[J言語]]」「S」「A」「K」「Q」といった派生言語が生み出されている。APLの記号構文は一つの手本になりその流れは後年の「[[FP (プログラミング言語)|FP]]」から「[[Haskell]]」にも汲まれた。続く1966年に発表された「[[ISWIM]]」は手続き型と関数型を組み合わせたマルチパラダイムの原点的言語であり、[[ALGOL]]を参考にした構造化プログラミングに高階関数とwhereスコープが加えられていた。60年代の関数型プログラミングの歴史はもっぱらLISPの発展を中心にしていたが、ISWIMは後年の「ML」「Scheme」のモデルにされている。


[[ケネス・アイバーソン]]が1962年<ref group="注釈">{{harv|Iverson|1962}}</ref>に発表した [[APL]] は、純粋な関数型プログラミング言語ではないが、その関数型的な部分を取り出したサブセットがラムダ式に頼らずに関数型プログラミングを実現する方法の一例であるという点で、関数型プログラミング言語の歴史を考察する際に言及する価値はある<ref name="名前なし-12"/>。実際に、アイバーソンが APL を設計した動機は、配列のための代数的なプログラミング言語を開発したいというものであり、アイバーソンのオリジナル版は基本的に関数型的な記法を用いていた<ref name="名前なし-12"/>。その後の APL では、いくつかの命令型的な機能が追加されている<ref name="名前なし-12"/>。
'''1970年代'''


== 脚注 ==
[[スタンフォード大学]]と[[エディンバラ大学]]で実施された[[対話型証明系|対話型]][[自動定理証明]]プロジェクト「''Logic for computable functions''」の中で1973年に導入された「[[ML (プログラミング言語)|ML]]」は[[代数的データ型]]、[[多態性|パラメトリック多相]]、[[型推論]]などを備えた関数型言語であり、計算機科学者[[ロビン・ミルナー]]によって開発された。また、1975年に[[MIT人工知能研究所]]の計算機科学者[[ガイ・スティール・ジュニア|ガイ・スティール]]と工学者[[ジェラルド・ジェイ・サスマン|ジェラルド・サスマン]]が設計してAIリサーチ用に導入された「[[Scheme]]」は任意タイミング評価（call/cc）可能な[[継続]]と[[ガーベジコレクション]]を備え、レキシカルスコープで構造化が図られており[[末尾再帰]]を最適化していた。MLとScheme双方の登場は関数型プログラミングのマイルストーンになった。同年代に代数的データ型を初めて導入し[[クリーネの再帰定理]]を証明実装した「Hope」と、関数の数学的純粋性を初めて重視した「SASL」も発表されている。1977年、[[バッカス・ナウア記法|BNF記法]]と[[FORTRAN]]開発の功績でこの年の[[チューリング賞]]を受けた計算機科学者[[ジョン・バッカス]]は「''Can Programming Be Liberated From the von Neumann Style? -A Functional Style and Its Algebra of Programs-''」と題した記念講演を行い、一説にはこれを境にして関数型（''functional''）というパラダイム名が定着したと言われているが、同時に発表された「[[FP (プログラミング言語)|FP]]」は関数水準（''function-level''）言語として紹介されている。[[ノイマン型]]からの脱却を題目に掲げたバッカスは、FPのプログラムをアトム+関数+フォーム（=高階関数）の階層構造と定義し、[[プロセス代数|代数]]を用いるフォームの結合で構築されると提唱した。


{{脚注ヘルプ}}
'''1980年代'''


=== 注釈 ===
MLの開発者ミルナーが発表していた型推論アルゴリズムが1982年に証明されると、パラメトリック多相に対応した[[型推論]]機能を眼目にした''Hindley–Milner''型体系が確立されて代数的データ型の実用性が高められた。80年代に入ると共に方言が多様化していたLISPとMLの両コミュニティで一定の標準化が求められるようになり、1983年に''Hindley–Milner''型体系を導入した「[[Standard ML]]」が発表された。それに対して1984年に発表された「[[Common Lisp]]」では[[手続き型プログラミング|手続き型パラダイム]]が強調されて関数型の枠組みからやや外れた方向性を示したので、関数型言語の枢軸はMLに置かれた。1985年にはML方言の代表格となる「Caml」が公開された。同じく1985年にSASLの後継として発表された「[[Miranda]]」は、遅延評価を標準にしながら関数の数学的純粋性を追求した言語であり、関数型プログラミング研究用[[オープン標準|オープンスタンダード]]のコンセンサスで1987年から策定が開始された[[Haskell]]のモデルになりその進捗を大きく後押しした。それと前後してMirandaは1987年公開の純粋関数型言語「[[Clean]]」にも大きな影響を与えている。Cleanは後発のHaskellをも叩き台にして改良を続けた。また関数型と[[並行計算]]の適性が認識される中で1986年の通信業界で開発された「[[Erlang]]」は[[並行プログラミング]]指向の面で特に注目を集めている言語である。1988年公開の「[[Wolfram (プログラミング言語)|Wolfram]]」はAPLスタイルのデータ集合処理に機能を豊富にしたパターンマッチングやイテレーションを加えた言語で90年代を通して改良が続けられていた。


{{Notelist}}
'''1990年代'''


=== 出典 ===
1990年に関数型プログラミングの第二のマイルストーンと言える純粋関数型言語「[[Haskell]]」が初リリースされた。Haskellは遅延評価と型理論の文脈を形式化した型クラスと圏論由来のデザインパターンであるモナドの導入を特徴にしていた。1992年に[[動的型付け]]レコードと[[多重ディスパッチ]]を扱う関数型言語「[[Dylan]]」が登場した。1993年に[[ベクトル]]、[[行列]]、[[表 (データベース)|表テーブル]]などのデータストラクチャを扱えて[[統計的検定]]、[[時系列分析]]、[[データ・クラスタリング|クラスタリング]]分野に特化した関数型言語「[[R言語|R]]」が発表された。1995年にLISPの[[マクロ (コンピュータ用語)|マクロ]]機能を大幅に強化したコンポーネント指向により各分野に合わせた[[ドメイン固有言語]]として振る舞える「[[Racket]]」が登場した。1996年にはML方言のCamlにオブジェクト指向視点の[[抽象データ型]]を導入した「[[OCaml]]」が公開された。90年代の関数型プログラミングの歴史では関数の数学的純粋性に則った[[参照透過性]]の重視の他、[[オブジェクト指向プログラミング|オブジェクト指向]]との連携の模索が目立っていた。日本ではStandard MLに独自の拡張を施した「SML#」が発表されている。風変りなものに[[コンビネータ論理]]の形式に立ち返った「[[Unlambda]]」がある。1995年に公開された「Mercury」は関数型と[[論理型プログラミング|論理プログラミング]]の合の子のような言語であり、[[自動推論]]分野への応用に特化されていた。


{{Reflist}}
'''2000年代'''


== 参考文献 ==
2000年代になると関数型プログラミングへの注目度は更に高まり、マルチパラダイムに応用された関数型言語が様々に登場した。2003年のJava仮想マシン動作でオブジェクト指向と関数型を融合した「[[Scala]]」、2005年のマイクロソフト製のML方言「[[F Sharp|F#]]」、2007年のJava仮想マシン動作のLISP方言「[[Clojure]]」など数々のポピュラー言語が生み出されている。また、[[カリー＝ハワード同型対応|カリー=ハワード同型対応]]の理論に基づいた{{仮リンク|プルーフアシスタント|en|Proof asistant|label=}}によるプログラム正当性の数学的証明を指向した関数型言語が支持され、2004年に「Epigram」2007年に「[[Agda]]」および純粋関数型「Idris」が発表されている。これらの言語では数学者[[ペール・マルティン＝レーフ|マルティン・レーフ]]による{{仮リンク|直感的型理論|en|Intuitionistic type theory}}準拠の[[依存型]]を中心にした型システムが実現されている。関数型構文の有用性がより広く認識されるに従い、オブジェクト指向言語やスクリプト言語にも積極的に導入されるようになった。産業分野からも注目されるようになり、[[Constructive Solid Geometry|CSG]]幾何フレームワーク上で動く[[CAD]]への導入も始められた。しかし関数型コンセプトに馴染まないオペレーターが定数化規則による値の再代入制限に困惑して設計作業に支障をきたすなどの弊害も明らかになっている。


* {{Cite Q|Q55890017|last=Church|first=Alonzo}}
== 代表的な関数型言語 ==
* {{Cite Q|Q105884272|last=Church|first=Alonzo}}
'''[[LISP]]'''　（1958年）
* {{Cite Q|Q55871443|last=Hudak|first=Paul}}
* {{Cite Q|Q105954505|last=Iverson|first=Kenneth}}
* {{Cite Q|Q56048080|last=McCarthy|first=John}}
* {{Cite Q|Q30040385|last=Landin|first=Peter}}
* {{Cite Q|Q105941120|last=Landin|first=Peter}}
* {{Cite Q|Q54002422|last=Landin|first=Peter}}
* {{Cite Q|Q105845956|edition=1st (1st printing)|last=Lipovača|first=Miran}}
* {{Cite Q|Q105833610|edition=1st (1st printing)|last=本間|first=雅洋|last2=類地|first2=孝介|last3=逢坂|first3=時響}}


== 外部リンク ==
: 動的型付け、先行評価


* [http://www.sampou.org/haskell/article/whyfp.html なぜ関数プログラミングは重要か]
'''[[APL]]'''　（1964年）
* [https://fxsl.sourceforge.net/articles/FuncProg/Functional%20Programming.html lang|en|The Functional Programming Language XSLT - A proof through examples]([http://alamos.math.arizona.edu/courses/rychlik/CourseDir/589/Assignments/a3/fp.pdf PDF])


== 関連項目 ==
: 配列プログラミング言語、動的型付け、先行評価


* [[カリー化]]
'''[[ISWIM]]'''　（1966年）←　LISP、[[ALGOL]]

: 静的型付け、先行評価

[[ML (プログラミング言語)|'''ML''']]　（1973年）←　ISWIM

: 静的型付け、先行評価

'''[[Scheme]]'''　（1975年）←　LISP、ISWIM

: LISP方言、動的型付け、先行評価

[[FP (プログラミング言語)|'''FP''']]　（1977年）←　APL

: 関数水準言語、動的型付け、先行評価

'''[[Standard ML]]'''　（1983年）←　ML、Hope、[[Pascal|PASCAL]]

: ML方言、静的型付け、先行評価

'''Caml'''　（1985年）←　ML

: ML方言、静的型付け、先行評価

'''[[Miranda]]'''　（1985年）←　ML、Hope、SASL

: 純粋関数型言語、静的型付け、遅延評価

'''[[Erlang]]'''　（1986年）←　LISP、[[Prolog]]、[[Smalltalk]]

: 動的型付け、先行評価

'''[[Clean]]'''　（1987年）←　Miranda

: 純粋関数型言語、静的型付け、遅延評価

'''[[Haskell]]'''　（1990年）←　Scheme、Standard ML、Miranda、FP

: 純粋関数型言語、静的型付け、遅延評価

'''[[Dylan]]'''　（1993年）←　Scheme、[[Common Lisp Object System|CLOS]]、[[ALGOL]]

: LISP方言、動的型付け、先行評価

[[R言語|'''R''']]　（1993年）←　Scheme、[[Common Lisp Object System|CLOS]]

: 配列プログラミング言語、動的型付け、先行評価

'''[[Racket]]'''　（1995年）←　Scheme、[[Eiffel]]

: LISP方言、動的型付け、先行評価

'''[[OCaml]]'''　（1996年）←　Caml、Standard ML、[[Modula-3]]

: ML方言、静的型付け、先行評価、オブジェクト指向

'''[[Scala]]'''　（2003年）←　Scheme、Standard ML、Haskell、Erlang、[[Smalltalk]]、[[Java]]

: 静的型付け、先行評価、オブジェクト指向

[[F Sharp|'''F#''']]　（2005年）←　Standard ML、Haskell、Erlang、Scala、[[Python]]、[[C♯]]

: ML方言、静的型付け、先行評価

'''[[Clojure]]'''　（2007年）←　Scheme、Haskell、Erlang、[[Java]]

: LISP方言、動的型付け、先行評価
'''[[Rust (プログラミング言語)|Rust]]'''　（2010年）←　Scheme、Standard ML、Haskell、Erlang、[[C♯]]
: 静的型付け、先行評価

== 関数型プログラミングの例 ==
アルゴリズムの[[Hello world|Hello World]]と言える[[フィボナッチ数列|フィボナッチ数]]を求めるプログラムは、チュートリアルなどでよく引き合いに出されるものであり、本稿でも手続き型言語との比較を兼ねて取り上げる。一般的な手続き型言語によるソースコードは以下のようになる。<syntaxhighlight lang="pascal">
FUNCTION fibona (num: INTEGER): INTEGER;
VAR
x, y, tmp: INTEGER;
BEGIN
x := 1;
y := 1;
FOR i := 2 TO num DO
BEGIN
tmp := x;
x := y;
y := y + tmp;
END;
fibona := y;
END;
</syntaxhighlight>

それに対して一般的な関数型言語によるソースコードは以下のようになる。<syntaxhighlight lang="haskell">
let rec fibona num = if num < 2 then 1 else fibona (num-2) + fibona (num-1)
</syntaxhighlight>
コード行の羅列であるテキスト的な手続き型プログラミングと比較すると関数型プログラミングの方は、ガードとリミットによる分岐終点ルールで枠組みされたリーフ値と再帰関数のノードによるツリー化手順が一目で把握可能であり、ソースコードから式のツリー構造が直感的に浮かび上がってくる。同様のアルゴリズムで後続値とのペア（2-tuple）を表示するものは以下のようになる。<syntaxhighlight lang="haskell">
let rec fibona num =
if num = 0 then (1, 1) else let (x, y) = fibona (num-1) in (y, x+y)
in
fibona 5

result is (5, 8)
</syntaxhighlight>
<!--
<syntaxhighlight lang="haskell">
let
sum x = if x == 0 then 0
else x + sum (x - 1)
in
sum 10
</syntaxhighlight>
-->

== 脚注 ==
{{脚注ヘルプ}}
=== 注釈 ===
{{Notelist}}
=== 出典 ===
{{Reflist}}

== 外部リンク ==
* [http://www.sampou.org/haskell/article/whyfp.html なぜ関数プログラミングは重要か]
* [http://www.topxml.com/xsl/articles/fp/ {{lang|en|The Functional Programming Language XSLT - A proof through examples}}]


{{プログラミング言語の関連項目}}


{{Normdaten}}
{{Normdaten}}
{{プログラミング言語の関連項目}}


{{DEFAULTSORT:かんすうかたけんこ}}
{{DEFAULTSORT:かんすうかたふろくらみんく}}
[[Category:関数型言語|*]]
[[Category:関数型プログラミング|*]]
[[Category:プログラミングパラダイム]]
[[Category:プログラミングパラダイム]]

2024年11月3日 (日) 14:27時点における最新版

プログラミング・パラダイム

命令型プログラミング

宣言型プログラミング

マルチパラダイム

関数型プログラミング（かんすうがたプログラミング、英: functional programming）とは、数学的な意味での関数を主に使うプログラミングのスタイルである[1]。 functional programming は、関数プログラミング（かんすうプログラミング）などと訳されることもある[2]。

関数型プログラミング言語（英: functional programming language）とは、関数型プログラミングを推奨しているプログラミング言語である[1]。略して関数型言語（英: functional language）ともいう[1]。

概要

[編集]

関数型プログラミングは、関数を主軸にしたプログラミングを行うスタイルである[1]。ここでの関数は、数学的なものを指し、引数の値が定まれば結果も定まるという参照透過性を持つものである[1]。

参照透過性とは、数学的な関数と同じように同じ値を返す式を与えたら必ず同じ値を返すような性質である[1]。次の square 関数は、 2 となるような式を与えれば必ず 4 を返し、 3 となるような式を与えれば必ず 9 を返し、いかなる状況でも別の値を返すということはなく、これが参照透過性を持つ関数の一例となる[1]。 

def square(n):
  return n ** 2

次の countup 関数は、同じ 1 を渡しても、それまでに countup 関数がどのような引数で呼ばれていたかによって、返り値が 1, 2, 3, ... と変化するため、引数の値だけで結果の値が定まらないような参照透過性のない関数であり、数学的な関数とはいえない[1]。 

counter = 0
def countup(n):
  global counter
  counter += n
  return counter

関数型プログラミングは、参照透過性を持つような数学的な関数を使って組み立てた式が主役となる[1]。別の箇所に定義されている処理を利用することを、手続き型プログラミング言語では「関数を実行する」や「関数を呼び出す」などと表現するが、関数型プログラミング言語では「式を評価する」という表現も良く使われる[3]。

参照透過性

[編集]
→詳細は「参照透過性」を参照

参照透過性とは、同じ値を与えたら返り値も必ず同じになるような性質である[1]。参照透過性を持つことは、その関数が状態を持たないことを保証する[4]。状態を持たない数学的な関数は、並列処理を実現するのに適している[4]。関数型プログラミング言語の内で、全ての関数が参照透過性を持つようなものを純粋関数型プログラミング言語という[4]。

入出力

[編集]

関数型プログラミングでは、数学的な関数を組み合わせて計算を表現するが、それだけではファイルの読み書きのような外界とのやり取りを要する処理を直接的に表現できない[5]。このような外界とのやり取りを I/O (入出力) と呼ぶ[5]。数学的な計算をするだけ、つまり 1 + 1 のようなプログラム内で完結する処理ならば、入出力を記述できなくても問題ないが、現実的なプログラムにおいてはそうでない[5]。

非純粋な関数型プログラミング言語においては、式を評価すると同時に I/O が発生する関数を用意することで入出力を実現する[5]。たとえば、 F# 言語では、printfn "Hi." が評価されると、 () という値が戻ってくると同時に、画面に Hi. と表示される I/O が発生する[5]。

Haskell では、評価と同時に I/O が行われる関数は存在しない[5]。たとえば、 putStrLn "Hi." という式が評価されると IO () 型を持つ値が返されるが画面には何も表示されず、この値が Haskell の処理系によって解釈されて初めて画面に Hi. と表示される[5]。 I/O アクションとは、ファイルの読み書きやディスプレイへの表示などのような I/O を表現する式のことである[5][6]。 IO a という型は、コンピュータへの指示を表す I/O アクションを表現している[5][7]。ここでの IO はモナドと呼ばれるものの一つである[8]。

Clean では、一意型を用いて入出力を表す。

手法

[編集]

最初に解の集合となる候補を生成し、それらの要素に対して1つ（もしくは複数）の解にたどり着くまで関数の適用とフィルタリングを繰り返す手法は、関数型プログラミングでよく用いられるパターンである[9]。

Haskell では、関数合成の二項演算子を使ってポイントフリースタイルで関数を定義することができる[9]。関数をポイントフリースタイルで定義すると、データより関数に目が行くようになり、どのようにデータが移り変わっていくかではなく、どんな関数を合成して何になっているかということへ意識が向くため、定義が読みやすく簡潔になることがある[9]。関数が複雑になりすぎると、ポイントフリースタイルでは逆に可読性が悪くなることもある[9]。

言語

[編集]

関数型プログラミング言語とは、関数型プログラミングを推奨しているプログラミング言語である[1]。略して関数型言語ともいう[1]。全ての関数が参照透過性を持つようなものを、特に純粋関数型プログラミング言語（英語版）という[4]。そうでないものを非純粋であるという[5]。

関数型プログラミング言語の多くは、言語の設計において何らかの形でラムダ計算が関わっている[3]。ラムダ計算はコンピュータの計算をモデル化する体系の一つであり、記号の列を規則に基づいて変換していくことで計算が行われるものである[3]。

関数型プログラミング言語
名前 型付け 純粋性 評価戦略 理論的背景
Clean 静的型付け 純粋 遅延評価
Elm 静的型付け 純粋 正格評価
Erlang 動的型付け 非純粋 正格評価
F# 静的型付け 非純粋 正格評価
Haskell[2] 静的型付け[2] 純粋[2] 遅延評価[2] 型付きラムダ計算[3]
Idris 静的型付け 純粋 正格評価 型付きラムダ計算
Lazy K 型なし 純粋 遅延評価 コンビネータ論理
LISP 1.5
Scheme
Common Lisp
Clojure 		動的型付け 非純粋 正格評価 型無しラムダ計算[3]
LISPの各種方言[3] 方言による 方言による 方言による
Miranda 静的型付け 純粋 遅延評価
ML
Standard ML
OCaml 		静的型付け 非純粋 正格評価
Scala 静的型付け 非純粋 正格評価
Unlambda 型なし 非純粋 正格評価 コンビネータ論理
Lean 静的型付け 純粋 正格評価 型付きラムダ計算

手続き型プログラミングとの比較

[編集]

C 言語や Java 、 JavaScript 、 Python 、 Ruby などの2017年現在に使われている言語の多くは、手続き型の文法を持っている[10]。そのような言語では、文法として式 (expression) と文 (statement) を持つ[10]。ここでの式は、計算を実行して結果を得るような処理を記述するための文法要素であり、加減乗除や関数呼び出しなどから構成されている[10]。ここでの文は、何らかの動作を行うようにコンピュータへ指示するための文法要素であり、条件分岐の if 文やループの for 文と while 文などから構成されている[10]。手続き型の文法では、式で必要な計算を進め、その結果を元にして文でコンピュータ命令を行うという形で、プログラムを記述する[10]。このように、手続き型言語で重要なのは文である[10]。

それに対して、関数型言語で重要なのは式である[10]。関数型言語のプログラムはたくさんの式で構成され、プログラムそのものも一つの式である[10]。たとえば、 Haskell では、プログラムの処理の記述において文は使われず、外部の定義を取り込む import 宣言も処理の一部として扱えない[10]。関数型言語におけるプログラムの実行とは、プログラムを表す式の計算を進めて、その結果として値 (value) を得ることである[10]。式を計算することを、評価する (evaluate) という[10]。

手続き型言語ではコンピュータへの指示を文として上から順に並べて書くのに対して、関数型言語では数多く定義した細かい式を組み合わせてプログラムを作る[10]。手続き型言語では文が重要であり、関数型言語では式が重要である[11]。

式と文の違いとして、型が付いているかどうかというのがある[11]。式は型を持つが、文は型を持たない[11]。プログラム全てが式から構成されていて、強い静的型付けがされているのならば、プログラムの全体が細部まで型付けされることになる[11]。このように細部まで型付けされているようなプログラムは堅固なものになる[11]。

歴史

[編集]

1930年代

[編集]

関数型言語の開発において、アロンゾ・チャーチが1932年[注釈 1]と1941年[注釈 2]に発表したラムダ計算の研究ほど基本的で重要な影響を与えたものはない[12]。ラムダ計算は、それが考え出された当時はプログラムを実行するようなコンピュータが存在しなかったためにプログラミング言語として見なされなかったにもかかわらず、今では最初の関数型言語とされている[12]。1989年現在の関数型言語は、そのほとんどがラムダ計算に装飾を加えたものとして見なせる[12]。

1960年代

[編集]

1960年にジョン・マッカーシー等が発表した LISP は関数型言語の歴史において重要である[13]。ラムダ計算は LISP の基礎であると言われるが、マッカーシー自身が1978年[注釈 3]に説明したところによると、匿名関数を表現したいというのが最初にあって、その手段としてマッカーシーはチャーチのラムダ計算を選択したに過ぎない[14]。

歴史的に言えば、 LISP に続いて関数型プログラミングパラダイムへ刺激を与えたのは、1960年代半ばのピーター・ランディン（英語版）の成果である[15]。ランディンの成果はハスケル・カリーとアロンゾ・チャーチに大きな影響を受けていた[15]。ランディンの初期の論文は、ラムダ計算と、機械および高級言語 (ALGOL 60) との関係について議論している[15]。ランディンは、1964年[注釈 4]に、 SECD マシンと呼ばれる抽象的な機械を使って機械的に式を評価する方法を論じ、1965年[注釈 5]に、ラムダ計算で ALGOL 60 の非自明なサブセットを形式化した[15]。1966年[注釈 6]にランディンが発表した ISWIM（If You See What I Mean の略）という言語（群）は、間違いなく、これらの研究の成果であり、構文や意味論において多くの重要なアイデアを含んでいた[15]。 ISWIM は、ランディン本人によれば、「 LISP を、その名前にも表れたリストへのこだわり、手作業のメモリ割り当て、ハードウェアに依存した教育方法、重い括弧、伝統への妥協、から解放しようとする試みとして見ることができる」[15]。関数型言語の歴史において ISWIM は次のような貢献を果たした[16]。

  • 構文についての革新[15]
    • 演算子を前置記法で記述するのをやめて中置記法を導入した[15]。
    • let 節と where 節を導入して、さらに、関数を順序なく同時に定義でき、相互再帰も可能なようにした[15]。
    • 宣言などを記述する構文に、インデントに基づいたオフサイドルールを使用した[15]。
  • 意味論についての革新[16]
    • 非常に小さいが表現力があるコア言語を使って、構文的に豊かな言語を定義するという戦略を導入した[15]。
    • 等式推論 (equational reasoning) を重視した[15]。
    • 関数によるプログラムを実行するための単純な抽象機械としての SECD マシンを導入した[16]。

ランディンは「それをどうやって行うか」ではなく「それの望ましい結果とは何か」を表現することに重点を置いており、そして、 ISWIM の宣言的なプログラミング・スタイルは命令的なプログラミング・スタイルよりも優れているというランディンの主張は、今日まで関数型プログラミングの賛同者たちから支持されてきた[17]。その一方で、関数型言語への関心が高まるまでは、さらに10年を要した[17]。その理由の一つは、 ISWIM ライクな言語の実用的な実装がなかったことであり、実のところ、この状況は1980年代になるまで変わらなかった[17]。

ケネス・アイバーソンが1962年[注釈 7]に発表した APL は、純粋な関数型プログラミング言語ではないが、その関数型的な部分を取り出したサブセットがラムダ式に頼らずに関数型プログラミングを実現する方法の一例であるという点で、関数型プログラミング言語の歴史を考察する際に言及する価値はある[17]。実際に、アイバーソンが APL を設計した動機は、配列のための代数的なプログラミング言語を開発したいというものであり、アイバーソンのオリジナル版は基本的に関数型的な記法を用いていた[17]。その後の APL では、いくつかの命令型的な機能が追加されている[17]。

脚注

[編集]
[脚注の使い方]

注釈

[編集]
  1. ^ (Church 1932)
  2. ^ (Church 1941)
  3. ^ (McCarthy 1978)
  4. ^ (Landin 1964)
  5. ^ (Landin 1965)
  6. ^ (Landin 1966)
  7. ^ (Iverson 1962)

出典

[編集]
  1. ^ a b c d e f g h i j k l 本間, 類地 & 逢坂 2017, p. 3
  2. ^ a b c d e 本間, 類地 & 逢坂 2017, p. 2
  3. ^ a b c d e f 本間, 類地 & 逢坂 2017, p. 4
  4. ^ a b c d 本間, 類地 & 逢坂 2017, p. 5
  5. ^ a b c d e f g h i j 本間, 類地 & 逢坂 2017, p. 6
  6. ^ 本間, 類地 & 逢坂 2017, p. 23
  7. ^ 本間, 類地 & 逢坂 2017, p. 31
  8. ^ 本間, 類地 & 逢坂 2017, p. 32
  9. ^ a b c d Lipovača 2012, p. 22
  10. ^ a b c d e f g h i j k l 本間, 類地 & 逢坂 2017, p. 22
  11. ^ a b c d e 本間, 類地 & 逢坂 2017, pp. 22–23
  12. ^ a b c Hudak 1989, p. 363
  13. ^ Hudak 1989, p. 367
  14. ^ Hudak 1989, pp. 367–368
  15. ^ a b c d e f g h i j k l Hudak 1989, p. 371
  16. ^ a b c Hudak 1989, pp. 371–372
  17. ^ a b c d e f Hudak 1989, p. 372

参考文献

[編集]
  • Church, Alonzo (1932年4月), “A Set of Postulates for the Foundation of Logic” (英語), Annals of Mathematics 33 (2): 346, doi:10.2307/1968337, ISSN 0003-486X, JSTOR 1968337, https://jstor.org/stable/1968337 , Wikidata Q55890017
  • Church, Alonzo (1941年) (英語), The Calculi of Lambda Conversion, プリンストン大学出版局 , Wikidata Q105884272
  • Hudak, Paul (1989年9月1日), “Conception, evolution, and application of functional programming languages” (英語), ACM Computing Surveys 21 (3): 359–411, doi:10.1145/72551.72554, ISSN 0360-0300 , Wikidata Q55871443
  • Iverson, Kenneth (1962年12月1日) (英語), A Programming Language, ジョン・ワイリー・アンド・サンズ, ISBN 978-0-471-43014-8, OL 26792153M , Wikidata Q105954505
  • McCarthy, John (1978年), History of LISP, doi:10.1145/800025.808387 , Wikidata Q56048080
  • Landin, Peter (1964年1月1日), “The Mechanical Evaluation of Expressions” (英語), The Computer Journal 6 (4): 308-320, doi:10.1093/COMJNL/6.4.308, ISSN 0010-4620 , Wikidata Q30040385
  • Landin, Peter (1965年), “Correspondence between ALGOL 60 and Church's Lambda-notation” (英語), Communications of the ACM 8, ISSN 0001-0782 , Wikidata Q105941120
  • Landin, Peter (1966年3月1日), “The next 700 programming languages” (英語), Communications of the ACM 9 (3): 157-166, doi:10.1145/365230.365257, ISSN 0001-0782 , Wikidata Q54002422
  • Lipovača, Miran 田中英行, 村主崇行訳 (2012年5月25日), すごいHaskellたのしく学ぼう! (1st (1st printing) ed.), オーム社, ISBN 978-4-274-06885-0 , Wikidata Q105845956
  • 本間雅洋; 類地孝介; 逢坂時響『Haskell入門 関数型プログラミング言語の基礎と実践』（1st (1st printing)）技術評論社、2017年10月10日。ISBN 978-4-7741-9237-6。 , Wikidata Q105833610

外部リンク

[編集]

関連項目

[編集]
コンピュータ・プログラミング言語の関連項目
言語水準
言語処理系
言語分類
その他
関連項目
「https://ja-two.iwiki.icu/w/index.php?title=関数型プログラミング&oldid=102441972」から取得