Git是纯函数式数据结构?

1,198 阅读5分钟
原文链接: mp.weixin.qq.com
前言

最近看到一篇文章,标题是“Git is a purely functional data structure” , 把Git的Commit, Branch等操作和数据的不变性做了类比,很有意思,和大家分享一下。 

注意,这篇文章并不是一字一句的翻译。 

原文地址: 

https://blog.jayway.com/2013/03/03/git-is-a-purely-functional-data-structure/ 

作者:Philip Nilsson

不变性

函数式编程中有个很重要的概念就是不变性(immutablity),就是说一个对象的状态在构造完成以后不可改变。

比如有个list 是[3,2,1],如果它是可变的,那我们就可以向头部插入一个元素4, 从而让这个列表变成[4,3,2,1]。之前的list 对我们来说丢失了,我们只能看到新的列表。

在函数式编程中,这是不应该发生的,当我们插入一个元素4的时候, 并不会修改老的列表,相反,我们会创建一个全新的列表:[4,3,2,1], 老的列表[3,2,1]依然存在。

可能有人会想到:这个immutablity有什么好处呢?  

很重要的一点就是线程安全,一个线程对数据的修改不会影响到另外一个线程,哪些为了互斥而引入的锁就不需要了。

但是每次添加一个元素就要创建一个新的列表出来,这样做是不是很浪费、效率很低呢?

嗯,想办法做点优化,复用原来的列表吧, 就像这样:

老的列表和新的列表复用了内存中的元素,但是从外界的使用者看来,这是两个不同的列表。

如果线程要在[3,2,1]之前插入新的元素9 , 怎么处理?  同样,还是可以复用:

如果我想把list 1中的元素3更新成元素5, 这就有点难办了,因为它会影响到两个新的列表,list 1和list 2。  没办法,只有把元素copy一下了:

(码农翻身注: 《Clojure编程》一书中有对不变性和共享存储有更多的讨论)

经过若干次操作,形成了四个列表:

老的列表: [3,2,1]

list 1: [4,3,2,1]

list 2: [9,3,2,1]

list 3: [4,5,2,1]

这四个列表对外界而言是完全独立的,只不过内部的数据是复用的。

Git vs 不变性

但是,这和Git有什么关系?和版本控制有什么关系? 对比下不变性和版本控制:

版本控制的目的:

(1) 用新版本的文件来更新代码仓库,老版本的文件还要保留。

(2) 大家在同一个代码仓库中协作的时候,需要互不干涉。

不可变的数据结构能让我们:

(1)  保持老的数据结构不变的情况下,更新数据结构

(2)  一个线程对数据结构的更改不会影响另外一个线程

两者是不是很像?

更进一步,我们可以说Git就是一个纯函数式的、不变的数据结构,它给你提供了一个命令行客户端让你去操作。

为了完成这种类比,我们需要把上面例子中的数字替换成Commit。

假设说我们有一个代码仓库,其中的master 分支包含了三个按次序的Commit : A, B, C。

用图来表示就是这样:

对于每个commit来讲,还有一些metadata,如comment,暂时忽略他们。

Git commit

如果我们新增一个Commit : D,  就会变成这样:

master “指针”相等于“后移”了一步, 老的history还在(即 master^)

Git amend

如果你用过Git的话,你也许知道可以使用 commit --amend来更新最近一次的Commit, 但是你真的把那个Commit给更新了吗? 

实际上并没有,Git只是创建了一个新的Commit (下图中的E),并且让branch指针指向它而已。 通过git reflog命令,你依然能看到那个Commit (假设它的hash value 是 33b90b7)。

Git branch

正如你在上面看到的,每次你使用 commit --amend , 你实际上创建了一个新的分支!

分支实际上就是给一个我们想引用的commit起了个名字而已。

我们甚至可以使用那个“被替换掉的”,“废弃的”Commit (33b90b7)来创建一个分支:

git checkout -b mybranch 33b90b7

所以,只要你理解了Git 是函数式数据结构的本质,你就可以“为所欲为”,从任何commit上来创建分支了。

原文还讲了Rebase/Merge和不变性的比较,我觉得就不是很贴切了,这里不再展开,感兴趣的同学可以看下原文。

总结

与其把Git描述成一个版本控制系统,不如说版本控制是“不变性”数据结构的一个自然属性。

如果以这种方式来思考的话,Git在概念上比SVN, CVS等要简单。 大家认为Git更加复杂可能是因为这种复杂性能支持更有趣的workflow。

(码农翻身注: 老刘认为Git看起来很复杂,主要是因为是分布式的,需要在本地仓库和远程仓库之间协作。)

(完)

码农翻身,用故事讲解技术本质, 更多精彩文章,请移步《码农翻身三年文章精华