フィールドアクセスの型解決

Folangで型推論を書いていた所、フィールドアクセスの所がうまく書けない事に気づいたので考えている事のメモを。

問題のコード

以下のコードが動かない、というのが問題の発端。

package_info _ =
  let Head<T> : []T->T

type Item = {fs:string; f4:int}

let hello (items: []Item) = 
  let one = items |> Head
  one.fs

Headは型解決により Head: []Item->Item になるので、oneの型は Item になるから one.fs はstringになる、 というのが期待値だが、oneをパースしている時点でこれをどう扱うべきか？ という問題。

現状のアルゴリズムと動かない理由

現状はルートレベルのletの関数定義のbodyの中では、未定の型にはType Variableを割り当てて、 最後にunifyされるべき型同士の関係をまとめて解決をしている。 unifyは現時点ではイコールしか扱えない。

これをパースのあとにやっているため、one.fsの時点ではoneの型は分からない。 だからone.fsというフィールドアクセスの型が表現出来ない。

各exprごとに解決をしてやればoneの時点で型が確定するのでこの問題は解決出来るが、 そもそももっと一般的にどういう問題なのか、というのを考えたい。

型の依存

以下の部分で、

let one = items |> Head

型の割当としては、

• items []Item
• Head []T1->T1

と割り当てられて、oneにはT1がassignされる。

そして以下の部分で型をどう表現するか？というのが問題となる。

one.fs

one.fsにT2という型を割り当てるのはいいのだが、 このT2は何と等しくなるか？というと、「T1に”fs”というフィールドアクセスでアクセスした型」と等しくなる。

これまででもT2と[]T1が等しい、とかは扱ってきたが、 これらは引数がいらない。 でもフィールドアクセスは”fs”という文字列の引数が必要になる。

概念的には FieldAccess(T1, "fs") みたいな型であり、これとT2が等しい、というのが表現すべきものになる。

もっと一般的な表現にはならないか？

FieldAccess型というのはいかにも具体的すぎるので、 もう少し一般的に考えるなら、フィールドアクセスはT1と”fs”を引数に新しい型を返すもので、 さらにその型がT2と等しくないといけない。

• one.fsはT1と”fs”から型を返す何か、これをTF0と呼ぼう。
• T2 は TF0にT1と”fs”を渡して帰ってきた型と等しい

というような事が書けないといけない。

T2 = TF0(T1, "fs")

そしてこのTF0に相当する概念を記述する方法が現在の実装には無い。

これが難しいのは、単に型だけでは無くてフィールドの識別子、ここでは”fs”に相当する文字列の引数がある、という所だ。 スライスとかと違って単純なパターンマッチに出来ない。 一般的に定義するのはなかなか難しい。

フィールドアクセス専用の型というのは、型が解決されれば存在しないものだ。 けれど型解決のためには必要そうな気もする。

T1が解決した時にT2も解決された、と伝える必要があるので、T2はT1に依存している、 という事を表現する必要がある。 けれど現状はTF0に相当するものが無いので、イコールで関係を記述出来ない。

関数と変数のイコール、というのは一般的すぎる気がするな。

フィールドアクセス型を作るものなのかもしれない

書き始めた時はType VariableがなんかメタVariableみたいな感じでTypeを作り出す関数のようなものをサポートするのかと思っていたが、 ここまで書いてみると、本当に一般的なケースなんてあるのか？と疑問に思うようになってきた。

少し他のケースも考えてみたが、どうもこういう特殊な関係は、フィールドアクセスしか存在しないような気がしてきた。 単に解決されるまでしか存在しないフィールドアクセス型という特殊な型があればいいのでは？

Type Variableを置き換えるだけでは不十分になって、 置き換えたあとにFA型はレコードを見て解決する必要が出てくるが、 それくらいはやれそうな気がする。

Type Variable以外に最終的には現れない型がIRに入るのはなんか納得いかないが、 これだけなら作ればいいような気もする。

追記： 実装してみたらスライスとの等価がうまく扱えなかった

FA型を実装してみた所、以下みたいなケースが出てきて、

[]T1 = FA(T2, "nePair")

解決時にいつも左辺をType Variableにするようにしていたのだが、 このケースはそう出来ない、という事態になる。

新たなType Variable T3を割り振って、以下のような関係に直せば良さそうだが、

T3 = []T1
T3 = FA(T2, "nePair")

解決の途中に新しい変数を割り当てる、 というのは、計算が終わるか不安にもなるし、 少なくともこれまではやってないのでやれるように直さないといけない。

うーん、この路線でいいのかなぁ。

追記: Unionのマッチも同じようなのがあった

フィールドアクセスだけ特別扱いすればいいかと思って実装して試してみた所、Unionのマッチでも同じようなのにぶつかった。

package_info _ =
  let Head<T> : []T->T

type MyUni =
| MInt of int
| MStr of string

let hello (items: []MyUni) = 
  let one = items |> Head
  match one with
  | MInt a ->
    a+2
  | MStr _ ->
    1234

こういうような時に、oneにT1を割り振ると、 match one withの時点ではoneの型が決まってないので、 aの型はT2を割り振る事になる。 だがこのT2はT1と無関係では無い。

このT2はT1のUnionの中のMIntという奴の構成要素、という事が分かっているが、 単純なイコールでは表せない。 UnionのメンバをUMで表すと、

UM(T1,"MInt") = T2

となる。これも特別な型が必要になってしまう。 こういうのが当たる都度特別な型を手作業で作っていくのはやはり筋が良くない気がするなぁ。

でもレコード型で型を出す方法とUnion型で型を出す方法、全然違うからなぁ。

でも引数がType Variableと文字列で、解決すると型を出す所は一緒だ。 でもType Variableと文字列から型を出すロジックは全然違う。

FAとかUMという型の識別子と引き出す方法のfactoryみたいなのを組みて登録する、 とか仕組みを作る事は出来るかもしれないが。

おまけ：なぜ関数呼び出しにならないのか？

最初、フィールドの取得が関数呼び出しになれば単なる関数の解決に出来ないか？と思ったが、 これはならない。

例えば one.fs を GetField(one, "fs") に置き換えたらどうなるかを考えてみる。

このGetFieldの型はoneだけからは決まらない。”fs”の値による。 そしてこれを単なる文字列として関数に渡してしまうと、 パース時には関数の仕組みでは戻りの型が決定出来ない。

だから関数のType Parameterの解決の仕組みだけではこの問題はうまく解決出来ない。