これはKMC Advent Calender 12/8の記事です。12日先の未来から投稿しています。
初めに
こんにちは、KMC（京大マイコンクラブ） 49代で1回生のakkeyです。
昨日12/7のアドベントカレンダーは、仕様と真面目に向き合う「Pietプログラミング」ガイドでした。昨日に引き続いて、言語処理系の記事ですね。
（追記）昨日12/7の記事は単語当てゲーム「ことのはたんご」で絶対に負けたくないでした。すみません。
最近「Rustでインタプリタを作りたい」という思いを抱いていたのですが、先日NF(京大の11月祭)が終わったのを機に思いを放出することにしました。
今までにC#, Python, Rustなどで何度か簡易的な動的型付けインタプリタ言語開発をしたことがあるので、今回は型推論を行う静的型付け言語を作ってみました。
ところで先日このような記事を見つけました。
競プロでしかUnionFindを見たことが無かった僕は、読んでいて面白かったので自分でも実装してみました。
今回作った言語はこちらです。
まだ開発経験が少なく、読みづらいコードになっていると思いますが、ご了承ください。また、理解が浅く、説明が間違っている可能性がありますが、その時は温かいご指摘を頂けると幸いです。
言語仕様
勉強用に作る簡易的静的型付け言語なので、扱えるものが圧倒的に少なく、実用からは程遠くなっています。
非純粋な関数型言語のような仕様になっています。
コメント記法
--で始まる行コメントのみが存在します。
-- これはコメントです
-- ここには何を書いても許されます
変数
let a = 0; -- 正格評価される変数
let x: Int = 34; -- 型を指定することもできる
-- `def`を用いて宣言された変数は遅延評価される
-- `forall`を用いる場合は`def`で宣言する必要がある
def undefined: forall a. a = undefined;
HM推論を完全に理解していないのと、多相型くらいは書いた方が人間にとって解りやすいのではないかという思想から、多相型は型を指定する必要があるという仕様になっています。
defで定義された変数は遅延評価されますが、評価された値はキャッシュされないので、毎度評価されます。
変数は全て不変で再代入は出来ませんが、シャドーイングは出来ます。
プログラムと型
数値型
24: Int;
12.25: Float;
文字列型
"hello": String;
"hello, " + "world"; -- = "hello, world"
リスト型
[1, 2, 4, 8]: [Int];
["a", "b", "c"]: [String];
[0, 1] + [2, 3]; -- = [0, 1, 2, 3]
Pair型とUnit型
-- 以下の2つの表記法は同じ意味で(Int, String, Float) = (Int, (String, Float))型
(3, "4", 5.0);
(3, ("4", 5.0));
,は()内のみで書ける右結合の二項演算子で(3, 4, 5)と(3, (4, 5))は同じ意味になります。つまり、Unit型と2つの値を取るタプル型(Pair型)しか存在していません。(Anteという言語の真似です)
分割代入などもできます。
let (x, y, z) = (0, 1, 2, 3);
-- x = 0
-- y = 1
-- z = (2, 3)
Unit型は以下のように書けます。
let (): () = ();
関数型
let add: Int -> Int -> Int = {\x y -> x + y};
add 3 5; -- => 8
let add2: (Int, Int) -> Int = {\(x, y) -> x + y};
add2 (3, 5); -- => 8
-- Scalaの部分適用に見た目が似た構文。
-- `{}`で囲まれた部分が暗黙的に引数を取るラムダ式となる
let add3: Int -> Int -> Int = {_ + _};
add3 3 5; -- => 8
-- 遅延評価演算子。Unit型を受け取る関数型に変換される。
'34: () -> Int;
F#のようなパイプライン演算子や、独特の記法の関数合成演算子があります。
4 |> print; -- print 4
print <| map f [0, 1, 2]; -- print ((map f) [0, 1, 2])
f .> g; -- {\x -> g (f x)}
g <. f; -- {\x -> g (f x)}
ifも構文としてでなく、関数として提供されていて、こんな感じに実行できます。
if (0 == 1) '"0 == 1" '"0 != 1"; -- => 0 != 1
型クラス
型を定義したり、型クラスを定義したり、型クラスのインスタンスを定義したりする文法はありませんが、型クラスを条件として指定する記法はあります。
def printTwice: forall a. Show a => a -> () = {\x ->
print x;
print x;
};
printTwice 34;
printTwice 3.4;
printTwice "Hoge";
printTwice [[0, 1, 2], [3, 4, 5]];
output
34
34
3.4
3.4
"Hoge"
"Hoge"
[[0, 1, 2], [3, 4, 5]]
[[0, 1, 2], [3, 4, 5]]
forallの付いた型は遅延評価されるdefでしか指定出来ないという仕様になっている理由は、型変数の型が確定してからでないと、型クラスの関数を呼び出すことが不可能だからです。
ちなみに余談ですが、この言語では、まだ型クラスのパラメータに、型コンストラクタを指定することが出来ないので、モナドは扱えません。
演算子
'以外の演算子は関数呼び出しのシンタックスシュガーになっていて、解釈の過程で展開されます。`で囲むことで、演算子を識別子として扱えます。
-- 実行結果は同じ
3 + 4;
`+` 3 4;
単項演算子の-や!は、それぞれ-_や!_のように展開されます。
レキサーの実装
レキサーはlogosを用いて作りました。
logosはトークンの定義に宣言型マクロを指定するだけで、レキサーが作れるので便利です。トークナイズしたあとで、キーワードを置換しています。（もっとスマートにキーワードを定義する方法があるような気はしますが、どんな機能があるのか、まだ完全に理解出来ていないので、このような形になっています）
レキサーとトークンの定義
use itertools::Itertools;
use logos::{Lexer, Logos};
use std::rc::Rc;
#[derive(Logos, Debug, PartialEq, Clone)]
#[logos(skip r"\s+")]
#[logos(skip r"--[^\n]*")]
pub enum Token {
#[regex("[0-9]+", |lex| Rc::from(lex.slice()))]
Int(Rc<str>),
#[regex(r"[0-9]+\.[0-9]+", |lex| Rc::from(lex.slice()))]
Float(Rc<str>),
#[regex(r#""([^"\\\x00-\x1F]|\\(["\\bnfrt/]|u[a-fA-F0-9]{4}))*""#, |lex| Rc::from(&lex.slice()[1..lex.slice().len()-1]))]
Str(Rc<str>),
#[token("(")]
ParenOpen,
#[token(")")]
ParenClose,
#[token("[")]
BracketOpen,
#[token("]")]
BracketClose,
#[token("{")]
BraceOpen,
#[token("}")]
BraceClose,
#[token("=>")]
BigArrow,
#[token("->")]
SmallArrow,
#[token(".>")]
CompositionRight,
#[token("<.")]
CompositionLeft,
#[token("|>")]
PipeRight,
#[token("<|")]
PipeLeft,
#[token("<<")]
ShiftLeft,
#[token(">>")]
ShiftRight,
#[token("||")]
DoublePipe,
#[token("|")]
Pipe,
#[token("&&")]
DoubleAmp,
#[token("&")]
Amp,
#[token(">=")]
GreaterEqual,
#[token("<=")]
LessEqual,
#[token(">")]
Greater,
#[token("<")]
Less,
#[token("==")]
DoubleEqual,
#[token("!=")]
NotEqual,
#[token("=")]
Equal,
#[token(";")]
Semicolon,
#[token(":")]
Colon,
#[token(",")]
Comma,
#[token(".")]
Dot,
#[token("#")]
Sharp,
#[token("!")]
Exclamation,
#[token("'")]
Apostrophe,
#[token("+")]
Plus,
#[token("-")]
Minus,
#[token("*")]
Mul,
#[token("/")]
Div,
#[token("%")]
Mod,
#[token("\\")]
Backslash,
#[regex(r"([[:alpha:]]|_)([[:alnum:]]|_)*|`[^`\\\x00-\x1F\s]*`", ident)]
Ident(Rc<str>),
Forall,
Let,
Def,
True,
False,
Underscore,
}
pub fn tokenize(src: &str) -> Option<Vec<Token>> {
Token::lexer(src)
.map_ok(|token| match token {
Token::Ident(word) if &*word == "forall" => Token::Forall,
Token::Ident(word) if &*word == "def" => Token::Def,
Token::Ident(word) if &*word == "let" => Token::Let,
Token::Ident(word) if &*word == "true" => Token::True,
Token::Ident(word) if &*word == "false" => Token::False,
Token::Ident(word) if &*word == "_" => Token::Underscore,
other => other,
})
.try_collect()
.ok()
}
fn ident<'s>(lex: &Lexer<'s, Token>) -> Rc<str> {
let s = lex.slice();
if s.starts_with('`') && s.ends_with('`') {
Rc::from(&s[1..s.len() - 1])
} else {
Rc::from(s)
}
}
パーサーを作る
パーサーはchumskyを用いて作りました。
chumskyは、parsecから影響を受けてそうなタイプのパーサージェネレーターです。Rustで似たようなパーサージェネレーターとして、他にnomやcombineがありますが、chumskyのメソッドが一番自分にとって書きやすそうに思えたので、何となくchumskyを使っています。
chumskyが提供している関数やマクロの中で、僕はselect!マクロを気に入っています。F#にあるfunction式に少し似ていますね。
let literal = select! {
Token::Int(n) => Expr::LitInt(n),
Token::Float(n) => Expr::LitFloat(n),
Token::Str(s) => Expr::LitStr(s),
Token::True => Expr::LitBool(true),
Token::False => Expr::LitBool(false),
}
.map(Rc::new);
その他にも、色々書きやすいメソッド群が存在しています。
ASTの定義
#[derive(Clone, PartialEq)]
pub enum Expr {
LitInt(Rc<str>),
LitFloat(Rc<str>),
LitStr(Rc<str>),
LitList(Vec<Rc<Expr>>),
LitBool(bool),
AppFun(Rc<Expr>, Rc<Expr>),
BinOp(Rc<Expr>, Token, Rc<Expr>),
UnOp(Token, Rc<Expr>),
Member(Rc<Expr>, Rc<str>),
Ident(Rc<str>),
Brace(Vec<Rc<Expr>>),
Unit,
Let(Rc<Pattern>, Rc<Expr>, Option<Rc<Kind>>),
Def(Rc<str>, Rc<Expr>, KindLike),
Lambda(Rc<Pattern>, Rc<Expr>),
ImplicitArg,
Typed(Rc<Expr>, Rc<Kind>),
}
#[derive(Clone, PartialEq, Eq)]
pub enum Kind {
Ident(Rc<str>),
App(Rc<Kind>, Rc<Kind>),
Arrow(Rc<Kind>, Rc<Kind>),
Unit,
Pair(Rc<Kind>, Rc<Kind>),
List(Rc<Kind>),
}
#[derive(Clone, PartialEq, Eq)]
pub struct Constraint {
pub type_class: Rc<str>,
pub args: Vec<Rc<Kind>>,
}
#[derive(Clone, PartialEq, Eq)]
pub struct KindLike {
pub bound_vars: Vec<Rc<str>>,
pub constraints: Vec<Constraint>,
pub kind: Rc<Kind>,
}
#[derive(Clone, PartialEq, Eq)]
pub enum Pattern {
Ident(Rc<str>),
Pair(Rc<Pattern>, Rc<Pattern>),
Wildcard,
Unit,
}
パーサーの定義は長いので割愛します。
chumskyには、ariadneというcrateと連携して構文エラーを解りやすく表示する機能があるのですが、時間が無くてエラーの表示までは実装できませんでした。
型推論
型システム
この言語の型システムは以下のように表せます（多分）。
\begin{eqnarray}
T &::=& \rightarrow \mid (~~,~~) \mid [~~] \mid \mathrm{Int} \mid \cdots \\
C &::=& \cdots \\
Q &::=& \epsilon \mid C\vec\tau \mid Q_1 \land Q_2 \\
\tau &::=& \alpha \mid T \vec\tau \\
\sigma &::=& \forall \vec\alpha .Q \Rightarrow \tau
\end{eqnarray}
それぞれ
$T$: 型コンストラクタ（0個以上の型を受け取り新たな型を作る、型の関数）
$C$: 型クラス
$Q$: 制約
$\tau$: 型
$\alpha$: 型変数
$\sigma$: 型スキーム
を表し、
$\vec \tau$などベクトルの記法が付いたものは0個以上であることを表します。
所謂「let多相」です（ただし、この言語では型スキームを指定した変数はdefで宣言する必要があるという仕様になっています）。
「型スキーム」という言葉は聞き慣れないかも知れません。型スキームは、型に$\forall$を付けたもので型と区別されています。let多相の言語では、束縛された変数にしか型スキームを指定出来ず、$\forall$が付いた型を持つ式というのは扱うことが出来ません。この言語の記法で書くならば、プログラム中に{\x -> x}のような式が登場しても、その型をforall a. a -> aとすることが出来ないということです。
型スキームと型を区別する理由は、$\forall$のついた型を認めてしまうと、決定的な型推論が出来ないからです。型スキームと型を区別した体系だと、サブタイピングのような概念がないなら、HM型推論(Algorithm W)で推論出来るそうです。
まあ、この言語では「forallを使う場合は、型スキームを明示する必要がある」というルールにしているので、もしかすると型と型スキームを区別せずとも、明示されていない部分を決定的に推論することが可能かも知れません。
型推論のアルゴリズム(Unify)
まず冒頭で示した記事にて紹介されていた部分を簡単に書こうと思います。
例として、以下のプログラムを例に考えてみましょう。繰り返しになりますが、この言語ではforallを使う場合は型スキームを明示する必要があるという仕様なので、以下の変数の型は、最終的にはf: Int -> Int, x: Intとなります。
let f = {\x -> x};
f 33;
まず、上から順に見て行って、型が解らないところはテキトーな型変数を置いてしまいます。
最初に、ここを解釈するにあたって
{\x -> x}
xの型がよく解らないのでx: t1と型変数を置きます。すると、{\x -> x}: t1 -> t1と解るので、
let f = {\x -> x};
の所でf: t1 -> t1と解ります。
次に
f 33;
の所ですが、fに対し、Int型の値を与えて何かしらの型の値を返していますね。ここではまだ、どんな型の値を返しているか解らないので、その型をt2と置きます。よって、f: Int -> t2, f 33: t2と解りました。
さてf: t1 -> t1とf: t2 -> Intとfの型について2通りの表し方が出来ましたが、この2つの型は同じになるはずです。そこで、t1 -> t1 = t2 -> Intという方程式を立てることで、型同士を統合(unify)していきます。
a -> bのような複合型の間になり立つ等式は、再帰的に小さな単位に分解できます。この過程でa -> b = Intのように絶対に成り立たない式が出てきたら、型エラーを吐いて終了します。
今回の場合は、t1 = t2とt1 = Intという式が成り立ちます。型変数同士の等式t1 = t2が出てきましたが、ここでUnionFindを使います。型変数を頂点とし、型変数同士が等しい場合に対応する頂点同士を辺で繋ぐ無向グラフを考えます。UnionFindを使えば、互いにpathで繋がった頂点の集合を一つのグループとしてグループ分けできるので、等しい型変数の集合が解ります。そして、そのグループのリーダー(UnionFindで得られる)と型を対応させることで、そのグループ内の型変数全てに型を割り当てられるという仕組みです。
多相のパラメータの推論
さて、この言語では型スキームは明示する必要があるということは散々繰り返しましたが、実はこの言語に多相のパラメータに代入する具体的な型を明示的に指定する手段はありません。つまり、パラメータに代入する型は推論する必要があります。どうやって推論するのでしょうか？
def id : forall a. a -> a = {\x -> x};
id 34;
id "ほげほげ";
id id : Int -> Int;
上を例に見ていきましょう。
idの型は御覧の通り$\forall a. a \rightarrow a$です。しかし、idが式として使われた瞬間に$\forall$が取り払われて、$a$には仮の型変数$t_1$が代入されます。その結果、以下のように仮の型付けがなされます。解りやすいように、idに対し添え字を振ると
id_1: t1 -> t1;
id_1 34: t2;
id_1: Int -> t2;
id_2: t3 -> t3;
id_2 "ほげほげ": t4;
id_2: String -> t4;
id_3: t5 -> t5;
id_4: t6 -> t6;
id_3 id_4: Int -> Int;
id_3: (t6 -> t6) -> (Int -> Int);
となり、以下のように推論されます。
t1 = t2 = Int
t3 = t4 = String
t5 = Int
t6 = (Int -> Int) -> (Int -> Int)
ではidの定義側では、どう推論するのが良いでしょうか？これは単純に$\forall$を外すだけで良いです。定義側では
id: a -> a = {\x -> x};
として推論されます。
型クラス
以下のような型クラスがあります。
（現状、この言語には型クラスを定義する構文は無いのでイメージです）
class Add a = {
`+`: a -> a -> a
};
instance Add Int;
instance Add Float;
instance Add String;
-- etc --
以下のような足し算の型推論をすることを考えましょう。
let addInt1 = {_ + 1};
let addFloat1 = {_ + 1.0};
let addString1 = {_ + "1"};
これも、先ほどの多相型のように推論することが出来ます。
型推論をするときは、
def `+` : forall a. a -> a -> a;
が存在することだけを考えて型推論を行い、aに代入される型が判明した後で、Add aを満たすかを調べれば良いわけです。
以下のような制約付きの関数も同様に出来ます。
def sum: forall a. Add a => a -> [a] -> a = foldl {_ + _};
sum 0 [1, 2, 4];
sum 0.0 [1.1, 2.2, 4.4];
sum "" ["a", "b", "c"];
インスタンスについても同様です。
instance Show a => Show [a];
print [[], [[]], [[], [[()]]]];
-- => [[], [[]], [[], [[()]]]]
実行
ASTをトップダウンに解釈するだけです。特に最適化などをしておらず、デシュガーされたASTをそのまま実行します。
まあ、Rustで実行するし、特に速さなんて求めていないので、これで良いでしょう。
試しにFizzBuzzを実行してみます。
let fizz_buzz = {\i ->
if (i % 15 == 0) '"FizzBuzz"
'(if (i % 3 == 0) '"Fizz"
'(if (i % 5 == 0) '"Buzz"
'(show i)))
};
def range = {\s e ->
if (s == e) '[]
'([s] + range(s + 1) e)
};
range 1 25 |> map fizz_buzz |> print
雑に再帰していますが、これで良いでしょう。では実行してみましょう。
thread '<unknown>' (17568) has overflowed its stack
え？何かが見えた気がしますが、きっと気のせいでしょう。もう一回実行してみます。
thread '<unknown>' (30972) has overflowed its stack
う……気のせいでは無いようです。これでは雑魚過ぎるので、スタックのサイズを16MiBに拡張してみます。
["1", "2", "Fizz", "4", "Buzz", "Fizz", "7", "8", "Fizz", "Buzz", "11", "Fizz", "13", "14", "FizzBuzz", "16", "17", "Fizz", "19", "Buzz", "Fizz", "22", "23", "Fizz"]
今度は問題なく実行できました。
次はループ回数を500回にしてみます。
range 1 500 |> map fizz_buzz |> print
thread '<unknown>' (14052) has overflowed its stack
うーむ……
末尾再帰最適化とかしてないし（そもそも末尾再帰ではないし）、スタックを食いつぶすことは解っていたのですが、500回程度のループで死ぬとか、いくら何でも雑魚過ぎませんか！？この程度で死んでいたら「チューリング完全」と称して良いかも、判らなくなります。
原因は恐らく単純にASTを巡って実行しているせいなので、実行用コードを生成して、ヒープ領域をスタックとして使うなどすれば解決するような気がします。
まあ、この記事は型推論を行うことがメインなので、実行用コード生成は気が向いたら実装しようと思います。
おわりに
以上、「Rustで型推論を行うオレオレ静的型付け非純粋関数型言語のインタプリタを作ってみた」でした。なんか500回程度のループで死んでいる言語をプログラミング言語呼ばわりしているのはタイトル詐欺っぽいですが、クリスマスも迫ってきたので、ここで終わりにします。
明日12/9のKMCアドベントカレンダーはRust製ゲームエンジンBevy 0.17で、ゼロから落ち物パズルを実装するです。今日に引き続き、明日もRustですね。話題のBevyエンジンが使われていて読んでいて、面白かったです。
最後になりましたが、アドベントカレンダー、遅れてしまいすみませんでした！
参考にさせて頂いた文献
https://keens.github.io/blog/2019/12/08/tetsuzukigatanoudekatasuironwojissoushitemita/
https://mizunashi-mana.github.io/blog/posts/2022/08/hm-type-system/
https://qiita.com/uint256_t/items/7d8c8feeffc03b388825