🦔

2023/02/21に公開

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>>>),
}
``````

``````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;
}
...
}
``````

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