Serendip

Web Studio

問題5.21 a. 再帰的 count-leaves

p62 の count-leaves をアセンブラで実装する。

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

p305 の図5.12 Fibonacci 数を計算する計算機の制御器を参考にして作った。

(define count-leaves-machine-a
  (make-machine
    '(continue tree val val-tmp tmp)
    (list (list '+ +) (list 'pair? pair?) (list 'null? null?) (list 'not not) (list 'car car) (list 'cdr cdr))
    '(start
       (assign continue (label count-leaves-done))
       (assign val (const 0))
    count-leaves-loop
       (test (op null?) (reg tree)) ;; tree が null
       (branch (label null))
       (assign tmp (op pair?) (reg tree))
       (test (op not) (reg tmp)) ;; tree がペアでない
       (branch (label not-pair))
       ;; (count-leaves (car tree)) を実行するように設定
       (save continue)
       (assign continue (label count-leaves-with-car))
       (save tree) ;; tree を退避
       (assign tree (op car) (reg tree)) ;; tree を (car tree) に変える
       (goto (label count-leaves-loop)) ;; 再帰呼び出しを実行
    null
       (assign val (const 0))
       (goto (reg continue))
    not-pair
       (assign val (const 1))
       (goto (reg continue))
    count-leaves-with-car
       (restore tree)
       (restore continue)
       ;; (count-leaves (cdr tree)) を実行するように設定
       (assign tree (op cdr) (reg tree))
       (save continue)
       (assign continue (label count-leaves-with-cdr))
       (save val) ;; (count-leaves (car tree)) を退避
       (goto (label count-leaves-loop))
    count-leaves-with-cdr
       (assign val-tmp (reg val))
       (restore val)
       (restore continue)
       (assign val (op +) (reg val) (reg val-tmp))
       (goto (reg continue))
    count-leaves-done)))

実行結果

(define x (cons (list 1 2) (list 3 4)))
(set-register-contents! count-leaves-machine-a 'tree (list x x))
(start count-leaves-machine-a)
(get-register-contents count-leaves-machine-a 'val)
gosh> 8

計算機プログラムの構造と解釈

posted with amazlet at 08.11.07

ジェラルド・ジェイ サスマン ジュリー サスマン ハロルド エイブルソン
ピアソンエデュケーション
売り上げランキング: 6542

Amazon.co.jp で詳細を見る