「関数型プログラミング」の版間の差分
削除された内容 追加された内容
4行目:
'''関数型言語'''({{lang-en-short|''functional language''}})は、'''関数型プログラミング'''のスタイルまたは[[プログラミングパラダイム|パラダイム]]を扱う[[プログラミング言語]]の総称である。関数型プログラミングは関数の[[写像|適用]]と[[関数の合成|合成]]から組み立てられる[[宣言型プログラミング]]の一種であり、関数は[[引数]]の適用から先行式の[[評価戦略|評価]]を後続式の適用に繋げて終端評価に到る[[式 (プログラミング)|式]]の[[ツリー構造|ツリー]]として定義される。関数は引数ないし返値として渡せる[[第一級関数]]として扱われる。
関数型プログラミングは[[数理論理学]]と[[圏論]]を主にした数学分野をルーツにし、関数[[形式体系]]の[[ラムダ計算]]と[[コンビネータ論理]]を幹にして構築され、[[LISP]]言語が実装面の先例になっている。関数の数学的な純粋性を追求した純粋関数型言語も存在する。純粋関数型パラダイムでは[[参照透過性]]が最重視され[[モナド (プログラミング)|モナド]]などの特別な[[型システム]]が導入されている。また{{誰範囲|date=2020年5月|{{要出典範囲|date=2020年5月|[[並行計算]]パラダイムでは純粋関数が重視されている}}}}。[[マルチパラダイムプログラミング言語|マルチパラダイム]]言語での導入例では、単に有用な構文スタイルとして扱われている事が多い。[[高階関数]]と[[第一級関数]]、[[クロージャ]]または[[無名関数]]、関数合成と部分適用、{{要出典範囲|ポイントフリーまたは[[パイプライン処理|パイプライン]]|date=2020年5月}}、[[イテレータ|イテレーション]]またはリスト処理、[[型推論]]、[[多態性|パラメータ多相]]とアドホック多相、[[パターンマッチング]]、[[再帰]]の最適化、[[束縛変数]]と[[イミュータブル]]
== 特徴 ==
<!-- 本節は一般的でない記述過多。この記事にはHaskellやLISPに偏重しない内容を記載すること <=このページは「関数型言語」ですのでそのマジョリティ(Scheme、ML、Miranda系)になるべく共通した項目を記述してるつもりです。また関数型に限った特徴のみを書き、他でも見られるものは意図的に省いてます。 -->
ここでは関数型プログラミング本来の構文スタイルを元にして説明する。式を基本文にする関数型に対して、[[文 (プログラミング)|ステートメント]]を基本文にする[[手続き型プログラミング|手続き型]]や[[オブジェクト指向プログラミング|オブジェクト指向]]などの[[命令型プログラミング]]言語では必要に応じて構文スタイルを変えて実装されている。代表的なのは「式の引数への適用」に対する「引数を関数に渡す」である。ただし双方ともアセンブリコード上では同様に符号化される。[[代数的データ型]]も[[構造体]]や[[連結リスト]]で置き換えられているのが通例である。
=== 式と関数 ===
{{出典の明記|date=2020年5月6日 (水) 02:29 (UTC)|section=1}}
*関数型プログラムの基本文は[[式 (プログラミング)|式]](''expression'')である。式は[[第一級オブジェクト]]と
*式は、値(''value'')と演算子(''operator'')と関数(''function'')で構成される。式内の代数部分が確定される前の式は抽象値と同義であり、確定後の式は実値と同義になる。ここでの代数とは式内の各束縛変数と、同じく式内の各関数の引数の双方を指す。実値の導出過程は評価(''evaluation'')と呼ばれる。
*式は値と同一視されるので、上述の式と値は相互再帰の関係にある。式内の値は他の式の評価値である事があり、その式内にもまた他の値があるといった具合である。
*式評価値の後続への反映は変数への代入ではなく、[[束縛変数]]で定数化するのが{{要出典範囲|本来の在り方である|date=2020年5月}}。
*
*関数も値と同一視される。関数は式に引数(''parameter'')
*関数は、式の引数への適用(''application'')と解釈される。{{要出典範囲|その対義概念として反適用(''
*関数は、式を第1引数に適用したもの→第2引数に適用したもの→第x引数に適用したもの→評価値、という形をとる。関数の型は各引数値から評価値までの型の連鎖として表現され、
*2個以上の引数を同時適用する非カリー化の関数も用いられる。無名関数がしばしばそれになる。この場合は部分適用やポイントフリーが制限される。
*関数は名前付きと名前無しの二通りある。後者はラムダ抽象を模した構文で式中に直接定義される。これは[[クロージャ]]または[[無名関数]]と呼ばれる。
*関数の引数値を関数にする事も可能であり、また関数の評価値を関数にする事も可能である。他の関数を引数値または評価値として扱える関数は[[高階関数]]と呼ばれる。他の関数から引数値または評価値として扱われる関数は[[第一級関数]]と呼ばれる。
*関数式の引数適用を任意の段階で保留して残り引数の適用を待つ第一級関数を生成できる。これは部分適用と呼ばれる。
*片方の評価値と片方の第1引数が同じ型の両関数を合わせて双方の写像をつなげた第一級関数を生成できる。これは関数合成と呼ばれる。
*言語によるが、演算子はデフォルトの式内容を持ち、引数が1~2個に限定された関数と同義である。演算子の式内容は任意に再定義できる。部分適用された演算子はセクションと呼ばれる第一級関数になる。
29 ⟶ 31行目:
*値(''value'')は代数的データ型(''algebraic data type'')として表現される。これは[[直積集合|直積]]、[[非交和]]、[[再帰]]の構造を持ち、単体値を兼ねたあらゆる値集合の汎用表現になる。代数的データによって単体値と値集合を同等に扱うスタイルが関数型プログラミングの代表的利点であるリスト処理([[イテレータ|イテレーション]])に繋がっている。
<!-- *代数的データ型は、''atom(プリミティブ)nil(無)cons(内包値+リンク)''の要素で実装される。''atom''は数値、論理値、文字、文字列を指す。''cons''の''内包値''は''atom''または次の''cons(=''入れ子の代数的データ)を指し、''cons''のリンクは次の''cons''または''nil''(=終端)を指す。代数的データは''cons''の再帰で構成されてゼロ個から複数以上の値を内包する事になる。この再帰ツリー構造は[[S式]]と呼ばれる。 --> <!-- LISP系に限定しすぎ。 -->
*代数的データ型は、''atom(プリミティブ)nil(無)cons(内包値+リンク)の要素で実装されるのが一般的である。atom''は数値、論理値、文字、文字列を指す。''cons''の''内包値''は''atom''または次の''cons(=''入れ子の代数的データ)を指し、''cons''のリンクは次の''cons''または''nil''(=終端)を指す。代数的データは''cons''の再帰で構成されてゼロ個から複数以上の値を内包する事になる。この再帰ツリー構造は[[S式]]と呼ばれる。
*値は型(''type'')によって分類される。
*全ての値が同じ型の代数的データは''list''と呼ばれ、異なる場合は''tuple''と呼ばれる。''list''は用法的に[[線形リスト]]と同義であり、''tupleは用法によっては''[[構造体]]の近似物になる。後者は前述の[[直積集合|直積]]である。
*型選択している代数的データは''variants''などと呼ばれ、[[共用体]]ないし[[列挙型]]の類似物になる。これは前述の[[非交和]]である。
*前述の再帰は代数的データの[[ネスティング|入れ子構造]]を表現できる。その入れ子はパラメータ多相で[[総称型]]にできる。
*
=== 再帰と評価戦略とパターンマッチング ===
47 ⟶ 50行目:
== 歴史 ==
初の関数型プログラミング言語とされる「[[LISP]]」は、1950年代に[[マサチューセッツ工科大学]]の[[ジョン・マッカーシー]]によって開発された。数々の後発言語の手本にされた[[マルチパラダイムプログラミング言語|マルチパラダイム]]言語であるLISPは同時に、[[ラムダ計算]]を
現代的な関数型プログラミング言語の祖としてはアイディアが1966年に発表された
1977年、
バッカスの
21世紀に入ると、[[Java
== 代表的な関数型言語 ==
|