Live4thee

曾经在(10)中聊过用工具自动在v2的基础上生成一些v3的代码，而今天才发现我又不得不在v3的基础上重新生成v2的代码 — 因为v3所基于的v2其实是一个post-v2分支，而两者的内部数据处理方式是不兼容的 — what’s the fuck! 为了让使用v2的客户在v3上仍旧happy，我只有牺牲自己的happy了。

曾经很好奇，如果biz software意味者兼容性、良好的支持和扩展性，这究竟是怎么做到的。现在终于明白了，大部分我所见到的biz software就是个BS，缩略语居然如此一致 — 难道这仅仅是巧合？那上面的这些内容又是如何实现的呢？答案是：廉价劳动力啊！

周末看了一篇”The Evolution of a Haskell Programmer“，里面列举了Haskell程序员写阶乘函数fac的各种实现方法，可以用两个成语来形容：琳琅满目、叹为观止。虽然感觉上有点类似孔乙己在纠缠茴香豆的茴字有几种写法，不过内容还真的挺有意思。其中有两个实现方法可以稍微聊一聊：1. CPS；2.利用Y combinator。

1. CPS - Continuation-passing style
   CPS是Gerald Jay Sussman和Guy L. Steele在1975年创建Scheme语言时提出的，其大意是处理的结果并不是像平时习惯的那样直接给出，而是给出一个临时结果。比如，写parser时，假设输入很复杂，我们不必一下给出解析的结果，而是步步为营。我们可以写出许多很简单，容易测试的小parser，比如parseNumber, parseString, 等等。每一步尝试一种解析，直到剩下的输入都不能被解析的为止。下面是个CPS风格的fac函数：
   > facCps k 0 = k 1
   > facCps k n = facCps (k . (n*)) (n - 1)
   > fac = facCps id
   • `.’在Haskell中是个函数组合算子，比如f (g x) = (f . g) x
   • (*) 在Haskell中是个函数，有两个参数，求得乘积。(n*)也是个函数，只有一个参数，如果给定m，则返回n*m — 这叫做currying，Haskell中所有函数都是currying的。
   • 函数id直接返回输入参数本身，比如id 3 = 3, id fac = fac
2. Y combinator
   Y combinator是递归函数理论中的重要概念，说它是计算机科学的奠基性基础理论也不为过 — MIT的计算机科学系的系徽就是它。它的数学形式是Y(f )= f (Y (f))，也就是说给定一个函数f，Y会求出该函数的不动点。有很多教程教你怎样一步步推导出Y函数，然而在Haskell中几乎直接原样照搬就行：
   > y f = f (y f)
   > fac = y (\f n -> if  n == 0 then 1 else n * f (n-1))
   • Haskell是lazy的，所以上面的递归定义没问题；
   • Haskell中函数名不能用大写字母开头，大写字母开头的是类名，类型名及其构造方法。

我以上帝的名义发誓，昨天我人品爆发居然写了个求平方根函数sqr = y (\f x -> x / f x)，因为y = x/y的不动点y’就是x的平方根，我敲了个sqr 3，居然得到1.732050… 精确到小数点后十几位 — 后来不能重现，每次都stack overflow — 而用稍微瞄一眼就知道这是应该的，因为这次没有递归结束条件，会无穷无尽递归下去。我确信没有误敲sqrt，从而调用了系统内置的平方根函数。莫非那是上帝开的小玩笑？:-)

源代码来自：http://www.cs.nott.ac.uk/~gmh/compiler.lhs

> data Expr                 =  Val Int | Add Expr Expr
>
> eval                      :: Expr -> Int
> eval (Val n)              =  n
> eval (Add x y)            =  eval x + eval y
>
> type Stack                =  [Int]
>
> type Code                 =  [Op]
>
> data Op                   =  PUSH Int | ADD
>
> exec                      :: Code -> Stack -> Stack
> exec []           s       =  s
> exec (PUSH n : c) s       =  exec c (n:s)
> exec (ADD    : c) (m:n:s) =  exec c (n+m:s)
>
> comp’                 :: Expr -> Code -> Code
> comp’ (Val n)   c     =  PUSH n : c
> comp’ (Add x y) c     =  comp’ x (comp’ y (ADD : c))
>
> comp                      :: Expr -> Code
> comp e                    =  comp’ e []

它只支持整型和求和，表达式转换成指令的列表后在堆栈上执行，结果放在栈顶。假设expr为 Add (Val 1) (Val 2)，则 comp expr 会得到 [PUSH 1,PUSH 2,ADD]，把这个结果丢给exec 则得到[3]。

*Main> let e = Add (Val 1) (Val 2)
*Main> exec (comp e) []
[3]

区区23行代码，代码之美，莫过于此！

第七课的小练习：http://www.cs.nott.ac.uk/~gmh/chapter7.ppt

> map’ :: (a -> b) -> [a] -> [b]
> map’ f = foldr (\a b -> (f a) : b) []
>
> filter’ :: (a -> Bool) -> [a] -> [a]
> filter’ f = foldr f’ [] where
>     f’ a b = if f a then a:b else b

午夜刚过，杀完一盘游戏后兴致盎然。抓起身边手机，屏幕还是那样静如一潭死水。吾愤愤不平对LP曰：”想当年还未结婚时，这时候一定会有几条短信了嘛！” LP说，”你out啦！人老珠黄，人去茶凉啊！”

一觉睡到大天亮。开机后短信声接连响起。还是有人记得俺生日的嘛！HOHO~ 谢谢各位兄弟姐妹。

下午刚准备出去晒晒太阳，大狼打来电话，吾心想：”不愧是同居于一个宿舍四年的死狗，知道今天打电话来。”聊啊聊，就这么挂了。NND，居然是个路人甲！吾恼羞成怒，只有再打回去，”来五角场吃饭，老子今天生日！” 不过说实话，和大狼还真有那么一点点心有灵犀 — 我结婚那天众宾客散去后，他从遥远的尼日利亚打电话回来，而他并不知道我的婚期。