github.com
はじめに
この記事は『第39回 #hiro_it』と『プログラミング言語処理系が好きな人の集まり 第３回定期ミートアップ』での発表資料を清書したものです。
『プログラミング言語処理系が好きな人の集まり』は、
プログラミング言語処理系が好きな人の集まりは，言語処理系に関する話題ならなんでもありなSlackワークスペースです．
です。
prog-lang-sys-ja-slack.github.io
『#hiro_it』は、
#hiro_itは広島で開催する学生向けのITコミュニティです．
です。
hiro-it.connpass.com
型シノニム
Malgoには、型の別名（型シノニム）を定義する機能があります。
type MyInt = Int32
type MyTuple a = (a, a)
このように型シノニムを定義すると、MyIntとInt32が同じ型として扱われます。
MyTuple MyIntは(MyInt, MyInt)であり(Int32, Int32)です。
型シノニムの実装にバグがあったというのが今回の最初の話題なのですが、その前にすこしMalgoの型検査について説明します。
Malgoの型推論のしくみ（簡単に）
Malgoは型推論を持ちます。例えば、
let x = (1, 2)
と書くと、xの型は(Int32, Int32)と推論されます。
addOne = { x -> x + 1 };
と書くと、addOneの型はInt32 -> Int32と推論されます。
addOneを例に、型推論の動作をざっくり述べると、
addOneの型を仮にαと置くxの型を仮にβと置くaddOne = { x -> ... }から、α ~ β -> γ（αとβ -> γは同じ型）だとわかるx + 1から、β ~ Int32とγ ~ Int32がわかるα ~ β -> γ, β ~ Int32, γ ~ Int32を解いてaddOne :: Int32 -> Int32, x :: Int32がわかる
Malgoの型シノニムのしくみ（バグってた）
型シノニムの（バグってた）実装では、α ~ β -> γなど型制約に加えて、MyInt ~ Int32を含めて解くことで実現していました。
この実装の問題点を明らかにするために、xの例を考えます。
let x = (1, 2)から、x :: (Int32, Int32)だとわかります。
そして、x :: MyTuple Int32やx :: MyTuple MyIntでもあってほしいわけです。
つまり、MyTuple α ~ (α, α)を含めて解かなければいけません。
(α, α)は、内部的にはTuple2 α αのような型として表されています。
MyTuple α ~ (α, α)はMyTuple α ~ Tuple2 α αという制約になります。
この制約は、~の左辺と右辺で項数が異なるため、簡単には解けそうにありません。
どうやら型シノニムを型制約として表すのは無理があるようです。（もしかしたらいいやり方があるかもしれませんが、見つけられませんでした）
結局、型制約を解く前に、型シノニムをすべて展開するように変更して解決しました。
(Int32, Int32) ~ MyTuple MyIntを(Int32, Int32) ~ (Int32, Int32)に展開すれば、この型制約の解は自明です。
「型シノニムは事前に展開する」というのは考えてみれば自然で簡単なんですが、
あんまり型シノニムを扱った型検査器の実装の話が見つからなくて苦労しました。
（結局GHCとかのコードを読んだ）
モジュール
Malgoはプログラムを分割するための機能としてモジュールを提供しています。
雰囲気としてはJavaのpackageと同じです。
今までのMalgoでは、例えばモジュールMainからPreludeをインポートしたいときには
module Main = {
import Prelude;
...
}
と書いていました。
今までのMalgoでは、import Prelude;と書くと、Preludeで定義されているすべての型・関数がMainの中に展開されたかのように振る舞います。これは明らかに不便です。例えば、同じ名前の関数を定義しているモジュールを複数インポートすると名前衝突を起こしてしまいます。
新しいimport文
importたるもの、「どの型・関数をインポートするか」ぐらいは指定できるようになっていて欲しいものです。
そこで、import周りの構文を大規模に改修して、こんな構文を定義しました。
module { putStrLn, appendString } = import Prelude;
こう書くと、putStrLnとappendStringのみがインポートされます。
また、
module {..} = import Prelude;
と書くと、今まで通りPrelude内のすべての型・関数がインポートされます。
（..を選んだのは、「省略している」雰囲気を重視したものです。Haskellのレコード展開の構文に影響を受けた気もします）
module P = import Prelude;
と書くと、P.putStrLnのように、モジュール名.名前とモジュール名のプレフィックスをつけることで参照できるようになります。
イメージはJavaScriptのrequireです。
名前解決のテーブルの設計
実装にあたって問題になったのは、名前解決のテーブルの設計でした。
今までは、
{ main -> [Main.main],
putStrLn -> [Prelude.putStrLn],
appendString -> [Prelude.appendString]
}
のような連想配列を使って、mainが出てきたらMain.mainに置き換え、putStrLnが出てきたらPrelude.putStrLnに置き換え……という実装でした。
Mainモジュール内でappendStringが定義されたら、
{ appendString -> [Main.appendString, Prelude.String] }
のようにエントリの先頭に新たな識別子を追加し、リストの先頭にあるものへ優先して置き換えることで、シャドウイングを実現していました。
しかし、新たなimportでは、P.putStrLnをPrelude.putStrLnに置き換えるような処理が必要になります。
そこで、
module { appendString } = import Prelude;
module P = import Prelude;
のとき、
{ main -> [implicit Main.main],
putStrLn -> [explicit as P Prelude.putStrLn],
appendString -> [implicit Prelude.appendString]
}
のように、「プレフィックスなしで参照できるか(implicit/explicit)」、「どんなプレフィックスで参照するか(as P)」をエントリに加えて、この情報をもとに名前解決するようにしました。
……と、ここまで書いて気づいたんですが、単に
{ main -> Main.main,
P.putStrLn -> Prelude.putStrLn,
appendString -> Prelude.appendString
}
としたほうが単純ですね。
まとめ
- 型シノニムの実装のバグを直しました
- import文をより便利にしました
