这周的课程没有作业，全是视频

Functions and State

首先我们需要回忆函数求值的过程，举一个例子

1
2
3
4
def iterate(n: Int, f: Int => Int, x: Int) = 
  if (n == 0) x else iterate(n-1, f, f(x))

def square(x: Int) = x * x

在这个定义下，求iterate(1, square, 3)

1
2
3
4
5
6
7
iterate(1, square, 3)
= if (1 == 0) x else iterate(1-1, square, square(3))
= iterate(0, square, square(3))
= iterate(0, square, 3 * 3)
= iterate(0, square, 9)
= if (0 == 0) 9 else iterate(0-1, square, square(9))
= 9

在这个变换过程中，可以随时选择任意一个路径化简，而不影响结果

对于if (1 == 0) x else iterate(1-1, square, square(3))

  • iterate(1-1, square, square(3))
  • if (1 == 0) x else iterate(1-1, square, 3 * 3)

以上两者是等价的。

因为最后的结果总是会交汇的。

这个规律有个难记的名字叫 Church-Rosser Theorem

上面的情况适用于没有状态转换的情况，如果我们引入的状态/副作用呢？

以存款取款为例

1
2
3
4
5
6
7
8
9
10
11
12
class BankAccount {
  private var balance = 0
  def deposit(amount: Int): Unit = {
    if (amount > 0) balance = balance + amount
  }
  def withdraw(amount: Int): Int = {
    if (0 < amount && amount <= balance) {
      balance = balance - amount
      balance
    } else throw new Error("insufficient funds")
  }
}

在REPL里测试下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
scala> val acc = new BankAccount
val acc: BankAccount = BankAccount@6e090aaa

scala> acc deposit 50

scala> acc withdraw 20
val res5: Int = 30

scala> acc withdraw 20
val res6: Int = 10

scala> acc withdraw 20
java.lang.Error: insufficient funds
  at BankAccount.withdraw(<pastie>:10)
  ... 32 elided

对于有状态类，我们对它进行同样的操作，结果会不同

Identity and Change

如果用E来代替抽象的表达式，如果

val x = E; val y = E并且x等于y

那么我们可以把上述表达式改写成val x = E; val y = x

这样的性质叫做引用透明(referential transparency)

这有什么好处呢？

  • 可以帮助证明程序的正确性(参照之前的数学归纳法证明)
  • 可以便于重构和修改代码(由于不会修改到可变的状态)
  • 可以通过记忆化，公共子表达式消除、惰性求值、或并行化来优化代码

但是现实生活中很多时候不满足这个性质

以之前的账户来举例

1
2
val 你 = new BankAccount
val 我 = new BankAccount

你和我都开了一个账户，我们的账户显然不一样。

为什么不一样呢？因为BankAccount中存放了可变的值余额

Loops

首先看一个计算乘方的例子

1
2
3
4
5
6
7
8
9
def power(x: Double, exp: Int): Double = {
  var r = 1.0
  var i = exp
  while (i > 0) {
    r = r * x
    i = i - 1
  }
  r
}

如果是习惯了命令式写法的选手，会觉得这个代码真是莫名其妙

为什么我不能直接对传入的参数修改，还得多此一举地声明两个新的变量r和i

还记得上一个小节提到地引用透明吗？其实这里的while循环不是必要的，我们可以用函数来消除其中不必要的状态量r和i

1
2
3
4
5
6
def WHILE(condition: => Boolean)(command: => Unit): Unit = {
  if (condition) {
    command 
    WHILE(condition)(command)
  } else ()
}

啊这，为什么写成这个鬼样子，原版的while不是简单多了？改成递归不怕爆栈吗？说好的参数是不能修改的，不就成死循环了？

不要急，下面会逐一解释。

我们可以看到，这个函数是柯里化的，第一个参数和第二个参数都是call by name

之所以设计成call by name，是为了能在每次调用时，都能感知到状态的变化，而不是传入时立即计算出结果，

之后就不变了，所以不会死循环。

另一方面，函数的返回值和自身的签名相同，或者是一个基本类型(对，Unit也是基本类型)

而这恰好满足了尾递归优化的条件，编译器会帮助我们将其展开成迭代的方式，这样只会用到常量大小的栈空间，从而避免的爆栈(StackOverflow)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
scala> def WHILE(condition: => Boolean)(command: => Unit): Unit = {
     |   if (condition) {
     |     command 
     |     WHILE(condition)(command)
     |   } else ()
     | }
def WHILE(condition: => Boolean)(command: => Unit): Unit

scala> val i = 5
val i: Int = 5

scala> var i = 5
var i: Int = 5

scala> var sum = 0
var sum: Int = 0

scala> while (i > 0)({sum += i; i-=1})

scala> sum
val res1: Int = 15

Extend Example: Discrete Event Simlation

本周课程的剩余时间，主要讲解如何实现一个模拟电路

由于个人的兴趣（模电数电的阴影），下面的内容就跳过了（可能之后会补上）

有兴趣的可以去了解下，如何用chisel3实现5级指令流水线