Pl

对长期纠结的PL和CC相关内容做一个小结 2013

published on

回顾一下在编程语言和编译原理方面的各种纠结,没有什么记录,凭记忆写。

我从高中毕业开始使用C++,到现在挺多年了。语法是靠高中看数据结构的书看会的,后来到了大学里面喜欢泡图书馆,大一时靠读了不少C++的经典奠定的基础,像是Effective C++,Exceptional C++等系列,有蹭着和学软件工程的同学讨论项目,自己翻一翻设计模式什么的书,学会了一点怎么用C++写项目,算是我第一个用着很熟悉的语言了(之前用过VB Pascal,均仅限于学习写所要的程序的必要的知识部分)。

在大二的样子,出于学习算法的目的也要考虑编译方面的算法,于是在图书馆了翻了不少相关的书,诸如传说中的三件套:龙书,虎书,鲸书,当然还有一些其他的玩意。比较喜欢的是虎书,所以借过好几次,慢慢的读。看的是虎书的C语言版,不过这就是按照ML语言版改写过来的,对象都是申请了之后不考虑释放的,里面实现的语言的语法也是参考者ML来的。我从那里面学到了不少东西,而且第一次注意到写程序还可以使用immutable的数据结构。也喜欢上了ML的语法。

再后来因为自己写游戏的原因,学习了lua语言,反反复复的用,把大部分特性都搞的差不多明白了,后来干脆把源码也全部看了一遍。lua这条线的话,后来发现了LuaJit这样一个玩意,遂对Jit产生了兴趣,在网上找了一些paper和code看了一下,之后又读了intel和amd x86-64芯片的手册,可是最后还是没有自己去写一个。

因为经常和lua拿来放在一起讨论的Google所做的JavaScript引擎v8,所以其相应的代码也拖下来读了一些,结果学了不少C/C++中的宏的使用技巧。

另外在学校的图书馆里找到了一本转本讲垃圾收集的书,里面对各种方法的各种讨论让我大开眼界,每一种现在用的收集策略都讨论了各种优化方法。我才意识到,原来这东西有这么多人研究啊。后来在LuaJit的Wiki上也发现一篇讲gc的内容,看起来还在等人赞助他加进去。

之后因为看两大名作SICP和CSAPP的缘故,接触到了Scheme,当然这不是最早接触的Lisp,最开始是高中的时候开始学着用Emacs,那是就摸索着写了一点Emacs Lisp。所以用Scheme的时候没有什么语法不适应的障碍,反而看SICP学了不少函数式编程的知识,当时触动特别的大,因为是第一次直接的接触到函数式编程相关的内容。

后面因为黑客与画家的原因看过一点Common Lisp,实在是不喜欢就弃了。所以Lisp这条路线基本一直是喜欢scheme的。scheme这条线下来,先是发现了有continuation和cps这样的东西,但是靠网上依稀的资料不是很明白,直到后面看了EOPL和PLAI,自己写解释器,慢慢就搞明白了。看到Y-combinator,然后自己推导过后,也学会了。后面也专门看过用Scheme的实际项目:Lilypond,可惜量太大,实在没耐心分析到最后。宏是最后在Cousera上选了一门Programming Language的课,听讲义学的。我个人绝对是听觉型的学习者,特别喜欢听老师讲,但老师太难找了,还是不得不努力的看了不少书。

Scheme这边发展后后面,对于怎么实现函数式语言的优化编译器又产生了性质,还找了一些书和paper,讲怎么写函数式语言的编译器,或者诸如对于动态语言,怎么通过尽量的静态分析,可以消除大部分运行时的类型检查。

还有一条线是考虑学一点实用的语言,于是看了Python和Ruby,Python没怎么看书,就随便看看tutor,看看别人的程序,然后慢慢居然也用熟了,Ruby正儿八经看了影印版的The Ruby Programming Language,最后还是没记住多少,学语言果然还是靠多写。再想想看个速度快点的,于是学了Go,看了tutor,最后还是没怎么用。一般还是C++/Python使用最多。

再有一条线就是几度尝试Haskell,尝试着看了一些资料,Tutor或者书。觉得实在是一门麻烦的语言,平时用来解决一般的问题都要采用这样的思路没必要,故没能更近一步。

然后再回到C++吧,后来网上看过不少C++11的资料,然后看到了公开课cppgm,可惜知道的比较晚,人家已经开始了,看到其使用的材料的是C++的标准。想到自己从没看过C++的标准,于是网上搞了一份,不过一直没什么机会想起来把他看下去。

最后是最近在Coursera上搞了一门PL的课,认真学了一点ML的语法,复习了scheme/Racket,学会了在scheme中怎么写宏,然后又复习了一点ruby的语法,发现忘了不少。期间还有纠结在要不要去学scala,要不要自己再写一个新语言的编译器,啊这些恐怕要留待明年继续纠结了。

写完了之后总觉得还漏了些什么,诸如LLVM之类的,反正估计永远都难以写完整了,先这样好了。

Read More...

书籍推荐 《Programming Languages: Application and Interpretation》

published on

正好赶上劳动节要放假了,在网上转悠的时候发现这本书。用来讲述编程语言特性的一门课程。这本书可以在线阅读,用plai作为关键词google一下就可以找到。

按照一般的作风,这里应该放一张封面的靓照,我就省去了。

今天简单的看了一下,非常喜欢,很快看到了第15章。书中的代码都是用的scheme实现的,不过为了教学目的,对scheme做了扩展,形成了专门为这个教学使用的语言。如果没有scheme经验的同学可以先看看《SICP》打打底。

书中的主要内容就是介绍语言的各种特性。方法就是通过编写具有这各种特性的语言的解释器。了解多种语言的特性可以帮助你理解在各种语言中,那些设计为什么要做成那样,哪些地方是好的设计,哪些地方实际上应该可以更合理。

说明: 后面关于书的内容的介绍是基于07版的,其网站上有2007版和 2012版两个版本的下载,而我是拿着07版在看,预计看完之后快速过一下新版的修改的内容完事了。

最开始,先是做了一些基本的介绍,说我们研究的不是具体的语法,而是语义。也就是区分不同语言的关键不在于看起来写成什么样,而是其具体有什么作用。所以用lisp有一个巨大的方便之处就在于不用在语法这件事情上纠结了,可以方便的得到ast,然后在上面做工作。

第二部分先实现了一个具有基本功能的语言,包括基本的计算和函数调用。同时会介绍static scopedynamic scope的区别。

第三部分讲惰性求值,举了两个例子,其一是Haskell,这个是很标准的惰性求值的语言。不多说,另一个是unix的管道的设计。管道的作用是将一个程序的输出作为另一个程序的输入。而输出会造成阻塞,只有另一个程序将这写输入了之后,前一个程序才会继续运算,所以这个设计就和惰性求值有着一样的特性:可以处理无限。例子比如命令 yes | head -n 5 就会输出5个y,而仅仅是yes的话,就会产生无穷的y,可以你要多少给多少。比如用在yes | rm * 这样的命令中就会很方便。

这里面提到unix的一个设计的哲学就是为10个元素提供10种工具,不如为1种元素提供100种工具,然后将这些工具组合起来就得到非常强大的力量。在unix中这个东西就是stream,但是最后这个东西有个缺陷,就是不便于表达结构化的数据,一切都为了内容是可读的。

这里其实隐含这再说lisp才是最牛逼的,这里什么都是用s表达式表示的,有大量操作s表达式的操作,所有的运算的输入和输出都是s表达式。多么美好啊。当然如果看前缀的算术表达式能习惯的话,是挺不错的。

这里扯多了,第四部分讲递归是怎么实现的。为了构造循环的Env,使用了初次使用了box功能。也就是说引入了非pure functional的部分,对已有的值进行了修改,否则很难想象怎么构造一个环:1.A引用B,2.而B引用A,1要求在你构造A的时候B已经构造好了,而2相反,所以只能先构造一个再改了。

第五部分简单的讲了一下我们不一定要用原生的类型来表示新语言中的值,比如你用C写一个解释器,解释的语言的整数在C中也可能是个string或者和struct什么的。在scheme里面我们甚至可以完全就靠闭包来当作数据结构使用,模拟各种值的行为(当然性能就很微妙了)

这只是一个简单的过场

第六部分开始为我们要解释的语言加入了副作用。显示加入了box和unbox这样的功能,类似C里面的指针,虽然没有赋值,指针不能变,但是我们可以改变指针指向的东西了。

之后要允许变量直接赋值了,修改变量的值相当于取出变量对应的地址,然后改对应地址的值。

出现变量赋值后,就又提出了一个问题,函数调用的时候就产生了两种方式传值和传引用。

整体来看这里已经涉及了比较丰富的概念了内容了。

后面的内容我还没有看,只是简单的过一下目录,下面概括一下,有机会以后再展开讨论。

第七部分讲延续(Continuations),通过web程序的特点引入的。然后提到了CPS转化,再引入延续,最后将怎么实现。不了解的同学或者听说过协程(Coroutines),其和延续关系非常大,具体不多转述。CPS的话可以参看一些node.js的资料应该会有个大致的印象。

第八部分讨论内存管理的思路,比较像C那样显式malloc free和函数式语言那样自动分配的区别。

第九部分专门讨论语义,具体看后再说。

第十部分类型系统,最后会涉及自动类型推导,目测会比较有意思。

第十一部分搜索,实现一个prolog那样工作的语言

第十二部分DSL和metaprogramming,元编程,让人疯狂的宏

Read More...