Functional Programming 笔记(2)

尾递归是否真的节省了 JVM 调用开销?

我们总是“听说”这样一件事情,眼见为实!我们以经典的计算阶乘为例,下面是两个实现:

object factorial {

  def fac (n: Int):Int = {
    def facIter (n:Int, prod:Int) : Int = {
       if (n == 0) prod else facIter (n-1, n*prod)
    }

    facIter (n, 1)
  }

  def fact (n: Int): Int =
    if (n<1) 1 else n * fact (n-1)

  def main (arg: Array [String]) = {
    println (fac (arg(0) toInt))
  }

}

编译后产生 factorial.class 和 factorial$.class 两个文件,前者可以看成是一个 wrapper,将 scala 的表示呈现到 java 里面,因此对应于一个 Java 的 class 的 static 方法,通过 javap 我们就能看到这些函数的声明。实际的实现在后者里面,我们使用 javap -c -p 将文件的 byte code 解析出来

 public int fact(int);
    Code:
       0: iload_1       
       1: iconst_1      
       2: if_icmpge     9
       5: iconst_1      
       6: goto          18
       9: iload_1       
      10: aload_0       
      11: iload_1       
      12: iconst_1      
      13: isub          
      14: invokevirtual #26                 // Method fact:(I)I
      17: imul          
      18: ireturn

  public int fac(int);
    Code:
       0: aload_0       
       1: iload_1       
       2: iconst_1      
       3: invokespecial #19                 // Method facIter$1:(II)I
       6: ireturn

  private final int facIter$1(int, int);
    Code:
       0: iload_1       
       1: iconst_0      
       2: if_icmpne     7
       5: iload_2       
       6: ireturn       
       7: iload_1       
       8: iconst_1      
       9: isub          
      10: iload_1       
      11: iload_2       
      12: imul          
      13: istore_2      
      14: istore_1      
      15: goto          0

很清楚的我们发现尾递归的调用使用 goto 将指令 rewind 到这个函数开头,的确利用了当前的 function frame,而并没有引入额外的函数调用。其实 C/C++ 编译器一样也知道什么情况下可以做类似的优化,作为程序员,尽量保证自己的代码通过 tail recursion 呈现就能保证通过一定的编译优化就能避免递归带来的额外开销。

higher-order functions

这个说起来就是把函数作为另一个函数的输入,往往这样做不如将函数还作为这个 higher-order function 的输出。课程中的例子很简单,就是将指定范围里面的整数进行 map/reduce,最开始 reduce 操作假定就是相加,函数定义就是 sum(Int => Int, Int, Int):Int,而后发现其实可以写成 sum (Int=>Int): ((Int, Int):Int),也就是说干脆把 sum 弄成一个接收 map 的函数,它返回的是一个接收整数范围返回整数的函数,作为 grammar sugar 这个可以简化写成 sum(Int=>Int) (Int, Int) : Int。可能从实现上来看两者差异挺大,但是这到底是如何的一个关系呢?我们简单的看看

object sum {

  def sum1 (f: Int => Int) : (Int, Int) => Int = {
    def red (a: Int, b:Int) : Int =
      if (a > b) 0 else f (a) + red (a + 1, b)
    red
  }

  def sum2 (f: Int => Int) (a:Int, b:Int) : Int =
    if (a > b) 0 else f (a) + sum2 (f) (a + 1, b)

  def sum3 (f: Int => Int, a:Int, b:Int) : Int =
    if (a > b) 0 else f (a) + sum3 (f, a + 1, b)

  def main (arg : Array[String]) = {
    def id (a : Int) = a
    assert (sum1 (id) (1, 5) == sum2 (id) (1, 5),
      "return value should be the same")
    assert (sum2 (id) (1, 5) == sum3 (id, 1, 5),
      "return value should be the same")

    def my_sum2 (a:Int, b:Int): Int = sum2 (id) (a, b)
    def my_sum3 (a:Int, b:Int): Int = sum3 (id, a, b)

    val sum2_alt : (Int, Int) => Int = sum2 (id)
    val sum3_alt : (Int, Int) => Int = (a:Int, b:Int) => sum3 (id, a, b)
    assert (sum1 (id) (1, 5) == sum2_alt (1, 5),
      "return value should be the same")
    assert (sum1 (id) (1, 5) == sum3_alt (1, 5),
      "return value should be the same")
  }
}

比较神奇的是怎么 interpret 这里的一些结果。如果你比较三者的代码,发现后两者比较接近,但是似乎从使用上来看 sum1/sum2 却是接近的,你如果对课程比较熟悉,某人还会告诉你 sum2 的 type 其实是跟 sum1 完全一致的。那么 scala 背后到底是怎样的呢?你可以和前面一样比较三者的反汇编结果,你会发现 sum2/sum3 居然是一模一样的,而 sum1 却截然不同。换言之,通过 type system 居然将两个完全一样的东西弄得用起来截然不同了。这也就是为什么称为 grammar sugar 了,实现类似的效果,sum1 的代码要显得复杂一些。

这里注意似乎 scala 2.9 在返回类型是函数类型(即 (输入参数类型) => 返回类型)时,似乎必须声明,否则竟然无法推断返回的是啥。这个可能跟 scala 放松了对括弧的要求有关系,一个没有参数的函数既可以写函数名也可以加上括号。所以返回类型或者是函数类型或者是函数返回的类型。

这类书写常被称为 curry,我们从例子里面看到,除了通过这个 grammar sugar 来实现,我们也能通过匿名函数来做,只是稍微显得麻烦,类似 groovy 这类支持 Closure 但没有对 curry 直接支持的语言,一般就是通过匿名函数来解决了。

固定点迭代与 momentum

其实觉得某人是不是数学系出身的,给的例子都是数值计算的,这个问题其实规则也很简单:一个是判定收敛,一个是迭代一次,利用 curry 我们可以将这个过程写的比较简单。例子里面通过 fixed point 求解平方根不收敛,加入了 momentum 收敛,等价于 Newton 法的结果。

语言一些小结

类型系统,比较重要的就是 Any 下面 AnyRef 和 AnyVal,另外就是 Nothing 和 Null。

——————
And he went, and fetched, and brought them to his mother: and his mother made savoury meat, such as his father loved.

Advertisements
Functional Programming 笔记(2)

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s