Genericsについてのメモ

遊びで作ってるFSharpっぽい言語のgoへのトランスパイラ、Folangで、雑にGenericsの対応をしていたが、タイプパラメータを変数に持たせるべきか型に持たせるべきか関数のコールのexprに持たせるべきかとかが一貫性が無い感じで、 どれが解決されていないのかとかもなんだか良く分からないmessyな感じになってしまった。 セルフホスト出来る最低限の実装くらいしかする気が無かったので目的は達成出来たのだけれど、 folang自身で再実装する前にもうちょっと良く考えてみよう、という気分になる。

別にこんな問題は世の中的にはすでに解決済みの領域なのでちゃんと調べれば答えはあるのだろうけれど、 調べて勉強したいというよりは、自分で考えてみたいという気がしている。 自分なりに考えたあとで答えを見る方が理解も深いし、何より楽しいしね。

という事で、用語や考えなどに誤りもあるだろうし考えもとっちらかってはいるが、とりあえず自分の現時点の理解を書き出す事で思考を深めてみよう。

IR上に存在するものには、全てタイプパラメータに型がassignされている

追記: これは多相ヴァリアントをサポートすると間違いである事が判明＞UnionのGenericsでは、assignされてないタイプパラメータを持つ変数がありうる

コード上では、すべてのタイプパラメータには型がassignされている。 ただしこのassignされている型は現在定義中の関数のtype parameterな事はある。

func hoge[T any]() {
  ika[T]() // ここではikaにとってはTという型がassignされている
}

この親のタイプパラメータがassignされているのとパラメータがassignされていない状態は区別して考えないといけなくて、 そしてassignされていない状態というのは実はコード上のどこにも無い、という気がする。 例えばikaのタイプパラメータがUなら、U=Tというassignが行われる（だからUというのが他の関数とかぶっていても問題が無い）.

当初は一番トップの定義のhogeの関数はtype parameterがassignされてないのでは？と思ったが、 パラメータやbodyをパースしている時点ではこれはassignされていると考える方がいいような気がしてきた。

そうすると、コードの中ではtype parameterがassignされていない状態というのは存在しない、という事になる。 すべての変数も関数もtype parameterは全てassignされている。

名前空間からlookupする所はtype parameterに型がassignされていない

けれどIR上以外ではtype parameterがassignされていない状態はある。

それがユーザー定義の型などを登録していく場所。

通常処理系は、ユーザー定義の型などが現れると、それを定義済みの型としてどこかに登録する。 そして型のパースなどでこの定義済みの型の中にあるものだったら、知っている型として処理する事になる。

このlookupする所には、まだtype parameterのassignされてないなにかが登録される事になる。 これは型というよりは、型のfactoryであって型では無い気もする、 少なくともコード上に存在するentityとしての型とは違うものだ。

このtype parameterのassignされてない型ファクトリは、定義済み型一覧の所（またはそれと同じようにアクセス出来る所）に登録される。 で、lookupされて使われる時にtype parameterが全てassignされて実際の型としてexprや変数などにつくようになる。

type parameterのassignされてない関数

関数についても同じような話がある。 関数が定義されると、定義済み関数の一覧に言語処理系は登録して、 コードの中で定義済み関数が出てきたら登録済み関数だと判断する事になる。

このlookupをする所でやはり全ての型パラメータになにかはassignされて、 それが一つ上の型パラメータになる。

例えば以下のような関数があった時に、

func hoge[T any] {
  ...
}

hogeというのはtype parameterのassignされてない関数として処理系には登録される。 だが、このhogeというのは定義された変数とは扱いが違う。

例えば以下のような事は出来ない。

a := hoge

普通の関数はhogeとして定義すればそれを変数として定義されていると処理出来るが、 genericな関数は変数としてスコープにいれるべきものでは無いように思う。 というのは、変数には型パラメータのassignされてない変数というのは存在しないので。

前の実装ではこのhogeを変数にしてスコープに登録していたので変な事になってしまった気がする。 lookupした時にはtype parameterはassignされてなくて良いのだが、 参照した瞬間には全てassignされる、で統一しないと変な事になるんじゃないか。

という事で次作る時はそう作ろう。

具体的な実装

具体的な処理としては、lookupしてgenericな型だった場合はその場でコンテキスト内に一意のtype parameterを割り当てて、 この割り当てたtype parameterの一覧が現在定義中の関数なり型なりのtype parameterになる、 という感じで処理するのが正しい気がする。

そのあと制約解消系が起動して解決出来た型は定義中関数のtype parameterからは消えてその解決された型に差し替わる。

この定義中関数のtype parameterへの引き上げは、golangなどの言語ではプログラマが手動でやっている事だが、 F#などは勝手に推論されてプログラマもなんのタイプパラメータがあるのか良く分からないまま関数は定義されていると思う。

「assignされてないtype parameterをIRに入れない」で統一する大切さ

現在の実装では、type parameterは関数しか対応していない（sliceなどは特別な型として扱っていて、それ以外のtype parameterのある型は未サポート）。

そしてこの（失敗した）実装では、VarとFunCallと関数の型（FFuncという名前）がそれぞれ型パラメータを持ってしまっていて、 しかもこれがassignされていたりされなかったりされているがそれが型パラメータだったりして良く分からない状態になっている。

どういう時にassignされてないんだろう？と考えていったら、 そもそもassignされてない状態は一箇所も無いように感じたので考え始めたのが今回のきっかけ。 VarもFunCallも型も、全部型パラメータはassignされている。

普通の関数は定義されるとVarに入れてスコープに追加していたが、genericな関数は変数としては扱わない方が良さそう。

まとめ

全ての変数やexprの型に、type parameterがassignされてない型は存在しない。 type parameterがassignされてないのは定義済みの型を登録する所だけで、それはtypeのfactoryとして振る舞い、typeでは無い。 type parameterがassignされている型はtype。