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