第178回 素人くさいSICP読書会（at 三田某所）

event
  • 会場提供ありがとうございました
  • 参加者はついに2名。記録更新
  • 理論上はこれ以上減りようがない
  • Common Lispの人は風邪だったそうです。お大事に
  • 参加者が何人だろうが最後まで問題をやり抜くだけですよ
  • 問題5.12
  • Haskell Nightのあと、無性にコードが書きたくなって夜中に書き上げたやつ
  • 基本的にはassembleが吐くinstsを変形していくだけ
  • 長いんで第二倉庫に貼った→ここ
  • 実行結果はこんな感じ↓

instructions: ((assign val (reg n)) (assign val (op +) (reg val) (reg n)) (assign n (reg val)) (assign continue (label afterfib-n-2)) (assign n (op -) (reg n) (const 2)) (assign n (op -) (reg n) (const 1)) (assign continue (label afterfib-n-1)) (assign continue (label fib-done)) (test (op <) (reg n) (const 2)) (branch (label immediate-answer)) (goto (reg continue)) (goto (label fib-loop)) (save val) (save continue) (save n) (restore continue) (restore val) (restore n))

label registers: (continue)

stacked registers: (val continue n)

assign sources: ((val ((op +) (reg val) (reg n)) (reg n)) (n ((op -) (reg n) (const 1)) ((op -) (reg n) (const 2)) (reg val)) (continue (label fib-done) (label afterfib-n-1) (label afterfib-n-2)))
done

  • 問題5.13
  • 引っかけ問題。問題5.12と関係あるように見えて、実は関係ない
  • 最初、5.12の情報を使おうとしてうまくいかず
  • なぜか。5.12の情報はassembleが終わらないと得られないが、assembleの過程で既にレジスタが必要になるため
  • 問題文の「命令のアセンブリ中に，初めて見る度に，レジスタを割り当てる」が最大のヒント
  • 答えは、make-machineのレジスター関連の部分を削除して、make-new-machineの中のlookup-registerを以下のように書き換えるだけ
(define (lookup-register name)
  (let ((val (assoc name register-table)))
    (if val
        (cadr val)
        (begin (allocate-register name)
               (cadr (assoc name register-table))))))
  • 問題5.14
  • 基本的には本文のコードを写経して動かしてみるだけの問題
  • こんなコードを用意↓
(define fact-machine
  (make-machine
   '(n val continue)
   (list (list '= =) (list '- -) (list '* *))
    '(
      (perform (op initialize-stack))
       中略
      (perform (op print-stack-statistics)))))

(define (test-fact-til n)
  (define (iter count)
    (if (> count n) 'done
        (begin
          (set-register-contents! fact-machine 'n count)
          (display (list 'n '= count))
          (start fact-machine)
          (newline)
          (iter (+ count 1)))))
  (iter 2))
  • 動かすとこんな感じ↓
(test-fact-til 6)

(n = 2)
(total-pushes = 2 maximum-depth = 2)
(n = 3)
(total-pushes = 4 maximum-depth = 4)
(n = 4)
(total-pushes = 6 maximum-depth = 6)
(n = 5)
(total-pushes = 8 maximum-depth = 8)
(n = 6)
(total-pushes = 10 maximum-depth = 10)
done
  • total-pushesとmaximum-depthの値は一般には異なるけど、factは単純にガーッと積んでガーッと取ってくるだけなんで、両者の値は一致する
  • すなわち「(n - 1) * 2」
  • 1日で3問も進んだ。近年まれに見る進捗具合
  • 来週はもうちょっと来てほしいなあ