工作札记 (11)

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

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

CPS & Y-combinator

周末看了一篇"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，从而调用了系统内置的平方根函数。莫非那是上帝开的小玩笑？:-)

mini-mini-compiler

源代码来自：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行代码，代码之美，莫过于此！

map/filter with foldr

第七课的小练习：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，居然是个路人甲！吾恼羞成怒，只有再打回去，"来五角场吃饭，老子今天生日！" 不过说实话，和大狼还真有那么一点点心有灵犀 -- 我结婚那天众宾客散去后，他从遥远的尼日利亚打电话回来，而他并不知道我的婚期。

程序随笔 - 7

前些日子兴致起来，学了点OCaml，因为不太习惯Haskell的那么pure，或者是太习惯了“printf大法”。OCaml除了impure之外，和Haskell非常相像 -- 可能这也是很多从命令式编程(imperative programming)转到FP的时候，更喜欢OCaml而非Haskell的原因吧。

很巧的是，前几天为一些同事做了关于Linux File I/O programming的培训。我一直在想，如果时间充裕的话(虚拟语气)我应该会聊一些关于 side-effect 之类的东西。讲File I/O的时候我讲了一些关于pipe的东西，而学 Haskell Monad 的时候，我脑子里蹦出来的是两个东西：pipe和Scheme中的continuation。

这几天我断断续续的在想，一个理想中的程序[1]是不是本来就不应该如此直接[2]。突然意识到，像Haskell那样小心翼翼的把pure和impure分隔开简直是个绝妙的想法！硬件设计者或许会在心里痛斥软件设计者的不思进取，因为系统性能的提高很多时候是靠硬件的进步而非软件 -- 软件越来越臃肿，即使是硬件的并发性能提高到令人惊讶的程度，而软件的发展却始终是原地踏步。MSDN Channel 9上Brain Beckman博士有一个长达一个多小时的视频：Don't fear the Monad，深入浅出，相当精彩。无需任何FP背景，只要稍微了解一点编程就能心领神会。

[1] 我也无法描述心中的理想的程序，不过至少应该是简洁、易扩展、高并发吧；

[2] 就像C中可以到处插入printf，添加全局变量等等。

Training是个体力活

天骤冷，鼻炎也趁机发难。讲得热火朝天、嗓门发烟、浑身冒汗，不过鼻炎却似乎缓解一些。

今天是linux network administration，明天还有两小时关于Linux IO的system programming，相对而言我还是更喜欢后者这个话题。前者多少有点routine，而后者则需要一点创造力。

误人子弟

下周公司内部有个training，关于Linux系统管理和编程，为了省钱，做training的都是自己的员工。而我不幸属于trainer行 列，负责network administration 和 IO programming。不幸在于要准备PPT，比较烦 -- 而且给定的时间是前者3小时、后者2小时，实在很难展开，估计只能误人子弟了，还好只有三十几个人，不至于大面积受灾 ^_^。

用Haskell写个JSON解析器

本想自力更生试着用Haskell写个JSON解析器，一不小心网上一搜一大把，并且忍不住瞄了几眼。那就做个简单的修改加翻译吧，原文链接：http://snippets.dzone.com/posts/show/3660

> import Text.ParserCombinators.Parsec
> import System
> import qualified Data.Map as Map

引入一些必要的库，比如Parsec，祭起我们的利器哈！

> mainParser = do {
>               val <- valueParser
>             ; skipMany space
>             ; eof
>             ; return val
>             }

解析器的主函数，该函数以典型的Monad风格对输入数据调用valueParser函数进行解析，do中的操作是序列华的，每一个行都是一次匹配，这三行的意思是，它期待的输入的格式是JSON数据、可能的一些空字符、文件尾巴，如果解析成功就返回解析后的数据val。

> main :: IO ()
> main = do {
>         args <- getArgs
>       ; val <- parseFromFile mainParser $ args !! 0
>       ; print val
>       }

main函数先得到命令行参数存在列表args中，列表的第一个元素(args !! 0)作为文件名，parserFromFile是Parsec里的一个函数，它调用mainParser对命令行指定的文件进行解析，最后在打印出解析结果val。

> data JSON = ListValue [JSON]
>           | LiteralString String
>           | LiteralInt Integer
>           | LiteralBoolean Bool
>           | RecordValue (Map.Map String JSON)
>             deriving Show


上面的这些玩意儿叫做ADT，它的意思是：我们有JSON这样一种数据结构，它有五个构造函数ListValue, LiteralString, LiteralInt, LiteralBoolean和RecordValue，每个构造函数后面跟着的都是一种类型。最后，该数据结构继承所有Show类具有的行为 -- 这使得JSON类型的数据可以用print显示出来。

有了上面的定义后，我们可以方便的构造出一些JSON类型的数据，比如：

LiteralString "abc"
LiteralInt 123

在GHC或者Hugs中可以用:t来显示给定输入的类型：

:t LiteralString "abc"
LiteralString "abc" :: JSON

这是说LiteralString "abc"是个JSON类型。好了，接下来写几个简单的parser，我们可以dive & conquer。第一个Parser用来识别字符串 -- 字符串以'"'开头，中间是一个或者多个字符，最后有个'"'收尾。解析成功后会返回一个JSON类型的字符串。
> literalString :: Parser JSON
> literalString = do {
>     char '"'
>     ; val <- many1 letter
>     ; char '"'
>     ; return $ LiteralString val
>     }

接下来雷同的便是解析整型、布尔型：
> literalInt :: Parser JSON
> literalInt = do {
>     ; val <- many1 digit
>     ; return $ LiteralInt (read val)
>     }
>
> literalBoolean :: Parser JSON
> literalBoolean =
>         do {
>           string "true"
>         ; return $ LiteralBoolean True
>         }
>     <|> do {
>         string "false"
>         ; return $ LiteralBoolean False
>         }

这里'<|>'是个combinator，它用来连接两个parser，如果前一个解析不成功，就用下一个来解析。用'<|>'可以把整个JSON的解析写成如下形式：
> valueParser :: Parser JSON
> valueParser =
>      literalString
>  <|> literalInt
>  <|> literalBoolean
>  <|> recordParser
>  <|> listParser

其中还有两个parser没有实现：recordParser和listParser，分别用来解析object和array。list以'['打头，']'结尾，其中的数据以','分割：
> listParser :: Parser JSON
> listParser = do {
>     char '['
>     ; words <- sepBy1 valueParser listSeparator
>     ; char ']'
>     ; return $ ListValue words
>     }
>
> listSeparator :: Parser ()
> listSeparator = do {
>     skipMany space
>     ; char ','
>     ; skipMany space
>     }

最后就是解析object啦，打完收功！
> recordParser :: Parser JSON
> recordParser = do {
>     char '{'
>     ; defs <- endBy definitionParser listSeparator
>     ; char '}'
>     ; return $ RecordValue $ Map.fromList defs
>     }
>
> definitionParser :: Parser (String, JSON)
> definitionParser = do {
>     skipMany space
>     ; key <- many1 letter
>     ; char ':'
>     ; skipMany space
>     ; val <- valueParser
>     ; return (key, val)
>     }
>
> definitionSeparator :: Parser ()
> definitionSeparator = do {
>     skipMany space
>     ; char ','
>     ; skipMany space
>     ; return ()
>     }

Lion King

>           ___         _______________      ____
>          /_  \     __/               \__  /  __\ amw
>         /  \  \  _/  ___           ___  \/  /   \
>         |   \  \/   / __\         / __\   \/    |
>         |   \      | / _||       | / _||   |    |
>          \         |/_/@||    ___|/ /@||   |   /
>           \__            /         \       |__/
>              |          / \ ________\      |
>               \      /     (_       _)     |
>                |    /\\_     \_____/  |    /
>                 \     \ \_    __|__   |  _/
>                 |\     \  \__/     \__/_/
>                 | \     \             /
>                 |        \___________/

ASCII Art from http://www.ascii-art.de/ascii/s/simba.txt

似已登堂，尚未入室

曾经立志成为Linux内核高手，并为此努力研究了几年，后来无论是实习、还是现在的第一份工作都与此有所背离，于是就希望在compiler方面有所建树 -- 想要成为一个有功力、有底气的非内核程序员，这个应该是一个有意义的方向。于是就先读了SICP(当然其中还有老大的影响)，学了Scheme -- 记得当时在某个邮件列表上看见说Scheme很适合用来模拟别的语言。读SICP还是相当令人愉悦的，从中学到了很多有益的思想并有了一点函数式编程思维。

SICP中有一章是用Scheme写个Scheme解释器，比较好玩。后来看见网上有份详细的教程，用Haskell写个Scheme解释器 -- 因此顺便学了点Haskell，中间因为工作需要，学了Ruby。Ruby很适合用来实现DSL，而Scheme(包括其他Lisp方言)的macro系统也及其牛b。Haskell的ADT比较酷，加上Parsec，还有酷酷的pattern matching，使得它写parser相当轻松。

嗯，我要把Haskell学学好。:-)

见闻录

上上周末，五角场。路过星巴克，隔着玻璃看见一位中年妇女捧着一台Mac，当然这在星巴克很常见。回头路过的时候又瞄了一眼，发现那是个蓝天白云WindowsXP，桌面光光的很干净，不过也因此很明显的看见装了个360安全卫士。

上周末，路过人民公园。起风，有的冷。不过公园里面却异常热闹，到处都是告示之类。走近了一看才发现原来都是代为相亲的父母，而那些帖得一排一排的貌似"告示"的东西其实都是征婚启事。