ITエンジニアのブログ

IT企業でエンジニアやってる人間の日常について

Schemeインタプリタについての話

github.com


自身のウェブサイトで各プログラムの GitHub 及び Bitbucket のリポジトリ内でのコード記述行数を掲載しているのですが、 Scheme の記述行数がかなり少なかったので、 Scheme で何か書こうと思いました。大学の講義で Scheme による Scheme インタプリタを実装したことがあって、そのプログラムを紛失してしまっていたので、再び書き直そうと思いました。 Scheme インタプリタについては以前 Ruby でも書いたことがあります。

Scheme では read という関数を用いて S式を読み込むことが可能なので、構文解析についてはこれだけで完成してしまいます。

次は評価です。構文解析によって S式 s が与えられたとします。これが、例えば 1 や #t などのリテラルであれば、特に変更を加えること無くそのまま返り値とできます。

s がシンボルの場合を考えます。インタプリタでは環境という概念があって、環境で変数と値が束縛されています。 gosh で次のような入力

(define a 1)

を与えると、 (a, 1) という関係が環境の中に定義され、 a という変数を評価すると 1 を返すようになります。インタプリタを作成する場合、この環境を正しく実装することが重要です。

実は、インタプリタの種類によって、環境の形状も変わってきます。 GitHub 上に OCaml で実装した型推論付き ML インタプリタも公開していますが、 Scheme インタプリタとは環境の構成が変わっています。私はこの2種類の環境を知っていて、それぞれフレーム型と直線型というように勝手に名付けています。それぞれについて少し説明してみます。

まずフレーム型です。先程も言及した通り、呼び方は私が勝手に決めただけで、一般的なものではありません。このタイプは Scheme などで取られている手法ですが、インタプリタに限らない場合、 C言語Java なども同じようなものと考えても良いと思います。例が示しやすい C言語で話をしてみます。

int a = 3;
int b = 2;

int add(int x){
  return a + x;
}

このように、同じスコープに定義されている変数は、同じフレーム内に変数が束縛されています。この例だと、グローバルのスコープに対応する環境は下記のようになります。

[(a, 3), (b, 2)]

そして、 if や関数定義の中括弧の中では、さらに一つのフレームがスタックのように上に作られます。例えば、 add(5) を実行したとしましょう。 x に 5 が束縛されます。

[(x, 5)], [(a, 3), (b, 2)]

変数を参照する場合は、上のフレームから順に探索され、値を見つけます。関数適用が終わった時に、上のフレームのみ削除されます。こうすることで、他のスコープを汚すこと無く実行できます。

次に直線型について。 OCamlインタプリタなどを実行した際にこれになります。

let a = 1;;
let add x = x + a;;

上記の式を定義したとき、環境は [(add, ), (a, 1)] となっています。ここで、

let b = 3 in add b;;

を実行しても、途中経過は次のようになり、フレームなどは作られません。

[(x, 3), (b, 3), (add, <fun>), (a, 1)]

勿論、関数適用や let ... in が終われば、 x や b の束縛は消去されます。

この違いは、次のプログラムを実行するとわかりやすいかもしれません。

フレーム型 (Scheme)

(define a 7)
(define (add n) (+ n a))
(add 1)
(define a 10)
(add 1)

直線型 (OCaml)

let a = 7;;
let add n = n + a;;
add 1;;
let a = 10;;
add 1;;

Scheme では add 1 の結果が 8 から 11 になりますが、 OCaml では変更がありません。 Scheme ではフレームの最深部で a の値が変更されたため、関数適用の際にその変更が影響しますが、 OCaml では関数定義の際に環境が定まっており、直線的にそれ以前の環境を参照するために変更が影響しないのです。

環境についても色々、ということで、話を終わります。

次に s が空ではないリストの場合を考えてみましょう。

(define a 1)

こういった場合、最初に先頭のみ評価されます。環境が変に弄られていなければ、 define という syntax が環境に入っているはずなので、 define の動作をします。 define では一番上にある連想リストに変数と値の対応関係を追加します。他の syntax も同様に、環境と式を受け取って特殊な処理を行います。先頭が subroutine の場合は、引数の値を評価して、個々の処理を行います。

クロージャを考えてみましょう。

((lambda (x) (+ x 1)) 1)

ラムダ式を評価すると、クロージャが作られます。クロージャは引数 (x) と式 (+ x 1) に加えて、そのときの環境を保持します。そして、関数を適用するときに、新たなフレームを作り、環境の一番上のスコープに乗っけて式を評価します。この場合では (+ x 1) を評価するために、仮引数 x に引数 1 を束縛して新たに環境を作り、評価します。