Hatena::Groupcadr

わだばLisperになる このページをアンテナに追加 RSSフィード

2004 | 12 |
2005 | 01 | 02 | 07 | 10 | 11 |
2006 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 11 |

2011-06-29

逆もまたしかり

| 21:35 | 逆もまたしかり - わだばLisperになる を含むブックマーク はてなブックマーク - 逆もまたしかり - わだばLisperになる

クヌース先生の「goto文を用いた構造的プログラミング」を読んでいて末尾呼び出しはgotoに直せ、また逆も正しい、との記述を読んで、そういえばあまり逆方向のことは考えないなと思ったので試してみました。

単に試してみただけで特にオチはありません…。

試してみる

(loop :for i :from 0 :below 100 :count i)

マクロの展開系を関数にしたようなgogo

(defun gogo ()
  (declare (optimize (safety 0) (speed 3)))
  (block nil
    (let ((i 0))
      (declare (type (and real number) i))
      (let ((loop-sum 0))
        (declare (type fixnum loop-sum))
        (tagbody
         NEXT-LOOP
           (when (>= i '100)
             (go END-LOOP))
           (when i
             (setq loop-sum (1+ loop-sum)))
           (setq i (1+ i))
           (go NEXT-LOOP)
         END-LOOP
           (return-from nil loop-sum))))))

(gogo)
;=> 100

disassembleしてみる

; disassembly for GOGO
;        XOR ECX, ECX ; no-arg-parsing entry point
;        XOR EDX, EDX
;        JMP L1
; L0:    ADD RDX, 8
;        ADD RCX, 8
; L1:    CMP RCX, 800
;        JL L0
;        MOV RSP, RBP
;        CLC
;        POP RBP
;        RET

上のgogo(loopマクロの展開形)をそのまま再帰呼び出しに変換したようなrecrec

(defun recrec ()
  (declare (optimize (safety 0) (speed 3)))
  (block nil
    (let ((i 0))
      (declare (type (and real number) i))
      (let ((loop-sum 0))
        (declare (type fixnum loop-sum))
        (labels ((NEXT-LOOP ()
                   (when (>= i '100)
                     (END-LOOP))
                   (when i
                     (setq loop-sum (1+ loop-sum)))
                   (setq i (1+ i))
                   (NEXT-LOOP))
                 (END-LOOP ()
                   (return-from nil loop-sum)))
          (NEXT-LOOP))))))

(recrec)
;=> 100

disassembleしてみる

; disassembly for RECREC
;       XOR ECX, ECX ; no-arg-parsing entry point
;       XOR EDX, EDX
;       JMP L2
; L0:   CMP RCX, 800
;       JL L1
;       MOV RSP, RBP
;       CLC
;       POP RBP
;       RET
; L1:   ADD RDX, 8
;       ADD RCX, 8
; L2:   JMP L0

ジャンプの順番と回数が多少違いますが、gogoもrecrecも大体同じものになりました。(まあ、最適化してるからなんですけど…)

めでたしめでたし。