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> 

あ、ひげぽんさんのコメントに_最適化が抑制_って書いてありますな。成程。