“Show me your flowchart and conceal your tables, and I shall continue to be mystified. Show me your tables, and I won’t usually need your flowchart; it’ll be obvious.” – Fred Brooks, The Mythical Man Month (1975)
吐槽一下，最近手指好疼，怀疑打字打太多了，等下有空看看医生，orz
我们先看这一个著名的笑话：
三个程序员被要求穿过一片田地，到达另一侧的房子。
菜鸟程序员目测了一下之间很短的距离，说：“不远！我只要十分钟。”
资深程序员看了一眼田地，想了一会，说：“我应该能在一天内过去。”菜鸟程序员很惊讶。
大神程序员看了一眼田地，说：“看起来要十分钟，但我觉得十五分钟应该够了。” 资深程序员冷笑了一声。
菜鸟程序员出发了，但只过了一会，地雷爆炸了，炸出了巨大的洞。这下他必须偏移预定的路线，原路返回，反复尝试穿过田地。最后他花了两天到达目的地，到的时候颤颤发抖，还受了伤。
资深程序员一出发就匍匐前进，仔细地拍打地面，寻找地雷，只有在安全的时候才前进。他在一天的时间内小心谨慎地缓慢爬过了这片地，只触发了几个地雷。
大神程序员出发之后径直穿过了田地，十分果断。他只用了十分钟就到了另一边。
“你是怎么做到的？”另外两个人问道，“那些地雷怎么没有伤到你？”
“很简单，”他回答道，“我最初就没有埋地雷。”
一般来说，我们写程序，都是这样的步骤：
0：写出程序
1：写测试
2：通过测试查找错误，回到0修补，如果没发生问题就假装程序写好了
这时候有一个很大的问题：debug是一个很麻烦的过程，而且debug后不代表程序没有问题，只代表了程序在这些测试上没有问题（所以你还要牢费心力找测试）。更严重的问题是，在多线程或者分布式系统里面，同一段代码同一段输入，问题是概率性的：有可能会发生，也有可能不会发生。更更糟糕的一点 - 这些分布式代码，比如paxos的实现，往往是最核心的代码，当这些代码发生问题后，会带垮整个服务器集群，造成巨大的损失。
但是，为什么我们要劳心劳力的去debug？我们不把错误放进程序，不就好了？
或者，我们更进一步，为什么要写程序？把程序种子埋土里，然后过几天等程序长大了，就收掉，不就行了？
你先别笑，这的确是编写复杂程序的一个方法。
更具体的说，当我们程序运行到一半，假设我们随机修改一下变量的值，很明显程序不会没问题的继续运行下去。
比如说，如果我们在写一个二叉搜索树，当我们运行的时候，把一颗树的最左节点跟最右节点交换了，那接下来可能会找不到需要的值。
也就是说，我们的程序需要遵守一定的规则(invariant)。对于上面的例子来说，我们需要遵守的invariant是，一个二叉树的左边的所有节点小于等于自身，自身小于等于右边的所有节点。
所以，我们写程序的时候，要保证这些invariant的正确性。但是，我们可以反过来，从这些invariant，推导出一个程序！
更具体的说，我们
0 - 写下程序输入跟输出符合的条件，一般来说，输入的条件并不等价于输出的条件，所以这时候，这两个条件之间，是有一个空缺的
1 - 根据这些规则，猜出一小段代码，这些代码会把这些空缺变得更小，然后我们不停进行这个操作，直到空缺消失。这时候，程序就编写完成了。
这时候，由于invariant给予了程序很大的限制，只要我们指定了invariant，剩下的程序，往往就没有什么‘选择’，只有一个写法了，于是写起来就很简单！这个方法，叫做stepwise refinement。
我们下面就用一个inplace quicksort做例子吧：
我们先写下开头：
# 0 <= lo <= hi <= len(l)
def quicksort_aux(l, lo, hi):
# ...
pass
# l[lo, hi) is a sorted permutation of l[lo, hi) at input time
def quicksort(l):
quicksort_aux(l, 0, len(l))
return l
注意，这里我们用的是左闭右开语法：l[lo, hi)指所有l[i]，where lo <= i < hi。
这时候，很明显我们的程序没写完，有个巨大的gap：我们需要把这个范围排序！我们用…代表这里的程序还没有写完。
这时候，我们有一个最简单的case:如果lo == hi，那数组长度为0，排序完毕，我们可以直接返回。
# 0 <= lo <= hi <= len(l)
def quicksort_aux(l, lo, hi):
if lo == hi:
return
else:
# lo < hi
# ...
pass
# l[lo, hi) is a sorted permutation of l[lo, hi) at input time
那我们可以写下lo == hi的判断。判断结束后，注意：当lo != hi的时候，结合lo <= hi，我们可以得知lo < hi。只有这时候，我们才可以去取数组里的元素（否则数组里根本没元素！）。换句话说，我们得到了新的条件，成功把这个gap缩小了点。
这时候，我们就可以取出这个数组的首个元素：
# lo < hi
x = l[lo]
# ...
为了节省蕾米莉亚，我会只显示程序的修改跟修改附近的代码。
我们接下来，可以根据x，把这整个数组分成三部分，<x，=x，>x。
当然，这个区分不是trivial的，我们需要分成多个步骤进行。
我们可以思考一下 - 区分好的程序，是怎么样的捏？
这时候，我们会有三个子数组，a, b, c,其中lo == a.start, a.end == b.start, b.end == c.start, c.end == hi。
并且，l[a.start, a.end) < x, l[b.start, b.end) == x, l[c.start, c.end) > x
这时候我们的程序是不满足这些条件的，但是，假设我们无视掉c.end == hi，我们可以把a, b, c的start，end都设成lo，这时候，其他的条件全部满足。那我们先写下来这一部分程序，然后再想办法取满足c.end == hi吧。
由于a.end == b.start, b.end == c.start，我们只需要一个变量来记录a.end跟b.start，b.end跟c.start同理。这时候，除了上面两个，我们只需要c.end，所以只有三个变量。
x = l[lo]
i, j, k = lo, lo, lo
# invariant:
# lo <= i <= j <= k <= hi
# l[lo, i) < x
# l[i, j) == x
# l[j, k) > x
如果我们需要debug，我们可以把上面的这些invariant作为assertion，这时候，这些assertion保证了我们程序最核心的正确性，但这不是我们的重点：
assert lo <= i
assert i <= j
assert j <= k
assert k <= hi
for a in range(lo, i):
assert l[a] < x
for a in range(i, j):
assert l[a] == x
for a in range(j, k):
assert l[a] > x
然后，我们需要使得k == hi。怎么办捏？很简单！
while k != hi:
pass
# k == hi
很明显，当这个循环退出的时候，!(k != hi)，所以只要我们让这循环退出，就可以了。
quicksort_aux(l, lo, i)
quicksort_aux(l, j, k)
然后，我们只需要递归调用quicksort，任务就完成了。
换句话说，从最初的‘编写quicksort’我们成功的把问题化简为‘使k == hi’，很明显后者简单很多！
那我们怎么办捏？首先，当k != hi的时候，由于k <= hi，k < hi。换句话说，我们可以读k元素：
# k < hi
y = l[k]
然后，由于我们要分成<x, =x, >x三个数组，我们可以对y<x, y==x, y>x三种情况进行判断：
if y < x:
# ...
pass
elif y == x:
# ...
pass
else:
# y > x
# ...
pass
当y > x的时候，最简单，于是我们先处理这个（注：先处理那个都最终会产生一样的程序，但是我在教学，于是用最简单的先做例子）。这时候，l[j, k+1) > x，于是我们可以很简单的自增k，这时候，l[j, k) > x依然成立，并且我们做了一点微小的工作：[j, k)里面的元素更多了。我们试试看对剩下的程序做这些工作吧。
# l[j, k+1) > x
k += 1
# l[j, k) > x
那接下来简单的是y == x。这时候，我们并不可以自增j完成工作，因为l[j] > x。
但是，我们可以把l[j], l[k]交换，这时候l[j] == x。当然，这时候打破了l[j, k) > x的这个invariant，但是，我们会对j自增，把invariant重新修复。
l[j], l[k] = l[k], l[j]
j += 1
这时候，要注意！j += 1打破了j <= k的invariant，于是我们要修复之。修复起来其实很经典：如果j > k，那k += 1就行了。这时候，我们并不会给[j, k)增加元素：本来是空数组，弄完还是空数组，所以没有打破其他invariant。
# j - 1 <= k
if j > k:
# j == k + 1
k += 1
# j <= k
else:
# j <= k
pass
这时候，我们剩下了y < x这个case。我们照样swap然后自增：
l[i], l[k] = l[k], l[i]
i += 1
然后修复i <= j：
# i - 1 <= j
if i > j:
# j == i + 1
j += 1
# i <= j
# ...
else:
i <= j
当然，要注意：j += 1破坏了j <= k，我们用一样的办法修复。
等我们写完后，就会有整个程序：
# 0 <= lo <= hi <= len(l)
def quicksort_aux(l, lo, hi):
if lo == hi:
return
else:
# lo < hi
x = l[lo]
i, j, k = lo, lo, lo
# invariant:
# lo <= i <= j <= k <= hi
# l[lo, i) < x
# l[i, j) == x
# l[j, k) > x
while k != hi:
# k < hi
y = l[k]
if y < x:
l[i], l[k] = l[k], l[i]
i += 1
# i - 1 <= j
if i > j:
# j == i + 1
j += 1
# i <= j
# j - 1 <= k
if j > k:
# j == k + 1
k += 1
# j <= k
else:
# j <= k
pass
else:
i <= j
elif y == x:
l[j], l[k] = l[k], l[j]
j += 1
# j - 1 <= k
if j > k:
# j == k + 1
k += 1
# j <= k
else:
# j <= k
pass
else:
# y > x
# l[j, k+1) > x
k += 1
# l[j, k) > x
pass
# k == hi
quicksort_aux(l, lo, i)
quicksort_aux(l, j, k)
# l[lo, hi) is a sorted permutation of l[lo, hi) at input time
def quicksort(l):
quicksort_aux(l, 0, len(l))
return l
这时候回来看，我们会发现这个程序很长，并且很复杂，有最高五层的嵌套！但是，如果你回顾一下，我们写这个程序的时候，似乎并不困难：我们的每一步，只是把gap缩小了一点点。特别是，当我们进入while loop这个核心代码块的时候，我们就进入了
0 - 做一点微小的工作
1 - 修复这个操作破坏掉的invariant
这个循环。
这个跟原神背后的道理是相通的。当你开始玩原神的时候，你连打史莱姆都费劲。但是随着你玩游戏，你会不停的累积资源，提升自己，到最后就可以挑战极度困难的事物。这其中，其实并没有一个‘很困难的地方’！
所以，当你下次写程序不思考invariant，遇到了奇怪的错误，无法修复的时候，要记住：
