月度归档:2014年03月

scala类型系统:柯里-霍华德同构

通过柯里-霍华德同构实现联合类型

在这个系列之前的这篇blog scala类型系统:10) 交集类型与联合类型 里曾提到过实现union类型的另一种方式是柯里-霍华德同构

这段代码是从这里看到的:

type ¬[A] = A => Nothing
type ∨[T, U] = ¬[¬[T] with ¬[U]]
type ¬¬[A] = ¬[¬[A]]
type |∨|[T, U] = { type λ[X] = ¬¬[X] <:< (T ∨ U) }

def size[T : (Int |∨| String)#λ](t : T) = t match {
    case i : Int => i
    case s : String => s.length
}

scala> size(3)
res0: Int = 3

scala> size("three")
res1: Int = 5

要理解这段类型证明,先要了解复合类型,结构类型,函数类型的逆变,类型投影,以及type-lambda等,这些点可以从之前的blog里参考。

对于普通的class来说,A with B复合类型是类型AB的子类型:

scala> import scala.reflect.runtime.universe._

scala> class A; class B;

scala> typeOf[A with B] <:< typeOf[A]
res0: Boolean = true

但对于函数类型,因为其参数类型是逆变的,所以情况正好反过来:

scala> typeOf[ A=>Nothing ] <:< typeOf[ (A with B)=>Nothing ]
res1: Boolean = true

用图来看:

 __________               _________________________ 
|          |             |                         |
|     A    |             |  (A with B) => Nothing  |
|__________|             |_________________________|
      ^                               ^ 
      |                               | 
 __________               _________________________ 
|          |             |                         |
| A with B |             |        A => Nothing     |
|__________|             |_________________________|  

所以,我们把上文中定义的:¬[¬[A]]¬[¬[T] with ¬[U]] 两个表达式展开的话,会发现这两个函数类型是有继承关系的(如果参数类型A与T或U相同的话):

//¬[¬[A]]
scala> type T1 = (A=>Nothing) => Nothing  

//¬[¬[T] with ¬[U]]
scala> type T2 = ((A=>Nothing) with (B=>Nothing)) => Nothing  

scala> typeOf[T1] <:< typeOf[T2]
res3: Boolean = true

然后定义了一个结构类型:

type |∨|[T, U] = { type λ[X] = ¬¬[X] <:< (T ∨ U) }

这个结构类型里的λ是一个类型工厂,当传入给它某个类型参数时,它会构造出一个新的类型 ¬¬[X] <:< (T ∨ U) ,这个是中缀写法,还原成普通类型写法是: <:<[¬¬[X], (T ∨ U)] 关于 <:< 这个类型是用于约束两个类型关系的,它是在Predef里定义的:

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

它要求 ¬¬[X] 是类型 T v U (即v[T,U])的子类型。

而这个要求,我们前边证明 ¬[¬[X]]¬[¬[T] with ¬[U]] 的关系时已经论证过了,当类型参数X与T或U一致时即:

// 只有当
X =:= T //或 
X =:= U 

//下面的约束才成立
¬¬[X] <:< (T ∨ U) 

那么现在来单独用λ这个类型构造器,它的表达方式为 (T |v| U)#λ,这是一段type-lambda,它描述的是一个构造器类型,它可以由类型参数X,构造出一个复杂的约束类型:

<:<[(X=>Nothing)=>Nothing, ((T=>Nothing) with (U=>Nothing))=>Nothing]

这个约束类型能够编译通过的前提如前边所说,需要X等于TU才行。

现在我们把用一个具体的,由IntString类型参数构造的 |∨|[Int, String] 类型中的λ类型构造器用Factory来表示:

type Factory[T] = (Int |∨| String)#λ[T]

这个Factory类型构造器,对于任何类型参数 T,构造出的类型展开后为:

<:<[(T=>Nothing)=>Nothing, ((Int=>Nothing) with (String=>Nothing))=>Nothing]

也就是说T必须是IntString才能满足。最后用隐式参数的方式(context bound)在方法定时时描述这种约束

def size[T: Factory](p: T) = ...

相当于:

def size[T](p: T)(implicit ev: Factory[T]) ...

如果你纳闷这个ev隐式参数是哪里来的,参考一下以前的这篇: scala类型系统:22) 类型约束与特定方法

整个过程只涉及到类型证明,与以前的实现方式对比不需要显式提供任何隐式转换或隐式参数(只用到了语言默认提供的一个隐式参数),也没有创建任何“单例”或“实例对象”,柯里-霍华德同构可以简单理解为类型证明(type-lambda)即程序。

scala类型系统:类型推导

类型推导是一门博大的学问,背后有繁冗的理论,好在非编译器开发者不用太多了解,我看到这方面的文章时立刻就知难而退了。这里蜻蜓点水的带过。

Scala采用的局部的(local)、基于流的(flow-based)类型推断;而非像ML,Haskell等语言采用的更加全局化的Hindley-Milner类型推断方式。

在《Programming in Scala》一书中提到基于流的类型推断有它的局限性,但是对于面向对象的分支类型处理比Hindley-Mlner更加优雅。

基于流的类型推导在偏应用函数场景下,不能对参数类型省略,正体现了它的局限性。下面的偏应用函数声明,在Hindley-Milner类型推导(基于全局的)可以正常的推导的,会在scala里报错:

scala> def foo(a:Int, b:String) = a+b

scala> val f = foo(200, _)
<console>:8: error: missing parameter type for expanded function ((x$1) => foo(200, x$1))
   val f = foo(200, _)
                    ^

上面第二个参数占位符缺乏类型。需要显式的声明变量f的类型

scala> val f: String=>String = foo(200, _)
f: String => String = <function1>

或者显式的声明占位符参数类型

scala> val f = foo(200, _:String)
f: String => String = <function1>

不过这里有一个细节是eta-expansion的情况下可以省略参数类型,比如:

scala> def foo(a:Int, b:String) = a+b

scala> val f = foo _
f: (Int, String) => String = <function2>

scala> val f = foo(_,_)
f: (Int, String) => String = <function2>

上面两种写法占位符都是对全部参数,foo _foo(_,_) 在编译过程会编译器会进行eta-expansioneta扩展会把这个表达式转换为与foo方法类型一致的函数对象。这是在规范里定义的。

而最开始的写法 foo(200, _)并不是eta-expansion(原因见之前的这篇)。这种情况下类型推导并不会从方法体的上下文去推断参数的类型。所以需要显式的声明参数类型。

另外,对于泛型方法的情况,类型推导也需要注意泛型参数,参考这篇

java可以创建多少个线程

记得以前在jvm的群里讨论过,与系统环境设置有关,我在mac os上试验的。

% sysctl kern.num_taskthreads  
kern.num_taskthreads: 2048

用repl来模拟一下,在启动repl后线程大概有20个左右,现在看看还可以启动多少个线程:

scala> import java.util.concurrent.atomic.AtomicInteger

scala> val n = new AtomicInteger(0)

scala> val run = new Runnable(){
        override def run() { n.incrementAndGet ;Thread.sleep(1000000) }}

scala> try{ while(true){ val t = new Thread(run); t.start } } catch{
            case e:Throwable => println("count: " + n.get) 
        }
count: 2025

运行过程中jvm可能还有其他线程也会启动,总的线程数加起来正好2048(或者接近).

如果系统参数设置一个很大的值,那java可创建的线程数就只与内存相关了。

如果指定的-Xss越大,java进程在non-heap区域为每个线程分配的初始也越大。栈空间分配的初始值通常比Xss设定的要小,VM并不会一上来就分配与之对等的内存。

另外一点有趣的是,如果你分配给jvm的堆空间(heap size)太大,系统中如果没有足够多的剩余空间的话,non-heap可分配的就越小,可创建的线程数也反而少了。也就是说heap与non-heap是竞争关系。参考这里

scala类型系统:case class与代数数据类型

ADT(algebraic data type) 是很多函数式编程语言中支持的一种类型。不清楚最初是否来自haskell。

《Programming in Scala》中文版,在术语表中有提到ADT:

通过提供若干个含有独立构造器的备选项(alternative)来定义的类型。通常可以辅助于通过模式匹配解构类型的方式。这个概念可以在规约语言和函数式语言中发现。代数数据类型在Scala中可以用样本类(case class)模拟。

参考wiki:http://en.wikipedia.org/wiki/Algebraic_data_type

在计算机编程、特别是函数式编程与类型理论中,代数数据类型(ADT)是一种组合类型(composite type).例如,一个类型由其它类型组合而成。两个常见的代数类型是product(乘积)类型(比如tuplesrecords)和sum类型,它也被称为”tagged unions”或”variant type”

ADT最大的价值是用于“模式匹配”,即解构一个对象。

我们看看Scala怎么用case class模拟ADT,比如一副扑克按花色来分类:

sealed abstract class Suit
case class Heart(value: Int) extends Suit
case class Diamond(value: Int) extends Suit
case class Spade(value: Int) extends Suit
case class Club(value: Int) extends Suit

当然case class的构造参数并没有限制,比如下面这个描述一棵树的节点和叶子:

sealed abstract class Tree
case class Node(left: Tree, right: Tree) extends Tree
case class Leaf[A](value: A) extends Tree
case object EmptyLeaf extends Tree

关于case class更多细节请参考模式匹配系列blog。

scala2.11编译器对lint的增强

scala2.11的编译器对lint也做了一些改善,对没有用的局部变量会给出警告,比如:

% cat /tmp/A.scala

object A{
    def foo() {
        val a = 2
        println("ok")
    }
}

% ./scalac -Xlint /tmp/A.scala

/tmp/A.scala:4: warning: local val in method foo is never used
val a = 2
    ^

对于类型推导方面,下面的情况也给出了合适的警告 (在2.10下lint不会警告)

% ./scala -Xlint

scala>  def mycons[B](x:B, xs:List[B]):List[B] = x :: xs

scala> mycons("hi", List(200))
<console>:9: warning: a type was inferred to be `Any`; this may indicate a programming error.
          mycons("hi", List(200))
                 ^
res0: List[Any] = List(hi, 200)

上面两个参数类型分别是StringList[Int],编译器为了能通过方法,在类型推导时把两个参数当成AnyList[Any]来对待,这有可能与实际预期不否,给出警告还是很有用的。

scala2.11编译环节的一些变动: delambdafy

scala2.11在编译环节与2.10相比,默认去掉了cps和一些优化环节(phase),同时也引入了delambdafy这个“去lambda化”的环节,见下面的22:

    % scalac -Xshow-phases
        phase name  id  description
    ----------  --  -----------
        parser   1  parse source into ASTs, perform simple desugaring
         namer   2  resolve names, attach symbols to named trees
packageobjects   3  load package objects
         typer   4  the meat and potatoes: type the trees
        patmat   5  translate match expressions
superaccessors   6  add super accessors in traits and nested classes
    extmethods   7  add extension methods for inline classes
       pickler   8  serialize symbol tables
     refchecks   9  reference/override checking, translate nested objects
       uncurry  10  uncurry, translate function values to anonymous classes
     tailcalls  11  replace tail calls by jumps
    specialize  12  @specialized-driven class and method specialization
 explicitouter  13  this refs to outer pointers
       erasure  14  erase types, add interfaces for traits
   posterasure  15  clean up erased inline classes
      lazyvals  16  allocate bitmaps, translate lazy vals into lazified defs
    lambdalift  17  move nested functions to top level
  constructors  18  move field definitions into constructors
       flatten  19  eliminate inner classes
         mixin  20  mixin composition
       cleanup  21  platform-specific cleanups, generate reflective calls
    delambdafy  22  remove lambdas
         icode  23  generate portable intermediate code
           jvm  24  generate JVM bytecode
      terminal  25  the last phase during a compilation run

通过 -Ydebug 选项可以把没有使用的phases也显示出来:

 % scalac -Xshow-phases -Ydebug
   ...
    selectiveanf  xx  ANF pre-transform for @cps
    selectivecps  xx  @cps-driven transform of selectiveanf assignments
   ...
         inliner  xx  optimization: do inlining
  inlinehandlers  xx  optimization: inline exception handlers
        closelim  xx  optimization: eliminate uncalled closures
        constopt  xx  optimization: optimize null and other constants
             dce  xx  optimization: eliminate dead code

上面的这些phases是2.11编译过程中默认没有启用的,而在scala2.10默认编译过程是有启用的(2.10的phases参考这里

selectiveanfselectivecps是针对cps的,在2.11中如果要用,需要显示的增加-P:continuations:enable编译选项;另外5个optimization也需要显示的增加-optimise选项:

    % scalac -Xshow-phases -optimise -P:continuations:enable
        phase name  id  description
    ----------  --  -----------
        parser   1  parse source into ASTs, perform simple desugaring
         namer   2  resolve names, attach symbols to named trees
packageobjects   3  load package objects
         typer   4  the meat and potatoes: type the trees
        patmat   5  translate match expressions
superaccessors   6  add super accessors in traits and nested classes
    extmethods   7  add extension methods for inline classes
       pickler   8  serialize symbol tables
     refchecks   9  reference/override checking, translate nested objects
  selectiveanf  10  ANF pre-transform for @cps
  selectivecps  11  @cps-driven transform of selectiveanf assignments
       uncurry  12  uncurry, translate function values to anonymous classes
     tailcalls  13  replace tail calls by jumps
    specialize  14  @specialized-driven class and method specialization
 explicitouter  15  this refs to outer pointers
       erasure  16  erase types, add interfaces for traits
   posterasure  17  clean up erased inline classes
      lazyvals  18  allocate bitmaps, translate lazy vals into lazified defs
    lambdalift  19  move nested functions to top level
  constructors  20  move field definitions into constructors
       flatten  21  eliminate inner classes
         mixin  22  mixin composition
       cleanup  23  platform-specific cleanups, generate reflective calls
    delambdafy  24  remove lambdas
         icode  25  generate portable intermediate code
       inliner  26  optimization: do inlining
inlinehandlers  27  optimization: inline exception handlers
      closelim  28  optimization: eliminate uncalled closures
      constopt  29  optimization: optimize null and other constants
           dce  30  optimization: eliminate dead code
           jvm  31  generate JVM bytecode
      terminal  32  the last phase during a compilation run

之所以默认放弃了optimization的几个选项大概是因为很难实现好,导致的问题较多收益不大(参考这里这里);而放弃cps选项则是因为scala后续2.12将不再包含continuations插件和库,转而采用Async来替代,因为基于CPS重写(CPS-based rewriting)的异步代码每次暂停时会产生一个闭包,同时也可能导致类型错误并且难以理解。

现在来看一下delambdafy这个新增的phase,借用adriaanm的例子

object Test {
    def takeLambda(f: Int => Int ): Int = f(12)

    def main(args: Array[String]): Unit = {
        println(takeLambda(x => x+1))
        println(takeLambda(x => x*2))
    }
}

先不启用delambdafy选项看看编译结果:

% scalac -print /tmp/Test.scala
...

def main(args: Array[String]): Unit = {
  scala.this.Predef.println(scala.Int.box(Test.this.takeLambda({
    (new <$anon: Function1>(): Function1)
  })));
  scala.this.Predef.println(scala.Int.box(Test.this.takeLambda({
    (new <$anon: Function1>(): Function1)
  })))
};

...

@SerialVersionUID(0) final <synthetic> class anonfun$main$1 extends 
                    scala.runtime.AbstractFunction1$mcII$sp with Serializable {
    final def apply(x: Int): Int = anonfun$main$1.this.apply$mcII$sp(x);
    <specialized> def apply$mcII$sp(x: Int): Int = x.+(1);
    final <bridge> <artifact> def apply(v1: Object): Object = 
                scala.Int.box(anonfun$main$1.this.apply(scala.Int.unbox(v1)));

    def <init>(): <$anon: Function1> = {
        anonfun$main$1.super.<init>();
        ()
    }
};
@SerialVersionUID(0) final <synthetic> class anonfun$main$2 extends 
                    scala.runtime.AbstractFunction1$mcII$sp with Serializable {
    final def apply(x: Int): Int = anonfun$main$2.this.apply$mcII$sp(x);
    <specialized> def apply$mcII$sp(x: Int): Int = x.*(2);
    final <bridge> <artifact> def apply(v1: Object): Object = 
                scala.Int.box(anonfun$main$2.this.apply(scala.Int.unbox(v1)));

    def <init>(): <$anon: Function1> = {
        anonfun$main$2.super.<init>();
        ()
    }
}
...

再看看使用delambdafy:method选项:

% scalac -Xprint:jvm -Ydelambdafy:method /tmp/Test.scala
...

def main(args: Array[String]): Unit = {
  scala.this.Predef.println(scala.Int.box(Test.this.takeLambda({
    (new main1(): runtime.AbstractFunction1).$asInstanceOf[Function1]()
  })));
  scala.this.Predef.println(scala.Int.box(Test.this.takeLambda({
    (new main2(): runtime.AbstractFunction1).$asInstanceOf[Function1]()
  })))
};

final <artifact> private[this] def $anonfun$1(x: Int): Int = x.+(1);
final <artifact> private[this] def $anonfun$2(x: Int): Int = x.*(2);

final <synthetic> <static> <bridge> protected def accessor1(x: Int): Int = 
                                    Test.this.$anonfun$1(x);
final <synthetic> <static> <bridge> protected def accessor2(x: Int): Int = 
                                    Test.this.$anonfun$2(x)
...

@SerialVersionUID(0) final <synthetic> class main2 extends 
                    runtime.AbstractFunction1 with Serializable {
    <synthetic> def <init>(): main2 = {
        main2.super.<init>();
        ()
    };
    final <synthetic> def apply(x: Int): Int = Test.this.accessor2(x);
    final <synthetic> <bridge> def apply(x: Object): Object = 
                            scala.Int.box(main2.this.apply(unbox(x)))
};
@SerialVersionUID(0) final <synthetic> class main1 extends 
                    runtime.AbstractFunction1 with Serializable {
    <synthetic> def <init>(): main1 = {
        main1.super.<init>();
        ()
    };
    final <synthetic> def apply(x: Int): Int = Test.this.accessor1(x);
    final <synthetic> <bridge> def apply(x: Object): Object = 
                            scala.Int.box(main1.this.apply(unbox(x)))
}

在开启delambdafy:method选项之后,原先在匿名类中实现的方法,被移到了当前对象中,并提供了静态accessor方法,在scala.tools.nsc.transform.Delambdafy的文档里是这么描述的:

1) a static forwarder at the top level of the class that contained the lambda 
2) a new top level class that 
    a) has fields and a constructor taking the captured environment 
    b) an apply method that calls the static forwarder 
    c) if needed a bridge method for the apply method 
3) an instantiation of the newly created class which replaces the lambda

目前还是一个实验性质,这个做法更接近用method handles,显然是为了下一步支持jsr292做准备的。

scala2.11字节码仍兼容jdk1.6,不会采用invokedynamic,而scala2.12的字节码会直接跳到 jdk1.8。

Email正则表达式问题

有段email的正则表达写法是这样的:

^\w+([-+.']\w+)*@\w+([-.]\w+)*\.\w+([-.]\w+)*$

测试指出,这段正则的逻辑里,允许了域名的部分包含下划线,这是不合法的,比如这个非法的email用上面的可以通过:

scala> val pattern = """^\w+([-+.']\w+)*@\w+([-.]\w+)*\.\w+([-.]\w+)*$"""

scala> "a@b_.cn" matches pattern
res45: Boolean = true

于是开发后来修改成了这样的表达式:

[a-zA-Z0-9._+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,4}

这个限制了域名部分只能是字母、数字、点和横杠,甚至最后边的顶级域名是2到4位字符,看上去靠谱,但测试又测出了这种情况:

scala> val pattern = """[a-zA-Z0-9._+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,4}"""

scala> "a@..info" matches pattern
res46: Boolean = true

开发开始google,然后发现这个问题并没有那么简单。首先如果按照rfc规范来说,Email地址从语义上可以支持的格式非常广泛,可以说是五花八门,参考这里:http://en.wikipedia.org/wiki/Email_address

对于域名中是否允许包含下划线的问题,在rfc1034和2181规范里没有禁止使用下划线的,参考这里:http://stackoverflow.com/questions/2180465/can-someone-have-a-subdomain-with-an-underscore-in-it,他举例这两个都是:

_jabber._tcp.gmail.com 
_sip._udp.apnic.net

但貌似为了避免混乱,又不建议DNS里使用下划线: http://www.quora.com/Domain-Name-System-(DNS)/Why-are-underscores-not-allowed-in-DNS-host-names

Email的RFC经历过好几次修订,从最初的rfc822到后来的rfc2822再到rfc5322,是在不断补充增强的。

要支持完整的合理语义Email,并不是一个简单的正则能表达的,从这里http://stackoverflow.com/questions/201323/using-a-regular-expression-to-validate-an-email-address 的讨论看来,能够完整的支持Email地址的那个正则复杂度已经大大超出了预期,所以只能选择一个对业务来说适合绝大部分情况的,最终从这篇帖子里选择了下面的表达式:

^[a-zA-Z0-9.!#$%&'*+/=?^_`{|}~-]+@[a-zA-Z0-9](?:[a-zA-Z0-9-]{0,61}[a-zA-Z0-9])?(?:\.[a-zA-Z0-9](?:[a-zA-Z0-9-]{0,61}[a-zA-Z0-9])?)*$