SchemeAndImpl / 4.WritingAnInterpreter

SchemeAndImpl

インタープリタを書いてみる †

この章では、Scheme のサブセット言語のための簡単なインタープリタを見せます。 それは Scheme で書かれています。

まずは、簡単な算術の式だけを理解できる Scheme の小さなサブセットのための、非常に簡単なインタープリタからはじめましょう。

そして、そのインタープリタをいろいろと改良していきます。

あとの章で、このインタープリタに戻ってきて、マクロを加えるつもりです。 (云々)

インタープリタでの実行とコンパイル †

プログラミング言語は普通はインタープリタかコンパイラとして、あるいは両方の混ざったものとして、実装されます。実際には、ほとんどすべての言語の実装は、少なくとも少しは両方が混ざったもので、線引きは驚くほど曖昧です。

純粋なインタープリタは、プログラムのソースを読んで、それを分析し、それが書かれたように実行します。これは普通はとても遅い -- インタープリタは文字列を解釈して何を意味しているのかを特定するために多くの時間を費やします。 純粋なインタープリタは、それがソースコードに出会うたびに、次は何をするのかを知る為に、ひとつひとつの式を分析し、認識しなければなりません。これは UNIX シェルや Tclなどの大抵のコマンド・シェル言語が動くやり方ととても似ています。

純粋なコンパイラはプログラムのソースを読んで、それを実行する機械語に翻訳します。コンパイラの大きな利点は一度ソースを通して読んで、分析することができて、インタープリタで実行するのと同じ効果を持つコードを生成することができる点です。 出会う式を毎回分析するのではなく、コンパイラは分析を一度だけ行いますが、インタープリタがプログラムのある時点でとる行動は、記録してあるようなものです。

その効果として、コンパイラは、インタープリタの「振り」をしながら、インタープリタがするであろうことを記録しておくといった、変わった種類ともいえます。それはインタープリタが取るであろう行動の記録をたどり、インタープリタで実行するのと同じ実行効果がある指示を吐き出すのです。 インタープリタが取る意志決定の大半は、-- 式が代入式なのか手続き呼び出しなのかを見極めるのと同じように -- コンパイル時になされます。なぜならその式はプログラムが実行されるときに毎度出会うのと、同じものだからです。

コンパイラの仕事は、いつも同じものであり、実行時にのみ為されるであろう「本当の仕事」を行なう指示を吐き出すことです。なぜならプログラムが操作する実際のデータに、動きが依存するからです。*1 たとえば、if ステートメントはいつでもif ステートメントであり、分析は一度為されればよいです。ですが、どちらの枝が取られるかということは、式の実行時の値によるものであり、そういうわけでコンパイラは式の値をテストするコードを生成し、適切な枝を取ることとします。

大半の実際のインタープリタは、純粋なインタープリタとコンパイラの間のどこかにあるものです。それはプログラムのソースコードを一度読み、扱いやすい「中間表現」-- ある種のデータ構造 -- に翻訳し、それを実行します。ソースコードの文字列を逐次実行するというよりは、もっと便利な形でソースコードの内容を表している、ずっと速く実行できるデータ構造を逐次実行するのです。これは、ある分析を一度行い、ソースコードをあるデータ構造に変換し、あとはデータ構造を逐次実行することでプログラムを実行することになります。

Scheme インタープリタを Scheme のプログラム例として使うことには４つのよい理由があります。

1. 本当に簡単なインタープリタは簡単ですが、Scheme の使いやすい特徴を見せることができます。それは Scheme プログラミングの良い例です。
2. 本格的なプログラムはある種のコマンド・インタープリタを含んでいて、プログラマはそのインタープリタを適切に書く書き方を知っているべきです。しばしば、コマンド・インタープリタはシステムの使いやすさや威力に非常に大きな影響を持つのですが、まずいコマンド・インタープリタを持っているプログラムが多すぎるのです。
3. Scheme のインタープリタがどのように動くかを理解することは、言語の問題を明らかにしてくれます。Scheme が式に出会ったときにしていることを、はっきりと具体的に理解することができ、それによってあなたのプログラムが何をするかも知るようになります -- 例えば、いつ quote(引用符)が必要か、括弧が必要か、あるいは必要でないかが明らかになります。
4. すべてのプログラマはコンパイラの働きの基本を理解するべきです。Scheme インタープリタを理解するなら、Scheme コンパイラを理解するのを半分終えたことになります。Scheme コンパイラは、本当に Scheme インタープリタに似ています。-- それは Scheme の式を分析し、何をするのかを特定します。インタープリタとコンパイラの主な違いは、ただ、インタープリタが何をすべきか特定したらすぐにそれを行なうのに対し、コンパイラはそれを後で走らせるときのために、記録しておくことです。

簡単なインタープリタを実装する †

このセクションでは、Scheme の小さいサブセットのためのインタープリタを実装するために、 Scheme を使用します。われわれが実現するインタープリタは簡単なものですが、本物のインタープリタです。-- それは多くの実際の Scheme システムと同じ原則にのっとって動きます。次の章では、Scheme の重要な特徴の大半を実装するもう少し込み入ったインタープリタと、Scheme コンパイラの骨格(skelton)を見ていきます。

インタープリタは Scheme プログラミングを学ぶにあたって良い例です。なぜならそれは再帰をヘビーに使うから -- 読んで評価するプロセスは自然に再帰的なものなので -- です。 見れば分かりますが、そのコードは大部分が関数的なプログラミング(ほとんど副作用なし)の例ともなります。再帰を自然な形で使うことは、副作用の必要性を避けます。なぜならデータ構造は大抵正しいときに作成されるので、早すぎる時期につくられて後で更新しなければならない、とはならないからです。

われわれのインタープリタは Scheme の組み込み read 手続きを、S式の形で入力を受け付けるために使用します。S式は、シンボル、数値、それらから作られたネストしたリストなど標準的な Schemeのデータ構造をあらわす式のことです。[思い出してもらえば…] S式は、シンボルの場合は単純であり、ネストしたリストの場合は複雑です。

Read-Eval-Print ループ †

(このセクションは、もし「読み評価し表示するループ」(read-eval-print loopのこと。REPLとも言う。) に興味がなければ、読み飛ばしてもらってもかまいません。それは評価器の「フロントエンド」として動く簡単なコマンド・インタープリタに過ぎません。)

あなたがテキストを入力することで、Scheme と対話しているとき、Schemeの手続きであるread-eval-print loopと対話しているのです。この手続きはただループし、一度に１つのコマンドを受付け、それを実行し、結果を表示します。

このループの繰り返しごとに取られる３段階は、

1. 文字列を読むために read 手続きを呼び、キーボードの入力バッファに作られるテキスト形式の式を読み、それを表すデータ構造を作ります。
2. 式を評価する為に eval を呼び、-- 直観的には、eval は、「式が意味するところを特定し」「それが為せというところを為す」-- そして式の値を返します。そして･･･
3. テキスト形式の表現を表示するために、write を呼び、それによりユーザが見られるようになります。(もっと一般的には、われわれはキーボードバッファというよりファイルから式を呼ぶのですが、いまはそれは無視します。)

あなたは自分のプログラムのために、自身で read-eval-print loop を書くことができ、そしてユーザが式を入力でき、あなたが望むようにそれを解釈することができます。後ほど、評価器をどのように書くかを見て行きますが、これが役に立つでしょう*2。この read-eval-print loop を (rep-loop) と入力することで起動でき、それが普通の Scheme の read-eval-print loop の位置を占め、式をあなたのやり方で解釈することができます。

ここにとても簡単な read-eval-print loop があります。

(define (rep-loop)
   (display "repl>")      ; プロンプトを表示する
   (write (eval (read)))  ; 式を読んで、&color(Green){eval}; に渡し、結果を書く
   (rep-loop))            ; もう一度行なうためにループする(末尾再帰)

((write (eval (read)))式が、適切な read-eval-print の順番で物事を行なっていることに注意してください。 なぜなら、手続き呼び出しごとの引数は実際の呼び出しの前に計算されるからです。Scheme では、他の大半の言語と同じように、ネストした手続き呼び出しは、「内側から外側へ」と行なわれます。)

私は、ループ構造ではなく、繰り返しを再帰的にコードしました。最後にしていることが自分自身を呼び出すことなので、手続きは末尾再帰です。Scheme はこの種の再帰をスマートに扱い、手続きの実行状態の情報をスタックに構築してしまい、スタックオーバーフローを起こしたりはしないことを覚えておいてください。一日中でも末尾再帰は可能です。末尾での呼び出し後の手続き呼び出しで何も起こらないので、Scheme は呼び出し元に戻ることを避けられ、戻るべき状態を保存することもしません。*3

上記の read-eval-print loop は、あまりフレンドリーではありません。そこから抜け出る機会を提供せずに永遠にループしつづけるからです。シンボル halt を入力することで、末尾再帰を止めることができるように、それを修正しましょう。

(define (rep-loop)
   (display "repl>")              ; プロンプト表示
   (let ((expr (read)))           ; 式を読み、expr に保存する
      (cond ((eq? expr 'halt)     ; ユーザが止める指示を出した？
             (display "exiting read-eval-print loop")
             (newline))
             (#t                  ; そうでなければ
             (write (eval expr))  ; 評価して表示する
             (newline)
             (rep-loop)))))       ; もう一度するためにループする

再帰呼び出しをしている枝では、その後に他に何もすることがないため、末尾再帰がまだ残っていることに注意してください。

この read-eval-print loop は、もう少し改善できます。シンボル halt をループを止めるコマンドとして使うことで、halt を式として評価することができなくなりました。これは、halt コマンドが言語の中でどんな文法ももっていないことを確認することで避けられますが、それを今は気にしないでよいでしょう。

同じ read-eval-print loop で、違うインタープリタを使うことを可能にするために、別の改良ができます。上にある rep-loop 手続きは、式を評価するために eval という手続きを呼ぶ前提となっています。違った評価器であっても、この rep-loop が動いて欲しいので、eval を名前で呼ぶ代わりに、どの評価器を使うのかを引数として渡せるようにしましょう。手続きはファーストクラスなので、それに評価手続きへのポインタを渡すことができます。

(define (rep-loop evaluator)
   (display "repl>")                 ; プロンプト表示
   (let ((expr (read)))              ; 式を読んで、expr に保存する
      (cond ((eq? expr 'exit)        ; ユーザが止める指示を出した？
             (display "exiting read-eval-print loop")
             (newline))
            (#t                      ; そうでなければ
             (write (evaluator expr)) ;  評価し、表示する
            (rep-loop evaluator))))) ;  そしてもう一度ループする

ここで、３つの変更を行ないました。our-eval に手続きを取る引数を加えました。そして、われわれは eval の呼び出しを our-eval の呼び出しに変え、なんであろうと与えられた評価器(evaluator)を呼ぶようにしました。そして、rep-loop への再帰呼び出しを変更し、次の再帰呼び出しにも引数を渡すようにしました。*4

リーダー †

われわれのインタープリタのために、リーダーを全部書いたりはしませんが、どのようにリーダーが働くかの概要を示し、簡単なリーダーを見せましょう。

(われわれのインタープリタは、実装する基の Scheme システムからリーダーをただ「盗んで」きているだけですが、どのようにリーダーをアックことができるか知ることはよいことで、それは再帰的プログラミングのよい例になります。)

リーダーは単なる read 手続きであり、いくつかの低レベルの手続きをつなげ、個々の文字を読んでトークンを作成し、それを read が、ネストしたデータ構造に押し込めるのです。 トークンはネストした構造を持たない非常に単純な項目に過ぎません。例えば、リストはネストしますが、シンボルはしませんし、文字列もしませんし、数値もしません。

read が使っている低レベルのルーチンは、ただ個々のトークンを入力(文字のストリーム)から読み込みます。これらのトークンは、シンボル、文字列、数値、括弧を含みます。括弧は特別です、というのは、リーダーにネスト構造を読むために、いつ最近が必要かを教えるからです。

(私は文字の I/O については説明していませんが、心配しないでください。 -- Schemeには入力文字をテストしたりしながら、一度に１文字読む処理があります。いまは、その詳細は無視して、リーダーの全体的な構造を描くに留めます。)

われわれが、単にシンボルや、整数や、文字列を読んで、それらから成り立っている(ネストしている可能性のある)リストを読む、簡単なリーダーを持っていると仮定しましょう。それを拡張して、他の種類のものを読むようにするのはどうするか、明らかになるでしょう。

read を実装する †

read は左から右へと入力された文字を読んでいく間に、ネストされたデータ構造を構築するために再帰を使います。

例えば、入力の文字の並びが、こうだったとしましょう。

(foo 20 (baz))

それは、3つの要素からなるリストと読まれ、その最初の２つのシンボルは、foo と値 20 であり、3番目の要素は唯一の要素がシンボル baz *5であるようなまた別のリストです。

read はまた簡単なもの、シンボルや数値といったものを自分で読むことができます。

read が構築するデータ構造は、S式と呼ばれます。S式は文字列や数値のような簡単なものであったり、S式のリストであってもよいです。(この再帰的な定義により、任意の深くネストしたリストもカバーされることに気付いてください。)

(一般に、S式は木の構造を持った(非環状＝サイクリックでない)データ構造であり、Scheme が読み書きすることを知っているシンボル、数値、文字列、文字リテラル、論理値、また、S式のリストやベクターを形作ります。 時に、その用語はもっと広く用いられさえし、Schemeのデータ構造のほとんどの種類を含んでしまうように使われたりしますが、大抵は、そのS式という言葉で、何か標準的なテキストで表される何か、標準的な読み書きできるデータ構造を指すものとして使います。)

この伝統的な術語であるS式は、とても不運なのです。技術的には式はプログラムの一片であり、それは評価されて、Schemeでの値となります。

S式は本当は式などではありません。　-- それは単なるデータ構造であり、それをプログラム内で式を使用することを選ぶかどうかということです*6。リーダーの仕事がただテキストで表された式を扱いやすいデータ構造に変換するだけであったことを思い出してください。それらのデータ構造をプログラムとして解釈する必要はないのです。実際にデータ構造をプログラムとして解釈するのは評価器であって、リーダーではないのです。これが　read-eval-print　ループが、read から戻ってきた S式を評価するために eval　に渡す理由です。

read　の簡略化し過ぎともいえる版を見せましょう。これを micro-read と呼びます。主な簡略化は、micro-read が数個の基本的な型 -- シンボル、非負整数、リスト -- しか扱わないことです。そしてほとんどエラーチェックのコードも書きません。われわれが読もうとしているのは Schemeのデータ構造をきちんと表しているテキスト表現だという前提です。標準入力ではなく、ファイルから読み込むことも扱っていませんし、ファイルの終わりにきたらどうするかもやっていませんので。

read を実装するのをやさしくするために、われわれは一度に 1つのトークンを読むヘルパー手続き read-token というのを使いましょう。直観的に分かるでしょうが、read-token を繰り返し使うことにより、入力を「単語」に分けられます。そして、read はこれらの「単語」をグループに分けて、「句」を形作り、そのようにして、複雑なデータ型を記述することができます。

例えば、次の入力の文字の並びがあったとします。

 (foo 1 (a "bar"))

これは、read-token を繰り返し呼ぶことにより、左から右へと走査され、一度に一つずつ、次に示すようなトークンに分解されます。

 (
 foo
 1
 (
 a
 "bar"
 )
 )

左括弧も右括弧も、一文字で書かれていますが、トークンなのです。それらが出てきたら read に新しいリストが始まったり、終わったりする位置を知らせる特別な単語と考えることもできます。

read-token があるので、read はネスト構造を認識しなければなりません。--- 直観的に言うなら、read-token が個々の単語を認識するので、read は、句を認識しなければなりません。それはもしかするとネストしているかも知れません。各々の句は　read が構築するはずのS式に対応していてネストした句はネストしたS式に対応しています。

読む仕事の大半は、単一の入力トークン、-- 例：シンボル、　文字列リテラル、数値、あるいは左括弧、右括弧といったものを読む read-token　によってなされます。つまり read-token はレキシカル分析(走査としても知られていますが)を行います。read-token は「単語」を認識するまで文字の連なりを読みます。

（われわれの小さなスキャナーは、入力から一回に1文字を読むために、 Scheme の手続きである　read-char を使用します。そして、述語手続きである char-alphabetic? と char-numeric? を使います。これにより文字が英文字であるか、数値であるかを判定します。われわれは Scheme　の文字列リテラルオブジェクトである #\" 、 #\( 、 #\) を使います。左から順に、二重引用符、左括弧、右括弧を表します。）

 ;;; Schemeのレキシカル構文の簡単なサブセット用のスキャナー 
 (define (read-token)
   (let ((first-char (read-char)))
      (cond ;; もし最初の文字が空白や行区切りならば、それを飛ばして、
            ;; 自分を再度呼ぶことで再帰的なループを行なう。
            ((char-whitespace? first-char)
             (read-token))
            ;; もし左括弧ならば、左括弧のトークンを表す
            ;; 特殊なオブジェクトを戻す。
            ((eq? first-char #\( )
             left-paren-token)
            ;; 右括弧についても同様
            ((eq? first-char #\) )
             right-paren-token)
            ;; もし文字ならば、それをシンボルの最初の文字だと仮定し、
            ;; 識別子を形成する残りの文字を読んで、シンボルを戻すために、
            ;; read-identifier を呼ぶ。
            ((char-alphabetic? first-char)
             (read-identifier first-char))
            ;; もし数字ならば、それを数値の最初の数字だと仮定し、
            ;; 数値を形成する残りの数字を読んで数値を戻すために、
            ;; read-number を呼ぶ。
            ((char-numeric? first-char)
             (read-number first-char))
            ;; 上記以外の、この小さなリーダーでは扱えない何かであれば、
            ;; エラーを表示する。
            (else
             (error "不正なレキシカル構文です")))))

[レキシカル分析*7や状態機械*8などについては、手元のプリントを参照のこと*9]

read-token の基本的な操作は入力から 1文字を読んで、その文字を元に、どの種類のトークンが読まれつつあるかということを判断することです。それから、その種類のトークン専用のルーチンが呼ばれ、そのルーチンがトークンを形作る残りの文字を読み、そのトークンが表す Scheme オブジェクトを返すようにさせます。われわれは foo のようなトークンを Schemeのシンボルを表すものとし、122のような数字の連なりを明らかに Scheme　の数値オブジェクトであるとして扱います。

read-token はまた、われわれが自分たちで定義したヘルパー述語も使っています。char-whitespace? は、文字が空白文字か -- スペース文字か改行文字 -- をチェックします。このために、われわれはスペース文字オブジェクトと改行文字オブジェクトを表すリテラル表現を使い、space と newline と書きました。こういうコードです。

;;; whitespace? はスペースか改行文字かをチェックします。
 (define (char-whitespace? char)
   (or (eq? char #\space)
       (eq? char #\newline)))

(節・翻訳途中)

Implementing read †

Implementing the read procedure †

Comments on the Reader †

Recursive Evaluation †

Comments on the Arithmetic Evaluator †

A Note on Snarfing and Bootstrapping †

Snarfing †

Bootstrapping and Cross-compiling †

Improving the Simple Interpreter †

Implementing top-level variable bindings †

Running the improved interpreter †

Discussion and Review †