コンテンツにスキップ

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

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

出典: フリー百科事典『ウィキペディア(Wikipedia)』
削除された内容 追加された内容
Slappi (会話 | 投稿記録)
(同じ利用者による、間の3版が非表示)
2行目: 2行目:
{{プログラミング言語|index=かんすうかたけんこ}}
{{プログラミング言語|index=かんすうかたけんこ}}
[[ファイル:Orange_lambda.svg|代替文=|境界|右|フレームなし|167x167ピクセル]]
[[ファイル:Orange_lambda.svg|代替文=|境界|右|フレームなし|167x167ピクセル]]
'''関数型言語'''({{lang-en-short|''functional language''}})は、関数型プログラミングの[[プログラミングパラダイム|パラダイム]]を扱う[[プログラミング言語]]の総称である。'''純粋関数型'''(''purely functional'')'''非純粋関数型'''(''impure functional'')二つに大別され、後者の方が幅広く用いられてい[[マルチパラダイムプログラミング言語|マルチパラダイム言語]]に組み込まれているもは例外なく非純粋である。関数プログラミング文(''syntax'')設計(''design'')の二つの視点から解釈される。構文スタイルと設計原則の双方に忠実なのが純粋関数型である。構文面を中心に導入し設計面にそれほど忠実でないか又はほんど度外視してのが非純粋関数型である。
'''関数型言語'''({{lang-en-short|''functional language''}})は、'''関数型プログラミング'''スタイルまたは[[プログラミングパラダイム|パラダイム]]を扱う[[プログラミング言語]]の総称である。関数型プログラミングは関数の[[写像|適用]][[関数の合成|合成]]から組み立てられる[[宣言型プログラミング]]の一種であり、関数は[[引数]]の適用から先行式の[[評価戦略|評価]]を後続式の適用に順次ないし再帰的に繋げて終端評価に到る[[式 (プログラミング)|式]]の[[木造 (データ構造)|ツリー構造]]して定義される。関数は引数ないし返値として渡せ[[第一級関数]]として扱われる。


関数型プログラミングは[[数理論理学]]と[[圏論]]を主にした数学分野をルーツにし、関数[[形式体系]]の[[ラムダ計算]]と[[コンビネータ論理]]を幹にして構築され、[[LISP]]言語が実装面の先例になっている。関数の数学的な純粋性を追求した純粋関数型言語も存在する。純粋関数型パラダイムでは[[参照透過性]]が最重視され[[モナド (プログラミング)|モナド]]などの特別な[[型システム]]が導入されている。また[[並行計算]]パラダイムでは純粋関数が重視されている。関数型プログラミングと標榜される言語の多くは組込みスタイルとしてそれを扱っている。[[高階関数]]と[[第一級関数]]、[[クロージャ]]または[[無名関数]]、関数合成と部分適用、ポイントフリーまたは[[パイプライン処理|パイプライン]]、[[イテレータ|イテレーション]]またはリスト処理、[[型推論]]、[[多態性|パラメータ多相]]、[[パターンマッチング]]、[[再帰]]の最適化、[[演算子オーバーロード]]、[[イミュータブル]]定義などが関数型のスタイル要素として挙げられる。
== 特徴 - 構文面 ==

[[ラムダ計算]]と[[コンビネータ論理]]と[[LISP]]言語が土台になっている。
== 特徴 ==
ここでは関数型プログラミング本来の構文スタイルを元にして説明する。式を基本文にする関数型に対して、[[文 (プログラミング)|ステートメント]]を基本文にする[[手続き型プログラミング|手続き型]]や[[オブジェクト指向プログラミング|オブジェクト指向]]などの[[命令型プログラミング]]言語では必要に応じて構文スタイルが改変されている。代表的なのは「式の引数への適用」に対する「引数を関数に渡す」である。ただし双方ともアセンブリコード上では同様に符号化される。[[代数的データ型]]は[[構造体]]や[[連結リスト]]で置き換えられ、単体値ないし[[プリミティブ型|プリミティブ値]]では用いられないのが大半である。


=== 式と関数 ===
=== 式と関数 ===


*関数型プログラムの[[文 (プログラミング)|基本文]]は[[式 (プログラミング)|式]](''expression'')である。式は値と同一視される。
*関数型プログラムの基本文は[[式 (プログラミング)|式]](''expression'')である。式は値と同一視される。
*式は、値(''value'')と演算子(''operator'')と関数(''function'')で構成される。式内の代数部分が確定される前の式は抽象値と同義であり、確定後の式は実値と同義になる。ここでの代数とは式内の各束縛変数と、同じく式内の各関数の引数の双方を指す。実値の導出過程は評価(''evaluation'')と呼ばれる。
*式は、値(''value'')と演算子(''operator'')と関数(''function'')で構成される。式内の代数部分が確定される前の式は抽象値と同義であり、確定後の式は実値と同義になる。ここでの代数とは式内の各束縛変数と、同じく式内の各関数の引数の双方を指す。実値の導出過程は評価(''evaluation'')と呼ばれる。
*式を評価した値の後続式への反映は変数への代入ではなく、[[束縛変数]]で定数化するのが本来の在り方である。
*式を評価した値の後続式への反映は変数への代入ではなく、[[束縛変数]]で定数化するのが本来の在り方である。
*{{要出典範囲|{{仮リンク|暗黙プログラミング|en|tacit programming|label=}}が指向されており、直前の式の評価値はそのまま直式の適用値する事もできる。これは[[パイプライン処理|パイプライン]]またはポイントフリーと呼ばれる|date=2020年5月}}
*引数値または先行式の評価値をデフォルトで式の適用値と見なして値の記述を省略する構文が多用される。これは[[パイプライン処理|パイプライン]]またはポイントフリーと呼ばれる。
*関数も値と同一視される。関数は引数(''parameter'')と式を結び付けるユニットである。式の代数部分に引数値が順次束縛される。も値なで関数のフロー終端式がそのまま評価値になる。
*関数も値と同一視される。関数は引数(''parameter'')と式を結び付けるユニットである。式の代数部分に引数値が順次束縛されツリーの終端式が評価値になる。
*関数は、式の引数への適用(''application'')と解釈される。{{要出典範囲|その対義概念として反適用(''unapplication'')の仕組みも存在する。これは式の引数への適用を差し戻して元の引数を抽出する|date=2020年5月}}。
*関数は、式の引数への適用(''application'')と解釈される。{{要出典範囲|その対義概念として反適用(''unapplication'')の仕組みも存在する。これは式の引数への適用を差し戻して元の引数を抽出する|date=2020年5月}}。
*関数は、式を第1引数に適用したもの→第2引数に適用したもの→第x引数に適用したもの→評価値、というようなをと[[カリー化]]。LISPなど、例外もあ。関数の型は各引数値から評価値までの型の連鎖として表現される。
*関数は、式を第1引数に適用したもの→第2引数に適用したもの→第x引数に適用したもの→評価値、という形になのが標準で、これは[[カリー化]]と呼ばれる。関数の型は各引数値から評価値までの型の連鎖として表現され、これはカインド(''kind'')とも呼ばれる。
*2個以上の引数を同時適用する非カリー化の関数も用いられる。無名関数がしばしばそれになる。この場合は部分適用やポイントフリーが制限される。
*型の連鎖は、さながらパズルのような関数の断片化と連結を可能にする。前者は部分適用と呼ばれ、例えば式を第1引数に適用しただけのものを後続の式で使い回せる。後者は関数合成と呼ばれ、評価値と第1引数が同じ型の関数をつなげたものを後続の式で使い回せる。
*型の連鎖は、さながらパズルのような関数の断片化と連結を可能にする。前者は部分適用と呼ばれ、例えば式を第1引数に適用しただけのものを後続の式で使い回せる。後者は関数合成と呼ばれ、評価値と第1引数が同じ型の関数をつなげたものを後続の式で使い回せる。
*関数は名前付きと名前無しの二通りある。後者はラムダ抽象を模した構文で式中に直接定義される。これは[[クロージャ]]または[[無名関数]]と呼ばれる。
*関数は名前付きと名前無しの二通りある。後者はラムダ抽象を模した構文で式中に直接定義される。これは[[クロージャ]]または[[無名関数]]と呼ばれる。
*関数は値と同義なので、関数の引数値を関数にする事も可能であり、また関数の評価値を関数にする事も可能である。他の関数を引数値または評価値として扱える関数は[[高階関数]]と呼ばれる。他の関数から引数値または評価値として扱われる関数は[[第一級関数]]と呼ばれる。
*関数は値と同義なので、関数の引数値を関数にする事も可能であり、また関数の評価値を関数にする事も可能である。他の関数を引数値または評価値として扱える関数は[[高階関数]]と呼ばれる。他の関数から引数値または評価値として扱われる関数は[[第一級関数]]と呼ばれる。
*演算子は、デフォルトの式内容を持ち引数が1~2個に限定された関数と同義である。演算子の式内容は任意に再定義できる(例外もある。)。部分適用された演算子はセクションと呼ばれる第一級関数になる。
*演算子は、デフォルトの式内容を持ち引数が1~2個に限定された関数と同義である。演算子の式内容は一部の例外を除いて任意に再定義できる。部分適用された演算子はセクションと呼ばれる第一級関数になる。


=== 型と値 ===
=== 代数的データ型 ===
{{Cn|date=2020年5月}}
*値(''value'')は型(''type'')によって分類される。
*値は代数的データ(''algebraic data'')として表現される。代数的データは、''atom(プリミティブ)nil(無)cons(値+リンク)''の要素からなる。代数的データは''cons''の再帰で構成されており、ゼロ個から複以上の値を内包る事になる。''cons''の値は''atom''または入れ子の代数的データを指し、''cons''のリンクは次の''cons''または''nil''を指す。''atom''数値、論理値、文字、文字列す。この再帰ツリー構造は[[S式]]と呼ばれる。
*代数的データは単体値の表現でもあり、あらゆる値集合の原始的表現でもある。代数的データによって単値と値集合を同等に扱うスタイルが関数型プログラミングの代表的利点であるリスト処理([[イテレーション]])に繋がっている。
*代数的データは''cons''の再帰構造であり、先頭''cons''の値+リンクを常時分離表現できる。そのリンクは後続全''consを''表現する。そのリンクが指す''cons''を再帰関数の引数にして値+リンクを再度分離しそのまた再帰を繰り返していくと、結果的に代数的データの全内包値に作用を及ぼせる事になる。
*全ての値が同じ型の代数的データは''list''と呼ばれ、異なる場合は''tuple''と呼ばれる。''list''は用法的に[[線形リスト]]と同義であり、''tupleは用法によっては''[[構造体]]の近似物になる。


*値(''value'')は代数的データ型(''algebraic data type'')として表現される。これ[[直積]]、[[非交和]]、[[再帰]]の構造を持ち、単体値を兼ねたあらゆる値集合の汎用表現になる。代数的データによって単値と値集合を同等に扱うスタイルが関数型プログラミングの代表的利点であるリスト処理([[イテレータ|イテレーション]])に繋がっている。
=== 再帰と分岐 ===
*代数的データは、''atom(プリミティブ)nil(無)cons(内包値+リンク)''の要素で実装される。''atom''数値、論理値、文字、文字列す。''cons''の''内包''は''atom''または次の''cons(=''入れ子の代数的データを指し、''cons''のリンクは次の''cons''または''nil''(=終端)を指す。代数的データは''cons''の再帰で構成されてゼロ個から複以上の値を内包る事になる。この再帰ツリー構造は[[S式]]と呼ばれる。
*値は型(''type'')によって分類される。
*全ての値が同じ型の代数的データは''list''と呼ばれ、異なる場合は''tuple''と呼ばれる。''list''は用法的に[[線形リスト]]と同義であり、''tupleは用法によっては''[[構造体]]の近似物になる。この双方は前述の[[直積]]である。
*型選択している代数的データは''variants''などと呼ばれ、[[共用体]]ないし[[列挙型]]の類似物になる。これは前述の[[非交和]]である。
*前述の再帰は代数的データの[[ネスティング|入れ子構造]]を表現し、その入れ子はパラメータ多相で[[総称型]]にできる。
*値の型宣言と型指定は積極的に省略される。省略された型を自動的に導き出す機能は[[型推論]]と呼ばれる。型推論と[[多態性|パラメータ多相]]はよく併用される。

=== 再帰と非正格評価とパターンマッチング ===


*[[再帰]]が重視されている。関数の再帰呼び出しと[[相互再帰]]が多用される。データ定義でも、データ名に対する定義式の中で自身データ名が記述される再帰定義が多用される。
*[[再帰]]が重視されている。関数の再帰呼び出しと[[相互再帰]]が多用される。データ定義でも、データ名に対する定義式の中で自身データ名が記述される再帰定義が多用される。
*カウンタ変数を増減するループ文は用いられないのが本来の在り方である。同様の反復フローはカウンタ値を引数にした関数の再帰で行う。
*カウンタ変数を増減するループ文は用いられないのが本来の在り方である。同様の反復フローはカウンタ値を引数にした関数の再帰で行う。
*引数値による多分岐節([[パターンマッチング]])が多用される。関数型プログラミングにおける選択フローは、引数の多分岐から始まる関数に集約される。
*引数値による多分岐節([[パターンマッチング]])が多用される。関数型プログラミングにおける選択フローは、引数の多分岐から始まる関数に集約される。

== 特徴 - 設計面 ==
[[数理論理学]]と[[数学基礎論]]と[[圏論]]が土台になっている。ただし専門性の強いプログラムを除くと、それらの参考は大まかなものである。

=== パラダイム ===
関数型プログラミングは[[宣言型プログラミング]]のカテゴリに属している。宣言型と対照的関係にあるのが[[命令型プログラミング]]であり、そのカテゴリには[[手続き型プログラミング|手続き型]]や[[オブジェクト指向プログラミング|オブジェクト指向]]が属している。この両者を分ける一つの基準は[[副作用 (プログラム)|副作用]](''side-effect'')に対する扱い方である。副作用とは、現行プロセスの閉包領域の外にある様々な情報資源の状態である「環境」の変化と、その変化によって各プロセスの処理過程もまた影響を受ける事を指す。ここでの情報資源とは、プログラムの各種入出力を担う[[オペレーティングシステム|OS]]の現行状態と、プログラムを走行させている[[仮想マシン|ランタイム環境]]が提供する各種データリソースを意味する。命令型プログラミングは前述の「環境」に対して自由に作用を及ぼせるパラダイムであり、それが”''imperative''”の由来にもなっている。それに対して宣言型プログラミングは作用を及ぼせる対象と、自身がその影響を受ける事になる対象が、あらかじめ初期値または入力値として”''declarative''”された情報資源のみに限られている。加えて関数型プログラミングは原則的に、宣言されたデータに対しても作用を及ぼさず、他の値を導き出す為の因子として扱う。


=== 参照透過性 ===
=== 参照透過性 ===
関数型プログラミングの世界は[[参照透過性]]の原則下る。参照透過性の意味自体は非常にシンプルであり、関数は同じ引数値に対して必ず同じ評価値を恒久的に導出し、その評価過程においてプログラムの認知内における一切の情報資源に作用を及ぼさない、というものである。プログラムが認知する範囲内のいずれかの情報資源が変化するのと同時にいずれかの関数の評価過程も変化してしまう現象が[[副作用 (プログラム)|副作用]]と呼ばれる。
純粋関数型言語[[参照透過性]]の遵守をプログラムの枠組みしている。参照透過性の意味自体はシンプルであり、関数は同じ引数値に対して必ず同じ評価値を恒久的に導出し、その評価過程においてプログラムの認知内における一切の情報資源に作用を及ぼさない、というものである。プログラムが認知する範囲内のいずれかの情報資源が変化するのと同時にいずれかの関数の評価過程も変化してしまう現象が[[副作用 (プログラム)|副作用]]と呼ばれる。


=== 型システム ===
=== 型システム ===


=== 純粋関数とイミュータブルと並行計算 ===
=== 再帰と評価戦略 ===

=== 純粋関数と並行計算 ===


== 歴史 ==
== 歴史 ==

2020年5月5日 (火) 16:54時点における版

関数型言語: functional language)は、関数型プログラミングのスタイルまたはパラダイムを扱うプログラミング言語の総称である。関数型プログラミングは関数の適用合成から組み立てられる宣言型プログラミングの一種であり、関数は引数の適用から先行式の評価を後続式の適用に順次ないし再帰的に繋げて終端評価に到るツリー構造として定義される。関数は引数ないし返値として渡せる第一級関数として扱われる。

関数型プログラミングは数理論理学圏論を主にした数学分野をルーツにし、関数形式体系ラムダ計算コンビネータ論理を幹にして構築され、LISP言語が実装面の先例になっている。関数の数学的な純粋性を追求した純粋関数型言語も存在する。純粋関数型パラダイムでは参照透過性が最重視されモナドなどの特別な型システムが導入されている。また並行計算パラダイムでは純粋関数が重視されている。関数型プログラミングと標榜される言語の多くは組込みスタイルとしてそれを扱っている。高階関数第一級関数クロージャまたは無名関数、関数合成と部分適用、ポイントフリーまたはパイプラインイテレーションまたはリスト処理、型推論パラメータ多相パターンマッチング再帰の最適化、演算子オーバーロードイミュータブル定義などが関数型のスタイル要素として挙げられる。

特徴

ここでは関数型プログラミング本来の構文スタイルを元にして説明する。式を基本文にする関数型に対して、ステートメントを基本文にする手続き型オブジェクト指向などの命令型プログラミング言語では必要に応じて構文スタイルが改変されている。代表的なのは「式の引数への適用」に対する「引数を関数に渡す」である。ただし双方ともアセンブリコード上では同様に符号化される。代数的データ型構造体連結リストで置き換えられ、単体値ないしプリミティブ値では用いられないのが大半である。

式と関数

  • 関数型プログラムの基本文はexpression)である。式は値と同一視される。
  • 式は、値(value)と演算子(operator)と関数(function)で構成される。式内の代数部分が確定される前の式は抽象値と同義であり、確定後の式は実値と同義になる。ここでの代数とは式内の各束縛変数と、同じく式内の各関数の引数の双方を指す。実値の導出過程は評価(evaluation)と呼ばれる。
  • 式を評価した値の後続式への反映は変数への代入ではなく、束縛変数で定数化するのが本来の在り方である。
  • 引数値または先行式の評価値をデフォルトで後続式の適用値と見なして値の記述を省略する構文が多用される。これはパイプラインまたはポイントフリーと呼ばれる。
  • 関数も値と同一視される。関数は引数(parameter)と式を結び付けるユニットである。式の代数部分に引数値が順次束縛され、式ツリーの終端式が評価値になる。
  • 関数は、式の引数への適用(application)と解釈される。その対義概念として反適用(unapplication)の仕組みも存在する。これは式の引数への適用を差し戻して元の引数を抽出する[要出典]
  • 関数は、式を第1引数に適用したもの→第2引数に適用したもの→第x引数に適用したもの→評価値、という形になるのが標準で、これはカリー化と呼ばれる。関数の型は各引数値から評価値までの型の連鎖として表現され、これはカインド(kind)とも呼ばれる。
  • 2個以上の引数を同時適用する非カリー化の関数も用いられる。無名関数がしばしばそれになる。この場合は部分適用やポイントフリーが制限される。
  • 型の連鎖は、さながらパズルのような関数の断片化と連結を可能にする。前者は部分適用と呼ばれ、例えば式を第1引数に適用しただけのものを後続の式で使い回せる。後者は関数合成と呼ばれ、評価値と第1引数が同じ型の関数をつなげたものを後続の式で使い回せる。
  • 関数は名前付きと名前無しの二通りある。後者はラムダ抽象を模した構文で式中に直接定義される。これはクロージャまたは無名関数と呼ばれる。
  • 関数は値と同義なので、関数の引数値を関数にする事も可能であり、また関数の評価値を関数にする事も可能である。他の関数を引数値または評価値として扱える関数は高階関数と呼ばれる。他の関数から引数値または評価値として扱われる関数は第一級関数と呼ばれる。
  • 演算子は、デフォルトの式内容を持ち引数が1~2個に限定された関数と同義である。演算子の式内容は一部の例外を除いて任意に再定義できる。部分適用された演算子はセクションと呼ばれる第一級関数になる。

代数的データ型

  • 値(value)は代数的データ型(algebraic data type)として表現される。これは直積非交和再帰の構造を持ち、単体値を兼ねたあらゆる値集合の汎用表現になる。代数的データによって単体値と値集合を同等に扱うスタイルが関数型プログラミングの代表的利点であるリスト処理(イテレーション)に繋がっている。
  • 代数的データ型は、atom(プリミティブ)nil(無)cons(内包値+リンク)の要素で実装される。atomは数値、論理値、文字、文字列を指す。cons内包値atomまたは次のcons(=入れ子の代数的データ)を指し、consのリンクは次のconsまたはnil(=終端)を指す。代数的データはconsの再帰で構成されてゼロ個から複数以上の値を内包する事になる。この再帰ツリー構造はS式と呼ばれる。
  • 値は型(type)によって分類される。
  • 全ての値が同じ型の代数的データはlistと呼ばれ、異なる場合はtupleと呼ばれる。listは用法的に線形リストと同義であり、tupleは用法によっては構造体の近似物になる。この双方は前述の直積である。
  • 型選択している代数的データはvariantsなどと呼ばれ、共用体ないし列挙型の類似物になる。これは前述の非交和である。
  • 前述の再帰は代数的データの入れ子構造を表現し、その入れ子はパラメータ多相で総称型にできる。
  • 値の型宣言と型指定は積極的に省略される。省略された型を自動的に導き出す機能は型推論と呼ばれる。型推論とパラメータ多相はよく併用される。

再帰と非正格評価とパターンマッチング

  • 再帰が重視されている。関数の再帰呼び出しと相互再帰が多用される。データ定義でも、データ名に対する定義式の中で自身データ名が記述される再帰定義が多用される。
  • カウンタ変数を増減するループ文は用いられないのが本来の在り方である。同様の反復フローはカウンタ値を引数にした関数の再帰で行う。
  • 引数値による多分岐節(パターンマッチング)が多用される。関数型プログラミングにおける選択フローは、引数の多分岐から始まる関数に集約される。

参照透過性

純粋関数型言語は、参照透過性の遵守をプログラムの枠組みにしている。参照透過性の意味自体はシンプルであり、関数は同じ引数値に対して必ず同じ評価値を恒久的に導出し、その評価過程においてプログラムの認知内における一切の情報資源に作用を及ぼさない、というものである。プログラムが認知する範囲内のいずれかの情報資源が変化するのと同時にいずれかの関数の評価過程も変化してしまう現象が副作用と呼ばれる。

型システム

純粋関数とイミュータブルと並行計算

歴史

LISPは、その基本機能のモデルとして関数型の純LISPを持つなどといった特徴がある、最初の関数型言語である。今日広く使われているLISP方言のうち特にSchemeは関数型としての特徴が強い。

現代的な関数型プログラミング言語の祖としてはアイディアが1966年に発表されたISWIMが挙げられるが、1970年前後までは関数型プログラミング言語の歴史はLISPの発展が主である。1970年代にプロジェクトが開始されたロジック・フォー・コンピュータブル・ファンクションズ英語版のための言語としてMLが作られている。

またLISPにおいて、変数のスコープに静的スコープを採用したSchemeが誕生したのが1975年である。

1977年、FORTRANの設計とバッカス・ナウア記法の発明の業績でこの年のチューリング賞を受賞したジョン・バッカスは、Can Programming Be Liberated From the von Neumann Style?: A Functional Style and Its Algebra of Programs[1]と題した受賞記念講演で関数型プログラミングの重要性を訴えた。講演ではFPという関数型プログラミング言語の紹介もした(サブタイトルの後半の「プログラムの代数」はこれを指す)が、これはAPL(特に、高階関数の意味がある記号(APLの用語ではオペレーター(作用素)という))の影響を受けている。

バッカスのFPは広く使用されることはなかったが、この後関数型プログラミング言語の研究・開発は広まることとなった。1985年にMirandaが登場した。1987年に、遅延評価の純粋関数型プログラミング言語の標準の必要性が認識されHaskellの策定が始まった。1990年にHaskell 1.0仕様がリリースされた。同じく1990年にはMLの標準であるStandard MLもリリースされている。

Cleanは1987年に登場したが、発展の過程でHaskellの影響を受けている。1996年に、ML処理系のひとつであったCamlオブジェクト指向を追加したOCamlが登場した。また日本ではSMLに独自の拡張を施したSML#が開発されている。

21世紀に入ると、Java仮想マシン共通言語基盤CLI)をランタイムとする関数型プログラミング言語を実装しようという動きが現れ、ScalaClojureF#などが登場した。

代表的な関数型言語

言語 純粋さ 型付け
Clean 純粋 強い、静的
Clojure 非純粋 動的
Erlang 非純粋 動的
F# 非純粋 強い、静的
Haskell 純粋 強い、静的
Idris 純粋 強い、静的
Lazy K 純粋 型なし
LISP 非純粋 動的
Miranda 純粋 強い、静的
ML 非純粋 強い、静的
SML# 非純粋 強い、静的
Standard ML 非純粋 強い、静的
OCaml 非純粋 強い、静的
Scala 非純粋 強い、静的
Scheme 非純粋 動的
Unlambda 非純粋 型なし

純粋関数型言語では、参照透過性が常に保たれるという意味において、全てのや関数の評価時に副作用を生まない。純粋関数型言語であるHaskellCleanは非正格な評価を基本としており、引数はデフォルトで遅延評価される。一方、Idrisは純粋だが正格評価を採用している。入出力などを参照透過性を保ったまま実現するために、たとえば Haskell ではモナドClean では一意型英語版という特殊な型を通して一貫性のある表現を提供する。

非純粋関数型言語では、参照透過性を壊す、副作用があるような式や関数も存在する。LISPなどでデータ構造の破壊的変更などの副作用を多用したプログラミングを行うと、それはもはや手続き型プログラミングである。多くの場合、非純粋関数型言語の評価戦略は正格評価(先行評価)であるが、遅延評価する部分を明示することで、無限リストなどを扱えるものもある。

従来の手続き型と分類されるプログラミング言語においても、関数型プログラミングを行ないやすくなる機能を備えているものもある。C言語およびC++関数へのポインタをサポートし、関数をオブジェクトのように扱うことができるが、関数ポインタによって第一級関数をサポートしているとみなされてはいない。なお、C# 3.0、C++11、Java 8など、後発の規格においてラムダ式(無名関数)をサポートするようになった言語もある。

JavaScriptJavaなど近年[いつ?]高水準言語には、関数型言語の機能や特徴を取り入れているものがあるが、変数の値やオブジェクトの状態を書き換えるプログラミングスタイルを通常とするため、関数型言語とは分類されない。一方LISPは、その多くが副作用のある式や関数が多数あり、手続き型スタイルでのプログラミングがされることも多いが、理論的なモデル(「LISP」)の存在や副作用を使わないプログラミングが基本であること、ないし主には歴史的理由から、関数型言語だとされることが多い。なお、Pascalでは「手続き」と呼ばれるような値を返さないサブルーチンを、C言語では「関数」と呼んでいるが、これは単にルーチンについて、細分類して別の呼称を付けているか、細分類せず総称しているか、という分類と呼称の違いに過ぎず、「Pascalは手続き型言語で、C言語は関数型言語」[2]という一部の書籍に見られる記述は明確に誤りである。また、OCamlHaskellなどでは、「自明な値(例えば())を返す」と、値を返さない(Voidなど)は違うものであり、後者は停止しないか例外を出す(そのため結果がない)ようなプログラムを表す。

なお、「関数型言語である」と「関数型プログラミングをする」は同値ではなく、関数型には分類されない言語で関数型プログラミングをすること[注釈 1]や、関数型プログラミングを基本とする言語の上で他のパラダイムを実現する例もある[3]データフロープログラミング言語も関数型言語と共通した特徴を部分的に持つ。

その他の関数的性質を持つ言語

関数型プログラミングの例

関数型プログラミングは「計算とは何か」という数学の理論を基礎にしており、関数型プログラミングがもつ計算モデル関数モデルである[4]。たとえば、1 から 10 までの整数を足し合わせるプログラムを考える[注釈 2]命令型プログラミングでは以下のようにループ文を使って変数に数値を足していく(計算機の状態を書き換える)命令を繰り返し実行するという形を取る。

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)

ただし再帰呼び出しはスタックオーバーフローの危険性やオーバーヘッドを伴うため、注意深く使用しなければならない[5]。通例、関数型言語では、末尾再帰呼び出し (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のようにループ構文をサポートせず、従来の手続き型プログラミングが難しいケースもある。

逆に手続き型言語を使って関数型プログラミングを行なうことも可能であるが、末尾再帰呼び出しの最適化がサポートされるかどうかはコンパイラ次第である。

脚注

注釈

  1. ^ 関数型プログラミングのエッセンスとして、MISRA CのようにC言語でも副作用を極力用いないプログラミングを推奨しているコーディング標準もある。
  2. ^ 本来は等差数列の和の公式を用いて定数時間で問題を解く方法が最適解だが、ここではプログラミングスタイルの比較のため数値計算的手法を用いる。

出典

  1. ^ 「プログラミングはフォン・ノイマン・スタイルから解放されうるか?: 関数型プログラミング・スタイルとそのプログラム代数」、米澤明憲訳『ACMチューリング賞講演集』(共立出版)pp. 83-156
  2. ^ 共立出版ANSI C/C++辞典』ISBN 4-320-02797-3 など
  3. ^ Oleg Kiselyov, Ralf Lämmel. “Haskell's overlooked object system”. Sep 10, 2005閲覧。
  4. ^ 計算モデル2 関数モデル. (中略) 関数モデルに基づくプログラミング言語. 関数型言語. Lisp 犬塚信博 (2007)「プログラミング言語論 第1回 イントロダクション」名古屋工業大学
  5. ^ 関数 (F#) | MSDN

外部リンク