さかもとのブログ

つらつらと

SICP演習問題5.21

SICP

いままではif文の判定(2つしか分岐がないもの)をやっていたので，少し苦戦した．

a

今回の問題は

(define (count-leaves tree)
  (cond [(null? tree) 0]
        [(not (pair? tree)) 1]
        [else (+ (count-leaves (car tree))
                 (count-leaves (cdr tree)))]))

をレジスタ計算機で実装すること．
解答は

(define count-leaves-machine1
  (make-machine
   '(continue val1 val2 tree)
   (list (list 'car car) (list 'cdr cdr) (list 'pair? pair?)
         (list 'null? null?) (list '+ +))
   '((assign continue (label count-done))
    count-leaves-loop
     (test (op null?) (reg tree))
     (branch (label null))
     (test (op pair?) (reg tree))
     (branch (label pair))
     (assign val1 (const 1))
     (goto (reg continue))
    null
     (assign val1 (const 0))
     (goto (reg continue))
    pair
     (save continue)
     (assign continue (label car-loop))
     (save tree)
     (assign tree (op car) (reg tree))
     (goto (label count-leaves-loop))
    car-loop
     (restore tree)
     (assign tree (op cdr) (reg tree))
     (assign continue (label cdr-loop))
     (save val1)
     (goto (label count-leaves-loop))
    cdr-loop
     (assign val2 (reg val1))
     (restore val1)
     (restore continue)
     (assign val1 (op +) (reg val1) (reg val2))
     (goto (reg continue))
    count-done)))
実行
gosh> (set-register-contents! count-leaves-machine1 'tree '((1 2) (3 4 (5))))
done
gosh> (start count-leaves-machine1)
done
gosh> (get-register-contents count-leaves-machine1 'val1)
5
b

問題は

;; b
(define (count-leaves tree)
  (define (count-iter tree n)
    (cond [(null? tree) n]
          [(not (pair? tree)) (+ n 1)]
          [else (count-iter (cdr tree)
                            (count-iter (car tree) n))]))
  (count-iter tree 0))

treeのcdrをどうするのかわからなかったので，参考にした．

(define count-leaves-machine2
  (make-machine
   '(tree n val continue)
   (list (list 'null? null?) (list 'pair? pair?)
         (list '+ +) (list 'cdr cdr) (list 'car car))
   '((assign n (const 0))
     (assign continue (label count-done))
    count-iter
     (test (op null?) (reg tree))
     (branch (label null))
     (test (op pair?) (reg tree))
     (branch (label pair))
     (assign val (op +) (reg n) (const 1))
     (goto (reg continue))
    null
     (assign val (reg n))
     (goto (reg continue))
    pair
     (save continue)
     (assign continue (label car-iter))
     (save tree)
     (assign tree (op car) (reg tree))
     (goto (label count-iter))
    car-iter
     (restore tree)
     (assign tree (op cdr) (reg tree))
     (assign n (reg val))
     (assign continue (label cdr-iter))
     (goto (label count-iter))
    cdr-iter
     (restore continue)
     (goto (reg continue))
    count-done)))
実行
gosh> (set-register-contents! count-leaves-machine2 'tree '(3 (1 2) (3 (4) 5)))
done
gosh> (start count-leaves-machine2)
done
gosh> (get-register-contents count-leaves-machine2 'val)
6