Random Tech Thoughts

The title above is not random

The Second Most Important CS Class

Steve Yegge 在 Blog 里发新文章 “Rich Programmer Food“了,这次的话题是 Compiler。

先摘一段话来看看 Steve Yegge 认为 Compiler 有多重要:

Gentle, yet insistent executive summary: If you don’t know how compilers work, then you don’t know how computers work. If you’re not 100% sure whether you know how compilers work, then you don’t know how they work.

所以 Steve 说 Compiler Construction 是 CS 本科阶段第二重要的课程。(第一重要的课程呢?呵呵,到文章最后去找吧。)

Steve 在大学本科上了两次编译课程,第一次拿了 0 分,第二次才感觉学的不错。我在大三第一个学期学了编译原理,虽然分数不错,但是感觉只是知道了个大概,所以也就是说还是不明白编译器是怎么工作的。相信国内会有很不少人说编译原理没有用吧,但我自己看来还是有不少用处的。Steve 在文章里面提到了 7 个场景,其实学过编译的人都会明白怎样去解决,而没有学过的恐怕就没辙了。

因为我大三一年有三个学期,每个学期都比较短,所以编译原理只学了一小部分内容,主要就是词法分析、语意分析的部分,运行时环境稍微看过一些,代码生成和优化完全没有看过。但即使这样,我觉得语言语意分析的内容对我现在还是很有帮助。举几个例子来看看。一个是正则表达式,写程序经常要和文本打交道,另外 UNIX 系统里面文本文件也是无比的重要,正则表达式在处理文本上真的是帮了不少忙。第二点是写程序要解析文本的话会用词法分析里学到的东西,会用状态机或者 lex,写起来不会没有头绪。很可惜,语意分析那一部分在学习编译时没有太多编程的经验,所以现在一直都没有用上,当然也跟我写的程序没有这样的需求有关。

而另外很重要的一点时学习编译以后对程序设计语言也有了更多的理解。一些例子是明白了局部变量和全局变量的区别,名字覆盖是怎么回事,知道 BNF、EBNF 以后看到语言标准时不会一片茫然,而且有些简单的语言直接看 BNF 就可以知道它的语法规则。而当时仅有的一点运行时的概念也帮助我理解了 C 里面函数调用时参数究竟时怎么传递的,SICP 里面讲求值环境的内容也帮助我在学习 Ruby、Lisp 这样的动态语言时更容易理解其动态特性。

总得来说,就我目前所学的编译知识对我帮助最大的两个方面就是文本处理和对程序设计语言的了解。我现在想了解更多的是语言运行时环境方面的内容,尤其是动态语言的运行时环境。

关于大学 CS 专业的课程,Steve 说了下面一段话:

Most programmers gravitate towards a set of courses that can best be described as the olive-garden of computer science: the places where dumb programmers go to learn smart programmer stuff. I hesitate to name these courses explicitly. I wouldn’t be agile enough to dodge the game of graphic bloodshed aimed at me by animated, project-managing, object-oriented engineers using Java and Web 2.0 technologies to roast me via user interfaces designed rationally through teamwork and modern software methodologies. I’d become a case study in the ethics of software and its impact on our culture.

国外的不少大学开始把编译作为选修课程,许多学生为了得到一个好的 GPA 就放弃了这门课。Java、面向对象这样的课程当然也很重要,但是有些课程的话我个人觉得在大学以外的地方也可以学到。大学当然也需要教授技能,但是大学更重要的应该时传授思想。Java 有着非常丰富的类库,可以极大的方便我们写程序,但是用 Java 始终不会让我有多少成就感。有一个原因可能是周围太多用 Java 的人了,我不喜欢随大流,物以稀为贵,人也一样,虽然会比较孤立一些。当然这不是主要原因,更重要的原因是用 Java 以及其他项目提供的类库的时候,我自己始终只是一个用户,我所完成的工作不过是拿别人的东西来用而已。

学习使用一个库或者一个具体的技术现在看来其实都是很快的(并不是深入理解,只是了解到可以在实际工作中使用而已),边学边用的速度可能是最快的。但要学习思想和理论的时候需要一套比较完整的体系才能很好的了解,这个可能就是理论和技术的区别吧。技术因为可以在实践中去体会因此比较容易有感性认识,而理论则不是那么容易通过实践来体会的,所以那些能把理论转换为技术的人是很了不起的。想起之前看到的一篇文章,武学大师一般都是既懂理论,又有实战的人。只有实战的人可以很强,但是成不了大师,而只懂理论的人可能就只能摆花架子了。所以要做大师的话你可以从实战里面总结出一套理论出来,或者你学到一套武功秘技,然后在实践中加以发展最后自成一家。

所以我一直都希望在理论方面多学一点东西。目前打算看算法,然后想看计算理论、编译。以后的话还想了解些人工智能、分布式系统方面的东西。有些课程虽然已经学过了,但是总感觉深度不够。计算机要学的东西太多了,要深入的话只能选其中的一部分,不过太少的话就没有意思了。算上大四 1 年,研究生 2 年的话还有 3 年时间,得抓紧时间好好学了,当然前提是能顺利保研了,否则还得浪费半年时间去考。不过这些课程很可能都要自学了,有些课程学校都不会开设。

差点忘了说 CS 最重要的课程是什么了,我自己还没有办法确定那个是最重要的,Steve 说是打字入门。自己看着办吧。

X86-64 上为什么没有 linux-gate.so.1

reddit 今天有两个相关的 post。

第一篇讲 Linux 上的 linux-gate.so.1 是怎么回事,其实也就是 sysenter 和新的系统调用方式了,我之前也遇到过。

第二篇的作者看了这篇文章以后发现他的 64bit 的系统上没有 linux-gate.so.1,于是就开始了他的探索,最后发现在 x86-64 上只有 syscall 一种系统调用方式。我自己的机器是 64bit 的,但是装的操作系统是 32bit 的,所以表现和 32bit 的是一样的。

呵呵,看 Blog 长见识了,不是第二篇文章的话还不知道 syscall 呢 :–)

关于 Lisp 为什么没有流行的一篇文章 the Bipolar Lisp Programmer

很有趣的一篇文章,点这里。作者从分析那些聪明过人,但是最后却没有在学校里取得好成绩的学生为什么失败的原因,总结出他们的一个共有特点:brilliant bipolar mind (BBM)。因为他们聪明过人,所以很多事情在他们看来是 pointless 的(而事实上人类做的很多事情都是 pointless 的),因此不屑去做。

作者由此开始分析造成 Lisp 现状的问题。第一点是 Lisp 对问题的抽象能力强于 C/C++ 类的语言,BBM 们喜欢 Lisp(不知道是 BBM 们先喜欢 Lisp 还是 Lisp 容易让人们变成 BBM)。Lisp 社区通过 Thrown-away design 解决问题就 OK,或者只是为自己的问题考虑,自己理解就行。而使用 C/C++ 解决问题很难,需要许多人共同努力,于是人们写文档,让自己的工作成果可以为别人利用。

另一方面 BBM 们通常都不愿意妥协,作者说这导致了许多结果。一个例子就是 Lisp Machines,不愿意向市场妥协。

关于 BBM 的最后一点是在不景气时的失望、忧郁和遗失自我。Lisp 社区也有人对 Lisp 失去了希望。

作者最后总结到 Lisp 有两个问题,第一个是 Lisp mindset,也就是 BMM 存在的问题。另一个是 Lisp 本身的问题,但是作者最后又说到,

… because Lisp is, like life, what you make of it.

文章提到另一篇经典文章,Lisp: Good News, Bad News, How to Win Big,同样分析了 Lisp 的各个方面。(不过这篇文章发布于 1991 年,到现在也有不少东西发生变化了吧。)

Red Hat 的免费字体 Liberation

这里下载,试用了一下,效果还不错,已经换用这个字体了。

用的时候在 .fonts.conf 里面把 hinting 关掉效果比较好。另外这个字体是 condensed 风格的字体,所以我比较喜欢。它的 monotype 字体在 XFCE 的 terminal 中显示效果比 Dejavu 和 Bitstream 的 monotype 要好。

Sysenter, Int 0×80 和 Linux 系统调用

这次的作业里面要求修改 Linux 内核代码,统计系统调用执行的次数。看 《Linux Kernel Development》 的第一版(我买的早,所以是第一版),在 entry.S 里面加了几行代码,然后实现个系统调用把统计数据提供给用户空间进程,还是很简单的。

先说点题外话,《Linux Kernel Development》 一年前没有学过 Linux 编程的时候看不懂,现在再看感觉好多了,是本内核入门非常不错的书。

不过发现了点奇怪的现象。(无知,所以才觉得奇怪啊)测试程序里面用 C 库提供的 syscall 来调用自己写的系统调用,无论调用多少次,自己的那个调用的执行次数统计始终为 0。但是如果使用 _syscall 宏来调用自己的系统调用,每次调用统计次数都会增加。(我在 2.6.20 的内核 asm/unistd.h 中没有找到 _syscall 宏,拿了老版本代码里面的宏来用。)看 glibc 的 syscall 代码没有看懂(glibc 真是复杂,看的头大,不过倒是知道了什么是 weak symbol)。拿了 LKD 的第二版再来看,看到里面提到一句 Linux 的系统调用在 x86 上现在有了一种新的出发机制,名字就叫 sysenter。sysenter 进入内核的代码在 sysenter.c 里,我只改了 entry.S 所以如果用户空间进程以 sysenter 进入内核则系统调用的统计数据当然不会有变化。问题应该就是出在这里了。

于是就开始 Google 了,找到一些文章,ibm developer works 的介绍ChinaUnix 的一篇文章。马上来 fix 它。

想起去年暑假 IBM 的工程师凌棕说的一句话了,工程师只要找到问题,接下来就好解决了,难就难在怎样找到问题。再一次体会到了,不过这次运气还行,找到问题过程还算顺利。

Fedora, SELinux, Apache, Vsftpd 和 ReiserFS

这篇文章不知道起什么名字比较好,列了一堆名词,也许会很容易被 Google 到了……

在 Fedora Core 下配置服务器时遇到的问题。apache 的问题是自己指定的 Directory 总是 403 forbidden 错误,而 vsftpd 指定的 anon_root 目录以后匿名访问总是说没有权限进入那个目录。原因在于 Fedora Core 开启了 SELinux,安全策略不允许应用程序去访问那些目录和文件,所以出现了这样的错误。

关于 SELinux 的介绍这里有几个:Fedora Core FAQ 上的介绍,有人翻译的介绍ibm developworks的,教你自己搭建一个 SELinux 系统。

按我现在的理解,问题产生的原因是 httpd 进程运行在它自己的 domain 中(类似于 chroot,把一个进程被限制在一个目录下,不能跳出到那个目录的父目录),它只能访问属于这个 domain 的文件。而文件属于那个文件由文件系统上特别的 label 决定。

问题的解决的办法是针对特定的目录和文件使用 chcon 来给文件贴个标签(这样说应该还算合适吧,正式的说法应该是 security context)。先用 ls -Z 看能正常访问的位置的文件和目录的标签,比如 /var/www 是 system_u:object_r:httpd_sys_content_t,然后使用

chcon -R -h -t httpd_sys_content_t

来贴标签。-R 是递归,-h 不跟随符号链接。这样 apache 应该就可以访问这个文件和目录了。vsftpd 的解决办法也是类似的。

但是我在 ReiserFS 上做这个操作的时候总是出错,说不支持这样的操作,ext3 上没有问题。上网搜了一下,这篇 2006.01 的文章里面说 ReiserFS 上用不了 SELinux ,服务器内核配置中 ReiserFS 的 POSIX_ACL 和 FS_SECURITY 是配上的,但是还是出了问题。不知道是不是现在还不能用 SELinux。

(现在对 SELinux 还是一知半解,等以后多了解一点东西以后再回头来修改。)

功能强大的 Maxima

最早看到 Maxima 是在王垠那边,不过那时候没有使用的需要。现在用到了,发现真的是功能强大啊!想知道 Maxima 具体干什么的话还是去看王垠的介绍吧,简单说的话最主要是做符号计算的,它是一个计算机代数系统。Mathematica 和 Maple 就是这样软件的例子。Matlab 的话更多的是做数值计算吧,符号计算也可以做,但是和前面说的几个软件比的话可能会差一些。我只用过 Maxima,其他的都只是听说而已。

最近这几次作业只用了 Maxima 来做 taylor 展开,懒的自己手算了。Maxima 还可以解定积分、不定积分,函数求导,解线性、非线性方程,解常微分方程(另外也有人写了解一阶二阶偏微分方程的扩展),差分方程。其他还有许多功能,另外由于 Maxima 本身是用 Common Lisp 来写的,用 Common Lisp 来扩展它的功能也会比较方便。

我现在用的前端是 wxMaxima,最欣赏它的数学公式的输出,很漂亮,而且可以拷贝成 TeX 里面公式的形式。以后如果要在 TeX 里面排版数学公式的话可以考虑先在 wxMaxima 输入公式,然后由它的输出得到 TeX 里面的形式。

浮点数

最近学数值计算,第一次体会到浮点数精度的重要性了。

32 位机器上单精度浮点数有效数字只有 7 位。原因很简单,IEEE 754 (wiki 百科上的介绍很不错,不过访问受限,所以给了另外一个)的浮点数标准中 fraction 占 23 个 bit,换算到十进制的话就是 7 位。严格来说,对 normalized 形式的浮点数,因为小数点前的 1 被省略了, 所以其实是 24 个bit 也就是有 8 位有效数字,但是对于很小的正数,在 denormalized 的形式下,省略的那个 bit 是 0,对有效数字没有贡献,所以只有 7 位有效数字。

如果以单精度的浮点数来计算,要求得到误差小于 10-7 的结果,可以认为这个是不可能完成的任务吧。(我不知道有没有什么算法可以做到,有的话就太牛了。)输入数据的精度就只有 7 位有效数字,在计算过程中还要产生误差,要求最后的结果误差还要小于 10^(-7) 次方,听起来就比较愚蠢,但是我还是犯了这样的错误。

不过可以给自己一点借口。程序是用 Common Lisp 写的,刚开始使用,了解还不多,而 Common Lisp 默认使用的是单精度的浮点数。于是就发现我写的 Stiffenson 方法上千万次的迭代了还是迭代不到误差小于 10^(-7),更可笑的是根本就不收敛。千万次的 Stiffenson 方法迭代,算了好久得到这样的结果,瀑布汗啊…… 查程序半天没看出问题,最后才想到是浮点数精度的问题。改成双精度的,问题马上解决。

解决这种问题导致的错误真是痛苦……

数值计算的作业用 Lisp 这样的语言做真是非常棒,有理数精度基本上只受内存限制,函数当参数随便传,不像用 C 的话还得传指针,更何况还有高阶函数。另外边写边调试也很爽!

I Am Young!

“I am young!” 这是今天在市区时一个老外对我说的一句话。

今天进城去买五一回去的火车票,还顺便陪同学去协和琴行买琴托。买完琴托回来,在珠江路和中山路交界的十字路口(应该是这两条路的交界吧)等红灯时有一个老外来问路。这老外大概二十五六的样子,高大壮实,手里拿了一张地图,上来就要我帮他在地图上指出我们现在在哪里。那个十字路口我已经是第二次去了,不过上次就在这里走错了路。当时只确定有一条是中山路,再加上大脑发蒙,愣是看地图半天都没有找出具体的位置。最后直接问老外他要去哪,他在地图上指了下,于是知道他要去山西路百货那边。于是我提议让他和我们一起乘公交车去,但是那老外不领情,直接说 “no”,然后指了指十字路口的两个分支问 “This way or that way?” 给他指了正确的方向以后我告诉他从这里到山西路百货有很长一段路要走,老外却回了一句 “I am young!”。一开始我没反应过来,等让他再说一次以后明白他的意思了,一下子也就无话可说了。老外说了句谢谢便上路了。

老外一开始只是想知道他现在在哪里,这种问路的方式倒是很特别。我平常问路都是问到哪里应该怎么走,当然我手里没有地图,就算知道现在在哪里也是白搭。以前也听说老外们喜欢 travel 而不是 tour,他拒绝和我们一起坐公交车可能是因为他想更多的了解南京而选择用走路的方式,这样他可以看到更多的东西。但以这种方式去了解一个城市也实在时太累了,但人家老外的回答是 “I am young!”,这是我一点都没有想到的。

说来惭愧,在南京读书三年了,还没有怎么了解这个城市,南京值得看的地方也没有看过多少。学校在浦口固然是一个原因,但是真正的原因还在于懒惰。马上就要大四了,大四之后会在什么地方还不确定,如果要离开南京的话时间也不多了。如果直到离开的时候再后悔没有好好看一看南京恐怕就太晚了,也实在是遗憾,因为这样的机会很难说以后还有没有。更重要的是不趁现在年轻的时候多靠自己的双脚走些路,靠自己的双眼看些东西,等年纪大了就算有机会也没有这样的能力了。不光是了解一个城市吧,许多事情都只有在年轻时才能做,或者年轻时做效果最好。

好在 I am young! ( Even younger than that foreigner :–) ) 很多事情现在开始做还不算太晚,意识到并开始行动就可以补救吧。年轻真是好!