昨晩のエントリを受けて

末尾再帰と再帰でどうなるか、に興味しんしん。
単純な例で以下の差を見てみた。

(define (list-item-count-recursive l)
(if (null? l)
0
(+ 1 (list-item-count-recursive (cdr l))))

(define (list-item-count l)
(define (list-item-count-inner n l)
(if (null? l)
n
(list-item-count-inner (+ n 1) (cdr l))))
(list-item-count-inner 0 l))

こいつらを define して disasm してみたらどうなるか

gosh> (disasm list-item-count-recur)
main_code (name=list-item-count-recur, code=0x8149ee0, size=13, const=1, stack=10):
args: #f
0 LREF0 ; l
1 BNNULL 5 ; (null? l)
3 CONSTI(0)
4 RET
5 PRE-CALL(1) 11
7 LREF0 ; l
8 CDR-PUSH ; (cdr l)
9 GREF-CALL(1) #; (list-item-count-recur (cdr l))
11 NUMADDI(1) ; (+ 1 (list-item-count-recur (cdr l)))
12 RET
#
gosh> (disasm list-item-count)
main_code (name=list-item-count, code=0x814ef00, size=17, const=0, stack=16):
args: #f
0 CONSTI-PUSH(0)
1 LREF0-PUSH ; l
2 LOCAL-ENV(2) ; (list-item-count-inner 0 l)
3 LREF0 ; l
4 BNNULL 8 ; (null? l)
6 LREF1 ; n
7 RET
8 LREF1 ; n
9 NUMADDI(1) ; (+ n 1)
10 PUSH
11 LREF0 ; l
12 CDR-PUSH ; (cdr l)
13 LOCAL-ENV-JUMP(1) 3 ; (list-item-count-inner (+ n 1) (cdr l))
15 RET
16 RET
#
gosh>

たしか Gauche は 3imp で言う所の stack-based なソレだったはずなんですが、3imp 読みはソコまで辿り着いてないだよなぁ。LREF の Reading Gauche な解説を見るに LREF 関連なインストラクションは lexical address なソレに見える。引数は基本 push で云々、に見えます。

ざっくり見るに確かに末尾再帰は繰り返しになっていますね。繰り返しの方が中間コードが長いのもなんとなく面白い。

しかし Reading Gauche ヤりつつ、レベル的に自分がこれ、ってのも微妙ッス。
追記

SICP からパクッてこんなのも試してみた

gosh> (define (accumulate op init seq) (if (null? seq) init (op (car seq) (accumulate op init (cdr seq)))))
accumulate
gosh> (disasm accumulate)
main_code (name=accumulate, code=0x814efa0, size=19, const=1, stack=14):
args: #f
0 LREF0 ; seq
1 BNNULL 5 ; (null? seq)
3 LREF1 ; init
4 RET
5 LREF0 ; seq
6 CAR-PUSH ; (car seq)
7 PRE-CALL(3) 15
9 LREF2-PUSH ; op
10 LREF1-PUSH ; init
11 LREF0 ; seq
12 CDR-PUSH ; (cdr seq)
13 GREF-CALL(3) #; (accumulate op init (cdr seq))
15 PUSH
16 LREF2 ; op
17 TAIL-CALL(2) ; (op (car seq) (accumulate op init (cdr s ...
18 RET
#
gosh>

LREF2-PUSH とか最適化な痕跡が見える。これ、0 だの 1 だのが逆に見えるのは引数の先頭から push されるから、なのでしょうか。