[toc]

Martin Odersky - Working Hard to Keep It Simple

1.1 编程范式

主要编程范式：

• 命令式编程
  • 定义可变变量
  • 使用赋值
  • 使用控制结构，如 if-else-then, loops, break, continue, return
• 函数式编程
  • 严格意义上，函数式编程意味着没有可变变量，赋值，循环和其他命令式控制结构
  • 广泛来讲，函数式编程意味着关注于函数
  • 特别地，函数可以是生成，使用和组合的值
  • 函数是一等公民
    • 可定义于任何地方，包括其它函数内部
    • 可作为函数参数和返回值
    • 一系列操作组合成函数
• 逻辑编程

与之相对的是：

• 面向对象编程
  • 非严格意义上的编程范式，是上述几种范式的一个交叉产物

1.2 编程元素

算术表达式求值过程
(2 * pi) * radius
(2 * 3.14159) * radius
6.28318 * radius
6.28318 * 10
62.8318

带有参数的定义

scala> def square(x: Double) = x * x
square: (Double)Double

scala> square(2)
4.0

scala> square(5 + 4)
81.0

scala> def sumOfSquares(x: Double, y: Double) = square(x) + square(y)
sumOfSquares: (Double, Double)Double

scala> def power(x: Double, y: Int): Double = ...

代换模型

所有求值过程都会将一个表达式化简成一个值

求值策略

scala通常使用 call-by-value

call-by-value (CBV)

优势：所有函数参数只求值一次

sumOfSquares(3, 2+2)
sumOfSquares(3, 4)
square(3) + square(4)
9 + square(4)
9 + 16
25  

call-by-name (CBN)

优势：函数体未用到的参数不会被求值

sumOfSquares(3, 2+2)
square(3) + square(2+2)
3 * 3 + square(2+2)
9 + square(2+2)
9 + (2+2) * (2+2)
9 + 4 * 4
9 + 16
25

1.3 求值策略和终止

def loop: Int = loop

def first(x: Int, y: Int) = x

使用CBN first(1, loop) 结果为1
使用CBVfirst(1, loop) 死循环

scala通常使用call-by-value，要使用call-by-name，在参数中使用=>

def constOne(x: Int, y: => Int) = 1

第一个参数为call-by-value，第二个参数为call-by-name

constOne(1 + 2, loop)
constOne(3, loop)
1

constOne(loop, 1 + 2)
...无限循环

1.4 条件语句和值定义

if-else

def abs(x: Int) if (x < 0) -x else x

Boolean

值定义 (def vs val)

def属于by-name的形式，每次使用时对右侧求值
val属于by-value的形式，定义时对右侧求值，变量名指向值

val x = 2
val y = square(x)

y 指向 4，而不是 square(2)

def loop: Boolean = loop

def x = loop 可以定义
val x = loop 导致死循环

不使用 && 和 || 定义 and(x, y) 和 or(x, y)

def and(x: Boolean, y: => Boolean) = if(x) y else false

def or(x: Boolean, y: => Boolean) = if(!x) false else y

第二个参数不使用=>的话，在调用and(false, loop)时会死循环

def or(x: Boolean, y: => Boolean) = if(x) true else y
def or(x: Boolean, y: => Boolean) = if(!x) y else true

1.5 用牛顿方法求平方根

计算 sqrt(x)

• 从一个初始的估计值y开始（正数即可，这里选择 y = 1）
• 重复对 y 和 取平均值来提升精确度，平均值作为下一轮估计值

sqrt(2)

object session {

  def abs(x: Double) = if (x < 0) -x else x

  def sqrtIter(guess: Double, x: Double): Double =
    if (isGoodEnough(guess, x)) guess
    else sqrtIter(improve(guess, x), x)

  def isGoodEnough(guess: Double, x: Double) =
    abs(guess * guess - x) / x < 0.001

  def improve(guess: Double, x: Double) =
    (guess + x / guess) / 2

  def sqrt(x: Double) = sqrtIter(1.0, x)

  sqrt(2)
  sqrt(4)
  sqrt(1e-6)
  sqrt(1e30)
}

有问题的实现：

  def isGoodEnough(guess: Double, x: Double) =
    abs(guess * guess - x) < 0.001

小数字不精确，大数字不会终止。
对于小数字，x可能会小于阈值（这里的0.001)
对于大数字，？？？

1.6 词法作用域和语句块

嵌套函数

def sqrt(x: Double) = {
  def sqrtIter(guess: Double, x: Double): Double =
    if (isGoodEnough(guess, x)) guess
    else sqrtIter(improve(guess, x), x)

  def improve(guess: Double, x: Double) =
    (guess + x / guess) / 2

  def isGoodEnough(guess: Double, x: Double) =
    abs(square(guess) - x) < 0.001

  sqrtIter(1.0, x)
}

语句块

定义方式：

// 它的值由最后一个表达式确定，可定义在任何地方
{ ... }

可见性：块内-外部不可见，外部-块内可见，相同变量名，内部覆盖外部
因此，内部函数中的参数x可以省略：

object session {

  def abs(x: Double) = if (x < 0) -x else x

  def sqrt(x: Double) = {

    def sqrtIter(guess: Double): Double =
      if (isGoodEnough(guess)) guess
      else sqrtIter(improve(guess))

    def isGoodEnough(guess: Double) =
      abs(guess * guess - x) / x < 0.001

    def improve(guess: Double) =
      (guess + x / guess) / 2

    sqrtIter(1.0)
  }

  sqrt(2)
  sqrt(1e-6)
  sqrt(1e60)
}

分号

// Scala中分号是可选的，通常会省略。
val y = 2;

// 如果多个语句在同一行，用分号隔开
val y = x + 1; y * y

// 长表达式分行放置
someLongExpression
+ someOtherExpression

// 上面表达式会被编译器分解成两行
someLongExpression;
+ someOtherExpression

// 可将长语句括号，不会被分解成多行语句
(someLongExpression
+ someOtherExpression)

// 或者将操作符放在第一行，告诉编译器表达式尚未结束
someLongExpression +
someOtherExpression

1.7 尾递归 (tail recursion)

计算最大公约数(欧几里得算法)

def gcd(a: Int, b: Int): Int =
  if (b == 0) a else gcd(b, a % b)

gcd(14, 21)执行过程：

if (21 == 0) 14 else gcd(21, 14 % 21)
if (false) 14 else gcd(21, 14 % 21)
gcd(21, 14 % 21)
gcd(21, 14)
if (14 == 0) 21 else gcd(14, 21 % 14)
...
gcd(14, 7)
...
gcd(7, 0)
if (0 == 0) 7 else gcd(0, 7 % 0)
7

阶乘

def factorial(n: Int): Int =
  if (n == 0) 1 else n * factorial(n - 1)

factorial(4)执行过程：

if (4 == 0) 1 else 4 * factorial(4 - 1)
...
4 * factorial(3)
4 * (3 * factorial(2))
4 * (3 * (2 * factorial(1)))
4 * (3 * (2 * (1 * factorial(0))))
4 * (3 * (2 * (1 * 1)))
120

Scala中的尾递归

如果一个函数将调用自身作为最后一个操作，则这个函数的栈帧 (stack frame) 可以重用。这被称为尾递归。

尾递归执行使用常数级的栈空间。

函数的最后一个动作包括调用一个函数（可能为自身），一个栈帧就足够两个函数使用。这被称为尾调用 (tail-calls)

gcd函数中最后一个操作为调用自身，是尾递归
factorial函数最后一个操作为 n * factorial(n - 1)，非尾递归

可以使用@tailrec来指定一个函数为尾递归

@tailrec
def gcd(a: Int, b: Int): Int = ...  // 如果实现方式非尾递归会报错

尾递归版 factorial

def factorial(n: Int): Int = {
  def loop(acc: Int, n: Int): Int = 
    if (n == 0) acc
    else loop(acc * n, n - 1)
  loop(1, n)
}