lexical変数のことが分かったような気がする

lexical変数の設計を色々やってみて、最終的に落ち着いたものについて話します。
たぶんこれが正解に近いのかと。

少しでも速度改善したいと、clispのdisassembleでも見てみようかと思ったときのことです。
速度測定によく使っていたmk.eastasian.lispのextract-loop関数を出力してみました。

> (disassemble 'extract-loop)

Disassembly of function EXTRACT-LOOP
2 required arguments
0 optional arguments
No rest parameter
No keyword parameters
18 byte-code instructions:
0     L0
0     (LOAD&PUSH 1)
1     (LOAD&PUSH 3)
2     (FUNCALL 1)
4     (NV-TO-STACK 2)
6     (LOAD&JMPIFNOT 0 L19)
9     (LOAD&PUSH 1)
10    (LOAD&PUSH 4)
11    (JSR&PUSH L0)
13    (T)
14    L14
14    (PUSH)
15    (STACK-TO-MV 2)
17    (SKIP&RET 5)
19    L19
19    (LOAD&PUSH 4)
20    (NIL)
21    (JMP L14)
NIL

うん、わからない。
ちなみに元のコードは下記の通り。

(defun extract-loop (x call)
  (multiple-value-bind (ret check) (funcall call x)
    (if (null check)
      (values x nil)
      (values (extract-loop ret call) t))))

何がわかるかということもなく、ただdisassembleの出力は短いなーくらいしか思いませんでしたが、気になることがひとつ。
それは、lexicalの変数名がまるで出てこないということです。
たぶん(LOAD&PUSH 4)みたいに、4と書かれている数値が lexical変数なのではないかと思いました。

そうか、lexical変数はそのsymbol自体には何も意味がないのか。
今までそんなこと考えたことが無かったのですが、 symbolから値を直接取り出すのはspecial変数だけです。
例えば、

(let ((a 10) (b 20) (c 30))
  (+ a b c))

という文があったとして、 lexical変数であるa, b, cはどのような名前でも問題ないということです。
仮に<1>, <2>, <3>という名前に置き換えてしまいましょう。

(let ((<1> 10) (<2> 20) (<3> 30))
  (+ <1> <2> <3>))

変数をshadowする場合にはsymbolに意味を持ちますが、意味があるのはeval実行時であり、 functionになってしまえば関係ありません。
つまり、

(let ((a 10))
  (let ((a a)
        (b 20))
    (+ a b)))

という文は、evalの初段では次のように書き変わります。

(let ((<1> 10))
  (let ((<2> <1>)
        (<3> 20))
    (+ <2> <3>)))

番号に書き換えることで見えてくるものがありました。
それは、lexical変数の領域を配列として一括で確保できるということです。
今まではletが出てくるたびにlexical変数の領域を確保し、 letが終了したときにlexical変数の領域を解放していました。
letが2つあれば2回の領域確保と解放処理が生じます。
では上記の例文を次のように書き換えたらどうでしょうか。

(LET (<1> <2> <3>)
  (setq <1> 10)
  (setq <2> <1>)
  (setq <3> 20)
  (+ <2> <3>))

letがたった1つになりました。
letではなくLETと大文字で書いたのは特殊な命令であることを明示したかったからです。
局所的に領域確保と解放を行わなくていいので、例えばloopの時に高速化が期待できます。
次に下記の文を考えます。

(dotimes (i 10)
  (let ((x (* i i)))
    (push x list)))

こんな書き方をする人はあまりいないかもしれませんが、マクロが展開する場合もあります。
例ではループの中にlet文が入っているので、実行するたびに領域の確保と解放処理が生じます。
次のように書き換えるとどうなるでしょうか。

(LET (<1> <2>)
  (dotimes (<1> 10)
    (setq <2> (* <1> <1>))
    (push <2> list)))

この書き換えは非常に効率的です。
ただしこれができるのはlexical変数のみであり、 special変数では無理です。
上記のdotimesの例は、special変数の場合ならいちいち領域の確保と解放を10回繰り返すことになります。
最適化がうまい具合にやってくれるかもしれませんが。

そうだったのかー。
lexical変数ってこういうものだったんですね。
今になってようやく理解できた気がします。
なぜeval関数が空のlexical環境からスタートするかも分かりました。
makunboundでlexical変数をUnboundに設定できないのも分かります。
修正前のnptは、わざわざ手動で空のlexical環境を作っていたんですよね。

lexical変数はclosureに引っ掛けることができるだけであって special変数より手間だけがかかるものだと思っていたのですが、今回のような書き換えができるならlexical変数の方が高速です。

もう少し話を進めると、lexical変数以外にもfletとlabelsもいっしょに一つの配列で確保してしまいます。
tagbodyとblockのタグっぽいものも一緒に格納しましょう（詳細はこちらclosureには何が保存されるのか - nptclのブログ）。
lexical変数とflet/lablesは別で確保、みたいなことはせず、 1つの配列に変数と関数をゴチャゴチャに混ぜることになります。
ではその配列を確保するタイミングはいつになるでしょうか？

考えたのですが、たぶん関数を作成した時ですね。
nptでいうなら、lambda式とmacro専用のlambda式実行時。
さらにevalの一番最初にも領域確保するタイミングを設けます。
closureは2つの配列の境界に位置しているため、「以前の配列の何番目を、新しい関数の配列の何番目に格納する」みたいな処理になるのかと思います。

では以上のことを考慮した場合、次のコードを考えます。

(defun test (n)
  (let ((a 0) (sum 0))
    (flet ((aaa (x) (1+ x)))
      (block result
        (tagbody
          loop
          (when (< n a)
            (return-from result sum))
          (incf sum a)
          (setq a (aaa a))
          (go loop))))))

lexical変数, flet, block, tagが全部lexicalの領域に格納されるので、次のように書き換えられます。

(defun test (n)
  (LET ((<1> n)
        (<2> 0)
        (<3> 0)
        (<4> (lambda (x) (1+ x)))
        (<5> (system::block-name 'result))
        (<6> (system::tag-name 'loop)))
    (block <5>
      (tagbody
        <6>
        (when (< <1> <2>)
          (return-from <5> <3>))
        (incf <3> <2>)
        (setq <2> (<4> <2>))
        (go <6>)))))

closureはどうなるでしょうか？
例えば下記のコードを考えます。

(let ((a 10))
  (setq *call*
        (lambda ()
          (* 123 a))))

書き換えると次のようになります。

(LET ((<1> 10))
  (setq *call*
        (LET (([1] <1>))
          (lambda ()
            (* 123 [1])))))

上記では、<1>とは違ったlexical領域である [1]に値を渡すようにしてclosureを実現しています。
関数が作成されるたびに、新しいlexical領域が作成され、 closureはlexical変数だけではなく、flet, block, tagのオブジェクトも含めて新たな番号が付与されることになります。