「あの人も読んでる」略して「も読」。さまざまな寄稿者が最近気になった情報や話題をシェアする企画です。他のテックな人たちがどんな情報を追っているのか、ちょっと覗いてみませんか？
そろそろ職種が疑われるんじゃないかとヒヤヒヤしているしゅんそくです。
『型システムのしくみ』を読んでいます
『型システムのしくみ』という本を読んでいます。（7割程度読了）
型システムのしくみ ― TypeScriptで実装しながら学ぶ型とプログラミング言語
この書籍では、TypeScriptを用いて小規模なインタプリタの型検査器を段階的に実装していきます。構文対応を一歩ずつ進める構成になっており、非常に読みやすく、型システムの導入過程を丁寧に追える良書です。なお、身近な型検査器としては、Rubyの Sorbet や Python の mypy が該当します。
ただし、プログラミング言語の実行システム（言語処理系）を知っていることが前提になるので、初心者の場合はまず一冊インタプリタの自作本を買うと良いかもしれません。
インタプリタの作り方 －言語設計／開発の基本と2つの方式による実装－
この本はTypeScriptで実装されているのですが、Rustとかで実装してくれていると読みやすいのになーと思いました。エンジニアが思ったらするべきことはただ一つです。そう、実装です。
というわけで次の章からRustで入門する方法を解説します。
Rustで型システムに入門する（準備編）
インタープリタを自作して用意しましょう。
実のところ、『型システムの仕組み』を勉強するだけであればParser （入力したプログラムを木構造にしたものを生成するシステム）まで作れば十分です。今回は気分が乗ったので全部作りました。
fn main() {
let args: Vec<String> = env::args().collect();
println!("{}", format_args!("{:?}", args));
let tokens: Vec<Token> = Tokenizer::tokenize(args[1].as_str()).unwrap_or_else(|e| {
eprintln!("{}", tokenize_error_to_message(e));
exit(1)
});
println!("{:?}", tokens);
let ast: Stmt = Parser::new(tokens).parse().unwrap_or_else(|e| {
eprintln!("[Parse Error] {}", parse_error_to_message(e));
exit(1)
});
println!("{:?}", ast.clone());
let mut compiler: Compiler = Compiler::new();
let opcodes: Vec<OpCode> = compiler.compile_stmt(ast).unwrap_or_else(|e| {
eprintln!("[Compile Error] {}", compile_error_to_message(e));
exit(1)
});
println!("{:?}", opcodes.clone());
let mut vm = VM::new(opcodes);
let result = vm.run().unwrap_or_else(|e| {
eprintln!("[Runtime Error] {}", runtime_error_to_message(e));
exit(1)
});
println!("{:?}", result.unwrap());
exit(0);
}
次のような構文が動きます。
true ? 1 : 0
次の構文はエラーになります。
1 ? 0.0 : 0 // Runtime Error
condの部分の評価でBoolのみを許可しているからです。具体的には次のように定義されています。
fn evaluate_condition(obj: TinyObject) -> Result<bool, RuntimeError> {
match obj {
TinyObject::Bool(b) => Ok(b),
_ => Err(RuntimeError::InvalidOperation(
format!("Cond Expr must be bool: {:?}", obj).to_string(),
)),
}
}
同様に次の構文もエラーにしました。（TypeScriptでも許可されていないそうです）
true + 1 // Runtime Error
というわけで足し算の命令もホワイトリスト形式で定義しています。
OpCode::Add => {
let b = self.stack.pop().ok_or(RuntimeError::StackUnderflow)?;
let a = self.stack.pop().ok_or(RuntimeError::StackUnderflow)?;
match (a, b) {
(TinyObject::Int(a), TinyObject::Int(b)) => {
self.stack.push(TinyObject::Int(a + b));
}
(TinyObject::Float(a), TinyObject::Int(b)) => {
self.stack.push(TinyObject::Float(a + b as f32));
}
(TinyObject::Int(a), TinyObject::Float(b)) => {
self.stack.push(TinyObject::Float(a as f32 + b));
}
(TinyObject::Float(a), TinyObject::Float(b)) => {
self.stack.push(TinyObject::Float(a + b));
}
(a, b) => return Err(RuntimeError::InvalidOperation(
format!("Execute the Add operation for undefined type combinations. {:?} {:?}", a, b)
)),
}
self.pc += 1;
}
現在はVM実行時に型エラーが発生しますが、型システムを導入することで実行前にこうした不正なプログラムを検出可能になります。
繰り返しにはなりますが、詳細は次の本を参考にしてください。
インタプリタの作り方 －言語設計／開発の基本と2つの方式による実装－
Rustで型システムに入門する （実践編）
目標は main.rs に次のようなコードを追加することです。
TypeChecker::typecheck(ast.clone()).unwrap_or_else(|e| {
eprintln!("[TypeCheck Error] {}", typecheck_error_to_message(e));
exit(1)
});
そのためにTypeCheckerという構造体を作成し、typecheckというメソッドを関連付けます。
まず、TypeCheckerで利用する型の一覧の型がほしいので作成します。
type Type =
| { tag: "Boolean" }
| { tag: "Number" };
本では、このようにBooleanとNumberの2つになっています。TypeScriptではNumber型がありますが、Rustの場合はこれがいわゆるInteger型とFloat型に分かれているため、下記の通り、3つの型を書きます。
#[derive(PartialEq)]
pub enum TinyType {
Int,
Float,
Bool,
}
次にTypeCheckerが返すエラー型とヘルパーを定義します。本の実装では次の関数を呼び出している部分に相当します。
export function error(msg: string, node: any): never {
if (node.loc) {
const { start, end } = node.loc;
throw new Error(`test.ts:${start.line}:${start.column + 1}-${end.line}:${end.column + 1} ${msg}`);
} else {
throw new Error(msg);
}
}
今回はTypeCheckErrorという名前を使いました。
pub enum TypeCheckError {
CondMustBeBool,
TernaryReturnsTypeMustBeSame,
UndefinedOperation,
}
pub fn typecheck_error_to_message(e: TypeCheckError) -> String {
match e {
TypeCheckError::TernaryReturnsTypeMustBeSame => {
"ternary return type must be same".to_string()
}
TypeCheckError::CondMustBeBool => "condition value must be bool".to_string(),
TypeCheckError::UndefinedOperation => "you are trying undefined operation".to_string(),
}
}
余談ですが、TypeCheckErrorという名前は僕が好きなPythonライブラリのTypeGuardと同じなんですよね。TypeGuardは実行時チェックのライブラリですが、あこがれのライブラリと同じ名前を付けるのは素敵な体験だなぁと思いました。
最後に本体を実装します。書籍ではTermが使われていますが、私が初学者で誤用しそうな背景から名称をASTの要素名に変更しています。ネストが深くならないように関数に切り出していますが、基本的に本文と同じ方針の実装をしています。
pub struct TypeChecker {}
impl TypeChecker {
pub fn typecheck(ast: Stmt) -> Result<Option<TinyType>, TypeCheckError> {
match ast {
Stmt::Expr(expr) => Ok(Some(Self::typecheck_expr(expr)?)),
}
}
fn typecheck_expr(expr: Expr) -> Result<TinyType, TypeCheckError> {
match expr {
Expr::Bool(_) => Ok(TinyType::Bool),
Expr::Float(_) => Ok(TinyType::Float),
Expr::Int(_) => Ok(TinyType::Int),
Expr::If { cond, thn, els } => Ok(Self::typecheck_if(*cond, *thn, *els)?),
Expr::BinOp(op) => Ok(Self::typecheck_binop(*op)?),
}
}
fn typecheck_if(cond: Expr, thn: Expr, els: Expr) -> Result<TinyType, TypeCheckError> {
let cond: TinyType = Self::typecheck_expr(cond)?;
if cond != TinyType::Bool {
return Err(TypeCheckError::CondMustBeBool);
}
let thn: TinyType = Self::typecheck_expr(thn)?;
let els: TinyType = Self::typecheck_expr(els)?;
if thn != els {
return Err(TypeCheckError::TernaryReturnsTypeMustBeSame);
}
Ok(thn)
}
fn typecheck_binop(op: BinaryOperation) -> Result<TinyType, TypeCheckError> {
match op {
BinaryOperation::Add { left, right } => {
let left: TinyType = Self::typecheck_expr(*left)?;
let right: TinyType = Self::typecheck_expr(*right)?;
match (left, right) {
(TinyType::Float, TinyType::Float)
| (TinyType::Int, TinyType::Float)
| (TinyType::Float, TinyType::Int) => Ok(TinyType::Float),
(TinyType::Int, TinyType::Int) => Ok(TinyType::Int),
_ => Err(TypeCheckError::UndefinedOperation),
}
}
}
}
}
最後に実行してTypeCheckErrorになるか検証してみます。
エラーを発生させることができました!!
Rustの他にもHaskellなどの関数型言語だと比較的実装しやすいと思いますので皆さんも是非挑戦してみてください 💪💪💪