問題5.36 – SICP(計算機プログラムの構造と解釈)その287

問題5.36

コンパイラは右から左へと被演算子を評価していく。(5.5.3 組み合せの翻訳)

以下は (+ x y) をコンパイルした結果。
被演算子 y の探索が先にきている。

(env)
(env proc argl continue val)
  (assign proc (op lookup-variable-value) (const +) (reg env))
  (assign val (op lookup-variable-value) (const y) (reg env))
  (assign argl (op list) (reg val))
  (assign val (op lookup-variable-value) (const x) (reg env))
  (assign argl (op cons) (reg val) (reg argl))
  (test (op primitive-procedure?) (reg proc))
  (branch (label primitive-branch1))
compiled-branch2
  (assign continue (label after-call3))
  (assign val (op compiled-procedure-entry) (reg proc))
  (goto (reg val))
primitive-branch1
  (assign val (op apply-primitive-procedure) (reg proc) (reg argl))
after-call3

これを、左から右への評価順序に変更するには、コンパイル時に reverse される被演算子コードを実行時に reverse するように変更する。

(define (construct-arglist operand-codes)
  (let ((operand-codes operand-codes))
       (if (null? operand-codes)
           (make-instruction-sequence '() '(argl)
                                      '((assign argl (const ()))))
           (let ((code-to-get-last-arg
                   (append-instruction-sequences
                     (car operand-codes)
                     (make-instruction-sequence '(val) '(argl)
                                                '((assign argl (op list) (reg val)))))))
                (if (null? (cdr operand-codes))
                    code-to-get-last-arg
                    (tack-on-instrunction-sequence
                      (preserving '(env)
                                  code-to-get-last-arg
                                  (code-to-get-rest-args
                                    (cdr operand-codes)))
                      (make-instruction-sequence '() '()
                                               '((assign argl (op reverse) (reg argl))))))))))

以下は (+ x y) をコンパイルした結果。
被演算子 x の探索が先にきている。
実行時に reverse が呼び出されるため効率はこちらの方が落る。

(env)
(env proc argl continue val)
  (assign proc (op lookup-variable-value) (const +) (reg env))
  (assign val (op lookup-variable-value) (const x) (reg env))
  (assign argl (op list) (reg val))
  (assign val (op lookup-variable-value) (const y) (reg env))
  (assign argl (op cons) (reg val) (reg argl))
  (assign argl (op reverse) (reg argl))
  (test (op primitive-procedure?) (reg proc))
  (branch (label primitive-branch1))
compiled-branch2
  (assign continue (label after-call3))
  (assign val (op compiled-procedure-entry) (reg proc))
  (goto (reg val))
primitive-branch1
  (assign val (op apply-primitive-procedure) (reg proc) (reg argl))
after-call3
計算機プログラムの構造と解釈
ジェラルド・ジェイ サスマン ジュリー サスマン ハロルド エイブルソン
ピアソンエデュケーション
売り上げランキング: 6542
«
»