LispはLispプログラムを作り上げるブロックであり，Lispを作り上げるブロックでもある．
大抵のプログラミング言語では，
オペレータ + はユーザの定義した関数と全く違ったものになっている．
しかしLispは関数の適用という，
プログラムによって行われる全ての計算を説明する単一のモデルを持っている．
Lispのオペレータ + は1個の関数であり，
ユーザ自身が定義できる関数と全く同じだ．
事実，特殊オペレータと呼ばれる少数のオペレータを除き，Lispの中核はLispの関数の集合だ． この集合に追加するのをためらう必要があるだろうか？ そんなことはない：Lispがこれをしてくれたら， と思うことがあればそれを自分で書くことができ， その新しい関数は組み込みのものと全く同じように扱われるだろう．
この事実はLispプログラマにとって重要な結論をもたらす． これは新しい関数のどれもが，Lispへの追加とも， 特定のアプリケーションの一部とも考えられるということだ． 熟練Lispプログラマの典型的なやり方は，両方を幾らかずつ書き， プログラミング言語とアプリケーションが完璧に噛み合うまで二つの境界を調整することだ． この本はプログラミング言語とアプリケーションを相性よくまとめる方法について 書かれたものだ． この目標に向かって行うことはみな関数に依存するのだから， 関数から始めるのが自然なやり方だ．
Lispの関数を他から際だたせているのは2個の特徴だ． 1個目は，上で述べたようにLispそのものが関数の集合だということ． このことはLispに自分で作った新しいオペレータを追加できるということだ． 関数に関して知るべきもう一つの大事なことは，関数はLispのオブジェクトだということだ．
Lispは，他のプログラミング言語で目にするようなデータ型をほとんど提供する． 整数も浮動小数点数もあれば，文字列，配列，構造体等もある． しかしLispはあるデータ型を提供するが，これは最初は衝撃的かもしれない：関数だ． ほとんど全てのプログラミング言語が何らかの形で関数や手続きを提供する． Lispがそれらをデータ型として提供するとはいったいどのような意味なのだろう？ それはLispでは関数を使って， 他の親しみ深いデータ型（整数等）でやろうと思うことが全てできるということだ： 実行時に新しくオブジェクトを作り，変数や構造体の中に保持し， 他の関数に引数として渡し，結果として返す，等．
実行時に関数を生成し，それを返す能力は特に便利だ． これは「あるコンピュータで走る自己修正的機械語プログラム」 のように眉唾物の長所に思えるかもしれない． しかし実行時に新しい関数を生成することは， Lispプログラミングの定石テクニックということが分かるだろう．
大抵，最初にdefunで関数を定義する方法を習う筈だ．
次の式は引数の2倍を返すdoubleという関数を定義する．
> (defun double (x) (* x 2)) DOUBLE
Lispにこれを与えれば，doubleは他の関数内でも，トップレベルでも呼び出せる：
> (double 1) 2
Lispコードのファイルは主にそういったdefunから成り立っていて，
CやPascalのようなプログラミング言語での手続き定義のファイルに似ている．
しかし大きな違いが明らかになる．
このdefunは手続き定義ではなく，Lispの呼び出しなのだ．
この区別はdefunの背後で何が起きているのかを見れば明らかになるだろう．
関数はそれ自身が全くのオブジェクトだ．
実際にdefunが果たす機能は関数を作り，
1個目の引数として与えられた名前でそれを保持することだ．
だからdoubleを呼び出すのと同様，
その機能を実装する関数を得ることができる．
これには普通 #'（シャープ・クォート）オペレータを使う．
このオペレータは名前を実際の関数オブジェクトに対応させるものと理解すればいい．
これをdoubleの名前の前に置くことで
上の定義で作られた実際のオブジェクトが得られる：
> #'double #<Interpreted-Function C66ACE>
表示された表現はLisp処理系の実装ごとに違うけれど， Common Lispの関数は基本的オブジェクトで， 数や文字列といった親しみ深いオブジェクトと同じ役割を持っている． だからこの関数を引数として渡したり，返り値として返したり， データ構造のなかに保存したり，色々なことができる：
> (eq #'double (car (list #'double))) T
関数を作るのにはdefunも要らない．
Lispのオブジェクトのほとんどと同じように，それを文字通りに参照することができる．
整数を参照したいときは，ただ整数そのものを使う．
文字列を表現したいときは，ダブルクォートで囲まれた一連の文字を使う．
関数を表現するには，\emph{λ式}と呼ばれるものを使う．
$\lambda$式はリストで，3部分から成る：lambdaシンボル，仮引数のリスト，
0個以上の式から成る本体だ．
次のλ式はdoubleと等価な関数を示している：
(lambda (x) (* x 2))
これは1個の引数xを取り，2xを返す関数を規定している．
λ式は関数名とも考えられる．
doubleが「ミケランジェロ」のような固有名だとすれば，
(lambda (x) (* x 2))は
「システィーナ礼拝堂の天井画を描いた男」のような，定義となる説明だ．
シャープクォートをλ式の前に置くことで対応する関数が得られる：
> #'(lambda (x) (* x 2)) #<Interpreted-Function C674CE>
この関数はdoubleと全く同じ働きを持つが，二つは異なったオブジェクトだ．
関数呼び出しでは関数名が先頭に来て，引数が続く：
> (double 3) 6
λ式は関数名でもあるから，関数呼び出しの先頭に来ることもできる：
> ((lambda (x) (* x 2)) 3) 6
Common Lispではdoubleという関数とdoubleという変数を同時に持つことができる．
> (setq double 2) 2 > (double double) 4
名前が関数呼び出しの先頭かシャープクォートの次に来ると関数への参照と見なされ， それ以外では変数名と見なされる．
だから「Common Lispには変数と関数に異なった\emph{名前空間}がある．」と言える．
fooという変数とfooという関数を両方持つことができ，
それらは別々である必要もない．
この状況はややこしく，コードがかなり格好悪くなってしまうことにつながるが，
これはCommon Lispプログラマが付き合っていかなければならないことだ．
必要に応じ，Common Lispではシンボルをその表現する値に対応させたり，
その表現する関数に対応させる関数が使える．
関数symbol-valueはシンボルを引数に取り，
対応するスペシャル変数の値を返す：
> (symbol-value 'double) 2
またsymbol-functionはグローバル関数について同じことをする．
> (symbol-function 'double) #<Interpreted-Function C66ACE>
関数は普通のデータ・オブジェクトなので，変数が値として関数を持てることに注意：
> (setq x #'append) #<Compiled-Function 46B4BE> > (eq (symbol-value 'x) (symbol-function 'append)) T
背後では，defunはその1個目の引数のsymbol-functionを，
残りの引数で組み立てられる関数に設定しているのだ．
次の2個の式は大体同じことをしている：
(defun double (x) (* x 2))
(setf (symbol-function 'double)
#'(lambda (x) (* x 2)))
だからdefunは他のプログラミング言語での手続き定義と同じ役割を持つ．
つまり名前をコードの一部に関連づけることだ．
しかし背後の仕組みまで同じではない．
関数を作るのにdefunは必要ではなく，
関数は何かのシンボルの値として保存されなくてもいい．
他のプログラミング言語の手続き定義に似たdefunの背後には，
もっと一般的な仕組みが隠れている：
関数を作ることと，それをある名前に関連づけることは別々の働きだ．
Lispの関数の概念の一般性全体までは必要ないとき，
defunはもっと制限の強いプログラミング言語と同じ位単純に関数定義を行う．
関数がデータ・オブジェクトであるということは， 何より関数を他の関数の引数として渡せるということだ． この可能性はLispにおけるボトムアップ・プログラミングの重要性を 支えるものの一つなのだ．
関数がデータ・オブジェクトとなりうるプログラミング言語では，
オブジェクトはそれを呼び出す方法も何か提供しなければならない．
Lispではその関数はapplyだ．
一般的にapplyは2個の引数で呼ばれる：
関数と，そのための引数のリストだ．
以下の4個の式はみな同じ働きをする：
(+ 1 2) (apply #'+ '(1 2)) (apply (symbol-function '+) '(1 2)) (apply #'(lambda (x y) (+ x y)) '(1 2))
Common Lispではapplyには幾つの引数を渡してもよく，
1番目に渡された関数が適用されるのは，
残りの引数を最後のリストにコンシングすることで得られるリストだ．
だからこの式
(apply #'+ 1 '(2))
は上記の4個の式と等価だ．
引数をリストとして渡すのが不便だと思ったらfuncallを使えばいい．
これはその点のみがapplyと違っている．
この式
(funcall #'+ 1 2)
も上記の式と同じ働きを持つ．
Common Lispの組み込み関数の多くが関数を引数に取れる．
中でも最もよく使われるものの一つが対応付け(mapping)関数だ．
例えばmapcarは2個以上の引数（関数と1個以上のリスト，
その関数の取る引数毎にリストが1個必要）を取り，
その関数をそれぞれのリストの要素に先頭から適用していく．
> (mapcar #'(lambda (x) (+ x 10))
'(1 2 3))
(11 12 13)
> (mapcar #'+
'(1 2 3)
'(10 100 1000))
(11 102 1003)
Lispプログラマにはリストの要素それぞれに対して何か操作を行い，
結果のリストを返してほしいと思うことがよくある．
上の例の1番目はそれを行う古典的な例を示している：
してほしい操作を行う関数を作り，リストに渡ってmapcarを使う．
関数をデータとして扱えることがどれ程便利なことかは既に見てきた．
多くのプログラミング言語では，
mapcarのようなものに関数を引数として渡せるようになっていたとしても，
それはソースファイルのどこかで予め定義された関数でなければならない．
ただコードの一部でリストの要素それぞれに10を加えたいときでも，
plus_tenとかいう名の関数をそのためだけに定義しなければならないだろう．
λ式を使えば関数そのものを直接参照できる．
Common Lispとそれ以前の方言との大きな違いの一つは，
関数を引数に取れる関数が多数組み込まれていることだ．
あらゆるところで目にするmapcarの次に多く使われるのは，
sortとremove-ifだ．
前者は多目的の整列関数で，リストと述語を取り，
要素のペアをその述語に渡して整列したリストを返す．
> (sort '(1 4 2 5 6 7 3) #'<) (1 2 3 4 5 6 7)
sortの動作を覚えるには，重複のないリストを < で整列させ，
その結果に < を適用したら真が返る，と覚えておけばよい．
さてもしremove-ifがCommon Lispに含まれていなかったら，
これは一番最初に書き加えたいユーティリティだろう．
これは関数とリストを取り，そのリストの要素のうち関数が偽を返すものを全て返す．
> (remove-if #'evenp '(1 2 3 4 5 6 7)) (1 3 5 7)
関数を引数に取る関数の例として，
ここにremove-ifの機能限定版の定義を示す：
(defun our-remove-if (fn lst)
(if (null lst)
nil
(if (funcall fn (car lst))
(our-remove-if fn (cdr lst))
(cons (car lst) (our-remove-if fn (cdr lst))))))
この定義の中でfnにシャープクォートが付いていないことに注意．
関数はデータ・オブジェクトなので，変数は関数を値として普通に保持することができる．
上でやっていることはそれだ．
シャープクォートはシンボルで表される関数（普通defun等で
グローバルに定義されたもの）を参照するときだけしか使わない．
第4章で見るように，関数を引数に取るユーティリティを新しく書くのは
ボトムアップ・プログラミングの重要な要素だ．
Common Lispにはユーティリティがたくさん組み込まれているので，
必要だと思ったものは既に存在しているかもしれない．
しかしsort等の組み込みユーティリティを使うにせよ，
自分で書き加えるにせよ，原則に違いはない．
関数を連結せずに，関数を引数に渡せばいい訳だ．
関数がLispオブジェクトであるせいで，
新しい事態に対処できるように実行中に拡張できるようなプログラムが書ける．
動物の種類を取り，適切に振る舞う関数が書きたいとしよう．
大抵のプログラミング言語では，これを実現する方法はcase文だろう．
Lispでも次のようにして実現できる：
(defun behave (animal)
(case animal
(dog (wag-tail)
(bark))
(rat (scurry)
(squeak))
(cat (rub-legs)
(scratch-carpet))))
新しい動物を追加したいときにはどうしようか？ 新しい動物の追加を計画しているなら， 動物の振る舞いを以下のように定義する方がいいだろう：
(defun behave (animal) (funcall (get animal 'behavior)))
そして個々の動物の振る舞いは， 例えばその名前の属性リストに保存された関数として定義する：
(setf (get 'dog 'behavior)
#'(lambda ()
(wag-tail)
(bark)))
この方法では，新しい動物を追加するには新しい属性を定義しさえすればいい． 関数の書き直しは必要なくなる．
2番目の方法は柔軟だが，動作が遅いように思われる．事実その通りだ．
もし速度が最重要だというのなら属性リストの代わりに構造体を使い，
また特に関数をコンパイルしておくだろう．
（この方法は第foo章で説明する．）
構造体とコンパイル済み関数を使えば，
柔軟なコードでもcase文を使った方と同等かそれを凌ぐ速度が出る．
関数のこのような使い方はオブジェクト指向プログラミングでのメソッドの概念に対応する． 一般的に言って，メソッドとはオブジェクトのプロパティである関数であり， それは正にここで実現したものだ． このモデルに継承を加えればオブジェクト指向プログラミングの要素がみな揃う． 第foo章で見るように，これは驚く程短いコードで実現できる．
オブジェクト指向プログラミングの最大のセールス・ポイントの一つは， それによってプログラムが拡張可能になることだ． この見込みはLispの世界ではそれ程興奮を誘うものではない． ここでは拡張性はいつも当然のものと見なされているからだ． 必要な種類の拡張性が余り継承に頼らずに済むものなら，素のLispでも十分だろう．
Common Lispはレキシカルスコープを持つLispだ．
Schemeはレキシカルスコープを持つLisp方言のうち最も古いもので，
Scheme以前にはダイナミックスコープはLispの特徴的な機能とされていた．
レキシカルスコープとダイナミックスコープとの違いは，
処理系の実装がどのようにフリー変数を扱うかという点だ．
仮引数として現れるか，
変数を束縛する機能を持つletやdo等のオペレータによるかして，
変数として作られたシンボルは，式に束縛されている．
束縛されていないシンボルはフリーであると言われる．
次の例では，スコープが動作に絡んでくる：
(let ((y 7))
(defun scope-test (x)
(list x y)))
このdefun式の中では，xが束縛されていてyはフリーだ．
フリー変数は，あるべき値が明らかでないので興味深い．
束縛変数の値に関しては曖昧なことは何もない
---scope-testが呼ばれたとき，xの値はとにかく引数で渡されたものになる．
しかしyの値はどうあるべきだろう？
この問の答えはそのLisp方言のスコープの扱いによる．
ダイナミックスコープを持つLispでは，
scope-testの実行時のフリー変数の値を見つけるには，
それを呼び出した関数の連鎖を遡る必要がある．
そしてyが束縛されている環境が見つかれば，
その束縛がscope-testで使われているものだ．
見つからなかったら，yのグローバルな値が使われる．
だからダイナミックスコープを持つLispでは，
yの値は呼び出し側の式の中での値になる：
> (let ((y 5))
(scope-test 3))
(3 5)
ダイナミックスコープでは，scope-testが定義された時点で
yが7に束縛されていたことには何の意味もない．
影響があるのは，scope-testが呼ばれたときに
yの値が5だったということだ．
レキシカルスコープを持つLispでは，関数呼び出しの連鎖を遡る代わりに，
関数が定義された時点での周りの環境を遡って調べる．
レキシカルスコープを持つLispでは，上の例のyは
scope-testが定義された時点での束縛を持つだろう．
またCommon Lispでもそうなる：
> (let ((y 5))
(scope-test 3))
(3 7)
ここで，呼び出し時にyを5に束縛したことは返り値に何の影響も持たない．
変数をスペシャル宣言することでダイナミックスコープを持たせることができるが， Common Lispでは普通はレキシカルスコープになる． 一般的に言って，Lispコミュニティはダイナミックスコープの廃止を ほとんど残念に思っていないようだ． 一つには，それが恐ろしく捉えづらいバグを招いたことがある． しかしレキシカルスコープはバグ回避の方法程度のものではない． 次章で見るように，それによって幾つかの新しいプログラミング技法が可能になる．
Common Lispがレキシカルスコープを持つせいで， フリー変数を中に含む関数を定義したときには， 処理系はその関数が定義された時点でのそれらの変数の束縛をコピーして保存しなければならない． 関数と変数束縛の一式のそのような組み合わせは\emph{クロージャ}と呼ばれる． クロージャは多方面の応用において便利なものだと分かるだろう．
クロージャはCommon Lispの中に広く浸透しているので，
それとは意識することさえなく使うことができる．
mapcarにフリー変数を含むλ式をシャープクォートして与える度，
ユーザはクロージャを使っているのだ．
例えば，数のリストを取り，ある数をそれぞれに加える関数を書きたいとしよう．
この関数list+
(defun list+ (lst n)
(mapcar #'(lambda (x) (+ x n))
lst))
が望みの動作をしてくれる：
> (list+ '(1 2 3) 10) (11 12 13)
list+ の中でmapcarに渡される関数をよく見れば，
それが実際クロージャだと分かる．
nのインスタンスはフリーで，その束縛は周りの環境から来ている．
レキシカルスコープの下では，
そのような対応付け関数を使う度にクロージャが作られている
\footnote{ダイナミックスコープの下でも，
mapcarの仮引数がどれもxという名を持たない限り同じ例文が機能するが，
その理由は異なる．}．
AbelsonとSussmanの古典\emph{Structure and Interpretation of Computer Programs}\note{WizardBook}によって奨められたプログラミング・スタイルでは， クロージャはさらに顕著な役を担っている． クロージャはローカルな状態を持った関数であるとされる． この状態を使う例の最も単純なものは次のような状況だ：
(let ((counter 0)) (defun new-id () (incf counter)) (defun reset-id () (setq counter 0)))
これら2個の関数はカウンタとして働く変数を共有している．
1個目はカウンタを1増やしてその値を返し，2個目はカウンタを0にリセットする．
カウンタをグローバル変数とすることで同じことが実現できるが，
この方法ではカウンタは意図しない参照から守られている．
ローカルな状態を持つ関数を返せるのは便利でもある．
例えば，関数make-adder
(defun make-adder (n) #'(lambda (x) (+ x n)))
は数を取り，「呼ばれると引数にその数を加えるクロージャ」を返す． その足し算関数のインスタンスは幾らでも作ることができる：
> (setq add2 (make-adder 2)
add10 (make-adder 10))
#<Interpreted-Function BF162E>
> (funcall add2 5)
7
> (funcall add10 3)
13
make-adderに返されたクロージャでは内部状態が固定されているが，
状態を変化させられるクロージャを作ることもできる．
(defun make-adderb (n)
#'(lambda (x &optional change)
(if change
(setq n x)
(+ x n))))
上の新ヴァージョンのmake-adderが返すクロージャは，
1個の引数で呼ばれたときには古いものと全く同じ動作をする：
> (setq addx (make-adderb 1)) #<Interpreted-Function BF1C66> > (funcall addx 3) 4
しかし新しい足し算関数が非nilの第2引数と共に呼ばれると，
内部にあるnのコピーは第1引数として渡された値にリセットされる：
> (funcall addx 100 t) 100 > (funcall addx 3) 103
同じデータ・オブジェクトを共有するクロージャのグループを返すことさえ可能だ．
第\ref{fig:PrimitivDatebase}図には初歩的データベースを作る関数を示した．
それは連想リスト(db)を取り，それぞれエントリのクエリ，追加，削除を行う
3個のクロージャのリストを返す．
make-dbmsを呼び出す度，
連想リストの自分専用のコピーを内部で共有する新しい関数の組が返される．
> (setq cities (make-dbms '((boston . us) (paris . france)))) (#<Interpreted-Function 8022E7> #<Interpreted-Function 802317> #<Interpreted-Function 802347>)
(defun make-dbms (db)
(list
#'(lambda (key)
(cdr (assoc key db)))
#'(lambda (key val)
(push (cons key val) db)
key)
#'(lambda (key)
(setf db (delete key db :key #'car))
key)))
\caption{3個のクロージャがリストを共有する例．}
データベース内の実際の連想リストは，外からは見えない．
それどころか，それが連想リストなのかどうかも分からない．
しかしそれはcitiesのコンポーネントである関数を通じて到達できる：
> (funcall (car cities) 'boston) US > (funcall (second cities) 'london 'england) LONDON > (funcall (car cities) 'london) ENGLAND
リストのcarを呼ぶのは少し格好悪い．
実際のプログラムでは，アクセス関数は構造体のエントリでもいいかもしれない．
それらを使うとさらに簡潔になるだろう．
データベースは次のような関数
(defun lookup (key db) (funcall (car db) key))
から間接的にアクセスできるようになる．
しかし，クロージャの基本的な動作はそういったチューニングとは無関係だ．
実際のプログラム使われるクロージャとデータ構造は，
make-adderやmake-dbmsで見たものより手の込んだものだろう．
共有されている変数は1個だったが，幾つに増やしてもよく，
それぞれはどのようなデータ構造にも束縛できる．
クロージャはLispの長所のうち顕著で明白なものの一つだ．
Lispプログラムの中には，
努力すれば力の弱いプログラミング言語に翻訳できるものもあるかもしれない．
しかし上のようなクロージャを使うプログラムを翻訳しようとしてみれば，
この抽象化構造がどれ程労力の節約になっているか明らかになるだろう．
後の章ではクロージャをさらに詳細に扱う．
第5章では，それらを使って複合的な関数を作る方法を示す．
第6章では，伝統的データ構造の代わりとしての使用法を見る．
λ式で関数を定義したとき，defunでは分からなかった制限に直面する：
λ式で定義した関数には名前がなく，そのためにそれ自身を参照する方法がない．
このことは，Common Lispでは再帰関数を定義するのにλ式が使えないということだ．
ある関数をリストの要素全てに適用したいときは，
Lispの慣用法のうち最も親しみ深いものを使う：
> (mapcar #'(lambda (x) (+ 2 x))
'(2 5 7 3))
(4 7 9 5)
mapcarの第1引数に再帰関数を与えたいときにはどうすればいいのだろうか？
その関数がdefunで定義されていたら，
ただ関数の名前によってそれを参照すればいい：
> (mapcar #'copy-tree '((a b) (c d e))) ((A B) (C D E))
しかし使う関数が，mapcarの存在する環境から
幾つかの束縛を引き継ぐようなクロージャでなくてはいけないとしよう．
例に挙げたlist+
(defun list+ (lst n)
(mapcar #'(lambda (x) (+ x n))
lst))
ではmapcarへの第1引数 #'(lambda (x) (+ x n))は
list+ 内で定義されていなければいけない．
それはnの束縛を捉えなければいけないからだ．
そこまではいいが，ローカルな束縛を必要とし，
かつ再帰的な関数をmapcarに与えたいとしたらどうだろう？
ローカルな束縛が必要だから，別の場所でdefunで定義された関数は使えない．
また$\lambda$式で再帰関数を定義することはできない．
その関数には自分自身を参照する方法がないからだ．
このジレンマを解決するため，Common Lispにはlabelsが用意されている．
1点の重要な留保を除き，labelsは関数に対する一種のletとして説明できる．
labels式の中の束縛指定部は，それぞれ次のような形になる：
(<名前> <引数> . <本体>)
labels式の中では，
nameは次のような関数と等価な関数を参照する：
(lambda <仮引数> . <本体>)
例を挙げよう：
> (labels ((inc (x) (1+ x)))
(inc 3))
4
しかしletとlabelsには重要な違いがある．
let式の中では，
ある変数の値は同じletで作られた別の変数に依存することはできない．つまり
(let ((x 10) (y x)) ;;誤り y)
として，新しいyの値が新しいxの値を反映することを期待しても駄目なのだ．
それに対し，labels式の中で定義された関数fの本体では，
そこで定義されたどの関数を参照してもいい．
それはf自身でもよく，おかげで再帰関数の定義が可能になっている．
labelsを使ってlist+ に似た関数を書けるが，
こちらではmapcarへの第1引数が再帰関数になっている：
(defun count-instances (obj lsts)
(labels ((instances-in (lst)
(if (consp lst)
(+ (if (eq (car lst) obj) 1 0)
(instances-in (cdr lst)))
0)))
(mapcar #'instances-in lsts)))
この関数は1個のオブジェクトと1個のリストを取り， そのリストの要素内にオブジェクトが何個あったかの回数のリストを返す：
> (count-instances 'a '((a b c) (d a r p a) (d a r) (a a))) (1 2 1 2)
再帰関数とは自分自身を呼び出す関数だ． そして関数呼び出しの後に行うべき作業が残っていなければ， その呼び出しは\emph{末尾再帰}だ． 次の関数は末尾再帰でない．
(defun our-length (lst)
(if (null lst)
0
(1+ (our-length (cdr lst)))))
再帰呼び出しから戻った後，結果を1+ に渡さなければいけないからだ．
しかし次の関数は末尾再帰だ．
(defun our-find-if (fn lst)
(if (funcall fn (car lst))
(car lst)
(our-find-if fn (cdr lst))))
再帰呼び出しの値が即座に返されているからだ．
多くのCommon Lispコンパイラが末尾再帰の関数をループに変換できるので，
末尾再帰の方がいい．
そのようなコンパイラでは，
優美な再帰をソースコード内で使っても実行時に関数呼び出しのオーヴァヘッドは必要ない．
末尾再帰にすると速度は大抵かなり向上するので，
Lispプログラマはどんどん関数を末尾再帰にしようとする．
末尾再帰でない関数もしばしば末尾再帰に変換できることがある．
それには総和変数を使うローカルな関数を埋め込んでやればいい．
ここで総和変数とはそれまでに計算された値を保持するパラメータを指す．
例えばour-lengthは次のように変換できる：
(defun our-length (lst)
(labels ((rec (lst acc)
(if (null lst)
acc
(rec (cdr lst) (1+ acc)))))
(rec lst 0)))
ここでそれまでに読み取ったリストの要素の数は，
第2仮引数accに保持されている．
再帰がリスト末尾まで達したときaccの値がリスト全体の長さになっているので，
それをそのまま返せばいい．
呼び出しのツリーから戻る途中で値を求めていくのでなく，
呼び出しのツリーを下るにつれ値を累積していくことで，
recを末尾再帰に変えることができる．
Common Lispコンパイラの多くが末尾再帰の最適化を行うことができるが， それら全てが始めからそうする設定になっている訳ではない． だから自分の関数を末尾再帰に書き換えたら，ファイルの先頭に
(proclaim '(optimize speed))
と付け足し，努力の成果をコンパイラが確かに活用できるようにするといいかもしれない
\footnote{宣言(optimize speed)は(optimize (speed 3))の
省略形の筈だが，あるCommon Lisp処理系は前者では末尾再帰の最適化をするのに，
後者ではしないことが分かっている．}．
末尾再帰形式と型宣言を与えられると，
現在のCommon LispコンパイラはCと同等か，Cより速いコードを生成できる．
Richard Gabriel\note{Gabriel}による下の例の関数は，
1からnまでの整数の和を返す：
(defun triangle (n)
(labels ((tri (c n)
(declare (type fixnum n c))
(if (zerop n)
c
(tri (the fixnum (+ n c))
(the fixnum (- n 1))))))
(tri 0 n)))
高速なCommon Lispコードはこういう形になる． 始めは関数をこのように書くのは不自然に思えるかもしれない． 始めは関数をとにかく一番自然に思える形で書き， その後必要があれば等価な末尾再帰形式に書き換えるのがいい．
Lispの関数は1個1個でもファイル単位でもコンパイルできる．
トップレベルにdefun式を打ち込むだけだと
> (defun foo (x) (1+ x)) FOO
多くの処理系が作るのは（コンパイルされていない）インタプリタに読み込まれた関数だ．
ある関数がコンパイルされているかどうかは，
それをcompiled-function-pに渡せば分かる：
> (compiled-function-p #'foo) NIL
fooをコンパイルするにはその名前をcompileに与える：
> (compile 'foo) FOO
これはfooの定義をコンパイルし，
評価された関数をコンパイル済みのものに置き換える関数だ\note{compile}．
> (compiled-function-p #'foo) T
コンパイル済みの関数と評価された関数は共にLispのオブジェクトで，
違うのはcompiled-function-pを適用したときの結果だけだ．
関数を文字通りに表記したものもコンパイルできる：
compileは第1引数がコンパイルする関数の名前であることを期待するが，
第1引数にnilを与えると，第2引数で与えられた$\lambda$式をコンパイルする．
> (compile nil '(lambda (x) (+ x 2))) #<Compiled-Function BF55BE>
名前と関数を両方与えると，compileは
defunをコンパイルするような形になる：
> (progn (compile 'bar '(lambda (x) (* x 3))) (compiled-function-p #'bar)) T
プログラミング言語の中にコンパイルの命令があるということは，
プログラムが実行中に新しい関数を作ってコンパイルできるということだ．
しかしcompileを陽に呼ぶのは，
evalを呼ぶのに匹敵する程過激な方法で，同じくらい疑ってかかるべきだ
\footnote{陽にevalを呼ぶのがなぜいけないかは，fooページで説明する．}．
第2.1節で実行時に関数を作るのは頻繁に使われるプログラミング技法だと言ったが，
それはmake-adderに作られた新しいクロージャ等を指しており，
生のリストに対してcompileを呼んで作った関数のことではない．
compileを呼ぶのは頻繁に使われる技法ではない
---その方法は物凄く希だ．
だから不必要に使うのは避けること．
Lispの上に別のプログラミング言語を実装するのでもない限り
（そしてその場合でさえ大抵は），必要なことはマクロを使えば可能だろう．
2種類の関数はcompileに引数として与えることができない．
\textsf{CLtL2}によると（voxページ），
「空でないレキシカル環境においてインタプリタ的に定義された関数」だ．
つまりトップレベルでletを使ってfooを定義すると
> (let ((y 2)) (defun foo (x) (+ x y)))
(compile 'foo)には意味がない
\footnote{このコードをファイルに保存し，ファイルをコンパイルするのは問題ない．
制限は実装上の理由から「インタプリタ的に読み込まれたコード」という点に
対するもので，異なるレキシカル環境で関数を定義することに何も問題はない．}．
また既にコンパイル済みの関数でcompileを呼ぶこともできない．
この状況に関し\textsf{CLtL2}は不吉な示唆をしている．
曰く，「そのときの結果は…不定である．」
Lispコードをコンパイルする方法は，普通，
関数を個別にcompileでコンパイルするのでなく，
ファイル全体をcompile-fileでコンパイルすることだ．
この関数はファイル名を取り，ソースファイルのコンパイル済みのものを造り出す．
ファイル名本体は同じで拡張子が違う，というのが典型的なものだ．
コンパイル済みファイルが読み込まれると，
compiled-function-pはそのファイルで定義された全ての関数に真を返す筈だ．
後の章では，コンパイルの別の効果を使っている：
ある関数が別の関数内で作られ，外側の関数がコンパイルされると，
内側の関数もコンパイルされる．
\textsf{CLtL2}ではこうなるとは明記していないようだが，
ちゃんとした処理系ではこうなる筈と考えていい．
内部の関数のコンパイルの問題は，関数を返す関数を使うと明らかになる．
make-adder（fooページ）がコンパイルされると，
それが返す関数もコンパイルされている：
> (compile 'make-adder) MAKE-ADDER > (compiled-function-p (make-adder 2)) T
後の章で見るように，この事実は埋め込み言語の実装において大変重要だ． 新しいプログラミング言語がコード変換によって実装されているとき， 変換を司るコードがコンパイルされると，それはコンパイル済みコードを生成する． そして新しいプログラミング言語のためのコンパイラでその問題が明らかになる． （簡単な例をbazページで説明した．）
かなり小さい関数を定義したときは，それをインラインでコンパイルしてほしいことがある． そうしないと呼び出し機構に関数自体よりも多くの手間がかかってしまう． 関数を定義して
(defun 50th (lst) (nth 49 lst))
インライン宣言をすると
(proclaim '(inline 50th))
コンパイル済み関数内での50thへの参照には実際の関数呼び出しが要らなくなる．
このとき50thを呼び出す関数を定義してコンパイルすると
(defun foo (lst) (+ (50th lst) 1))
50thのコードはその中にそのまま組み入れられる．
すると最初の所で次のように書いたかのような結果になる：
(defun foo (lst) (+ (nth 49 lst) 1))
インライン関数の欠点は，
50thを定義し直したときにはfooを再コンパイルしなくてはいけないことだ．
そうしないとfooは50thの古い定義を反映したままになってしまう．
インライン関数に対する制限は，マクロに対するものと基本的に同じだ
（第foo章を参照）\note{inline}．
Lispの初期の方言では，関数がリストとして表現されているものがあった． このことはLispプログラムに自分自身でLispプログラムを書き，実行するという 注目すべき能力をもたらした． Common Lispでは，関数はもうリストから作られてはいない\wadash よくできた処理系は関数をネイティブな機械語にコンパイルする． しかしプログラムを書くプログラムをユーザが書くことは依然として可能だ． それはリストがコンパイラに対する入力形式だからだ．
LispプログラムがLispプログラムを書けるということは， どんなに強調しても強調し過ぎにはならない． 特に，この事実はしばしば軽く見られがちだからだ． 熟練Lispユーザでさえ，Lispのこの機能から得られる利点を理解していることは少ない． 例えばLispのマクロがあれ程強力な理由はこれだ． この本で説明されている技法のほとんどが， Lispの式を操作できるプログラムを書ける能力によるものだ．