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

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

関数型プログラミング言語は、宣言型プログラミング(declarative programming)の一形態であり、プログラムの挙動を記述する際に環境の動作に関するルールを定義し、その後は言語が処理を行うようにします。 これは手続き型言語とは異なり、機械に具体的な手順を指示するのではなく、問題の本質的な解決法を記述することに焦点を当てています。

関数型プログラミングの特徴として、数学的な関数を評価するという考え方があります。このスタイルでは、副作用を避け、純粋関数を重視します。階乗関数の例を挙げると、以下のようになります。

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

このような再帰的な定義は、数学的帰納法に基づいています。しかし、単純な再帰ではスタックを消費し(O(n)スタックスペースを使います)、効率が悪い場合があります。この問題を解決するために、累積器パラメーター(accumulator parameter)を使用することができます。

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

このようにすることで、再帰の最適化が可能になります。関数型プログラミングは、プロトタイピングや数学的証明がしやすく、また関数の合成や抽象化が得意なため、非常に強力なプログラミングパラダイムです。

一般的な関数型言語は、ラムダ計算を基盤としていますが、これは従来の手続き型言語とは異なる特徴を持ちます。重要な違いの1つは、副作用についてです。関数型言語では、関数の評価結果が引数にのみ依存し、外部の状態を変更しない純粋関数が推奨されます。これにより、プログラムの挙動を理解しやすく、テストやデバッグが容易になります。 Haskellは純粋な関数型言語の代表的な例であり、副作用を極力排除し、強力な型システムを持つことで安全性と表現力を両立させています。一方で、SchemeやMLなどの言語では、型システムや評価戦略に異なるアプローチが取られていますが、基本的な関数型プログラミングの原則は共通しています。

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

• 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つです。

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

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