计算机科学与函数式编程(FP)

(Updated: )
pl
函数, 程序语言, 计算机科学

老王今年公开了一个计算机科学入门小手册, 其他且不说, 认真看看然后看看能领悟到什么还是挺好的, 那就直接进入正题了, 文中如果没有特殊说明, 基本的内容核心是引自书里 (大部分省略了—>XX 说 “xxx”)

0x00. 前言

这是一个计算机科学的入门介绍书的第一章 (试读), 并且取名为 “从地而起” 不需要其他基础的书籍, 总 8 章, 公开的第一章是最多和最基础的内容, 里面的内容大部分是 iPad 绘画, 比较潦草(勿介意) , 大家如果阅读的时候, 要注意看一下 PDF 封面的最新日期[目前最新日期 2021.5.11], 老王说会定期更新:)

这本书是为想深刻理 Computer Science (计算机科学) 但是无从下手的同学准备的, 大部分的书要么前置要求过高 / 晦涩, 要么过于浅薄, 简而言之, 老王这本书试图把握到一个平衡点, 既通俗又深刻, 来看看

PS: 由于版权等要求, 基本不会直接引用原文, 但是会做一点笔记和提炼记录, 学习一下

0x01. 表达式

大概要求有一点基本的常识:

  • 小学加减乘除数学知识
  • 基本の逻辑

上来讨论了一个 expression (表达式)的概念, 比如 a + b * c 是一个算术表达式, 它最后的值 x 是一个 value, 这里应该是为了凸显值传递类的概念, 然后计算表达式的过程, 称之为 evaluation (赋值), 也就是 a + b * c = x 这里 = 代表的含义

然后把表达式分拆, 其实就类似语法解析里的 AST(抽象语法树)的构成, 拆为 a ,b, c 和 + , * 5个字符, 然后 b * c 的过程是

graph TD

a(b)-->b(*)
a2(c)-->b(*)-->x?

然后这里举了一个生活中的榨果汁的例子, b * c就像把 b (胡萝卜) 和 c (苹果) 两种水果放到了榨汁机(*)里, 榨汁的过程就是赋值(evaluation), 它最后输出的果汁就是value. 是一个挺形象的类比. 然后基于上, 可以画一个 a + b * c 的简图:

graph TD

b(b)-->c(*)
b2(c)-->c(*)--bc-->x(?)

a-->a1(+)-->x

这里 b * c 的结果 bc 是加法运算的输入(input), 然后再和a进行加法运算, 得到的结果 x 也就可称之为输出 (output), 然后基于此再想一下计算的优先级, 画一个 (a + b) * c 的图示:

graph TD

b(a)-->c(+)
b2(b)-->c--input-->x(?)

a(c)-->a1(*)-->x

从原始的表达式到语法树的抽象, 没有括号 () 的体现, 这里思考一下原因, 是因为图里的计算流程其实已经被图的拓扑结构定义了顺序, 所以即使没有括号在其中, 我们也能区分出计算流程, 任何一个表达式也都可以转化为这样的图流, 老王说这就是表达式的本质, 之后再悟一下.

0x02. 变量与函数(调用)

这里老王把 a * b 或者 a + b * c 称为最简单的计算机程序之一 (program), 然后提出 PL 中三大核心要素: 变量 + 函数 + 函数调用. 依次展开 (用浏览器内置 console)

1. Variable

首先在 console 里输入一个x的变量定义表达式

1
2
3
// console input & press enter
var x = 1 + 2;
// 'undefined' but not '3'?

为何回车会输出 undefined? 因为它表示的是整行语句的值, 也就是说把 var x = 1 + 2 整体看做一个表达式, 称之为 variable definition (定义变量), 那这里 undefined 的具体含义老王解释为 “已经完成了定义变量的操作”, 进一步推广单条输入语句都可以视为是一个表达式, 1 + 2 是, var a = 1 + 2 也是. 那么进一步想一下 3 是一个表达式么?

答案也是 Yes, 输入一个3 和 console 返回一个3 ,前者输入是一个表达式, 后者输出是一个值, 这里以前好像还真没细想过..

2. Function

接着继续试试, 那从上一节已经能知道, 定义一个函数也是一个表达式 x => x + x 返回什么呢? 是 undefined 么?

1
2
3
// input "x", return the value of "x + x"
x => x + x
// params --> body

不, 它返回的是同样的输入, 也就是说函数表达式的值是它自己本身. 这里把上面的函数定义抽象简化为两个部分, prams + body, 中间的 => 只是一个语法(syntax [‘sɪn.tæks]), 为了区分左右的不同语义. 它也可以是 -> 也看也是: 并不重要.

那定义了一个函数后如何使用它呢 –> 给一个输入

1
2
3
// why need '()', try without it
(x => x + x) (2)
// 4

如果不加 () 会有语义上的歧义, 那么整个 (x => x + x) (2) 就是下面的函数调用 (或简称 call)

3. Function Call

函数调用分为两个部分组成: 一边是 operator (运算符), 一边是 operand (运算数). 在上面的例子中, x => x + x 就是运算符, 后面的 2 是运算数. 类比函数的组成也是两个部分 (param + function body)

上面定义的函数我们在使用时发现并不方便, 因为没有给它命名, 所以如果要反复使用则需反复搬运完整的函数定义.

1
2
3
4
5
6
7
8
9
10
11
// how to name function
var f = x => x + 1;
> undefined

// use it?
f(3)
> 4

// function name's value?
f
> x => x + 1

然后我们尝试上面的几个表达式以及它的返回值, 尤其是最后一个, 当我们输入变量 f (同样是函数名), 它返回的值是和 1 + 2 代表的值有一样的语义, 所以对变量来说, 赋值函数表达式还是赋值普通算术表达式, 没啥本质区别.

那么 f(3) 的计算过程是什么样的呢, 其实也就很清晰了, 括号这里只是为了区分语义, 因为写 f3 可能视为一个单独的变量, 那么解析 f(3)的过程就是:

  1. 读取 f, 然后返回值 x => x + 1
  2. 然后带入 3, 变为 3 + 1 返回值 4

那紧接着如果输入 x, 会返回什么值呢? 如果之前没有额外定义过 x, 那么它会返回报错, 提示未定义(不是 undefined), 如果你之前定义过, 那么它返回之前的值, 和函数计算没有关系, 这也就是变量在函数中的生命周期体现.

0x03. 再探函数

1. Substitution

这是啥意思呢, 简单理解是 replace 替换, 代入的意思, 就比如上面 x => x + 1 的函数中, 传入 3 替换原有的 x , 也就是

1
(x = x + 1) (3)  --带入3--> 3 + 1  // 注意不是 x = 3 + 1

函数调用的值是函数体带入后的返回值, 如果是 x = 3 + 1 那么它就是另一个函数了, 所以函数体 (body) 决定了函数调用的返回值, 同样, 函数的 param 可以是多个, 就像数学中函数定义一样 F(x, y), 那么我们自然可以写出 (x, y) => x + y, 然后给它赋值给一个变量(命名), 并像 f(1, 2) 这样调用它.

PS: 老王说这里引入 substitution 这个带入的概念, 是为了帮助更简单的理解函数调用, 实际计算机为了优化性能会有更聪明的计算方式.

2. More function operation

既然上面反复说了函数是一个值, 就像一个数字 1 一样, 那么它也就可以当做一个值被传递和接收, 可以作为输入也可以作为输出

2.1 function as output
1
2
3
4
5
6
7
8
// what's mean? 
b => (a => a + b)

var f = b => (a => a + b)
// the value is?
f(1)
// then this?
f(1, 2)

那么就进入一个复杂一点的表达式了, 这里定义了一个嵌套的函数, 如何理解分解? f(1) 的返回值又是什么. 还是运用之前上文提到的两部分分解, => 左右分隔, 左边是 param, 右边是 body:

  1. b 是 param, a => a + b 整体是 body
  2. a 是 param, a + b 是 body

那从第一条可以看出, 函数本身也可以作为一个返回值来传递, 那么传入 1, 我们得到 a => a + b 这个返回值, 还是 a => a + 1 这样的返回值呢? 我以为是后者, 发现是前者, 嗯? 老王解释说是 console 隐式的把 1 转换为 b 了, why?

1
2
3
4
5
(a => a - 1) (3)
// 2

(b => (a => a - b)) (3) (1)
// 2

通过上面的验证, 我们发现, 当我们在嵌套的函数表达式传入两个变量时候, 实际还是两步:

  1. 1 => (a => a - 1)
  2. 3 => 3 - 1

这里有个疑问是为啥传入 3 和 1就会自动绑定到 a 和 b 上, 而不是 b 和 a 上呢, 依据从内到外的 param 顺序来绑定的么?

然后这里有点绕, 要注意变量生命周期和上下文, 最后说这种函数返回一个函数的做法就叫高阶函数 (high-order func), 然后给出这种函数命名和使用也是一样的 var f = (a => (b = b - a)) , 那么既然第一层参数返回的是一个函数, 那么我们就不能用 f(3, 1) 这样的做法去传入了, 我们需要构造一个 f(3) 作为整体传入

  1. var g = f(3) , 这里 f(3) 等价于 (b = b - a) (3)
  2. g(1) 等价于 (a => (b = b - a)) (3) (1) [其中 a = 1, b = 3]

函数可以返回函数当做输出, 上面就是一个代表性的例子, 那么同理, 作为一个值的函数, 自然也可以被当做另一个函数的输入

2.2 function as input

看看函数作为输入的用法, 上来给了一个没看懂的例子 var ap = (f, x) => f(x), 首先拆开:

  1. => 左边的 f 和 x 是 params, 理解为两个入参, 其中 f 是之前的函数定义 var f = xxfunc
  2. => 右边的 f(x) 是 body, 可是这里 f() 也是一个函数, 互相套娃是啥意思呢?
1
2
3
4
5
6
7
8
9
10
11
12
var f = x => (y = x + y)
// f represents ?
var ap = (f, x) => f(x)
ap(3, 1) // output: f is not a function, why?

// what param for input, try a func?
ap(x => x * 2, 5)
//10

// define a var
var ff = x => x * 2
ap(ff, 5) // equals to previous

明白上面的意思了么? 这就是说, 定义的函数 ap 有两个入参, 一个需要传入函数, 另一个传入普通数值, 如果我们已经定义了另一个函数 var ff = x => x * 2 , 那传递 ff 就等同于在传递函数了. 函数作为输入其实比作为输出好理解一些.

2.3 function as both

上面说了函数可单独作为输出和输入, 那么函数是否可以同时作为它们二者呢? 答案也是肯定的. 下面定义一个两个入参都是函数, body 也是函数的例子如下:

1
2
3
4
5
6
7
8
9
10
// define a complex var
var com = (f, u) => (x => f(u(x)))

// 1. split first
params: f, u
body: "x => f(u(x))"

// 2. split second
params: x
body: "f(u(x))"

容易想到, f 和 u 是两个单独的函数, 比如 a + 1 (f1) 和 b * 10(f2) ,但是如果仅仅传入 com(f1, f2), 我们只能得到第一层的body返回, 而没有传入到第二层的x参数, 那该怎么传入呢? 把它当一个整体, 试试函数体外外传入?

1
2
3
4
// already define f1 & f2 as above
com(f1, f2) (5) // error: u is not a func, why?

com(a=a+1, b=b*10) (5) // right?

这里再举回榨汁机和 computation graph 的概念, 把两个函数入参当做两个机器, 一个是削皮器, 一个是榨汁器, 输入一个苹果, 它需要先通过削皮机, 然后把处理后的输出作为输入传入榨汁机, 最后生成了一杯果汁. 可以得到如下的转换:

com(f1, f2) (5) <–> 加工(削皮器, 榨汁器) (苹果) , 这样也就是通过连接/封装两个已有的函数, 产生了一个新的函数, 这样理解, 后续就算再有更多的函数, 也很好拆分理解了.

3. Others

这里谈及函数中的参数名, 以及 body 中使用它们的本质, 如何定义两个函数是否相同/相等: 如果给两个函数相同的输入, 它们有相同的输出, 则认为它们两相等, 与参数名无关, 那么同理, 定义函数的方式在不同语言里也可以是语法(syntax)上各不一样的

1
2
3
4
5
6
7
8
9
10
11
// way1
function f(x) { return x*x;}

// way2
var f = x => x*x;

// way2.1
var f = function(x) { return x;}

// way3
var f = new Func(x, y, 'return x + y')

至此, 基本整个第一章试读的内容也就结束了, 觉得意犹未尽的话, 不妨再跟着看看其他的函数式编程入门文章? 看看是否有了更好的理解.

0x04. 再探 FP

篇幅原因, 本章后续拆分为单独的笔记, 单独记载其他相关的 FP 介绍和理解.

1. Wiki 百科

先看看历史, wiki 中介绍1930年邱奇提出的 λ演算 (数学抽象) 是 FP 的基础和核心, 然后紧接着第二段话就能与上面学习的内容呼应起来了:

In FP, functions are treated as first-class citizens, meaning that they can be:

  • bound to names (including local identifiers/param)

  • passed as arguments, and returned from other functions ( just as any other data type can)

    This allows programs to be written in a declarative and composable style, where small functions are combined in a modular manner.

最后总结说 FP 让函数就像上面举例的流水线处理果汁一样处理程序的风格, 算是一个官方总结吧. (后面其他太多就不列举了), 里面提到 FP 主要是在学术界使用, 工业界以前鲜有重视 (部分支持), 说是因为觉得存在低效利用 CPU/内存的原因, 不妨带着这个性能疑问后续学习

2. RYF

再来看看阮一峰2012年写的 FP 介绍 (RYF 的博文算是尽可能符合深入浅出, 简洁的代表), 他那时候预测 FP 会成为下一个主流(OOP 后)编程范式, 研发多少都需要懂一些.

简单说, FP 是一种编写程序的方法论, 属于“结构化编程”的一, 主要思想是把运算过程尽量写成一系列嵌套的函数调用

马上举了个例子, 先看下面的表达式, 然后不看提示, 学完上面讲的内容, 自己写一下 js 下的函数定义

1
2
3
4
5
6
7
8
9
10
11
12
// give a math expression
(1 + 2) * 3 - 4

// traditional way
var a = 1 + 2;
var b = a * 3;
var c = b - 4;

// fp?
var compose = (f, u, g) => (a, b, c, d => g(u(f(a, b), c), d))
// wrong, correct to?
compose(a, b => a + b, c, d => c * d, e, f => e - f) (1) (2) (3) (4)
a. 特点

这里接着说了5个典型特点: 一等公民, 表达式, 无副作用, 状态不变, 透明引用. 再来看看有哪些可以理解了?

Func is first class: 这个在上面最早就说了, 把函数当一个普通值类型来看待和传递, 自然可作为输入/输出

Use expression (not phrase): 这里就提到了, 表达式就一定有返回值 (没有 void?), 语句是可以没有的, FP 就算计算公式一样

No Site Effect: 就是说给一个函数, 它内部运算是不可受到/修改外部变量的, 保证变量的生命周期控制在 func 的范畴

Immutable State: 这里由上衍生, 函数仅计算, 不改变任何变量的值的前提下, 也不用变量存储状态, 状态只能用其他函数作为输入传递, 就类似上面的多步计算, 嵌套多个函数, 把 a 函数的输出作为 b 函数的输入, 如果是同一函数, 那就需要常使用递归的方式来传递状态变化.

Refe transparency: 这个引用透明是个最拗口的说法, 我觉得跟上面3, 4 点的确比较雷同了, 意思还是说相同输入和函数一定有相同输出, 不应受类似全局变量这种影响, 没有函数外的状态. 所以不用和它纠结.

b. 意义

  1. 简洁, 开发快: 首先引用了<<黑客与画家>> 里说的 Lisp 开发速度比 C 语言快 X 倍的举例, 我觉得不是很有说服力, 但是函数式编程的确简洁不少, 并且对多次的计算和 pipeline 式的操作的确明显思路更清晰也无需重复定义中间输出.

  2. 更接近自然语言: 这里不深究什么叫自然语言, 就举了两个例子, 简单说就是更接近人的 parse 思维 (logic), 短期可读性的确更好, 但是语句长了也不好说 (Gremlin 就是典型的代表):

    1
    2
    3
    4
    5
    6
    7
    // math expression: (1 + 2) * 3 - 4

    // fp can express like this
    add(1,2).multiply(3).subtract(4)

    // search a number after merge sort (fp way)≥
    merge([1,2],[3,4]).sort().search("3")

  3. 并发编程简单: 这个最主要来源于不可变对象/函数的原因, 也类似多个函数每个人相对独立所以不会受多线程互相影响, 只要一个线程只执行一个函数就避开了共享变量这个并发本质问题了, 函数外也没有上下文/有序性带来的影响. (以及衍生写单测和模块化组合也简单许多, 各司其职互不影响)

  4. 支持热升级: 这个倒是第一次听, 这里作者说只要函数只要能保证接口不变, 内部代码就不会影响整体, 用 Erlang 举例, 但是我觉得解释有点牵强, 留言区也表示了异议.

总得来说, RYF 这篇文章基于翻译的转述简单举了一点不一定严谨的例子来描述 FP, 可以作为一个参考选择阅读帮助理解.

3. Coolshell

在 coolshell 的文章开头, 就把 FP 的特点简化到了3个最主要的特性, 前两个已经见过多次不再说, 这里看看第三点:

  1. 函数一等公民
  2. 不可变特性
  3. 尾递归优化 (这里是之前没有提过的, 把它专门列到了一个特性?)

尾递归简单说就是每次递归会复用 stack, 而不是创造一个无尽长度的数组取放元素, 我一直没太搞清楚:) 这里说需要语言或编译器支持. 下面接着说了 FP 的几个技术点:

  1. Map & Reduce: 这里是说 FP 的最常用操作之一就是对集合做映射 + 归约/归并 的操作, 但是没有后文了..
  2. Pipeline: 这个就是之前反复提及的, 以及那个 “榨汁器 + 削皮器” 例子里提到的 FP 用法 (也类似 Unix 的管道设计?)
  3. Recursing: 复杂问题用很简单的代码描述, 作者备注说递归的精髓是 “描述问题”, 没太理解.
  4. Currying: 解释的很拗口, 说是把某个函数的多个 params 分解为多个函数? 可见简化函数的多个 param? 感觉像之前老王说的嵌套函数, f(g(x)) 这样的概念 (==不理解==)
  5. High order func: 之前 sample 里提到的传入函数, 生成函数的函数,

接着说了 FP 的几个优点:

  1. Lazy evaluation: 直译是惰性求值, 非人话.. 这个应该就是在 sample 那里老王提到的, x => x + y, 给 x 一个赋值后, 不会立刻绑定计算, 而是被保留直到真正需要用的时候, 说需要编译器支持 (优点是提升性能? 类似前端的懒加载么…)
  2. 恒等性和并行: 这些前面已经提过, 不重复.

紧接着, 下面引入了一些对比 FP 和普通编程范式的例子:

给一个变量 count 进行自增 + 1:

1
2
3
4
5
6
7
8
9
10
11
12
int count = 0;
void increase(){
    count = count + 1;
}

// 对比之前说的例如 js 中的 FP 定义
var increase = x => x + 1;

// 嵌套函数的例子 (同前), 这就是科里化么?
var f = x => (y => x + y);
var g = f(1);
g(2); // 输出 1 + 2 = 3

这里最典型的区别在于, FP 不允许函数内有全局/外部变量进行修改, 它一定是有一个确定的输入输出, 相对独立.

下面开始具体举 FP 在不同语言中的使用特点了, 例如 mr / pipeline 模式:

1
2
3
# py 里自带有不少 fp 的设计, 也比较简洁
# 这里 ':' 也只是替代之前 js 的 '=>', 只是符号不同罢了.
sqr = map(lambda x: x*x, range(5))

未完待续

0x05. 小结

以上就是计算机科学的第一章的内容, 个人感觉基本上是 PL 的范畴, 尤其是语法的解析和探索函数的本质, 有几个收获:

  • 发现自己之前很多很基本的 PL 概念没有仔细思考过, 关于 var a = 1; 这个整体是啥, 和语句有啥区别. 缺乏理解
  • 更好, 更本质的对 PL 和函数的抽象, 这样分析复杂的嵌套或者语法, 有了一个很简洁的方式
  • 发现函数/FP 以前想复杂了, 有两个原因:
    1. 语法太多变, 上手不明所以, 似懂非懂, 这次从最原始的版本来推敲, 好很多
    2. 很多概念名词 (λ演算/Lisp/尾递归/不可变/第一公民/mr/科里化/高阶函数/惰性求值/幂等)…. 上来就说的很拗口复杂

总之, 这次体验还是觉得挺有价值, 希望能多有一些类似的 CS 本质/原理探索和设计文章/课程, 从最简开始去探索计算机的奥秘, Thanks again.

参考资料:

  1. Group-Up Compute Science (Sample)
  2. 函数式编程 - Wikipedia
  3. 函数式编程初探 - RuanYiFeng
  4. 函数式编程 - Coolshell
  5. 函数式范式 - Gitbook
  6. Why Functional programming - Translate by Byvoid
  7. Why lisp is superior – Translate by RYF
  8. Functional Programming For The Rest of Us - 2006