「関数型プログラミング」の版間の差分
削除された内容 追加された内容
m い抜き言葉「やってる」「してる」の使用を回避 |
式と関数 |
||
(同じ利用者による、間の34版が非表示) | |||
1行目:
{{独自研究|date=2014年4月}}
[[ファイル:Orange_lambda.svg|代替文=|境界|右|フレームなし|209x209px]]
{{Template:プログラミング・パラダイム}}
'''関数型言語'''({{lang-en-short|''functional language''}})は、'''関数型プログラミング'''のスタイルまたは[[プログラミングパラダイム|パラダイム]]を扱う[[プログラミング言語]]の総称である。関数型プログラミングは関数の[[写像|適用]]をベースにした[[宣言型プログラミング]]の一形態であり、関数は[[引数]]の適用から先行式の評価を後続式の適用につなげて終端の[[評価戦略|評価]]を導き出す[[式 (プログラミング)|式]]の[[ツリー構造]]として定義される。式の評価に伴う[[副作用 (プログラム)|副作用]]の発生には大きな注意が払われる。関数は引数ないし返り値として渡せる[[第一級オブジェクト]]として扱われる。
関数型プログラミングは[[数理論理学]]と代数系をルーツにし、[[ラムダ計算]]と[[コンビネータ論理]]を幹にして構築され、[[LISP]]言語が実装面の先駆になっ
== 特徴 ==
{{出典の明記| date = 2020年5月6日 (水) 02:29 (UTC)| section = 1}}
ここでは関数型プログラミング本来の構文スタイルを元にして説明する。式を基本文にする関数型に対して、[[文 (プログラミング)|ステートメント]]を基本文にする[[命令型プログラミング]]言語では必要に応じて構文スタイルを変えて実装されている。代表的なのは「式に引数を適用する」に対する「関数に引数を渡す」である。値とその型付けに対するコンセプトおよびデータストラクチャの実装スタイルも異なっている。ただし双方ともアセンブリコード上では同様なものに符号化される。
=== 式と関数 ===
関数型プログラムの基本文は[[式 (プログラミング)|式]](''expression'')である。式は値(''value'')と関数(''function'')で構成される。関数の定義には[[演算子]](''operator'')も含まれている。値は後節で述べる[[データ構造|データストラクチャ]]と、[[ラムダ計算]]で言われる変数(''variable'')の双方を意味する。データストラクチャの定義には数値、論理値、文字値、文字列といった基本データ型=[[プリミティブ型|プリミティブ]]も含まれている。変数は[[束縛変数]]と[[自由変数と束縛変数|自由変数]]を指す。評価(''evaluation'')される前の式は、ラムダ計算で言われるネーム(''name'')と同義になる。ネームは数学上の数式または代数式に相当するものである。式は、式内の変数部分が確定される前は評価できない[[ボトム型]]であり、これはラムダ抽象(''abstraction'')と同義である。式内の変数部分を確定するのはラムダ適用(''application'')と同義である。このネームが評価されると値になり、これはラムダ計算で言われる簡約(''reduction'')と同義である。式は値と同一視されるので、すなわち式と値は相互再帰の関係にある。式内の値は他の式の評価値である事があり、その式内にもまた他の値があるといった具合である。この仕組みは[[高階論理]]''と呼ばれる。''
関数も値と同一視される。関数は写像の型の値であるが、プログラム的には式に引数を結び付ける機能であり、これは式に引数を[[写像|適用]](''application'')すると呼ばれる。式内の仮引数(''parameter'')箇所に実引数(''argument'')が順次当てはめられ、式ツリーの終端式が評価値になる。引数によっては[[ボトム型]]になる関数もありこれは部分関数と呼ばれる。ボトム型は虚(''falsity'')と見なされており、式のツリーないし写像の連鎖の失敗した終着点になる。関数は、式に第1引数を適用したもの→第x引数を適用したもの→評価値、という形をとる。引数を1個ずつ適用する形態は[[カリー化]]と呼ばれる。2個以上の引数を同時適用する形態は非カリー化と呼ばれる。関数の型(''function type'')は「A→B→C」のように各引数値から評価値までの写像パターンで表現される。片方の評価値と片方の第1引数が同じ型の両関数は任意に連結して新たな関数にできる。この双方の写像のつなぎ合わせは関数合成と呼ばれる。カリー化された関数は引数の適用を途中で止めて残り引数を後から適用するように保留できる。この保留状態の関数の生成は部分適用と呼ばれる。任意のタイミングで遅延評価(''call/cc'')するために評価を保留してる関数は[[継続]]と呼ばれる。その応用に、一つの式を個々の演算子適用(関数適用)に分解して各個[[継続]]化し、それらをボトムアップで組み上げて一つの継続集合体を生成する[[継続渡しスタイル]]がある。部分適用と継続はネームと同義である。関数も当然ながら[[高階論理]]に組み込まれている。引数値または評価値として扱うことができる関数は[[第一級関数]]と呼ばれる。その第一級関数を扱うことができる関数は[[高階関数]]と呼ばれる。
関数は名前付きと名前無しの二通りある。名前無しの関数は専らラムダ抽象を模した構文で定義される。式内に自由変数を内包しない方は[[無名関数]]と呼ばれ、自由変数を内包する方はそれを囲い込むという意味で[[クロージャ]]と呼ばれる。自由変数は外部データへの接点になる。[[無名関数]]は引数をピュア[[写像|マッピング]]する純粋関数である。[[クロージャ]]の引数の[[写像|マッピング]]は式内の自由変数に影響され、またその自由変数に作用する事もあるという副作用要素を閉包した非純粋関数である。関数の名前は、それに結び付けられた式または式ツリーの[[不動点]]の表現になる。自式の不動点を式内に置いて新たな引数と共に[[高階論理]]の式として評価する手法は[[再帰]]と呼ばれる。関数の終端式での再帰は実引数の更新+先端式へのアドレスジャンプと同等に見なせるのでもっぱらそちらに最適化されてこれは[[末尾再帰]]と呼ばれる。末尾再帰は論理性を損なわずにスタック資源から離れた無制限ループを可能にする実装概念として重視されている。名前付き関数で、仮引数記述を省略したものはポイントフリーと呼ばれ、その省略箇所に先行式評価値が実引数として暗黙適用される。名前無し関数で、先行式評価値を実引数にする記述を省略して、その仮引数箇所に暗黙適用するのもポイントフリーと呼ばれる。この暗黙適用の式を並べて連鎖させる手法は[[パイプライン処理|パイプライン]]と呼ばれるが、言語によっては特別な演算子と併せて明示する。リスト処理時にリストの各要素に対する作用子として渡される第一級関数は[[反復子|イテレータ]]と呼ばれる。作用後の各要素を別の新生リストに向けて複製する働きを加えたものは[[ジェネレータ (プログラミング)|ジェネレータ]]と呼ばれる。これは[[イミュータブル]]重視時に多用される。イテレータはポイントフリーの無名関数、ジェネレータはポイントフリーのクロージャとして定義される事が多い。
関数名は[[関手]]の識別子と同義なので、同じ識別子に個別の引数パターン候補を付けたものを列挙することで[[非交和]]または[[選言]]の関係でつなげる事ができる。これは[[多重定義|関数のパターンマッチング]]と呼ばれる。また、変数名を直接[[関手]]の識別子と見なしてパターンマッチ候補を列挙して非交和の関係でつなげる方は[[パターンマッチング|パターンマッチング式]]と呼ばれる。パターンマッチングは等価性照合、等値性照合、任意の要素をワイルドカードにした部分的等値性照合のいずれかで行われる。パターンマッチで特定された実引数値ないし変数値を更に任意の等値式または比較式で真偽判定し、その結果に従った写像の二択分岐や、偽の場合はパターンマッチをそこで無効にして写像をキャンセルする事もできる。これは[[ガード (プログラミング)|ガード]]と呼ばれる。
演算子はデフォルトの式内容を持ち、その引数が単項演算子なら1個、二項演算子なら2個に限定された関数と同義である。部分適用された演算子はセクションと呼ばれる。演算子は任意の型をフックした、又は任意の型にフックさせた再定義および追加定義ができる。前者のフックしたは関数のパターンマッチングと同じ仕組みで、後者のフックさせたは抽象データ型の静的メンバ関数と同じ仕組みで実装される。双方ともアドホック多相に該当するものである。
=== 値とデータストラクチャ ===
関数型プログラミングの値(''value'')は、単体値を兼ねたあらゆる[[多重集合]]を表わすデータストラクチャ(''data structure'')として実装される。単体値なデータストラクチャはただの[[プリミティブ型|プリミティブ]]である。そうでないの方のデータストラクチャは[[プリミティブ型|プリミティブ]]と[[構造体|コンポジット]]のミックスである。ただしこれは端的な表現であり、より正確な説明は後節に先送りする。プリミティブは数値、論理値、文字値、文字列を指す。コンポジットはC言語などの構造体と同等である。まずプリミティブが型構築子(''type constructor'')によってまとめられる。正確ではないが型構築子=構造体と見てもよい。型構築子は入れ子にできるので、型構築子をまとめた型構築子を定義できる。自分自身(型構築子)を入れ子にした再帰構造も定義できる。プリミティブと型構築子を任意に組み合わせた様々な型構築子の総称がデータストラクチャである。関数型言語で用いられるデータストラクチャの代表例は[[代数的データ型]]と[[S式]]である。データストラクチャ内のプリミティブとコンポジットの組み合わせはパターン(''pattern'')と呼ばれる。パターンには[[アノテーション]]要素や[[ガード (プログラミング)|ガード]]要素も加えられる。そのパターンが型になり、パターンの構築が型付けになり、パターンを[[量化]](''quantify'')すると型付け値になり、これはターム(''term'')と呼ばれる。タームは冒頭の値(''value'')を指す。型構築子のパターンの末端は必ずプリミティブになるので、パターン内の全てのプリミティブの値を決定することが量化になる。特定の文脈が求めるパターンにマッチするタームは等価(''equivalent'')とされる。この等価は同じ型と読み替えてもよい。等価性はあらゆる計算の可否を決定する。計算とは関数適用または演算子適用を指し、それらが求める仮引数と実引数にするタームが等価であればその計算は成立する事になる。各パターンが持つ数々の特徴は、[[型理論]]に従って直積型、非交和型、帰納型、ユニット型、ユニオン型、オプション型、詳細型、交差型などに分類されている。
[[S式]]は、コンス(''cons'')と呼ばれる双子セルを持つ二項型構築子のみで形成されるデータストラクチャである。S式はコンスを実行時に連結して任意のパターンを構築する[[動的型付け]]の値である。セルにはプリミティブまたは入れ子コンスが入る。コンスの連結によるセル要素の並びは[[型理論]]の[[直積集合|直積型]](''product type'')と見なされる。直積型は[[タプル]]のパターンを表わすが、S式では3要素以上の並びはコンスの再帰連結になるので[[線形リスト|リスト]]と呼ばれる。コンスのセルにはあらゆるタームが入れられるので事実上の[[非交和|非交和型]](''sum type'')として扱う事もできる。
[[代数的データ型]]は、[[型理論]]の[[直積集合|直積型]]と[[非交和|非交和型]]を定義できる型構築子の組み合わせで任意のパターンを構築する[[静的型付け]]の値である。直積型は[[タプル]]または[[構造体|レコード]]のパターンを表わす。非交和型は[[列挙型]]または[[共用体|タグ共用体]]のパターンを表わす。前者は等値性(''equality'')で識別される一般的な非交和である。後者は等価性(''equivalent'')で識別される非交和であるが、ユニオン型(''union type'')と個別定義されてもいる。自分自身の型構築子のネスティングは型理論の帰納型(''inductive type'')とされる。非交和型と帰納型とユニット型の組み合わせは[[連結リスト]]や[[二分木]]のパターンを表わす。ユニット型(''unit type'')はnilないしvoidであり空集合のパターンを表わす。ユニット型とそうでない型の二択の非交和型はオプション型(''option type'')とされMaybe値のパターンを表わす。上述の連結リストの要素になるタームは全て等価(同じ型)であることが原則である。「ターム集合→[[ガード (プログラミング)|ガード]]→抽出タームリスト」のパターンは詳細型(''refinement type'')とされ[[リスト内包表記]]を表わす。パターンに[[アノテーション]]を加えて元々の等価性に上乗せした任意の用途性で代数的データ型を分類するのは交差型(''intersection type'')とされ[[型クラス]]または型アノテーションを表わす。これはアドホック多相に相当する。パターン内のプリミティブと型構築子は、型変数(''type variable'')に置き換えることで[[ジェネリックプログラミング|ジェネリック化]]でき、型引数(''type parameter'')の指定でスペシフィック化できる。これはパラメトリック多相に相当する。代数的データ型は定義と実装を分けて後者を隠蔽するという意味でしばしば抽象化される。これは識別名を重複させる仕組みで実現され、型シノニムまたは型エイリアスと呼ばれる。
=== 評価戦略 ===
関数型プログラミングの[[評価戦略]](''evaluation strategy'')は、ネーム存在を値存在にする評価タイミング、引数の渡し方のcall-by-What、関数のボトム型の発生タイミングの三つを定義している。これはまず正格評価(''strict evaluation'')と非正格評価(''non-strict evaluation'')の二つに大別される。正格評価のネーム存在は、関数適用と同時に評価されて値存在になり、または変数による束縛と同時に評価されて値存在になる。この評価タイミングに注目した方は[[先行評価]](''eager evaluation'')と呼ばれる。引数のどれか一つがボトム型の値存在になった関数は反駁(''refutable'')されてそのままボトム型になる。この意味も包括した呼称が正格評価である。正格評価=先行評価のcall-by-Whatは値渡しになる。関数型プログラミングの性格から参照渡しと共有渡し(ポインタ渡し)は用いられない。代数的データ型では、型構築子に渡された型引数は型構築用とパラメトリック多相用の双方ともに先行評価対象である。
=== 参照透過性 ===
[[参照透過性]](''referential transparency'')とは関数は同じ引数値に対して必ず同じ評価値を恒久的に導出し、その評価過程において現行計算枠外の情報資源に一切の作用を及ぼさないというプロセス上の枠組みを意味する。現行計算枠外のいずれかの情報資源が変化するのと同時にいずれかの関数の評価過程も変化してしまう現象
=== 型システム ===
関数型プログラミングの[[型システム]](''type system'')は、[[型付きラムダ計算|型付けラムダ計算]]ベースの[[型理論]]に基づいたスタイルで実装されている。型システムの分類に従った対比で述べると、[[命令型言語]]では明示的型付け(''manifest typing'')が多用されるのに対し、関数型では推論的型付け(''inferred typing'')が多用される。また関数型では、所属する部品に注目して全体を識別する構造的型付け(''structural typing'')よりも、記名から全体を識別しその文脈で所属する部品も識別する記名的型付け(''nominal typing'')の方がよく用いられる。これはアドホック多相に相当するものであり、実例は[[型クラス]]と型アノテーションである。型クラスは型理論における”文脈”を形式化したものでインターフェースのように用いられる。型アノテーションはそれ自体が構造体化される実装もあり、この場合は様々な情報が付加されてやや無節操に応用される。なお、構造的型付けは[[ダックタイピング]]の考え方と同義である。
関数型初期の[[LISP]]系の[[S式]]は、二項型構築子(コンス)の実行時の連結でパターンを形成する潜在的型付け(''latent typing'')であり、これは形式化されていない推論的型付けと言えるもので[[動的型付け]](''dynamic typing'')に分類されている。[[ML (プログラミング言語)|ML]]系を境にしてパターンを事前形成する[[静的型付け]](''static typing'')が主流になった。その実装の[[代数的データ型]]は多項な型構築子の組み合わせであり、パラメトリック多相で[[ジェネリックプログラミング|ジェネリック化]]された。''Hindley–Milner''型体系は、このパラメトリック多相に対応した[[型推論]]機能を提供して強い静的型付けの実装をサポートした。値をメモリ上のビット列ではなく、構造的な代数式と見なすのが関数型プログラミングの特徴である。前者はただのビット列を識別するためにコンパイラがその識別情報を他に持ち、それを参照する為に予め型名を明示(''manifest'')せねばならないが、後者は値自体が識別情報を兼ねているので常時その推論(''inferred'')で型名を識別できる。この時に用いられる[[型推論]]は、代数的データ型のパターンを等価性を審査できる形まで簡約するという型理論に沿った用法だけでなく、ソースコードの前後の文脈までシークして型を導き出せるという実用面にも特化された機能である。これによって関数型言語での型注釈と型宣言はもっぱら省略される。値を構造的な代数式と見なす仕組みは、メモリ上のビット列の幅拡張や恣意解釈を利用した[[型変換]]を全排除するので結果的に強い型付け(''strong typing'')に結び付く。しかし随所で多用されるユニオン型(等価性による非交和型)の値は弱い型付け(''weak typing'')相当である。関数型プログラミングでは強を基軸にしつつも弱のジョイントで解釈の選択が図られている。
[[量化]]可能なパターン(型)はプロパータイプ(''proper type'')と呼ばれる。量化されたパターンはターム(型付け値)である。プリミティブではないプロパータイプは1個以上のタイプ(''type'')から形成される。型構築子はプロパータイプとタイプの依存関係を決めて同時にそのプロパータイプの識別子になる。タイプはプリミティブまたは型構築子(入れ子)を指す。タイプAとタイプBからなるプロパータイプCは、AとBに依存(''dependent'')している事になりその関係は「A→B→C」と表現される。型構築子内の任意のタイプを型変数にして[[ジェネリックプログラミング|ジェネリック化]](=パラトメトリック多相)すると、プロパータイプ未満の存在になって量化不可になる。これを量化可能なプロパータイプ存在にするには、その型構築子への型引数の指定が別途必要になる。プロパータイプ存在とその未満存在を区別する仕組みが[[型理論]]の[[カインド (型理論)|カインド]]である。カインドではタイプを*と総称表現する。カインドでは、プロパータイプ存在は「*」と表現される。型引数1個必要のプロパータイプ未満存在は「*→*」になる。2個必要なら「*→*→*」になり、これに型引数が1つ適用されると「*→*」になる。カインドは量化の可否の他、型構築子が設定する依存関係の要素箇所に当てはめられるかどうかの判別になる。
タイプに依存してプロパータイプを導出する仕組みが型構築子と呼ばれるのに対し、タームに依存してプロパータイプを導出する仕組みの方は[[型理論]]の[[依存型]]と呼ばれる。依存型の導出は、依存値×写像の直積で表現される。写像は依存関数とも呼ばれる。依存関数から導出される「型」とは、量化前のプロパータイプか、未確定の変数部分=量化されてない部分を内包しているネーム存在である。この型としてのネーム存在は簡約されるなどして柔軟な等価性照合を可能にする。型としてのネーム存在は量化されるとタームとしての値存在になり、それをまた依存値にした別の型の導出も可能である。依存関数は、依存値によって量化部分は異なるが同じ等価性の型を導出する[[全称量化子|全称量]](''for all'')と、依存値によって異なる等価性の型を導出する[[存在量化子|存在量]](''there exists'')に分かれる。依存型は、型構築子をメインにするそれとは異なる型システムの下で実装される事になった。
[[多態性]]三種の三番目であるサブタイプ多相は、データの[[セマンティクス]]または[[メソッド (計算機科学)|振る舞い]]の多相を扱う性質から関数型とは相容れない部分が多い。関数型の[[代数的データ型]]と[[オブジェクト指向プログラミング|オブジェクト指向]]の[[抽象データ型]]は対象的なデータストラクチャと見なされている。前者がデータのみの表現体であるのに対して、後者はセマンティクスを主にしたデータの表現体である。しかしオブジェクト指向との連携が模索される中で数々の手法も提示されている。動的型付けメインのLISP系ではS式の代わりに、各スロットに任意の変数を[[動的束縛|動的バインディング]]できるレコードを用いる。その動的バインディング用レコードを1個以上引数にできる関数によって[[多重ディスパッチ]]が表現される。動的バインディング用レコードの型チェックは[[ダックタイピング]]で行われる。静的型付けメインのML系ではパラメトリック多相による[[ジェネリックプログラミング|ジェネリック]]抽象データ型が用いられる。その型引数=型変数には抽象データ型が代入される。関数型プログラミングのサブタイプ多相はジェネリッククラスの[[継承 (プログラミング)|継承関係]]ではなく、型変数の方の継承関係を用いるのが特徴である。型変数の方の継承関係で結ばれたジェネリックインスタンスの機構はヴァリアンス(''variance'')と呼ばれる。ヴァリアンスはジェネリッククラスを中間媒体にしてサブタイプ多相のための継承構造を扱う仕組みである。ヴァリアンスには[[共変性と反変性 (計算機科学)|共変性]](''covariance'')と[[共変性と反変性 (計算機科学)|反変性]](''contravariance'')がある。共変性は指定の型変数を抽象軸にしたその子孫の型変数たちによる横並びのサブタイピングである。反変性は指定の型変数からその祖先の型変数までの階層的な縦並びのサブタイピングである。この時にアドホック多相に該当する型境界(''type bound'')または型制約(''type constraint'')で型引数=型変数を修飾させて静的な型チェックをサポートさせる事が多い。
== 歴史 ==
72 ⟶ 55行目:
'''1950年代'''
初の関数型プログラミング言語とされる「[[LISP]]」は、1958年に[[マサチューセッツ工科大学]]の計算機科学者[[ジョン・マッカーシー]]によって開発された。LISPの関数はラムダ計算の形式を元に定義され再帰可能に拡張されており、式のリスト化とその遅延評価および高階評価など幾つかの関数型的特徴を備えていた。LISPは数多くの”方言”を生み出しているが、その中でも「[[Scheme]]」「[[Dylan]]」「[[Racket]]」「[[Clojure]]」「Julia」は
'''1960年代'''
1964年に計算機科学者[[ケネス・アイバーソン]]が開発した「[[APL]]」は、数多く定義された関数記号
'''1970年代'''
相互[[自動定理証明]]に向けて始められた「''Logic for computable functions''」プロジェクトの中で1973年に導入された「[[ML (プログラミング言語)|ML]]」は[[代数的データ型]]、[[多態性|パラメトリック多相]]、[[型推論]]などを備えた関数型言語であり、計算機科学者[[ロビン・ミルナー]]によって開発された。また1975年に[[MIT人工知能研究所]]の計算機科学者[[ガイ・スティール・ジュニア|ガイ・スティール]]と工学者[[ジェラルド・ジェイ・サスマン|ジェイ・サスマン]]が設計してAIリサーチ用に導入された「[[Scheme]]」は任意
'''1980年代'''
'''1990年代'''
1990年に
'''2000年代'''
2000年代になると関数型プログラミングへの注目度は更に高まり、マルチパラダイムに応用された関数型言語が様々に登場した。2003年のJava仮想マシン動作でオブジェクト指向と関数型を融合した「[[Scala]]」、2005年のマイクロソフト製のML派生言語「[[F Sharp|F#]]」、2007年のJava仮想マシン動作のLISP方言「[[Clojure]]」など数々のポピュラー言語が生み出されている。また
== 代表的な関数型言語 ==
'''[[LISP]]''' (1958年)
: 動的型付け、先行評価
'''[[ISWIM]]''' (1966年)← LISP、[[ALGOL]]
: 静的型付け、先行評価
[[ML (プログラミング言語)|'''ML''']] (1973年)← ISWIM
: 静的型付け、先行評価
'''[[Scheme]]''' (1975年)← LISP、ISWIM
: LISP方言、動的型付け、先行評価
[[FP (プログラミング言語)|'''FP''']] (1977年
: 関数水準言語、動的型付け、先行評価
'''[[Standard ML]]''' (1983年)← ML、Hope、[[Pascal|PASCAL]]
: ML派生、静的型付け、先行評価
'''
:
'''[[Miranda]]''' (1985年)← ML、Hope、SASL
: 純粋関数型、静的型付け、遅延評価
'''[[Erlang]]''' (1986年)← LISP、[[Prolog]]、[[Smalltalk]]
: 動的型付け、先行評価
'''[[Clean]]''' (1987年)← Miranda
: 純粋関数型、静的型付け、遅延評価
'''[[Haskell]]''' (1990年)← Scheme、Standard ML
: 純粋関数型、静的型付け、遅延評価
'''[[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、
: 静的型付け、先行評価、オブジェクト指向
[[F Sharp|'''F#''']] (2005年)←
: ML派生、静的型付け、先行評価
'''[[Clojure]]''' (2007年)← Scheme、Haskell
: 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
y := 1;
FOR i := 2 TO num DO
BEGIN
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>
<!--
194 ⟶ 190行目:
</syntaxhighlight>
-->
== 脚注 ==
|