情報科学実験II資料 (2)
仕様説明

田浦

8/10/98

言語仕様

演習で実装する言語はSchemeのsubsetで, 大体Schemeから以下のものを取り除 いたものである.(注)

また, GCや動的なtype check等, さしあたって(レイトレを動かすために)必要 でないものは, 余力がある人のためのオプションとする.

実際には, とりあえず上のようなあまりpowerfulとはいえない仕様にしながら も, 授業で扱う枠組(CPS)は, 少しの変更でset!, さらには call-with-current-continuationまでをも扱えてしまうものである.

さて, 実装する言語は二つのlayerからなる. 一つはcompilerを極力単純化す るための本当に必要最小限の機能を持つ, ``Min-Scheme''(または ``Min-SchemeFix'')というlayerで, その上にもう少しだけrichな構文を備え た``Mini-Scheme''(または``Mini-SchemeFix'')である. Mini-XXXXは簡単な 構文上の置き換えによって, Min-XXXXに変換可能な言語である. XXXXと XXXXFixの違いは, それが自由変数を持つ関 数(局所関数の定義)をゆるすかどうかの違いで, XXXXFixはそれがあるおかげで非常にrichな 言語になる(おもしろいことに実装上の手間はほとんど変らない).

Min-Schemeの文法

Expr = Id 
     | Constant 
     | (if Expr Expr Expr) 
     | (let (Bind*) Expr) 
     | (Primsym Expr*)     ; primitive call
     | (Expr Expr*)        ; user-defined functions
Bind = (Id Expr)           ; let-bind
Definition = (define Id Expr) 
     | (define (Id Id*) Expr*) ; toplevel definition
Constant = Integer | Float | Boolean | '()
Primsym = +-two | --two | >>-two | <<-two 
        | <-two | >-two | <=-two | >=-two | =-two | eq?
        | heap | rref | rset!

Mini-Scheme (Min-Scheme + Syntax Sugars)

さて, Min-Schemeの仕様は本当に必要最小限なものであり, 不便な点が多 い. 例えば良く使うものとしては, condがない. 実際にはこれは ifの入れ子として実現できる. 他にも任意個の引数を受けとる足し算: +が使いたければ, これもまた2引数の足し算+-twoを入れ子にすれば良 い. このように, 多くの構文が簡単なsource → sourceの構文的 な変換で実現できる. このような, 本質的ではないがプログラマにとっての便 利を良くする構文を, 通常, syntax sugarと呼んでいる. それに対して, そうでないものをとりあえず, essential syntaxと呼んでおこ う. Compilerを作る際にessential syntaxの数をできるだけ少なくして, 多く の機能をsyntax sugarを使って実現すれば, compilerの複雑な部分(最適化や コード生成部)をほとんど複雑にしないまま, richな構文を実現することがで きる. (注)

以下に, Min-Schemeの構文を元にして, 簡単なsyntax sugarとして実現できる 構文をあげる.

何をprimitiveとするかの判断基準について

Compilerがどの演算をprimitiveとしてsupportすべきは, 絶対的な解答がある わけではない. むしろそれはtarget machineの持つ命令setに依存している. 例えばもしtarget machineがかけ算命令をsupportしていれば, compilerがか け算をprimitiveとして持つことは十分に合理的である. 逆にもし, 任意bit数 のshift命令がなければ, shift命令すらprimitiveとしないことも考えられる.

したがってその辺は, compiler担当者およびCPU担当者の間で十分情報交換お よび議論を行なった上で, 決めて欲しい. 例えば,

等や, それらを組み合わせた方法がある.

以下に, そのような議論が必要と思われるprimitiveを列挙する.

(注:) 最後の, 動的にsizeが決まる配列の生成はコンパイラの中にprimitive として入ってはいない(heapは固定長のデータの生成に限られる)ので, これは後からアセンブリで実現された関数として実現するのが良い.

Min-Schemeに足りないもの-lambda closure tex2html_wrap_inline252

概要

さて, Min-Schemeにはlambda closureというものがない. そしてそれは Min-Schemeに単純なsyntax sugarを加えて実現できるものではない(考えてみ よ).

実際のところこれで``Scheme compilerの作り方''とするのはどうも気が引け る. Compilerの実装,という観点から見て, lambda closureをsupportする言語 とそうでない言語の違いは何かというと, 前者は,

自由変数を持つ関数を許している
点にある. いいかえれば局所関数定義を許しすようなprogramming言語があれ ば, 表面的にlambda closureをsupportしていなくても, compilerの作りとい う観点からは同じことである.

このことをもう少し詳しく説明してみよう. 例えば, 局所関数定義を許さない, C言語を例にとってみる. C言語では, local変数の値は全て今の関数が起動さ れてからその関数内で代入された値である. その関数の外で代入され, 現在も 値がそこに残っていることが保証されたlocal変数というものは存在しない. 一方, Scheme, ML, Smalltalkなどの言語ではそうではない. 例えばSchemeで は,

(define (make-adder x)
  (lambda (y) (+ x y)))
の, 関数(lambda (y) (+ x y))において, xという変数は, この lambda式が起動されてからbindされるわけではない. xはこのlambda式 が起動されるずっと前にbindされて以来, その値を未来永劫保持しているので ある. MLでもlambda式と全く同様の, fnというconstructが存在するが, 別の書き方として,
fun make_adder (x : int) =
    let fun a y = x + y
    in a
    end;
のような書き方もある. これは表面的にはlambda closureを使っていないが, 中で局所的に定義される関数aの中で, その関数が起動される以前から bindされている変数xを読みにいくという点で, 同じ問題を抱えている. Implementationの観点からは, lambda式は, 上のように局所的な関数に名前を わざわざつける手間を省くための簡便な構文にすぎず, 本質は自由変数を持つ 局所的な関数が定義できるところにある. Smalltalkにも, block式という, lambda式と同じことをする構文がある.

さて, このことがimplementationに与える影響は何かというと, SchemeやMLで は, 関数のcanonicalな表現として,

関数のコード(のaddress) + 自由変数の値の組
をとらなくてはいけない, ということである. Cのようにlocal変数の値が全て 起動時およびその後に定まるような言語では, 関数は, 関数のコードの addressで表現しておけば足りる. 例えばCで,
int f (x)
{
    printf ("f's address is %x", f);
}
とした時にでてくるものは, fの命令列が書かれているcodeのaddressで ある.
int apply (f, x)
    int (* f)(); int x;
{
    return f (x);
}
とした時に, compilerは最終的に, fのaddressに制御を移そうとする (gcc -Sしてみよ).

しかし関数が自由変数を持つかも知れない言語ではそうはいかず, 関数は自由 変数の値を保持しておかねばならない. つまり, 関数の正体はrecordであり, そのrecordの中身は, 先頭がcodeのaddress, それ以降に自由変数の値が羅列 されているものである.(注)

(define (make-adder x)
  (lambda (y) (+ x y)))
で起こることは大体以下のようなことである(下では, { . . . > }で, . . . を要素とする配列を表すこととしている.
int * make_adder_code (fv, x)
{
    /* allocate new record on heap */
    return new { anonymous_0, x };
}

int anonymous_0 (fv, y)
{
    int x = fv [1];
    return x + y;
}

Min-SchemeFix

さて, 今から言語にlambda closureを導入しよう. 前述したように, lambda closureという構文自体は, 本質的ではなく, 自由変数を含んだ局所関数が定 義できるところが本質的であった. そこで我々の言語にも局所関数が定義でき る機構を, 新たなessential syntaxとして導入しよう. これが導入できれば, lambda closureはただのsyntax sugarとして実現できる. これを Min-SchemeFix と呼ぶことにする. Min-SchemeFix の構文は,

Expr = Id 
     | Constant 
     | (if Expr Expr Expr) 
     | (let (Bind*) Expr) 
     | (fix (Fbind*) Expr) 
     | (Primsym Expr*)     ; primitive call
     | (Expr Expr*)        ; user-defined functions
Bind = (Id Expr)           ; let-bind
Fbind = (Id (Id*) Expr)    ; fix-bind
Definition = (define Id Expr) 
     | (define (Id Id*) Expr*) ; toplevel definition
Constant = Integer | Float | Boolean | '()
Primsym = +-two | --two | >>-two | <<-two 
        | <-two | >-two | <=-two | >=-two | =-two | eq?
        | heap | rref | rset!
で, 加わったのは, fixという文である. Fixは局所関数を導入し てbodyを実行するという意味で, letと似ているが, 導入されるのは関 数に限られる(MLのlet fun ...に非常に近い). 例えば,
(fix ((even? (x) (if (= x 0) #t (odd? (- x 1))))
      (odd? (x) (if (= x 0) #f (even? (- x 1)))))
  (even? 10))
は正しいfix式である.

Mini-SchemeFix -再びSyntax Sugars

さて, なぜlambda closureではなく, fixがprimitiveなのかであるが, 上の例を見てもわかるように, fixは導入される関数に名前をつけるこ とで, 再帰的な関数を自然に定義することを許している. そしてlambda closureは, 単に何か適当な名前を生成してやれば簡単にsyntax sugarとして 実現できる. その意味でfixは, lambda closureを包含している. 逆に, lambda式を使ってfixを簡単に実現できるかというと, 一見fix 式で導入されるそれぞれの関数をlambda式として, それらをlet を使って定義してやれば良いように思えるが, 実はそれだと再帰的な関数の定 義はできない. 例えば上の例を,

(let ((even? (lambda (x) (if (= x 0) #t (odd? (- x 1)))))
      (odd? (lambda (x) (if (= x 0) #f (even? (- x 1))))))
  (even? 10))
としてしまうと, letのscope ruleにより, これらはodd?, even? を再帰的な関数として実現したことにはならない.

再帰的な関数を局所的に定義できることで, lambda式のみならず, 数々loopが syntax sugarとして実現できる. 以下に, fix式を元にして簡単なsyntax sugarとして実現できる構文をあげる.

named letやdoの仕様に馴染みがなければ, R5RS等を参照すること.

構文解析器の作成

言語の表層がが決まったところで, 構文解析ルーチン(parser)の製作にとりか かる. これからの説明では,

と仮定する.

以下にSchemeの「式」を構文解析するための関数を述べる. 実際にはこれにtoplevelに現れる式(define ...)を読み込むための関数 を作らなくてはならないはずである.

式は, Schemeの(read)関数を使ってリストの形で読み込まれる. 構文解 析器はこのリストを入力として受けとり, 結果としてparse treeを返す. Parse treeといってもそれはやはりS式で, 入力との違いは, syntax sugarが 全て展開されて, essential syntaxだけが残っているということである.

 1: (define (parse-expr e)
 2:   (if (terminal? e)
 3:       (parse-expr-terminal e) ; parse things like 1, 2, a
 4:       (let ((expander (lookup-parser (car e) syntax-sugar-table)))
 5:         (if expander
 6:             (parse-expr (expander e)) ; expand E and then parse it again
 7:             (let ((parser (lookup-parser (car e) expr-parse-table)))
 8:               (if parser
 9:                   (parser e)  ; if or let
10:                   (parse-app e)))))))
入力された式は3つの場合がある. 構文解析器はまず, 受けとった式がterminal (変数, 定数など, 中に式を再帰 的に含まない式)であるかどうかを検査する. そうであればterminalをparseす る関数を呼ぶ. なければ, 次にそれがsyntax sugarとして定義されている構文 かどうかを(car部を見ることにより)検査する. もしsyntax sugarであれば適 切な展開関数(各syntax sugarごとに定義する)を呼び, 展開された後の式を再 びparserに入力する. それ以外は, 組み込みのprimitiveまたは, essential syntaxであり, それぞれ適切なparser(各syntaxごとに用意する)を呼ぶ.

Syntax sugarを展開する関数の例として, cond式を展開するを示す(match構 文を使っている).

(define (expand-cond expr)
  (match expr
    (('cond ('else . exprs)) `(begin ,@exprs))
    (('cond (condition . exprs))
     `(internal-if ,condition (begin ,@exprs) #f))
    (('cond (condition . exprs) . others)
     `(internal-if ,condition (begin ,@exprs) (cond ,@others)))))
このような関数(展開関数)が各syntax sugarごとにあり, syntax-sugar-tableに登録されている.

Essential syntaxをparseする関数の例として, ifを展開する式を示す.

(define (parse-min-scheme-if expr)
  (match expr
    (('internal-if condition then-expr else-expr)
     `(if ,(parse-min-scheme-expr condition)
          ,(parse-min-scheme-expr then-expr)
          ,(parse-min-scheme-expr else-expr)))))
同様の関数が, applyおよびprimitiveに関してもある.

実験環境について

Which Scheme to Use?

さて, compilerを実装するのにSchemeを使う必要はないが, S式をparseするの なら, LispまたはSchemeが楽ではある. ここでは, compilerを書くためにお勧 めのSchemeを紹介しておく.

多くの人が使いなれていると思われる, xschemeはinterpreterなので決して速 くはない処理系である. その結果, compilerが出来上がったものの, やたらと compileが遅くて苦労するようである. 結論をいうと,

Chez Scheme
という売り物のSchemeを使うことをお勧めする(command名は, chezscheme). これはspeedが他の処理系に比べて段違いに速く, しかもinteractive環境から loadするだけで, 勝手にcompileしてくれる. マニュアルは米澤研にあるので 見たい場合は, 田浦にrequestして下さい.

その他に, compilerが実装されている処理系としては,

があるがいずれも, compileはstandaloneをはき出すためのもので, interpreterと同じようなノリでは使えない. 速度もchezschemeにはかなわな いので, 目下のところ, chezschemeを選ばない理由は何もない.

注:

Schemeの処理系を作るのでなくても, Schemeが好きな人は, lex/yaccなどでプ ログラム → S式というパーザーを作ってしまえば, 後はSchemeにそ れを読み込ませることができる. また, MLで処理系を作りたければ, ML-yacc というものもあるそうです.

matchについて

/usr/local/src/lang/matchにmatch.ssというSchemeでpattern matchを 行なうためのライブラリがある. これがあるとコンパイラの全てのコードが 非常に読みやすくなる.

使うには, 次のおまじない:

(current-expand eps-expand)
を実行してから,
(load "match.ss")
としてloadして下さい.

課題

Parserを完成させよ. Parserは後から簡単にsyntax sugarが追加できるような flexibleな構成にしておくこと.

可能ならば, レイトレのソースが無事に読み込まれ, 内部的にMin-Schemeない しMin-SchemeFix のessential syntaxのみから成る構文木(もちろんS式で良い) が作られていることを確認せよ.

ヒント: コンパイラが未束縛シンボル(知らない変数や関数名)に対して warningを出すようにしておくとデバッグが楽である. 自分がsyntax sugarに したはずのものがちゃんと展開されていないときなどは, こうして間違いが見 つかる.

締切り: 10月21日(水)

...いたものである.
もちろん標準的なライブラリ関数群(string関係 など)を全てまじめに実装する必要はない. ここではあくまで言語の本質的な 構文で, 取り除かれているものをあげた.
...きる.
LispやSchemeのmacroという機能はまさにこれを目指したものであ る.
...されているものである.
code addressが先頭に書かれている必要は ないが, 常に決まったoffsetに書かれていなくてはならない.
 



 

〔トップページへ〕 〔「コンパイラ演習レジュメ」のindexページへ〕
<vu@is.s.u-tokyo.ac.jp>

Last updated on 9 May, 1999