ひげぽんに助け舟を出そうとして遭難しかけたので備忘録。

ひげぽん OSとか作っちゃうかMona- - SICPを読もう - (3) 1章 - 手続きによる抽象の構築(1-30ページ)
再帰的なのはすぐ解ける。
;(略)
反復が分からない。

traceすればいいじゃん、と思って、実例をこさえようとして、手元にscheme implementationがないことに気がつき、さくっとgaucheをインストールして....あれ?traceがない!?

そう。実は私がschemeをちゃんと使ってたのはもう20年前。その頃はすでに人様が用意していた環境で作業(というか授業)していたので、traceが標準でないことなどすでにGCの彼方にすっとんでいたのであった。

ざくっと検索した結果、

(use slib)
(require 'trace)

すればよいということが判明。しかし....

gosh> (use slib)
*** ERROR: Compile Error: cannot find file "/usr/local/share/slib/require" to load
"(stdin)":1:(use slib)

Stack Trace:
_______________________________________
  0  (slib:load (in-vicinity (library-vicinity) "require"))
        At line 388 of "/usr/local/share/gauche/0.8.6/lib/slib.scm"

な、なんだってー!?そう。slibはgoshをはじめ、scheme implementationとは別売り、もとい別配布なのであった。FreeBSDのportsをまさぐると、slib-gaucheというportsが別にある。なーんだ。

FreeBSDの方はそれでいいが、OS Xはどうする?portsを解析。ふむふむ。MITからファイルを取って来て、それを/usr/local/で荷解きしてから、最後におまじないをかければいいのね。

cd ~ # 一応ここではhome directoryにdownload
curl -O http://swissnet.ai.mit.edu/ftpdir/scm/slib3a3.tar.gz # fetchでもwgetでも何でもOK
cd /usr/local
sudo tar zxvf ~/slib3a3.tar.gz # /usr/local/slib に荷解き
sudo gosh -uslib -E"require 'new-catalog" -Eexit # slibを初期化

で、めでたく

gosh> (require 'trace)
#t
gosh> (use slib)
#<undef>
gosh> (require 'trace)
#t

とtraceが使えるようになればもうこちらのもの。

gosh> (define (fact n) (if (<= n 1) 1 (* n (fact (- n 1)))))
fact
gosh> (fact 10)
3628800
gosh> (trace fact)
#<closure (debug:trace-procedure debug:trace-procedure)>
gosh> (fact 10)
CALL fact 10
 CALL fact 9
  CALL fact 8
   CALL fact 7
    CALL fact 6
    RETN fact 720
   RETN fact 5040
  RETN fact 40320
 RETN fact 362880
RETN fact 3628800
3628800

めでたしめでたし。やれやれ、shiroさんには聞けないよなあ、中年面さげて;)

で、ひげぽんへの助け舟。まずは再帰版をtraceしてみる。

ggosh>  
(define (f n)
  (cond ((< n 3) n)
        (else (+ (f (- n 1))
                 (* 2 (f (- n 2)))
                 (* 3 (f (- n 3)))))))
f
gosh> (f 5)
25
gosh> (trace f)
#<closure (debug:trace-procedure debug:trace-procedure)>
gosh> (f 5)
CALL f 5
 CALL f 4
  CALL f 3
   CALL f 2
   RETN f 2
   CALL f 1
   RETN f 1
   CALL f 0
   RETN f 0
  RETN f 4
  CALL f 2
  RETN f 2
  CALL f 1
  RETN f 1
 RETN f 11
 CALL f 3
  CALL f 2
  RETN f 2
  CALL f 1
  RETN f 1
  CALL f 0
  RETN f 0
 RETN f 4
 CALL f 2
 RETN f 2
RETN f 25
25

何度も行ったり来たりというのがわかると思う。で、繰り返し版(といっても、実は末尾再帰しているのだけど)もtraceしてみたいのだが、そのままだとtraceできないので、こうする。

gosh> 
(define (iter a b c count)
    (cond ((= count 0) c)
          ((= count 1) b)
          (else (iter (+ a (* 2 b) (* 3 c)) a b (- count 1)))))
iter
gosh> (define (f-iter n) (iter 2 1 0 n))
f-iter
gosh> (trace iter)
#<closure (debug:trace-procedure debug:trace-procedure)>
gosh> (f-iter 5)
CALL iter 2 1 0 5
 CALL iter 4 2 1 4
  CALL iter 11 4 2 3
   CALL iter 25 11 4 2
    CALL iter 59 25 11 1
    RETN iter 25
   RETN iter 25
  RETN iter 25
 RETN iter 25
RETN iter 25
25

これで何とはなしにわかってきたのではないか。

ちなみに、関数型言語でいちばんキツいのは、何の事はない、printf debugがお手軽にできないことだったりする。再帰はむしろ慣れれば楽ちんで、私はCでもPerlでも結構手軽に使う。上のようなことはperlなら

warn $retval;
return $retval;

とかで済ませてしまうだろう。もちろん本格的なtraceもdebuggerを使ったり、Hook::LexWrapとかを使えば簡単にできるが、この程度であればそれすら虫一匹始末するのにガトリング砲を使うような大げささに思えてしまう。

とりあえずtraceを覚えておこう。これはcheatにはならないだろう。だって学校でSICP(というか、現地では単に"Sussman"と呼んでた記憶が)を教科書に教える場合にだって、一応用意してあったのだから。20年前ですら。

なんか久しぶりに普段使わない筋肉を使った感じ。

Dan the Undusting Schemer