星にゃーん(@takoeight0821)です。 HaskellとかSF小説とかが好きです。
今日は自作言語Malgoの話をします。 https://github.com/malgo-lang/malgo
この発表は『第39回 #hiro_it』と『プログラミング言語処理系が好きな人の集まり 第3回定期ミートアップ』での発表です。 日程が被ってしまったので、事前録画&2窓してます。
『プログラミング言語処理系が好きな人の集まり』は、
プログラミング言語処理系が好きな人の集まりは,言語処理系に関する話題ならなんでもありなSlackワークスペースです.
です。 https://prog-lang-sys-ja-slack.github.io/wiki/
『#hiro_it』は、
#hiro_itは広島で開催する学生向けのITコミュニティです.
です。 https://hiro-it.connpass.com/
Malgoには、型の別名(型シノニム)を定義する機能があります。
type MyInt = Int32
type MyTuple a = (a, a)
このように型シノニムを定義すると、MyInt
とInt32
が同じ型として扱われます。
MyTuple MyInt
は(MyInt, MyInt)
であり(Int32, Int32)
です。
型シノニムの実装にバグがあったというのが今回の最初の話題なのですが、その前にすこし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
がわかる
型シノニムの(バグってた)実装では、α ~ β -> γ
など型制約に加えて、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周りの構文を大規模に改修して、こんな構文を定義しました。
module { putStrLn, appendString } = import Prelude;
こう書くと、putStrLn
とappendString
のみがインポートされます。
また、
module {..} = import Prelude;
と書くと、今まで通りPrelude
内のすべての型・関数がインポートされます。
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文をより便利にしました