Rustで作る自作言語(2)

前回: https://zenn.dev/taka2/articles/65c76d6ab42449
次回: https://zenn.dev/taka2/articles/9d3c61e6a2e30c

今回の目標

条件式の追加
if式の追加
単相型推論の実装

パーサー

次のプログラムがパース出来るようにする。

1 > 2
3 < 4
5 == 5

条件式用のパーサーとして次のものを追加した。

pub fn expr_op_4n(input: &str) -> IResult<&str, Expr> {
    let (input, e1) = expr_op_6l(input)?;
    let (input, optional) = opt(|input| {
        let (input, op) = alt((
            tag("=="),
            tag("!="),
            tag("<="),
            tag("<"),
            tag(">="),
            tag(">"),
        ))(input)?;
        let (input, e2) = expr_op_6l(input)?;
        Ok((input, (op, e2)))
    })(input)?;
    match optional {
        Some((op, e2)) => Ok((input, e_bin_op(op, e1, e2))),
        None => Ok((input, e1)),
    }
}

if式の文法は、

if (a > b) 1 else 2

のような文法にしたい。
ASTを定義

pub enum Expr {
    ...
    EIf(Box<Expr>, Box<Expr>, Box<Expr>),
}

パーサー定義

pub fn expr_if(input: &str) -> IResult<&str, Expr> {
    let (input, _) = symbol("if")(input)?;
    let (input, cond) = delimited(symbol("("), parser_expr, symbol(")"))(input)?;
    let (input, e1) = parser_expr(input)?;
    let (input, _) = symbol("else")(input)?;
    let (input, e2) = parser_expr(input)?;
    Ok((input, e_if(cond, e1, e2)))
}

Eval

Valueに真偽値を追加

pub enum Value {
    VInt(i64),
    VBool(bool),
}

条件式の評価の追加

(Value::VInt(n1), Value::VInt(n2)) => match &op as &str {
    ...
    "<" => Ok(v_bool(n1 < n2)),
    ">" => Ok(v_bool(n1 > n2)),
    "<=" => Ok(v_bool(n1 <= n2)),
    ">=" => Ok(v_bool(n1 >= n2)),
    "==" => Ok(v_bool(n1 == n2)),
    "!=" => Ok(v_bool(n1 != n2)),
    ...
}

if式の評価

Expr::EIf(cond, e1, e2) => {
    let cond = self.eval_expr(*cond)?;
    match cond {
       Value::VBool(true) => self.eval_expr(*e1),
       Value::VBool(false) => self.eval_expr(*e2),
       _ => Err("type error".to_string()),
   }
}

単相型推論の実装

1+Trueや、3==Falseなどの式を弾きたい
正しく単相型推論出来れば、その式は"正しい"式である。
まず型を表す型を定義する。

#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Type {
    TInt,
    TBool,
    TVar(u64, Rc<RefCell<Option<Type>>>),
}

次に、式の型を推論する関数、typeinfer_exprを定義する。

pub fn typeinfer_expr(ast: &Expr) -> Result<Type, String> {
    match ast {
        Expr::EInt(_) => Ok(Type::TInt),
        Expr::EBinOp(op, e1, e2) => match &op as &str {
            "+" | "-" | "*" | "/" => {
                unify(Type::TInt, typeinfer_expr(e1)?)?;
                unify(Type::TInt, typeinfer_expr(e2)?)?;
                Ok(Type::TInt)
            }
            "<" | ">" | "<=" | ">=" | "==" | "!=" => {
                unify(Type::TInt, typeinfer_expr(e1)?)?;
                unify(Type::TInt, typeinfer_expr(e2)?)?;
                Ok(Type::TBool)
            }
            _ => Err("unimplemented operator".to_string()),
        },
        Expr::EIf(cond, e1, e2) => {
            unify(Type::TBool, typeinfer_expr(cond)?)?;
            let t = typeinfer_expr(e1)?;
            unify(t.clone(), typeinfer_expr(e2)?)?;
            Ok(t)
        }
    }
}

unifyは渡された２つの型を単一化する関数である。

fn unify(t1: Type, t2: Type) -> Result<(), String> {
    match (t1, t2) {
        (t1, t2) if t1 == t2 => Ok(()),
        (Type::TVar(n1, _), Type::TVar(n2, _)) if n1 == n2 => Ok(()),
        (Type::TVar(_, t1), t2) if (*t1).borrow().is_some() => unify(unwrap_all(t1), t2),
        (t1, Type::TVar(_, t2)) if (*t2).borrow().is_some() => unify(t1, unwrap_all(t2)),
        (Type::TVar(n1, t1), t2) => {
            if occur(n1, t2.clone()) {
                Err("occur error!".to_string())
            } else {
                *(*t1).borrow_mut() = Some(t2);
                Ok(())
            }
        }
        (t1, Type::TVar(n2, t2)) => {
            if occur(n2, t1.clone()) {
                Err("occur error!".to_string())
            } else {
                *(*t2).borrow_mut() = Some(t1);
                Ok(())
            }
        }
        (t1, t2) => Err("unify error!".to_string()),
    }
}

occurは出現検査をする関数で、ある型変数が別の型の中に現れるかどうかを検査する。

fn occur(n: u64, t: Type) -> bool {
    match (n, t) {
        (_, Type::TInt) => false,
        (_, Type::TBool) => false,
        (n, Type::TVar(m, _)) if n == m => true,
        (n, Type::TVar(_, t1)) => match *(*t1).borrow() {
            Some(ref t1) => occur(n, t1.clone()),
            None => false,
        },
    }
}

replに型推論のフローを追加する

pub fn repl() {
	...
        match ast {
            Ok((_, ast)) => {
                let ty = typeinfer_expr(&ast);
                if let Err(err) = ty {
                    println!("type error: {}", err);
                    continue;
                }
		...
	}
}

:t <expr>で式の型が見られるようにする

pub fn repl() {
	...
	let mut is_typecheck = false;
        if program.starts_with(":t") {
            program = program[2..].to_string();
            is_typecheck = true;
        }
        let ast = parser_expr(&program);
        match ast {
            Ok((_, ast)) => {
                let ty = typeinfer_expr(&ast);
                if let Err(err) = ty {
                    println!("type error: {}", err);
                    continue;
                }
                if is_typecheck {
                    println!("{:?}", ty.unwrap());
                    continue;
                }
                ...
}

そろそろ独自のエラー型を定義したい。