15

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

関数の値は引数の値によってのみ決まる。→equational reasoning可能

equational reasoningの例： a = f(x) ⇒ g(f(x),f(x)) ≡ g(a,a)

純粋な（Pure）関数型言語：数学における関数と同様にequational reasoningが可能

命令型（Imperative）言語：関数型言語と同様の構文は有るが…

関数の動作について非局所変数への副作用（side effect）が許されている。

変数への代入が可能なので同じf(x)が同じ値について呼び出しである保証がない。

…ので関数の評価値が呼び出し毎に異なることがあり得る。

高階関数：関数型言語の特徴。

関数を引数として関数に渡せる。

関数値として関数を返せる。

また、そのようなことを行う関数を高階関数と呼ぶ。

関数の入れ子定義（nested function）

lexicalスコープ（あるいはブロック構造）

という特徴の下で高階関数が用いられると特に興味深い。

Tigerにおけるlexicalスコープ：入れ子の内側で定義された関数が外側の関数の変数や引数を参照できる。

高階関数型言語：入れ子の関数と高階関数を備えた関数型言語。

この章では…

Fun-Tiger：高階関数を含むよう拡張したTiger言語。副作用が許されていてequational reasoning不可。Scheme、ML、Smalltalkなどのような純粋でない高階関数型言語（impure, higher-order functional language）。

PureFun-Tiger：高階関数の追加に加えて関数で副作用を認めないよう変更されたTiger言語。厳密で純粋な関数型言語（strict, pure functional language）の本質を理解するための言語。（純粋な関数型に制限したMLのサブセットに似ている。）

Lazy-Tiger： Haskellのような遅延評価（Lazy Evaluation）を備えた厳密でなく純粋な関数型言語（non-strict pure functional language）。equational reasoningを良く支援する。

というような関数型言語における三つの異なった趣向について考える。

備考： SISALのように純粋な1階関数型言語はequational reasoningをサポートするが高階関数は受け付けない。

15.1 単純な関数型言語

/* 高階関数型言語　Ｆｕｎ-Tigerの実現その１ */

関数型の追加：

ty → ty -> ty

→ ( ty { , ty} ) -> ty

→ () -> ty

関数型の例：

int->string

整数1個を引数にとって文字列を返す関数の型。

(int, string)->intarray

整数と文字列を1つづつ引数にとってintarrayを返す関数の型。

()->string

getchar関数のように引数なしで文字列を返す関数の型。

(int->int)->int->int

->が右結合なので((int->int)->(int->int))とグループ化して考えて（こうは書けないが…）、int->int型の関数を引数にとってint->int型の関数を値として返す関数の型。

関数呼び出し式の変更：（呼び出し式で関数名に限られていた部分に任意の式を認める。）

exp → exp ( exp { , exp} )

exp → exp ( )

関数型の使用例：（プログラム例15.1）

addFiveとaddSevenが呼び出したintfun型のaddはそれぞれ引数nを5、7として関数hを返すのでnはhの各インスタンスについて非局所的に記憶しておく必要がある。これが後述する閉包（closure）実装の動機となる。同様にtwiceは関数fをgの各インスタンスについて記憶する必要がある。

15.2 閉包

/* 高階関数型言語　Ｆｕｎ-Tigerの実現その２ */

実行時における関数の表現：

＜入れ子の関数定義を持たない（Cのような）言語＞

→ 変数のように（関数の機械語コードを指す）番地で表現可能。

→ 変数と同様に格納、引数渡しでき、呼び出し時にはレジスタ番地を使った関数呼出し命令で呼び出せる。

→実装はラベルと変数用のテンポラリを利用できる。（P.312の例）

＜入れ子になった関数を許す言語＞

→ 外側のフレームの変数をアクセスするための情報が必要なので関数の番地だけでは不十分。（P.311のプログラム例でhがn、gがfを参照する。）

→ 関数の番地及び、非局所変数にアクセスするための情報をまとめた閉包（closure）として関数型変数を表現、記録する。

→ （閉包の簡単な実現）関数の番地とスタティック・リンクの対。スタティック・リンクをたどって非局所変数にアクセスできる。

備考：閉包が変数へのアクセスを提供する部分に注目する場合、環境（enviroment）と呼ばれる。

閉包の実現について：

閉包はスタティック・リンクに基づく必要はない。むしろスタティック・リンクによる閉包の実現には

最外側の変数にアクセスする場合多段の間接参照外しが必要

最外側の変数だけが必要で連鎖の中間にある変数が不要でも塵集めできない。

という不利な点もある。本章では簡単のためにスタティック・リンクを用いる。

ヒープに割り付けられたActivation Record

P.311の例から：　add終了後もaddはhに環境を提供する。　→addのフレームはaddの終了時に破棄できずスタックに置けない。　→フレームをヒープにおいて回収はGCに任せる。

改良（テキストの図15.2）：　抜け出している（escape）変数だけを抜け出し変数レコード（escaping variable record）にまとめてヒープに置く。それを指すEPという局所変数を用意する。スタティック・リンクは抜け出し変数レコード間で張る。

Tigerコンパイラの修正

Frameモジュールを修正する。

抜け出している変数のための抜け出し変数レコードを作成するコードを生成（procEntryExit1で生成するコード内）。

抜け出し変数レコードを指す抜け出していない変数EPを用意する。EPは通常の変数同様溢れれば（spill）フレームに置かれる。（allocLocal内）

関数の隠しパラメータとして渡されるスタティック・リンクは抜け出し変数レコードに置く（newFrame内）。

抜け出している変数のアクセスにはFPに代えてEPを用いる。

15.3 変更不能な変数

/* 厳密に純粋な関数型言語PureFun-Tigerの実現 */

equational reasoningを可能にするために世界（world）を変更するような副作用を禁止する。

変数への代入。（変数宣言のような初期化を除く。）

ヒープ上のレコードのフィールドへの代入。

目に見える作用を持つ関数（print、flush、getcharやexit）の呼び出し。

厳しすぎるように見えるが…

例：　15.3のプログラム（テキスト108ページの二分探索の実装）のように既存の木を更新するのではなくコピーして変更箇所を追加したものを結果とすれば動作できる。

t2 := enter(t1, "mouse", 4)後にt1もt2も利用でき、t1を放棄後はGCによって不要になったノードが回収される。

Continuationに基づく入出力

continuationに基づく入出力（continuation-based I/O）：　「代入なし」に従うため既存のデータ構造の更新によらず新たなデータ構造を生成する場合の入出力。

type answer

プログラム全体が返す「結果」を示す型。exit関数の戻り値の型。

type stringConsumer = string -> answer

入力後の動作を示す関数の型。この型の関数は一般に入力関数（ここではgetchar）から渡された値を処理する関数。この型の関数を入力関数に入力の受取り手として渡す。この関数の「結果」は入力関数の「結果」となる。

type cont = () -> answer

出力後の動作を示す関数の型。この型の関数を出力値と共に出力関数（ここではprintやflush）に渡す。この関数の「結果」は出力関数の「結果」となる。

この変更によって入出力はequational reasoningと共存できる。

加えてI/Oを行う関数の返値は全てanswer型を持つので型検査時から識別できる。

言語の変更

組み込み型answer、stringConsumer、contの追加。既定義の入出力関数について型の変更。（プログラム15.4）

「手続き（procedure）」（返値の型が明示されていない関数）の返値はanswer型とみなす。

代入文、whileループ、forループ、複合文を言語定義から取り除く。

プログラム例15.5：　これは整数の読みこみ、読みこんだ整数の階乗の出力をループによって12より大きい数が入力されるまで繰り返し行うPureFun-Tigerのサンプルプログラム。このプログラム内の呼び出し関係を下に図示する。最後のexit()が呼び出されるまで再帰的な呼び出しが続き、factrialの呼び出しを除いて、途中では復帰していないことがわかる。

純粋な関数型言語の最適化

PureFun-TigerはFun-Tigerから（既定義の型を変更した以外）機能を削減しただけ　→Fun-TigerコンパイラはPureFun-Tigerプログラムをコンパイルできる。

一般に関数型の言語は命令型言語の最適化（インライン展開、命令選択、ループ不変式解析、グラフ・カラーリングに基づくレジスタ割り当て、コピー伝播など）を全て利用することができる。

制御フローも計算できるが、

フローが関数の呼び出し関係で表わされる。

関数の呼び出しが変数値に基づくことがある。

のために若干難しくなる。

PureFun-Tigerでは以上に加えてequational reasoningが可能であることを生かしていくつかの最適化ができる。

type record = { a : …, b : …}

var a1 := 5

var b1 := 7

var r := { a := a1, b := b1 }

var x := f(r)

var y := r.a + r.b

というコード片について、ｆに副作用がない。　→　yの計算の際もr.aとr.bが各々a1=5、b1=7のままであり、y=12もこの後yのスコープ内では成り立っている。　→それぞれ定数で置き換えて良い。（同様の置換は命令型でも可能だが、副作用のため保守的に行わざるを得ず、殆ど置換できない。17.5節のalias解析参照）

備考：　MLには更新不能な純粋関数型のレコードと更新可能なレコードがあり、前者については定数への置換による変換が可能である。

15.4 インライン展開

/* 関数型言語Fun-Tiger ＆　PureFun-Tigerの最適化その1　*/

関数型のプログラムでは多くの小さな関数を使う。　＆　特に関数を引数に渡して使う。　→素朴にコンパイルすると命令型プログラムより関数呼び出しが増える。　→関数のインライン展開（inline expansion）：　関数呼び出しを関数本体のコピーで置きかえる。

例：　

15.6 ：汎用のリスト遷移関数doListの使用。

15.7(a) ：リスト遷移にprintDoubleという特定の動作が組み込まれて柔軟性が減っている。（一般のTigerでは関数を引数に渡せない。）

15.7(b) ：インライン展開と15.6節の末尾再帰の最適化で15.6のプログラムはこれと等価に最適化できる。

最適化は、特殊な目的の関数を書いたとき並に効率の良い関数を汎用性を失わない形で書けるようにすること。

変数の捕獲（variable capture）の回避

重複する名前の局所変数の宣言で外側で宣言された変数名が「隠されて」いる場合に単純な展開を行うと関数の意味が正しくなくなる場合がある。

例：仮引数によってfに導入された局所的なxがfで展開されるgの参照する外側の変数xと重複している。

対策：

仮引数や局所変数の名前が外側の変数名と重複しないように変換する（α-変換）。

展開する実パラメータの名前を重複しないように変換する。内側の新たな変数を置換してしまわないように注意して置換関数を定義する必要がある。

プログラム中の全ての変数の名前が重複しないように早い段階のパスで変換する。

インライン展開の規則

アルゴリズム15.8：

命令型プログラムにも適用可能。

(a) 実パラメータが単純な変数

関数本体中の仮引数を実引数の変数で置換

(b) 実パラメータが式

重複しない局所変数を実パラメータで初期化して宣言。その局所変数で関数本体中の仮引数を実引数の変数で置換。（equational reasoningが可能な場合は効率のため、そうでない場合は副作用の重複を避けるため。例はp.323。）

利用されていない関数の除去（Dead function elimination）

全ての呼び出しがインライン展開された関数、そして引数に渡される他のどんな方法でも参照されていない関数は取り除くことができる。

再帰的な関数のインライン展開

再帰呼び出しをしている関数をインライン展開するとループ中の最初の反復だけ（only the first iteration of the loop）が展開され展開結果に展開した関数の呼び出しが残る。

例：　printTable内のdoListを展開すると結果にリストの尾部に対するdoListの呼び出しが残っている。

対策：　loop-preheader変換。再帰呼び出しをしている関数を分割する。

序（prelude）：　外部から呼び出せる関数。例中のdoList。

ループ先頭（loop-header）：　序からだけ内部的に再帰呼び出しされる関数。例中のdoListX。

このようにしてから序の方だけが展開され、それに伴ってループ先頭は定義が局所的な関数としてコピーされる。

ループ不変（loop-invariant）な引数

ループ先頭（loop-header）の中で再帰の際にそのまま渡される引数がある場合に、その変数はループについて不変であると考えられる。これらは引数として渡さずとも、外側の定義を参照すればよい。（ループ不変変数の巻き上げ（loop-invariant hoisting）変換。アルゴリズム15.10。）

例：　書き換え後、doListXのfとcはそれぞれdoListXの引数から外れ、doListXは代わりにdoListのfxとcxを直接参照する（p.325上段の書き換え）。この書き換え後printTableでdoListを展開したものがp.325中段。

連鎖的（cascading）インライン展開

引数として渡された関数を連鎖的に展開する。

例：　printTableでprintDoubleをdoListに単に渡すのではなく、doListが展開された際、それがdoList内で呼ばれているところで展開する。（p.325の下段）

コードの爆発的増殖（code explosion）の回避

インライン展開は関数本体の複製を伴う。　→一般にプログラムが大きくなる。　→無差別な展開はプログラムの大きさを爆発的に増加させる。（実際、1つの関数展開が展開可能な関数のインスタンスを作り出して無限に増加させる例が作れる。）

爆発的増殖を抑止するHeuristicな規則：　

頻繁に呼び出されているところだけを展開する。：ループの入れ子の深さを解析したり、プロファイラからのフィードバックを利用する。

関数呼び出しのコード量に比較して小さな本体を持つ関数は展開する。

一度だけ呼ばれている関数は展開して、オリジナルは利用されていない関数の除去（Dead function elimination）によって削除する。

letの入れ子の展開（unnesting）

Tiger言語では

let dec₁ in let dec₂ in exp end

は

let dec₁ dec₂ in exp end

と等価。

例：　書き換え後はプログラム15.11。

15.5 閉包変換

/* 関数型言語Fun-Tiger ＆　PureFun-Tigerの最適化その2 */

関数型言語の閉包変換（closure conversion）フェーズはバックエンドを簡単化するために、自由変数（フレームと切り離して格納してある抜け出している変数）へのアクセスは仮引数を通じて明示的に行うようにプログラムを変換する。

具体的には：

一階層上へのスタティック・リンクと自由変数を含むレコードを明示的に宣言する。p.327の例ではvar rの宣言。

関数呼び出し時には第一の引数としてそのレコードへのポインタ（スタティック・リンクの最初の段となる。）を渡す。p.327の例ではa₀。

自由変数（上の階層の変数）へのアクセスはそのポインタを介して明示的に行う。

関数型の値：　関数型の引数が必要なときにはそのレコードへのポインタと関数へのポインタの対（閉包）を明示的に渡す。

例：　15.11を閉包変換して、15.12を得る。

doListXについてのレコード（15.12中のr2とr3）のように、レコードは自身を渡す相手の関数に応じて中身が違う複数種類の定義があってよい。（これによって1パスでレコードの定義が作れる。例えばr2の定義の時点ではdoRestFuncが定義できない。）

contに対応するスタティック・リンクの型を呼び出し側が知ることはできるとは限らない…

printTableのc引数はmainに由来する何か。（実際のところ15.6ではexit。）

doListに渡されるprintDoubleが受取るのはdoRest。

putIntに渡されるのはagain

…よってcontに対応するスタティック・リンクの型は？で表わされる。（展開と巻き上げの効果で、？の仮引数宣言が目に見える部分はprintTableだけ。）こうしてTigerの文法下でFun-TigerやPureFun-Tigerの関数を記述できるが、通常の意味での型検査は行われない。

15.6 効率的な末尾再帰

/* 関数型言語Fun-Tiger ＆　PureFun-Tigerの最適化その3　*/

関数プログラムでは制御フローは関数呼び出しで表わされる。

例：　15.7bのwhileループに対応するのが15.12ではdoListXの呼び出し。15.7bで単に2度呼び出されているputInt関数はcontinuation関数に変換されている。Fun-Tiger関数はこれらdoListX、doRestやagainを効率良くコンパイルする必要がある。

関数の呼び出しが末尾にある場合、その関数の返値は呼び出し元の返値でもあるから（p.329下段の例のf(x)）、その関数呼び出しをジャンプで実装して直接大元の呼出し元に復帰すればよい。もしスタック・フレームの中身がなくて準備する必要がなければ大変効率が良くなる。

「末尾」の形式的定義：　B_iは末尾。C_iはそうではない。

let var x := C₁ in B₁ end

C₁ (C₂)

if C₁ then B₁ else B₂

C₁ + C₂

関数呼び出しf(x)が式の末尾にあり、その式がそれを含む式の末尾にあり、そのようにして関数定義の末尾にあれば、末尾呼び出しだと言える。

末尾呼出し手順の実際：　

実パラメータを引数レジスタに移動する。

呼び出され側保存レジスタを復帰する。

もしあれば、呼び出す関数のフレームをpopする。

呼び出したい関数にジャンプする。

1は多くの場合コピー伝播（融合coalescing）フェーズで除去される。

2と3は呼び出す関数にスタック・フレームがなければ除去できる。（呼び出し元保存レジスタだけで作業ができればスタック･フレームは不必要。）

例：

プログラム15.12では全ての関数呼び出しが末尾呼び出しになっている。double関数の呼び出しは元の15.6では末尾にないが、インライン展開によって関数呼び出しでなくなっている。

表15.13はコンパイル後の比較。制御の流れは殆ど同一になっている。

残った違いは自由変数をヒープのレコードに確保する手間とスタックフレーム確保の手間の差。

ヒープ上の自由変数確保にかかる手間の削減：

抜け出し解析（escape analysis）によってヒープ上の自由変数がprintTableについて局所的であることを確認できればまとめてスタックにおける。これによって関数型のコードは命令型のコードと同一になる。

ヒープからの割り当てとGCは大変安価にしうる。４～5命令でヒープにレコードを確保できるので、命令型コードと殆ど同じ速さにできる（13.7節fast allocation参照。p.285）。

15.7 遅延評価（Lazy evaluation）

/* 関数型言語Lazy-Tigerの実現　*/

equational reasoningの主要な法則

β-置換（β-substitution）：　

f(x) = B ⇒　f(E) ≡　B[ x |→ E]

例（p.331）：　右側は左側のf(loop(y))をβ-置換（Ｂをfの本体としてEをloop(y)として）して展開したもの。

2つのプログラムはequational reasoningの下で同値だが動作は異なる。（y=0で左は無限ループに陥り、右は0を返す。）　→これは明らかに不都合。

PureFun-TigerではAがBを置換して作ったプログラムであるとき、双方とも停止すれば両者は同じ結果を与えるが、同じ入力集合について一方が停止しないことがあり得る。

この部分的な不都合を改善するために不精な評価（lazy evaluation）を導入する。

Lazy-Tigerの文法はPureFun-Tigerと同じ、意味も殆ど同じだが、Lazy evaluationされるところだけが異なる。

	特徴	言語の例
Lazy言語	他の部分で値が必要とされている式しか評価されない。	Miranda、Haskell、Lazy-Tiger
Strict言語	制御の流れが到達する式は全て評価される。	ML、Java、C、Tiger、PureFun-Tiger

名前による呼び出し評価（call-by-name evaluation）

Call-by-value：

関数の引数には値が渡される。f(g(x))の評価の例ではg(x)の結果がfで使われようが使われまいがg(x)が計算されて結果の値がfに渡される。（Pascal、ML、Java、C、Tiger、PureFun-Tigerの場合）

Call-by-name：

必要な値だけを計算するために変数宣言は関数宣言（サンク（thunk）と呼ばれる。）に、参照はその関数の呼び出しにそれぞれ変換される。

例えばint型の値が宣言されると()->intという関数型の値が作られ、int型の値が参照されるところではその()->int型の関数が呼び出される。（変数宣言は仮パラメータでも行われるので、関数呼び出しについて各実引数ごとに小さな関数宣言が必要となる。）

例15.14：　15.3aのlookについて上述の変換を行ったもの。

Call-by-nameの問題点：

サンクが大量に作られ呼び出される点。それらは同じ値を計算する場合も何度も呼び出される。15.14の例ではlook(t1, k)が呼び出される度にt1()も呼び出されて全く同一の木を何度も構築する。

必要時呼び出し（call-by-need）

Lazy evaluationは必要時呼び出し（call-by-need）とも呼ばれる。　→名前による呼び出しを修正して同じサンクが2度実行されないようにする。

実現方法の概要：

サンクにメモ･スロット（memo-slot）を追加してサンクの呼び出し毎にそこを調べる。

1度目の呼び出しならばメモ･スロットは空で、値を求めるサンク関数を呼び出してメモ･スロットに蓄え、その値を返す。

2度目以降の呼び出しではメモ･スロットに蓄えた値を返す。

実現の詳細：

サンク関数へのポインタとメモ・スロットからなるレコードでサンクを表現する。サンク関数へのポインタはunevaluatedサンク関数を指し、メモ・スロットは必要なスタティック・リンクを持つように初期化しておく。

1度目の呼び出しの際はメモ・スロットに記録しておいたスタティック・リンクを伴ってunevaluatedサンクが呼び出される。unevaluatedサンクは値をサンク関数へのポインタをevaluatedサンク関数へのポインタに差し換えて、値を計算してメモ・スロットに格納し、その値を返す。

2度目以降の呼び出しではevaluatedサンク関数が呼ばれる。evaluatedサンク関数は単にメモリ･スロットに蓄えた値を返すだけである。

例：　プログラム15.1のvar twenty := addFive(15)のコンパイル後擬似コード

intThunk：int値に対応するサンク（レコード）の型。intfunc：サンク対応したintを返す関数閉包の型。intfuncThunk：intを返す関数に対応するサンク（レコード）の型。

evaluatedFuncはintを返すevaluatedサンクの本体サンクのレコードを受けとってメモの値を返す。

EPの指すレコードには環境が含まれる。例えばaddFive関数についてのintfuncThunkも含まれる。

addFiveの引数の15はfifteenThunkという名のintThunk型サンクで表現され、将来の関数評価の際に計算を行うために関数内に局所変数として記録される。関数が呼び出された際にはサンクを使ってサンク関数を呼び出す。（定数なので最初からevaluatedFuncが使用されている。）

twentyFuncサンク関数は値を計算し、メモ・スロットに結果の値resultを蓄え、サンク関数をevaluatedFunc関数に差し換え、最後に結果の値resultを返す。

Lazyプログラムの評価

例：

15.3bのenter関数を使って

three　|→　3!

minusOne　|→　(-1)!

という写像のための木を作ることを考える。

ここでfact(-1)の結果は未定義である。

PureFun-Tiger：

木を作るためにfact(-1)を計算しようとして無限ループに陥る。

Lazy-Tiger：

3!の値を出力する。

↑の内訳：

変数t1が定義されるが実際にはenterは呼び出されないでt1のためのサンクが作られる。

変数t2が定義されるが実際にはenterは呼び出されないでt2のためにlook(t2, "three")を呼び出すためのサンクが作られる。（ただし直接そこで呼び出すわけではない。）

最後にanswerを返すputInt(…,exit)という式のためのサンクが定義される。ただし実際にanswerが計算されるのは最外側のサンクが呼び出されたとき。

putIntの実行が始まるとその最初の引数の値が必要になってlook(t2, "three")のためのサンクが実行される。

lookは引数tとkのためのサンクを実行する。

tが返したレコードのt.keyというフィールドもサンクなので実際には(t().key).()という関数によってキーとなる整数が得られる。（この場合それはfact(3)の値）

t.key()が"minouseOne"ならばlook(t().right, k)が呼び出されるが、この場合はminusOneに対応するノードのbindingサンクは呼び出されないので、fact(-1)は計算されず、無限ループに陥ることもない。

サンクが実行されることを触れる（touch）という。

Lazy関数型プログラムの最適化

遅延関数型言語でも厳密な関数型言語や命令型言語と同様の数多くの最適化が可能。

ループは認識され（単純な末尾再帰の場合）、induction変数は識別され、共通部分式は削除される、など。

加えて、遅延評価関数ならではのequational reasoningを生かした最適化が可能。

不変変量の巻き上げ（invariant hoisting）

例：

h(i)の計算はg()の実行とは独立して計算可能。→別に計算して変数に格納することで計算が削減できる（g()が複数回呼び出される場合）。

しかし厳密な言語ではこの変換ができない。

var a := f(8)

というコードがあって結果の関数aが全く呼ばれていなくて、かつh(8)が無限ループに陥るような場合、変換前は停止するが、変換後は無限ループに陥る。（この変換は非関数型言語では副作用の回数が変わるので論外。）

実行されないコード（dead-code）の除去

例：

dが使われていないのでg(x)の呼び出しも削減可能。

しかし：

非純粋関数型言語ではg(x)の副作用をアテにしている可能性があるのでこの最適化は不適切。

厳密に純粋な関数型言語では終了しないプログラムが終了するようになってしまう可能性があり、最適化レベルで挙動が代わるとプログラマを混乱させるので不適切。

deforestation

多くの言語では、あるモジュールがデータ構造を生成して、別のモジュールがそれを処理することが一般的。

例（プログラム15.15）：

range(i,j)がiからjまでの間の数のリストを生成する。

squaresは与えられたリストの数の二乗のリストを生成する。

sumは与えられた数に与えられたリストに含まれる全ての数を足しこむ。

この際、関数間で引き渡される中間結果も含めて3つのリストが作られるがそれは無駄。deforestして1つの関数に融合できる。（P.337真中の例）

非純粋関数型言語ではこの変換は一般に正しくない。（inc、mul、addが自分の結果を逐次出力した場合を考えると評価順が変わる。p.337の出力例は変換前でp.338の出力例は変換後。）

この変換は純粋な関数型言語では正しい。

厳密性解析（strictness analysis）

サンクの生成と評価のオーバーヘッドを減らす最適化が必要。これができないと他の最適化を利用してもなお遅くなると思われる。　→必要なサンクだけを生成する。

例：　f(x)は引数xを評価することが明らかならば、サンクを渡さずに値を渡せば良い。

厳密性の定義

関数f(x)が厳密（strictness）であるとはf(x)に渡される実引数aの評価が停止せず失敗するならばf(a)の評価も停止せず失敗することである。

多引数版：

関数f(x₁,…,x_n)がx_iについて厳密であるとは実引数aの評価が停止しないならf(b₁,…,b_i-1,a,b_i+1,…b_n)の評価も停止しないこと。

例：

ｆ：x、yの双方に付いて厳密。

ｇ：xについてのみ厳密。yは評価されない場合がある。

ｈ：どの引数についても厳密でない。どの引数も関数内で評価はされていない。

ｊ：xを評価していないにも関わらず定義からxについて厳密。（「ならば」の性質から。この定義をした目的は引数を評価してから渡す際の安全性をみることだからどのみち無限ループに陥る関数はどうせどっちでもいい。）

strictness解析の結果の利用

例（15.16）：　厳密性解析の結果を利用した15.3aのlook関数のcall-by-nameへの変換結果。

15.14の全面的にcall-by-needに変換した場合と似ているが…。

lookはtとkeyに関しては厳密（k>t.key式があるから）である。　→tとkeyについては触れる（touch）必要がない。

しかしt.key、t.left、t.rightについては厳密でなくサンクが必要。

引数が厳密なので呼び出し側はサンクを渡す必要はない（再帰呼び出しの部分を参照）。

近似strictness解析（Approximate strictness analysis）

上記の例のf、g、hの場合のように簡単（最適化コンパイラが見つけられる程度に）なこともあるが、厳密性を正確に調べることは一般には計算可能ではない（p.218の動的生存解析やその他のデータフロー問題と同様）。　→保守的に近似を行う。

保守的な近似：

ある引数について正確に厳密性を決定できない場合は厳密でないと仮定してサンクが生成される。　→遅くなるが、停止するプログラムを停止しないように変換することはなくなる。

厳密性計算アルゴリズム（15.17）：

関数fの引数の個数をnとする。

(f, (b₁,…,b_n))という組の集合をHとする。ここでb_iは論理値。（例：　f, (1, 1, 0)とはfの三つの引数のうち最初の二つの評価が停止して、三つ目の評価が停止しなくても関数の評価は停止するという意味。集合Hにこの組が含まれるなら関数は3番目の引数について厳密でない。集合Ｈに含まれないならばfが3番目の引数について厳密かどうかははっきりしない。）

補助的な関数として、式が停止するかどうかを計算する関数が必要。式Eと変数の集合σについてM(E, σ)とは「σの全ての変数の評価が停止するであろう場合、式Eの評価も停止するだろう。」を意味する。（例1：　E1をi+jについてiとjのサンクが停止しうるとき、E1も停止しうる：M(i+j, {i, j}は真。例2：　E2がif k then i else jであるとしてiとjが停止し得てもkが停止しないならばE2は停止しない：M(E2, {i, j})は偽。）

このアルゴリズムは高階関数を取り扱えないのでLazy-Tigerでは上手く働かない。高階関数を扱うにはより強力なアルゴリズムが必要。