Rust研究：シンプルなスタックマシン

Rust 初心者です。なかなか Hello world の域を脱却できず、焦りを感じています。

今回はシンプルなスタックマシンを Rust で実装してみます。

[前回](https://qiita.com/mekamaru/items/6a9e4658d9b1cf51a2b6)作成した数式パーサーと組み合わせることで、数式をスタックマシンで計算させてみます。

以下、コードを示しつつ、エッセンスを紹介します。

# スタックマシンのコマンド

前回の再掲です。

```rust
// command.rs

// スタックマシンのコマンド
#[derive(Debug, PartialEq, Clone)]
pub enum Command {
    Add,
    Sub,
    Mul,
    Div,
    Push (i32),
}
    
impl std::fmt::Display for Command {
    fn fmt (&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
    // 省略
```

少し例を示します。

push 100

というコマンドはスタックマシンに対して、スタックに 100 を積ませるコマンドです。
これを実行するとスタックマシンはスタックに 100 が積まれた状態になります。

push 200

というコマンドはスタックマシンに対して、スタックに 200 を積ませるコマンドです。
スタックマシンのスタックには先ほどの 100 の次に 200 が積まれた状態になります。

add

というコマンドはスタックマシンに対して、スタックに積まれた二つの値を取り出して（pop）、足し算を行い、その結果をスタックに積ませるコマンドです。

先の二つのコマンドにより 100 と 200 がスタックに積まれた状態で add を行うと、
計算結果である 300 だけがスタックに積まれた状態になります。

同様に sub は引き算、mul は掛け算、div は割り算に対応しています。

スタックマシンを Rust で次のように実装しました。

```rust
#[derive(Debug)]
pub struct StackMachine {
    stack: Stack,
}

impl StackMachine {
    pub fn new () -> Self {
        StackMachine {
            stack: Stack::new (),
        }
    }

    pub fn push (&mut self, value: i32) -> Result<()> {
        self.stack.push(value)
    }

    pub fn pop (&mut self) -> Result<i32> {
        self.stack.pop()
    }

    pub fn add (&mut self) -> Result<()> {
        let b = self.stack.pop()?;
        let a = self.stack.pop()?;

        // 整数オーバーフローのチェック
        if (a > 0 && b > 0 && i32::max_value() - a < b) ||
           (a < 0 && b < 0 && a < i32::min_value() - b) {
           return Err(Error::Overflow)
        }

        self.stack.push(a + b)
    }

    pub fn sub (&mut self) -> Result<()> {
        let b = self.stack.pop()?;
        let a = self.stack.pop()?;

        // 整数オーバーフローのチェック
        if (a > 0 && b < 0 && a > i32::max_value() + b)  || 
           (a < 0 && b > 0 && a < i32::min_value() + b) {
            return Err(Error::Overflow)
        }

        self.stack.push(a - b)
    }

    pub fn mul (&mut self) -> Result<()> {
        let b = self.stack.pop()?;
        let a = self.stack.pop()?;

        // 整数オーバーフローのチェック
        if (a > 0 && b > 0 && i32::max_value()/b < a) || 
           (a > 0 && b < 0 && i32::min_value()/a > b) ||
           (a < 0 && b > 0 && i32::max_value()/b > a) || 
           (a < 0 && b < 0 && i32::max_value()/a > b) {
            return Err(Error::Overflow)
        }

        self.stack.push(a * b)
    }

    pub fn div (&mut self) -> Result<()> {
        let b = self.stack.pop()?;
        let a = self.stack.pop()?;

        // ゼロ乗算のチェック
        if b == 0 {
            return Err(Error::ZeroDivision)
        }

        // 整数オーバーフローのチェック
        if a == i32::min_value() && b == -1 {
            return Err(Error::Overflow)
        }

        self.stack.push (a / b)
    }

    // コマンド列を処理する
    pub fn process (&mut self, commands:Vec<Command>) -> Result<()> {

        for command in commands {
            match command {
                Command::Add => self.add()?,
                Command::Sub => self.sub()?,
                Command::Mul => self.mul()?,
                Command::Div => self.div()?,
                Command::Push (value) => self.push(value)?,
            }
        }

        Ok(())
    }
}
```

add, sub, mul, div の中で整数オーバーフロー対策を行っています。
整数オーバーフローは計算結果が、扱える整数値の範囲を超える場合におこるエラーです。
Rust の実行ファイルは整数オーバーフローがあると即座にそこで処理が止まりますが、プログラムの中でエラーを検出することでエラー処理を行えるようにしています。

例えば、a + b の例で考えると、a と b 両方が正の整数のときに a + b ＞ 整数の最大値となる場合にオーバーフローとなります。
従って、途中の計算で整数の最大値を超えないよう工夫して、b ＞ 整数の最大値 - a となるかチェックすればオーバーフローは検出できます。
mul の場合は掛け算の結果が整数の最大値を超えるかどうかをみます。
div の場合は 0 乗算と整数の最小値÷(-1) となるかをチェックします。

…という話は、昔の IPA の試験でも出題されたように思いますので案外プログラミングの基本知識なのかもしれません。

スタックそのものは次のように実装しました。

```rust
// スタックサイズ
const STACK_SIZE:usize = 10;

// スタック
#[derive(Debug)]
pub struct Stack {
    data: [i32; STACK_SIZE],
    sp: usize,
}

impl Stack {
    pub fn new () -> Self {
        Stack {
            data: [0i32; STACK_SIZE],
            sp: 0,
        }
    }

    pub fn push (&mut self, value:i32) -> Result<()> {
        // スタックの容量を超えての push はエラー
        if self.sp >= STACK_SIZE {
            return Err(Error::StackOverflow)
        }

        self.data[self.sp] = value;
        self.sp += 1;

        Ok(())
    }

    pub fn pop (&mut self) -> Result<i32> {
        // スタックが空のときの pop はエラー
        if self.sp <= 0 {
            return Err(Error::StackEmpty)
        }

        self.sp -= 1;

        Ok(self.data[self.sp])
    }
}
```

スタックの領域はシンプルに整数の配列で用意し、配列のどのセルを参照しているかを示すスタックポインタ (sp) を移動させることでスタックを実現しています。

# コマンド列の読み出し

コマンド列は今回もストリームから読み出します。
BufReader にトレイトを使ってメソッドを追加しました。

```rust
// コマンド列を読みだす
pub fn read_commands<R:Read>(r:&mut BufReader<R>) -> ResultOption<Vec<Command>> {
    let mut commands:Vec<Command> = vec![];

    // 読みだせなくなるまでコマンドを読みだしていく
    loop {
        match r.read_command()? {
            // コマンド列に追加
            Some(command) => commands.push(command),
            None => break,
        }
    }

    if commands.len() < 1 {
        return Ok(None)
    }

    Ok(Some(commands))
}

impl<R:Read> MyRead for std::io::BufReader<R>{}

// 使用する制御コード等
const CR:u8 = 0x0D; // Carriage Return
const LF:u8 = 0x0A; // Line Feed
const HT:u8 = 0x09; // Horizontal Tabulation
const SP:u8 = 0x20; // SPace

trait MyRead: Read {

    // コマンドの読み出し
    fn read_command(&mut self) -> ResultOption<Command> {

        // 文字列を読みだして
        let s = match self.read_str()? {
            None => return Ok(None),
            Some(s) => s,
        };
        // 読みだした文字列で分岐
        match s.as_str() {
            "add" => Ok(Some(Command::Add)),
            "sub" => Ok(Some(Command::Sub)),
            "mul" => Ok(Some(Command::Mul)),
            "div" => Ok(Some(Command::Div)),
            "push" => {
                // push のときは続く整数を読みだす
                if let Some(value) = self.read_i32()? {
                    Ok(Some(Command::Push(value))) 
                } else {
                    Ok(None)
                }
            },
            _ => Err(Error::UnknownCommand),
        }
    }

    // 整数の読み出し
    fn read_i32(&mut self) -> ResultOption<i32> {
        // 文字列を読みだして
        match self.read_str()? {
            Some(s) => {
                // 整数としてパースする
                let n:i32 = s.parse()?;
                Ok(Some(n))        
            }, 
            None => Ok(None),
        }
    }

    // 文字列の読み出し
    fn read_str(&mut self) -> ResultOption<String> {

        // 読みだしたバイト列を保管する変数
        let mut bytes:Vec<u8> = vec![];

        loop {
            // 1 バイト読みだして
            if let Some(c) = self.read_1byte()? {
                // それが空白だったときに
                if is_space(c) {
                    if bytes.len() > 0 {
                        // 読み出し途中のバイト列があるときはループを抜ける
                        break
                    }
                    // 読み出し途中のバイト列がないときはバイト列に追加せずループを継続
                } else {
                    // 空白以外のときはバイト列に追加
                    bytes.push(c)
                }
            } else {
                // 1バイトも読みだせなかったときはループをぬける
                break
            }
        }

        if bytes.len() < 1 {
            // まったく読み出せなかったとき
            return Ok(None)
        }

        // 読みだしたバイト列を文字列に変換して返す。
        Ok(Some(String::from_utf8(bytes)?)) // utf8 でなかったときはエラーになる
    }

    // 1バイトを読みだすデフォルトメソッド
    fn read_1byte (&mut self) -> ResultOption<u8> {
        // 省略
}

// 「空白」かどうか。CRLFやタブも「空白」とみなすことに注意
fn is_space(c:u8) -> bool {
    c == CR || c == LF || c == HT || c == SP
}
```

# 実行例

main 関数です。
標準入力でスタックマシンのコマンド列を読みだして、スタックマシンに処理させます。
最後にスタックの先頭に積まれた値を表示します。

```rust
fn main () {
    if let Err(e) = process () {
        eprintln!("[ERROR] {:?}", e);
    }
}

// 標準入力からスタックマシンのコマンド列を読みだしてスタックマシンに処理させる
fn process () -> Result <()> {

    // スタックマシンの作成
    let mut s = StackMachine::new ();

    // 標準入力のバッファリーダを作成
    let mut r = std::io::BufReader::new(std::io::stdin ());

    // バッファリーダからコマンド列を読みだして、スタックマシンで処理
    if let Some(commands) = read_commands (&mut r)? {
        s.process (commands)?; 
    }

    // スタックの先頭にある計算結果を POP して表示
    let answer = s.pop ()?;
    println! ("answer = {}", answer);

    Ok(())
}
```

これを sm.exe という名前の実行ファイルにコンパイルしました。
いくつか実行例を示します。

```
C:\work>echo push 10 push 20 add | sm.exe
answer = 30

C:\work>echo push 10 push 20 add push 30 add | sm.exe
answer = 60

C:\work>echo push 10 push 20 push 30 add add | sm.exe
answer = 60

C:\work>echo push 10 push 20 push 30 mul add | sm.exe
answer = 610

C:\work>echo push 10 push 20 push 30 add mul | sm.exe
answer = 500
```

# 数式パーサとの連携

前回作成した数式パーサの expr.exe と連携させてみます。
まず数式パーサの動きの確認です。

```
C:\work>expr.exe "10 + 20 + 30"
[DEBUG] ast = BinaryExpr(Add, BinaryExpr(Add, Number(10), Number(20)), Number(30))
push 10
push 20
add
push 30
add
```

数式に対応するASTを標準エラーに表示し、コンパイル結果となるスタックマシンのコマンド列を標準出力に表示します。

次に、expr.exe の標準出力をパイプで sm.exe の標準入力につなげてみます。

```
C:\work>expr.exe "10 + 20 + 30" | sm.exe
[DEBUG] ast = BinaryExpr(Add, BinaryExpr(Add, Number(10), Number(20)), Number(30))
answer = 60
```

10 + 20 + 30 は 60 ということでスタックマシンにより数式の計算が行われたことがわかります。

他にもいくつか動作例を示します。

```
C:\work>expr.exe "10 + 20 * 30" | sm.exe
[DEBUG] ast = BinaryExpr(Add, Number(10), BinaryExpr(Mul, Number(20), Number(30)))
answer = 610
```

```
C:\work>expr.exe "(10 + 20) * 30" | sm.exe
[DEBUG] ast = BinaryExpr(Mul, BinaryExpr(Add, Number(10), Number(20)), Number(30))
answer = 900
```

```
C:\work>expr.exe "(10 + 20) + 30 - 666 / (121 - 10)"  | sm.exe
[DEBUG] ast = BinaryExpr(Sub, BinaryExpr(Add, BinaryExpr(Add, Number(10), Number(20)), Number(30)), BinaryExpr(Div, Number(666), BinaryExpr(Sub, Number(121), Number(10))))
answer = 54
```

今回はシンプルなスタックマシンを Rust で実装し、前回実装した数式パーサと組み合わせることで数式の計算を行いました。

また整数オーバーフロー対策を実装しました。
長いこと Python を使ってると整数オーバーフローがないので忘れますね。
たまたま動作確認中に対策忘れに気がつき、追加しました。
C や Java で開発していた頃は結構当たり前にやっていたのですけどね。

と、どうせこんな記事誰も興味ねーよなー、なんて思いながら書いてみました。