Rust LT#2 で話をしました．「インタプリタを作ってまなぶ Rust らしい書き方」という話です．内容は実は，Ruby のコードを Rust のコードに置き換えてみようという内容でした．Ruby 製のインタプリタを Rust に置き換えるセッションです．
しかし，5分では無理がありました．とくにインタプリタを2分以内で説明し切るのは完全に無理で，その実装を3分で説明し切るには時間が少なすぎました．なので，今回インタプリタを自作してみようという方向けに，どのような背景知識が必要となってくるのかについて簡単に書き残しておこうと思います．また，今回上げたソースコードの解説もこの記事の後半で加えておきます．
インタプリタ側の話
コンパイラという単語についてはすでに聞いたことがあるという前提で進めます．コンパイラそのものの解説．あくまでイメージを掴んでもらうことを目的としていますので，厳密さには欠きます．
コンパイラ
コンパイラの中身について軽く説明します．コンパイラは実は，いくつかのフェーズに分かれます．
- 字句解析
- 構文解析
- 意味解析
- 中間コード生成
- コード最適化
- コード生成
字句解析
プログラムの書かれた文字列を受け取って，トークンと呼ばれるものを最終的に生成します．具体的には，
position = initial + rate * 60
というプログラム文字列があったとき，これを次のようなくくりで分解します．
〈position〉 〈=〉 〈initial〉 〈+〉 〈rate〉 〈*〉 〈60〉
〈〉 で囲まれた1つ1つの塊をトークンと呼び，コンパイラはこのトークンからすべてがはじまります．このとき多くの言語ではホワイトスペースやタブは消失します．
ここで，= を Eq，+ を Add，* を Mul というトークンとして管理するとします．さらに，60 を Num, value というトークンとして管理するものとします．すると，
〈position〉 〈Eq〉 〈initial〉 〈Add〉 〈rate〉 〈Mul〉 〈Num, 60〉
というふうにトークンを整理できます．さらに，変数は記号表と呼ばれるものに保存することが多いです．position，initial，rate などの変数を，Var, id というトークンで管理し，記号表に内容を保存するものとしましょう．
〈Var, 1〉 〈Eq〉 〈Var, 2〉 〈Add〉 〈Var, 3〉 〈Mul〉 〈Num, 60〉
というトークン列に分解することができました．記号表は
| id | name | value |
|---|---|---|
| 1 | position | ... |
| 2 | initial | ... |
| 3 | rate | ... |
というような構成になります．
構文解析
字句解析を行った結果，トークン列を受け取ります．そしてトークン列が持つ文法構造を明らかにしていくのが，構文解析です．最終的には構文木(あるいは抽象構文木: Abstract Syntax Tree; AST)と呼ばれる中間表現物を結果として得ます．
先ほど得たトークン列
〈Var, 1〉 〈Eq〉 〈Var, 2〉 〈Add〉 〈Var, 3〉 〈Mult〉 〈Num, 60〉
は，たとえば次のような構文木を作ります．
構文木は手順を表します．なので，掛け算は足し算よりも優先度が高いので足し算の木よりも処理があとに来るように構文木を構築します．
また，足し算引き算以外にもif や while，for などの制御構文を構文木に直したりします．
この木構造でできているというのがポイントで，木構造だからこそ再帰的な処理で効率よく文章をたどっていくことができるのです．
意味解析
このフェーズではいくつかやることがあります．
- 変数とか関数とかの使い方が言語定義に沿ったものになっているかチェック
- スコープの決定
- 型情報を収集して型検査
- etc
このようにプログラムの意味の正しさについてチェックするフェーズが意味解析です．今回作成したインタプリタでは意味解析はほぼやっていません．
中間コード生成
〈Var, 1〉 〈Eq〉 〈Var, 2〉 〈Add〉 〈Var, 3〉 〈Mult〉 〈Num, 60〉
先程のこのトークン列からコンパイラが解析しやすい形にさらにトークンを変換します．たとえば今回のコンパイラでは，足し算と掛け算を一気に扱うと計算順序の一貫性を後続処理まで担保し続けることが難しいので両者を切り離したいと考えたとします．このとき，次のような中間コードを生成します．var1 = position, var2 = initial, var3 = rate だと思ってください．
m1 = 60 m2 = var3 * m1 m3 = var2 + m2 var1 = m3
このように切り分けた後，次の最適化フェーズでさらに中間生成物などの無駄を省いてコードを最適化します．
コード最適化
コード最適化フェーズでは要するに中間コードの無駄を省きます．
具体的には，上の中間コードでは， m1 は2度出てきていますし，m3 も2度出てきてしまっています．なので，
m1 = var3 * 60 var1 = var2 + m1
というように最適化できるので，このフェーズでそれをやってしまいます．
コード生成
最適化された中間コードからアセンブリなどが生成されます．
代表的なこれらのフェーズで一通りコンパイラの中で何が起きているか理解できたかと思います．
詳しいところは下記の本などが有名なのでそちらをご覧ください．
コンパイラ―原理・技法・ツール (Information & Computing)
- 作者: A.V.エイホ,R.セシィ,J.D.ウルマン,M.S.ラム,Alfred V. Aho,Jeffery D. Ullman,Ravi Sethi,Monica S. Lam,原田賢一
- 出版社/メーカー: サイエンス社
- 発売日: 2009/06/01
- メディア: 単行本
- 購入: 1人 クリック: 128回
- この商品を含むブログ (30件) を見る
補足知識
さらに補足知識としてよく言語処理系の教科書で出てくる単語を簡単に抑えておきましょう．
パーサー
今回作成したインタプリタでは，構文木を人力で渡すとしていました．しかし通常プログラミング言語のコンパイラでは，構文解析フェーズ (抽象構文木を作るところ) を自動的に解決させます．具体的にはトークンの優先度や前後関係，何を子にもつかなどを別ファイルに定義し，それに従ってプログラムにトークンを木構造に再整理させます．そのような機能をもつものをパーサーと呼びます．
インタプリタ
今回作成したインタプリタは，要するに意味解析くらいまでをやって，そこからそのままコードを評価してしまいます．実行ファイルを生成して，その実行ファイルに対して実行コマンドをかけるわけではないということです．
抽象機械
プログラムをどのように実行するかという規則を定義する装置です．これを抽象機械 (ちょっと具体化したものを仮想機械; Virtual Machine) と呼びます．
ラムダ計算
プログラミング言語の基礎理論として学ぶものです．今回登場させた簡約という概念も，じつはラムダ計算の中に登場してきます．ちなみに今回の発表したコードはラムダ計算で言うところのスモールステップ意味論，操作的意味論などの単語が概念的には該当します．
さすがに書くと長くなるので参考資料をあげさせて代用とさせてください: [pdf] ラムダ計算入門
ここまで準備できたところで，ようやく今回作成したコードを読み解くための基礎知識を得たことになります．長くて申し訳ないですが，上記までを軽く理解していただいてからコードを読んでいただくとすんなり入ってくるのではないかと思っています．
Rust のサンプルコード側の話
さて，今回作成した Rust のコードの話にフォーカスして解説していきます．ソースコードは下記のリポジトリにあります．
構成
トークンを表現する enum Token と，VM を表現する struct Machine によって成り立っています．
enum Token
#[derive(Clone)] pub enum Token { Number(i32), BoolValue(bool), Var(String), Add(Box<Token>, Box<Token>), Multiply(Box<Token>, Box<Token>), LessThan(Box<Token>, Box<Token>), }
Rust において enum は代数的データ型になっています．パターンマッチすることができます．代数的データ型は数学的には直和の表現のようです．
たとえば，各トークンの情報をコンソール上に文字列で出力したいとします．Rust では Display トレイトを実装することで，Java で言うところの toString を定義できます．その定義の際に self に対してパターンマッチを行うことで，各トークンの出力方法を定義することができます．
impl fmt::Display for Token { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { use Token::*; match self { &Number(v) => write!(f, "{}", v), &BoolValue(b) => write!(f, "{}", b), &Var(ref n) => write!(f, "{}", n), &Add(ref blv, ref brv) => write!(f, "{} + {}", blv.to_string(), brv.to_string()), &Multiply(ref blv, ref brv) => write!(f, "{} * {}", blv.to_string(), brv.to_string()), &LessThan(ref blv, ref brv) => write!(f, "{} < {}", blv.to_string(), brv.to_string()), } } }
Token 1つ1つの簡約定義
さて各 Token には簡約定義をつけます．後々再帰的にトークンの簡約処理を回して結果を取得するためです．
そのためにまず，「これ以上簡約可能か？」を定義します．たとえば Add や Multiply は評価を走らせさえすればもっと式を単純化できますが，Number や BoolValue はこれ以上評価のしようがありませんよね．
pub fn is_reducible(&self) -> bool { use Token::*; match *self { Number(_) => false, BoolValue(_) => false, Var(_) => true, Add(_, _) => true, Multiply(_, _) => true, LessThan(_, _) => true, } }
で，fn is_reducible が true だった場合には，fn reduce が走ります．
pub fn reduce(&self, env: &HashMap<String, Token>) -> Token { use Token::*; match self { &Number(_) => panic!("Number token couldn't reduce!"), &BoolValue(_) => panic!("BoolValue token couldn't reduce!"), &Var(ref name) => env.get(name).expect("Variable couldn't get!").clone(), &Add(ref blv, ref brv) if blv.is_reducible() => { Add(Box::new(blv.reduce(env)), brv.clone()) } &Add(ref blv, ref brv) if brv.is_reducible() => { Add(blv.clone(), Box::new(brv.reduce(env))) } &Add(ref blv, ref brv) => match **blv { Number(left_value) => match **brv { Number(right_value) => Number(left_value + right_value), _ => panic!("Unexpected error in Add!"), }, _ => panic!("Unexpected error in Add!"), }, &Multiply(ref blv, ref brv) if blv.is_reducible() => { Multiply(Box::new(blv.reduce(env)), brv.clone()) } &Multiply(ref blv, ref brv) if brv.is_reducible() => { Multiply(blv.clone(), Box::new(brv.reduce(env))) } &Multiply(ref blv, ref brv) => match **blv { Number(left_value) => match **brv { Number(right_value) => Number(left_value * right_value), _ => panic!("Unexpected error in Multiply!"), }, _ => panic!("Unexpected error in Multiply!"), }, &LessThan(ref blv, ref brv) if blv.is_reducible() => { LessThan(Box::new(blv.reduce(env)), brv.clone()) } &LessThan(ref blv, ref brv) if brv.is_reducible() => { LessThan(blv.clone(), Box::new(brv.reduce(env))) } &LessThan(ref blv, ref brv) => match **blv { Number(left_value) => match **brv { Number(right_value) => BoolValue(left_value < right_value), _ => panic!("Unexpected error in LessThan!"), }, _ => panic!("Unexpected error in LessThan!"), }, } }
fn reduce では何をやっているかというと，「親自身が簡約可能なのであれば，左右それぞれの子どもの簡約可能性を見て，さらに簡約可能性探索処理を走らせる．これ以上無理なら簡約する．」ということをやっているだけです．再帰の力を存分に使っています．美しいですね．ちなみに簡約できなかった子の方を clone() しているのはなんとなく無駄かなと思っています．
**blv とか **brv みたいな変数の頭についている ** については，参照外しを2回行っているということです．わかりにくいですが，ref blv というのは要は ref Box<T> になっていて，参照が2つくっついているん (Box も参照の一種) ですね．素の値を欲しいがために ** としています．
エラーメッセージについては，本来はきちんと何行目のどこで出力されたのかを蓄積して持ち回る必要があります．failure クレートなどを使って書くべきではあるんですが，今回は panic で済ませました．
struct Machine
スライドの中でまったくこちらに触れられなかったので解説します．Machine は VM を表現した構造体で，「現在のトークン列の解析状況」と先ほど出てきた「記号表」を保持しています．
pub struct Machine { expression: RefCell<Token>, // 現在のトークン列の解析状況 environment: HashMap<String, Token>, // 記号表 }
実行．
impl Machine { pub fn new(expression: Token) -> Self { Machine { expression: RefCell::new(expression), environment: HashMap::new(), } } pub fn run(&self) { let environment = HashMap::new(); while self.expression.borrow().is_reducible() { println!("{}", self.expression.borrow()); self.step(&environment); } println!("{}", self.expression.borrow()); } fn step(&self, environment: &HashMap<String, Token>) { self.expression .replace(self.expression.clone().into_inner().reduce(environment)); } }
fn new(...) というのはよくやる手で，これを作っておくと構造体の生成が楽になります．こんなふうに．
Machine::new(actual).run();
実行そのもの (fn run) は何をやっているかというと，
- 記号表を
HashMapで生成． - Token が簡約可能かチェック
- 簡約可能ならば，簡約用の関数
fn stepを走らせる． fn stepの中で簡約を起こし，途中経過をexpressionに保存する．
というようなことをやっています．重要なのは reduce() の再帰処理を繰り返しているということで，これはインタプリタを作る上ではよく使う手です．
これで実行できるようになりました．テストコードもそれなりに書いてあるので，よかったらデバッグしてみてください．
作ってみた感想とか
- どこで所有権を奪ってとか，どれの所有権を持ち回るかみたいなところがまだまだ難しい: 困ったら
cloneしちゃうんですよね．してもいい場合とかもちろんあるんですけど，余計なメモリ上のコピーなどはできるだけ少なくしたいなと常々思いつつなかなかうまくできません．設計の問題なのかもしれません． - 型推論強い: たとえば
fn runの中のlet environment = HashMap::new();なんかは，Scala だと型パラメータをつけないと (今回の場合だとHashMap[String, Token]()みたいにね)Nothingになってしまってダメなんですが，Rust は後ろのfn stepの仮引数の型パラメータから推論してくれるのか，HashMap::new()で済んでしまうのがすごいですね．Hindley/Milner やっぱすごいな．
最後に
元ネタの引用を忘れていたので元ネタ載せておきます．一応元ネタがあります．Ruby コードで載っていて，Rust で書き直すちょうどいい練習になったので今回発表に使わせてもらいました．
いい本です．コンピュータサイエンスの教科書を読み解くと，どうしても数式の羅列だったりしてそもそもそういった数学教育を受けていないと解読が難しかったりします．しかしこの本はコードでコンピュータサイエンスの諸概念を解説してくれるので，コードさえ読めればどんな難しい概念でも理解できるすばらしい一冊です．よかったらどうぞ．
アンダースタンディング コンピュテーション ―単純な機械から不可能なプログラムまで
- 作者: Tom Stuart,笹田耕一,笹井崇司
- 出版社/メーカー: オライリージャパン
- 発売日: 2014/09/18
- メディア: 大型本
- この商品を含むブログ (11件) を見る
