scala的类型系统居然可以解题

曾经听说scala的类型系统很强大，是“图灵完备”的，而“图灵完备”的语言的计算能力是相同的。这岂不是说，利用scala的类型系统，就可以完成普通编程语言才能做的事情？

这一直是我心里的一个疑问，类型系统怎么看都只是一些定义，怎么能编程，还能解题？连想都不知道如何去想。直到前几天再次看到了老高在09年（没错，四年前）写的那一篇文章，豁然开朗，仿佛推开了一道光亮的门。

老高的文章地址：http://www.blogjava.net/sean/archive/2009/11/23/303374.html

(注：原始来源应该是https://gist.github.com/jrudolph/66925)

该文章讲的是如何利用scala的类型系统去解题，通过implicit指示编译器寻找合适类型的时候，在类型的层面上使用了递归。如果你仔细看那段代码，会发现几乎所有的方法实现都是空的，真正起到解题的作用的，是里面各种类型定义和它们在声明时参数位置的变化，再加上implicit关键字，让编译器帮我们实现了解题过程。

利用类型系统解汉诺塔的Scala代码

为了理解方便，我把代码复制在这里，修改了里面的一些类型名称以帮助理解，并做了少量改进（在新版的scala中，有一些内容已经废弃，如Manifest改为了ClassTag，使用了sealed trait等）。

import scala.reflect.ClassTag

object Hanoi extends App {

  def simpleName(m: ClassTag[_]): String = {
    val name = m.toString()
    name.substring(name.lastIndexOf('$') + 1)
  }

  // 利用类型来表示数字
  sealed trait Num
  trait Next[Pre <: Num] extends Num
  trait _1 extends Num

  type _2 = Next[_1]
  type _3 = Next[_2]
  type _4 = Next[_3]
  type _5 = Next[_4]
  type _6 = Next[_5]
  type _7 = Next[_6]

  // 利用类型参数来表示移动时需要的信息
  trait Move[TOP_N <: Num, FROM, TO, TEMP]

  // 两个implicit告诉编译器如何推导类型
  implicit def move1[FROM, TO, TEMP](implicit from: ClassTag[FROM], to: ClassTag[TO]): Move[_1, FROM, TO, TEMP] = {
    println("Move from " + simpleName(from) + " to " + simpleName(to))
    null
  }

  implicit def moveN[N <: Num, FROM, TO, TEMP](
    implicit m1: Move[N, FROM, TEMP, TO],
             m2: Move[_1, FROM, TO, TEMP],
             m3: Move[N, TEMP, TO, FROM]): Move[Next[N], FROM, TO, TEMP] = null

  // 开始
  def startToMove[TOP_N <: Num, FROM, TO, TEMP](implicit m: Move[TOP_N, FROM, TO, TEMP]) = null

  // 三根柱子
  trait Left
  trait Center
  trait Right

  // 只放了3个盘子
  startToMove[_3, Left, Right, Center]

}

为了看懂这段代码，我们需要有这些背景知识：

_1, _2, _3, _4 这些，是手动定义出来的整数序列，每一个都是Num的子类型，它们之间是依次递增的关系。这个递增可以看作是对自然数的抽象，在类型系统中，似乎经常有这种表示法。我们一会儿要用它们当作数字来表示我们将要移动柱子最上面的“几个”盘子
我们需要多少数字，就需要手动定义多少个这样的类型，因为scala没有批量定义类型的功能（类型系统的目的不是解题）。所以如果你想解20个盘子的汉诺塔，你需要定义_1,_2,_3,.._9,_10,_11,...,_19,_20
ClassTag对象保存了与类型相关的信息，它由系统提供，我们只需要用implicit来声明它。scala在运行时会自动产生合适的对象传进来，有点像依赖注入。
“implicit参数"和"implicit方法"是关键。它们的作用是告诉scala编译器，在编译时请帮我寻找合适的对象注入进来。从哪里找呢？看所在域中有没有合适的implicit对象或者implicit方法。
implicit是由编译器在编译期自己调用的，所以我们在代码中不需要写调用代码。但我们需要巧妙地定义各类型参数，通过类型和顺序，来指示编译器做什么。这就是为什么定义了一些方法，但它们实现为空，因为我们要看的仅仅各参数的类型值。
当一个implicit方法的参数也是implicit时，编译器会先为该参数寻找合适的implicit来源，递归就这么产生了。
解题过程体现在参数和返回值的类型上，看代码时要把目光放在它们身上，跟我们平时写scala代码时的注意力正好相反。

implicit与classTag

先来一个简单的例子，看一下implicit和classTag的运作：

class User

def hello(implicit user: ClassTag[User]) {
    println(user.toString)
}

hello

在REPL中运行这几行代码，会打印出：

$line30.$read$$iw$$iw$User

即那个参数user的内容。而我们调用hello时，并没有传入user对象，这说明是由scala自己产生了合适的ClassTag对象并传了进去。

题目思路

回到原题，从后往前看。

startToMove[_3, Left, Right, Center]

这一句代码是解题的入口。在调用startToMove的时候，我们没有为它传入implicit m这个参数，而是指明了各类型参数的实际类型。这些信息，将决定其implicit参数m的实际类型为Move[_3, Left, Right, Center]。

对于本题来说，这样的一个类型，代表我现在要处理的是一个有3个盘子的汉诺塔，目的是把盘子从Left柱移到Right柱，移动过程中可以用Center柱子作为中转。

然而这个类型不存在，且m前面有implicit关键字，所以编译器要去找看能不能找到某个implicit object正好是这个类型，又或者某个implicit method的返回值正好是这个类型。

编译器很幸运，看到了moveN这个implicit方法，它的返回值类型是：Move[Next[HEAD], FROM, TO, TEMP]，正好跟Move[_3, Left, Right, Center]能对上。所以它将会尝试调用这个方法，以便将它的返回值传给m。

注意，由于_3对应了类型Next[_2]，所以在这次调用中，moveN的N类型将会是_2。所以编译器将调用方法 moveN[_2, Left, Right, Center]。

编译器还没松口气，又看到它有三个implicit参数，分别是：

m1: Move[N, FROM, TEMP, TO],
m2: Move[_1, FROM, TO, TEMP],
m3: Move[N, TEMP, TO, FROM]

即：

m1: Move[_2, Left, Center, Right],
m2: Move[_1, From, Right, Center],
m3: Move[_2, Center, Right, Left]

其实这里就是我们的解题算法。当我们需要把3个盘子从左柱移到右柱时，我们的思路是这样的：

首先把上面2个盘子移到临时柱上
然后把剩下那1个盘子移到目标柱上
再把临时柱上的那2个盘子移到目标柱上

由于这三个参数又是implicit的，所以编译器只好再去寻找相应的implicit object或implicit method。首先它会寻找第一个参数m1对应的类型Move[_2, Left, Center, Right]，发现只有moveN方法能返回一个符合要求的类型，于是再次调用moveN[_1, Left, Center, Right]，递归就这么产生了。编译器一层层地找下去，直到遇到了某个参数要求的类型是：

[_1, FROM, TO, TEMP]

编译器终于开心地发现move1方法的返回值正好满足其要求，并且不需要再递归，于是它调用move1方法，打印出了一句"Move from x to y"的话，然后再一层层回去，直接成功地返回m1所要求的Move[_2, Left, Center, Right]类型。

然后编译器处理m2，这次直接调用move1函数即可。

接着处理m3，又需要经过一层层递归，才能产生Move[_2, Center, Right, Left]类型的对象。

而当编译器松了最后一口气，为run方法产生了合适的类型的时候，题目就这么自然而然的解出来了。

它将会在console中打印：

Move from Left to Right
Move from Left to Center
Move from Right to Center
Move from Left to Right
Move from Center to Left
Move from Center to Right
Move from Left to Right

这正是我们移动三个盘子的汉诺塔所需要的步骤。

从这个例子可以看出，scala的类型系统很强大，而且implicit的作用要比我之前以为的大得多，它是我们操作scala类型的一种手段。

编译器到底对implicit做了什么

上面反复提到编译器需要某类型但又没有找到时，会查看相应的implicit method的返回值，这里是可以递归的，直到最后找到了某个不需要推导的类型。

那么编译器到底做了什么呢？正如对于下面的简单代码：

implicit def richString(s:String) = new {
  def hello():Unit = println("Hello, " + s)
}
"Scala".hello()

Scala会在编译器把它编译为

richString("Scala").hello()

一样，在Hanoi这段代码中，Scala编译器会生成大量的对moveN和move1的方法调用。

生成的代码是这样的（经过jad反编译，并经过简化）：

public final void delayedEndpoint$1() {
  startToMove(
    moveN(
      moveN(
        move1(ClassTag$.MODULE$.apply(Left), ClassTag$.MODULE$.apply(Right)),  
        move1(ClassTag$.MODULE$.apply(Left), ClassTag$.MODULE$.apply(Center)),  
        move1(ClassTag$.MODULE$.apply(Right), ClassTag$.MODULE$.apply(Center))  
      ),  
      move1(ClassTag$.MODULE$.apply(Left), ClassTag$.MODULE$.apply(Right)),
      moveN(
        move1(ClassTag$.MODULE$.apply(Center), ClassTag$.MODULE$.apply(Left)),
        move1(ClassTag$.MODULE$.apply(Center), ClassTag$.MODULE$.apply(Right)),
        move1(ClassTag$.MODULE$.apply(Left), ClassTag$.MODULE$.apply(Right)))
      )
  );
}

可以看到，原来Scala编译器居然帮我们生成了这么多的代码！如果我设了一个非常大的数字，比如1000，岂不是会生成一个巨大无比的.class文件！

最后还有点疑问，关于scala的类型系统，还有别的类似的例子吗？

一些评论

Vincent Xu

Scala因为受限于擦拭法，做出来的还是有限。06年熊桑在C++里用类型系统做了个MarsRover，我用Haskell的类型系统做过简单的解释器。这都不是厉害的。老袁用C++类型系统做了电信产品的DSL，这是我知道的，最厉害的一个应用。

(2013-06-12) scala的类型系统居然可以解题