Posts tagged 语言理论

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 […]

又是命名法

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

圆周率绘图

自从翻译了维基上那篇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, …}。 […]

复合功能就是代码坏味

这句话要反复重复给自己听。 今天在看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 […]

协程的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; } […]

自动编程 – 语言的级别

先说一个悖论吧。 程序员的任务是让机器帮助人类做工作。 程序员的唯一工作就是开发代码。 程序员喜欢手动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++了。。 […]

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