Haskell初心—认识Monad

从三月份开始看Real World Haskell这本书,断断续续看到7月份,总算初步对Haskell有了一些认识。
我想,学习Haskell这门语言,第一个门槛就是Monad这个概念。今天初步来做一点总结。

在读书和试着用haskell做一些习题的时候,就会感觉到,haskell是一门实践性极强的语言。当然,他同时也是一门理论性极强的语言,他允许甚至鼓励你用数学方法去推导函数签名,通过定义一系列公理可以对特定类型的函数式进行数学变形,以达到最短最优美的代码形式。

但对于我而言,那些过分抽象的函数和概念,非常难以理解,并且即使是形式上理解了他的定义,还是无法理解他为何要如此定义,有什么意义。Haskell代码的特点在于极端的精炼,许多函数定义看上去什么都没做,像是在说废话。幸好RWH是一本非常好的教材,他通过许多实例来说明这些抽象定义在实践中的用途,让你看到许许多多在实际代码中经常遇到的痛点,在Haskell中都有解药。如同醍醐灌顶般爽快。(请参见代码交叉拷贝悖论

Monad就是Haskell的一个经典设计。它来源于“范畴论”,可以说是数学中的数学,一坨“抽象废话”。我先不去考虑他的数学含义,单看他在代码中如何化繁为简。这里我抄一段RWH中的代码(略简化)。

data MovieReview = MovieReview {
      revTitle :: String
    , revUser :: String
    , revReview :: String
}

simpleReview :: [(String, String)] -> Maybe MovieReview
simpleReview alist = 
    case lookup "title" alist of
      Just title@(_:_) ->
          case lookup "user" alist of
            Just user@(_:_) ->
                case lookup "review" alist of
                  Just review@(_:_) ->
                      Just (MovieReview title user review)
                  _ -> Nothing         -- no review
            _ -> Nothing               -- no user
      _ -> Nothing                     -- no title

这一段代码是说,有一个电影影评的类型MovieReview,包含revTitle,revUser,revReview三个字段。现在用一个association list来对他进行初始化,simpleReview函数中的case语句略似if else,我们可以看到这段代码的大意是说如果alist中含有title、user、review三个键值并且对应的字段不为空,则用这三个字段初始化MoviewReview类型,否则依次返回Nothing (Maybe是一个包装类型,它的值可以是对应类型的值,或者是Nothing)。
这里是采取了最传统的方式,展现了写代码时经常遇到的苦恼。三层if判断,里面的操作很雷同,应该有办法抽象出来。在C语言中我会采取的办法是把title, user, review三个键值存在数组里,并且通过一个循环来依次判断,虽然实现了重用代码,但是代码可读性变差了。代码主体内充满了类似

auto moviereview = new MovieReview (alist[keylist[0]], 
                                    alist[keylist[1]], 
                                    alist[keylist[2]]);


这样的代码。我们来看看Haskell如何通过monad实现对这样的代码的抽象。实际上Maybe类型就是一个Monad。一个Monad可以简单理解为一个包装类型,他包装了一个变量(可能是函数、操作、状态等等),并且提供一个“>>=”运算,这个运算的意思是,把它包装的变量提取出来,当作参数传入一个可以接受这种类型参数的函数中,而这个函数的返回值必须也是monad包装的。
另外Monad还需提供一个return函数,方便其他函数将原始类型包装为Monad类型。

class Monad m where
  -- chain
  (>>=) :: m a->(a -> m b) -> m b
  -- inject
  return :: a -> m a


为何要这样定义>>=运算,一个monad >>=运算将一个Monad (m a)中的变量(a)扔进一个(a -> m b)函数中,生成一个新的Monad,它包含的变量类型跟传入的可能不同(m b)。这个m b还是Monad,就又可以继续通过>>=方法扔进新的(a -> m b)中。并且这里特别将输入类型m a和输出类型m b分别表示,从而可以将许多不同的方法通过>>=连接起来。就好象一个Monad被送上了生产线,经过一道道工序加工它本身的类型也可以经过许多变化,最终输出一个m b。

这个定义非常优美,我相信c++中的输入输出流操作符就是从这里借鉴的。不过这个流可不仅仅能做输入输出的操作,它可以控制任何一种操作流,非常神奇。因此在RWH中称>>=算符是一种可编程的分号 每个操作后面用>>=结尾可以对应于命令式语言中的;分号,在haskell这样的函数式语言中,通过monad实现了命令式的编程范式。更加强大的是,他的可扩展性远高于传统的命令依次执行,具有灵活的可操控性。

Maybe就是一种monad。他的>>=方法将其包装的变量提取出来,给后续的函数作为参数。如果为Nothing则短路,直接返回Nothing

(>>=) :: Maybe a ->(a -> Maybe b) -> Maybe b
Nothing >>= _ = Nothing
Just v >>= f = f v


通过这一层包装可以很好的将前面的一段代码简化,依次处理title, user, review三个字段,通过>>=这个“可编程的分号”来控制操作流。如果任何一个字段出现Nothing,则后续的>>=函数都会返回Nothing,不会继续调用lookup函数。

simpleReview alist = 
  lookup "title" alist >>=
  \title -> lookup "user" alist >>=
  \user -> lookup "review" alist >>= 
  \review -> Just (MovieReview title user review)  


可以看到代码已经充分简化了。但Haskell的设计者还是不满意,这样的代码还有重复之罪。如果我们可以直接将(lookup “string” alist)作为参数,放进MovieReview的构造函数的话,就可以一行代码实现这个任务了。现在遇到的困难是,lookup返回包裹在Maybe中的量:可能找得到,可能找不到。而MovieReview的构造函数,仅当三个查找都不为空的时候才应当调用,并且其参数应当是解除包装的字符串类型。如何将Monad包裹的值当作参数传入普通的Pure function中呢?

这里Haskell引入了Functor的概念:

class Functor f where
    fmap :: (a->b) -> f a -> f b


他将一个普通的函数(a -> b)提升为对包装类进行操作的Functor (f a -> f b)。这里f是包装函数。这样使得任何包装类型都可以轻松继承所有pure function的代码。在Monad中定义了这样的一个提升操作,称之为liftM

liftM :: (Monad m) => (a -> b) -> m a -> m b
liftM f m = m >>= \i -> return (f i)


这样任何一个f都可以对Monad中包装的值通过“提升操作”进行调用了。这里的liftM仅针对单参函数(a -> b)。我们的MovieReview需要3个参数,这里我们可以借用haskell函数库中的liftM3,针对3参数函数进行提升。

liftM3 :: (Monad m) => (a -> b -> c -> d) -> m a -> m b -> m c -> m d
liftM3 f m1 m2 m3 =
    m1 >>= \a ->
    m2 >>= \b ->
    m3 >>= \c ->
    return (f a b c)

那我们的代码又可以进一步简化了

liftReview alist =
    liftM3 MovieReview (lookup "title" alist)
                       (lookup "user" alist)
                       (lookup "review" alist)


看,经过提升之后MovieReview就像是可以接受三个Maybe作为参数一样地进行调用了,并且>>=符隐藏在了liftM3中,其中控制了一旦任意一个maybe为nothing的时候短路这个流程。虽然这样client代码已经非常优美了,但是lib代码会有些问题。这里的liftM3已经有些呆板了。如果是要提升10个参数的函数怎么办。精益求精,Haskell提供了ap函数让提升操作可以链状调用。

ap :: (Monad m) => m (a -> b) -> m a -> m b
ap  =  liftM2 id


从函数类型可以看出,他要求将pure function (a -> b)包装到monad中。这样做可以进行链式调用。可是为何通过这样的链式调用就能将多参函数链式提升了呢?这是因为实际上haskell仅支持单参函数。例如(a -> b -> c -> d)这个类型,他表示接受(a, b, c)三个参数,并且返回d类型的函数。这个函数实际上是接受a类型的参数,并且返回一个(b-> c -> d)类型的函数的函数。这有点像是通过接受了参数a来绑定了三个参数中的一个,生成了一个偏特化的函数(partial function)。
ap函数类似是通过提升将这个多参函数的第一个参数提升了,返回用monad包装的偏特化函数(m b)。这个新的被monad包装的函数可以继续传入ap,继续偏特化下一个参数。因此这个操作可以链式提升多参函数的每一个参数,最终完成提升过程。这里ap的名字意思是“apply”,就能清楚他的意义了。
ap实际上通过liftM2 id实现。id是返回本身

id a = a


而liftM2提升两个参数并返回调用f的包装结果,现在f是id

liftM2 :: (Monad m) => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r
liftM2 f m1 m2 =
    m1 >>= \a1 ->
    m2 >>= \a2 ->
    return (f a1 a2)

liftM2 id = 
    m1 >>= \a1 ->
    m2 >>= \a2 ->
    return (a1 a2)   -- id means self


这里有个不太符合直觉的地方,return (a1 a2)就是m (a1 a2), 他怎么就变成ap的m (a -> b) -> m a -> m b了?
这要看传入的参数。ap接受两个参数分别是m (a -> b)和 m a。用这两个参数替换liftM2的a1和a2后

liftM2 id (m (a -> b)) (m a) = 
    m (a -> b) >>= \(a -> b) ->
    m a >>= \a ->
    return ( (a -> b)  a)


经过这个推导,可以清晰地看出,liftM2 id将ap的第一个参数m (a -> b)提升后绑定了第一个参数a,也就是ap的第二个参数m a。并且返回了绑定参数后的偏特化函数b的包装monad, m b。这个绑定的过程可以在最后一句体现出来:return ( ( a -> b ) a)。对(a->b)应用参数a。
从这里可以看出monad是一个极端抽象的概念,讨论他经常会遇到不易理解的地方,只有带上实际使用的参数后才能容易理解。

利用ap函数的代码如下,这里使用`符号包裹一个双参数的函数,将函数当作操作符来使用,从而得到链式调用的代码

liftReview alist =
    MovieReview `liftM` lookup "title" alist
                   `ap` lookup "user" alist
                   `ap` lookup "review" alist

好了,做个小结。我刚学haskell不久,对monad有了一个初步的了解。可以看到monad是一个实践性非常强的抽象,涉及到的lift, functor等概念,如果只是形式上地看他的设计,很难理解设计的意图,就像是一坨抽象废话。但是一旦从实践中多利用这些工具,就能轻松的避免各种各样的代码坏味,得到美观自然和可读性非常强的代码。Haskell这样的语言,只要用心设计好函数和变量名,即使不写注释也能明白代码的意图,并且很难出错。因为他把实现隐藏起来,代码就是直接表达了意图。我认为这是非常有潜力的语言,今后会做进一步的学习和研究,并尽快将其用于实战。

又是命名法

命名法是个我不想再纠结的东西,不过最近又遇上了…
碰巧过完年,脑子锈掉了,居然读不懂自己年前写的代码了。我向来奉行“代码即注释”原则,也就是说…几乎不写注释…完全依靠函数和变量命名的含义来表达代码的意图和思路,除非真有复杂到需要注释的地方,例如莫名其妙的需要多线程同步的地方之外,其余一律不写注释。不过反作用就是,年前那阵子贪玩,没认真好好写代码,导致命名有点糟糕,过了年回来再读就有点绕人了…

一边改那些变量的名字,一边就遇到这个命名法的问题。我还在用匈牙利前缀,整数用n,浮点数用f,字符串用sz。现在需要自己增加几个自己的规则。
iterator类型,我原先用it做前缀,打出的代码看上去非常丑陋,例如:


for(std::vector<Phone>::iterator itPhone = phoneList.begin(), 
    itPhoneEnd = phoneList.end(); itPhone != itPhoneEnd; ++itPhone) {
  //...
}

单纯就觉得这两个字母放在前面不搭,不美…现在我用小写t做前缀,好看多了。


for(std::vector<Phone>::iterator tPhone = phoneList.begin(),
    tPhoneEnd = phoneList.end(); tPhone != tPhoneEnd; ++tPhone) {
  //...
}

当然了,这是古董代码了,有了foreach,这样的代码已经可以进垃圾堆了。不过难免用到iterator的时候俺就该记得用这个t前缀。还有就是项目里的代码我不想霰弹枪一起动,先这样放着比乱改安全很多…

受这个启发,typedef出来的变量类型用大写T前缀,例如


typedef std::vector<Phone> TPhoneList; 
for(TPhoneList::iterator tPhone = phoneList.begin(), 
    tPhoneEnd = phoneList.end(); tPhone != tPhoneEnd; ++tPhone) {
  //...
}

我喜欢typedef出几个项目中常用的容器类型。仅仅到容器类型,而iterator类型直接使用Type::iterator引用,而不进一步typedef。这样恰好保持代码的简洁程度适中,容易理解。

std::string类型用str前缀,而raw string类型(0结尾的字节序列)用sz类型,从而区分两者。这一点通常不重要,但是当你使用printf的时候:


std::string strName = "Peter Pan";
printf("hello %s\n", strName.c_str());

str前缀会提醒你记得用上c_str()方法。事实上这个问题惹恼我好几回了,最倒霉的一回是同事从北京打电话跟我联调,他那边输出的log出现乱码,而我这边丝毫没有,他通过IM给我看输出,告诉我printf打出来的。我不相信我的眼睛,好像就是变戏法。直到调了好久他才突然说,噢!忘记.c_str()了!
当然这仍旧不是好方法。真正问题出在printf不是一个类型安全的函数,编译器无法为你做编译时检查。但是类似printf, sprintf这类函数使用方便,即使最终产品不使用,调试阶段输出log还是会经常使用的。这个时候区分std::string和raw string就变得有意义了。

堆上空间使用p前缀,而栈上空间不使用。这里主要说的是数组。主要目的是当你使用p前缀的变量时候,就会提醒着自己记得思考该让谁delete掉他这个问题了。
例如


char szName[] = "Peter Pan";
char* pszName = new char[10];

我忽然在思考,是不是应该用q前缀来命名那些堆空间的拥有者,而用p前缀来命名那些弱引用。但如果是这样,那么不明拥有者,或者拥有者变更的情况怎么办?再引入一个ps前缀(p_shared_)?也许会弄得太复杂了。也许既然想了这么多,还不如一开始就用智能指针。为什么我不想引入智能指针?我不想引入复杂度。因此如果仅仅为了区区命名而导致复杂度增加,还不如一开始就简单化。所以还是所有指针都用p前缀。到底谁负责,自己好好想清楚。我想,引导读程序的人思考,比用带有暗示意味却可能是错误的命名要好得多。
在使用弱引用时,我经常使用的名字,例如pRead, pWrite, pBegin, pEnd, pCurrent, 等等,这些名字具有强烈的暗示性,说明他们是弱引用,正常人是不会去释放这样名称的变量的,更不会给这样的变量开辟空间。而另一些名字则比较危险,比如pNext, pChild, pParent, pSibling。这些名字的变量,可能你需要去释放他,可能你不需要(例如这是一个树状数组)。这个时候注释是必须的,否则很可能今天写的代码,明天就忽然觉得,不对,这里既然pNext被移动了,那么原来那个东西就应该先释放掉。然后Boom!程序崩溃。还好,现代程序员几乎不需要自己编写类似这样的基础数据结构,直接用酒精久经考验的标准库就行了。而且,就算偶尔碰上了,只要仔细调试通过,以后几乎不会再去改他了(毕竟最多的改动还是在上层嘛)。所以不算什么太大的麻烦。

呜,暂时想记录的就这么多了,给以后想要偷懒的自己看。

圆周率绘图

自从翻译了维基上那篇BBP的文章一直想做这个用圆周率绘图的小程序。今天终于尝试了一下。可惜由于php的性能问题,没法绘出我想要的那种整幅的具有震撼效果的圆周率的外貌图。。。
目前只好用一个小小的24*24的小图先凑合着。其实BBP是个并行算法,要并行起来跑才会快的。但是php的多进程执行实在有点麻烦。所以准备以后有机会再来进一步做下去了。

图片正在加载,请等待

集合论研学初心

最近在网上看了几位大牛的博客,对集合论逐渐产生兴趣。进而去维基上翻了翻,对集合论有了个初步的了解。这里做点笔记。

集合论是一个目标统一全宇宙的超级理论。当然也有可能他统一不了了,但透过集合论,去理解人类逻辑的固有定式,去理解数学如何解释世界,是很有意思的事情。

朴素集合论是很容易理解的事情。首先有元素这个概念。然后元素可以属于集合。两个集合相等完全由其元素一一相等来判定(外延公理)。然后集合的元素也可以是集合,集合可以为空(空集公理)。
这就是高中课本上的集合定义了吧。但这样的定义存在巨大的问题。

例如著名的罗素悖论:设存在集合R, 它包含的元素由对“所有集合”应用的一个函数(谓词)来确定,即“不包含自身的集合”(固有前提,该元素是一个集合)。这个谓词是合理的,因为在”所有集合”这个范围内确实存在不包含自身的集合。那么,将所有这样的集合作为元素,放到这个集合R里,理论上似乎可行。那么我们看这样的集合R有什么特性呢? 他或许不包含自身(R不属于R),如果是这样,那么他就应该包含R(因为R是所有不包含自己的集合嘛)。但是如果他包含了自己,他立刻就不应该包含自己了(包含自己的集合不应该属于R)。

为了阻止这种情况发生,严谨的集合论不得不增加一些公理和概念来回避这个问题。首先,使用一个谓词确定的集合不再确保构成一个集合。他们只是属于一类(内涵公理替代公理)。因此“”这个概念比集合更广泛。如果一个类不是一个集合(例如“不包含自身的所有集合”),那么他就是一个“真类”。
另外,在一个集合上使用一个谓词仍然可以得到所有符合这个谓词的元素的集合。这称之为分类公理
之后引入“正则性公理”来确保集合的合理性。这个公理描述起来有点费力。首先,公理化集合论一般认为所有集合都是集合的集合,不存在集合之外的概念。集合的元素也是集合(有可能是空集,所以这个定义是可以终止的)。然后正则性公理是说,任意非空集合,总存在一个元素,这个元素(同时也是集合)与这个集合的交集为空。这样理解很困难,我们反过来理解。任意非空集合,不可能发生这种情况:他的所有元素都与其相交。这仍然很难想象,我们举个例子来观察这样的集合的特性。
假设R符合这个条件,假设他包含一个元素。则 R = {A}
这里A和R相交非空,则A交R = B
B是A和R的交集,则B是R的子集。同时B非空。则B只能是{A}。也就是说,B = R。
所以A交R = B。A = {A, …}
而R = {A}, 所以R = {{A, …}} = {{{A, …}, …}} = {{{{A, …}, …}, …}}
这样的A是无穷递归定义的。或者说,在有限时间内无法写出R的定义。这和无穷集合并不相同。无穷集合只是在有限时间内无法写出这个集合中的元素而已。如果一个集合无法被定义,我们应该认为他就是不存在的吧。
R包含更多元素的情况比较复杂,不过归结到最后都是如这样形式的无穷递归。可以说这个公理防止了这样的不良定义的集合出现。所以“禁止自包含”就是正则公理的内涵之一。

以上几个公理定义了集合的内涵和外延,以及一个操作(分类)。接下来还需定义集合的并(并集公理)这个操作。这个操作的定义与朴素集合论中的定义略有不同。
这个定义的形式描述有点绕,这里形象的说明就是:一个形如R = {{A},{B},{C}, …}的集合,他的并U R = {A, B, C, …}。
所以,{A, B, C}U{D} = U{{A, B, C},{D}} = {A, B, C, D}
相信读到这里很多lisp玩家已经感到似曾相识了。确实函数式语言、图灵机等等计算机科学基本概念都可以说是自集合论派生出来。这也是我会忽然跳这个大坑的原因。

定义了并之后,集合操作基本定义完全。至于说交集这个定义呢,因为存在分类公理,交集其实是分类公理使用“属于某个集合”这个谓词的一种特化形式。因此无需使用公理定义出来。
还有几个公理,我这里配合描述集合论构造自然数的定义来描述。因为这一段似乎是集合论中最容易懂的一部分了

这里直接给出定义的形式,他比描述还容易懂。之后根据这个形式中出现的几个特征,引出几个定义。

0 = {} (空集)
1 = {0} = { {} }
2 = {0,1} = { {}, { {} } }
3 = {0,1,2} = {{}, { {} }, { {}, { {} } }}
4 = {0,1,2,3} = { {}, { {} }, { {}, { {} } }, {{}, { {} }, { {}, { {} } }} }

由于自然数是无穷的,必须使用归纳法定义全体自然数。前面集合的并集的定义是一个铺垫:
首先 0 = {} 是自然数。
然后 假设x是自然数,则x的下一个自然数x’ = x U {x}

由是自然推出了元素的“后继”这个概念。x’是x的后继,则x’ = x U {x}。并依据后继这个概念定义归纳法(无穷公理):
存在集合A,首先,空集属于A,并且对于任意的元素x属于A,则x的后继x’ = x U {x}也属于A。
这不破坏正则公理,因为空集属于A。因此A中存在一个元素,{},他与A的交集是空。
这并不是文字游戏。要求空集包含于A是非常重要的。这相当于是数学归纳法中的初始条件。否则归纳法无法成立。

此外还引出了集合中元素的顺序问题。称x’是x的后继,就是说,x和x’之间存在顺序关系。并且这个顺序关系可以传导。也就是说,x1是x0的后继,x2是x1的后继,则x0和x2也存在x0在前, x2在后这样的关系。 通过这个关系,可以得出集合的序的概念。

首先定义良序集合。所谓良序集合,通俗地说,需要符合两个条件。其一,首先给定一个判定关系的运算符,任意举出这个集合中的两个元素,在这个运算符上能够判定顺序关系(因此这是一个线性的顺序关系,每个元素如果有,都仅有一个后继和一个前驱);其二,任意给定这个集合的子集,能够找出该子集的最小元素(无需保证最大元素)。符合这个条件的集合和这个关系一起就称作良序集。因此自然数在<=这个关系上是良序的。但是整数在<=这个关系上就不是良序。因为不存在这个集合的最小元素。但是如果用其他的顺序关系运算,仍然可以给出一个良序的整数集。例如0, -1, -2, ..., 1, 2, ... 这个顺序,0最小,然后负数比整数小,然后绝对值小的数更小,则得到一个良序集。为何一定要确保最小值,其实就是为了使归纳法成立。后续的大量论证将会建立在良序集的归纳法之上(超限归纳法)。

好了,对于良序集,既然后继是唯一确定的,就可以不停地向后列举下一个后继。如果这个集合是有限集,则最后一个后继的序号(序数)就是一个自然数。如果是可数无穷集合,则这个最大的序数无法在有限时间内获取到。我们设这个数为ω (自然数的序数)。仍然存在序数比ω还大的可数无限集合。例如整数,假如按照上述排序方式,则其序数相当于是ω+ω。又比如,自然数如果采取另一种排序方式0, 3, 6, 9, …, 1, 4, 7, …, 2, 5, 8, …则自然数的序数是ω+ω+ω。我们看到,序作为衡量集合大小的指标有一个不足,就是序是由一个人为确定的关系运算符来确定的。关系不同,就有可能改变序大小。因此还需要更通用的,仅与集合本身相关的指标来衡量集合的大小。

接下来应该引入基数的概念。但由于这一块我还没有完全理解,所以暂且写到这里了。

后续会写一篇文章记录读到目前为止我的各种疑问。作为思考题,推动自己接下来继续去学习~
引用:
维基百科:公理化集合论
刘未鹏:永恒的金色对角线
Matrix67:对角线方法之后的故事

复合功能就是代码坏味

这句话要反复重复给自己听。
今天在看java的官方文档的时候看到了这么一个例子:


List suits = ...;
List ranks = ...;
List sortedDeck = new ArrayList();

// BROKEN - throws NoSuchElementException!
for (Iterator i = suits.iterator(); i.hasNext(); )
    for (Iterator j = ranks.iterator(); j.hasNext(); )
        sortedDeck.add(new Card(i.next(), j.next()));

文档中举这个例子是为了推广foreach语句的使用。但在我看来,之所以容易产生这样的错误,原因是java的iterator的方法不够内聚。

为什么要用iterator.next()返回iterator指向的值?

这让我想起了C++的STL中一系列关于堆栈的操作。获取栈顶的方法是back()或front(),出栈的方法是pop_front()或pop_back()。是这样做,而不是令pop_back()直接返回栈顶值同时弹出。这就保证了函数方法的绝对内聚。从而避免了如同前例那样的潜在错误。

永远保证自己的函数功能单一,没有副作用。不要用小技巧去让一个函数多功能化。有时候潜在的错误远远不是一眼能看得出来的。

论资源抢占的系统设计

怎么会想到这个问题,出发点是来自提出一个更通用的多线程架构的问题。其实这个问题我现在讨论有点过早,因为至今还没仔细研究过go和erlang,不了解多线程编程的现状。但总归在这个blog的小小圈子里,随便抒发几句应该是问题不大。

其实我的想法是很简单的,就是想增加一个 “任务” 的概念。这个必然很多语言很多系统已经提供了,我为什么还要提。我主要是感觉,现在的多线程编程,还有网络编程,每个程序都自己定义一套多线程管理、进程池、线程池、网络连接池、数据库连接池等等概念。虽然有库函数,不必每次从头造轮子,但每个程序一份几乎完全雷同的管理机制,绝对是有问题的。

况且,现在的操作系统,除了CPU占用这一点实现了“抢占”之外,其他的系统资源仍然是依赖程序间的谦让协作的。我前几天发的帖子,就是因为adb的一个bug,导致占用了过多的系统连接,导致其他程序无法使用网络。同样的例子,臭名昭著的迅雷,因为过量占用连接数导致你根本无法上网。虽然最近迅雷提供了种种功能,他会检测你有没有使用浏览器,他会检测某些著名的端口(对应各大著名网游),确定你是不是在打游戏,等等,来谦让地给你腾出一些网络带宽。但问题是,这样看来,是不是太委屈迅雷大哥了。虽然霸占过多网络资源是他的不对,但是研究到底应该使用多少资源,并不是一个应用程序能够做到的事情(迅雷也只是经验性的猜测,你自己写的网游、小众的网络服务,他一定是无法猜测到的)。

参考CPU抢占的系统设计,其实资源抢占完全也是可以做到的。还可以参考虚拟内存的方式,给每个应用程序足够巨大的虚拟资源空间,并使用工作集、缺页调度等机制,调度所有的资源。这样擅自开辟了大量网络连接的服务(如adb),也不会导致系统无法打开更多的网络连接,霸占了大量资源的迅雷,也无法阻止其他程序连接网络(因为有工作集的限制)。操作系统可以根据资源使用的活跃程度等因素调度资源,例如当其他程序都不使用网络时,就可以让例如迅雷这样开辟了过多连接的程序拥有更大的工作集,保证系统资源的最大化利用。

好吧,话说到这里已经扯开去了。前面提到的多线程管理的机制,其实跟这个资源抢占的机制没有任何关系。只是因为思路飘忽扯到这里来了。说回那个多线程管理的问题,也是一样的,我希望提供一种机制说明任务的并发逻辑(可能要使用新的语言,至少C语言无法表达并发逻辑这种概念),然后要使用什么样的并发度,这个决定让系统来做。因为系统有多少内存资源,有多少CPU资源,这些事情本不该是应用程序该知道、该负责的事情。尤其是,跟本身的应用程序一起,系统里还有哪些其他的程序在跑,他们对内存和CPU的消耗如何,更加不是应用程序的职责范围能知道的。但是决定一个任务的并发度,必须从系统级思考问题。因此把并发逻辑列清楚之后,让系统去决策如何并发,才是最良好的策略。我不知道go语言或者erlang这些传说有着高度并发支持的语言是否已经做到这样,如果是这样的话,我就再次后知后觉了;不过作为一个思考练习,也是挺好的~(热烈欢迎评论拍砖=)

好吧,把资源抢占和这个多线程管理机制综合到一起,就变成了更系统更完善的系统管理机制。因为并发度不仅要考虑内存CPU,也要考虑硬盘、网络、设备等等等等。把所有的资源使用频率整合统筹调度,就能得到最优化的系统,当然这个多维度的最优问题,也将成为一个巨大的算法难点。也正是因为想到这里,我才感到格外兴奋。

说实话,即使用十年时间去开发出来这样一个系统也不会太迟。但要做到一点,就是对市场现有产品的兼容性。如果能运行java虚拟机,或者能兼容linux系统调用(也就是说新系统在linux的基础上修改得到,说实话我觉得这是一个靠谱的打算),或者至少旧有的程序代码通过编译能够运行在新的系统上,并且仍能体现系统的优越性,那么新东西做出来就不会没有市场没有价值。

不过我真的要跳这么个大坑么。。还是仅仅满足于YY然后坐看系统更替风云变幻?说实话,自己感觉暂时能力有限不足以完成伟任呢,或者说过于浮躁也有可能。暂时先记录一下吧,也许明天就会自否命题了呢囧|||

有时间先去研究下go和erlang哈哈:)

PS. 还有一个关于通用缓冲区设计的思考练习,目前正在开发和实验中,有结果了一定写bo!

linux内核学习 – C风格的面向对象

linux内核大量使用面向对象的编码风格。然而linux内核是完全使用C写就。学习他们如何使用C模拟面向对象机制很有意思。这种做法很可能被人贬为扯淡,但是的确使用C模拟面向对象机制,使得程序员对类型构造/析构,拷贝/赋值等操作有了绝对的控制权,可以提高对效率的嗅觉,减少错误,同时也避免了对C++编译器各种不同类/对象实现机制的依赖。

类的多态特征是linux内核经常用到的。例如在驱动代码中常常使用函数指针来定义一组设备操作函数,从而模拟了多态的特点。


struct file_operations scull_fops = {
    .owner = THIS_MODULE,
    .llseek = scull_llseek,
    .read = scull_read,
    .write = scull_write,
    .ioctl = scull_ioctl,
    .open = scull_open,
    .release = scull_release,
};

上面的例子是Linux Device Driver中抄来的示例代码。很好地展示了file operation结构体如何使用这种机制来定义一组文件操作的方式。用这种方式,Linux很好地贯彻了所有的设备都是文件这种概念。不同的设备可以有不同的处理函数,但使用相同的接口,这样就把底层设备的差异在文件系统这一层隔离开来了。

Linux内核中也经常用到类的继承关系。这种关系使用C也很容易模拟,就是使用结构体嵌套。例如


struct scull_dev {
     struct scull_qset *data;   
     int quantum;               
     int qset;                  
     unsigned long size;    
     unsigned int access_key;  
     struct semaphore sem;     
     struct cdev cdev;      //内嵌linux内核定义的cdev结构体
};

这个例子同样来自LDD。注意在自定义的cdev字符设备结构体中包含了struct cdev cdev成员。这个成员同样是一个结构体,由内核定义,是字符设备描述符。使用这种方式,可以一定程度模拟C++的继承机制,当然有他的局限,例如他不能如同在C++中一样直接引用cdev的成员,而必须通过scull_dev.cdev来引用。

另一方面,这种方式也无法通过“基类”,即cdev的指针,访问“子类”,即scull_dev的成员。精彩的部分来了,linux通过一组宏,巧妙的实现了这一点。在文件处理的函数中,入参会给入inode指针,从这个指针可获得其cdev成员。如何从这个cdev成员获取包含它的“子类”对象,scull_dev的指针呢?

container_of(ptr, type, member)

使用这个宏,container_of(inode->i_cdev, struct scull_dev, cdev)就可获得包含cdev的scull_dev的地址。这个巧妙的宏是如何实现的呢?

#define container_of(ptr, type, member) ({ \
                const typeof( ((type *)0)->member ) *__mptr = (ptr); 
                (type *)( (char *)__mptr - offsetof(type,member) );})

这个宏首先定义一个指向结构体成员的指针__mptr = (ptr),他的类型是const typeof(...)。这里用到了C语言一个较新的关键字typeof,可以在编译期获得变量的类型。而这个类型是((type*)0)->member,这里type和member分别是宏传入的参数。这一行代码就比较清晰了。得到这个__mptr之后,将他向回移动一个offset,(char*)__mprt - offsetof(...),而这个offset恰好为member相对于type的偏移量,offsetof(type,member),则移动完毕__mptr就指向type类型的起始地址了,只需将其转换为type*类型就可以了,(type*)(...)

好了,这个宏已经看懂,神奇的地方就出在这个offsetof宏了,他是如何计算成员相对于结构体的偏移量呢?这里linux内核hacker们用了一个小小trick。

#define offsetof(s, m)   (size_t)&(((s *)0)->m)

是的,代码非常简单。其思想是,假如结构体处于0地址,获取其成员的地址。这个地址就是成员相对于结构体初始地址的偏移量了。没错0地址是不能运行时访问的,但这句代码只在编译期使用了0地址,因此是合法的。当然其实使用成员指针和结构体指针相减也可做到,但用这种方式可以减少一次运算,确保了这个宏可以在编译期求出结果。可谓是精益求精。

我说错了。即使使用减法也可以做到编译期求值,因为结构体和成员指针地址都是可以编译期得到的,常量数值计算应该可以做到编译期优化,计算完成。这种做法应该是
&((type*)0)->member - ((type*)0)
这样的代码的一个直觉性的优化,减0的话,何必还要减呢。事实上两句代码的运行时间是一样的,但这样做可以减轻编译时间。
在container_of宏中,也有一句减法计算。这个计算引用了运行时求值的__mptr,所以无法做到编译期求值。

类似这种用法,在linux内核中经常出现。深深佩服大牛们的创造力,并且深深的意识到了即使是C语言也是学无止境的。

协程的C实现

今天正好跟ownwaterloo聊到协程,于是查了查资料,顺便写个博客记录一下吧。

我主要参考的是这篇资料http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html,是Simon Tatham提出的一个协程的C实现,非常有意思。

协程的思想主要是为了解决多个任务如何分享CPU这个问题的。线程在很多协作问题上处理的不好,而且需要锁机制,导致运行缓慢,不易理解,容易出错。协程的思想是,一系列互相依赖的协程间依次使用CPU,每次只有一个协程工作,而其他协程处于休眠状态。与线程不同,协程是自己主动让出CPU,并交付他期望的下一个协程运行,而不是在任何时候都有可能被系统调度打断。因此协程的使用更加清晰易懂,并且多数情况下不需要锁机制(或者说他本身就是一个全局锁)。

Simon的举例是一个生产者消费者例子。传统的程序可能是生产者一个循环不断产生字符,之后退出。而消费者一个循环不断读取字符,并处理之。使用时或许会用一个管道,将生产者的输出重定向到消费者的输入。从而使两者协作。

Simon提出,如何使这样的简单任务无需通过管道这类操作系统相关的重型机制,就能完成。他提出,生产者或者消费者之间,有一方需要改变自己的工作模式。不再是在循环中不断处理任务,而是一次只处理一个字符然后立刻返回。而另一方依旧保持原状,只需在原本输出到或读取自标准IO的地方修改为调用对方的那个函数就可以了。

但这种写法难以维护。他提出了协程的概念,并期待写出类似这样的代码:

int function(void) {
    int i;
    for (i = 0; i < 10; i++)
        return i;   /* won't work, but wouldn't it be nice */
}

在这里return语句并不是终止函数,而是将函数转入睡眠的状态,并将CPU交付给另一个函数执行。例如生产者写入一个字符后,调用类似的return语句,交付消费者处理这个字符。稍后当消费者处理完并调用return语句后,能重新激活生产者协程,并继续这个for循环。

如何在C语言中实现这样的功能而不需使用汇编代码去hack堆栈和寄存器呢?他给出的最初的实现是使用goto语句。

int function(void) {
    static int i, state = 0;
    switch (state) {
        case 0: goto LABEL0;
        case 1: goto LABEL1;
    }
    LABEL0: /* start of function */
    for (i = 0; i < 10; i++) {
        state = 1; /* so we will come back to LABEL1 */
        return i;
        LABEL1:; /* resume control straight after the return */
    }
}

巧妙的使用静态变量存储函数状态,并使用goto语句来继续for循环。但这种写法不够优美,于是又引入了Duff’s device。

switch (count % 8) {
        case 0:        do {  *to = *from++;
        case 7:              *to = *from++;
        case 6:              *to = *from++;
        case 5:              *to = *from++;
        case 4:              *to = *from++;
        case 3:              *to = *from++;
        case 2:              *to = *from++;
        case 1:              *to = *from++;
                       } while ((count -= 8) > 0);
    }

使用这种trick来将switch-case语句作为循环中的跳转。这就避免了goto-label语句需要同时维护goto和label两处代码的麻烦。于是前面的代码可以变成这个样子。

int function(void) {
    static int i, state = 0;
    switch (state) {
        case 0: /* start of function */
        for (i = 0; i < 10; i++) {
            state = 1; /* so we will come back to "case 1" */
            return i;
            case 1:; /* resume control straight after the return */
        }
    }
}

他的文章后面还有一些内容,例如如何使用宏包装这套机制。如何使用__LINE__宏避免state被赋予相同的数值。如何避免多线程调用下干扰静态变量等等。我这里就不赘述了,大家有兴趣可参考原文。
总之读此文的两个收获一个是认识协程,一个是学习到了一种诡谲的C语言用法。非常开心。

自动编程 – 语言的级别

先说一个悖论吧。
程序员的任务是让机器帮助人类做工作。
程序员的唯一工作就是开发代码。
程序员喜欢手动hack开发代码。

这就是我今天想要讨论的。

今天读到了阮一峰翻译的为什么Lisp语言如此先进?感触很深。原文Revenge of the Nerds

正如我开头说明的一样,之所以软件工程这个领域这么奇怪,有什么人月神话;有各种其他工程都完全不可能遇见的奇怪问题;即使开发得非常熟悉的类型的项目,再去开发仍然无法准确估计工期和成本;最讨厌的代码就是别人的代码,要知道别的工程领域流水线都是最重要的提高效率的方案,也就是在其他人做了某个步骤的产品基础之上在做一个步骤;即使软件工程理论已经存在和发展了几十年,软件项目的可测性和可控性都完全没有提高;被业界高呼了二十年的面向对象被骂为骗局;等等等等。。。
之所以这一切问题存在,是因为软件工程根本就是一个悖论。当别的工程领域早就摆脱了手工作坊生产,早就工业化自动化了的时候,软件工程还在手动hack代码。就像摆着高大的吊车和推土机不用,软件工程师们想要徒手建造长城,一次又一次的非要从地基开始重新建起。

这里再附上之前在代码交叉拷贝悖论中同ownwaterloo的讨论吧,在读到上述那篇文章之前,其实我们已经走到某一个角落了,其实已经离这个真理只差一步之遥了。(好吧。。虽然我说的也不见得就是啥“真理”啦。。)

OwnWaterloo at 10/11/2010 18:12
不知道是不是想要这样的效果? 伪代码大致是这样:
for image in [ thumb, caption, buttom /* 这里还可以更多 */ ] :
image.offset(height)
image.rotation(270)
hawk at 10/11/2010 23:58
呜!这段代码很漂亮!
可惜c++效仿起来有难度。。
OwnWaterloo at 10/12/2010 10:36
其实那代码是一个暗示……
做GUI这种效率不吃紧的东西, 能不用C++, 就别用C++……
如果我早点学python, 并且发现OpenCV其实有python的绑定……
不知道可以节省多少时间…… 陪gf玩玩什么的……
hawk at 10/12/2010 16:25
那时候因为是在winCE上做widget,没有.NET,所以只能用C++了。。
现在做界面都尽可能用网页或者.NET了。。。
OwnWaterloo at 10/13/2010 12:37
.net也行, 它至少有元数据, 可以”按名字调用”。
C++在运行前完成”名字到地址的转换”, 运行时就没函数名了。
其实按今天的内存和磁盘容量来说, 元数据并不大。
但需要它的时候, 真离不开它……
貌似C++0x也不打算加入……
hawk at 10/14/2010 23:27
是的,javascript那种字符串直接当代码调用的功能强大得一塌糊涂!!

是的,.net的按名字调用,甚至javascript的自解释。为什么他们就那么强大呢?到lisp这里就找到祖宗了。可能就像文章中说的“格林斯潘第十定律”一样,在你追求代码自动化的过程中,你最终就会找到祖宗那里去了。

当然了,我相信lisp肯定也不是最终的完美。但是它是一个指引,指导我们什么是我们想要的。那就是自动化的编程。以前见过貌似是《程序员修炼之道》里面提到过的unix哲学理念,其中有一条是被人大为忽视的,就是让程序自动生成代码。刚在网上翻了一下,维基上的说法是“六:尽可能地榨取软件的全部价值”[引用]。这点是关键吧。软件工程应该像其他的工程一样,尽可能工业化、自动化,早日脱离3、5人小团队的作坊式生产(当然这样说很可能导致一批人失业,不过那是十年或者二十年后的事情了)。当然手工生产会留下来,做那些最精细,最高难,计算机无法自动完成的事情。另外就是确定需求分析设计这部分,这部分是机器无法自动化的。
当然,软件行业变成当今的现状是很自然的。程序员都是聪明而高傲的。他们喜欢证明自己更优秀。他们喜欢hack。他们瞧不起催进度的老板和搞需求的公关。并且程序究竟该怎么开发这点烂事是企业里的管理人员无法操心的。他们看不见那些无形的重型机械被程序员抛开,也看不见程序员其实是在手工修建长城。但是程序员应该自己反省。是的,一次两次骗过肥头胖脑的老板可能蛮有趣的,但是总是手动hack程序员就偏离了自己职业的宗旨-让机器帮助人。

我一直以来都是c\c++的忠实拥趸,藐视高级语言,喜欢重度hack,喜欢重头发明轮子。但是最近的反思,加上这次看到的文章,让我大大醒悟了。高级语言的真正高级之处,就是他强大的自动生成代码的能力啊!
作为一个高傲的程序员,低头使用别人的代码生成器总有“食嗟来之食”的感觉(当然这是不对的。。当真正要解决问题的时候我还是会用合适的工具的!lisp当然也在学,python和perl也在学,也知道用网页和.net来做一些事情了,也体会到.net和js的强大了)。那就自己去发掘,自己去创造。这话说得貌似又变成重新发明轮子了。当然工程实践中不会这么去做的。但是作为理论学习的方向,这方面应该是重点。我研究生专业学的是嵌入式方向,学的是最底层最hack的东西。学的是怎么把c当成汇编来用,怎么把编程看成是操作实际硬件。假如沉迷于此的话,我的软件观就彻底歪掉了。这些东西都算不上是软件。只不过是硬件接口罢了。软件的宗旨是正好相反的。软件的任务就是形而上学,就是纯粹的逻辑和理学的完美。只有结合了天堂的圣洁和地域的邪恶,才能创造出人类世界。

另外一点就是借着AIIDE的契机,学习了机器学习和人工智能的东西。这是软件工程未来的一个新的方向。就是用人工智能来开发代码。是的,不仅仅是用人工智能来解决问题,还要让人工智能来开发程序,让人工智能来开发人工智能。那其实是人工智能提出的时候最早的目标。可惜大多数学习这个领域的人都专注于用它做其他的事情了。遗传编程,一开始就是为了让程序自动创造程序而研究出来的,可惜现在都在做其他的解决方案。
可能说到人工智能产生人工智能,有些人就要想到黑客帝国了。一方面作为理论研究不应该考虑太多伦理问题,伦理是随着理论进步的。另一方面人工智能不等于生命,再高级也不等于生命。关于他的纯哲学讨论我放到下一篇博客去讲吧。估计这里的人多数不会有兴趣看的。

总之今天就像醍醐灌顶了一样一下子有了很多新想法。可惜我的问题在于想法太多动手太少。。。要努力实践!

lisp学习笔记

2013年重读这篇笔记,错误很多,对定义的理解有很多混淆;作为自己学习和成长的记录不再将其中的错误一一纠正了

刚刚开始学lisp,还只是开始熟悉他的语法。但是学lisp确实是开阔眼界的一个好办法,能从更高的角度来看程序语言。

至今为止任何类型的程序语言其实都是图灵机的一个实现。比如说经典的x86 CPU吧,他就是一个图灵机。这个问题我其实还是想了好久才想出来的。可能是我太愚钝了吧。。图灵机的一种描述是这样的,存在一个两边都无穷长的纸带,一个含有一系列状态和命令的指针。这个指针一次执行一个命令,或者向前或向后移动一格,或者在纸带上读取或写入一个符号,命令有可能改变指针的状态。而读取到的符号会根据指针的当前状态产生一个新的指令。循环往复。直至到达某个特定的状态(终态)停止下来。

一开始我觉得CPU的寄存器表示状态。可这样的话,寄存器的值是不确定的,于是似乎不能模拟确定有限自动机。静下心来想想,其实应该认为所有寄存器的一种取值组合就是一个状态,所以假如有m个寄存器,每个寄存器的取值数量是ni,则总的状态数量就是i从1取到m, 将所有的ni相乘。(不能打公式郁闷。。)然后应该认为汇编代码就是那个带子上的符号。这样比如

ADD a, a, b ;a=a+b

这样的一条指令,应该看作是一个符号(所有可能的汇编指令应该是有限的,可以认为每一个都给编了唯一确定的符号)。这个符号对应CPU的不同状态,(例如这里的a和b的所有不同状态组合),可以看作每个状态都有接受了这个符号之后指向一个新的状态的箭头。使得寄存器状态改变。比如对于a=1,b=3这组状态(1, 3),这个箭头就应该指向(4, 3),当然这里没有考虑溢出位啦。同时又存在一些其他的操作,例如处理内存或中断的操作,可以看作是向纸带上的特定位置写入字符(由于内存和中断的数量也是有限的,所以可以给他们的每一个地址对应纸带上的一个位置)。

那么lisp呢,lisp是怎样实现图灵机的呢?

根据lisp1的自解释逻辑,可以认为lisp是一个不断扫描输入纸带的一个指针。他的状态则由输入中给定的“环境”决定。可以认为lisp仅有函数定义和函数调用两种语法。对于函数定义,其实是增加了新的状态组,把它的所有形参的所有取值组合看作是一组状态加入到自动机中。而函数调用,就是将实参值带入形参,计算函数结果的过程,对应于状态接受一个输入指向另一个状态的一个箭头,即在此实参情况下,如何应该进入什么样的下一个状态(次态)。

不过很有趣的是,鉴于lisp的递归定义,可以认为他的状态机也是递归的。在运行的最初,该状态机仅有函数定义及函数调用的最基本语法。指针扫描纸带(程序源代码)一遍,生成了最外层的函数定义,这是状态机为这些新函数增加新的状态,之后指针移动到该函数调用的起始位置,第二遍扫描源码,生成新一层次的函数定义,向状态机添加新的状态,直至最终所有的函数定义全部生成结束,递归到最底层,所有的实参都被计算成为原子,再依次递回,直至最上层。

从这个角度看lisp的有趣之处在于他用自己的规则定义自己,不断充实自己。不过也因为这种灵活性,使得用c实现一个高效的lisp编译器变得有些困难。一开始我在考虑的是lisp只有递归没有循环,确实不符合c语言的常规思路。不过转念一想,尾递归优化成循环其实倒反而是一件轻松的事情,只需要将形参改成自变量,把递归调用的那一句改成goto到函数开头就可以了。然后再改成while循环即可。麻烦就麻烦在这个函数的动态声明。有没有可能一次扫描完lisp文本之后就确定全部的函数定义呢?给定两个附加条件,一是所有的函数定义必须在他的调用的同一级或外层(注意这里指的是定义这个函数的外层,而不是调用这个函数的外层),二是函数定义必须在函数调用的前面。这样就可以逐级求值而避免递归了(相当于首递归)。当然这里避免的仅仅是(相当于)编译期的递归,在(相当于)运行期的递归仍然是避免不了的(也不可能避免)。当然对于lisp而言,编译和运行是交叉进行的,也没法分得这么仔细啦。(所以才说是解释型语言嘛。。汗)当然话说回来,将lisp先编译成机器码再运行也是可能的。只是编译时间会比较长而已,而且对于变量类型可能要做一些处理。(最简单的想法是用链表,不管是树也好,字符串也好,数字也好,都可以用链式结构存,以适应lisp的list结构。)

好吧,先做这些记录,下次有了感想再写了。

呼,因为结束实习,搬家,赶毕设,一下子好久没有写博了呢。。今天终于补了一篇。。证明我这段时间也没有荒废时间啊。。以后还是要经常写博客自勉啊。。回头看了一下大半夜的逻辑有点混乱估计有写错的地方。。不过天色晚了没心情挑错了,改天再回来改吧。。