「関数型プログラミング」の版間の差分
m編集の要約なし |
|||
(同じ利用者による、間の29版が非表示) | |||
1行目: | 1行目: | ||
{{独自研究|date=2014年4月}} |
{{独自研究|date=2014年4月}} |
||
{{プログラミング言語|index=かんすうかたけんこ}} |
{{プログラミング言語|index=かんすうかたけんこ}} |
||
[[ファイル:Orange_lambda.svg|代替文=|境界|右|フレームなし| |
[[ファイル:Orange_lambda.svg|代替文=|境界|右|フレームなし|209x209px]] |
||
<!-- 本節はHaskellやLISPに偏重しすぎ --> |
<!-- 本節はHaskellやLISPに偏重しすぎ --> |
||
'''関数型言語'''({{lang-en-short|''functional language''}})は、'''関数型プログラミング'''のスタイルまたは[[プログラミングパラダイム|パラダイム]]を扱う[[プログラミング言語]]の総称である。関数型プログラミングは関数の[[写像|適用]]と[[関数の合成|合成]]から組み立てられる[[宣言型プログラミング]]の一種であり、関数は[[引数]]の適用から先行式の[[評価戦略|評価]]を後続式の適用に繋げて終端評価に到る[[式 (プログラミング)|式]]の[[ツリー構造|ツリー]]として定義される。関数は引数ないし返値として渡せる[[第一級関数]]として扱われる。 |
'''関数型言語'''({{lang-en-short|''functional language''}})は、'''関数型プログラミング'''のスタイルまたは[[プログラミングパラダイム|パラダイム]]を扱う[[プログラミング言語]]の総称である。関数型プログラミングは関数の[[写像|適用]]と[[関数の合成|合成]]から組み立てられる[[宣言型プログラミング]]の一種であり、関数は[[引数]]の適用から先行式の[[評価戦略|評価]]を後続式の適用に繋げて終端評価に到る[[式 (プログラミング)|式]]の[[ツリー構造|ツリー]]として定義される。関数は引数ないし返値として渡せる[[第一級関数]]として扱われる。 |
||
関数型プログラミングは[[数理論理学]]と |
関数型プログラミングは[[数理論理学]]と代数系をルーツにし、[[ラムダ計算]]と[[コンビネータ論理]]を幹にして構築され、[[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月|関数型プログラミングのスタイル要素として挙げられる}}。 |
||
== 特徴 == |
== 特徴 == |
||
ここでは関数型プログラミング本来の構文スタイルを元にして説明する。式を基本文にする関数型に対して、[[文 (プログラミング)|ステートメント]]を基本文にする[[手続き型プログラミング|手続き型]]や[[オブジェクト指向プログラミング|オブジェクト指向]]などの[[命令型プログラミング]]言語では必要に応じて構文スタイルを変えて実装されている。代表的なのは「式の引数への適用」に対する「引数を関数に渡す」である。ただし双方ともアセンブリコード上では同様に符号化され |
ここでは関数型プログラミング本来の構文スタイルを元にして説明する。式を基本文にする関数型に対して、[[文 (プログラミング)|ステートメント]]を基本文にする[[手続き型プログラミング|手続き型]]や[[オブジェクト指向プログラミング|オブジェクト指向]]などの[[命令型プログラミング]]言語では必要に応じて構文スタイルを変えて実装されている。代表的なのは「式の引数への適用」に対する「引数を関数に渡す」である。ただし双方ともアセンブリコード上では同様なものに符号化される。 |
||
値(''value'')は代数的データ型(''algebraic data type'')として表現される。代数的データ型は[[型理論]]にある様々なタイプの複合体であり、各タイプの表現代数式を各言語仕様に沿ったプログラムパーツで置き換えてあらゆる値を数学的に表現する仕組みである。代数的データ型は言わば「型の式」であり、その式パターンが「型」になり、式パターンの構築が「型付け」になる。結果的に全ての値は「型」で分類される事になる。代数的データ型の実装方法はそれを意識させない位単純なものから忠実なものまで言語ごとに様々である。代数的データ型は単体値を兼ねたあらゆる[[多重集合]]の表現になる。命令型言語での導入例はまず無くより平易で直感的な構造体やクラスが型付けに使われている。 |
|||
=== 式と関数 === |
=== 式と関数 === |
||
{{出典の明記|date=2020年5月6日 (水) 02:29 (UTC)|section=1}} |
{{出典の明記|date=2020年5月6日 (水) 02:29 (UTC)|section=1}} |
||
*関数型プログラムの基本文は[[式 (プログラミング)|式]](''expression'') |
*関数型プログラムの基本文は[[式 (プログラミング)|式]](''expression'')である。 |
||
*式は、値(''value'')と演算子(''operator'')と関数(''function'')で構成される。式内の |
*式は、値(''value'')と演算子(''operator'')と関数(''function'')で構成される。値は[[束縛変数]]と[[自由変数と束縛変数|自由変数]]を包括する。式内の変数部分が特定される前の式は評価できない[[ボトム型]]存在である。特定後は[[評価戦略]]に従ったタイミングで評価(''evaluation'')されて式存在から値存在になる。 |
||
*式は値と同一視されるので |
*式は値と同一視されるので上述の式と値は相互再帰の関係にある。式内の値は他の式の評価値である事があり、その式内にもまた他の値があるといった具合である。この仕組みは[[高階論理]]''と呼ばれる。'' |
||
*関数も値と同一視される。関数は式に引数を結び付ける機能であり、これは式の引数への[[写像|適用]](''application'')と呼ばれる。式内の仮引数(''parameter'')箇所に実引数(''argument'')が順次当てはめられ、式ツリーの終端式が評価値になる。 |
|||
*式評価値の後続への反映は変数への代入ではなく、[[束縛変数]]で定数化するのが{{要出典範囲|本来の在り方である|date=2020年5月}}。 |
|||
*関数は、式を第1引数に適用したもの→第2引数に適用したもの→第x引数に適用したもの→評価値、という形をとる。引数を1個ずつ適用する形態は[[カリー化]]と呼ばれる。2個以上の引数を同時適用する形態は非カリー化と呼ばれる。関数の型は「A→B→C→D」のように各引数値から評価値までの写像パターンで表現される。 |
|||
*任意の後続式の[[自由変数と束縛変数|自由変数]]の記述を省略して自動的に引数または先行式の評価値を適用する構文がしばしば用いられる。これはポイントフリーまたは[[パイプライン処理|パイプライン]]と呼ばれる。 |
|||
*関数も[[高階論理]]に組み込まれている。引数値または評価値として扱うことができる関数は[[第一級関数]]と呼ばれる。その第一級関数を扱うことができる関数は[[高階関数]]と呼ばれる。 |
|||
*関数も値と同一視される。関数は式に引数(''parameter'')を結び付けるものである。式の代数部分に引数値が順次束縛され、式ツリーの終端式が評価値になる。 |
|||
*カリー化された関数は引数の適用を途中で止めて残り引数を後から適用できる第一級関数を生成できる。これは部分適用と呼ばれる。 |
|||
*関数は、式の引数への適用(''application'')と解釈される。{{要出典範囲|その対義概念として反適用(''unapply'')の仕組みも存在する。これは式の引数への適用を差し戻して元の引数を抽出する|date=2020年5月}}。 |
|||
*片方の評価値と片方の第1引数が同じ型の両関数は任意に連結できる。この双方の写像のつなぎ合わせは関数合成と呼ばれる。 |
|||
*関数は、式を第1引数に適用したもの→第2引数に適用したもの→第x引数に適用したもの→評価値、という形をとる。引数を1個ずつ適用する形態は[[カリー化]]と呼ばれる。 |
|||
*仮引数記述を省略した関数はポイントフリーと呼ばれ、その省略箇所に先行式評価値が実引数として暗黙適用される。実引数記述を省略して先行式評価値を後続関数の仮引数箇所に暗黙適用するのもポイントフリーと呼ばれる。この暗黙適用の式を並べて連鎖させる手法は[[パイプライン処理|パイプライン]]と呼ばれる。言語によっては特別な演算子と併せて明示する。 |
|||
*2個以上の引数を同時適用する非カリー化の関数も用いられる。無名関数がしばしばそれになる。この場合は部分適用やポイントフリーが制限される。 |
|||
*関数は名前付きと名前無しの二通りある。後者はラムダ抽象を模した構文で式中に直接定義される。これは[[クロージャ]] |
*関数は名前付きと名前無しの二通りある。後者はラムダ抽象を模した構文で式中に直接定義される。これは[[無名関数]]と呼ばれる。式内に自由変数を持った無名関数は[[クロージャ]]と個別に定義される。自由変数には外部データが代入される。自身を参照する無名関数を内包したデータ構造体(=[[関数オブジェクト]])もクロージャに相当する。 |
||
*[[無名関数]]は引数をピュア[[写像|マッピング]]する純粋関数であるが、毎回違う値が渡される用途から事実上[[メモ化]]できない事がコーディング上の利便性を除いた存在理由になっている。[[クロージャ]]の引数[[写像|マッピング]]は式内の自由変数に影響され、またその自由変数に作用する事もある即ち副作用要素を閉包した非純粋関数である。 |
|||
*関数の引数値を関数にする事も可能であり、また関数の評価値を関数にする事も可能である。他の関数を引数値または評価値として扱える関数は[[高階関数]]と呼ばれる。他の関数から引数値または評価値として扱われる関数は[[第一級関数]]と呼ばれる。 |
|||
*関数の名前は、それに結び付けられた式または式ツリーの[[不動点]]の表現になる。自式の不動点を式内に置いて新たな引数と共に[[高階論理]]の式として評価する手法は[[再帰]]と呼ばれる。 |
|||
*関数式の引数適用を任意の段階で保留して残り引数の適用を待つ第一級関数を生成できる。これは部分適用と呼ばれる。 |
|||
*イミュータブル性が重視されない場合、関数の終端式での再帰は、実引数の更新+先端式へのアドレスジャンプと同等に見なせるので専らそちらに最適化される。これは[[末尾再帰]]と呼ばれる。相互再帰を同様に最適化したものは兄弟再帰(''sibling recursion'')と呼ばれる。 |
|||
*片方の評価値と片方の第1引数が同じ型の両関数を合わせて双方の写像をつなげた第一級関数を生成できる。これは関数合成と呼ばれる。 |
|||
*リスト処理時にリストの各要素に対する作用子として渡される第一級関数は[[反復子|イテレータ]]と呼ばれる。作用後の各要素を別の新生リストに向けて複製する働きを加えたものは[[ジェネレータ (プログラミング)|ジェネレータ]]と呼ばれる。これは[[イミュータブル]]重視時に多用される。前者はポイントフリーの無名関数、後者はポイントフリーのクロージャとして定義される事が多い。 |
|||
*演算子はデフォルトの式内容を持ち、引数が1~2個に限定された関数と同義である。演算子も部分適用でき、セクションと呼ばれる第一級関数になる。言語や演算子によるが、演算子は任意に再定義、追加ができる([[利用者定義演算子]])。 |
|||
*任意のタイミングで遅延評価(''call/cc'')される用途の第一級関数は特別に[[継続]]と呼ばれる。関数の引数を順々に評価して間に分岐などを挟める[[継続渡しスタイル]]はその応用例である。 |
|||
*部分関数は引数によって[[ボトム型]]を返せる関数である。ボトム型は命令型言語における例外発生と同等に解釈できる。 |
|||
*演算子はデフォルトの式内容を持ち、引数が1~2個に限定された関数と同義である。部分適用された演算子はセクションと呼ばれる第一級関数になる。演算子は任意の型にフックさせた再定義および追加定義ができる。これはアドホック多相と呼ばれる。 |
|||
=== 代数的データ型 === |
=== 値と代数的データ型 === |
||
{{出典の明記|date=2020年5月6日 (水) 02:30 (UTC)|section=1}} |
{{出典の明記|date=2020年5月6日 (水) 02:30 (UTC)|section=1}} |
||
*値(''value'')は |
*値(''value'')は代数的データ型(''algebraic data type'')として表現される。代数的データ型は[[型理論]]にある様々なタイプの複合体である。代数的データ型は言わば「型の式」である。 |
||
*代数的データ型の式パターンは型構築子(''type constructor'')に束縛される。型構築子は新たな代数的データ型の識別名になる。式パターン内で代数的データ型は入れ子にできる。その入れ子とプロパー型は式パターン内で型変数(''type variable'')として扱われ、パラメトリック多相で総称化できる。型構築子は型引数(''type parameter'')と併せて定義され、総称化された各要素を決定する。 |
|||
<!-- *代数的データ型は、''atom(プリミティブ)nil(無)cons(内包値+リンク)''の要素で実装される。''atom''は数値、論理値、文字、文字列を指す。''cons''の''内包値''は''atom''または次の''cons(=''入れ子の代数的データ)を指し、''cons''のリンクは次の''cons''または''nil''(=終端)を指す。代数的データは''cons''の再帰で構成されてゼロ個から複数以上の値を内包する事になる。この再帰ツリー構造は[[S式]]と呼ばれる。 --> <!-- LISPの用語に頼りすぎ。S式に至っては他言語にはない --> |
|||
*値は型(''type'')に |
*数値、論理値、文字値、文字列は[[プリミティブ型|プロパー型]](''proper type'')に分類され、最も基本的な式パターン要素になる。 |
||
*代数的データ型は、代数的データ型の入れ子で帰納的に構成される事もあるがその末端は必ずプロパー型になる。この帰納的な仕組みは[[高階論理|高階]]型(''higher-order types'')と呼ばれる。 |
|||
*全ての値が同じ型の代数的データは''list''と呼ばれ、異なる場合は''tuple''と呼ばれる。''list''は用法的に[[線形リスト]]と同義であり、''tupleは用法によっては''[[構造体]]の近似物になる。後者は前述の[[直積集合|直積]]である。 |
|||
*代数的データ型は、プロパー型に到るまでの帰納パターンである[[カインド (型理論)|カインド]]で抽象化分類される。カインドは「*→*」「*」のように表現される。カインドはパターンマッチングと型シノニムの成立基準になる。 |
|||
*型選択している代数的データは''variants''などと呼ばれ、[[共用体]]ないし[[列挙型]]の類似物になる。これは前述の[[非交和]]である。 |
|||
* |
*左辺のもので右辺のものを置き換えられるという代数的データ型間の[[項書き換え]]ルールを定義できる。これは型シノニムと呼ばれる。[[リスコフの置換原則]]に似たものである。 |
||
*代数的データ型は、[[直積集合|直積型]](''product type'')[[非交和|非交和型]](''sum type'')帰納型(''inductive type'')[[依存型]](''dependent type'')ユニット型(''unit type'')などのタイプを持つ。式的役割は直積型=×演算子、非交和型=+演算子、帰納型=式再帰または高階式、依存型=パターンマッチング式、ユニット型=NILである。この5タイプで大半の値を表現できる。 |
|||
*値は式評価の束縛と解釈される傾向から値の型宣言は省略される傾向にある。<!-- プログラマによるしHaskellでは記述が推奨されている -->。型を自動的に導き出す機能は[[型推論]]と呼ばれる。型推論と[[多態性|パラメータ多相]]はよく併用される。 |
|||
*直積型は、(A, B) のような[[タプル]]のパターンを表わす。また標準的な[[構造体|レコード]]を表現する。 |
|||
*非交和型は、(A | B) のような[[共用体|修飾共用体]]または[[列挙型]]のパターンを表わす。 |
|||
*帰納型は、[[ボックス化]]と前述の入れ子のパターンを表わす。また帰納型と非交和型とユニット型は併用されて[[連結リスト]]、[[二分木]]、[[ツリー構造|データツリー]]のパターンを表わす。 |
|||
*依存型は、一つの依存値による[[パターンマッチング]]式をそのままタイプと見なしたものである。その[[パターンマッチング|ケース節]]パターンのみはオプション型(''option type'')[[ガード (プログラミング)|ガード節]]パターンのみはリファイン型(''refinement type'')と個別定義される。これらは[[動的配列]]、Maybe値、リスト内包表記などの構造を表わす。 |
|||
*ユニット型は、NILないしVOIDであり空集合のパターンを表わす。 |
|||
*交差型(''intersection type'')は、型クラスや型エイリアスなどのアドホック多相によるパターンの表現に用いられる。 |
|||
*[[パターンマッチング]]式は、CASE式の値に依存した依存型またはオプション型のその場構築である。条件分岐式(IF-THEN-ELSE)は、IF式の値に依存したリファイン型のその場構築である。前者は型推論と式評価による等価性または等値性のパターン審査を行う。後者は式評価による等値性または順序性の論理的審査を行う。 |
|||
*関数の写像パターンは指数型(''exponential type'')で説明される。”関数適用の評価値”は指数型と直積型の併用で表現される。そのまま関数の型(''function type'')と呼ばれる事が多い。関数のパターンマッチングはもっぱらアドホック多相の方で解釈される。 |
|||
*[[型推論]]は、代数的データ型の式パターンを等価性を審査できる形まで演繹する機能である。これはいわゆる「型」を導き出すのと同義である。この機能により束縛変数の型注釈はもっぱら省略される。型推論は値の等価性審査の手段であり、いわゆる型チェックや遅延パターンマッチングなどを実現する。 |
|||
=== |
=== 評価戦略 === |
||
関数型プログラミングにおける[[評価戦略]]とは「式存在」を「値存在」にする評価タイミングの定義を指す。これはまず正格評価(''strict evaluation'')と非正格評価(''non-strict evaluation'')の二つに大別される。前者の式存在は、関数による適用と同時に評価されて値存在になり、または変数による束縛と同時に評価されて値存在になる。関数の引数節で直積された式存在は理論上全て同時に評価される事になる。その実装は直積された式存在を副作用を伴わずに並行計算するか、そうでない場合は一つ一つ評価していく事になる。単に一つ一つ評価していくものは[[先行評価]]になり、ここでも副作用を伴わない事が原則とされるが必須ではなくなる。 |
|||
*反復構造は変数代入したカウンタを増減するループ文ではなく再帰で表現するのが好まれる。カウンタは再帰呼び出し時に、引数として与えて操作するか、イテレーションを用いる。 |
|||
*選択構造では関数の引数値による[[パターンマッチング]]が多用される。[[真理値]]による単純な比較など、パターンマッチングでは大げさな場合は[[if文]]も用いられる。 |
|||
後者の非正格評価はほとんどのケースで[[遅延評価]]と同義の言葉になる。遅延評価の式存在は、関数に適用されても式存在のままであり、または変数に束縛されても式存在のままである。後続式において改めて他の関数ないし演算子に適用される時に初めて評価されて値存在になり、または改めて他の変数に束縛される時に初めて評価されて値存在になる。これが遅延評価のデフォルトタイミングである。[[継続]]コール(''call/cc'')手法や不可反駁(''irrefutable'')指定によって更に評価を遅延させる事もできる。継続コールは変数束縛した第一級関数またはクロージャを任意のタイミングで評価して値を導出できる機能である。これは値の導出後も式存在のままなので再利用できる。コール前の部分適用とコール時の引数適用、クロージャの方では自由変数への任意時代入も可能である。不可反駁指定はその式存在の変数部分が不特定で[[ボトム型]]を導出する場合は評価を取り止め、特定してる場合のみに評価を成立させて値存在にする機能である。ただしこれは遅延パターンマッチングでワンクッション置くための内包表記用途にほぼ限定されている。代数的データ型の式パターンは全て遅延評価対象になり、これによって無限リストの表現が可能になっている。 |
|||
プログラム実装上において先行評価は決して必須ではないが遅延評価の方は必須になる。帰納、再帰、無限、極限といった代数的表現は遅延評価でのみ実装できる。部分関数も遅延評価前提の式存在である。フロー分岐によって参照されなくなる式評価を結果的にスキップできる事は処理の高速化につながる。それはしばしばテクニックとしても用いられる。またボトム型が発生する式評価のスキップは[[フォールトトレラント設計|フォールトトレランス]]にもつながる。ただし柔軟な評価タイミングは同時に式存在と値存在の把握を難しくてバグの温床になりがちである。従って遅延評価が必要になる処理以外では、評価タイミングが明白な先行評価を標準にする方が理想と見なされている。従来の関数型言語はおおむね遅延評価を標準にしているが、先行評価標準の方が望ましいとする見方も広まっており純粋関数型や並行プログラミング分野では顕著である。 |
|||
=== 参照透過性 === |
=== 参照透過性 === |
||
[[参照透過性]]とは関数は同じ引数値に対して必ず同じ評価値を恒久的に導出し、その評価過程において現行計算枠外の情報資源に一切の作用を及ぼさないというプロセス上の枠組みを意味する。現行計算枠外のいずれかの情報資源が変化するのと同時にいずれかの関数の評価過程も変化してしまう現象は[[副作用 (プログラム)|副作用]]と呼ばれる。参照透過性はこの副作用の排除も同時に意味している。参照透過性の実装は、プログラムから代入(=''assignment''、≠''substitution'')処理を排除する事で具体的に成立する。 |
|||
純粋関数型言語は[[参照透過性]]をプログラム全体の枠組みにしている。その主な利点は一定の[[証明論]]に基づいたプルーフアシスタントによる[[正当性 (計算機科学)|プログラム正当性]]の自動的な[[形式的検証]]および[[論証|数学的論証]]が可能になる事である。プルーフアシスタントはソフトウェアツールである。ただしプログラム正当性が[[数学的証明|証明]]されてもランタイム環境側のプログラム運用部分のデバッグは残される事になる。プログラム全体に参照透過性を適用するには前述の”代入”を排除するコーディング上の注意の他に、プログラムレベルでは回避できない各種I/O作業に伴う必然的副作用の論理的排除も必要になるので専用のランタイム環境上での動作が必須になる。ランタイム環境は”環境データ”を走行プログラムとの仲介にする。プログラム内の各関数は、ライナー型引数値として渡された”環境データ”に作用するという形で各種I/O作業を行う。その仮想的I/O作業はランタイム環境側で実際に代行され、そのI/O作業で変化したコンピュータ環境はその都度”環境データ”に反映される。関数は”環境データ”をライナー型返り値として渡し返す。ライナ―型(''linear type'')は[[型理論]]における派生構造型(''substructural type'')の一形態であり[[線形合同法]]に似たデータ生成アルゴリズムによる全体的な整合性を取るための[[型システム]]である。これはユニークネス型とも呼ばれる。”環境データ”に”関連値”を注入する仕組みはアフィン型(''affine type'')、抽出する仕組みは関連型(''relevant type'')と呼ばれる。双方とも派生構造型の一形態である。このように各種I/O作業を”環境データ”への作用という形にする事で副作用を論理的に排除し、ライナー型の疑似乱数列に似た仕組みで参照透過性を論理的に維持している。この論理的とは言わば見せかけの意味に近いが、一定の問題をプログラム側から綺麗に切り離してランタイム環境側に丸投げできるメカニズムは開発上極めて有益と見なされている。なお、型システムの代わりに[[圏論]]を利用して全体的な整合性を取るための[[デザインパターン (ソフトウェア)|デザインパターン]]手法が[[モナド (プログラミング)|モナド]]である。”環境データ”を加工するモナド演算子は数学問題における[[公理]]や[[公式]]と同等の存在であり、決められたルールに従って用いるだけで副作用の排除と参照透過性の維持を論理的に表現できる。 |
|||
=== 型システム === |
=== 型システム === |
||
=== 純粋関数とイミュータブルと並行計算 === |
|||
== 歴史 == |
== 歴史 == |
||
1930年代に数学者[[アロンゾ・チャーチ]]によって発明された[[ラムダ計算]]は[[写像|関数適用]]をベースにした計算用[[形式体系]]であり、1937年に数学者[[アラン・チューリング]]自身により[[チューリング完全]]の性質が明らかにされて、[[チューリングマシン]]と等価な[[計算模型]]である事が証明されている。この経緯からラムダ計算は関数型プログラミングの基底に据えられた。ラムダ計算と同等の[[計算理論]]に[[コンビネータ論理]]があり、1920年代から1930年代にかけて数学者[[ハスケル・カリー]]らによって発明されている。こちらは関数型プログラミングの原点である[[高階論理]]式の基礎モデルにされた。チャーチはラムダ計算を拡張してその各タームに型を付与した[[型付きラムダ計算|型付けラムダ計算]]も考案しており、これは関数型プログラミングにおける[[型理論]]と[[型システム]]の源流になった。 |
|||
'''1950年代''' |
|||
現代的な関数型プログラミング言語の祖としてはアイディアが1966年に発表された[[ISWIM]]が挙げられるが、1970年前後までは関数型プログラミング言語の歴史はLISPの発展が主である。1970年代にプロジェクトが開始された[[ロジック・フォー・コンピュータブル・ファンクションズ]](英語版)のための言語として[[ML (プログラミング言語)|ML]]が作られている。またLISPにおいて、変数のスコープに静的スコープを採用したSchemeが誕生したのが1975年である。 |
|||
初の関数型プログラミング言語とされる「[[LISP]]」は、1958年に[[マサチューセッツ工科大学]]の計算機科学者[[ジョン・マッカーシー]]によって開発された。LISPの関数はラムダ計算の形式を元に定義され再帰可能に拡張されており、式のリスト化とその遅延評価および高階評価など幾つかの関数型的特徴を備えていた。LISPは数多くの”方言”を生み出しているが、その中でも「[[Scheme]]」「[[Dylan]]」「[[Racket]]」「[[Clojure]]」「Julia」は取り分け関数型の特徴を明確にした言語である。1956年に公開された「[[Information Processing Language]]」の方が先駆であるが、こちらはアセンブリベースの[[低水準言語]]なので前段階扱いである。IPLが備えていた[[ニーモニック・コード|ニーモニックコード]]のリストをオペランドにできるジェネレータ機能はLISPに影響を与えたと言われる。高階オペランドの演算処理は高階関数と同じ働きをし、メモリ一括処理のストリング命令の効率を高めるなどした。 |
|||
1977年、FORTRANの設計と[[バッカス・ナウア記法]]の発明の業績でこの年の[[チューリング賞]]を受賞した[[ジョン・バッカス]]は、''Can Programming Be Liberated From the von Neumann Style?: A Functional Style and Its Algebra of Programs''と題した受賞記念講演で関数型プログラミングの重要性を訴えた。講演では[[FP (プログラミング言語)|FP]]という関数型プログラミング言語の紹介もした(サブタイトルの後半の「プログラムの代数」はこれを指す)が、これは[[APL]](特に、[[高階関数]]の意味がある記号(APLの用語ではオペレーター([[作用素]])という))の影響を受けている。 |
|||
'''1960年代''' |
|||
バッカスのFPは広く使用されることはなかったが、この後関数型プログラミング言語の研究・開発は広まることとなった。1985年に[[Miranda]]が登場した。1987年に、遅延評価の純粋関数型プログラミング言語の標準の必要性が認識されHaskellの策定が始まった。1990年にHaskell 1.0仕様がリリースされた。同じく1990年にはMLの標準である[[Standard ML]]もリリースされている。Cleanは1987年に登場したが、発展の過程でHaskellの影響を受けている。1996年に、ML処理系のひとつであったCamlに[[オブジェクト指向]]を追加したOCamlが登場した。また日本ではSMLに独自の拡張を施した[[SML#]]が開発されている。 |
|||
1964年に計算機科学者[[ケネス・アイバーソン]]が開発した「[[APL]]」は、数多く定義された関数記号を多次元配列データに適用する機能を中心にした言語であり、取り分け[[スプレッドシート]]処理に対する効率性が見出されて、1960年代以降の商業分野と産業分野に積極導入された。APLは関数型ではなく配列プログラミング型に位置付けられてるが、配列を始めとするデータ集合に対する関数適用の有用性を特に証明した言語になった。そのデータ集合処理の可能性に注目した「J」「K」「Q」といった派生言語が後年に登場している。続く1966年に発表された「[[ISWIM]]」は関数型を有用な構文スタイルとして扱うマルチパラダイム言語の原点とされ、[[ALGOL]]を参考にした構造化プログラミングに高階関数とwhereスコープが加えられていた。60年代の関数型プログラミングの歴史はもっぱらLISPの発展を中心にしていたが、ISWIMは後年の「ML」「Scheme」のモデルにされている。 |
|||
21世紀に入ると、[[Java仮想マシン]]や[[共通言語基盤]](CLI)をランタイムとする関数型プログラミング言語を実装しようという動きが現れ、[[Scala]]・[[Clojure]]・[[F Sharp|F#]]などが登場した。 |
|||
'''1970年代''' |
|||
相互[[自動定理証明]]に向けて始められた「''Logic for computable functions''」プロジェクトの中で1973年に導入された「[[ML (プログラミング言語)|ML]]」は[[代数的データ型]]、[[多態性|パラメトリック多相]]、[[型推論]]などを備えた関数型言語であり、計算機科学者[[ロビン・ミルナー]]によって開発された。また1975年に[[MIT人工知能研究所]]の計算機科学者[[ガイ・スティール・ジュニア|ガイ・スティール]]と工学者[[ジェラルド・ジェイ・サスマン|ジェイ・サスマン]]が設計してAIリサーチ用に導入された「[[Scheme]]」は任意時評価(call/cc)[[継続|第一級継続]]などを備え、レキシカルスコープで構造化が図られており[[末尾再帰]]を最適化していた。MLとScheme双方の登場は関数型プログラミングのマイルストーンになった。また同年代に関数の数学的純粋性を重視した「SASL」と[[クリーネの再帰定理]]の実装を主な目的にした「Hope」も発表されている。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に導入される並列[[パイプライン処理]]に通じる構想であった。 |
|||
'''1980年代''' |
|||
数学者[[ペール・マルティン=レーフ|マルティン=レーフ]]が1972年から提唱していた直感的型理論は、関数型プログラミングの世界に[[型理論]]の[[依存型]]の重要性を認識させて[[型システム]]の拡張に貢献した。1978年にML設計者のミルナーが発表した型推論アルゴリズムが1982年に証明されると、''Hindley–Milner''型体系と定義されて型システムは更に成熟した。1983年にMLの標準化を目的にした「[[Standard ML]]」が発表され、続く1985年にMLの派生言語「Caml」が公開された。同じく1985年にSASLの後継として発表された「[[Miranda]]」は、遅延評価を標準にしながら関数の数学的純粋性を追求した言語であり、関数型プログラミング研究用[[オープン標準|オープンスタンダード]]のコンセンサスで1987年から策定が開始された[[Haskell]]のモデルになりその進捗を大きく後押しした。それと前後してMirandaは1987年公開の純粋関数型言語「[[Clean]]」にも大きな影響を与えている。Cleanは後発のHaskellをも叩き台にして改良を続けた。また関数型と[[並行計算]]の適性が認識される中で1986年の通信業界で開発された「[[Erlang]]」は[[並行プログラミング]]指向の面で特に注目を集めている言語である。 |
|||
'''1990年代''' |
|||
1990年にこれも関数型プログラミングのマイルストーン的な純粋関数型言語「[[Haskell]]」が初リリースされた。1992年に[[動的型付け]]レコードクラスと[[多重ディスパッチ]]メソッドを扱う関数型言語「[[Dylan]]」が登場した。1993年に[[ベクトル]]、[[行列]]、[[表 (データベース)|表テーブル]]などのデータストラクチャを扱えて[[統計的検定]]、[[時系列分析]]、[[データ・クラスタリング|クラスタリング]]分野に特化した関数型言語「[[R言語|R]]」が発表された。1995年にLISPの[[マクロ (コンピュータ用語)|マクロ]]機能を大幅に強化したコンポーネント指向により各分野に合わせた[[ドメイン固有言語]]として振る舞える「[[Racket]]」が登場した。1996年にはML系列のCamlにオブジェクト指向視点の[[抽象データ型]]を導入した「[[OCaml]]」が公開された。90年代の関数型プログラミングの歴史では、関数の数学的純粋さを追求する[[参照透過性]]指向とオブジェクト指向との連携が比較的目立っていた。日本ではStandard MLに独自の拡張を施した「SML#」が発表されている。風変りなものに[[コンビネータ論理]]の形式に立ち返った「[[Unlambda]]」がある。[[論理型プログラミング]]との親和性も見直されるようになり1995年に「Mercury」が公開された。論理型のルール&ファクトパラダイムはデータ集合に対するフィルタリングなどに活用された。1988年公開の「[[Wolfram (プログラミング言語)|Wolfram]]」はAPLスタイルのリスト処理に一定のデータリレーションを定義できる[[項書き換え]]を組み合わせた言語で90年代を通して改良が続けられていた。 |
|||
'''2000年代''' |
|||
2000年代になると関数型プログラミングへの注目度は更に高まり、マルチパラダイムに応用された関数型言語が様々に登場した。2003年のJava仮想マシン動作「[[Scala]]」、2005年のマイクロソフト製「[[F Sharp|F#]]」、2007年のLISP方言「[[Clojure]]」など数々のポピュラー言語が生み出されている。また直感的型理論と[[カリー=ハワード同型対応|カリー=ハワード同型対応]]の理論に基づいたプルーフアシスタント(''Proof assistant'')によるプログラム正当性の数学的証明を指向した関数型言語が支持され、2004年に「Epigram」2007年に「[[Agda]]」および純粋関数型「Idris」が発表されている。関数型構文の有用性がより広く認識されるに従い、オブジェクト指向言語やスクリプト言語にも積極的に導入されるようになった。産業分野からも注目されるようになり、[[Constructive Solid Geometry|CSG]]幾何フレームワーク上で動く[[CAD]]への導入も始められた。しかし関数型コンセプトに馴染まないオペレーターが定数化規則による値の再代入制限に困惑して設計作業に支障をきたすなどの弊害も明らかになっている。 |
|||
== 代表的な関数型言語 == |
== 代表的な関数型言語 == |
||
'''[[LISP]]''' (1958年) |
|||
{| class="wikitable sortable" |
|||
!言語 |
|||
: 動的型付け |
|||
!純粋さ |
|||
!型付け |
|||
'''[[ISWIM]]''' (1966年)← LISP、[[ALGOL]] |
|||
|- |
|||
|{{lang|en|[[Clean]]}}||純粋||強い、静的 |
|||
: 静的型付け |
|||
|- |
|||
|{{lang|en|[[Clojure]]}}||非純粋||動的 |
|||
[[ML (プログラミング言語)|'''ML''']] (1973年)← ISWIM |
|||
|- |
|||
|{{lang|en|[[Erlang]]}}||非純粋||動的 |
|||
: 静的型付け |
|||
|- |
|||
|{{lang|en|[[F Sharp|F#]]}}||非純粋||強い、静的 |
|||
'''[[Scheme]]''' (1975年)← LISP、ISWIM |
|||
|- |
|||
|{{lang|en|[[Haskell]]}}||純粋||強い、静的 |
|||
: LISP方言、動的型付け |
|||
|- |
|||
|{{lang|en|[[Idris]]}}||純粋||強い、静的 |
|||
[[FP (プログラミング言語)|'''FP''']] (1977年) |
|||
|- |
|||
|{{lang|en|[[Lazy K]]}}||純粋||型なし |
|||
: 純粋 |
|||
|- |
|||
|{{lang|en|[[LISP]]}}||非純粋||動的 |
|||
[[Standard ML|'''Standard ML''']] (1983年)← ML、Hope、[[Pascal|PASCAL]] |
|||
|- |
|||
|{{lang|en|[[Miranda]]}}||純粋||強い、静的 |
|||
: ML派生、静的型付け |
|||
|- |
|||
|{{lang|en|[[ML (プログラミング言語)|ML]]}}||非純粋||強い、静的 |
|||
'''[[Miranda]]''' (1985年)← ML、SASL、Hope |
|||
|- |
|||
|{{lang|en|[[SML#]]}}||非純粋||強い、静的 |
|||
: 純粋、静的型付け |
|||
|- |
|||
|{{lang|en|[[Standard ML]]}}||非純粋||強い、静的 |
|||
'''[[Erlang]]''' (1986年)← LISP、[[Prolog]]、[[Smalltalk]] |
|||
|- |
|||
|{{lang|en|[[OCaml]]}}||非純粋||強い、静的 |
|||
: 動的型付け |
|||
|- |
|||
|{{lang|en|[[Scala]]}}||非純粋||強い、静的 |
|||
'''[[Clean]]''' (1987年)← Miranda |
|||
|- |
|||
|{{lang|en|[[Scheme]]}}||非純粋||動的 |
|||
: 純粋、静的型付け |
|||
|- |
|||
|{{lang|en|[[Unlambda]]}}||非純粋||型なし |
|||
'''[[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派生、静的型付け |
|||
純粋関数型言語では、[[参照透過性]]が常に保たれるという意味において、全ての[[式 (プログラミング)|式]]や関数の「評価時」に[[副作用 (プログラム)|副作用]]を生まない。純粋関数型言語である{{lang|en|[[Haskell]]}}や{{lang|en|[[Clean]]}}は非[[正格]]な評価を基本としており、引数はデフォルトで[[遅延評価]]される。一方、{{lang|en|[[Idris]]}}は純粋だが正格評価を採用している。入出力などを[[参照透過性]]を保ったまま実現するために、たとえば {{lang|en|Haskell}} では[[モナド|モナド]]、{{lang|en|Clean}} では{{仮リンク|一意型|en|Uniqueness type}}という特殊な型を通して一貫性のある表現を提供する。 |
|||
'''[[Scala]]''' (2003年)← Scheme、Haskell、OCaml、Erlang、[[Smalltalk]]、[[Java]] |
|||
非純粋関数型言語では、参照透過性を壊す、副作用があるような式や関数も存在する。{{lang|en|LISP}}などでデータ構造の破壊的変更などの副作用を多用したプログラミングを行うと、それはもはや手続き型プログラミングである。多くの場合、非純粋関数型言語の[[評価戦略]]は正格評価(先行評価)であるが、遅延評価する部分を明示することで、無限リストなどを扱えるものもある。 |
|||
: 静的型付け |
|||
従来の手続き型と分類されるプログラミング言語においても、関数型プログラミングを行ないやすくなる機能を備えているものもある。[[C言語]]および[[C++]]は[[関数へのポインタ]]をサポートし、関数をオブジェクトのように扱うことができるが、関数ポインタによって[[第一級関数]]をサポートしているとみなされてはいない。なお、C# 3.0、[[C++11]]、Java 8など、後発の規格においてラムダ式([[無名関数]])をサポートするようになった言語もある。 |
|||
[[F Sharp|'''F#''']] (2005年)← Haskell、OCaml、Erlang、Scala、[[Python]]、[[C♯]] |
|||
{{lang|en|[[JavaScript]]}}や{{lang|en|[[Java]]}}など{{いつ範囲|date=2018年10月|近年}}の[[高水準言語]]には、関数型言語の機能や特徴を取り入れているものがあるが、変数の値やオブジェクトの状態を書き換えるプログラミングスタイルを通常とするため、関数型言語とは分類されない。一方{{lang|en|[[LISP]]}}は、その多くが副作用のある式や関数が多数あり、手続き型スタイルでのプログラミングがされることも多いが、理論的なモデル(「[[純LISP|純{{lang|en|LISP}}]]」)の存在や副作用を使わないプログラミングが基本であること、ないし主には歴史的理由から、関数型言語だとされることが多い。なお、{{lang|fr|Pascal}}では「手続き」と呼ばれるような値を返さない[[サブルーチン]]を、C言語では<!--<code>void</code>型の値を返す関数と捉える--><!--void型の値というものは存在せず、存在しないものについて、それを返す関数と「捉える」ことは常人には困難-->「関数」と呼んでいるが、これは単にルーチンについて、細分類して別の呼称を付けているか、細分類せず総称しているか、という分類と呼称の違いに過ぎず、「{{lang|fr|Pascal}}は手続き型言語で、C言語は関数型言語」<ref>[[共立出版]]『{{lang|en|ANSI C/C++}}辞典』ISBN 4-320-02797-3 など</ref>という一部の書籍に見られる記述は明確に誤りである。また、{{lang|en|OCaml}}や{{lang|en|Haskell}}などでは、「自明な値(例えば<code>()</code>)を返す」と、値を返さない(<code>Void</code>など)は違うものであり、後者は停止しないか例外を出す(そのため結果がない)ようなプログラムを表す。 |
|||
: 静的型付け |
|||
なお、「関数型言語である」と「関数型プログラミングをする」は同値ではなく、関数型には分類されない言語で関数型プログラミングをすること{{efn|関数型プログラミングのエッセンスとして、[[MISRA C]]のように[[C言語]]でも副作用を極力用いないプログラミングを推奨しているコーディング標準もある。}}や、関数型プログラミングを基本とする言語の上で他のパラダイムを実現する例もある<ref name="Novatchev">{{cite web|url=http://arxiv.org/abs/cs/0509027|author=Oleg Kiselyov, Ralf Lämmel|title=Haskell's overlooked object system|accessdate=Sep 10, 2005}}</ref>。[[データフロープログラミング]]言語も関数型言語と共通した特徴を部分的に持つ。<!--<ref>「関数型言語」に関するFAQ形式の一般的説明 https://qiita.com/esumii/items/ec589d138e72e22ea97e</ref>[[Wikipedia:検証可能性#通常は信頼できないとされる情報源]]--> |
|||
'''[[Clojure]]''' (2007年)← Scheme、Haskell、OCaml、Erlang、[[Java]] |
|||
'''その他の関数的性質を持つ言語''' |
|||
: LISP方言、動的型付け |
|||
*{{lang|en|[[APL]]}} |
|||
*{{lang|en|[[XSL Transformations|XSLT]]}} |
|||
== 関数型プログラミングの例 == |
== 関数型プログラミングの例 == |
2020年5月31日 (日) 04:59時点における版
![]() | この記事には独自研究が含まれているおそれがあります。 |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/8f/Orange_lambda.svg/200px-Orange_lambda.svg.png)
関数型言語(英: functional language)は、関数型プログラミングのスタイルまたはパラダイムを扱うプログラミング言語の総称である。関数型プログラミングは関数の適用と合成から組み立てられる宣言型プログラミングの一種であり、関数は引数の適用から先行式の評価を後続式の適用に繋げて終端評価に到る式のツリーとして定義される。関数は引数ないし返値として渡せる第一級関数として扱われる。
関数型プログラミングは数理論理学と代数系をルーツにし、ラムダ計算とコンビネータ論理を幹にして構築され、LISP言語が実装面の先駆になっている。応用面では圏論がパラダイムモデルにされている。関数の数学的な純粋性を指向したものは純粋関数型言語と個別に定義されている。命令型プログラミング言語では単に有用な構文スタイルとして扱われている事が多い。高階関数、第一級関数、関数合成、部分適用、無名関数、クロージャ、継続、部分関数、ポイントフリー、パイプライン、イテレータ、ジェネレータ、代数的データ型、型推論、パターンマッチング、ガード、パラメトリック多相、アドホック多相、末尾再帰、束縛変数、イミュータブル、純粋関数などが関数型プログラミングのスタイル要素として挙げられる[誰?]。
特徴
ここでは関数型プログラミング本来の構文スタイルを元にして説明する。式を基本文にする関数型に対して、ステートメントを基本文にする手続き型やオブジェクト指向などの命令型プログラミング言語では必要に応じて構文スタイルを変えて実装されている。代表的なのは「式の引数への適用」に対する「引数を関数に渡す」である。ただし双方ともアセンブリコード上では同様なものに符号化される。
値(value)は代数的データ型(algebraic data type)として表現される。代数的データ型は型理論にある様々なタイプの複合体であり、各タイプの表現代数式を各言語仕様に沿ったプログラムパーツで置き換えてあらゆる値を数学的に表現する仕組みである。代数的データ型は言わば「型の式」であり、その式パターンが「型」になり、式パターンの構築が「型付け」になる。結果的に全ての値は「型」で分類される事になる。代数的データ型の実装方法はそれを意識させない位単純なものから忠実なものまで言語ごとに様々である。代数的データ型は単体値を兼ねたあらゆる多重集合の表現になる。命令型言語での導入例はまず無くより平易で直感的な構造体やクラスが型付けに使われている。
式と関数
![]() |
- 関数型プログラムの基本文は式(expression)である。
- 式は、値(value)と演算子(operator)と関数(function)で構成される。値は束縛変数と自由変数を包括する。式内の変数部分が特定される前の式は評価できないボトム型存在である。特定後は評価戦略に従ったタイミングで評価(evaluation)されて式存在から値存在になる。
- 式は値と同一視されるので上述の式と値は相互再帰の関係にある。式内の値は他の式の評価値である事があり、その式内にもまた他の値があるといった具合である。この仕組みは高階論理と呼ばれる。
- 関数も値と同一視される。関数は式に引数を結び付ける機能であり、これは式の引数への適用(application)と呼ばれる。式内の仮引数(parameter)箇所に実引数(argument)が順次当てはめられ、式ツリーの終端式が評価値になる。
- 関数は、式を第1引数に適用したもの→第2引数に適用したもの→第x引数に適用したもの→評価値、という形をとる。引数を1個ずつ適用する形態はカリー化と呼ばれる。2個以上の引数を同時適用する形態は非カリー化と呼ばれる。関数の型は「A→B→C→D」のように各引数値から評価値までの写像パターンで表現される。
- 関数も高階論理に組み込まれている。引数値または評価値として扱うことができる関数は第一級関数と呼ばれる。その第一級関数を扱うことができる関数は高階関数と呼ばれる。
- カリー化された関数は引数の適用を途中で止めて残り引数を後から適用できる第一級関数を生成できる。これは部分適用と呼ばれる。
- 片方の評価値と片方の第1引数が同じ型の両関数は任意に連結できる。この双方の写像のつなぎ合わせは関数合成と呼ばれる。
- 仮引数記述を省略した関数はポイントフリーと呼ばれ、その省略箇所に先行式評価値が実引数として暗黙適用される。実引数記述を省略して先行式評価値を後続関数の仮引数箇所に暗黙適用するのもポイントフリーと呼ばれる。この暗黙適用の式を並べて連鎖させる手法はパイプラインと呼ばれる。言語によっては特別な演算子と併せて明示する。
- 関数は名前付きと名前無しの二通りある。後者はラムダ抽象を模した構文で式中に直接定義される。これは無名関数と呼ばれる。式内に自由変数を持った無名関数はクロージャと個別に定義される。自由変数には外部データが代入される。自身を参照する無名関数を内包したデータ構造体(=関数オブジェクト)もクロージャに相当する。
- 無名関数は引数をピュアマッピングする純粋関数であるが、毎回違う値が渡される用途から事実上メモ化できない事がコーディング上の利便性を除いた存在理由になっている。クロージャの引数マッピングは式内の自由変数に影響され、またその自由変数に作用する事もある即ち副作用要素を閉包した非純粋関数である。
- 関数の名前は、それに結び付けられた式または式ツリーの不動点の表現になる。自式の不動点を式内に置いて新たな引数と共に高階論理の式として評価する手法は再帰と呼ばれる。
- イミュータブル性が重視されない場合、関数の終端式での再帰は、実引数の更新+先端式へのアドレスジャンプと同等に見なせるので専らそちらに最適化される。これは末尾再帰と呼ばれる。相互再帰を同様に最適化したものは兄弟再帰(sibling recursion)と呼ばれる。
- リスト処理時にリストの各要素に対する作用子として渡される第一級関数はイテレータと呼ばれる。作用後の各要素を別の新生リストに向けて複製する働きを加えたものはジェネレータと呼ばれる。これはイミュータブル重視時に多用される。前者はポイントフリーの無名関数、後者はポイントフリーのクロージャとして定義される事が多い。
- 任意のタイミングで遅延評価(call/cc)される用途の第一級関数は特別に継続と呼ばれる。関数の引数を順々に評価して間に分岐などを挟める継続渡しスタイルはその応用例である。
- 部分関数は引数によってボトム型を返せる関数である。ボトム型は命令型言語における例外発生と同等に解釈できる。
- 演算子はデフォルトの式内容を持ち、引数が1~2個に限定された関数と同義である。部分適用された演算子はセクションと呼ばれる第一級関数になる。演算子は任意の型にフックさせた再定義および追加定義ができる。これはアドホック多相と呼ばれる。
値と代数的データ型
![]() |
- 値(value)は代数的データ型(algebraic data type)として表現される。代数的データ型は型理論にある様々なタイプの複合体である。代数的データ型は言わば「型の式」である。
- 代数的データ型の式パターンは型構築子(type constructor)に束縛される。型構築子は新たな代数的データ型の識別名になる。式パターン内で代数的データ型は入れ子にできる。その入れ子とプロパー型は式パターン内で型変数(type variable)として扱われ、パラメトリック多相で総称化できる。型構築子は型引数(type parameter)と併せて定義され、総称化された各要素を決定する。
- 数値、論理値、文字値、文字列はプロパー型(proper type)に分類され、最も基本的な式パターン要素になる。
- 代数的データ型は、代数的データ型の入れ子で帰納的に構成される事もあるがその末端は必ずプロパー型になる。この帰納的な仕組みは高階型(higher-order types)と呼ばれる。
- 代数的データ型は、プロパー型に到るまでの帰納パターンであるカインドで抽象化分類される。カインドは「*→*」「*」のように表現される。カインドはパターンマッチングと型シノニムの成立基準になる。
- 左辺のもので右辺のものを置き換えられるという代数的データ型間の項書き換えルールを定義できる。これは型シノニムと呼ばれる。リスコフの置換原則に似たものである。
- 代数的データ型は、直積型(product type)非交和型(sum type)帰納型(inductive type)依存型(dependent type)ユニット型(unit type)などのタイプを持つ。式的役割は直積型=×演算子、非交和型=+演算子、帰納型=式再帰または高階式、依存型=パターンマッチング式、ユニット型=NILである。この5タイプで大半の値を表現できる。
- 直積型は、(A, B) のようなタプルのパターンを表わす。また標準的なレコードを表現する。
- 非交和型は、(A | B) のような修飾共用体または列挙型のパターンを表わす。
- 帰納型は、ボックス化と前述の入れ子のパターンを表わす。また帰納型と非交和型とユニット型は併用されて連結リスト、二分木、データツリーのパターンを表わす。
- 依存型は、一つの依存値によるパターンマッチング式をそのままタイプと見なしたものである。そのケース節パターンのみはオプション型(option type)ガード節パターンのみはリファイン型(refinement type)と個別定義される。これらは動的配列、Maybe値、リスト内包表記などの構造を表わす。
- ユニット型は、NILないしVOIDであり空集合のパターンを表わす。
- 交差型(intersection type)は、型クラスや型エイリアスなどのアドホック多相によるパターンの表現に用いられる。
- パターンマッチング式は、CASE式の値に依存した依存型またはオプション型のその場構築である。条件分岐式(IF-THEN-ELSE)は、IF式の値に依存したリファイン型のその場構築である。前者は型推論と式評価による等価性または等値性のパターン審査を行う。後者は式評価による等値性または順序性の論理的審査を行う。
- 関数の写像パターンは指数型(exponential type)で説明される。”関数適用の評価値”は指数型と直積型の併用で表現される。そのまま関数の型(function type)と呼ばれる事が多い。関数のパターンマッチングはもっぱらアドホック多相の方で解釈される。
- 型推論は、代数的データ型の式パターンを等価性を審査できる形まで演繹する機能である。これはいわゆる「型」を導き出すのと同義である。この機能により束縛変数の型注釈はもっぱら省略される。型推論は値の等価性審査の手段であり、いわゆる型チェックや遅延パターンマッチングなどを実現する。
評価戦略
関数型プログラミングにおける評価戦略とは「式存在」を「値存在」にする評価タイミングの定義を指す。これはまず正格評価(strict evaluation)と非正格評価(non-strict evaluation)の二つに大別される。前者の式存在は、関数による適用と同時に評価されて値存在になり、または変数による束縛と同時に評価されて値存在になる。関数の引数節で直積された式存在は理論上全て同時に評価される事になる。その実装は直積された式存在を副作用を伴わずに並行計算するか、そうでない場合は一つ一つ評価していく事になる。単に一つ一つ評価していくものは先行評価になり、ここでも副作用を伴わない事が原則とされるが必須ではなくなる。
後者の非正格評価はほとんどのケースで遅延評価と同義の言葉になる。遅延評価の式存在は、関数に適用されても式存在のままであり、または変数に束縛されても式存在のままである。後続式において改めて他の関数ないし演算子に適用される時に初めて評価されて値存在になり、または改めて他の変数に束縛される時に初めて評価されて値存在になる。これが遅延評価のデフォルトタイミングである。継続コール(call/cc)手法や不可反駁(irrefutable)指定によって更に評価を遅延させる事もできる。継続コールは変数束縛した第一級関数またはクロージャを任意のタイミングで評価して値を導出できる機能である。これは値の導出後も式存在のままなので再利用できる。コール前の部分適用とコール時の引数適用、クロージャの方では自由変数への任意時代入も可能である。不可反駁指定はその式存在の変数部分が不特定でボトム型を導出する場合は評価を取り止め、特定してる場合のみに評価を成立させて値存在にする機能である。ただしこれは遅延パターンマッチングでワンクッション置くための内包表記用途にほぼ限定されている。代数的データ型の式パターンは全て遅延評価対象になり、これによって無限リストの表現が可能になっている。
プログラム実装上において先行評価は決して必須ではないが遅延評価の方は必須になる。帰納、再帰、無限、極限といった代数的表現は遅延評価でのみ実装できる。部分関数も遅延評価前提の式存在である。フロー分岐によって参照されなくなる式評価を結果的にスキップできる事は処理の高速化につながる。それはしばしばテクニックとしても用いられる。またボトム型が発生する式評価のスキップはフォールトトレランスにもつながる。ただし柔軟な評価タイミングは同時に式存在と値存在の把握を難しくてバグの温床になりがちである。従って遅延評価が必要になる処理以外では、評価タイミングが明白な先行評価を標準にする方が理想と見なされている。従来の関数型言語はおおむね遅延評価を標準にしているが、先行評価標準の方が望ましいとする見方も広まっており純粋関数型や並行プログラミング分野では顕著である。
参照透過性
参照透過性とは関数は同じ引数値に対して必ず同じ評価値を恒久的に導出し、その評価過程において現行計算枠外の情報資源に一切の作用を及ぼさないというプロセス上の枠組みを意味する。現行計算枠外のいずれかの情報資源が変化するのと同時にいずれかの関数の評価過程も変化してしまう現象は副作用と呼ばれる。参照透過性はこの副作用の排除も同時に意味している。参照透過性の実装は、プログラムから代入(=assignment、≠substitution)処理を排除する事で具体的に成立する。
純粋関数型言語は参照透過性をプログラム全体の枠組みにしている。その主な利点は一定の証明論に基づいたプルーフアシスタントによるプログラム正当性の自動的な形式的検証および数学的論証が可能になる事である。プルーフアシスタントはソフトウェアツールである。ただしプログラム正当性が証明されてもランタイム環境側のプログラム運用部分のデバッグは残される事になる。プログラム全体に参照透過性を適用するには前述の”代入”を排除するコーディング上の注意の他に、プログラムレベルでは回避できない各種I/O作業に伴う必然的副作用の論理的排除も必要になるので専用のランタイム環境上での動作が必須になる。ランタイム環境は”環境データ”を走行プログラムとの仲介にする。プログラム内の各関数は、ライナー型引数値として渡された”環境データ”に作用するという形で各種I/O作業を行う。その仮想的I/O作業はランタイム環境側で実際に代行され、そのI/O作業で変化したコンピュータ環境はその都度”環境データ”に反映される。関数は”環境データ”をライナー型返り値として渡し返す。ライナ―型(linear type)は型理論における派生構造型(substructural type)の一形態であり線形合同法に似たデータ生成アルゴリズムによる全体的な整合性を取るための型システムである。これはユニークネス型とも呼ばれる。”環境データ”に”関連値”を注入する仕組みはアフィン型(affine type)、抽出する仕組みは関連型(relevant type)と呼ばれる。双方とも派生構造型の一形態である。このように各種I/O作業を”環境データ”への作用という形にする事で副作用を論理的に排除し、ライナー型の疑似乱数列に似た仕組みで参照透過性を論理的に維持している。この論理的とは言わば見せかけの意味に近いが、一定の問題をプログラム側から綺麗に切り離してランタイム環境側に丸投げできるメカニズムは開発上極めて有益と見なされている。なお、型システムの代わりに圏論を利用して全体的な整合性を取るためのデザインパターン手法がモナドである。”環境データ”を加工するモナド演算子は数学問題における公理や公式と同等の存在であり、決められたルールに従って用いるだけで副作用の排除と参照透過性の維持を論理的に表現できる。
型システム
歴史
1930年代に数学者アロンゾ・チャーチによって発明されたラムダ計算は関数適用をベースにした計算用形式体系であり、1937年に数学者アラン・チューリング自身によりチューリング完全の性質が明らかにされて、チューリングマシンと等価な計算模型である事が証明されている。この経緯からラムダ計算は関数型プログラミングの基底に据えられた。ラムダ計算と同等の計算理論にコンビネータ論理があり、1920年代から1930年代にかけて数学者ハスケル・カリーらによって発明されている。こちらは関数型プログラミングの原点である高階論理式の基礎モデルにされた。チャーチはラムダ計算を拡張してその各タームに型を付与した型付けラムダ計算も考案しており、これは関数型プログラミングにおける型理論と型システムの源流になった。
1950年代
初の関数型プログラミング言語とされる「LISP」は、1958年にマサチューセッツ工科大学の計算機科学者ジョン・マッカーシーによって開発された。LISPの関数はラムダ計算の形式を元に定義され再帰可能に拡張されており、式のリスト化とその遅延評価および高階評価など幾つかの関数型的特徴を備えていた。LISPは数多くの”方言”を生み出しているが、その中でも「Scheme」「Dylan」「Racket」「Clojure」「Julia」は取り分け関数型の特徴を明確にした言語である。1956年に公開された「Information Processing Language」の方が先駆であるが、こちらはアセンブリベースの低水準言語なので前段階扱いである。IPLが備えていたニーモニックコードのリストをオペランドにできるジェネレータ機能はLISPに影響を与えたと言われる。高階オペランドの演算処理は高階関数と同じ働きをし、メモリ一括処理のストリング命令の効率を高めるなどした。
1960年代
1964年に計算機科学者ケネス・アイバーソンが開発した「APL」は、数多く定義された関数記号を多次元配列データに適用する機能を中心にした言語であり、取り分けスプレッドシート処理に対する効率性が見出されて、1960年代以降の商業分野と産業分野に積極導入された。APLは関数型ではなく配列プログラミング型に位置付けられてるが、配列を始めとするデータ集合に対する関数適用の有用性を特に証明した言語になった。そのデータ集合処理の可能性に注目した「J」「K」「Q」といった派生言語が後年に登場している。続く1966年に発表された「ISWIM」は関数型を有用な構文スタイルとして扱うマルチパラダイム言語の原点とされ、ALGOLを参考にした構造化プログラミングに高階関数とwhereスコープが加えられていた。60年代の関数型プログラミングの歴史はもっぱらLISPの発展を中心にしていたが、ISWIMは後年の「ML」「Scheme」のモデルにされている。
1970年代
相互自動定理証明に向けて始められた「Logic for computable functions」プロジェクトの中で1973年に導入された「ML」は代数的データ型、パラメトリック多相、型推論などを備えた関数型言語であり、計算機科学者ロビン・ミルナーによって開発された。また1975年にMIT人工知能研究所の計算機科学者ガイ・スティールと工学者ジェイ・サスマンが設計してAIリサーチ用に導入された「Scheme」は任意時評価(call/cc)第一級継続などを備え、レキシカルスコープで構造化が図られており末尾再帰を最適化していた。MLとScheme双方の登場は関数型プログラミングのマイルストーンになった。また同年代に関数の数学的純粋性を重視した「SASL」とクリーネの再帰定理の実装を主な目的にした「Hope」も発表されている。1977年、バッカス・ナウア記法とFORTRAN開発の功績でこの年のチューリング賞を受けた計算機科学者ジョン・バッカスは「Can Programming Be Liberated From the von Neumann Style? -A Functional Style and Its Algebra of Programs-」と題した記念講演を行い、一説にはこれを境にして関数型(functional)というパラダイム名が定着したと言われる。なお同時に発表された「FP」は関数水準(function-level)言語として紹介されている。バッカスはFPのプログラムをアトム+関数+フォーム(=高階関数)の階層構造と定義し、代数を用いるフォームの結合で全体構築されると提唱した。ノイマン型からの脱却を題目に掲げているバッカスの理論は、後年のCPUに導入される並列パイプライン処理に通じる構想であった。
1980年代
数学者マルティン=レーフが1972年から提唱していた直感的型理論は、関数型プログラミングの世界に型理論の依存型の重要性を認識させて型システムの拡張に貢献した。1978年にML設計者のミルナーが発表した型推論アルゴリズムが1982年に証明されると、Hindley–Milner型体系と定義されて型システムは更に成熟した。1983年にMLの標準化を目的にした「Standard ML」が発表され、続く1985年にMLの派生言語「Caml」が公開された。同じく1985年にSASLの後継として発表された「Miranda」は、遅延評価を標準にしながら関数の数学的純粋性を追求した言語であり、関数型プログラミング研究用オープンスタンダードのコンセンサスで1987年から策定が開始されたHaskellのモデルになりその進捗を大きく後押しした。それと前後してMirandaは1987年公開の純粋関数型言語「Clean」にも大きな影響を与えている。Cleanは後発のHaskellをも叩き台にして改良を続けた。また関数型と並行計算の適性が認識される中で1986年の通信業界で開発された「Erlang」は並行プログラミング指向の面で特に注目を集めている言語である。
1990年代
1990年にこれも関数型プログラミングのマイルストーン的な純粋関数型言語「Haskell」が初リリースされた。1992年に動的型付けレコードクラスと多重ディスパッチメソッドを扱う関数型言語「Dylan」が登場した。1993年にベクトル、行列、表テーブルなどのデータストラクチャを扱えて統計的検定、時系列分析、クラスタリング分野に特化した関数型言語「R」が発表された。1995年にLISPのマクロ機能を大幅に強化したコンポーネント指向により各分野に合わせたドメイン固有言語として振る舞える「Racket」が登場した。1996年にはML系列のCamlにオブジェクト指向視点の抽象データ型を導入した「OCaml」が公開された。90年代の関数型プログラミングの歴史では、関数の数学的純粋さを追求する参照透過性指向とオブジェクト指向との連携が比較的目立っていた。日本ではStandard MLに独自の拡張を施した「SML#」が発表されている。風変りなものにコンビネータ論理の形式に立ち返った「Unlambda」がある。論理型プログラミングとの親和性も見直されるようになり1995年に「Mercury」が公開された。論理型のルール&ファクトパラダイムはデータ集合に対するフィルタリングなどに活用された。1988年公開の「Wolfram」はAPLスタイルのリスト処理に一定のデータリレーションを定義できる項書き換えを組み合わせた言語で90年代を通して改良が続けられていた。
2000年代
2000年代になると関数型プログラミングへの注目度は更に高まり、マルチパラダイムに応用された関数型言語が様々に登場した。2003年のJava仮想マシン動作「Scala」、2005年のマイクロソフト製「F#」、2007年のLISP方言「Clojure」など数々のポピュラー言語が生み出されている。また直感的型理論とカリー=ハワード同型対応の理論に基づいたプルーフアシスタント(Proof assistant)によるプログラム正当性の数学的証明を指向した関数型言語が支持され、2004年に「Epigram」2007年に「Agda」および純粋関数型「Idris」が発表されている。関数型構文の有用性がより広く認識されるに従い、オブジェクト指向言語やスクリプト言語にも積極的に導入されるようになった。産業分野からも注目されるようになり、CSG幾何フレームワーク上で動くCADへの導入も始められた。しかし関数型コンセプトに馴染まないオペレーターが定数化規則による値の再代入制限に困惑して設計作業に支障をきたすなどの弊害も明らかになっている。
代表的な関数型言語
LISP (1958年)
- 動的型付け
- 静的型付け
ML (1973年)← ISWIM
- 静的型付け
Scheme (1975年)← LISP、ISWIM
- LISP方言、動的型付け
FP (1977年)
- 純粋
Standard ML (1983年)← ML、Hope、PASCAL
- ML派生、静的型付け
Miranda (1985年)← ML、SASL、Hope
- 純粋、静的型付け
Erlang (1986年)← LISP、Prolog、Smalltalk
- 動的型付け
Clean (1987年)← Miranda
- 純粋、静的型付け
Haskell (1990年)← ML、Scheme、Miranda、Clean、FP
- 純粋、静的型付け
Dylan (1993年)← Scheme、CLOS、ALGOL
- LISP方言、動的型付け
- 動的型付け
- LISP方言、動的型付け
OCaml (1996年)← Caml、Standard ML、Modula-3
- ML派生、静的型付け
Scala (2003年)← Scheme、Haskell、OCaml、Erlang、Smalltalk、Java
- 静的型付け
F# (2005年)← Haskell、OCaml、Erlang、Scala、Python、C♯
- 静的型付け
Clojure (2007年)← Scheme、Haskell、OCaml、Erlang、Java
- LISP方言、動的型付け
関数型プログラミングの例
関数型プログラミングは「計算とは何か」という数学の理論を基礎にしており、関数型プログラミングがもつ計算モデルは関数モデルである[1]。たとえば、1 から 10 までの整数を足し合わせるプログラムを考える[注釈 1]。命令型プログラミングでは以下のようにループ文を使って変数に数値を足していく(計算機の状態を書き換える)命令を繰り返し実行するという形を取る。
- Pascalによる例:
program test;
var total, i : Integer;
begin
total := 0;
for i := 1 to 10 do
total := total + i;
WriteLn(total)
end.
一方、関数型プログラミングでは、繰り返しには一時変数およびループを使わず、関数の再帰呼び出しを使う。
- F#による例:
printfn "%d" (let rec sum x = if x > 0 then x + sum (x - 1) else 0
sum 10)
ただし再帰呼び出しはスタックオーバーフローの危険性やオーバーヘッドを伴うため、注意深く使用しなければならない[2]。通例、関数型言語では、末尾再帰呼び出し (tail-recursive call) の形で書かれた関数をループに展開する末尾呼出し最適化により、スタックオーバーフローの危険性および再帰のオーバーヘッドを解消できる。Schemeなど、関数型言語の中には末尾再帰呼び出しの最適化を仕様で保証するものもある。再帰関数を末尾再帰に書き換えることが難しいケースも有り、そのような場合は一般的なループが採用される。
また、関数型言語は文 (statement) よりも式 (expression) を中心とした言語仕様となっていることも特徴である。前述の例において、再帰関数sum
を束縛するlet
は式である。また、条件分岐のif-then-else
も式である。文よりも式で書けることが多いほうが都合がよい。
関数型言語は関数型プログラミングをサポートする言語ではあるが、手続き型プログラミングを行なうことも可能である。例えばF#では以下のようなPascal風の書き方もできる。
let mutable total = 0
for i = 1 to 10 do
total <- total + i
printfn "%d" total
ただしHaskellのようにループ構文をサポートせず、従来の手続き型プログラミングが難しいケースもある。
逆に手続き型言語を使って関数型プログラミングを行なうことも可能であるが、末尾再帰呼び出しの最適化がサポートされるかどうかはコンパイラ次第である。
脚注
注釈
出典
- ^ 計算モデル2 関数モデル. (中略) 関数モデルに基づくプログラミング言語. 関数型言語. Lisp 犬塚信博 (2007)「プログラミング言語論 第1回 イントロダクション」名古屋工業大学
- ^ 関数 (F#) | MSDN
外部リンク