阿袁工作的第1天: 函数式编程的历史

阿袁中午和阿静一起吃午餐。阿袁说起他最近看的《艾伦·图灵传如谜的解谜者》。
由于阿袁最近在学习Scala，所以关注了一下图灵传中关于函数式编程的一些历史。
关于函数式编程的故事，可以从1928年开始讲起：希尔伯特在当年的一个大会上，提出了他的问题：

第一，数学是完备的吗？
是不是每个命题都能证明或证伪。
第二，数学是相容的吗？
永远不会推出矛盾的命题？
第三，可判定性问题：数学是可判定的吗？
是否存在一个算法，可以应用于任何命题，然后自动给出该命题的真假？

希尔伯特的哲学企图是：每个问题的答案都将会是“是”。我想这个信念来自于对数学的神圣信仰。

不幸的是，在这同一个大会上，第一个问题就被否定了。一个年轻的捷克数学家，柯特·哥德尔的宣布，能够证明，
算术一定是不完备的：存在既不能证明，也不能证伪的命题。

注：欧几里得几何的五大公理并不是一个反例。欧几里得几何可以被一阶公理化为一个完备的系统。
（这句话啥意思？）我的理解是：公理是一个定义，或者说是不证自明的。

随后，哥德尔不完备定理的第二定理又否定了第二个命题：“数学是相容的吗？”

对于第三问题(可判定性问题)，在1936年，丘奇（Alonzo Church）和艾伦·图灵分别证明了存在不可解的问题。
图灵提出的图灵机模型，而丘奇提出了一个基于lambda演算(lambda calculus)的模型，这两个模型被图灵证明是等价的。
图灵在图灵机的思想上，继续思考，逐步设计出早期的计算机（一个英国版的计算机，比冯诺依曼的计算机更早被建造出来。冯诺依曼对图灵机也是认可的。），并且考虑人工智能的问题。
而lambda演算概念，则被发扬光大成了函数式编程思想。
伟大的数学！

函数式编程是基于表达式(expression)的一种编程范式。
函数式编程将计算视为对数学函数的求值过程。

函数式编程是：
- 声明式编程(declarative programming)，其含义是基于表达式(expression)。
- 基于表达式的含义：表达式是用来求值的。
- 倾向避免使用可变数据。
面向对象编程的特点：
- 命令式编程(imperative programming)，其含义是基于陈述(statement)。
- 基于陈述的含义：语句是用来执行的。

阿袁工作的第2天: 函数式编程：告别对象，迎接函数

阿袁和阿静中午又在一起，继续讨论函数式编程。
“我认为，我们可以把函数式编程理解成在做数学计算。这种编程风格是一种面向表达式(expression-oriented)风格。”，阿静慢慢地说道。
"我也是这么想的。所以，作为一个面向对象的程序员，我们先要把对象的概念舍去掉。"
“是啊，倒空一些，才能学习到新的知识。”
“我们怎么考虑class的作用呢？”
“在面向对象中，class的一个主要作用的封装。”
“那么，在函数式编程中，class的作用应该是对算法（函数）的分类了。”
“正解！我们做一个游戏，看看如果把一个面向对象的程序，变成面向表达式的程序。”
“好啊，我先用Scala写一个面向对象的例子。”

// 这个例子的主要功能是对一个List排序。
// 这是一个基于面向对象思想的实现。
object Main {

    // 一个支持排序的class。
    // 这个class，需要外部提供一个比较器。
    class ListSorter[T](a: List[T]) {
        def data: List[T] = a
        def sort(comparer: IComparer[T]): List[T] = {
            return data.sortWith(comparer.compare)
        }
    }

    // 我们为比较器定义一个interface，带一个比较函数compare。
    trait IComparer[T]{
        def compare(a: T, b: T): Boolean
    }

    // 这个一个具体的比较器，实现了比较器IComparer。
    class IntComparer extends IComparer[Int] {
        override def compare(a: Int, b: Int): Boolean = {
            return a < b
        }
    }
    
    // 测试一下
    def main(args: Array[String]): Unit = {
        val list = List(9,1,6,3,5)
        val sorter = new ListSorter[Int](list)
        // 在调用sort方法时，传入一个具体比较器对象。
        println(sorter.sort(new IntComparer()))
    }
}

在这个例子中，ListSorter需要外部提供一个比较方法。为了解决这个问题，面向对象的思路是:

对外部功能，定义了一个接口。并在接口中，声明这个比较函数。

ListSorter的sort函数，通过接口来使用外部的比较方法。

外部：定义了一个具体类，实现了这个接口。

调用者：在调用ListSorter的sort函数时，传入一个具体类的对象。

“现在，我们的任务就是：把这个例子改成面向表达式的风格。”
“首先，把sort函数的输入参数comparer变成一个函数类型。”
“这样，我们就不需要IComparer，这个接口了。”
“IntComparer就可以从一个封装类，变成一个带比较函数的静态类。”

函数式编程的第一个例子：

// 这个例子的主要功能是对一个List排序。
// 这是一个基于面向表达式的实现。
object Main {
    // 一个支持排序的class。
    // 这个class，需要外部提供一个比较函数。
    class ListSorter[T](a: List[T]) {
        def data: List[T] = a
        def sort(f: (T, T) => Boolean): List[T] = {
            return data.sortWith(f)
        }
    }

    // 实现了一个比较函数。
    object IntComparer {
        def compare(a: Int, b: Int): Boolean = {
            return a < b
        }
    }

    def main(args: Array[String]): Unit = {
        val list = List(9,1,6,3,5)
        val sorter = new ListSorter[Int](list)

        // use function rather than object
        println(sorter.sort(IntComparer.compare))
        // use function with lambda expression
        println(sorter.sort( (a, b) => a < b ))
        // use function with underscore
        println(sorter.sort( _ < _ ))

        // fluent infix style
        println(sorter sort IntComparer.compare)
        // fluent infix style with lambda expression
        println(sorter sort {(a, b) => a < b})
        // fluent infix style with underscore
        println(sorter sort { _ < _ })
    }
}

注：这里面实现了多种风格。
lambda expression，可以看成匿名函数的实现方法。
underscore: underscore在scala中有多种含义。这里是一种匿名函数的实现，scala会根据上下文推测"_"的含义。
infix style: 可以看出，不需要"."了。

“太好了，我们向函数式编程迈出了第一步！”

阿袁工作的第3天: 函数式编程：再纯粹一些

“在昨天的例子中，我们还是实例化了ListSorter。”
“是啊，按照函数式编程的思想，我们需要把ListSorter的sort方法看成一个函数。”
“另外，我还学到了一点，在面向表达式风格中，不要写return。最后一条expression的结果就应该是函数的返回值。”
“嗯，好的，我们继续改改看。”
函数式编程的改进版：

// 这个例子的主要功能是对一个List排序。
// 这是一个基于面向表达式的实现。
// * Changed ListSorter as module
// * Do not use return
object Main {
    object ListSorter {
        def sort[T](a: List[T], f: (T, T) => Boolean): List[T] = {
            // Do not use return
            a.sortWith(f)
        }
    }

    object IntComparer {
        def compare(a: Int, b: Int): Boolean = {
            // Do not use return
            a < b
        }
    }

    def main(args: Array[String]): Unit = {
        val list = List(9,1,6,3,5)
        // use function rather than object
        println(ListSorter.sort(list, IntComparer.compare))
        // use function with lambda
        println(ListSorter.sort[Int](list, (a, b) => a < b))
        // use function with underscore
        println(ListSorter.sort[Int](list, _ < _))
    }
}

发现了吗？ fluent infix style没有了。这是因为，infix操作支持有一个参数的函数。

阿袁工作的第4天: 函数式编程：卷积（currying）

“fluent infix style有点接近人类的语言，使用好的话，可以增加可读性。”
"但是，它也有个限制，只支持有一个参数的函数。"
“其实，卷积可以解决这个问题。"
"卷积？"
“给你举个例子。一般的函数是这样的。”

    def normalFunc(a: Int, b: Int, c:Int): Int = {
        a + b + c
    }

"而卷积函数变成这样，参数被分隔一个一个的。"

    def curriedFunc(a: Int)(b: Int)(c:Int): Int = {
        a + b + c
    }

"卷积的思想是: 每次只给函数的一个参数赋值。这样的一个主要用途是：局部函数(partial function application)，
可以想象为把一个计算分成多个步骤计算（multiple stage computation）。这是调用的方法："

        // Usage: Currying in partial function application
        val add2OneByOne = curriedFunc(1) _
        // call a curried function variable with a normal arugment
        println(add2OneByOne(2)(3))
        // output: 6

“卷积带来的一个附加益处，就是支持了多参数函数的infix操作。”

        // Usage: call a curried function with an expression in fluent infix style
        println(curriedFunc {1} {2} {3})
        // output: 6

“scala真强大啊！我们继续改改看。”

// 这个例子的主要功能是对一个List排序。
// 这是一个基于面向表达式的实现。
// * Using currying
object Main {
    object ListSorter {
        // curried function (a)(b)
        def sort[T](a: List[T])(f: (T, T) => Boolean): List[T] = {
            a.sortWith(f)
        }
    }

    object IntComparer {
        def compare(a: Int, b: Int): Boolean = {
            a < b
        }
    }

    def main(args: Array[String]): Unit = {
        val list = List(9,1,6,3,5)
        // use function rather than object
        println(ListSorter.sort(list)(IntComparer.compare))
        // use function with lambda expression
        println(ListSorter.sort(list)((a, b) => a < b ))
        // use function with underscore
        println(ListSorter.sort(list)(_ < _ ))

        // fluent infix style
        println(ListSorter.sort {list} {IntComparer.compare})
        // fluent infix style with lambda expression
        println(ListSorter.sort {list} {(a, b) => a < b})
        // fluent infix style with underscore
        println(ListSorter.sort {list} { _ < _ })

        // currying usage: partial function application
        val sortWith = ListSorter.sort(list) _
        // fluent infix style
        println(sortWith(IntComparer.compare))
        // fluent infix style with lambda expression
        println(sortWith {(a, b) => a < b})
        // fluent infix style with underscore
        println(sortWith { _ < _ })
    }
}

阿袁工作的第5天: 函数式编程：如何处理null

"今天有个新的认识。在面向对象语言中，我们经常使用null。但是在数学计算中，null是没有意义的。"
“那么要使用什么呢？”
“如果返回值类型是一个集合，最好返回空集合。”
“如果返回值类型是一个值，scala提供了一个Option的泛型类，提供了一个None对象，表示返回的值是没有值。”
“代码示例如下。”

// 这个例子的主要功能是说明使用Nil和None、
object Main {
    object NilNoneSample {
        // 使用空集合。不要使用null。
        def getEmptyList(): Seq[Int] = {
            Nil
        }
        
        // 使用空集合。不要使用null。
        def getEmptyVector(): Vector[Int] = {
            Vector()
        }
        
        // 对于可能返回“没有值”的结果，使用Option泛型类。
        def getValueIfLargeThanZero(a: Int): Option[Int] = {
            if (a > 0) Option(a) else None
        }
    }

    def main(args: Array[String]): Unit = {
        // use empty collection replace null
        println(NilNoneSample.getEmptyList)
        // output: List()
        println(NilNoneSample.getEmptyVector)
        // output: Vector()

        // use None replace null
        println(NilNoneSample.getValueIfLargeThanZero(1).get)
        // output: 1
        println(NilNoneSample.getValueIfLargeThanZero(-1).isEmpty)
        // output: true
    }
}

阿袁的日记

2016年9月X日星期六
最近和阿静接触的机会多了很多。也学会了一些函数式编程的概念。
总结一下：
函数式编程的风格，即面向表达式编程风格，有如下要求：

把类看是算法的分类。
使用函数代替对象。
对于变量和参数，尽量使用：值（最好是不变的），Collection和函数等类型。
尽量使用不可变的数据类型。（重申一遍）
避免使用return语句。
对于集合类型，使用空集合来代替null。
对于其他数据类型，使用None代替null。
可以使用卷积来方便于多步骤计算的要求。

参照

Functional programming
哥德尔不完备定理
[英]安德鲁・霍奇斯. 艾伦·图灵传如谜的解谜者