sbclのインタプリタでスタックを溢れさせてみた

再帰関数を末尾再帰にすると、コンパイル時に最適化されてJUMP命令になるからスタックを消費しなくていいよね。と言いたいのですが。。。

末尾再帰，継続，アクタ，コルーチン : セマンティックウェブ・ダイアリー

SBCLだと、あれれ？？となります。。。

末尾再帰関数をコンパイルしていないのにスタックが溢れない？？

こちらは末尾再帰関数です。

(defun test-tail (n)
  (when (eq (mod n 1000) 0)
	(print n))
  (test-tail (1+ n)))

ロードして、関数を呼び出します。

$ sbcl --load test-tail.lisp
This is SBCL 2.0.1.debian, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.

SBCL is free software, provided as is, with absolutely no warranty.
It is mostly in the public domain; some portions are provided under
BSD-style licenses.  See the CREDITS and COPYING files in the
distribution for more information.
* (test-tail 0)

関数は末尾再帰になっていますが、コンパイルしていないのでスタックが溢れてエラーで止まることを期待する。。。のですが、再帰が止まることがありません。

REPLの中でコンパイルしていたのか！

なぜかといえば、以下のように関数がコンパイルさているからです。

* (compiled-function-p #'test-tail)
T

REPLでの関数定義なのにコンパイルされるのですね。もう少し調べてみると。。。

#:g1: SBCLのインタプリタが強化されたらしい

SBCLはCCLと並んでコンパイラ指向の処理系として知られています。
(中略)
そんなSBCLですが、1.3.0から従来のSB-EVALに代って、SB-FASTEVALというのが入ったみたいです。

なるほど。。。そういうことなのですね。。。

SBCLのREPLをインタプリタ動作にして試してみる

では前出の記事を参考に、インタプリタ動作するSBCLのREPLで、コンパイルされていない末尾再帰関数でスタックが溢れるか検証してみます。

$ sbcl --load test-tail.lisp
This is SBCL 2.2.3.201-6e19f8c7a, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.

SBCL is free software, provided as is, with absolutely no warranty.
It is mostly in the public domain; some portions are provided under
BSD-style licenses.  See the CREDITS and COPYING files in the
distribution for more information.
* (compiled-function-p #'test-tail)
NIL

* (test-tail 0)
0
1000
2000
3000
4000
5000
INFO: Control stack guard page unprotected
Control stack guard page temporarily disabled: proceed with caution
6000
debugger invoked on a SB-KERNEL::CONTROL-STACK-EXHAUSTED in thread
#<THREAD "main thread" RUNNING {1001630003}>:
  Control stack exhausted (no more space for function call frames).
This is probably due to heavily nested or infinitely recursive function
calls, or a tail call that SBCL cannot or has not optimized away.

PROCEED WITH CAUTION.

Type HELP for debugger help, or (SB-EXT:EXIT) to exit from SBCL.

restarts (invokable by number or by possibly-abbreviated name):
  0: [ABORT] Exit debugger, returning to top level.

(SB-KERNEL::CONTROL-STACK-EXHAUSTED-ERROR)

以上のように、めでたく？？6000から7000の間でスタックが枯渇しました。

ついでに(compile 'test-tail)したところ、再帰が止まることなく処理が継続することも確認できました。

最後に

わざわざインタプリタ動作せて検証するのも大変なので記事にしてみました。何かのお役に立てば幸いです。ありがとうございました。