Serendip

Web Studio

問題5.21 b. カウンタを陽に持つ再帰的 count-leaves

(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))

2つある再帰のうち1つは末尾再帰であるため "問題5.21a" のレジスタ計算機と比べて再帰呼び出しの為の入り口のラベルが1つ減っている。

(define count-leaves-machine-b
  (make-machine
    '(continue tree n 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 n (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))
       (save continue)
       (assign continue (label count-iter-with-car))
       (save tree)
       (assign tree (op cdr) (reg tree))
       (goto (label count-leaves-loop))
    null
       (assign val (reg n))
       (goto (reg continue))
    not-pair
       (assign val (op +) (reg n) (const 1))
       (goto (reg continue))
    count-iter-with-car
       (restore tree)
       (restore continue)
       (assign tree (op car) (reg tree))
       (assign n (reg val))
       (goto (label count-leaves-loop))
    count-leaves-done)))

実行結果

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

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

posted with amazlet at 08.11.07

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

Amazon.co.jp で詳細を見る