問題5.22

問題5.22 – SICP（計算機プログラムの構造と解釈）その272

2009年10月29日

p149 の "問題3.12" の append と append! のレジスタ計算機を作る。

`append`

(define (append x y)
  (if (null? x)
      y
      (cons (car x) (append (cdr x) y))))

(define append-machine
  (make-machine
    '(continue lis1 lis2 lis-result cons-tmp)
    (list (list 'null? null?) (list 'cons cons) (list 'car car) (list 'cdr cdr))
    '(start
       (assign continue (label append-done))
    append-loop
       (test (op null?) (reg lis1))
       (branch (label null))
       (save continue)
       (assign continue (label after-append))
       (save lis1)
       (assign lis1 (op cdr) (reg lis1))
       (goto (label append-loop))
    null
       (assign lis-result (reg lis2))
       (goto (reg continue))
    after-append
       (restore lis1)
       (restore continue)
       (assign cons-tmp (op car) (reg lis1))
       (assign lis-result (op cons) (reg cons-tmp) (reg lis-result))
       (goto (reg continue))
    append-done)))

実行結果

(set-register-contents! append-machine 'lis1 '(a b))
(set-register-contents! append-machine 'lis2 '(c d))
(start append-machine)
(get-register-contents append-machine 'lis-result)
gosh> (a b c d)

`append!`

(define (append! x y)
  (set-cdr! (last-pair x) y)
  x)

(define (last-pair x)
  (if (null? (cdr x))
      x
      (last-pair (cdr x))))

(define append!-machine
  (make-machine
    '(continue lis1 lis2 cdr-tmp)
    (list (list 'set-cdr! set-cdr!) (list 'null? null?) (list 'cdr cdr))
    '(start
       (assign continue (label append!-done))
       (save lis1)
    append!-loop
       (assign cdr-tmp (op cdr) (reg lis1))
       (test (op null?) (reg cdr-tmp))
       (branch (label null))
       (assign lis1 (op cdr) (reg lis1))
       (goto (label append!-loop))
    null
       (assign lis1 (op set-cdr!) (reg lis1) (reg lis2))
       (goto (reg continue))
    append!-done
       (restore lis1)
    )))

実行結果

(set-register-contents! append!-machine 'lis1 '(a b))
(set-register-contents! append!-machine 'lis2 '(c d))
(start append!-machine)
(get-register-contents append!-machine 'lis1)
gosh> (a b c d)

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

posted with amazlet at 08.11.07

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

Amazon.co.jp で詳細を見る