我看到了它，却不敢相信它.—by康托尔

前言

这是一个我想写了很久的话题,但是却迟迟没有开始,因为这个话题过于艰深而且涉及的知识面已经超出了我的边际,然而在这几周重读了递归之后还是打算将其记录下来,记录下这令人神往着迷的美妙的数学世界的经历.

标题很自大地致敬了**哥德尔、艾舍尔、巴赫–集异璧之大成**这本刷新我认知的奇书

**康托尔、哥德尔、图灵——永恒的金色对角线**这篇我非常喜欢的关于不动点的博客.

从递归说起

递归,这个编程中基础到不能再基础的知识点,却在我开始学习SICP之后一次次刷新着我的编程观,大道化简,即便是这样一个在认知中基础得不能再基础的编程方式也以其独特的魅力向我们展示着编程和数学中隐藏着的深刻而绮丽的美丽之处.

汉诺塔

这是一个几乎每个学习编程的人都会学到的关于递归的最好的例子,在此就不再详述这个问题的介绍了,维基百科链接在这里.

给出移动的流程:

1
2
3
4

移动4个盘子=
    移动3个盘子到B
    移动最大的盘子到C
    移动3个盘子到C

下面给出python版本的解法:

1
2
3
4
5
6

def solve_toh(n_disks):
    if n_disks == 0:
        return
    solve_toh(n_disks-1)
    move_disk(n_disks-1)
    solve_toh(n_disks-1)

这个凝聚了大量的智力劳动的问题却以其极简的表达形式展示了出来而且是这么的容易被理解,这也是递归的魅力所在吧.

二进制

下面我们引入二进制,当然这也是非常基础的计算机知识了,但是这里我们需要关注的是它的计数规律:

1
2
3
4

数出二进制1111=
    数出二进制0111:     0111
    将首位置1,后三位恢复:1000
    数出二进制0111:     1111

可以看到的是,这个过程是非常递归的一个过程,1111需要先数0111而0111需要先数0011…..那么这和汉诺塔有什么关系呢?让我们这样来考虑问题:

我们将A柱子上的4个盘子记为一个4位二进制数,它的起始状态就是0000,然后我们开始计数:0001,0010,0011….而每次某个二进制位变成1的时候,就将对应的盘子向右移动一个柱子(到最左的话就移动到A),如:0001就是将编号为0的盘右移到B:

然后如此循环,我们就可以解决汉诺塔问题.当我看到这里的时候我是很惊异的,这难道只是一个巧合吗?我们来观察一下上面的2段代码:

1
2
3
4
5
6
7

solve_toh(n_disks-1)
move_disk(n_disks-1)
solve_toh(n_disks-1)

数出二进制0111:     0111
将首位置1,后三位恢复:1000
数出二进制0111:     1111

正好一一对应,不是吗?

也就是说,移动编号为1的盘子,需要移动0号盘子2^1-1=1下,而移动2号盘子需要移动0号和1号盘子总共2^2-1=3下,而3下中也是0号2下,1号1下,明显的是:二进制数字变化是递归的且和每个盘的变化是一一对应的.

还是递归

匿名递归

在SICP第一章中我们就了解到,我们可以将求根的函数和寻找一个函数的不动点结合起来,只要这个函数在迭代的过程中是收敛的,比如(其中的fixed-point就是寻找不动点的函数):

1
2
3
4
5

(define (f x)
    (/ 2(+ x (/ x 2))))

(define (sqrt x)
    (fixed-point f 1))

在维基百科的定义中,函数的不动点就是x=f(x)的点,但是这对于递归有什么意义呢?我们这样来思考问题:写一个lamdba表达式来实现递归求解阶乘.

阶乘

那么就先把函数给写出来:

1

lamdba n: n==0?1,self*(n-1)

这里的self就是这个函数的名称,在不使用匿名函数的时候,固然是很简单的,直接将函数名填进去就行了,但是lamdba就不行了,因为在函数被定义之前它是没有名字的.既然我们不能直接填入函数名,那么就将其参数化:

1

lamdba self,n: n==0?1,self*(n-1)

然后我们给他加一个名字:

1

let P = lamdba self,n: n==0?1,self*(n-1)

观察这个函数我们可以发现,如果调用P的时候,我们传一个真正的阶乘函数进去,那么P(power, 10)就可以正确的求解阶乘了.恩?但是我们不就是在找一个阶乘函数吗?虽然有这样的疑惑,但是还是先写一个出来再说嘛:

1

power(n) = n==0? 1,n*power(n-1)

然后我们靠柯里把这个函数变成这样:P(power),也就是说这个函数还等待接收一个数字就能求出对应的阶乘了.恩?等等,这个power也不行啊,这也是个不存在的函数啊!那么别急,先展开一下:

1

P(power) = n==0?1,power(n-1)

恩?这不就是power的定义吗,what?是的,P(power)=power了!,这是什么,这不就是函数的不动点吗!也就是说,对于伪递归函数P,存在一个点power使得P(power)=power,那么问题就变成了,我们要找到一个工具,只要对P用一下这个工具,我们就能获得power,power是什么?power可是一个真正的递归函数啊,那么这个问题就解决了.也就是说:找到一个函数Y,使得Y(P)=power:

1
2
3
4

Y(P)=power
因为:P(power)=power
所以:Y(P)=power=P(power)=P(Y(P))
也就是说:Y(P)=P(Y(P))

那么问题就变成了寻找这个Y,似乎问题到了这里也没有丝毫推进但是只要得到Y,那么这就是一个银弹可以对任何一个函数使用,就可以得到其真正的递归函数.让我们回到

1

let P = lamdba self,n: n==0?1,self*(n-1)

如果我们调用P(P,3)会得到:

1

3==0?1,P(3-1)

发现并不能继续循环调用下去,那么我们调整一下P函数:

1

let P = lamdba self,n: n==0?1,self*(self, n-1)

那么上面的调用就会变成:

1

3==0?1,P(P,3-1) ==> P(P,2)

诶?这不是就搞定了吗,那我们绕这么远的路还要寻找Y干嘛呢?我们将这个思想代入到Y中:

1
2
3

let Y = lambda F: 
    let f= lambda self: F(self(self))
    return f(f)

用P代入:

1
2
3
4
5
6
7
8
9

Y(P):
    let f = lamdba self: P(self(self))
    return f(f)
也就是:
Y(P)=f(f)
而f(f)根据定义可以得到:
f(f)=P(f(f))
也就是:
Y(P)=f(f)=P(f(f))

将其代回P函数中:

1
2
3

P(f(f)) = lambda: n==0?1,n*P(f(f))(n-1)
假设P(f(f))=fib,那么:
fib = lambda: n==0?1,n*fib(n-1)

终于得到了一个完美的阶乘函数!而这个Y不是别的,就是Y组合子.也就是说,只要使用Y组合子这个神奇的函数,我们就可以获得所有函数的递归形式.

我们赋予了函数式编程能够表达递归的能力

下面给出一个python的实现:

1
2

def y_combinator(f):
    return (lambda u: u(u))(lambda x: f(lambda *args: x(x)(*args)))

那么匿名的阶乘函数就如下:

1

y_combinator(lambda fab: lambda n: 1 if n < 2 else n * fab(n-1))(10)

在SICP的课程开始,老师说过:如果我们想要操纵一个精灵(函数)只要能够叫出它的名字就可以,而有了Y组合子的帮助,我们能够操纵一大类叫做匿名函数的精灵了.

Congratulations!你已经正式加入了Lisp邪教!这是会徽:

递归艺术

爱舍尔有一副很有名的画–画手,这也是一个将递归在绘画艺术中发挥到极致的画家了.

可以看到这也是一个很递归的过程,而在SICP的第四章中,eval和apply就像是图上的两只手,在互相描绘着对方.

print itself

我们可以让一个程序输出它本身吗?下面给出一个js的实现和一个python的实现:

1

(function (s) { console.log( '(' + s + ')(' + s + ')' )})(function (s) { console.log( '(' + s + ')(' + s + ')' )})

1

print(lambda x:x+`(x,)`)('print(lambda x:x+`(x,)`)',)

递归分形

在SICP第二章中,我们使用Lisp来实现过一个能够画出递归的图片的语言,效果如下:

还有一种分形的图形叫做谢尔宾斯基三角形

一种递归的实现方法是每次连接一个三角形的三条边的中点,然后对所有的三角形重复这个过程.伪代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def sierpinski(points,degree):
   drawTriangle(points)
    if degree > 0:
        sierpinski([points[0],
                        getMid(points[0],points[1]),
                        getMid(points[0],points[2])],
                   degree-1)
        sierpinski([points[1],
                        getMid(points[0],points[1]),
                        getMid(points[1],points[2])],
                   degree-1)
        sierpinski([points[2],
                        getMid(points[2],points[1]),
                        getMid(points[0],points[2])],
                   degree-1)

还是汉诺塔

(你说的是三角形,关我汉诺塔什么事?)

我们来改变一下移动汉诺塔的策略,每次移动的时候只能把圆盘移动到相邻的柱子上,改变了策略之后会发生什么呢?我们来假设移动一下4个盘子:

1
2
3
4
5
6
7

移动4个盘子=
    移动3个盘子到C
    移动最大的盘子到B
    移动3个盘子到A
    移动最大的盘子到C
    移动三个盘子到B
    移动三个盘子到C

如果这时候我们还要保持每一位数的变化和对应盘子的移动的话,可以看一下上面的流程:

1
2
3
4

移动4个盘子=
    移动3个盘子到B
    移动最大的盘子到C
    移动3个盘子到C

很自然的可以想到,因为每次都多移动了一下,那么使用三进制怎么样?right

这时候事情就变得有趣了起来,让我们想一下:4个盘子进行移动一共移动多少下?3^4=81次.4个盘子总共可以产生的不重复的盘子分布状态是几种?

3*3*3*3=81种,这是巧合吗?也就是说,上面按照三进制的走法就是最优解了(因为如果前后有重复的状态的话,中间的步骤就可以被省略了),事情变得非常有趣了起来.

我们把所有可能的盘子状态按照两个直接可以一步做到的方式连在一起,例如(0号盘可以相互一步到达):

这样把全部的盘面都连接在一起的话:

恩?这是什么?这不是谢尔宾斯基三角形嘛

虽然难以置信,但是事情就是这样发生了

是的,虽然大家平时完全不见面,但是通过递归使得分形和汉诺塔联系在了一起.

当你一旦发现了数学中的某些规律在你的知识的每个角落都散发着光芒的时候,这将你深深吸引的绚丽的光芒就将指引着你去寻找更多美丽的存在. —by沃·兹基硕德

那么最优解呢?最优解也是可以找到的

看到这里,相信没有人会不感叹数学之美以及这递归中的种种巧合与联系.

总结

总感觉意犹未尽但是又说不出来,写完也总是不能令自己满意,但是总也不写的话就会一直惦记着,就先把想到的写出来要是以后还有再继续补充罢.

关于Y组合子和停机问题以及哥德尔不完备定理的内容还是参见康托尔、哥德尔、图灵——永恒的金色对角线这篇文章和哥德尔、艾舍尔、巴赫–集异璧之大成这本书,这里空白太小写不下.

引用

用二进制来解汉诺塔问题

隐藏在汉诺塔中的分形曲线

康托尔、哥德尔、图灵——永恒的金色对角线

谢尔宾斯基三角形能用编程写出来么？该怎么写？

10种编程语言实现Y组合子

python数据结构与算法 23 宾斯基三角形

谈谈递归

Quine 是什么

Even while it changes, it stands still

前言

第三章的阅读之路也算是比较漫长了,和计划的SICP进度可能还是差距很大,但是好歹也是在慢慢推进了..第三章内容算是比较杂的但是挺重要的吧,特别是在这个流和分布式被越来越重视的8102年,而且在工作之后再来看这些问题也是有很多的新收获,确实很多知识虽然过了几十年,其实本质上是没有什么变化的,而我的感觉就是SICP提供给我一种从语言的角度来看待计算机问题的角度,从而使得对很多问题的思考更加全面和多样了.

总结

在前两章的基础上,在我们构建系统的时候,还需要一些知识来使得我们在构建大型的系统时使得系统更具模块性,我们希望这种策略能够在有新的对象或者动作添加进系统的时候不需要修改原有的代码,只需要加一些额外的代码(symbolic analogs)就能够解决问题.

在我们构建系统的时候有两种看待事物的角度:

• 第一种是把一个大型系统视为对象的集合,而对象的行为可能随时间变化
• 第二种是像电子工程师一样把系统看作是信号处理系统,把系统看成是信号在元件之间流动.

赋值和局部状态

看待系统中状态变化的一种观点是:状态变化可以被分组成几个紧密相关的子系统并且子系统之间的关系要保持松散.这也就导致我们想到要使得每个对象都有其局部的状态(local state varibles)

引入set!

比如在取钱的时候,我们的流程应该是下面这样的:假设我们有100块钱

1
2
3
4
5
6
7
8

(withdraw 25)
75
(withdraw 25)
50
(withdraw 60)
"Insufficient funds"
(withdraw 15)
35

而这样的求值方式前面没有状态的函数肯定是做不到的了,因为每次调用相同的函数都会产生不同的结果了.这时候就需要引入赋值,也就是set!.代码的实现如下:

1
2
3
4
5
6

(define balance 100)
(define (withdraw amount)
    (if (>= balance amount)
        (begin (set! balance (- balance amount))
            balance)
        "Insufficient founds"))

而set!的引入也导致前面的替换模型的规则就失效了.因为balance变成了一个绑定在全局环境里的变量.

引入赋值的好处

It is tempting to conclude this discussion by saying that, by introducing assignment and the technique of hiding state in local variables, we are able to structure systems in a more modular fashion than if all state had to be manipulated explicitly, by passing additional parameters.

通过局部状态可以使得我们更加模块化的来构建系统.

引入赋值的代价

那么,代价是什么呢?

1. 替换模型在这里不再适用了
2. 由于引入了赋值,函数的执行顺序变得重要了,我们也失去了函数式编程的一部分优雅
3. 我们不得不接受命令式编程一样的复杂性

programming with assignment forces us to carefully consider the relative orders of the assignments to make sure that each statement is using the correct version of the variables that have been changed.This issue simply does not arise in functional programs

求值的环境模型

为了应付set!这个需求,我们需要引入一个叫做环境的结构,环境就是一系列的帧(frames)构成的.而相对应的,环境模型的求值规则是:

1. Evaluate the subexpressions of the combination.
2. Apply the value of the operator subexpression to the values of the operand subexpressions.

大致就是为每一个子表达式创建一个自己的环境,然后绑定它的父表达式,子表达式内的变量自己用,求值的时候的感觉就是自底向上求值.

用帧来存储局部状态

根据上面的规则翻译一下上面从银行取钱的函数就是这样的:

1
2
3
4
5
6
7
8
9
10

(define (make-withdraw balance)
  (lambda (amount)
    (if (> amount balance)
      "Insufficient"
      (begin
        (set! balance (- balance amount))
        balance))))

(define W1 (make-withdraw 100))
(W1 50)

求值(W1 50)的过程如下图:

环境模型解释了使得局部过程定义变成模块化编程中实用技巧的两个关键特性:

• 局部过程被绑定在自己的帧中,只在运行时被创建,优于全部绑定在全局变量中的方式
• 局部过程可以轻松访问绑定环境中的参数,因为这是一个对其封闭的过程.

对可变的数据进行模块化

主要还是讲一些数据结构,但是使用了新的技术.

Mutable List Structure

主要是借助set!来实现对List进行可变的操作.下图就是把x的cdr变成y的图片(set-cdr! x y)

表示队列

队列的概念和操作就不写了,大致就是用set!来修改队首和队尾来实现一个队列.

表示表格(Tables)

key-value的形式,和字典或者JSON比较相似.

模拟数字电路

这也就是开始提到的使用电子工程师的眼光来看待问题的例子,在课程上老师也讲到了他认为电气系统是最完美的系统.

用与非门来构造一个半加器:

数字电路的优势就在于可以使用简单的模块构造出具有复杂功能的模块,然后使用复杂的模块构造出更复杂的模块,比较类似于第一章讲到pair时pair的闭包性质一样.

而数字电路设计的难点就在于信号在电路中的传输是有延迟的.

约束传播

在之前我们都把代码组织成单向的计算,而这里就举了一个可以从任何方向来求值的约束传播的例子.

而这其实也是一种新的抽象问题的方式.

并发:时间是本质问题

The central issue lurking beneath the complexity of state, sameness, and change is that by introducing assigment we forced to admit time to our computational models.

what makes this complicated is that more than one process may be trying to manipulate the shared state at the same time.

一个两个人同时从银行中取钱的例子:

使得事情变得复杂的原因就在于多个进程可以同时操作同一个共享的状态,重要的就是如何保证操作的原子性,一种解决的办法就是使用Serializer(串行化),也就是类似于锁的机制.

而一旦引入了锁也就会有deadlock(死锁)的存在(这里就略过).

并发,时间和交流

The basic phenomenon here is that synchronizing different processes, establishing shared state, or imposing an order on events requires communication among the process.

一旦涉及到并发也就涉及到了通讯的问题,也就是进程之间分享同一个状态的方式,当然这就有很多的取舍可以做了,是要大家都能同时获取状态的变化还是可以延时获取状态的变化,而这个问题到了分布式中就会变得越发的明显,而Hadoop最大的性能瓶颈其实也就是在于网络的IO.

从本质上看,在并发控制中,任何时间概念都必然与通信有内在的密切联系.有意思的是,时间与通信之间的这种联系也出现在相对论里,在那里的光速(可能用于同步事件的最快信号)是与时间和空间有关的基本常量.在处理时间和状态时,我们在计算模型领域所遭遇的复杂性,事实上,可能就是物理世界中最基本的复杂性的一种反映.

可能这就是科学的共性吧.虽然感觉有点玄乎,但是这也是SICP的魅力所在吧.

Streams(流)

streams are a clever idea that allows one to use sequence manipulations without incurring the cost of manipulating sequence as lists.

简单的说流就是延时求值,也可以说是需求驱动(demand-driven)的,就是你要一个就给你一个,Python中的yield就是这种感觉.

Infinite Streams

而使用delay和force来实现延时求值也使得我们可以做一些以前办不到的事,比如一个表示正整数的无穷流:

1
2
3

(define (integers-starting-from n)
  (cons-stream n (integers-starting-from (+ n 1))))
(define integers (integers-starting-from 1))

信号系统中的流

把积分过程看作是一个信号处理系统:

1
2
3
4
5
6

(define (integral integrand initial-value dt)
    (define int
        (cons-stream initial-value
            (add-streams (scale-stream integrand dt)
                            int)))
int)

函数式编程的模块化和对象的模块化

如果我们把合并请求交易模块化的话,就像下面这样:

问题在于我们每次都要接收Peter和Paul的请求才能进行一次合并,如果两个人请求的频率相差很大的话,那么频繁请求的人就会堆积很多请求不能处理,而一旦引入显式的同步来保证事件发生顺序的正确性的话,又会引入函数式编程中的一个大问题(因为显式同步引入了赋值和时间,这是函数式编程想避免的):也就是在没有时间这个属性的情况下如何去”公平”的合并两个请求.

总结

We can model the world as a collection of separate, time-bound, interacting objects with state, or we can model the world as a single, timeless, stateless unity.

我们面临的不是编程方法的挑战,而是两种不同的世界观的挑战,看待世界不同的方法导致了OO和FP两种分支,如果两个分支在将来能够融合的话是坠吼的.

你问我支不支持,我肯定是支持的

第三章的总结也到此结束了,可以说在SICP的这一段历程是玄幻的和充满乐趣的,这也是这本魔法书的魅力所在吧.而在项目中遇到的包括并发,分布式的问题也增加了对这些CS中基本的问题的思考:

吾尝终日而思矣,不如须臾之所学也

application/x-www-form-urlencoded

这是比较常用的提交数据的方式,在项目中也使用的是这一种,在MockMvc测试的参数准备时可以这样使用:

1
2
3
4
5
6
7
8
9

UrlEncodedFormEntity form = new UrlEncodedFormEntity(Arrays.asList(
                new BasicNameValuePair("参数1", value1),
                new BasicNameValuePair("参数2", value2),
        ), "utf-8");
MvcResult result = mvc.perform(MockMvcRequestBuilders.post("/test")
        .contentType(MediaType.APPLICATION_FORM_URLENCODED)
        .content(EntityUtils.toString(form))
)
        .andExpect(status().isOk()).andReturn();

主要使用的是UrlEncodedFormEntity类,要注意的是需要设置字符集否则传参的时候中文会变成???.

application/json

我使用的是用阿里开源的fastjson直接转换的形式:

1
2
3
4
5
6
7
8
9

Parm parm = new Parm(); //你要传的参数的对象
//设置参数对象的值
String requestJson = JSONObject.toJSONString(parm);
MvcResult result = mockMvc.perform(post("/softs")
        .contentType(MediaType.APPLICATION_JSON)
        .content(requestJson)
)
        .andDo(print())
        .andExpect(status().isOk()).andReturn(); 

multipart/form-data

这个没有使用过,就借鉴Stack Overflow上的一个答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

MockMultipartFile file = new MockMultipartFile("data", "dummy.csv",
        "text/plain", "Some dataset...".getBytes());

MockMultipartHttpServletRequestBuilder builder =
        MockMvcRequestBuilders.fileUpload("/test1/datasets/set1");
builder.with(new RequestPostProcessor() {
    @Override
    public MockHttpServletRequest postProcessRequest(MockHttpServletRequest request) {
        request.setMethod("PUT");
        return request;
    }
});
mvc.perform(builder
        .file(file))
        .andExpect(status().ok());

get请求传参

这个虽然不是POST也很简单,但是也记录一下

1
2
3
4
5

MvcResult result = mvc.perform(MockMvcRequestBuilders.post("/v4/address/deleteAddress")
        .param("参数1", value1)
        .param("参数2", value2)
)
        .andExpect(status().isOk()).andReturn();

也可以使用params的方式使用Map来传参,但是我还是习惯这样来初始化,因为毕竟每个参数还是需要自己设置的,这样看起来也清晰一点.