「関数型プログラミング」の版間の差分
削除された内容 追加された内容
タグ: Refタグつき記述の除去 ビジュアルエディター |
|||
18行目:
*関数型プログラムの基本文は[[式 (プログラミング)|式]](''expression'')である。
*式は、値(''value'')と演算子(''operator'')と関数(''function'')で構成される。式内の代数部分が確定される前の式は抽象値と同義であり、確定後の式は実値と同義になる。ここでの代数とは式内の各束縛変数と、同じく式内の各関数の引数の双方を指す。実値の導出過程は評価(''evaluation'')と呼ばれる。
*式は値と同一視されるので、上述の式と値は相互再帰の関係にある。式内の値は他の式の評価値である事があり、その式内にもまた他の値があるといった具合である。これは[[
*式評価値の後続への反映は変数への代入ではなく、[[束縛変数]]で定数化するのが標準である。
*後続式の[[自由変数と束縛変数|自由変数]]を省略し、引数または先行式評価値を自動適用する構文がしばしば用いられる。これはポイントフリーまたは[[パイプライン処理|パイプライン]]と呼ばれる。
26行目:
*2個以上の引数を同時適用する非カリー化の関数も用いられる。無名関数がしばしばそれになる。この場合は部分適用やポイントフリーが制限される。
*関数は名前付きと名前無しの二通りある。後者はラムダ抽象を模した構文で式中に直接定義される。これは[[クロージャ]]または[[無名関数]]と呼ばれる。
*
*関数式の引数適用を任意の段階で保留して残り引数の適用を待つ第一級関数を生成できる。これは部分適用と呼ばれる。
*片方の評価値と片方の第1引数が同じ型の両関数を合わせて双方の写像をつなげた第一級関数を生成できる。これは関数合成と呼ばれる。
35行目:
*値は型(''type'')によって分類される。型は代数的データ型(''algebraic data type'')として実装される。ただしその実装スタイルはそれを意識させない位単純なものから複雑なものまで言語ごとに様々である。
*代数的データ型は言わば「型の式」である。代数的データ型は自身の構成要素になる「型」を値と同義の代数として扱う。その代数はパラメトリック多相で総称化できる。
*代数的データ型(=型の式)は、直積型(''product type'')非交和型(''sum type'')帰納型(''inductive type'')依存型(''dependent type'')ユニット型(''unit type'')などの
*直積+非交和+帰納+依存+ユニットの五構造で大半のデータストラクチャを表現できるが、その他にも指数型(''exponential type'')交差型(''intersection type'')など様々にあり、また依存型は用途によって詳細型(''refinement type'')選択型(''option type'')などに特化される事がある。
*直積型は、(A, B) のような[[タプル]]の構造を表わす。また標準的な[[構造体]]を表現する。
*非交和型は、(A | B) のような[[共用体|修飾共用体]]または[[列挙型]]の構造を表わす。
*帰納型は、[[ボックス化]]の構造を表わす。また帰納型は非交和型およびユニット型と併用されて、[[連結リスト]]、[[二分木]]、[[ツリー構造|多分木]]
*依存型は、もっぱら関数+環境値+対象値のセットで対象値は参照時に常時関数適用される。その写像は環境値によって変化する。依存型は他の型構造と併用されて動的配列、Maybe値などの構造を表わす。依存型の写像パターンはカインド(''kind'')と呼ばれる。
*ユニット型は、NIL、NULL、VOIDであり空集合の構造を表わす。
*指数型は、”関数の型”の構造を表わす。”関数適用の評価値”は指数型と直積型の併用で表現される。
*交差型は、トレイトや型クラスの構造を表わす。
*プリミティブ値はあくまで理論上ではあるが、数値は非交和型、論理値は非交和型、文字は非交和型、文字列は直積型と非交和型と依存型(可変長文字列
*代数的データ型は単体値を兼ねたあらゆる[[多重集合]]の表現になり、それに対する関数適用は[[全単射]]と同義になる。これが関数型プログラミングの代表的利点であるリスト処理に繋がっている。
*値が式評価の束縛と解釈されるケースではその型宣言はもっぱら省略される。型を自動的に導き出す機能は[[型推論]]と呼ばれる。型推論と[[多態性|パラメトリック多相]]はよく併用される。
70 ⟶ 72行目:
'''1970年代'''
相互[[自動定理証明]]に向けて始められた「''Logic for computable functions''」プロジェクトの中で1973年に導入された「[[ML (プログラミング言語)|ML]]」は、[[代数的データ型]]と[[多態性|パラメトリック多相]]などを備えたマルチパラダイム関数型言語であり、計算機科学者[[ロビン・ミルナー]]によって開発された。また1975年に[[MIT人工知能研究所]]の計算機科学者[[ガイ・スティール・ジュニア|ガイ・スティール]]と[[ジェラルド・ジェイ・サスマン|ジェイ・サスマン]]が設計してAIリサーチ用に導入された「[[Scheme]]」もMLに劣らぬ言語仕様を備えており、関数用レキシカルスコープが採用されて構造化が図られていた。
1977年、[[バッカス・ナウア記法]]と[[FORTRAN]]開発の功績でこの年の[[チューリング賞]]を受けた計算機科学者[[ジョン・バッカス]]は「''Can Programming Be Liberated From the von Neumann Style? -A Functional Style and Its Algebra of Programs-''」と題した記念講演の中で関数型プログラミングの重要性を訴えた。同時に自ら考案した関数型ならぬ関数水準(''function-level programming'')言語「[[FP (プログラミング言語)|FP]]」を紹介している。バッカスはFPのパラダイムをヒエラルキー手法と定義し、それはプログラム代数を用いるコンバイン・フォーム(LISPの''form'')で実装されると提唱した。[[ノイマン型]]からの脱却を題目に掲げているバッカスの理論は、後年のCPUに導入される並列[[パイプライン処理]]に通じる構想であった。しかしFPが示す[[自由変数と束縛変数|自由変数]]を極力排した関数水準プログラミングはさほど支持を得られなかった。
76 ⟶ 78行目:
'''1980年代'''
数学者[[ペール・マルティン=レーフ|マルティン=レーフ]]が1972年から提唱していた直感的型理論は、関数型プログラミングの世界に[[型理論]]の[[依存型]]の重要性を認識させて[[型システム]]の拡張に貢献した。1978年に
'''1990年代'''
1990年にこれも関数型プログラミングのマイルストーン的な純粋関数型言語「[[Haskell]]」が初リリースされた
'''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年)
: 非純粋、動的型付け
'''[[ISWIM]]''' (1966年)← LISP、[[ALGOL]]
: 非純粋、静的型付け
[[ML (プログラミング言語)|'''ML''']] (1973年)← ISWIM
: 非純粋、静的型付け
'''[[Scheme]]''' (1975年)← LISP、ISWIM
: 非純粋、動的型付け
[[FP (プログラミング言語)|'''FP''']] (1977年)
: 純粋、型なし
: 非純粋、静的型付け
'''[[Miranda]]''' (1985年)← ML、SASL、Hope
: 純粋、静的型付け
'''[[Erlang]]''' (1986年)← LISP、[[Prolog]]、[[Smalltalk]]
: 非純粋、動的型付け
'''[[Clean]]''' (1987年)← Miranda
: 純粋、静的型付け
'''[[Haskell]]''' (1990年)← ML、Scheme、Miranda、Clean、FP、Hope
: 純粋、静的型付け
▲[[Standard ML|'''Standard ML''']] (1990年)← ML、Hope、[[Pascal|PASCAL]]
'''[[Dylan]]''' (1993年)← Scheme、[[Common Lisp Object System|CLOS]]、[[ALGOL]]
: 非純粋、動的型付け
[[R言語|'''R''']] (1993年)← Scheme、[[Common Lisp Object System|CLOS]]
: 非純粋、動的型付け
'''[[Racket]]''' (1995年)← Scheme、[[Eiffel]]
: 非純粋、動的型付け
'''[[OCaml]]''' (1996年)← Caml、Standard ML、[[Modula-3]]
: 非純粋、静的型付け
'''[[Scala]]''' (2003年)← Scheme、Haskell、OCaml、Erlang、[[Smalltalk]]、[[Java]]
: 非純粋、静的型付け
[[F Sharp|'''F#''']] (2005年)← Haskell、OCaml、Erlang、Scala、[[Python]]、[[C♯]]
: 非純粋、静的型付け
'''[[Clojure]]''' (2007年)← Scheme、Haskell、OCaml、Erlang、[[Java]]▼
▲'''[[Clojure]]''' (2007年)← Scheme、Haskell、OCaml、Erlang、[[Java]]
: 非純粋、動的型付け
== 関数型プログラミングの例 ==
|