nptclのブログ

Common Lisp処理系nptの開発メモです。https://github.com/nptcl/npt

lambda式で関数生成しない場合を考える

Common Lisp npt

最近知ったのですが、lambda式はクロージャーが値を捕捉していない場合は 実行するたびにいちいち関数生成なんてしないで、 グローバルの関数を返却すればいいんだそうです。

どういうことかというと、例えば次の関数を考えてみます。

(defun aaa ()
  (lambda () :hello))

関数aaaはlambda式により関数を返却しますが、 内側の関数は:helloを返すだけでクロージャーによる値の捕捉はありません。
こう言う場合は、同じ関数オブジェクトを返却しても良いという事です。

sbclで次のコードを実行してみます。

(format t "~S~%" (aaa))
(format t "~S~%" (aaa))
(format t "~S~%" (aaa))

実行結果は次の通り。

#<FUNCTION (LAMBDA () :IN AAA) {22473ABB}>
#<FUNCTION (LAMBDA () :IN AAA) {22473ABB}>
#<FUNCTION (LAMBDA () :IN AAA) {22473ABB}>

返却された関数のアドレスが全て22473ABBになっており、 3つとも全部同一なオブジェクトであることが分かります。
つまり、

(eq (aaa) (aaa))
  -> T

です。
しかしクロージャーが値を持った場合はどうでしょうか。
次の文をsbclで実行します。

(defun bbb (x)
  (lambda () x))

(format t "~S~%" (bbb 10))
(format t "~S~%" (bbb 10))
(format t "~S~%" (bbb 10))

結果は次の通り。

#<CLOSURE (LAMBDA () :IN BBB) {10018A818B}>
#<CLOSURE (LAMBDA () :IN BBB) {10018A9E2B}>
#<CLOSURE (LAMBDA () :IN BBB) {10018AAE0B}>

表記がFUNCTIONではなくCLOSUREになっています。
しかもアドレスが全てバラバラです。
eqの判定もしてみましょう。

(eq (bbb 10) (bbb 10))
  -> NIL

そうか、こういう事ができるのか。
clispではこうなりませんでしたが、cclでは同じような結果になりました。

nptでは当然こうなっていませんでした。
だって知らなかったんですもの。
同じことやりたいなと思いましたが、 結局これをやったところで何が嬉しいのか。

最適化を実現した場合は、最初の一回だけ関数生成を行い、 二回目からはキャッシュを返却するようになります。
デザインパターンと呼ばれるものにシングルトンってのがあった覚えがありますが、 それに近いことをします。
いまオブジェクト指向は全然関係ありませんけどね。

それで関数をいちいち生成しないので、その分の処理時間が短く heap領域も節約できます。

短所は新しい中間言語の命令が必要なことくらいでしょうか。
手間なのは、中間の命令を増やすのでcompile-file関数による コンパイルにも対応させなければならないということ。
しかもどれもこれも結構めんどくさい。

でも頑張ってやってみました。
せっかくなのでoptimizeの値でON/OFFを切り替えられるようにしました。
optimizeのspeedが0でキャッシュOFFにします。
1以上ではONであり、デフォルトの動作もONです。

例文をあげます。
ここからはnpt専用のコードです。

(defun aaa-on ()
  (declare (optimize (speed 1)))
  (lambda () :hello))

(defun aaa-off ()
  (declare (optimize (speed 0)))
  (lambda () :hello))

(format t "ON: ~S~%" (aaa-on))
(format t "ON: ~S~%" (aaa-on))
(format t "ON: ~S~%" (aaa-on))
(format t "ON: ~S~%" (eq (aaa-on) (aaa-on)))

(format t "OFF: ~S~%" (aaa-off))
(format t "OFF: ~S~%" (aaa-off))
(format t "OFF: ~S~%" (aaa-off))
(format t "OFF: ~S~%" (eq (aaa-off) (aaa-off)))

実行結果は下記の通り。

ON: #<FUNCTION LAMBDA #x801286e90>
ON: #<FUNCTION LAMBDA #x801286e90>
ON: #<FUNCTION LAMBDA #x801286e90>
ON: T
OFF: #<FUNCTION LAMBDA #x80128bfc0>
OFF: #<FUNCTION LAMBDA #x80128ccd0>
OFF: #<FUNCTION LAMBDA #x80128d9e0>
OFF: NIL

ついでに速度も見てみます。

(defmacro test-macro (n)
  `(let ((ret 0))
     (dotimes (i ,n)
       (incf ret (funcall (if (evenp i)
                            (lambda (x) (+ x x))
                            (lambda (x) (* x x))) i)))
     ret))

(defun test-on (n)
  (declare (optimize (speed 1)))
  (test-macro n))

(defun test-off (n)
  (declare (optimize (speed 0)))
  (test-macro n))

(defparameter value 1000000)
(time (format t "*** ON: ~A~%" (test-on value)))
(time (format t "*** OFF: ~A~%" (test-off value)))

実行結果は下記の通り。

*** ON: 166667166665500000
Real-Time      1779669
Run-Time       54500057
Heap-Space     47995832
Heap-Count     2999705
*** OFF: 166667166665500000
Real-Time      1968749
Run-Time       56500049
Heap-Space     191979576
Heap-Count     7998697

全てにおいて改善されました。
時間はそれほど短縮されてはいませんが、 heapオブジェクトの生成回数と確保容量が半分以下になっています。
これはとてもいいのではないでしょうか。

最後に。
この考え方は別のプログラミング言語の話題で知りました。
何だったか忘れましたけどC#だったかな？
もしかしたら専門家の間では当たり前なテクニックなのかもしれませんが、 自分はプロでも専門家ではないしIT？みたいなのにも 関わってないので全然知りませんでした。

Lispでは末尾最適化というものが有名だと思います。
これもどうしていいのかわからなかったからnptでは実装してないんですよね。
でも最近Schemeを少し勉強してみたら、仕様書に末尾最適化のことが載っていました。
そのうち、これを参考にnptでも実装できたらいいなと思います。
色々なことに興味を持って勉強すると新しい発見があって面白いですね。

【追記】仕様書にちゃんと記載してありました

http://www.lispworks.com/documentation/HyperSpec/Body/s_fn.htm
https://nptcl.github.io/npt-japanese/docs/ansicl/5.3.function-special.html
https://nptcl.github.io/npt-japanese/md/ansicl/5.3.function-special.html

If name is a lambda expression, then a lexical closure is returned. In situations where a closure over the same set of bindings might be produced more than once, the various resulting closures might or might not be eq.

だそうです。
翻訳作業してて初めて気が付きました。

【追記・ここまで】