🙌
Rustで作る自作言語(10) 代数的データ型
代数的データ型の定義の文法
代数的データ型は次のように定義します。
enum Hoge {
Foo(Int, String),
Bar
};
このASTは、次のように定義しました。
#[derive(PartialEq, Eq, Debug, Clone)]
pub enum Statement {
Assign(String, Expr),
TypeDef(String, Vec<ConstructorDef>),
}
#[derive(PartialEq, Eq, Debug, Clone)]
pub struct ConstructorDef {
pub name: String,
pub args: Vec<Type>,
}
代数的データ型の定義文のパーサー
pub fn statement_typedef(input: &str) -> IResult<&str, Statement> {
let (input, _) = keyword("enum")(input)?;
let (input, id) = identifier_start_with_capital(input)?;
let (input, _) = symbol("{")(input)?;
let (input, constructors) = separated_list0(symbol(","), |input| {
let (input, name) = identifier_start_with_capital(input)?;
let (input, args) = opt(|input| {
let (input, _) = symbol("(")(input)?;
let (input, args) = separated_list0(symbol(","), parser_type)(input)?;
let (input, _) = symbol(")")(input)?;
Ok((input, args))
})(input)?;
match args {
Some(args) => Ok((input, ConstructorDef { name, args })),
None => Ok((input, ConstructorDef { name, args: vec![] })),
}
})(input)?;
let (input, _) = symbol("}")(input)?;
let (input, _) = symbol(";")(input)?;
Ok((input, Statement::TypeDef(id, constructors)))
}
parser_type関数は、型のパーサーである。
pub fn parser_type(input: &str) -> IResult<&str, Type> {
let (input, id) = identifier_start_with_capital(input)?;
Ok((input, Type::TType(id)))
}
現状では関数の型->やVector型などに対応していない。
単相型
0引数の一般の単相型を次のように表すことにする。
pub enum Type {
TType(String),
}
これに伴い、StringやIntなどをType::TType("String".to_owned())やType::TType("Int".to_owned())に書き換える。
型定義の型推論部での処理
型定義のASTStatement::TypeDefは、typeinfer_statementメソッドにて次のような処理がなされる。
Statement::TypeDef(type_name, constructor_def_vec) => {
for ConstructorDef { name, args } in constructor_def_vec {
self.env.borrow_mut().insert(
name.to_owned(),
args.iter()
.rev()
.fold(Type::ttype(type_name), |acm, ty| t_fun(ty.clone(), acm)),
)
}
}
具体的には、型定義で定義されている各コンストラクタを型環境に加えている。
例として、次のような型定義があった場合について考えてみる。
enum OptionInt {
Some(Int),
None
};
この場合、型環境にはSomeコンストラクタの型Int -> OptionIntとNoneコンストラクタの型OptionIntが加えられる。
型定義の評価部での処理
まずは、コンストラクタを表す値を定義する。
VConstructor(String, Vec<Value>),
そして、型定義のASTStatement::TypeDefの場合の処理をeval_statementメソッドに追加する。
Statement::TypeDef(_, constructor_def_vec) => {
for ConstructorDef { name, args } in constructor_def_vec {
self.env.borrow_mut().insert(
name.to_owned(),
Value::VConstructor(name.to_owned(), vec![]),
)
}
Ok(())
}
そして、関数適用の評価に、コンストラクタの場合を追加しておく。(コンストラクタはFoo(3)のように使われるので、構文解析すると関数適用として処理される。)
fn fun_app_helper(&self, v1: Value, v2: Value) -> Result<Value, EvalError> {
match v1 {
...
Value::VConstructor(name, args) => {
let mut mut_args = args;
mut_args.push(v2);
Ok(Value::VConstructor(name, mut_args))
}
_ => Err(EvalError::InternalTypeError),
}
}
型の構文解析
さて、今の所単純な型(IntやHoge等)のみしか構文解析出来ないのを、関数の型やVector型などを構文解析出来るようにしていく。(型変数を含む型については、代数的データ型で型変数を含む型が定義できるようにする拡張を施すときに一緒に構文解析を実装する。)
pub fn parser_type_init(input: &str) -> IResult<&str, Type> {
parser_fun_type(input)
}
pub fn parser_fun_type(input: &str) -> IResult<&str, Type> {
let (input, t1) = parser_type(input)?;
let (input, t2) = opt(|input| {
let (input, _) = symbol("->")(input)?;
let (input, t2) = parser_fun_type(input)?;
Ok((input, t2))
})(input)?;
match t2 {
Some(t2) => Ok((input, Type::TFun(Box::new(t1), Box::new(t2)))),
None => Ok((input, t1)),
}
}
pub fn parser_type(input: &str) -> IResult<&str, Type> {
alt((
delimited(symbol("("), parser_type_init, symbol(")")),
parser_ref_type,
parser_vector_type,
parser_simple_type,
parser_unit_type,
))(input)
}
まず、parser_type_initがエントリーポイントとなっている。そしてparser_fun_typeでは関数の型の構文解析がされる(->は右結合)。parser_typeでは、Unit型、Vector型、Ref型、普通の型(IntやHogeなど)、括弧で囲われた型の構文解析がなされる。
match式のAST
パターンマッチの式(match式と呼ぶことにします)の文法は次のようなものです。
(式) match {
(パターン) => (式),
...
(パターン) => (式)
}
match式のASTは次のようにしました。
pub enum Expr {
...
EMatch(Box<Expr>, Vec<(Pattern, Expr)>)
}
// Patternの定義
#[derive(PartialEq, Eq, Debug, Clone)]
pub enum Pattern {
PValue(Expr),
PConstructor(String, Vec<Pattern>),
PVar(String),
}
match式のパーサー
パターンマッチのパターンは(現状では)三種類あります。
- 値パターン
- コンストラクタパターン
- 変数パターン
値パターンはその名の通り3や()等の値のことです。コンストラクタパターンは、Some()等の代数的データ型のコンストラクタのことです。コンストラクタパターンは、その引数にパターンを持つ場合があります。変数パターンは、その変数に、マッチする値が格納されます。
それぞれのパーサーは次のようになります。
pub fn parser_pattern(input: &str) -> IResult<&str, Pattern> {
alt((
parser_constructor_pattern,
parser_variable_pattern,
parser_value_pattern,
))(input)
}
pub fn parser_variable_pattern(input: &str) -> IResult<&str, Pattern> {
let (input, var) = identifier(input)?;
Ok((input, Pattern::PVar(var)))
}
pub fn parser_value_pattern(input: &str) -> IResult<&str, Pattern> {
let (input, expr) = alt((expr_int, parser_unit))(input)?;
Ok((input, Pattern::PValue(expr)))
}
pub fn parser_constructor_pattern(input: &str) -> IResult<&str, Pattern> {
let (input, name) = identifier_start_with_capital(input)?;
let (input, args) = opt(|input| {
delimited(
symbol("("),
separated_list0(symbol(","), parser_pattern),
symbol(")"),
)(input)
})(input)?;
match args {
Some(args) => Ok((input, Pattern::PConstructor(name, args))),
None => Ok((input, Pattern::PConstructor(name, vec![]))),
}
}
match式の型推論
match式の型推論の大枠は次のようになります。
Expr::EMatch(expr, match_arms) => {
let ty = self.typeinfer_expr(expr)?;
if match_arms.len() == 0 {
return Ok(ty);
}
let result_ty = self.newTVar();
for (pattern, expr) in match_arms {
let mut typeinfer = TypeInfer::from(
TypeEnv::new_enclosed_env(Rc::clone(&self.env)),
self.unassigned_num,
self.level,
);
typeinfer.typeinfer_pattern(&pattern, &ty)?;
unify(&result_ty, &typeinfer.typeinfer_expr(expr)?)?;
self.unassigned_num = typeinfer.unassigned_num
}
Ok(result_ty)
}
typeinfer_patternメソッドは、そのパターンがexprの型にマッチするかを確認し、変数パターンが現れたときはその変数とその型を型環境に追加します。パターンマッチではマッチアームごとにスコープが切られるようになっています。
typeinfer_patternメソッドは次のようになります。
fn typeinfer_pattern(&mut self, pattern: &Pattern, ty: &Type) -> Result<(), TypeInferError> {
match pattern {
Pattern::PValue(value) => unify(&self.typeinfer_expr(value)?, ty)?,
Pattern::PConstructor(name, patterns) => {
let constructor_ty = self.env.borrow().get(&name)?;
let (args, result) = constructor_ty.separate_to_args_and_resulttype();
if args.len() != patterns.len() {
return Err(TypeInferError::InvalidArgumentPatternError(
args.len(),
patterns.len(),
));
}
for i in 0..args.len() {
self.typeinfer_pattern(&patterns[i], &args[i])?;
}
unify(&result, ty)?;
}
Pattern::PVar(var_name) => {
let new_type = self.newTVar();
unify(&new_type, ty)?;
self.env.borrow_mut().insert(var_name.clone(), new_type)
}
};
Ok(())
}
match式の評価
Expr::EMatch(expr, match_arms) => {
let expr = self.eval_expr(*expr)?;
for (pattern, expr_arm) in match_arms {
let eval = Eval::from(Environment::new_enclosed_env(Rc::clone(&self.env)));
if eval.expr_match_pattern(&expr, &pattern)? == true {
return eval.eval_expr(expr_arm);
}
}
Err(EvalError::NotMatchAnyPattern)
}
exprがpatternにマッチするかをチェックして、マッチする場合はマッチアームの中身の式を評価します。マッチアームごとにスコープを切っています。
パターンにマッチするかどうかを判断しているのは以下のメソッドです。
fn expr_match_pattern(&self, expr: &Value, pattern: &Pattern) -> Result<bool, EvalError> {
match pattern {
Pattern::PValue(value) => {
let value = self.eval_expr(value.clone())?;
Ok(value == *expr)
}
Pattern::PConstructor(name, patterns) => {
if let Value::VConstructor(constructor_name, args) = expr {
if constructor_name != name {
return Ok(false);
} else if patterns.len() != args.len() {
return Err(EvalError::InternalTypeError);
}
let mut result = true;
for i in 0..patterns.len() {
result = result && self.expr_match_pattern(&args[i], &patterns[i])?;
}
Ok(result)
} else {
Ok(false)
}
}
Pattern::PVar(var_name) => {
self.env.borrow_mut().insert(var_name.clone(), expr.clone());
Ok(true)
}
}
}
まとめ
以上で代数的データ型と、パターンマッチが実装できました。次回は、この型システムを構造的型システムに変更していきたいと思います。
Discussion