https://www.coursera.org/learn/progfun1
该课程更像是Scala版本的SICP

WEEK 1 notes:
这周主要是sbt、idea插件等环境准备，然后通过几个案例简单介绍下Scala的语法

  • 环境准备: jdk1.8, sbt0.13.x
  • Evaluation Rules: call by value, call by name
  • 牛顿迭代求平方根
  • 尾递归

Prepare

$ brew install sbt

# 国内repo
$ cat ~/.sbt/repositories
[repositories]
local
osc: http://maven.oschina.net/content/groups/public/
typesafe: http://repo.typesafe.com/typesafe/ivy-releases/, [organization]/[module]/(scala_[scalaVersion]/)(sbt_[sbtVersion]/)[revision]/[type]s/[artifact](-[classifier]).[ext], bootOnly
sonatype-oss-releases
maven-central
sonatype-oss-snapshots

# idea插件, 使用：cd 工程目录 && run `sbt gen-idea` && import project in idea
$ cat ~/.sbt/0.13/plugins/build.sbt
addSbtPlugin("com.github.mpeltonen" % "sbt-idea" % "1.6.0")

Evaluation Rules

  • Call by value: evaluates the function arguments before calling the function
  • Call by name: evaluates the function first, and then evaluates the arguments if need be
def test(x: Int, y: Int) = x * x

// which faster?
test(2, 3)      // same steps
test(3+4, 8)    // CBV
test(7, 2*4)    // CBN
test(3+4, 2*4)  // same steps
  • If CBV evaluation of an expression e terminates, then CBN evaluation of e terminates, too
  • The other direction is not true
def test(x: Int, y: Int) = x
test(1, loop)   // Under CBN --> 1
test(1, loop)   // Under CBV --> Non-termination
  • Scala normally use call-by-value, but if the type of a function parameter starts with => it uses call-by-name
def example = 2      // CBN, evaluated when called
val example = 2      // CBV, evaluated immediately
lazy val example = 2 // evaluated once when needed

def square(x: Double)    // call by value
def square(x: => Double) // call by name
def myFct(bindings: Int*) = { ... } // bindings is a sequence of int, containing a varying # of arguments

SICP Newton’s method

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) < 0.001

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

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

the isGoodEnough test is not very precise for small numbers and lead to Non-termination for very large numbers.

  • 0.001
  • 0.1e-20
  • 1.0e20
  • 1.0e50

the improved isGoodEnough

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

Blocks and Lexical Scope

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

def sqrt(x: Double) = {

  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

  sqrtIter(1.0, x)
}

much cleaner

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)
}

Tail Recursion

If a function calls itself as its last action, the function’s stack frame can be reused.
参照SICP 1.2节，递归计算过程的两种形式

  • linear recursive process 线性递归计算过程
    构造阶段会形成一个很长的链条，收缩阶段再执行具体计算操作
  • iterative process 迭代计算过程
    常量空间中执行迭代计算，即使这一计算是用递归过程描述的

Tail recursive functions are iterative processes.


不要混淆recursive process(递归计算过程)和recursive procedure(递归过程)；递归过程只是一个概念，而它的进展方式可以是迭代的，也可以是线性递归的
// Tail Recursion
def gcd(a: Int, b:Int): Int =
  if (b == 0) a else gcd(b, a % b)

// Not Tail Recursion, the expression gets bigger and bigger
def factorial(n: Int): Int =
  if (n == 0) 1 else n * factorial(n - 1)

Tail Recursion in Scala
尾递归一直被当做一种编译技巧，有了尾递归的实现，就可以用常规的调用机制表述迭代，所以能使各种复杂的专用迭代结构包装成各种语法糖；比如Scala @tailrec编译器优化尾递归，如果实现方法不是尾递归会报异常

//a tail recursive version of factorial
def factorialTailRecursion(n: Int): Int = {
  @tailrec
  def loop(acc: Int, n: Int): Int =
    if (n == 0) acc
    else loop(acc * n, n-1)
  loop(1, n)
}