Memo

メモ > 技術 > プログラミング言語: Rust > プログラミング言語（rustack）
プログラミング言語（rustack）

Rustで作るプログラミング言語 ―コンパイラ／インタプリタの基礎からプログラミング言語の新潮流まで：書籍案内｜技術評論社
https://gihyo.jp/book/2024/978-4-297-14192-9

GitHub - msakuta/rustack: A very simple stack based language interpreter in Rust
https://github.com/msakuta/rustack

前述の「コンソールアプリケーション」でも作ったが、書籍の順番どおり、まずは逆ポーランド記法で計算できるプログラムを作成する
以下のとおり、プロジェクトを作成する

>cd C:\Users\refirio\Rust
>cargo new rustack --bin
>cd rustack

■ハードコーディングでの実装

src/main.rs の内容を以下のようにする
（「{stack:?}」という書き方は、前述の「基本の文法」内にある「変数」を参照）

fn main() {
    let mut stack = vec![];

    stack.push(42);
    stack.push(36);

    add(&mut stack);

    println!("stack: {stack:?}");
}

fn add(stack: &mut Vec<i32>) {
    let x = stack.pop().unwrap();
    let y = stack.pop().unwrap();
    stack.push(x + y);
}


以下のように、計算結果を表示できる

>cargo run
stack: [78]

■標準入力からの読み込み

src/main.rs の内容を以下のようにする

fn main() {
    let mut stack = vec![];

    stack.push(42);
    stack.push(36);

    add(&mut stack);

    println!("stack: {stack:?}");
}

fn add(stack: &mut Vec<i32>) {
    let x = stack.pop().unwrap();
    let y = stack.pop().unwrap();
    stack.push(x + y);
}


以下のように、入力内容に応じた結果が表示される
終了したい場合、Ctrl+Cで終了する

>cargo run
42 36 +						… 入力
Line: ["42", "36", "+"]				… 結果が表示される■パースとコマンドの実行

src/main.rs の内容を以下のようにする

fn main() {
    for line in std::io::stdin().lines() {
        let mut stack = vec![];
        if let Ok(line) = line {
            let words: Vec<_> = line.split(" ").collect();

            for word in words {
                if let Ok(parsed) = word.parse::<i32>() {
                    stack.push(parsed);
                } else {
                    match word {
                        "+" => add(&mut stack),
                        _ => panic!("{word:?} could not be parsed"),
                    }
                }
            }

            println!("stack: {stack:?}");
        }
    }
}

fn add(stack: &mut Vec<i32>) {
    let x = stack.pop().unwrap();
    let y = stack.pop().unwrap();
    stack.push(x + y);
}


以下のように、入力内容に応じた計算結果が表示される
終了したい場合、Ctrl+Cで終了する

>cargo run
42 36 +						… 入力
stack: [78]					… 計算結果が表示される
42 36 + 22 +					… 入力
stack: [100]					… 計算結果が表示される■四則計算

src/main.rs の内容を以下のようにする
（直感的な計算結果にするため、各計算の関数内でxとyの順番を逆にしているので注意）

fn main() {
    for line in std::io::stdin().lines() {
        let mut stack = vec![];
        if let Ok(line) = line {
            let words: Vec<_> = line.split(" ").collect();

            for word in words {
                if let Ok(parsed) = word.parse::<i32>() {
                    stack.push(parsed);
                } else {
                    match word {
                        "+" => add(&mut stack),
                        "-" => sub(&mut stack),
                        "*" => mul(&mut stack),
                        "/" => div(&mut stack),
                        "%" => rem(&mut stack),
                        _ => panic!("{word:?} could not be parsed"),
                    }
                }
            }

            println!("stack: {stack:?}");
        }
    }
}

fn add(stack: &mut Vec<i32>) {
    let y = stack.pop().unwrap();
    let x = stack.pop().unwrap();
    stack.push(x + y);
}

fn sub(stack: &mut Vec<i32>) {
    let y = stack.pop().unwrap();
    let x = stack.pop().unwrap();
    stack.push(x - y);
}

fn mul(stack: &mut Vec<i32>) {
    let y = stack.pop().unwrap();
    let x = stack.pop().unwrap();
    stack.push(x * y);
}

fn div(stack: &mut Vec<i32>) {
    let y = stack.pop().unwrap();
    let x = stack.pop().unwrap();
    stack.push(x / y);
}

fn rem(stack: &mut Vec<i32>) {
    let y = stack.pop().unwrap();
    let x = stack.pop().unwrap();
    stack.push(x % y);
}


以下のように、入力内容に応じた計算結果が表示される
終了したい場合、Ctrl+Cで終了する

>cargo run
2 3 +						… 入力
stack: [5]					… 計算結果が表示される
2 3 -						… 入力
stack: [-1]					… 計算結果が表示される
2 3 *						… 入力
stack: [6]					… 計算結果が表示される
2 3 /						… 入力
stack: [0]					… 計算結果が表示される
2 3 %						… 入力
stack: [2]					… 計算結果が表示される■ブロックとネスト構造

src/main.rs の内容を以下のようにする

#[derive(Debug, PartialEq, Eq)]
enum Value<'src> {
    Num(i32),
    Op(&'src str),
    Block(Vec<Value<'src>>),
}

impl<'src> Value<'src> {
    fn as_num(&self) -> i32 {
        match self {
            Self::Num(val) => *val,
            _=> panic!("Value is not a number"),
        }
    }
}

fn main() {
    for line in std::io::stdin().lines().flatten() {
        parse(&line);
    }
}

fn parse<'a>(line: &'a str) -> Vec<Value> {
    let mut stack = vec![];
    let input: Vec<_> = line.split(" ").collect();
    let mut words = &input[..];

    while let Some((&word, mut rest)) = words.split_first() {
        if word.is_empty() {
            break;
        }
        if word == "{" {
            let value;
            (value, rest) = parse_block(rest);
            stack.push(value);
        } else if let Ok(parsed) = word.parse::<i32>() {
            stack.push(Value::Num(parsed));
        } else {
            match word {
                "+" => add(&mut stack),
                "-" => sub(&mut stack),
                "*" => mul(&mut stack),
                "/" => div(&mut stack),
                "%" => rem(&mut stack),
                _ => panic!("{word:?} could not be parsed"),
            }
        }
        words = rest;
    }

    println!("stack: {stack:?}");

    stack
}

fn parse_block<'src, 'a>(input: &'a[&'src str]) -> (Value<'src>, &'a[&'src str]) {
    let mut tokens = vec![];
    let mut words = input;

    while let Some((&word, mut rest)) = words.split_first() {
        if word.is_empty() {
            break;
        }
        if word == "{" {
            let value;
            (value, rest) = parse_block(rest);
            tokens.push(value);
        } else if word == "}" {
            return(Value::Block(tokens), rest);
        } else if let Ok(value) = word.parse::<i32>() {
            tokens.push(Value::Num(value));
        } else {
            tokens.push(Value::Op(word));
        }
        words = rest;
    }

    (Value::Block(tokens), words)
}

fn add(stack: &mut Vec<Value>) {
    let y = stack.pop().unwrap().as_num();
    let x = stack.pop().unwrap().as_num();
    stack.push(Value::Num(x + y));
}
fn sub(stack: &mut Vec<Value>) {
    let y = stack.pop().unwrap().as_num();
    let x = stack.pop().unwrap().as_num();
    stack.push(Value::Num(x - y));
}

fn mul(stack: &mut Vec<Value>) {
    let y = stack.pop().unwrap().as_num();
    let x = stack.pop().unwrap().as_num();
    stack.push(Value::Num(x * y));
}

fn div(stack: &mut Vec<Value>) {
    let y = stack.pop().unwrap().as_num();
    let x = stack.pop().unwrap().as_num();
    stack.push(Value::Num(x / y));
}

fn rem(stack: &mut Vec<Value>) {
    let y = stack.pop().unwrap().as_num();
    let x = stack.pop().unwrap().as_num();
    stack.push(Value::Num(x % y));
}

#[cfg(test)]
mod tests {
    use super::{parse, Value::*};

    #[test]
    fn test_group() {
        assert_eq!(
            parse("1 2 + { 3 4 }"),
            vec![Num(3), Block(vec![Num(3), Num(4)])]
        );
    }
}


以下のように、ブロックの処理内容が表示される
終了したい場合、Ctrl+Cで終了する

>cargo run
1 1 +								… 入力
stack: [Num(2)]							… 計算結果が表示される
1 2 + { 3 4 + } 5						… 入力
stack: [Num(3), Block([Num(3), Num(4), Op("+")]), Num(5)]	… 計算結果が表示される
1 2 + { 3 4 }							… 入力
stack: [Num(3), Block([Num(3), Num(4)])]			… 計算結果が表示される■if制御構文

src/main.rs の内容を以下のようにする

#[derive(Debug, Clone, PartialEq, Eq)]
enum Value<'src> {
    Num(i32),
    Op(&'src str),
    Block(Vec<Value<'src>>),
}

impl<'src> Value<'src> {
    fn as_num(&self) -> i32 {
        match self {
            Self::Num(val) => *val,
            _=> panic!("Value is not a number"),
        }
    }

    fn to_block(self) -> Vec<Value<'src>> {
        match self {
            Self::Block(val) => val,
            _=> panic!("Value is not a block"),
        }
    }
}

fn main() {
    for line in std::io::stdin().lines().flatten() {
        parse(&line);
    }
}

fn parse<'a>(line: &'a str) -> Vec<Value> {
    let mut stack = vec![];
    let input: Vec<_> = line.split(" ").collect();
    let mut words = &input[..];

    while let Some((&word, mut rest)) = words.split_first() {
        if word.is_empty() {
            break;
        }
        if word == "{" {
            let value;
            (value, rest) = parse_block(rest);
            stack.push(value);
        } else {
            let code = if let Ok(num) = word.parse::<i32>() {
                Value::Num(num)
            } else {
                Value::Op(word)
            };
            eval(code, &mut stack);
        }
        words = rest;
    }

    println!("stack: {stack:?}");

    stack
}

fn eval<'src>(code: Value<'src>, stack: &mut Vec<Value<'src>>) {
    match code {
        Value::Op(op) => match op {
            "+" => add(stack),
            "-" => sub(stack),
            "*" => mul(stack),
            "/" => div(stack),
            "%" => rem(stack),
            "if" => op_if(stack),
            _ => panic!("{op:?} could not be parsed"),
        },
        _ => stack.push(code.clone()),
    }
}

fn parse_block<'src, 'a>(input: &'a[&'src str]) -> (Value<'src>, &'a[&'src str]) {
    let mut tokens = vec![];
    let mut words = input;

    while let Some((&word, mut rest)) = words.split_first() {
        if word.is_empty() {
            break;
        }
        if word == "{" {
            let value;
            (value, rest) = parse_block(rest);
            tokens.push(value);
        } else if word == "}" {
            return(Value::Block(tokens), rest);
        } else if let Ok(value) = word.parse::<i32>() {
            tokens.push(Value::Num(value));
        } else {
            tokens.push(Value::Op(word));
        }
        words = rest;
    }

    (Value::Block(tokens), words)
}

fn add(stack: &mut Vec<Value>) {
    let y = stack.pop().unwrap().as_num();
    let x = stack.pop().unwrap().as_num();
    stack.push(Value::Num(x + y));
}
fn sub(stack: &mut Vec<Value>) {
    let y = stack.pop().unwrap().as_num();
    let x = stack.pop().unwrap().as_num();
    stack.push(Value::Num(x - y));
}

fn mul(stack: &mut Vec<Value>) {
    let y = stack.pop().unwrap().as_num();
    let x = stack.pop().unwrap().as_num();
    stack.push(Value::Num(x * y));
}

fn div(stack: &mut Vec<Value>) {
    let y = stack.pop().unwrap().as_num();
    let x = stack.pop().unwrap().as_num();
    stack.push(Value::Num(x / y));
}

fn rem(stack: &mut Vec<Value>) {
    let y = stack.pop().unwrap().as_num();
    let x = stack.pop().unwrap().as_num();
    stack.push(Value::Num(x % y));
}

fn op_if(stack: &mut Vec<Value>) {
    let false_branch = stack.pop().unwrap().to_block();
    let true_branch = stack.pop().unwrap().to_block();
    let cond = stack.pop().unwrap().to_block();

    for code in cond {
        eval(code, stack);
    }

    let cond_result = stack.pop().unwrap().as_num();

    if cond_result != 0 {
        for code in true_branch {
            eval(code, stack);
        }
    } else {
        for code in false_branch {
            eval(code, stack);
        }
    }
}

#[cfg(test)]
mod tests {
    use super::{parse, Value::*};

    #[test]
    fn test_group() {
        assert_eq!(
            parse("1 2 + { 3 4 }"),
            vec![Num(3), Block(vec![Num(3), Num(4)])]
        );
    }

    #[test]
    fn test_if_false() {
        assert_eq!(
            parse("{ 1 -1 + } { 100 } { -100 } if"),
            vec![Num(-100)]
        );
    }

    #[test]
    fn test_if_true() {
        assert_eq!(
            parse("{ 1 1 + } { 100 } { -100 } if"),
            vec![Num(100)]
        );
    }
}


>cargo run
{ 1 -1 + } { 100 } { -100 } if					… 入力
stack: [Num(-100)]						… 処理結果が表示される
{ 1 1 + } { 100 } { -100 } if					… 入力
stack: [Num(100)]						… 処理結果が表示される■変数の定義

src/main.rs の内容を以下のようにする

use std::collections::HashMap;

#[derive(Debug, Clone, PartialEq, Eq)]
enum Value<'src> {
    Num(i32),
    Op(&'src str),
    Sym(&'src str),
    Block(Vec<Value<'src>>),
}

impl<'src> Value<'src> {
    fn as_num(&self) -> i32 {
        match self {
            Self::Num(val) => *val,
            _=> panic!("Value is not a number"),
        }
    }

    fn to_block(self) -> Vec<Value<'src>> {
        match self {
            Self::Block(val) => val,
            _=> panic!("Value is not a block"),
        }
    }

    fn as_sym(&self) -> &'src str {
        if let Self::Sym(sym) = self {
            *sym
        } else {
            panic!("Value is not a symbol")
        }
    }
}

struct Vm<'src> {
    stack: Vec<Value<'src>>,
    vars: HashMap<&'src str, Value<'src>>,
}

impl<'src> Vm<'src> {
    fn new() -> Self {
        Self {
            stack: vec![],
            vars: HashMap::new(),
        }
    }
}

fn main() {
    for line in std::io::stdin().lines().flatten() {
        parse(&line);
    }
}

fn parse<'a>(line: &'a str) -> Vec<Value> {
    let mut vm = Vm::new();
    let input: Vec<_> = line.split(" ").collect();
    let mut words = &input[..];

    while let Some((&word, mut rest)) = words.split_first() {
        if word.is_empty() {
            break;
        }
        if word == "{" {
            let value;
            (value, rest) = parse_block(rest);
            vm.stack.push(value);
        } else {
            let code = if let Ok(num) = word.parse::<i32>() {
                Value::Num(num)
            } else if word.starts_with("/") {
                Value::Sym(&word[1..])
            } else {
                Value::Op(word)
            };
            eval(code, &mut vm);
        }
        words = rest;
    }

    println!("stack: {:?}", vm.stack);

    vm.stack
}

fn eval<'src>(code: Value<'src>, vm: &mut Vm<'src>) {
    match code {
        Value::Op(op) => match op {
            "+" => add(&mut vm.stack),
            "-" => sub(&mut vm.stack),
            "*" => mul(&mut vm.stack),
            "/" => div(&mut vm.stack),
            "%" => rem(&mut vm.stack),
            "<" => lt(&mut vm.stack),
            ">" => gt(&mut vm.stack),
            "if" => op_if(vm),
            "def" => op_def(vm),
            _ => {
                let val = vm.vars.get(op).expect(&format!(
                    "{op:?} is not a defined operation"
                ));
                vm.stack.push(val.clone());
            }
        },
        _ => vm.stack.push(code.clone()),
    }
}

fn parse_block<'src, 'a>(input: &'a[&'src str]) -> (Value<'src>, &'a[&'src str]) {
    let mut tokens = vec![];
    let mut words = input;

    while let Some((&word, mut rest)) = words.split_first() {
        if word.is_empty() {
            break;
        }
        if word == "{" {
            let value;
            (value, rest) = parse_block(rest);
            tokens.push(value);
        } else if word == "}" {
            return(Value::Block(tokens), rest);
        } else if let Ok(value) = word.parse::<i32>() {
            tokens.push(Value::Num(value));
        } else {
            tokens.push(Value::Op(word));
        }
        words = rest;
    }

    (Value::Block(tokens), words)
}

macro_rules! impl_op {
    {$name:ident, $op:tt} => {
        fn $name(stack: &mut Vec<Value>) {
            let y = stack.pop().unwrap().as_num();
            let x = stack.pop().unwrap().as_num();
            stack.push(Value::Num((x $op y) as i32));
        }
    }
}

impl_op!(add, +);
impl_op!(sub, -);
impl_op!(mul, *);
impl_op!(div, /);
impl_op!(rem, %);
impl_op!(lt, <);
impl_op!(gt, >);

fn op_if(vm: &mut Vm) {
    let false_branch = vm.stack.pop().unwrap().to_block();
    let true_branch = vm.stack.pop().unwrap().to_block();
    let cond = vm.stack.pop().unwrap().to_block();

    for code in cond {
        eval(code, vm);
    }

    let cond_result = vm.stack.pop().unwrap().as_num();

    if cond_result != 0 {
        for code in true_branch {
            eval(code, vm);
        }
    } else {
        for code in false_branch {
            eval(code, vm);
        }
    }
}

fn op_def(vm: &mut Vm) {
    let value = vm.stack.pop().unwrap();
    eval(value, vm);
    let value = vm.stack.pop().unwrap();
    let sym = vm.stack.pop().unwrap().as_sym();

    vm.vars.insert(sym, value);
}

#[cfg(test)]
mod tests {
    use super::{parse, Value::*};

    #[test]
    fn test_group() {
        assert_eq!(
            parse("1 2 + { 3 4 }"),
            vec![Num(3), Block(vec![Num(3), Num(4)])]
        );
    }

    #[test]
    fn test_if_false() {
        assert_eq!(
            parse("{ 1 -1 + } { 100 } { -100 } if"),
            vec![Num(-100)]
        );
    }

    #[test]
    fn test_if_true() {
        assert_eq!(
            parse("{ 1 1 + } { 100 } { -100 } if"),
            vec![Num(100)]
        );
    }

    #[test]
    fn test_var() {
        assert_eq!(
            parse("/x 10 def /y 20 def x y *"),
            vec![Num(200)]
        );
    }

    #[test]
    fn test_var_if() {
        assert_eq!(
            parse("/x 10 def /y 20 def { x y < } { x } { y } if"),
            vec![Num(10)]
        );
    }
}


>cargo run
/x 10 def /y 20 def x y *					… 入力
stack: [Num(200)]						… 処理結果が表示される
/x 10 def /y 20 def { x y < } { x } { y } if			… 入力
stack: [Num(10)]						… 処理結果が表示される■複数行のソースコードへの対応

src/main.rs の内容を以下のようにする

use std::{
    collections::HashMap,
    io::{BufRead, BufReader}
};

#[derive(Debug, Clone, PartialEq, Eq)]
enum Value {
    Num(i32),
    Op(String),
    Sym(String),
    Block(Vec<Value>),
}

impl Value {
    fn as_num(&self) -> i32 {
        match self {
            Self::Num(val) => *val,
            _=> panic!("Value is not a number"),
        }
    }

    fn to_string(&self) -> String {
        match self {
            Self::Num(i) => i.to_string(),
            Self::Op(ref s) | Self::Sym(ref s) => s.clone(),
            Self::Block(_) => "<Block>".to_string(),
        }
    }

    fn as_sym(&self) -> &str {
        if let Self::Sym(sym) = self {
            sym
        } else {
            panic!("Value is not a symbol")
        }
    }

    fn to_block(self) -> Vec<Value> {
        match self {
            Self::Block(val) => val,
            _=> panic!("Value is not a block"),
        }
    }
}

struct Vm {
    stack: Vec<Value>,
    vars: HashMap<String, Value>,
    blocks: Vec<Vec<Value>>,
}

impl Vm {
    fn new() -> Self {
        Self {
            stack: vec![],
            vars: HashMap::new(),
            blocks: vec![],
        }
    }
}

fn main() {
    if let Some(f) = std::env::args()
        .nth(1)
        .and_then(|f| std::fs::File::open(f).ok())
    {
        parse_batch(BufReader::new(f));
    } else {
        parse_interactive();
    }
}

fn parse_batch(source: impl BufRead) -> Vec<Value> {
    let mut vm = Vm::new();
    for line in source.lines().flatten() {
        for word in line.split(" ") {
            parse_word(word, &mut vm);
        }
    }
    vm.stack
}

fn parse_interactive() {
    let mut vm = Vm::new();
    for line in std::io::stdin().lines().flatten() {
        for word in line.split(" ") {
            parse_word(word, &mut vm);
        }
        println!("stack: {:?}", vm.stack);
    }
}

fn parse_word(word: &str, vm: &mut Vm) {
    if word.is_empty() {
        return;
    }
    if word == "{" {
        vm.blocks.push(vec![]);
    } else if word == "}" {
        let top_block = vm.blocks.pop().expect("Block stack underrun!");
        eval(Value::Block(top_block), vm);
    } else {
        let code = if let Ok(num) = word.parse::<i32>() {
            Value::Num(num)
        } else if word.starts_with("/") {
            Value::Sym(word[1..].to_string())
        } else {
            Value::Op(word.to_string())
        };
        eval(code, vm);
    }
}

fn eval(code: Value, vm: &mut Vm) {
    if let Some(top_block) = vm.blocks.last_mut() {
        top_block.push(code);
        return;
    }
    match code {
        Value::Op(ref op) => match op as &str {
            "+" => add(&mut vm.stack),
            "-" => sub(&mut vm.stack),
            "*" => mul(&mut vm.stack),
            "/" => div(&mut vm.stack),
            "%" => rem(&mut vm.stack),
            "<" => lt(&mut vm.stack),
            ">" => gt(&mut vm.stack),
            "if" => op_if(vm),
            "def" => op_def(vm),
            "puts" => puts(vm),
            _ => {
                let val = vm.vars.get(op).expect(&format!(
                    "{op:?} is not a defined operation"
                ));
                vm.stack.push(val.clone());
            }
        },
        _ => vm.stack.push(code.clone()),
    }
}

macro_rules! impl_op {
    {$name:ident, $op:tt} => {
        fn $name(stack: &mut Vec<Value>) {
            let y = stack.pop().unwrap().as_num();
            let x = stack.pop().unwrap().as_num();
            stack.push(Value::Num((x $op y) as i32));
        }
    }
}

impl_op!(add, +);
impl_op!(sub, -);
impl_op!(mul, *);
impl_op!(div, /);
impl_op!(rem, %);
impl_op!(lt, <);
impl_op!(gt, >);

fn op_if(vm: &mut Vm) {
    let false_branch = vm.stack.pop().unwrap().to_block();
    let true_branch = vm.stack.pop().unwrap().to_block();
    let cond = vm.stack.pop().unwrap().to_block();

    for code in cond {
        eval(code, vm);
    }

    let cond_result = vm.stack.pop().unwrap().as_num();

    if cond_result != 0 {
        for code in true_branch {
            eval(code, vm);
        }
    } else {
        for code in false_branch {
            eval(code, vm);
        }
    }
}

fn op_def(vm: &mut Vm) {
    let value = vm.stack.pop().unwrap();
    eval(value, vm);
    let value = vm.stack.pop().unwrap();
    let sym = vm.stack.pop().unwrap().as_sym().to_string();

    vm.vars.insert(sym, value);
}

fn puts(vm: &mut Vm) {
    let value = vm.stack.pop().unwrap();
    println!("{}", value.to_string());
}

#[cfg(test)]
mod tests {
    use super::{Value::*, *};
    use std::io::Cursor;

    fn parse(input: &str) -> Vec<Value> {
        parse_batch(Cursor::new(input))
    }

    #[test]
    fn test_group() {
        assert_eq!(
            parse("1 2 + { 3 4 }"),
            vec![Num(3), Block(vec![Num(3), Num(4)])]
        );
    }

    #[test]
    fn test_if_false() {
        assert_eq!(
            parse("{ 1 -1 + } { 100 } { -100 } if"),
            vec![Num(-100)]
        );
    }

    #[test]
    fn test_if_true() {
        assert_eq!(
            parse("{ 1 1 + } { 100 } { -100 } if"),
            vec![Num(100)]
        );
    }

    #[test]
    fn test_var() {
        assert_eq!(
            parse("/x 10 def /y 20 def x y *"),
            vec![Num(200)]
        );
    }

    #[test]
    fn test_var_if() {
        assert_eq!(
            parse("/x 10 def /y 20 def { x y < } { x } { y } if"),
            vec![Num(10)]
        );
    }

    #[test]
    fn test_multiline() {
        assert_eq!(
            parse(
                r#"
/x 10 def
/y 20 def

{
    x y <
}
{
    x
}
{
    y
} if
"#
            ),
            vec![Num(10)]
        );
    }
}


input.txt を作成し、以下の内容を記述する

/x 10 def
/y 20 def

{
    x y <
}
{
    x
}
{
    y
} if

puts


>cargo run -- input.txt
10

なお、プログラム中にある「and_then」は、成功した場合のみ処理を実行するもの
「(|f| std::fs::File::open(f).ok())」については、前述の「クロージャ」を参照

■関数呼び出し

src/main.rs の内容を以下のようにする

use std::{
    collections::HashMap,
    io::{BufRead, BufReader}
};

#[derive(Debug, Clone, PartialEq, Eq)]
enum Value {
    Num(i32),
    Op(String),
    Sym(String),
    Block(Vec<Value>),
    Native(NativeOp)
}

impl Value {
    fn as_num(&self) -> i32 {
        match self {
            Self::Num(val) => *val,
            _=> panic!("Value is not a number"),
        }
    }

    fn to_string(&self) -> String {
        match self {
            Self::Num(i) => i.to_string(),
            Self::Op(ref s) | Self::Sym(ref s) => s.clone(),
            Self::Block(_) => "<Block>".to_string(),
            Self::Native(_) => "<Native>".to_string(),
        }
    }

    fn as_sym(&self) -> &str {
        if let Self::Sym(sym) = self {
            sym
        } else {
            panic!("Value is not a symbol")
        }
    }

    fn to_block(self) -> Vec<Value> {
        match self {
            Self::Block(val) => val,
            _=> panic!("Value is not a block"),
        }
    }
}

#[derive(Clone)]
struct NativeOp(fn(&mut Vm));

impl PartialEq for NativeOp {
    fn eq(&self, other: &NativeOp) -> bool {
        self.0 as *const fn() == other.0 as *const fn()
    }
}

impl Eq for NativeOp {}

impl std::fmt::Debug for NativeOp {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "<NativeOp>")
    }
}

struct Vm {
    stack: Vec<Value>,
    vars: HashMap<String, Value>,
    blocks: Vec<Vec<Value>>,
}

impl Vm {
    fn new() -> Self {
        let functions: [(&str, fn(&mut Vm)); 14] = [
            ("+", add),
            ("-", sub),
            ("*", mul),
            ("/", div),
            ("%", rem),
            ("<", lt),
            (">", gt),
            ("if", op_if),
            ("def", op_def),
            ("puts", puts),
            ("pop", pop),
            ("dup", dup),
            ("exch", exch),
            ("index", index),
        ];
        Self {
            stack: vec![],
            vars: functions
                .into_iter()
                .map(|(name, fun)| {
                    (name.to_owned(), Value::Native(NativeOp(fun)))
                })
                .collect(),
            blocks: vec![],
        }
    }
}

fn main() {
    if let Some(f) = std::env::args()
        .nth(1)
        .and_then(|f| std::fs::File::open(f).ok())
    {
        parse_batch(BufReader::new(f));
    } else {
        parse_interactive();
    }
}

fn parse_batch(source: impl BufRead) -> Vec<Value> {
    let mut vm = Vm::new();
    for line in source.lines().flatten() {
        for word in line.split(" ") {
            parse_word(word, &mut vm);
        }
    }
    vm.stack
}

fn parse_interactive() {
    let mut vm = Vm::new();
    for line in std::io::stdin().lines().flatten() {
        for word in line.split(" ") {
            parse_word(word, &mut vm);
        }
        println!("stack: {:?}", vm.stack);
    }
}

fn parse_word(word: &str, vm: &mut Vm) {
    if word.is_empty() {
        return;
    }
    if word == "{" {
        vm.blocks.push(vec![]);
    } else if word == "}" {
        let top_block = vm.blocks.pop().expect("Block stack underrun!");
        eval(Value::Block(top_block), vm);
    } else {
        let code = if let Ok(num) = word.parse::<i32>() {
            Value::Num(num)
        } else if word.starts_with("/") {
            Value::Sym(word[1..].to_string())
        } else {
            Value::Op(word.to_string())
        };
        eval(code, vm);
    }
}

fn eval(code: Value, vm: &mut Vm) {
    if let Some(top_block) = vm.blocks.last_mut() {
        top_block.push(code);
        return;
    }
    if let Value::Op(ref op) = code {
        let val = vm.vars.get(op).expect(&format!(
            "{op:?} is not a defined operation"
        )).clone();

        match val {
            Value::Block(block) => {
                for code in block {
                    eval(code, vm);
                }
            }
            Value::Native(op) => op.0(vm),
            _ => vm.stack.push(val),
        }
    } else {
        vm.stack.push(code.clone());
    }
}

macro_rules! impl_op {
    {$name:ident, $op:tt} => {
        fn $name(vm: &mut Vm) {
            let y = vm.stack.pop().unwrap().as_num();
            let x = vm.stack.pop().unwrap().as_num();
            vm.stack.push(Value::Num((x $op y) as i32));
        }
    }
}

impl_op!(add, +);
impl_op!(sub, -);
impl_op!(mul, *);
impl_op!(div, /);
impl_op!(rem, %);
impl_op!(lt, <);
impl_op!(gt, >);

fn op_if(vm: &mut Vm) {
    let false_branch = vm.stack.pop().unwrap().to_block();
    let true_branch = vm.stack.pop().unwrap().to_block();
    let cond = vm.stack.pop().unwrap().to_block();

    for code in cond {
        eval(code, vm);
    }

    let cond_result = vm.stack.pop().unwrap().as_num();

    if cond_result != 0 {
        for code in true_branch {
            eval(code, vm);
        }
    } else {
        for code in false_branch {
            eval(code, vm);
        }
    }
}

fn op_def(vm: &mut Vm) {
    let value = vm.stack.pop().unwrap();
    eval(value, vm);
    let value = vm.stack.pop().unwrap();
    let sym = vm.stack.pop().unwrap().as_sym().to_string();

    vm.vars.insert(sym, value);
}

fn puts(vm: &mut Vm) {
    let value = vm.stack.pop().unwrap();
    println!("{}", value.to_string());
}

fn pop(vm: &mut Vm) {
    vm.stack.pop().unwrap();
}

fn dup(vm: &mut Vm) {
    let value = vm.stack.last().unwrap();
    vm.stack.push(value.clone());
}

fn exch(vm: &mut Vm) {
    let last = vm.stack.pop().unwrap();
    let second = vm.stack.pop().unwrap();
    vm.stack.push(last);
    vm.stack.push(second);
}

fn index(vm: &mut Vm) {
    let index = vm.stack.pop().unwrap().as_num() as usize;
    let value = vm.stack[vm.stack.len() - index - 1].clone();
    vm.stack.push(value);
}

#[cfg(test)]
mod tests {
    use super::{Value::*, *};
    use std::io::Cursor;

    fn parse(input: &str) -> Vec<Value> {
        parse_batch(Cursor::new(input))
    }

    #[test]
    fn test_group() {
        assert_eq!(
            parse("1 2 + { 3 4 }"),
            vec![Num(3), Block(vec![Num(3), Num(4)])]
        );
    }

    #[test]
    fn test_if_false() {
        assert_eq!(
            parse("{ 1 -1 + } { 100 } { -100 } if"),
            vec![Num(-100)]
        );
    }

    #[test]
    fn test_if_true() {
        assert_eq!(
            parse("{ 1 1 + } { 100 } { -100 } if"),
            vec![Num(100)]
        );
    }

    #[test]
    fn test_var() {
        assert_eq!(
            parse("/x 10 def /y 20 def x y *"),
            vec![Num(200)]
        );
    }

    #[test]
    fn test_var_if() {
        assert_eq!(
            parse("/x 10 def /y 20 def { x y < } { x } { y } if"),
            vec![Num(10)]
        );
    }

    #[test]
    fn test_multiline() {
        assert_eq!(
            parse(
                r#"
/x 10 def
/y 20 def

{
    x y <
}
{
    x
}
{
    y
} if
"#
            ),
            vec![Num(10)]
        );
    }

    #[test]
    fn test_function() {
        assert_eq!(
            parse(
                r#"
/double { 2 * } def
10 double
"#
            ),
            vec![Num(20)]
        );
    }
}


input.txt を作成し、以下の内容を記述する

/double { 2 * } def
/square { dup * } def

10 double puts
10 square puts


>cargo run -- input.txt
20
100

今度は input.txt の内容を以下のように変更する
これで10の階上を計算できる（関数の再帰呼び出しができていることを確認できる）

/factorial { 1 factorial_int } def

/factorial_int {
  /acc exch def
  /n exch def
  { n 2 < }
  { acc }
  {
    n 1 -
    acc n *
    factorial_int
 }
 if
} def

10 factorial puts


>cargo run -- input.txt
3628800

■ローカル変数

引き続き…
Memo

Advertisement
