関数型言語の特徴

ガベージコレクション

多くの関数型言語ではリストが基本的なデータ構造となる。純粋な関数型言語では再束縛が不可となるので、forループで配列を扱うことはできず、リストを使って再帰関数で処理するのが基本となる。リストが関数の引数や返り値となるため、計算量的な事情からリストを指すポインタのみをやり取りする。関数内で宣言されたリストも返り値となるのでスタック領域ではなくヒープ領域に確保することになる。

ガベージコレクションはLISPが発表された1960年の論文Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part Iで初めて提案された。論文の4 The LISP Programming SystemではレジスタマシンにおけるLISPの実装について検討している。

Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I

Registers can be put back on the free-storage list when they are no longer needed. Even one register returned to the list is of value, but if expressions are stored linearly, it is difficult to make use of blocks of registers of odd sizes that may become available.

Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I

When the contents of a base register are changed, it may happen that the register to which the base register formerly pointed cannot be reached by a car − cdr chain from any base register. Such a register may be considered abandoned by the program because its contents can no longer be found by any possible program; hence its contents are no longer of interest, and so we would like to have it back on the free-storage list.

Lispでヒープアロケーションを多用することからガベージコレクションが導入されたらしい。

またクロージャを実装する手段の一つとしてもヒープアロケーションが使われる。

Closure (computer programming) - Wikipedia)

A language implementation cannot easily support full closures if its run-time memory model allocates all automatic variables on a linear stack. In such languages, a function's automatic local variables are deallocated when the function returns. However, a closure requires that the free variables it references survive the enclosing function's execution. Therefore, those variables must be allocated so that they persist until no longer needed, typically via heap allocation, rather than on the stack, and their lifetime must be managed so they survive until all closures referencing them are no longer in use.

This explains why, typically, languages that natively support closures also use garbage collection.

遅延評価

関数型言語では経時的に変化するようなオブジェクトを無限長リスト（ストリーム）で表現することがある。ストリームで表現することで状態をなくすことができる。粒子の状態をと定義すればそれは時刻によって変化するが、状態をの無限長リスト（世界線）で表現すれば状態は変化しない。その場合、将来のは分からないので評価を遅らせる必要が出てくる。また関数が参照透過なら引数の評価タイミングを任意にできるので遅延評価で無駄な計算を削減できる。Schemeはデフォルトで正格評価だけど遅延評価を利用することもできる。

関数型言語の分類

非純粋なら引数の評価タイミングが意味を持ってしまうので遅延評価は困難。動的型付けの純粋関数型言語として純Lispなどがあるがあまり多くないらしい。したがって関数型言語のパターンとして多いのは(静的，純粋，正格)，(静的，純粋，遅延)，(静的，非純粋，正格)，(動的，非純粋，正格)の四つ。属性の組合せごとに一個ずつ触れておくと良いかもしれない。

言語	型付け	純粋性	評価戦略
Idris	静的	純粋	正格
Haskell	静的	純粋	遅延
ML	静的	非純粋	正格
OCaml	静的	非純粋	正格
F#	静的	非純粋	正格
Scala	静的	非純粋	正格
Lisp	動的	非純粋	正格
Scheme	動的	非純粋	正格
Clojure	動的	非純粋	正格