プログラミング言語/関数型言語

関数型プログラミング言語

宣言型プログラミング(declarative programming)の考え方は、環境の動作に関するルールを定義し、あとは言語がすべて解決してくれるようにすることです。これは，機械に何をすべきかを正確に指示する手続き型言語とは対照的です。関数型プログラミングは、宣言型プログラミングを実現する方法の1つです。その典型的な例が階乗関数です。新しい関数を定義する最初のステップは、まず些細なケースを処理することです。次に、非自明なケースを、最終的に単純なケースに帰着するように定義します。nの階乗は、nにnより1小さい階乗を掛けたものと定義されます。

fac 0 = 1

fac n = (fac (n-1)) * n

このような単純な実装では、forループよりも多くのメモリーと処理時間を消費します(O(n)スタックスペースを使います)が、これは単純な変更で解決できます。コンパイラーやインタープリターが関数呼出しのコストを排除するために、累算器パラメーター(accumulator parameter)を使用するのです。

facb 0 acc = acc

facb n acc = facb (n-1) (n*acc)

fac n = facb n 1

関数型プログラミングには大きな用途があります。関数型言語をコードのプロトタイプとして使い、手続き型言語よりも関数型コードを書いて、それが望ましい結果を生成することを証明するのは多くの場合簡単です。そして、手続き型の技術を使って最適化します。関数型はバイナリツリーを非常に効率的にトラバースすることができます。

• TODO: 一般的な関数型言語がラムダ計算とどう違うか、重要な副作用について説明しなさい（ただし、Haskellについては言及すること）。
  • SchemeとMLは整数、浮動小数点数、リスト、文字列のような型が内蔵されている
  • Schemeはテールコール最適化を持っています。
  • Schemeはcurryの代わりに複数引数の関数を持つ
  • Schemeは全ての構成要素に関数表記を用い、括弧を必要とします。
  • Schemeはハイジェニックマクロです。
  • MLは推論を伴う静的型付け
  • MLのパターンマッチ構成
  • MLは単一引数の関数しか持たないが，curryingやタプルを使って複数引数をシミュレートできる
  • MLでは，関数の呼出しにラムダ計算を使いますが，組み込みの構成要素にはキーワードを使います（つまり，ifの関数表記を使いません）．

ラムダはアウトスコープで参照される変数への参照を保持し、なおかつこれらの関数を保存して呼出し関数が長く戻ったときに呼出すことができるため、ラムダを使用する言語にはガベージコレクションがあります。関数型プログラミング 「純粋関数」を書くことに焦点を当てた宣言型プログラミングのサブセットです。関数型プログラミングは、宣言型プログラミングの一種です。これに対して、C#、Visual Basic、C++、Javaなどのオブジェクト指向プログラミング（OOP）言語を含む主流の言語は、主に命令型（手続き型）プログラミングをサポートするように設計されています。コンピュータサイエンスでは、関数型プログラミングはプログラミングパラダイム（コンピュータプログラムの構造と要素の構築スタイル）の一つで、計算を数学関数の評価として扱い、状態の変化や変更可能なデータを回避しています。宣言型のプログラミングパラダイムであり、プログラミングは文の代わりに式や宣言で行われます。関数型コードでは、関数の出力値は関数に渡された引数にのみ依存するため、引数 x に同じ値を指定して関数fを2回呼出すと、毎回同じ結果 f(x) が得られます。これは、ローカルまたはグローバルな状態に依存する手続きが、同じ引数で異なるプログラム状態から呼出されると異なる結果を生成する場合があるのとは対照的です。副作用、すなわち関数の入力に依存しない状態の変化を排除することで、プログラムの挙動を理解し予測することが非常に容易になります。これが、関数型プログラミングの開発の主な動機の1つです。

コンビネーター論理は、モーゼス・シェンフィンケルとハスケル・カリーによって開発された、同等の理論的基盤です。もともとは、数学の基礎をより明確にするために開発されました。コンビネーター論理は一般にラムダより抽象的と認識されており、ラムダより先に発明されました。

• レキシカルスコープとダイナミックスコープ