Rustで作る自作言語(4)

前回: https://zenn.dev/taka2/articles/9d3c61e6a2e30c
次回: https://zenn.dev/taka2/articles/97df820e0c38be

今回の目標

関数を定義、使用することが出来るようになる

関数定義の文法

let add(a, b) = a + b;

ASTの定義

関数を表す式のASTを定義する。

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

次の関数定義は、

let add(a, b) = a + b;

次のようなASTとなる。

Assign("add", EFun("a", EFun("b", EBinOp("+", EVar("a"), EVar("b")))))

関数定義のパーサーの定義

まず上記関数定義のパーサーを定義します。

pub fn fun_def(input: &str) -> IResult<&str, Statement> {
    let (input, _) = keyword("let")(input)?;
    let (input, id) = identifier(input)?;
    let (input, _) = symbol("(")(input)?;
    let (input, args) = many0(identifier)(input)?;
    let (input, _) = symbol(")")(input)?;
    let (input, _) = symbol("=")(input)?;
    let (input, expr) = parser_expr(input)?;
    let mut result = expr;
    for i in (0..args.len()).rev() {
        result = Expr::EFun(args[i].clone(), Box::new(result))
    }
    Ok((input, Statement::Assign(id, result)))
}

rustでのfoldr的な関数が分からないので手続き的に書いてしまいました。

次に、前回の代入文も含めた文のパーサを定義した。

pub fn parser_statement(input: &str) -> IResult<&str, Statement> {
    let (input, statement) = alt((fun_def, statement_assign))(input)?;
    Ok((input, statement))
}

あと、今までパーサーの入力がすべて消費されていなくてもパースエラーになっていなかったのが気になっていたので、そのような入力がエラーとなるようにした。

pub fn parser_statements(input: &str) -> IResult<&str, Statements> {
    let (input, statements) = many1(parser_statement)(input)?;
    let (input, _) = eof(input)?;
    Ok((input, statements))
}
pub fn parser_for_repl(input: &str) -> IResult<&str, StatementOrExpr> {
    let (input, stmt) = parser_statement_or_expr(input)?;
    let (input, _) = eof(input)?;
    Ok((input, stmt))
}

型推論の実装

まず、関数の型を定義する。

TFun(Box<Type>, Box<Type>),

次に、typeinfer_exprのastのマッチアームにEFunの場合を追加します。

            Expr::EFun(arg, e) => {
                self.env.new_enclosed_env();
                let ty = self.newTVar();
                self.env.insert(arg.to_string(), ty.clone());
                let result_ty = self.typeinfer_expr(e)?;
                self.env = *self.env.outer.clone().unwrap();
                Ok(t_fun(ty, result_ty))
            }

cloneが多くて何とかしたいです...
TypeEnvの定義を変えて、

struct TypeEnv {
    env: HashMap<String, Type>,
    outer: Option<Box<TypeEnv>>,
}

新しいメソッドを定義します。

    pub fn new_enclosed_env(&mut self) {
        self.outer = Some(Box::new(self.clone()));
        self.env = HashMap::new();
    }

getの方も修正

    pub fn get(&self, name: String) -> Result<Type, TypeInferError> {
        match self.env.get(&name) {
            Some(ty) => Ok(ty.clone()),
            None => match &self.outer {
                None => Err(TypeInferError::UndefinedVariable(name)),
                Some(env) => env.get(name),
            },
        }
    }

関数定義の評価

続いて評価の方の実装をする。
まずEval型のenvをRc<Refcell<..>>で包む。

pub struct Eval {
    env: Rc<RefCell<Environment>>,
}

そして、Environmentにouterを追加する。

impl Environment {
    pub fn new() -> Self {
        Environment {
            env: HashMap::new(),
            outer: None,
        }
    }
    pub fn get(&self, name: String) -> Result<Value, EvalError> {
        match self.env.get(&name) {
            Some(value) => Ok(value.clone()),
            None => match &self.outer {
                None => Err(EvalError::UndefinedVariable(name)),
                Some(env) => env.borrow().get(name),
            },
        }
    }
    pub fn insert(&mut self, name: String, val: Value) {
        self.env.insert(name, val);
    }
    pub fn new_enclosed_env(env: Rc<RefCell<Environment>>) -> Self {
        Environment {
            env: HashMap::new(),
            outer: Some(env),
        }
    }
}

(Rustでの『Go言語で作るインタプリタ』のネット上での実装を真似した)
このRc<RefCell<..>>を使ったやり方で、型推論の方も書き直してみる。

pub struct TypeInfer {
    env: Rc<RefCell<TypeEnv>>,
    unassigned_num: u64,
}
struct TypeEnv {
    env: HashMap<String, Type>,
    outer: Option<Rc<RefCell<TypeEnv>>>,
}
impl TypeInfer {
    fn from(env: TypeEnv, unassigned_num: u64) -> Self {
        TypeInfer {
            env: Rc::new(RefCell::new(env)),
            unassigned_num,
        }
    }
    pub fn typeinfer_expr(&mut self, ast: &Expr) -> Result<Type, TypeInferError> {
    ... {
            Expr::EFun(arg, e) => {
                let mut typeinfer = TypeInfer::from(
                    TypeEnv::new_enclosed_env(Rc::clone(&self.env)),
                    self.unassigned_num,
                );
                let ty = self.newTVar();
                typeinfer
                    .env
                    .borrow_mut()
                    .insert(arg.to_string(), ty.clone());
                let result_ty = typeinfer.typeinfer_expr(e)?;
                self.unassigned_num = typeinfer.unassigned_num;
                Ok(t_fun(ty, result_ty))
            }
	}
    }
}

関数適用のパーサーの定義

pub fn fun_app(input: &str) -> IResult<&str, Expr> {
    let (input, e) = alt((delimited(symbol("("), parser_expr, symbol(")")), |input| {
        let (input, ident) = identifier(input)?;
        Ok((input, Expr::EVar(ident)))
    }))(input)?;
    let (input, _) = symbol("(")(input)?;
    let (input, args) = separated_list0(symbol(","), parser_expr)(input)?;
    let (input, _) = symbol(")")(input)?;
    Ok((
        input,
        args.iter()
            .fold(e, |acc, expr| e_fun_app(acc, expr.clone())),
    ))
}

関数適用の型推論

            Expr::EFunApp(e1, e2) => {
                let t1 = self.typeinfer_expr(e1)?;
                let t2 = self.typeinfer_expr(e2)?;
                let t3 = self.newTVar();
                unify(t1, t_fun(t2, t3.clone()))?;
                Ok(t3)
            }

簡単ですね！
replで実験していたら奇妙なバグを発見した

Welcome to lunalang repl!
>>let id(x) = x;
>>:t id  
a1 -> a1
>>:t id(3)
a1
>>:t id(3)
Int
>>

一回目の:t id(3)でもIntと表示されるはずが何故かa1になってしまっている...

            Expr::EFun(arg, e) => {
                let mut typeinfer = TypeInfer::from(
                    TypeEnv::new_enclosed_env(Rc::clone(&self.env)),
                    self.unassigned_num,
                );
                let ty = typeinfer.newTVar(); //ここがself.newTVar()になっていたのが原因
                typeinfer
                    .env
                    .borrow_mut()
                    .insert(arg.to_string(), ty.clone());
                let result_ty = typeinfer.typeinfer_expr(e)?;
                self.unassigned_num = typeinfer.unassigned_num;
                Ok(t_fun(ty, result_ty))
            }

直った
もう一つバグを発見

>>let f(x) = x(x);

この入力がType Errorにならない(occur errorになるはず)

関数適用の評価

関数適用の評価の本体

             )),
+            Expr::EFunApp(e1, e2) => {
+                let v1 = self.eval_expr(*e1)?;
+                let v2 = self.eval_expr(*e2)?;
+                match v1 {
+                    Value::VFun(arg, expr, env) => {
+                        let eval = Eval::from(env);
+                        eval.env.borrow_mut().insert(arg, v2);
+                        eval.eval_expr(expr)
+                    }
+                    _ => Err(EvalError::InternalTypeError),
+                }
+            }
         }

Eval::fromは次のような実装となっている

+    fn from(env: Environment) -> Eval {
+        Eval {
+            env: Rc::new(RefCell::new(env)),
+        }
+    }

これで、再帰関数や高階関数も動く。

Welcome to lunalang repl!
>>let fib(n) = if (n==1) 1 else if (n==2) 1 else fib(n-1) + fib(n-2);
>>fib(10)
Ok(VInt(55))
>>let double(f, x) = f(f(x));
>>double(fib, 3)
Ok(VInt(1))
>>let succ(n) = n+1;
>>double(succ, 3)
Ok(VInt(5))

ついでにテストを見やすくした。

バグの修正

>>let f(x) = x(x);

これがエラーにならないバグを修正した。

             Ok((_, StatementOrExpr::Statement(stmt))) => {
-                repl.typeinfer.typeinfer_statement(&stmt);
-                repl.eval.eval_statement(stmt);
+                match repl.typeinfer.typeinfer_statement(&stmt) {
+                    Ok(()) => match repl.eval.eval_statement(stmt) {
+                        Ok(()) => (),
+                        Err(err) => println!("eval error: {}", err),
+                    },
+                    Err(err) => println!("type error: {}", err),
+                }
             }

replでのStatementOrExprのStatement側での処理にて、typeinferのtype errorが無視されていたのが原因だった。

次回の目標

リファクタリング
文字列型を追加する