Three Implementation Models for Scheme

とある方からの勧めで、「Three Implementation Models for Scheme」を読み始めました。
180ページもあって「うげー」という感じだったのですが、1ページあたりの文字の量が少なく、
また、内容もソースが多くて読みやすかったのでむしろ「ほへー」という感じでした。

4章まで読み終わったので、適当なまとめを書いておきます。

  • Schemeは関数と継続がfirst class objectで末尾呼出、代入のサポートも必要
    => 従来のコンパイラ/インタプリタの手法が使いにくい
  • 全てをヒープにおくことによってコンパイラとVMを作ることができる
    => ただし、動作が遅い
  • スタックを使えば速い(変数などもスタックに入れる)
    => first classの関数、継続、末尾呼出、代入はそのままではサポートできない
  • スタックを継続オブジェクトに丸ごとコピーすることで継続を実装
    => もちろん遅いが、継続の作成はそう頻繁には起こらないと仮定すれば大丈夫
  • Display Closureに関数とその自由変数の値(のコピー)を持たせてヒープに置く
    => これにより関数をfirst classにできる
  • 以上の手法を使うと、継続と関数の持つ変数の値はコピーであるため、代入に対応できない
    => set!を使う変数だけを特別扱いして対処(MLの参照型のようにする)
  • set!を使う変数は値をヒープにもち、変数自体にはヒープへの参照を持たせる
    => 変数のコピーも同じ領域を指すので代入に対応できる
  • 末尾呼出の最適化はスタックの使い方を工夫すればできる
  • あと色々工夫すればさらに速くできる

たぶんこんな感じです。
英語が良く分からなくてもソースさえ読めれば結構分かるので、
英語が苦手な方にもお勧め。

One Response to “Three Implementation Models for Scheme”

  1. Lisp/処理系

    主にソースが公開されてるものとかを インタプリタ、全体 CAMPUS LIsP MiniScheme TinyScheme AM-Schem…

Leave a Reply