path 依存型って何? 調べてみました!

qiita.comの 12/21 です。

先日社内の勉強會で Tour of Scala を見返してゐたら「path 依存型」と云ふ文言を見て、名前しか知らんなと思ひ返しました。そこで

path 依存型って何? どんなもの? 年齡は? 結婚してる? 調べてみました!

speakerdeck.com scrapbox.io

type selection

path 依存型 (path-dependent type) は、Scala の實裝者達による論文Nada Amin, Tiark Rompf, and Martin Odersky. 2014. Foundations of path-dependent types. SIGPLAN Not. 49, 10 (October 2014), 233–249.にて考察されてゐる、型の一つです。この論文では "type selection" と云ふ名で考察されてゐます。

この形の記號が目印なので、讀む時はこの形を目指してみてください。が variable (變數) で、が型で、組み合はせてと云ふ型です。變數に依存した型、と云ふ訣で path「依存」型と呼ぶのでせう (依存型 (dependent type) の一種と呼べん事は無い…。實際、path 依存型と關聯して Scala 3 から導入された依存函數型 (dependent function type) は依存型の一種です)。

type selection がどう導入されるのかは、論文末尾の式を鑑賞していただく事として、ここでは path 依存型の使ひどころを眺めてみませう。

path 依存型

path 依存型は、class や trait の內側で定義した class や trait の instance の型として登場します。

docs.scala-lang.org

class A {
  class B {
    def f(b: B): Unit = {}
  }
  def newB: B = new B()
}

val a1 = new A()
a1.newB.f(a1.newB) // OK

val a2 = a1
a1.newB.f(a2.newB)
// Found:    Playground.a2.B
// Required: Playground.a1.B
a2.newB.f(a1.newB)
// Found:    Playground.a1.B
// Required: Playground.a2.B

class A の內側で定義した class B の instance の型は、class B の instance を生成する時に使った class A の instance に依存します。a1.newB の型は a1.B であり、a2.newB の型は a2.B と、區別されます。變數 a1 と變數 a2 は、val a2 = a1 であり同じ値ですが、path 依存型は値ではなく變數に依存するので、class B の instance の型は區別されます (nominality (名前的な型) と general refinements (總稱細別型 (「細別型」は大抵「篩型」と譯されますね)) とを考慮してとの事だと論文にはあります)。

path 依存型は、型射影 (type projection) による型 A#B に cast でき、cast すると同じ型の値として扱へる樣になります (A#B として振る舞はせると Java っぽくなりますね)。

何に使ふの?

さて使ひどころです。

多くの記事には、tree の appendChild 先を閒違へない樣にする例を見ましたが、そんな狀況って多いんでせうか?

面白かったのはPath dependent types. Modeling algebraic structures has never… | by Marcin Rzeźnicki | VirtusLab | Mediumの例です。2 進數の演算體系と 10 進數の演算體系を作って、それぞれの中では演算できますが、2 進數の數と 10 進數の數を演算しようとすると compile error にできます。

case class Z(modulus: Int) {
  sealed class Modulus {
    val value = modulus
  }

  object Modulus {
    implicit val mod: Modulus = new Modulus()
  }
}

class IntMod[N <: Z#Modulus] private (val value: Long) extends AnyVal {
  def +(x: IntMod[N])(implicit m: N): IntMod[N] = value + x
}

object IntMod {
  import scala.language.implicitConversions

  implicit def longAsIntModN[N <: Z#Modulus](i: Long)(implicit
      modulus: N
  ): IntMod[N] =
    new IntMod[N](i % modulus.value)

  implicit def intModN2Long(a: IntMod[_]): Long = a.value
}

val z1 = Z(2)
val z2 = Z(10)

val i1z1 = 1: IntMod[z1.Modulus]
val i2z1 = 3: IntMod[z1.Modulus]
val i1z2 = 1: IntMod[z2.Modulus]
val i2z2 = 3: IntMod[z2.Modulus]

println(i1z1 + i2z1) // 0: IntMod[z1.Modulus]
println(i1z2 + i2z2) // 4: IntMod[z2.Modulus]

println(i1z1 + i2z2)
// Found:    (Playground.i2z2 : Playground.IntMod[Playground.z2.Modulus])
// Required: Playground.IntMod[Playground.z1.Modulus]

他にはDependent Types in Scala - Some Tips, Tricks and Techniquesで、まるで普通の依存型かの樣に使ふ力強い使ひ方を紹介してあり、面白いものでした。

依存函數型

關聯する仕樣に Scala 3 から導入された依存函數型 (dependent function type) や dependent method (dependent method は Scala 2 から在ります) があります。

docs.scala-lang.org docs.scala-lang.org

函數や method の引數に登場した變數に依存した型を、他の引數や返り値の型として書けるものです。

trait A { type B; val b: B }
val f: (a: A) => a.B = (a: A) => a.b

函數 f の型が (a: A) => a.B となってゐる、a.B と云ふ path 依存型が含まれてゐるのが (Scala で言ふ) 依存函數型です。

總稱型みたいに使ふのが多いんでせうか。總稱型では、

case class Key[V](name: String) {}

class DB {
  def set[V](k: Key[V], v: V): Unit = {
    println(k)
    println(v)
  }
}

val db = new DB
val k1 = Key[String]("k1")
val k2 = Key[Double]("k2")

db.set(k1, "v1")
db.set(k2, 42.0)

と書くところは、依存函數型では、

abstract class Key(name: String) { type Value }
def key[V](name: String) = new Key(name) { override type Value = V }

class DB {
  def set(k: Key, v: k.Value): Unit = {
    println(k)
    println(v)
  }
}

val db = new DB
val k1 = key[String]("k1")
val k2 = key[Double]("k2")

db.set(k1, "v1")
db.set(k2, 42.0)

となりますね。set method の型 parameter が消えております。

いかがでしたか?