型推論のメリット

あまり知られていない Frege (あるいは Haskell) の利点として、型推論の方式が挙げられます。あまり知られていない理由のひとつは、数多の言語がそのファクトシートで型推論に触れているせいで、みな型推論を見ても面白い機能だと思わないからです。しかしながら型推論と一口に言っても、その意味するところは何も述べていないものからあらゆる内容を包含しているものまで様々です。

いくつかの言語では単に、変数の定義と代入が同じ行で行われる時に型宣言を繰り返す必要がないことを指して型推論と呼んでいます。
また別の言語では、型システムがリテラルによって宣言された変数の型を推論できることを指して型推論と呼んでいます。
いくつかの型システムでは、引数の型が与えられている時に戻り値となる式の型を局所的に推論できます。
Frege が属する ML 系の言語では、ヒンドリー・ミルナー型システムを活用します。これらの言語ではプログラム自体が式を組み合わせて作られており、プログラム中のすべての式ひとつひとつの型を、プログラム全体に至るまで、大域的 に推論することができます。型推論のためにプログラマ側からのヒントが必要となるのは、高階型が含まれるような極めて特殊な場合のみです。

それでは、このことがなぜ大きな違いを生むのかを例で見てみましょう。

最初はシンプルに

スタート地点となるもっとも簡単な例は、f x すなわち単に関数 f を x に一度適用するというものでしょう。この関数 (once とします) を f x で定義すれば、Frege がこの関数に対してどのような型を推論するか確認できます。

単純な定義

once f x = f x

REPL なら :type once、Eclipse プラグインなら Ctrl + Space で推論された型を確認することができます。また、fregedoc ツールにより生成される API ドキュメントにも推論された型が記載されます。

推論された型

once :: (b->a) -> b -> a

ここでは以下のような解釈が行われています。f x からわかるのは f が関数であるということだけです。関数 f は引数 x をひとつ取ります。x にも f x の戻り値にも型の制約は要求されていないため、単に型変数 a および b として扱われます。

f が型 b → a を持つため、結果として once のひとつめの引数の型は b → a であり、ふたつめの引数 x の型は (f に渡されているため) b でなくてはならず、once の戻り値の型は f の戻り値と等しくなくてはならないため a となります。

Frege が推論する型は可能な限り多相的になります。しかしこの多相性を 増やしたり減らしたり するとどうなるでしょう？

もっと多相的に、あるいは非多相的に

上記のコードでは、型はまったく宣言せず型推論器に任せています。しかし必要であれば自分自身で型を宣言することも可能で、またそのほうがよい理由もいくつか存在します。

型宣言を含めて定義した例

once :: (b->a) -> b -> a
once f x = f x

まず明らかな利点として、コードを読んだ人が、IDE や REPL、あるいは API ドキュメントを確認するまでもなく即座に型がわかります。型宣言は、once がどんな型の上で定義されており、特定の型の引数を与えた時に戻り値として何を返すか (f の戻り値の型と同じ) を示す、一種の内部的なドキュメントとなっています。

しかし、より特殊化、すなわち非多相化することも可能です。Int を取って String を返す関数だけを考えればよいとしましょう。実装は先ほどの例と完全に同じですが、型宣言によって関数が単相 (monomorphic、mono は one、morph は form を意味する) になっています。

非多相化 (単相化) した例

once :: (Int->String) -> Int -> String
once f x = f x

ここで面白いのは、何にせよ型推論器は、実装されたコードが与えられた型宣言に合うようコンパイルできるかどうかを検査しているという点です。もし合わなければエラーになります。型を明示的に宣言する場合、一貫性が保たれていれば特殊化 (より非多相的に) するのは問題ありませんが、一般化 (より多相的に) することはできません。

結局のところ、このような表面上は単純に見える例であっても、最初に考えるほど簡単ではないということです。また少し拡張を施すことでさらにチャレンジングなものにすらなります。

若干の拡張

f を x に 1 回ではなく 2 回適用する以外は once と同じように動作する関数 twice を作りたいとしましょう。

f を 2 回適用する関数

twice f x = f (f x)

今回は f を x だけではなく f x の 戻り値 にも適用するため、f xの戻り値の型は x の型と等しくなる必要があるのは明らかですね？

目が回る？

ここの理屈は頭が痛くなっても無理がありません。落ち着いて、意味がわかるまで読み直してみましょう。

言い換えれば、twice の型は

twice :: (a->a) -> a -> a

でなくてはならず、型システムはまさにこの型を推論してくれます。やったね！

もし間違えてしまったら？

型推論器が頭の痛い問題を我々の代わりに引き受けてくれるのは結構なことですが、もし何らかの原因で間違えて、以下のような問題のある型宣言を書いてしまった場合はどうなるでしょうか？

問題のある型宣言

falseTwice :: (b->a) -> b -> a
falseTwice f x = f (f x)

はい、このような場合であっても Frege が我々を失望させることはありません。どこで間違えたのかについて非常に詳細な説明を表示してくれます。先ほどの例で出力されるメッセージを見てみましょう。

上の例に対するエラーメッセージ

E <console>.fr:7: type error in expression f x
    type is : a
    expected: b

Frege は式 f x を間違いとして指摘しています。これは f x の型シグネチャで (b→a) を宣言しており、したがってf x の型が a になるためです。

しかし型推論器は、式 f (f x) の外側の f の第一引数として扱われていることから、f x の型はb であると推論します。

エラーメッセージを読み解く

Haskell や Frege のような型推論を持つ言語は、例えば Java などとは違ってわかりづらいエラーメッセージを表示するという悪名が知られています。そしてこれは事実です。

この理由の一端は、型推論が「宣言から実装」の順でコードを検査するだけでなく、逆向きにも検査を行っていることにあります。コードは徹底的すぎるほど精査されるのです。しかし不整合が発見される際、宣言と実装とのどちらが間違っているとは言い難い場合がしばしばあります。

しかしながらこの件は継続的改善の最中であり、Frege プロジェクトチームは改善の余地があるエラーメッセージ例の報告を歓迎しています。

究極の型推論

型推論が行われる例として、QuickCheck に勝るものはありません。

明示的な型シグニチャなしで twice を実装したとしましょう。次に、2 回適用するための関数が必要ですが、ここではプレフィックスを付けられる型なら何でもプレフィックスを付けるような関数を使ってみましょう。つまりこんな感じ。

プレフィックス関数

prefix front x = front ++ x

プレフィックスを付ける対象が 何であるか について、人間が考えるのではなく、ここで使用できるであろう最も一般的な型を Frege に判断させます。

マニア向け

Frege は prefix 関数に対してちょっとびっくりするような型 ListSemigroup b ⇒ b a → b a → b a を推論しますが、さしあたりここでは無視します。文字列や任意のリストのような、++ で連接できるようなものを表す代数的な型であるとだけ述べておきましょう。

それではここで、ランダムな入力に対して常に満たされるべき性質を定義しましょう。すなわち twice は任意の関数を 2 回 適用すること (当たり前ですが) を仮定します。Frege にとっては厄介なことですが、テストされるべき式は関数を参照するのではなくラムダ式の形で与えます。このとき Frege は、部分式の型を推論しなければならないことになります。

prefix を使ったとき twice が満たすべき性質

import Test.QuickCheck
applied_twice = property $ \x -> twice (prefix "<") x == "<<" ++ x
quickCheck applied_twice

そして QuickCheck はしっかりと OK, passed 100 tests. を返します。

想像してみましょう。Frege はこの作業をするためにかなり頭を使っています。ランダムな値を入れられるようにするためには、Frege は x の型を見つける必要があります。x は twice の引数ですが twice の型について制約はついていないので、ここから直接情報を得ることはできません。しかし x の型は twice の第一引数の戻り値すなわち prefix "<"の型でもあります。またしかしこの型は ListSemigroup という極めて抽象的な型です。文字列 "<" (prefix の第一引数) を prefix の戻り値 (ListSemigroup String) と単一化して初めて、QuickCheck は (prefix "<") が文字列を返すことを知ります。そこから (prefix "<") にはまず文字列が与えられる必要があることがわかるため、x は文字列であることが判明し、String 型にランダム値を生成させるという流れになります。ふぅ。

Frege はこの結論プログラマからの助けを全く借りずにこの結論に至ったことになります。

いずれにせよ、コードは構造的に正しいことが保証されました。しかもコンパイル時に！

練習問題

納得がいかない場合は、2 回呼ばれると問題が起こりそうな関数を twice に与えて確認してみましょう。

最後に考えてみてください。Frege 以外の JVM 言語でこんなことができますか？

参考文献

Type Inference	Hindley-Milner Type System
Semigroup	Wikipedia, Haskell Typeclassopedia, Semigoupoid (API), ListSemigroup (API)
QuickCheck	Frege Wiki Page

型推論のメリット