11. 関数型言語

11.1. 関数型言語とは

関数型言語のはっきりした定義はない。関数型と言われる言語には次のような特徴がある。

  • プログラムは関数定義の集合であり、関数呼び出しによってそれらを組み合わせる。

  • 関数は first class object である。

  • 文という単位は無く、プログラムの実行とは式を評価することである。

  • 参照透過性がある。

注釈

最も重要なのは参照透過性であるが、これを厳密に守っている言語は割と少ない。例えばLispは、代入などがあるので参照透過性は守られていない。ただ、参照透過性が守られる範囲でプログラムを書くこともできるので、Lispを関数型に分類する人も多い。

特に言語全体で参照透過性を守っていることを強調したい時は純粋関数型言語と言う場合がある。

11.2. 参照透過性

参照透過性(referential transparency)とは、式の構成要素がすべて同じなら、式の値は常に同じになるということ。

  • これの意味するところは、式の値を計算するのに、その時点での状態というものを考慮する必要がないということである。例えば、もし f(x) という式の評価結果が2になったとしたら、 f(x) を何回呼び出しても常に2を返す。

  • 手続き型言語に参照透過性がない原因は、変数の値が途中で変わることと、式の構成要素以外のもの（大域変数など）に依存した計算ができることである。

変数の値が途中で変わらないということから、関数型言語では、変数名は場所ではなく値に束縛される。

  • 同じ変数名でも環境が違えば異なる値に束縛されることに注意。これは、本来違う変数なのだがたまたま同じ名前が付いていると考える。

  • 環境を切り替えるのと代入するのは同じじゃないかと思うかもしれないが、次のような点が違う。

    • 環境が切り替わる点は関数呼び出しやletなど限られており、構文的なブロック構造と対応させることが多いので、代入よりもどこで変わるかがわかりやすい。

    • 環境を切り替えても前の値が消えてしまうわけではないので、元の環境に戻せば前の値にアクセスできる。それに対して代入というのは破壊的操作なので、前の値に戻すことができない。

構造を持つデータの場合は、構造が途中で変わらないということを意味する。これを永続データ構造(persistent data structure)と呼ぶ。

  • 例えば、リストの末尾に要素を追加する場合は、元のリストを変更してはいけないので、リストをコピーして要素を追加する。したがって、遅い。それに対して、リストの先頭に要素を追加する場合は、（リストの実装方法によるが）元のリストを共有できるので、速い。つまり、アルゴリズムによって効率が大きく変わることがある。

  • ほんとに永久に保存するわけではなくて、参照されなくなったデータはゴミ集めによって消去される。

11.3. 理論的な基礎

関数の概念を形式化した論理体系に ラムダ計算 がある。

  • ラムダ計算の式は、ラムダ抽象（関数定義に相当）と関数適用（関数呼び出しに相当）を組み合わせたものである。

11.3.1. 簡約

数学的な等式の場合、 1+3= の右辺には 5-1 と書いてもよいし、 22 と書いてもよい。しかし、プログラムの場合は 1+3 という式を評価した時に 4 以外のものが返ってきては困る。

  • ラムダ抽象と関数適用の組に対して、ベータ変換（関数の実行に相当）を行って式を書き換えることができる。書き換えた式は、元の式より簡単になることが多いので、これを簡約(reduction)と呼ぶ。

  • 簡約を繰り返し行って、もうそれ以上簡約ができない形になったら、それを最初の式の正規形（評価結果に相当）と呼ぶ。正規形は存在しないこともある。

関数型言語における式の評価とは、単に数学的に等しいものに変形するということではなく、簡約によって正規形を求めるということ。

11.3.2. 簡約戦略

ラムダ抽象と関数適用が複数含まれている式に対しては、ベータ変換のやり方も複数ある。その場合、どういう順序でベータ変換をやっていくかを決める規則を簡約戦略と呼ぶ。

作用的順序(applicative order)

入れ子になっている関数適用の内側から簡約していく。正規形が存在しても、到達できないことがある。

正規順序(normal order)

入れ子になっている関数適用の外側から簡約していく。正規形が存在すれば、必ず到達できる。

プログラミング言語で言うと、関数呼び出しの時に引数をいつ評価するかということに相当する。

正格評価(strict evaluation)

関数の引数を評価してから関数に渡す。作用的順序に対応。実装について言う場合は先行評価(eager evaluation)とも言う。

非正格評価(non-strict evaluation)

関数の引数を評価せずに関数の実行を始める。正規順序に対応。実装について言う場合は遅延評価(lazy evaluation)とも言う。

作用的順序

正規順序

正格評価

非正格評価

先行評価

遅延評価

値渡し

名前渡し

ラムダ計算で正規形に到達しないということは、プログラミング言語で言うと無限ループに相当する。

正格性と無限ループ

JavaScriptは正格な言語である。下のコードで bar(foo("a")) は無限ループになる。

function foo(x) {
  return foo(x)
}

function bar(x) {
  return "b"
}

console.log(bar(foo("a")))

Haskellは非正格な言語である。 foo "a" を評価すると無限ループになるが、 bar (foo "a") は引数を評価しないので、すぐに "b" が返ってくる。

foo :: String -> String
foo x = foo x

bar :: String -> String
bar x = "b"

main = putStrLn (bar (foo "a"))

11.4. モナド

参照透過性は関数型言語の重要な性質だが、それでは困る場合もある。

  • 乱数を使う場合。 random が毎回同じ値を返しては乱数にならない。

  • 入力を行う場合。例えばキーボードから一行入力する getLine は、人間が入力した値を返すので、呼び出されるたびに違う値になる。

また、遅延評価では副作用が起きる順序が不定なので困る場合もある。

  • 複数の出力を行う場合。例えば putStrLn("1") と putStrLn("2") を評価すると、1と2のどちらが先に出力されるかわからない。

上のような事態に対応するため、Haskellはモナド(monad)を導入した。