プログラミングと絵と音楽

コンピューター科学を専攻し、絵と音楽を趣味とするエンジニアのブログです。

プログラミング言語を作る。第13回:関数と型推論

関数型の要素を静的型付けの言語の仕様に持ち込むならば、やはり型推論は欲しいところです。ただし、言語の仕様によっては、型推論は関数定義などを行うときにかなりややこしいことになる可能性があります。

例えば、簡潔で強力な型推論の例として、 OCaml のプログラムを挙げてみましょう。

let add x y = x + y

この関数 add は、型推論によって int -> int -> int という型を持つことがわかります。もう一つの例として、 Haskell で同じような関数を定義しましょう。

add x y = x + y

この関数 add は、型推論によって Num a => a -> a -> a という型を持つことがわかります。

私が作ろうと思っている言語の仕様の中には、 Scala のように、それぞれのクラスに対してオーバーロード可能の関数、演算子の定義をでき、ドットでメソッドを適用できるものを考えていました。考えを詰めていくと、大きく二つの問題に直面することが分かりました。

一つ目として、ドットでメソッドを適用できる場合の型推論です。

class A(i: Int){ def f(i: Int) = this.i + i }
class B(i: Int){ def f(i: Int) = this.i < i }
class C(i: Int){ def f(d: Double) = this.i.toDouble * d }

例えば、具体的な型を使っている場合は、方が推論できます。例えば、

var a = new A(1)
var b = a.f(2)

では、 a が A であり、 b が Int であることがわかります。しかし、ラムダ式を使っている場合、具体的に型を決定することができないので、型推論時に問題が起こります。以下に具体例を挙げます。

var z = x => y => x.f(y) の型を推論してみましょう。 f を持つメソッドは A, B, C に当てはまるため、 x の型はそのうちどれかわかりません。 f の引数の型も、 Int, Double など不定であるため、 y の型もわかりません。返り値の型も、 x, y の型が決まっていなければ、 Int, Bool, Double のどれになるかわかりません。結局、これだと型推論ができないのです。実際に Scala でも、ラムダ式を定義する際には、引数の型がわかるような状態でなければエラーを起こします。以下が例です。

(n: Int) => n + 1 // OK
var succ: Int => Int = n => n + 1 // OK
var succ = n => n + 1 // NG

先程の例の型推論ができなかった理由の根本は、 x の型がわからなかったことです。 x の型 a さえ分かれば、 引数 y の型 b、そして返り値 x.f(y) の型 c が分かり、 z の型 a -> b -> c も分かります。さて、解決手法として、具体的な型がわからない場合は、クラス名 . メソッド名という表記に限定するという方法を挙げてみました。

x => y => A.f x y

x.f(y) というのを、 x が A だと明示するために A.f という表記をするのです。こうすると、 x は A の型だとわかりますので、その他の型も芋づる式に分かります。具体的な型がわからない場合は、 x.f のような記法を禁止するという方法で、なんとかできそうです。

二つ目の問題として、オーバーロードができる場合の型推論です。

class D(i: Int){
  def f(i: Int) = this.i + i
  def f(b: Boolean) = if(b){ - this.i }else{ this.i }
  def f(d: Double) = this.i.toDouble * d
}

同じように、 x => y => x.f(y) を考えてみましょう。先ほどの問題は解決したものとして、 x: D がわかっているものとします。しかし、 y の型は D の中に f が 3 つ定義され、一つの型を三種類の方法でとっているため、そのうちどのメソッドを適用すればよいのかわかりません。

そもそも OCamlHaskell では、関数のオーバーロードができません。これは、関数自体の型を確定するためだと思われます。関数やメソッドの型が確定していないと、型推論ができません。最初の例も、 + という演算子が int -> int や Num a => a -> a -> a という型に固定されていたために型推論が実現しているのです。関数のオーバーロードと強力な型推論共存することができないことが分かりました。では、型推論オーバーロードを仕様から外さなければなりません。おそらく、オーバーロードの方が重要度の低い存在だと思うのでそちらを外すことになりそうです。関数やメソッドのデフォルト引数もオーバーロードと本質は同じであるため、同じ運命になります。