程序的构造和解释

1. 构造函数抽象

先思考一个问题，如何计算平方根？
最常用的方法就是牛顿逐步逼近法， 比如我们要计算2的平方根，假定初始猜测值是1

猜测	商	平均值

一般我们用代码写出来就是下面这样：

    fun sqrtIter(guess: Float, x: Int): Float {
        if (goodEnough(guess, x)) {
            return guess
        } else {
            return sqrtIter(improve(guess, x), x)
        }
    }

    fun goodEnough(guess: Float, x: Float): Boolean {
        return Math.abs(square(guess) - x) < 0.001
    }

    fun improve(guess: Float, x: Float): Float {
        return average(guess, x / guess)
    }

    fun average(x: Float, y: Float): Float {
        return (x + y) / 2
    }

    fun sqrt(x: Float): Float {
        return sqrtIter(1.0f, x)
    }

在编程语言中，函数是一种用于封装可重用代码的语法结构。函数可以接收从外部调用环境传入的数据，并在函数体内以复合语句的形式，使用这些数据构建独立的功能逻辑单元。借助函数，我们可以将一个程序的实现过程拆分为多个子步骤，并以结构化的方式来构建程序。这种方式可以减少程序中的重复代码，并通过抽象和替换来提高代码的整体可读性，以及可追溯性。

我们可以看到，这些函数的抽象层级是不一样的，对于这里所说的抽象层级，我们不用去定量描述，只需要直观感受就行了。我们可以看到sqrtIter函数和goodEnough的抽象层级明显不一样，前者比后者抽象层级更高。

还有就是，求平方根函数的调用者不关心除了sqrt以外的函数，而且有的函数只能作为求平方根的辅助函数，无法复用，这个函数会占用一个唯一的函数名称，所以我们更希望将这种辅助函数局部化。

   fun sqrt(x: Float): Float {
        fun square(x: Float): Float {
            return x * x
        }

        fun goodEnough(guess: Float, x: Float): Boolean {
            return Math.abs(square(guess) - x) < 0.001
        }

        fun average(x: Float, y: Float): Float {
            return (x + y) / 2
        }

        fun improve(guess: Float, x: Float): Float {
            return average(guess, x / guess)
        }

        fun sqrtIter(guess: Float, x: Float): Float {
            if (goodEnough(guess, x)) {
                return guess
            } else {
                return sqrtIter(improve(guess, x), x)
            }
        }
        return sqrtIter(1.0f, x)
    }

上面这种嵌套的定义可以被称为块结构。广泛地使用这种结构，可以帮助我们将大问题拆解成一个个小问题，将复杂程序拆解成一个个一眼看上去明显不会出bug的小函数。

比如这里的辅助简单函数，100%不会出问题，所以我们在排查问题的时候，瞄一眼就知道以后基本不用看这部分代码了，关注更高抽象层级的函数就行了。

我们继续思考，还有没有其它方法求平方根？

我们先来了解一种找函数不动点的过程，对于x，如果满足则x为函数f的不动点。

在寻找函数不动点的代码中，我们不需要知道函数f是什么，所以f需要以参数的形式存在。

    fun fixedPoint(f: (Float) -> Float, firstGuess: Float): Float {
        fun closeEnough(a: Float, b: Float): Boolean {
            return Math.abs(a - b) < 0.00001
        }

        fun find(guess: Float): Float {
            val next = f(guess)
            if (closeEnough(next, guess)) {
                return next
            } else {
                return find(next)
            }
        }
        return find(firstGuess)
    }

这里也是通过猜测一个初始值然后逐步逼近的方法，直到传入的参数和返回值相等为止。

那么，我们可以认为求一个数a的平方根，可以看做是求函数的不动点

    fun sqrt(a: Float): Float {
        fun f(x: Float) = 1f/2 * (x + a/x)
        return fixedPoint(::f,1.0f)
    }

看到这里大家可能会觉得奇怪，如果要求a的平方根，根据函数应该是
是的没错，问题是这个函数无法收敛，所以我们需要对其进行改造，通过平均阻尼的方法使其收敛，这个方法就是用参数与结果的平均数作为下一次计算的参数。这个过程我们用代码描述的时候，需要将函数作为返回值

fun averageDamp(f: (Float) -> Float) = { x: Float -> average(x, f(x)) }

现在我们得到了一个通用的，可以一般化的求根的函数：

    fun sqrt(a: Float): Float {
        return fixedPoint(averageDamp { x -> a / x }, 1.0f)
    }

既然我们说它是一个通用的求根函数，那我们再来试一试，如果这时候我们需要计算立方根，应该怎么处理？

    fun cubeRoot(a: Float): Float {
        return fixedPoint(averageDamp { x -> a / (x * x) }, 1.0f)
    }

大家可以看到，很简单，就只用改动传入函数f的表现形式就行了。即求函数的不动点

上述我们的函数，

• 可以用变量命名
• 可以作为函数参数
• 可以作为函数返回值

这类函数叫做高阶函数，它和普通函数相比，进一步提升了抽象层级。

这里还有个抽象概念值得说一下，我们再回过头来看第一步写的代码，第一步的代码更像是在操作内存和CPU，这种方式一般称为命令式编程；而我们后面高阶函数的实现，更像是在描述一个逻辑思路，类似于伪代码，这种方式一般称为声明式编程。这两种编程方式，在直观的感受上来说，抽象层级也是不一样的。声明式的抽象层级明显是高于命令式的。

2. 构造数据抽象

在前面一部分，我们使用的都是基础数据，为了提升我们在设计程序时所位于的抽象层级，提高设计的模块性，增强语言的表达能力，我们还需要使用复合数据。

我们来思考设计一个系统，来实现复数的运算。
形如的数就是一个复数，其中𝑥和𝑦是任意的实数，分别称为复数𝑧的实部和虚部。

    lateinit var makeFromRealImag: ((Number, Number) -> Any)
    lateinit var realPart: ((Any) -> Number)
    lateinit var imagPart: ((Any) -> Number)

    fun addComplex(c1: Any, c2: Any): Any {
        return makeFromRealImag(realPart(c1) + realPart(c2), imagPart(c1) + imagPart(c2))
    }

    fun subComplex(c1: Any, c2: Any): Any {
        return makeFromRealImag(realPart(c1) - realPart(c2), imagPart(c1) - imagPart(c2))
    }

因为篇幅有限，这里只展示加减运算，以及描述复数的3个函数，分别是构造函数，取实部函数和取虚部函数。这时我们还不知道复数底层数据结构的具体表示，但我们已经可以描述复数的运算操作了。

将程序中数据对象的实现和使用分离的方法，叫做数据抽象。

数据抽象的基本思想就是为每一类数据对象写出一组操作，我们对数据对象的使用都可以基于这些操作，而不用关心它底层具体实现的数据结构。

这里我们可以分析一下数据的抽象层级

complex-cengji.png

• 使用者使用层，运算
• 数据表示层，构造和操作
• 数据的实现层，具体数据结构

这种分层思想使程序更容易维护和修改，每一层的修改几乎都不会影响其它部分。

继续我们的思考，前面我们实现了复数的直角坐标形式（实部和虚部），如果现在需要添加复数的另一个形式，极坐标形式（模和幅角），定义是
r为模，θ是幅角

这时情况变得更加复杂，因为前面对复数的操作，都只默认了一种类型，现在每个函数都需要做修改，来适应新的变更。因为直角坐标形式和极坐标形式需要进行相互转换，才能满足所有的操作。

为了解决这个问题，我们很自然想到的方法是为数据增加类型，函数体里也需要根据类型进行区分执行。即对复数对象增加类型标记操作，每次使用之前从读取类型函数读取该复数的类型，判断该复数是直角坐标形式还是极坐标形式，再进行计算。
比如获取复数实部的函数，根据类型区分开，就会有两种

    lateinit var attachTag: (Any) -> Unit
    lateinit var typeTag: (Any) -> Any
    lateinit var realPartRectangular: ((Any) -> Number)
    lateinit var realPartPolar: ((Any) -> Number)

    fun realPart(complex: Any): Number {
        return if (typeTag(complex) == "rectangular") {
            realPartRectangular(complex)
        } else {
            realPartPolar(complex)
        }
    }

这种方法对于只有两种表示形式的复数系统来说是够用的，但这个方法的缺点也很明显，在我增加了极坐标形式之后，为了不出现同名函数，则系统原有的函数名需要作修改。更麻烦的是，如果我想再增加第三种类型的时候，我们需要修改每一个类型判断的地方，增加一个分支。

很明显，这个方法的可扩展性不好。对于大型复杂的系统，在没有一个程序员能全面了解所有细节的情况下，去做大量的修改，成本非常高，风险非常大。

我们需要继续思考，有没有更好的方案。

我们把数据类型和操作做成一个表格：

	极坐标	直角坐标
实部	realPartPolar	realPartRectangular
虚部	imagPartPolar	imagPartRectangular
模	magnitudePolar	magnitudeRectangular
幅角	anglePolar	angleRectangular

只要我们实现这个表格的查询过程，根据操作和类型去查找对应的函数，就可以对任意复数进行操作。如果未来要新加类型或者新加操作，只需要增加这个表的内容就行了。

这个表只要实现根据类型添加函数和根据类型获取函数这两个操作就可以了。
写表和查表的过程我们也可以抽象出来，只要实现get和put方法就行了。
这里我们同样不需要关心数据表的底层实现。

put <op><type><item>
get <op><type>

    fun installRectangularPackage() {
        fun realPart(complex: Pair<Number, Number>): Number {
            return complex.second
        }
        put("real-part","rectangular",::realPart)
    }

    fun realPart(complex: Any): Number {
        val f: ((Any) -> Number)? = get("real-part", typeTag(complex))
        return f?.invoke(complex) ?: throw java.lang.RuntimeException("no method for these types")
    }

我们通过安装的时候写表，使用的时候查表操作，实现了更彻底的隔离，如果我们只需要其中一种数据类型，仅安装这个数据类型的函数包就行了，可以减少内存的占用。如果要扩展多种类型，只需要新增一些安装包，独立地写表就行了，操作变得非常安全和简单。

image.png

这里我们不仅实现了纵向的分层设计，甚至是实现了横向的分层设计，这种设计下，代码的可插拔实现变得更简单。

3. 构造状态抽象

我们写程序的时候，一般会将物理世界的内容看作是许多聚集在一起的独立对象，每个对象都有着随时间变化的状态。比如你的银行卡余额就是随时间变化的。我们可以用几个状态变量表示出一个对象当下的状态。

在代码里，实现这种状态随时间变化，我们是通过对变量的赋值实现的。

引入赋值操作让我们的代码描述能力更强，但也带来了一些问题。

赋值的正确性是依赖时间顺序的。现实世界里的对象的状态并不是按顺序变化的，它们总是并发地活动。比如你的银行卡余额，并不是只有你能操作，其它人也能给你转账。

赋值在并发情况下会变得复杂和不可靠。我们采用的方案是串行化，通过串行化工具来实现对共享变量的保护。

一般就是使用互斥量来保证对共享变量的串行访问，比如Java中sychronized关键字和基于AbstractQueuedSynchronizer的一些实现都能实现串行化，除了语言层面，操作系统和硬件同样需要支持对共享变量的串行访问操作。我们使用这些串行化工具，可以实现对共享变量的串行访问。

串行化提供了一种非常好的抽象，让我们能控制并发程序的复杂性。对于单个共享变量，这些工具是完全足够的。

我们需要继续思考，多个共享变量存在的情况。这个情况下，使用串行化工具，会带来一个更加复杂的问题，死锁。

比如我随便写个示例代码，在两个任务分别获取两个共享变量的时候，在竞争互斥量的时候，就容易发生死锁。

fun parallelExecute() = runBlocking {
    val m1 = Mutex()
    val m2 = Mutex()
    launch {
        m1.withLock {
            println("lock m1")
            delay(1000)
            m2.withLock {
                println("lock m2")
            }
        }
    }
    launch {
        m2.withLock {
            println("lock m2")
            delay(1000)
            m1.withLock {
                println("lock m1")
            }
        }
    }
}

对于死锁问题，至今没有什么特别好的、一劳永逸的方案，只能依赖程序员的仔细检查。像上述代码这种非常明显的死锁基本上不会出现。

实际环境更加复杂，在拿到第一个互斥量之后，中间还有无数个调用栈，你不知道执行到什么时候才会遇到第二个串行场景。试图在出现问题之前排查出来，非常困难。

我们需要继续思考，有没有什么其它的抽象工具，能减少串行化的使用，从而减少死锁的发生。

我们重新回到只有一个共享变量的场景。

这个共享变量会随着程序运行的过程中，被赋值改变。如果我们能把针对这个共享变量所有读写活动都抽象到一起，通过某种方式组织起来，按时间顺序分发状态去执行，就可以不使用锁工具。

这里我们需要引入一个新的数据结构，流。

fun <T> stream(consumer: (T) -> Unit, producer: (((T) -> Unit)) -> Unit): Cons<(T) -> Unit, (((T) -> Unit)) -> Unit> {
    return Cons(consumer, producer)
}

fun <T> streamConsume(stream: Cons<(T) -> Unit, (((T) -> Unit)) -> Unit>) {
    streamProduce(stream)
}

fun <T> streamProduce(stream: Cons<(T) -> Unit, (((T) -> Unit)) -> Unit>) {
    stream.second.invoke(stream.first)
}

fun main() {
    val s = stream<Int>(consumer = {
        println(it)
    }, producer = {
        it(1)
    })
    streamConsume(s)
}

上面我们用3个函数实现了一个流结构。在这里我们还需要实现延时求值的逻辑，在消费者使用之前，生产者不会产生数据。
这样我们就可以用一个无穷长的序列去模拟状态随时间变化的场景，不需要赋值改变状态值。

fun integers() {
    val s = stream<Int>(consumer = { println(it) }, producer = {
        for (i in 1..100) {
            it(i)
        }
    })

    fun <T> filter(stream: Cons<(T) -> Unit, ((T) -> Unit) -> Unit>, predicate: (T) -> Boolean) {
        val temp = stream.first
        stream.first = {
            if (predicate(it)) {
                temp(it)
            }
        }
    }

    fun <T> map(stream: Cons<(T) -> Unit, ((T) -> Unit) -> Unit>, f: (T) -> T) {
        val temp = stream.first
        stream.first = {
            temp(f(it))
        }
    }
    filter(s) {
        it > 50
    }
    map(s) {
        it * 2
    }
    streamConsume(s)
}

当我们需要对状态数据进行读取和操作的时候，可以实现一系列操作函数，对一个个状态数据进行处理。

在某些场景，流结构很好地避免了串行化的使用，但是流结构也有很大的缺陷，并不是每个场景都适用。比如某些情况，需要多个流进行归并操作，这就是多个共享变量存在的情况，依然会有死锁问题。

这样看来，我们无法找到一个一劳永逸的方案，只能是面对不同的场景选择一个最优的方案，去尽量避免复杂问题的产生。

4.构造解释抽象

前面3部分，我们主要讨论了一个问题，如何将复杂的问题简单化。为了解决这个问题，我们想了很多方案，模块化，高阶函数，分层设计，串行化和流。这些方案为解决业务上的复杂，提供了很好的思路。
为了让我们的语言需要支持上述方案，我们需要实现这些语言特性。我们写的代码本质上就是一些字符串，让它运行起来还需要解释或者编译，而实现这些语言也是一个很复杂的东西。
我们需要思考一下，怎么去减少解释语言的复杂程度？