月度归档:2013年11月

scala类库中的api陷阱(1): LinkedList.append

scala.collection.mutable.LinkedList 可变集合的 append 方法有个细节需要注意:

// 当list为空时
scala> val list = LinkedList[String]()

scala> val list2 = LinkedList[String]("ele")

scala> list.append(list2)
res6: scala.collection.mutable.LinkedList[String] = LinkedList(ele)

scala> list
res7: scala.collection.mutable.LinkedList[String] = LinkedList()

scala> list.size
res8: Int = 0

看到 list 本身并没有改变,仍为空,它的实现是判断自身为空时append方法直接返回要附加的对象,所以得这样用。

scala> val r = list.append(list2)
r: scala.collection.mutable.LinkedList[String] = LinkedList(ele)

scala> r(0)
res9: String = ele

当它不为空时,才会改变自身:

scala> val list = LinkedList[String]("1")

scala> list.append(list2)

scala> list.size
res11: Int = 2

它的文档里有讲到这点,但仍觉得很不合理,一是不符合大众的直觉,二是也并非所有的可变集合在为空时 append 操作也这样,比如ListBuffer里的append方法,在自身为空时仍会改变自身:

scala> val buf = ListBuffer[String]()
buf: scala.collection.mutable.ListBuffer[String] = ListBuffer()

scala> buf.append("A")

scala> buf
res4: scala.collection.mutable.ListBuffer[String] = ListBuffer(A)

scala> buf(0)
res5: String = A

scala雾中风景(9): List(1,2,3) == Seq(1,2,3) ?

惜朝在来往的扎堆里问:

scala> List(1, 1, 2) == Seq(1, 1, 2)
res219: Boolean = true

scala里Seq和List是一会儿事?

这个问题归根到底在于 == 在集合里是怎么实现的?在scala里==的语义等同于java里的equals,我们跟踪一下

val a = List(1,2,3)
val b = Seq(1,2,3)
a.equals(b)     // 设置断点

注意,在a.equals(b)出设置断点,scala-ide不一定能进入内部逻辑,你还是需要在它父类equals方法内设置断点才行。

上面的equals实际会到 GenSeqLike.equals,见下图:

它的逻辑是判断两个集合是否“可比较”(canEqual),如果可比较,则判断内部的元素是否相同:

override def equals(that: Any): Boolean = that match {
    case that: GenSeq[_] => (that canEqual this) && (this sameElements that)
    case _               => false
}   

于是我们推测 List(1,2,3)Seq(1,2,3)的容器类型应该是相同的类型或有继承关系,但是进入到canEqual逻辑内部,无法验证这个判断,它直接返回true,按理说应该对两个容器的类型进行比较一下才合适(看来只是给用户实现的集合类型实现equals时留了一个扩展点,scala自己的集合类型并不做类型判断)。

接下来进入 sameElements 逻辑,因为List混入了LinearSeqOptimized特质,这块的逻辑是在LinearSeqOptimized中的,见下图:

我们看到它通过模式匹配,要求目标集合也必须是LinearSeq类型。然后迭代并比较了两个容器内的各个元素是否相同,都相同的话就认为两个容器也相同。不过从这里的逻辑我们也可以判断出来,两个容器equals为true的话,并不一定需要是完全同样的类型或者有父子关系。我们验证一下:

1)两个集合分别是Seq特质与Set特质下的子类,是两种不一样的集合

scala> List(1,2,3) == Set(1,2,3)
res28: Boolean = false

2) 两个集合都是Set特质下的子类

scala> HashSet(1,2,3) == TreeSet(1,2,3)
res29: Boolean = true

3) 两个集合都是Seq特质下的子类

scala> ListBuffer(1,2) == LinkedList(1,2)
res20: Boolean = true

4) 两个集合都是Seq特质下的子类,不过QueueLinearSeq下的,而RangeIndexedSeq下的

scala> Queue(1,2) == Range(1,2)
res18: Boolean = false

5) 两个集合都是Seq特质下的子类,Seq(1,2,3)的实现是?

scala> Range(1,2,3) == Seq(1,2,3)
res12: Boolean = false

第1种情况好理解,ListSet 毕竟是另种含义不同集合,Set的实现也不会是LinearSeq特质的,所以返回false.第2种也容易理解,两个集合都是Set特质下的。

问题是3,4,5,为何Seq下会有多种情况,这还要我们再全面的看一下scala的集合框架,借用
这里的图片:

正是因为 Seq 特质下,又分为了IndexedSeqLinearSeq 两个分支,并且这两个特质中各自对 sameElements的逻辑有不同的实现,使得IndexedSeq的集合与LinearSeq下的集合比较时不可能相等。

另,对于 List(1,2,3)Seq(1,2,3)在构造集合的背后逻辑,可以参考这篇:通过List.apply方法构造List的背后逻辑

通过List.apply方法构造List的背后逻辑

通过List伴生对象的apply方法来创建实例: List("A","B") 过程发生了什么

首先,List伴生对象的apply方法接收的是一个可变参数列表,即数组:

override def apply[A](xs: A*): List[A] = xs.toList

而我们传入的Array("A","B")数组会被隐式转换为 WrappedArray 的子类型,这是在LowPriorityImplicits里定义的:

// Since the JVM thinks arrays are covariant, one 0-length Array[AnyRef]
// is as good as another for all T <: AnyRef.  Instead of creating 100,000,000
// unique ones by way of this implicit, let's share one.

implicit def wrapRefArray[T <: AnyRef](xs: Array[T]): WrappedArray[T] = {
    if (xs eq null) null
    else if (xs.length == 0) WrappedArray.empty[T]
    else new WrappedArray.ofRef[T](xs)
}

随后对这个WrappedArray 的子类型ofRef[String]类型,调用 toList 方法

不过在进行toList时用到了隐式参数CanBuildFrom,我们先看一下List伴生对象中定义的,用于生成CanBuildFrom信息的隐式方法:

/** $genericCanBuildFromInfo */
implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, List[A]] =
    ReusableCBF.asInstanceOf[GenericCanBuildFrom[A]]

现在来追踪toList的执行过程,在父类TraversableOncetoList方法里调用了to方法,而这个to方法里有声明一个隐式参数。

用隐式参数CanBuildFrom构造了一个List类型的容器,把数据填充进去,再返回result

里面的隐式参数:

implicit cbf: CanBuildFrom[Nothing, A, Col[A @uV]] 

先不用管里面难懂的类型参数,编译在寻找对应的隐式参数值时,通过上面的 to[List]声明的目标类型是List,所以从List的伴生对象中去寻找,通过 canBuildFrom隐式函数得到了需要的参数,它是把一个可复用的对象造型成我们需要的CBF类型:

ReusableCBF.asInstanceOf[GenericCanBuildFrom[A]]

ReusableCBF的意思是可复用的CanBuildFrom,它在 GenTraversableFactory里定义:

通过这个CBF隐式参数帮我们构造了一个新的容器,然后把当前集合里的数据放进去,最后再调用新容器的result来得到List

通过断点,发现 b.result 时进入了 ListBuffer.toList 的代码里,也就是说这个隐式参数构造出来的新容器类型是 ListBuffer 的子类型。

最终,它返回ListBuffer类里的start成员,这个start是一个 :: 类型(List的子类)

scala雾中风景(8): 高阶函数与Unit的谜题

这个问题是在spray-routing的使用过程中发现的,又是一个“障眼法”问题。

简化一下,假定有下面的类型:

scala> class Request

scala> type Route = Request => Unit

Route是一个函数类型,然后我们定义一个接受Route类型的方法

scala> def hf(r:Route) { println("ok") }
hf: (r: Request => Unit)Unit

现在传递一个Route类型的实例,调用hf方法:

scala>  hf( req => {} )
ok

上面传递了一个 req => {} 的函数对象,运行没有问题。

我们再定义一个Route的生成器:

scala> def routeGenerator: Route = req => println("do nothing")
routeGenerator: Request => Unit

把这个生成器作为参数传递给 hf 方法:

scala> hf(routeGenerator)
ok

跟刚才没什么区别。

现在我们如果传入一个看上去像是高阶函数的函数: req => routeGenerator,hf方法还会接受吗?

scala> hf ( req => routeGenerator )
ok

是不是有点奇怪?我传入的不是 Request => Route 类型吗?展开的话应该是 Request => (Request => Unit) 为什么hf方法也能接受呢?

这里核心的问题就在于 req => routeGenerator 这个函数实例,究竟是什么类型?这与编译器的类型推导逻辑有关。

当我们定义一个变量,不声明类型,把上面的函数对象赋给这个变量:

scala> val param =  (req:Request) => routeGenerator
param: Request => (Request => Unit) = <function1>

变量param的类型是 Request => (Request => Unit) 类型,与我们预测的一致。

如果定义param时,指定它的类型是RouteRequest => Unit,上面的函数对象还可以赋值吗?

scala> val param: Route  =  (req:Request) => routeGenerator
param: Request => Unit = <function1>

这里困惑我们的是,为什么函数对象右边的routeGenerator的类型在这次的上下文中变成了Unit,而不是我们定义的Route类型了呢?

如果你对Unit类型真的了解(参考之前的这篇:scala雾中风景(4): Unit类型),这个时候就不会被迷惑了。

因为Unit类型自身的特点,在赋值时,可以把任意类型的表达式赋值给它:

scala> val tmp:Unit = "hello"
tmp: Unit = ()

因为表达式背后会被翻译为: { "hello", () },同理,在之前的上下文里,定义了 param 是一个 Reuqest => Unit
类型的变量,在赋值时,编译器就会把 req => routeGenerator 翻译成:

req => { routeGenerator; () } 

这个问题看上去像是个高阶函数的问题,实际与高阶函数没关系。至于Unit类型为何在给变量赋值时设计成这样,可能与函数式语言的历史上已经是这样设计了,scala很可能是从ML那块继承的这个设计。

或许我们可以把Unit类型在赋值时,理解成一个带有副作用的”过程”,这个过程接受无论什么类型的表达式,执行这些表达式,但最终返回的是()这个值。

scala类型系统:27) 回顾常见的type classes

在scala世界,type classes是一种非常常见的模式,我们回顾一下scala库的实现中有哪些采用这种模式的

1) Ordering

scala> def foo[T:Ordering] (l:List[T]) { 
            l.sorted.foreach(print) 
        }

scala> foo(List(2,3,1))
123

Ordering[_]抽象了大于、等于、小于等用于比较的方法。它是一个典型的type class

2) Numeric

scala> def foo[T:Numeric] (l:List[T]) { 
            print(l.sum) // List只对数字类型才能使用sum方法
        }

scala> foo(List(1,2,3))
6

scala> def bar[T:Numeric](a:T, b:T) {
            implicitly[Numeric[T]].plus(a,b) 
        }

scala> bar(2,3)

Numeric[_]对抽象了所有数字类型中的加、减、乘、除等操作。

3) Manifest/TypeTag/ClassTag 等

scala> def biuldArray[T:ClassTag](len:Int) = new Array[T](len)

scala> buildArray[Int](3)
res8: Array[Int] = Array(0, 0, 0)

4) <:<[-From, +To], =:=[From,To]

scala> def test[T](i:T) (implicit ev: T <:< java.io.Serializable) { 
            print("OK") 
        }

不要被它的两个类型参数和中缀方式给迷惑,这两个用于类型证明的泛型类,使用上也属于type class模式

在《scala in depth》中总结了type classes模式的几个优点:

1) Separation of abstractions (抽象分离)
2) Composability (可组合)
3) Overridable (可覆盖)
4) Type safety (类型安全)

scala类型系统:26) type classes模式

在进入主题之前,先了解一下通过泛型实现参数化多态的形式:

trait Comparable[T] { 
    def comp(o:T) = this.hashCode - o.hashCode 
}

class A extends Comparable[A] { 
    override def comp(o:A) = super.comp(o) 
}

class B(val i:Int) extends Comparable[B] { 
    override def comp(o:B) = this.i - o.i 
}

上面定义了一个Comparable的泛型特质,对于A,B等实现者可以设定不同的参数类型。

在scala里因为有隐式转换的功能,也可以在定义时不显式的继承Comparable特质,而在伴生对象里定义一个隐式转换,在需要用comp方法的时候,编译器会自动转换为目标类型:

scala> class A; 

scala> object A { 
            implicit def convert(a:A) : Comparable[A] = {
                new a.type with Comparable[A] { 
                    override def comp(o:A) = a.hashCode - o.hashCode 
                } 
            }
        }   

scala> a.comp(new A)
res2: Int = -1633174887

不过scala已经不鼓励使用隐式转换,必要的话,可以使用隐式参数:

// 需要定义一个新的comparable2特质,comp方法接受2个参数
scala> trait Comparable2[T] { def comp(x:A, y:A) = x.hashCode - y.hashCode } 

scala> class A; 

scala> object A { 
            implicit val compA = 
                new Comparable2[A] { override def comp(o:A) = super.comp(o) }
        }

上面定义了一个隐式参数compA它是Comparable[A]类型,不过这样如果要用到A的comp行为,需要在调用的方法中声明隐式参数

// 柯里化,最后一个参数是隐式的,编译器会自动在上下文找

scala> def call[T](x:T, y:T) (implicit c : Comparable2[T]) { 
            c.comp(x,y) 
        }

scala> val x = new A; val y = new A;

scala> call(x,y)

这样做相当于把A的结构与行为(方法)给分离开了(解耦);或者说对某个类型,在不改动其本身的情况下,具备了扩展其行为的能力。

这个模式被称为type classes,源于haskell,我对haskell不熟悉,为什么用这么奇怪的一个名字?从这儿看到:在haskell里没有类似于java/scala里的class的概念,所以class这个术语可以随意使用,它的意思相当于”class of types”,可以理解为对某一系列类型的抽象(即高阶类型)。

scala里的type classes模式主要通过隐式参数来实现,但需要注意的是,并不是所有的隐式参数都可以理解为type classes模式,隐式参数的类型必须是泛型的(高阶),它表示某种抽象行为,这种行为的具体实现要由它的具体类型参数决定。

// 隐式参数c在这里是多态的
scala> def call[T](x:T, y:T) (implicit c : Comparable2[T])

// 针对A实现了一个具体的comp行为,它的参数类型是A 
scala> implicit object CompA extends Comparable2[A] { 
            override def comp(x:A, y:A) = super.comp(x, y) 
        }

简单总结,type classes模式通过泛型来描述某种通用行为,对每个想要用到这种行为的具体类型,在现实时行为部分并不放在类型自身中,而是通过实现一个type class实例(对泛型具化),最后在调用时(通过隐式参数)让编译器自动寻找行为的实现。

scala类型系统:23) 用类型证明实现联合类型

我们用类型证明来实现一个联合类型(union type):

// 让参数类型满足Int或String

scala> def f[A](a: A)(implicit ev: (Int with String) <:< A) = println("OK")
f: [A](a: A)(implicit ev: <:<[Int with String,A])Unit

scala> f(2) 
OK

scala> f("hi")
OK

跟我们之前通过context bound来是实现联合类型,对比一下更简洁。

scala类型系统:22) 类型约束与特定方法

对于类型限制 =:=<:<

A =:= B  //表示A类型等同于B类型
A <:< B  //表示A类型是B类型的子类型

这个看上去很像操作符的=:=<:<,实际是一个类,它在Predef里定义:

sealed abstract class =:=[From, To] extends (From => To) with Serializable

sealed abstract class <:<[-From, +To] extends (From => To) with Serializable

它定义了两个类型参数,所以可以使用中缀写法:From <:< To

2.10之前还有一个 <%< 类似于view bound,表示 A可以当作B,即A隐式转换成B也满足。但在2.10里已经废弃这种写法。

类型限制用在特定方法(specialized methods)的场景,所谓特定,是指方法只针对特定的类型参数才可以运行:

scala> def test[T](i:T)(implicit ev: T <:< java.io.Serializable) { print("OK") }
test: [T](i: T)(implicit ev: <:<[T,java.io.Serializable])Unit

scala> test("hi")
OK

scala> test(2)
<console>:9: error: Cannot prove that Int <:< java.io.Serializable.

上面定义的test方法,在方法的第二个参数使用了一个隐式参数ev,它的类型是:T <:< java.io.Serializable,表示只有参数类型Tjava.io.Serializable的子类型,才符合类型要求。

或许你会奇怪上面test方法调用”hi”时,隐式参数ev是从哪儿传入的?当前并没有定义这个隐式参数。这个隐式参数也是由Predef里的隐式方法产生的

private[this] final val singleton_<:< = new <:<[Any,Any] { def apply(x: Any): Any = x }

implicit def conforms[A]: A <:< A = singleton_<:<.asInstanceOf[A <:< A]

当调用test("hi"),编译器推断出T是String,在寻找 String <:< java.io.Serializable类型的隐式参数时,上下文中找不到,于是通过conforms隐式方法来产生一个,conforms方法只有一个类型参数,它产生的结果是<:<[String,String]类型的对象,但因为<:<[-From,+To]第一个类型参数是逆变的,第二个类型参数是协变的,所以<:<[String,String]符合<:<[String,java.io.Serializable]的子类,满足要求。

而调用test(2)时,因为隐式方法产生的<:<[Int,Int]不符合<:<[Int,java.io.Serializable]子类型,抛出了异常。可见这块编译器是利用函数类型的多态机制来实现类型检测的。

另外,对于Type类型,在判断之间的关系时也有类似的写法,不过这里是Type类型的方法:

scala> typeOf[List[_]] =:= typeOf[List[AnyRef]]
res4: Boolean = false

scala> typeOf[List[Int]] <:< typeOf[Iterable[Int]]
res1: Boolean = true

上面的是方法调用:typ1.=:=(typ2) ,虽然效果都是证明类型关系,但不要混淆。

//2013.11.8 补充
昨天泽彬在csug的旺旺群(94329267/csugcsug)里问<:<:<的差异:

object A{
    def test[T <: java.io.Serializable](i:T) {}
    test(1) // 编译时报错

    def test2[T](i:T)(implicit ev: T <:< java.io.Serializable)  {}
    test2(1) // 同样编译时报错
}

两者的效果似乎一样,应该怎么选择?他在stackoverflow上也问了一下:http://stackoverflow.com/questions/19829770/whats-different-between-and-in-scala

有人给出这样的解释:

def foo[A, B <: A](a: A, b: B) = (a,b)

scala> foo(1, List(1,2,3))
res1: (Any, List[Int]) = (1,List(1, 2, 3))

传入第一个参数是Int类型,第二个参数是List[Int],显然这不符合 B <: A 的约束,编译器在做类型推导的时候,为了满足这个约束,会继续向上寻找父类型来匹配是否满足,于是在第一个参数被推导为Any类型的情况下,List[Int] 符合Any的子类型。

def bar[A,B](a: A, b: B)(implicit ev: B <:< A) = (a,b)

scala> bar(1,List(1,2,3))
<console>:9: error: Cannot prove that List[Int] <:< Int.

通过隐式参数ev来证明类型时,类型推断过程不会像上面那样再向上寻找可能满足的情况,而直接报错。

确实,在用 <: 声明类型约束的时候,不如用<:<更严格,除了上面的类型推导,存在隐式转换的情况下:

scala> def foo[B, A<:B] (a:A,b:B) = print("OK")

scala> class A; class B;

scala> implicit def a2b(a:A) = new B

scala> foo(new A, new B)  //存在A到B的隐式转换,也可满足
OK

scala> def bar[A,B](a:A,b:B)(implicit ev: A<:<B) = print("OK")

scala> bar(new A, new B)  //隐式转换并不管用
<console>:17: error: Cannot prove that A <:< B.

scala类型系统:21) type specialization与类爆炸

Type Specialization的paper,这里也已经有翻译了。简单的说,就是出于性能考虑,避免基础类型的装箱拆箱,为基础类型保留了特定的实现。

class V[@specialized T]{
    var i:T = _
}

上面用了specialized注释,除了定义一个泛型的V[A],之外,编译器还会额外生成9个特定的类型:

% scalac V.scala && ll
-rw-r--r--  1 hongjiang  wheel  1060 11  5 16:07 V$mcB$sp.class
-rw-r--r--  1 hongjiang  wheel  1070 11  5 16:07 V$mcC$sp.class
-rw-r--r--  1 hongjiang  wheel  1066 11  5 16:07 V$mcD$sp.class
-rw-r--r--  1 hongjiang  wheel  1063 11  5 16:07 V$mcF$sp.class
-rw-r--r--  1 hongjiang  wheel  1065 11  5 16:07 V$mcI$sp.class
-rw-r--r--  1 hongjiang  wheel  1060 11  5 16:07 V$mcJ$sp.class
-rw-r--r--  1 hongjiang  wheel  1063 11  5 16:07 V$mcS$sp.class
-rw-r--r--  1 hongjiang  wheel  1032 11  5 16:07 V$mcV$sp.class
-rw-r--r--  1 hongjiang  wheel  1063 11  5 16:07 V$mcZ$sp.class
-rw-r--r--  1 hongjiang  wheel  3549 11  5 16:07 V.class
-rw-r--r--  1 hongjiang  wheel    41 11  5 16:07 V.scala

hongjiang@whj-mbp /tmp/dd % javap V\$mcD\$sp     
Compiled from "V.scala"
public class V$mcD$sp extends V{
    public double i$mcD$sp;
    public double i$mcD$sp();
    public double i();              // 这个是针对double类型的
    public void i$mcD$sp_$eq(double);
    public void i_$eq(double);
    public boolean specInstance$();
    public void i_$eq(java.lang.Object);
    public java.lang.Object i();
    public V$mcD$sp();
}

从上面看到,哪些匿名类的类名中的:B,C,D,F,I,J,S,V,Z,分别对应 byte,char,double,float,int,long,short,void(scala里的Unit), boolean

在类型参数比较多的情况下,specialization会产生类爆炸的情况,参考stackoverflow上的一个例子

class Huge[@specialized A, @specialized B, @specialized C](
  val a: A, val b: B, val c: C
) {} // 730 files, 2.9 MB

上面的类产生了730个文件:9x9x9+1。之前在模拟perm gen的oom时,用到过这个特性。

//2012.5.30
在REPL下,模拟perm gen的oom案例:

虽然perm gen确实在不断增加,并且可能会OOM(如果perm gen设置比较小的话),但通过jconsole的类加载来看并非把这些定义的class都load了;对比了前后的class load

之前:3797 个class被load

运行一次:

class Test[@specialized A, @specialized B, @specialized C, @specialized D]

之后:4180 ,增加了383个而不是 9x9x9x9=6561个 why?

通过jvisualvm工具dump了前后的内存对比,scala.tools.nsc.io.VirtualFile 实例数从2增加到了 6573,增长了 6571 个,并且每运行一次都会增加 6571个,比6561多出10个

继续测试

class Test[@specialized A] 

也是会使 VirtualFile 新增 19个而非9个,另外多出来的10个实例还没有清楚是什么。

scala类型系统:20) 数组类型

在java里,引用类型的数组类型是支持协变的,即 String[] 类型是 Object[] 的子类型,martin问过gosling,回答是希望有一个通用处理数组的简单方法。

void sort(Object[] a, Comparator cmp) { … }

数组的协变被用来确保任意参数类型的数组都可以传入排序方法。随着java引入了泛型,sort方法可以用类型参数,因此数组的协变不再有用。只是考虑到兼容性。

scala里不支持数组的协变,以尝试保持比java更高的纯粹性。即 Array[String]的实例对象不能赋给Array[Any]类型的变量。

在数组的设计上,scala是走过弯路的,这里有篇文章翻自martin写的关于scala2.8数组的paper,已经解释的非常好了。

正是因为2.8中的数组背后的实现要与java保持一致,使得通过泛型创建某个数组时

def test[T]() {
    val a = new Array[T] //运行时类型缺失,无法创建对应的java数组
}

因为java里的数组,实际会对应int[],float[],char[],等8个基础类型数组,与1个支持协变的引用类型数组。

更细的看一下java引用类型的数组类型:

scala> class A { 
|       val a1 = new Array[java.lang.Object](1);
|       val a2 = new Array[String](1);
| }

scala> :javap A    
...
//  a1:[Ljava/lang/Object;
...
//  a2:[Ljava/lang/String;

看到String[]会被编译器翻译为[Ljava/lang/String,而Object[]被翻译为[Ljava/lang/Object,其实可以看做是一种泛型类型的特例,[L 是类型构造器,StringObject 等是类型参数。但不同于java里其他泛型集合的实现,数组类型中的类型参数在运行时是必须的,即 [Ljava/lang/String[Ljava/lang/Object 是两个不同的类型,不像 Collection<String>Collection<StringBuilder> 运行时参数类型都被擦拭掉,成为Collection<Object>

为此,2.8中不得不引入了Manifest来保存T在运行时的类型信息(参考上一篇对Manifest与TypeTag的介绍),从而保证运行时scala数组与java的数组实现一致。