はじめに
42の課題で、いろんな計算ができるインタプリタをRustで作成したため、その備忘録として書いています。
作成した手順や、どこに工夫したかなどを重点的に書いているため、課題全体の解説というわけではない点についてはご了承ください。
作成したものはこちらにあります。
また42の他の活動についてはこちらにありますので、42自体に興味がある方はぜひこちらもどうぞ。
ちなみに前回解いた課題の記事はこちらになります。
作ったもの
ということで作ったものですが、以下のようなものになります！
./computorv2
> func(x) = x^2 + 3x + 3
x ^ 2 + 3 * x + 3
> y = 1
1
> func(x) = y ?
2 + 3x^1 + x^2 = 0
Two solutions on R:
-1
-2
色々な機能があって全部乗せるとそれだけでいっぱいになってしまうので、簡単にですが以下のようなことができます。
- 変数、関数の使用
- 有理数（float）、複素数、行列
- i, pi（円周率）
- sin, cos, tan, abs（絶対値）, exp（e^2とか）, sqrt（ルート）
- 二次までの方程式の解を求める
- 登録した変数、関数の表示と、コマンド履歴の表示
- --richオプションで、少し高機能なターミナル
詳細については、冒頭に載せたgithubをご覧ください。
作成した手順
ここからは、どのように作成していったかになります。
インタプリタの作成
まずは動くようにしたいなと思ったので、インタプリタの作成からはじめました。
ちなみにインタプリタとは……
この段階では打ち込まれた文字を返すだけの単純なものです。
exitで終了します。
$ cargo run
> hello
hello
> computor
computor
> exit
exit
また、Go言語で作るインタプリタという本があるそうで、それをRustでやってみたという以下の記事が見つかり、とても参考になりました。
字句解析
次に字句解析を行いました。
ここでは、入力した文字列を、あとで使いやすいように分解しておくことをしました。
例えば私は以下のようにしました。
$ cargo run
> ()^*/%**+-i=?[],;a1A2zz ZZ123.098^A
[LParen, RParen, Caret, Asterisk, Slash, Percent, TwoAsterisk, Plus, Minus, I, Equal, Question, LBracket, RBracket, Comma, SemiColon, String("a"), NumString("1"), String("A"), NumString("2"), String("zz"), String("ZZ"), NumString("123.098"), Caret, String("A")]
今回大文字と小文字は区別しないので、後ほどすべて小文字にしようと思っているのですが、その変換や、文字列を数字に変換する部分については、後回しにしています。
ここではあくまで分解するだけです。
floatの計算
次に、数字を扱う構造体を作っていく作業に移ります。
私はNumというenumで、floatも複素数も行列も管理できるようにしました。
このおかげで、例えばA.add(B)というようにすれば、A, Bがfloatでも複素数でも行列でも計算ができるようになっています。
ここではまずその準備として、floatの計算だけできるようにしました。
ちなみに一つだけ演算の部分を載せると、以下のようになっています。
pub fn supported_add(&self, rhs: &Num) -> Result<Num, String> {
match (self, rhs) {
(Num::Float(l), Num::Float(r)) => {
Ok(Num::Float(l + r))
},
}
}
まだfloatだけなのでうまみがないですが、この段階で作成しておくことで、複素数や行列を後から追加しても、修正量が少なくなるようにしています。
また、例えば実数と行列の足し算は定義されないので、その２つの演算になった場合にはエラーになるようにします。
二分木
次は構文解析のために二分木を作りました。
二分木については、こちらの2つを参考にしました。
特に2つめの方は、このサンプルが載っている書籍（プログラミングRust 第2版）が、Rustで書くうえで何かと参考になりました。
構文解析
ここからはいよいよ構文解析です。ここからが本番という感じです。
floatの計算
まずは簡単にfloatの計算だけできるようにしました。
以下のように掛け算などの順番も正しく判別できるようになってます。
> 1+2*3^2-2
17
ちなみに1+2*3を構文木にする際には以下のようにしています。
+
/ \
1 *
/ \
2 3
また、処理の流れとしては以下のようになっています。
- +の左を展開する→1をゲット
- +の右を展開する
- *の左を展開する→2をゲット
- *の右を展開する→3をゲット
- *の計算を行う->6
- +の計算を行う→7
このように演算子にあたったら左右を展開して演算……という繰り返しで計算をしています。
かっこ
次はかっこに対応させました。
> 1 + 2 ^ (1 + 2) * 3 - 2
23
ちなみにかっこに関しては構文木では以下のようにしています。
(
/ \
A )
かっこの場合は、「左側を持ってくる演算子」として定義して、基本的には演算子と同じように扱っています。
=の判定
次に細かい話ですが、課題の形式にそろえるために、以下のように=?となっていた場合のみ計算するようにしました。
> 1 + 2 ^ (1 + 2) * 3 - 2 =?
23
また、内部的には、=の左右を完全に別のものとして扱っていて、構文木もわけています。
単項演算子
次に単項演算子……つまり、-1や+2などに対応しました。
例えば-2は構文木上では以下のようになっています。
-
/ \
D 2
ここで、「D」は、ダミー変数になります。
ダミーは出力時には無視するようにし、また計算時には0になるようにしています。
変数
次に変数に値を登録できるようにしました。
値の登録は以下のようにできます。
> x = 2 * 3 + 1
7
> x = ?
7
このように、登録した値はそのあとで使えるようになっています。
値の登録は、HashMapに変数名をkey, 値をvalueとして登録するようにしました。
関数
次に関数の登録を行いました。
関数は、変数のときに使ったHashMapに、関数名をkey、(構文木, その中の変数)をvalueとして登録するようにしました。
> funA(b) = 2*b + b
2 * b + b
> func(2) = ?
6
ちなみに微妙にひっかかったのが、以下のようなパターンでした。
> x = -1
-1
> func(a) = a + x
a + -1
> func(a) = x ^ a
- 1 ^ a
これは本当は以下のようになってほしいので、そのための修正も行いました。
> func(a) = a + x
a - 1
> func(a) = x ^ a
( - 1 ) ^ a
また、関数 f(A) は、構文木上では以下のようにしました。
f
/ \
( )
/ \
A )
fの右側に入っている「)」は、ダミーのような感じで、実際には全く読み込まれないものになります。
また、以下のように、すでに登録されている変数を使用しても、関数の登録時にはローカル変数を優先するようなイメージで、無視するようにしました。
> x = 1
1
> y = 2
2
> funA(x) = y*x + x
2 * x + x
> func(x) = ?
3
複素数
ここまでで構文解析としてのだいたいの機能は実装できたので、複素数の対応をしました。
Floatのところでの話の通り、同じenumで計算をできるようにしたため、構文解析的には、「i」を解釈できるようにすることくらいの修正ですんでいます。
複素数は、実部と虚部をもつ以下のような構造体で表現しました。
pub struct Complex {
pub r: f64,
pub z: f64,
}
これで、以下のようなことができるようになりました。
> func(x) = x * 2i
x * 2 * i
> a = i
i
> b = a + 1
1 + i
> func(b) =?
-2 + 2i
変数と関数の一覧表示
このあたりで登録した変数や関数を見たくなってきたので、一覧表示をする機能を加えました。
> variables
a: i
b: 1 + i
> functions
func(x): x * 2 * i
行列
次に行列の演算をできるようにしました。
例えばこんな感じです。
> x = [[3,3,3];[3,3,3]]
[ 3 , 3 , 3 ]
[ 3 , 3 , 3 ]
> y = [[1,2];[2,2];[2,2]]
[ 1 , 2 ]
[ 2 , 2 ]
[ 2 , 2 ]
> x ** y =?
[ 15 , 18 ]
[ 15 , 18 ]
これも、floatや複素数と同じところに入れているので、共通の呼び出し方法で演算ができるようにしています。
そのおかげで、行列の実装と、入力から読み込む部分を作成したら、あとはほとんど修正がいりませんでした。
方程式
次に方程式を解けるようにしました。
> x^2 + 2x + 1 = 0?
1 + 2x^1 + x^2 = 0
Only one solution on R:
-1
> x^2 - 3x + 2 = 0?
2 - 3x^1 + x^2 = 0
Two solutions on R:
2
1
> x^2 = -1 ?
1 + x^2 = 0
Two solutions on C:
± i
実はこちらは以前別の課題↓で行ったので、構文木から別の課題でやったフォーマットに変換する部分を作成し、あとは流用して実装しました。
ここまでで必須項目はだいたい終えたので、あとはこのインタプリタを強化することを行いました。
合成関数
関数の中に関数を入れたりできるようにしました。
ここまでは、構文木の中の変数を「値」に変換することは行いましたが、ここでは構文木の中に「構文木」を差し込むことを行いました。
特殊な変数・関数の登録
次に、sin, cosなどの特殊な関数をデフォルトで使えるようにしました。
こちらは、変数や関数を登録しているHashMapとは別のHashMapに登録するようにしています。
また、sinなどは既存の構文木では表現できないため、sinはsinのまま構文木に入れるようにしました。
また、特殊な変数としては、π（pi）のみ使えるようにしました。
コマンド履歴
次に、コマンドの履歴を保存できるようにしました。
これは、VecDequeという、前からでも後ろからでも出したり入れたりできる構造を使って実装しました。
Vecでない理由ですが、入れるときはコマンドとその結果を両方合わせてVecDequeに後ろから入れているのですが、コマンドが一定の量になったら古いコマンドは吐き出したく、その古いコマンドは手前にあるため、後ろから入れて前から吐き出すことができるVecDequeを使いました。
コマンドの履歴は以下のようにhistoryで取り出せるようにしました。
> x = 1
1
> x + 2 = ?
3
> history
x = 1: 1
x + 2 = ?: 3
ターミナルの強化
最後に、ターミナルを強化するために、crossterm crateを導入しました。
これによって、入力時のカーソルを右左に動かしたり、上下に動かすことで履歴をたどったりすることができるようになりました。
crossterm crateについては、以下のテキストエディタを作成するチュートリアルが非常に参考になりました。
おわりに
ということで、ざらっと手順等のご紹介をしました。
このインタプリタシリーズはこれで課題としては終わりですが、とても楽しかったので、個人的に改良していきたいなと思いました。