letrec とか相互再帰とか
どっかで見た、と思っていた例はプログラミング言語 Scheme でした。以下。
(letrec ((even? (lambda (x) (or (= x 0) (odd? (- x 1))))) (odd? (lambda (x) (and (not (= x 0)) (even? (- x 1)))))) (list (even? 20) (odd? 20)))
これを disasm してみたらどうなるか。
gosh> (disasm (lambda () (letrec ((even? (lambda (x) (or (= x 0) (odd? (- x 1))))) (odd? (lambda (x) (and (not (= x 0)) (even? (- x 1)))))) (list (even? 20) (odd? 20))) )) main_code (name=#f, code=0x814bea0, size=23, const=1, stack=18): args: #f 0 LOCAL-ENV-CLOSURES(1) (#<lambda 0>); (letrec ((even? (lambda (x) (or (= x 0) ... 2 PRE-CALL(1) 16 4 CONSTI-PUSH(20) 5 LOCAL-ENV(1) ; (lambda (x) (or (= x 0) (odd? (- x 1)))) 6 LREF0 ; x 7 BNUMNEI(0) 10 ; (= x 0) 9 RET 10 LREF0 ; x 11 NUMADDI(-1) ; (- x 1) 12 PUSH 13 LREF10 ; odd? 14 LOCAL-ENV-TAIL-CALL(1) ; (odd? (- x 1)) 15 RET 16 PUSH-PRE-CALL(1) 21 18 CONSTI-PUSH(20) 19 LREF0 ; odd? 20 LOCAL-ENV-CALL(1) ; (odd? 20) 21 LIST(2) ; (list (even? 20) (odd? 20)) 22 RET internal_closure_0 (name=odd?, code=0x8153eb0, size=18, const=0 stack=8): args: #f 0 LREF0-PUSH ; x 1 CONSTI(0) 2 NUMEQ2 ; (= x 0) 3 NOT ; (not (= x 0)) 4 RF 5 LREF0 ; x 6 NUMADDI(-1) ; (- x 1) 7 PUSH-LOCAL-ENV(1) ; (lambda (x) (or (= x 0) (odd? (- x 1)))) 8 LREF0 ; x 9 BNUMNEI(0) 12 ; (= x 0) 11 RET 12 LREF0 ; x 13 NUMADDI(-1) ; (- x 1) 14 PUSH 15 LREF20 ; odd? 16 TAIL-CALL(1) ; (odd? (- x 1)) 17 RET #<undef> gosh>
むむむ。なんだこれは。一応 LOCAL-ENV-CLOSURES は使ってますが、これも最適化具合が相当に激しい模様。
あらら?
ひげぽんさんからご教示頂いた -fno-inline オプション使ったら出力が違うな。以下が gosh -fno-inline で disasm した結果です。
gosh> (disasm (lambda () (letrec ((even? (lambda (x) (or (= x 0) (odd? (- x 1))))) (odd? (lambda (x) (and (not (= x 0)) (even? (- x 1)))))) (list (even? 20) (odd? 20))) )) main_code (name=#f, code=0x8144f40, size=15, const=2, stack=17): args: #f 0 LOCAL-ENV-CLOSURES(2) (#<lambda 0>#<lambda 1>); (letrec ((even? (lambda (x) (or (= x 0) ... 2 PRE-CALL(1) 7 4 CONSTI-PUSH(20) 5 LREF1 ; even? 6 CALL(1) ; (even? 20) 7 PUSH-PRE-CALL(1) 12 9 CONSTI-PUSH(20) 10 LREF0 ; odd? 11 CALL(1) ; (odd? 20) 12 PUSH-GREF-TAIL-CALL(2) #<identifier user#list>; (list (even? 20) (odd? 20)) 14 RET internal_closure_1 (name=odd?, code=0x814bea0, size=21, const=3 stack=18): args: #f 0 PRE-CALL(1) 10 2 PRE-CALL(2) 8 4 LREF0-PUSH ; x 5 CONSTI-PUSH(0) 6 GREF-CALL(2) #<identifier user#=>; (= x 0) 8 PUSH-GREF-CALL(1) #<identifier user#not>; (not (= x 0)) 10 RF 11 PRE-CALL(2) 17 13 LREF0-PUSH ; x 14 CONSTI-PUSH(1) 15 GREF-CALL(2) #<identifier user#->; (- x 1) 17 PUSH 18 LREF11 ; even? 19 TAIL-CALL(1) ; (even? (- x 1)) 20 RET internal_closure_0 (name=even?, code=0x8153f00, size=17, const=2 stack=12): args: #f 0 PRE-CALL(2) 6 2 LREF0-PUSH ; x 3 CONSTI-PUSH(0) 4 GREF-CALL(2) #<identifier user#=>; (= x 0) 6 RT 7 PRE-CALL(2) 13 9 LREF0-PUSH ; x 10 CONSTI-PUSH(1) 11 GREF-CALL(2) #<identifier user#->; (- x 1) 13 PUSH 14 LREF10 ; odd? 15 TAIL-CALL(1) ; (odd? (- x 1)) 16 RET #<undef> gosh>
あ、ひげぽんさんのコメントに_最適化が抑制_って書いてありますな。成程。