Scheme - 翻訳系の概観(preserving機構によるスタック使用の最適化)

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Mavericks - Apple(OS)
• Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
• Scheme (プログラミング言語)
• MIT/GNU Scheme (処理系)

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の5(レジスタ計算機での計算)、5.5(翻訳系)、翻訳系の概観、5.5.5(翻訳したコードの例)、問題 5.37.を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs

問題 5.37.

常にsaveとrestore演算を生成するようにpreservingを修正。

コード(BBEdit)

sample.scm

(definne (preserving regs seq1 seq2)
  (if (null? regs)
      (append-instruction-squences seq1 seq2)
      (let ((first-reg (car regs)))
        (preserving (cdr regs)
         (make-instruction-sequence
          (list-union (list first-reg)
                      (register-needed seq1))
          (list-difference (registers-modified seq1)
                           (list first-reg))
          (append '((save ,first-reg))
                  (statements seq1)
                  '((restore ,first-reg))))))))

式、(+ n 1)の翻訳。

常にsaveとrestore演算を生成するpreserving機構の場合。

  (save continue)
  (assign proc (op lookup-variable-value) (const +) (reg env))
  (save proc) ;; 異なる
  (save env) ;; 異なる
  (save continue) ;; 異なる
  (assign val (const 1))
  (restore continue) ;; 異なる
  (assign argl (op list) (reg val))
  (restore env) ;; 異なる
  (save argl) ;; 異なる
  (save continue) ;; 異なる
  (assign val (op lookup-variable-value) (const n) (reg env))
  (restore continue) ;; 異なる
  (restore argl) ;; 異なる
  (assign argl (op cons) (reg val) (reg argl))
  (restore proc) ;; 異なる
  (restore continue)
  (test (op primitive-procedure?) (reg proc))
  (branch (label primitive-branch))
compiled-branch
  (assign val (op compiled-procedure-entry) (reg proc))
  (goto (reg val))
primitive-branch
  (assign val (op apply-priitive-procedure) (reg proc) (reg argl))
after-call
  (goto (reg continue))

元の、スタック使用を最適化するpreserving機構の場合。

  (save continue)
  (assign proc (op lookup-variable-value) (const +) (reg env))
  (assign val (const 1))
  (assign argl (op list) (reg val))
  (assign val (op lookup-variable-value) (const n) (reg env))
  (assign argl (op cons) (reg val) (reg argl))
  (restore continue)
  (test (op primitive-procedure? proc))
  (branch (label primitive-procedure))
compiled-branch
  (assign val (op compiled-procedure-entry) (reg proc))
  (goto (reg val))
primitive-branch
  (assign val (op apply-primitive-procedure) (reg proc) (reg argl))
after-call
  (goto (reg continue))

単純な式の翻訳でも多くの不要なスタック演算が見つかった。