型レベルプログラミング

Scala

kmizu(id:kmizushima)さんが twitter でつぶやいていたリンク先を、ちょろっと試してみました。

まーたScalaで型レベルプログラミングやろうとしてるけったいな人が。

http://twitter.com/kmizu/statuses/3630059097

リンク先: http://apocalisp.wordpress.com/2009/08/28/a-scala-puzzler/

Boolean の例

Lambda の変態的なやつは、まるでわからなかったのでパスして、まずは Boolean のやつを。

例示されていたコードは以下の通り。

  trait Boolean { type cond[t, f] }
  trait TFalse extends Boolean { type cond[t, f] = f }
  trait TTrue extends Boolean { type cond[t, f] = t }

Boolean 型ですが cond というメンバ型*1を定義しています。cond メンバ型は型パラメータ t および f をとることが宣言されています。Boolean の型の時点では宣言のみで定義はされていません。val や def と同様に、メンバ型についても抽象メンバ*2を作ることが可能なようです。
型パラメータや抽象メンバの機能が使えるおかげで、型システム上でさまざまなことを表現できそうです。*3


続いて TFalse と TTrue ですが、両方とも Boolean を継承し、cond メンバ型を定義しています。TFalse では型パラメータ f の値を、TTrue では 型パラメータ t の値を cond メンバ型の内容として定義しています。つまり、TFalse では TFalse#cond は*4型パラメータ f で指定した型を表し、TTrue#cond は型パラメータ t で指定した型を表します。


実際に scala の REPL*5で試した結果は以下の通りになります。



scala> trait Boolean { type cond[t, f] }

defined trait Boolean
scala> trait TTrue extends Boolean { type cond[t, f] = t }

defined trait TTrue
scala> trait TFalse extends Boolean { type cond[t, f] = f }

defined trait TFalse
scala> val value: TTrue#cond[Int, String] = 1

value: TTrue#cond[Int,String] = 1
scala> val value: TTrue#cond[Int, String] = "a"

<console>:6: error: type mismatch;

 found   : java.lang.String("a")

 required: TTrue#cond[Int,String]

       val value: TTrue#cond[Int, String] = "a"

                                            ^
scala> val value: TFalse#cond[Int, String] = 1

<console>:6: error: type mismatch;

 found   : Int(1)

 required: TFalse#cond[Int,String]

       val value: TFalse#cond[Int, String] = 1

                                             ^
scala> val value: TFalse#cond[Int, String] = "a"

value: TFalse#cond[Int,String] = a
scala>

TTrue、TFalse ともに Boolean を継承した型なのですが、cond メンバ型の表す型がそれぞれ異なっています。上記の場合、TTrue#cond は Int 型になっているため、val value: TTrue#cond[Int, String] = 1 が問題なく評価されています。一方 TFalse#cond は String 型になっているため、val value: TFalse#cond[Int, String] = 1 は type mismatch のエラーとなっています。


この例から、型についても値や関数のよう*6に柔軟に扱えるというのが実感できます。

チャーチ数の例

続いてチャーチ数のやつをば。そもそもチャーチ数って何？つおいの？な状態なのですが、どうやら自然数(0, 1, 2, ...)を式の形(≒型？)として表現する方法のひとつみたいです*7。正直何をいっているかわからないのですが、例を見る限りでは型の深さを自然数に見立てているようです。


例示されていたコードは以下の通りです。このコードでは 0, 1, 2, 3 の数を定義しています。

trait Num { type a[F[_], X] }
trait Zero extends Num { type a[F[_], X] = X }
trait One extends Num { type a[F[_], X] = F[X] }
trait Two extends Num { type a[F[_], X] = F[F[X]] }
trait Three extends Num { type a[F[_], X] = F[F[F[X]]] }

型パラメータの F[_] には任意の型パラメータを一つとる型(List[T] 等)が、X には末端要素の型を想定しています。
例をあげると、Zero#a[List, String] が表す型は String に、One#a[List, String] が表す型は code>List[String]、Two#a[List, String] では List[List[String]] という具合になります。


続いて例示されていたコードですが、上述の数に対する演算を定義しています。

trait PApp[F[P[_], _], A[_]] {
  type a[X] = F[A, X]
}

trait Plus[M <: Num, N <: Num] extends Num { type a[F[_], X] = M#a[F, N#a[F, X]] }
trait Succ[N <: Num] extends Num { type a[F[_], X] = F[N#a[F, X]] }
trait Mult[M <: Num, N <: Num] extends Num { type a[F[_], X] = PApp[N#a, PApp[M#a, F]#a]#a[X] }
Plus について
trait Plus[M <: Num, N <: Num] extends Num { type a[F[_], X] = M#a[F, N#a[F, X]] }

数を表す型を型パラメータ M および N として受け取ります。M の末端要素の型として N を指定することで、M + N の深さをもった型を a として定義しています。実際に型パラメータを手作業で展開(?)してみます。

  1. Plus[One, Two]#a[List, String] を展開します
  2. Plus[M <: Num, N < Num] なので、 M = One, N = Two になります
  3. また Plus#a[F[_], X] なので、F = List, X = String になります
  4. Plus#a = M#a[F, N#a[F, X]] の型パラメータに実際の型を入れると Plus#a = One#a[List, Two#a[List, String]] になります
  5. One#a を展開すると、Plus#a = List[Two#a[List, String]]
  6. Two#a を展開すると、Plus#a = List[List[List[String]]]

ちゃんと List が三つ入れ子の型になりました。

Succ について
trait Succ[N <: Num] extends Num { type a[F[_], X] = F[N#a[F, X]] }

入れ子とする型の型パラメータに N の型を指定することで、N + 1 の深さをもった型を定義しています。これも実際に展開してみます。

  1. Succ[One]#a[List, String] を展開します
  2. Succ[N <: Num] なので、N = One になります
  3. また Succ#a[F[_], X] なので、F = List, X = String になります
  4. Succ#a = F[N#a[F, X]] の型パラメータに実際の型をいれると Succ#a = List[One#a[List, String]] になります
  5. One#a を展開すると、Plus#a = List[List[String]]

こちらもちゃんと List が二つ入れ子の型になりました。

PApp について

最後に Mult なのですが、その前に Mult で使用する PApp について。

trait PApp[F[P[_], _], A[_]] {
  type a[X] = F[A, X]
}

PApp の型パラメータ F の一つ目の型パラメータに、PApp の型パラメータ A を指定したメンバ型 a を定義しています。F の二つ目の型パラメータにはメンバ型の型パラメータ X を指定しています。これにより、型定義に対して部分適用のようなことを実現しているみたいです。展開例は以下のとおりです。

  1. PApp[Two#a, List]#a[String] を展開します
  2. PApp[F[P[_], _], A[_]] なので、F = Two#a, A = List になります
  3. また PApp#a[X] なので、X = String になります
  4. PApp#a = F[A, X] の型パラメータに実際の型をいれると、PApp#a = Two#a[List, String] になります
  5. Two#a を展開すると、PApp#a = List[List[String]]

Two#a の型パラメータに対して、List と String を指定したのと同じになりました。

Mult について
trait Mult[M <: Num, N <: Num] extends Num { type a[F[_], X] = PApp[N#a, PApp[M#a, F]#a]#a[X] }

型パラメータ N の入れ子とする型パラメータに M を指定することで、N * M の深さをもった型を定義しています。
手作業で展開、展開！

  1. Mult[Two, Three]#a[List, String] を展開します
  2. Mult[M <: Num, N <: Num] なので、M = Two, N = Three になります
  3. また Mult#a[F[_], X] なので、F = List, X = String になります
  4. Mult#a = PApp[N#a, PApp[M#a, F]#a]#a[X] に実際の型をいれると、Mult#a = PApp[Three#a, PApp[Two#a, List]#a]#a[String] になります
  5. 外側の PApp および Three を展開します
    1. 外側の PApp を展開すると、Mult#a = Three#a[PApp[Two#a, List]#a, String]
    2. Three を展開すると、Mult#a = PApp[Two#a, List]#a[PApp[Two#a, List]#a[PApp[Two#a, List]#a[String]]]
  6. 残った PApp を展開します
    1. 内側の PApp を展開すると、Mult#a = PApp[Two#a, List]#a[PApp[Two#a, List]#a[Two#a[List, String]]]
    2. 真ん中の PApp を展開すると、Mult#a = PApp[Two#a, List]#a[Two#a[List, Two#a[List, String]]]
    3. 外側の PApp を展開すると、Mult#a = Two#a[List, Two#a[List, Two#a[List, String]]]
  7. Two を展開します
    1. 内側の Two を展開すると、Mult#a = Two#a[List, Two#a[List, List[List[String]]]]
    2. 真ん中の Two を展開すると、Mult#a = Two#a[List, List[List[List[List[String]]]]]
    3. 外側の Two を展開すると、Mult#a = List[List[List[List[List[List[String]]]]]]

List が六つ入れ子になった型に展開されました。

ちなみに Mult を Scala 2.7.5 で試そうとすると



<console>:11: error: cyclic aliasing or subtyping involving type a
と、怒られてしまいます。(追記: -Yrecursion というオプションをつければ出来るそうです*8 )

なので、Scala 2.8 を Nightly Build から取得して試しました。Scala 2.8 で試した結果は以下の通りです。



scala> class Pa[T](val value: T) { override def toString = "Pa("+value+")" }

defined class Pa
scala> object Pa { def apply[T](value: T) = new Pa(value) }

defined module Pa
scala> val value: Mult[Two, Three]#a[Pa, String] = Pa(Pa(Pa(Pa(Pa(Pa("Perfume"))))))

value: Pa[Pa[Pa[Pa[Pa[Pa[String]]]]]] = Pa(Pa(Pa(Pa(Pa(Pa(Perfume))))))
scala>
ちゃんと、「ぱっぱっぱっぱっぱっぱっPerfume♪」できました！



最後に課題として出されている Exp[M, N] はまだやれていないです・・・

*1:メンバ型という呼び方が正しいのか不明ですが、便宜上このように呼んでおきます

*2:Java でいうところの抽象メソッド、C++ でいうところの純粋仮想関数

*3:リンク先でも「This feature gives you quite a lot of expressive power in the type system.」と書かれている

*4:'#' はメンバ型へアクセスするための記号

*5:scala> とでるインタプリタみたいなアレ、インタプリタとは別物らしいです

*6:さすがに値や関数ほど扱いやすくはないですが(汗

*7:「自然数をラムダ式で表現する方法・・・」wikipedia より

*8:kmizu さんありがとうございます!