[ 目次, 前節, 次節, 索引 ]

⟨標的proc, 接続nextで演算子の翻訳⟩
⟨被演算子を評価し引数リストをarglに構成する⟩
⟨与えられた標的と接続で手続き呼出しの翻訳⟩

   要求されたコードはcompile-applicationが生成する. これは作用させるべき手続きをprocに置くコードを作るため, 演算子を, また作用の個々の被演算子を評価するコードを作るため, 被演算子を再帰的に翻訳する. 被演算子に対する命令列は(construct-arglistにより)引数のリストをarglに構成するコードと共に組み合され, 結果の引数リストのコードは, 手続きのコードと( compile-procedure-callが作った)手続き呼出しを実行するコードと組み合される. コードの列を連結するには, envレジスタを(演算子の評価が, 被演算子を評価するのに必要になろうenvを修正するかも知れないので)演算子の評価の前後で, またprocレジスタを(被演算子の列が, 実際の手続き作用に必要になるprocを修正するかも知れないので)引数リストの構成の前後で, 保存しなければならない. continueも手続き呼出しの接続として必要なので, 全体にわたって保存しなければならない.

(define (compile-application exp target linkage)
  (let ((proc-code (compile (operator exp) 'proc 'next))
        (operand-codes
         (map (lambda (operand) (compile operand 'val 'next))
              (operands exp))))
    (preserving '(env continue)
     proc-code
     (preserving '(proc continue)
      (construct-arglist operand-codes)
      (compile-procedure-call target linkage)))))

   引数リストを構成するコードは, 各被演算子をvalへ評価し, その値をargl にためられる引数リストにconsする. 引数はarglに順にconsするので, 引数が結果のリストに最初から最後の順で現れるように, 最後の引数から始め, 最初で終らなければならない. この評価の列を設定するのにarglを空に初期化して命令を浪費する代りに, 最初のコード列に, 最初のarglを作らせる. 従って引数リストの構成の一般形は, 次のようになる:

⟨valを標的に最後の被演算子の翻訳⟩
(assign argl (op list) (reg val))
⟨valを標的にその前の被演算子の翻訳⟩
(assign argl (op cons) (reg val) (reg argl))
...
⟨valを標的に最初の被演算子の翻訳⟩
(assign argl (op cons) (reg val) (reg argl))

   この引数コードの翻訳は, 評価すべき最初の被演算子の特別な扱いとarglと envを異った場所で保存する必要性のため, 幾分巧妙である. construct-arglist手続きは引数として個々の被演算子を評価するコードをとる. 被演算子が全くなければ, 単に命令

(assign argl (const ()))

(define (construct-arglist operand-codes)
  (let ((operand-codes (reverse 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
              (preserving '(env)
               code-to-get-last-arg
               (code-to-get-rest-args
                (cdr operand-codes))))))))

(define (code-to-get-rest-args operand-codes)
  (let ((code-for-next-arg
         (preserving '(argl)
          (car operand-codes)
          (make-instruction-sequence '(val argl) '(argl)
           '((assign argl
              (op cons) (reg val) (reg argl)))))))
    (if (null? (cdr operand-codes))
        code-for-next-arg
        (preserving '(env)
         code-for-next-arg
         (code-to-get-rest-args (cdr operand-codes))))))

手続きの作用

 (test (op primitive-procedure?) (reg proc))
 (branch (label primitive-branch))
compiled-branch
 ⟨与えられた標的と適切な接続で翻訳された手続きに作用させるコード⟩
primitive-branch
 (assign ⟨標的⟩
         (op apply-primitive-procedure)
         (reg proc)
         (reg argl))
 ⟨接続⟩
after-call

(define (compile-procedure-call target linkage)
  (let ((primitive-branch (make-label 'primitive-branch))
        (compiled-branch (make-label 'compiled-branch))
        (after-call (make-label 'after-call)))
    (let ((compiled-linkage
           (if (eq? linkage 'next) after-call linkage)))
      (append-instruction-sequences
       (make-instruction-sequence '(proc) '()
        `((test (op primitive-procedure?) (reg proc))
          (branch (label ,primitive-branch))))
       (parallel-instruction-sequences
        (append-instruction-sequences
         compiled-branch
         (compile-proc-appl target compiled-linkage))
        (append-instruction-sequences
         primitive-branch
         (end-with-linkage linkage
          (make-instruction-sequence '(proc argl)
                                     (list target)
           `((assign ,target
                     (op apply-primitive-procedure)
                     (reg proc)
                     (reg argl)))))))
       after-call))))

翻訳した手続きの作用

 (assign continue (label proc-return))
 (assign val (op compiled-procedure-entry) (reg proc))
 (goto (reg val))
proc-return
 (assign ⟨標的⟩ (reg val))   ; 標的がvalでなければ挿入する
 (goto (label ⟨接続⟩))       ; 接続コード

 (save continue)
 (assign continue (label proc-return))
 (assign val (op compiled-procedure-entry) (reg proc))
 (goto (reg val))
proc-return
 (assign ⟨標的⟩ (reg val))   ; 標的がvalでなければ挿入する
 (restore continue)
 (goto (reg continue))           ; 接続コード

   実際, 標的がvalでなければ, それはまさにわれわれの翻訳系が生成するコードである.39 しかし, 通常は標的はvalである. (翻訳系が別のレジスタを指定する唯一の時は, 演算子の評価をprocに標的する時である.) そこで手続きの結果は, 標的レジスタに直接置き, それをコピーする特別の場所に戻る必要はない. その代り, 手続きが呼出し側の接続が指定した場所に直接「戻る」ようにcontinueを設定してコードを単純化する:

⟨接続のためcontinue⟩を設定
(assign val (op compiled-procedure-entry) (reg proc))
(goto (reg val))

(assign continue (label ⟨接続⟩))
(assign val (op compiled-procedure-entry) (reg proc))
(goto (reg val))

(assign val (op compiled-procedure-entry) (reg proc))
(goto (reg val))

   そうではなく, return接続とval標的を持つ手続き呼出しを, 上に示したvalでない標的と同様に扱ったとしよう. これは末尾再帰を破壊する. システムはどの式にも同じ値を与えるであろう. しかし手続きを呼び出す度に, continueを退避し, (不要な)退避をし戻す呼出しの後, 戻るであろう. これらの余分な退避は手続きの呼出しの入れ子の間にたまる.40

   compile-proc-applは, 呼出しの標的がvalかどうか, 接続がreturn かどうかによる四つの場合を考慮して, 上の手続き作用のコードを生成する. 手続き本体の実行がレジスタをどのようにも変更し得るので, 命令列は, すべてのレジスタを修正するように宣言していることを見よう.41 また標的valと接続returnの場合のコード列はcontinue を必要とするよう宣言されていることにも注意しよう: continueは二命令列で陽には使われないが, 翻訳した手続きに入った時, continueが正しい値を持っていることに注意しなければならない.

(define (compile-proc-appl target linkage)
  (cond ((and (eq? target 'val) (not (eq? linkage 'return)))
         (make-instruction-sequence '(proc) all-regs
           `((assign continue (label ,linkage))
             (assign val (op compiled-procedure-entry)
                         (reg proc))
             (goto (reg val)))))
        ((and (not (eq? target 'val))
              (not (eq? linkage 'return)))
         (let ((proc-return (make-label 'proc-return)))
           (make-instruction-sequence '(proc) all-regs
            `((assign continue (label ,proc-return))
              (assign val (op compiled-procedure-entry)
                          (reg proc))
              (goto (reg val))
              ,proc-return
              (assign ,target (reg val))
              (goto (label ,linkage))))))
        ((and (eq? target 'val) (eq? linkage 'return))
         (make-instruction-sequence '(proc continue) all-regs
          '((assign val (op compiled-procedure-entry)
                        (reg proc))
            (goto (reg val)))))
        ((and (not (eq? target 'val)) (eq? linkage 'return))
         (error "return linkage, target not val -- COMPILE"
                target))))

39 実際, return接続を要求する唯一の場所は, 手続きの翻訳中であり, 手続きは値をvalに返すのが約束だから, 標的がvalでなく, 接続がreturnなら, エラーとする.

40 翻訳系に 末尾再帰的コードを生成させるのは直截な考えのように見えるかも知れない. しかしCやPascalを含め, 通常の言語の翻訳系はそうしない. それ故これらの言語は反復的プロセスを手続き呼出しだけを使っては表現出来ない. これらの言語で 末尾再帰が困難なのは, 手続き引数と局所変数と戻り番地を格納するのにスタックを使うからである. 本書に述べるSchemeの実装は, 引数と変数を, ごみ集めされるメモリーに入れる. 変数と引数にスタックを使う理由は, 言語でそれ以外にはいらないごみ集めの必要性を避け, その方が遥かに効率的と一般に信じられているためである. 巧妙なLisp翻訳系は, 実際末尾再帰を破壊せずに, 引数にスタックを使うことが出来る. (記述については, Hanson 1990参照) そもそもスタック割当てがごみ集めより実際にずっと効率的かどうかには議論があり, 細部は計算機アーキテクチャの細かい点に依存するようだ. (この論点の反対意見は Appel 1987および MillerとRozas 1994参照)

41 変数 all-regsはすべてのレジスタ名のリストに束縛されている:

(define all-regs '(env proc val argl continue))

[ 目次, 前節, 次節, 索引 ]