Scheme - 翻訳系の概観(特殊目的計算機とスタック演算、翻訳系の性能と改良)

計算機プログラムの構造と解釈
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.7(翻訳したコードと評価器のインターフェース)、解釈と翻訳、問題 5.45-b.を解いてみる。

その他参考書籍

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

問題 5.45-b.

翻訳系で翻訳したものと、特殊目的のを比較してみる。

翻訳系で翻訳したコード。

コード(BBEdit)

sample.scm

(load "./eval.scm")
(load "./compiler5.44.scm")

(print-compiled
(compile
'(define (factorial n)
   (if (= n 1)
       1
       (* (factorial (- n 1)) n)))
 'next
 'val
 '()) 
)

入出力結果(Terminal, REPL(Read, Eval, Print, Loop))

$ scheme
MIT/GNU Scheme running under MacOSX
Type `^C' (control-C) followed by `H' to obtain information about interrupts.

Copyright (C) 2011 Massachusetts Institute of Technology
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Image saved on Saturday October 26, 2013 at 11:02:50 PM
  Release 9.1.1 || Microcode 15.3 || Runtime 15.7 || SF 4.41 || LIAR/C 4.118
  Edwin 3.116

1 ]=> (load "./sample.scm")

;Loading "./temp.scm"...
;  Loading "./eval.scm"... done
;  Loading "./compiler5.44.scm"... done

(env)
(val next)
  (assign val (op make-compiled-procedure) (label entry2) (reg env))
  (goto (label after-lambda1))
entry2
  (assign env (op compiled-procedure-env) (reg proc))
  (assign env (op extend-environment) (const (n)) (reg argl) (reg env))
  (assign arg1 (op lexical-address-lookup) (const (0 0)) (reg env))
  (save arg1)
  (assign arg2 (const 1))
  (restore arg1)
  (assign val (op =) (reg arg1) (reg arg2))
  (test (op false?) (reg val))
  (branch (label false-branch4))
true-branch5
  (assign val (const 1))
  (goto (reg continue))
false-branch4
  (save continue)
  (assign proc (op lookup-variable-value) (const factorial) (reg env))
  (assign arg1 (op lexical-address-lookup) (const (0 0)) (reg env))
  (save arg1)
  (assign arg2 (const 1))
  (restore arg1)
  (assign val (op -) (reg arg1) (reg arg2))
  (assign argl (op list) (reg val))
  (test (op primitive-procedure?) (reg proc))
  (branch (label primitive-branch8))
compiled-branch7
  (assign continue (label proc-return9))
  (assign val (op compiled-procedure-entry) (reg proc))
  (goto (reg val))
proc-return9
  (assign arg1 (reg val))
  (goto (label after-call6))
primitive-branch8
  (assign arg1 (op apply-primitive-procedure) (reg proc) (reg argl))
after-call6
  (save arg1)
  (assign arg2 (op lexical-address-lookup) (const (0 0)) (reg env))
  (restore arg1)
  (assign val (op *) (reg arg1) (reg arg2))
  (restore continue)
  (goto (reg continue))
after-if3
after-lambda1
  (perform (op define-variable!) (const factorial) (reg val) (reg env))
  (assign next (const ok))
  (goto (label val))
;... done
;Value: done

1 ]=> ^D
End of input stream reached.
Moriturus te saluto.
$

特殊目的の階乗計算との違いを並べてみる。

1. 特殊目的の階乗計算機は、被演算子のリストの構成(argl, arg1, arg2)についてのスタック演算(退避、回復)がない。
2. 特殊目的の階乗計算機は環境についてのスタック演算(退避、回復)がない。

1について、性能において、手で加工した版に近づくようなコードを生成するのを支援するような翻訳系の改良ができそう。

具体的には、被演算子のリストの各要素が、環境を変更するかどうかを判定するようにし、変更しない場合は他の要素のスタック演算(退避、回復)を省略するようにする。

上記のコードで省略出来るスタック演算の部分。

;; entry2ラベルとfalse-branch4ラベル
  ;; この部分のarg1は退避する必要がない
  (save arg1)
  (assign arg2 (const 1))
  ;; 退避してないのでこの回復も必要なくなるる。よっtスタック演算を減らすことが出来る。
  (restore arg1)