20130723

解密:LL与LR解析 2(译,完结)

由于GFW,我无法联系到作者,所以没有授权,瞎翻译的。原文在这里[http://blog.reverberate.org/2013/07/ll-and-lr-parsing-demystified.html]。

这是第2部分和完结。

3. 解析树的形状


到目前为止,我们使用的算术表达式的那棵树,仍然不是解析树,因为它并未与语法关联。要考查一棵真正的解析树,我们需要语法。不幸的是,为中缀算术表达式写语法不像你期待的那么简单和优雅。对优先级和结合性 (杨注:操作符左结合还是右结合)编码,保证语法没有二义性 (并受LL和LR支持) ,是非常丑陋和不符合直觉的。这也是为什么LL和LR解析器也允许你做指定操作符优先级这样的扩展;比如,参见Bison优先级的相关特性[http://www.gnu.org/software/bison/manual/html_node/Precedence.html#Precedence]。而这篇文章的目的是打算讨论纯的LL和LR。

因此,我们得把那个算术表达式的例子调整为比较容易写的语法的形式。我们将使用JSON (杨注:JSON是javascript的对象表示方法) ,既然它非常简单,而又足够复杂和有趣。

1 object → '{' pairs '}'
2  
3 pairs → pair pairs_tail | ε
4 pair → STRING ':' value
5 pairs_tail → ',' pairs | ε
6  
7 value → STRING | NUMBER | 'true' | 'false' | 'null' | object | array
8 array → '[' elements ']'
9  
10 elements → value elements_tail | ε
11 elements_tail → ',' elements | ε


上面,我用了单引号括起的字符串表示 原文文字标记 (literal tokens),用大写字母,比如STRING,表示那些拼写不确定的tokens (比如,"abc"和""都是有效的STRING tokens)。所有的名字小写字母的,都是语法规则 (也称 非叶节点)。

你可能奇怪,为什么我要用 pairs_tail 和 elements_tail,而不用重复构造 (repetition construct) ,像很多解析器比如ANTLR支持的那样。这样,我们就可以这样写:

elements → value (',' value)*

使用*的这种语法,用起来更方便,语法也更简单,但是同时,它导致解析树概念上更复杂了一点,因为某个给定的语法规则的子树个数不再是确定不变的。并且,LR解析器不支持重复操作符(比如,Bison就不支持),这样,我上面写的语法就既可以用于LL也可以用于LR解析器。因此,我们现在要使用这个有点复杂的语法。

现在,我们有语法了,那么我们来看一个token的流的例子,再来看输出的解析树。

{"message":"Hello, World!"}

上述这段文字的token流是:

{ STRING : STRING }

而它的解析树,按我们的语法,就是:



注意,所有的叶结点 (绿色的)都是tokens,它们的顺序与我们的解析器的输入顺序是完全一致的。 (我做了一点小弊,把ε作为叶结点了,不过正如我们所看到的,这看起来更干净更规则一些)

我前面曾经断言过,LL解析器输出的是先序遍历,而LR解析器输出的是后序遍历。从这一点出发,我们可以知道LL和LR解析器对上述输入分别会给出什么输出:



既然叶节点总是输入的tokens本身,且完全按输入的顺序,所以所有的解析器真正所做的,就是把中间节点 (杨注:语法规则)插入到合适的位置。看这一点的另一个角度就是,一棵解析树,就是一堆结构体,这堆结构体定义在输入的tokens的序列之上。我们稍微重新安排一下之前的这个图示,这一点看起来就更清楚了。
 



我们正集中讨论一个非常简单的模型,用这个模型描述LL和LR解析器如何工作。LL和LR解析器二者都读入一个输入tokens的流,再把相同的流作为输出,并且把规则 (杨注:中间节点)插入到适当的位置,以形成解析树的先序 (LL)或后序 (LR)遍历。




这样,按波兰和逆波兰表示法考虑,这种对解析器输出的认识又带给我们一个好处。它使得我们可以对解析器的输入和输出都按简单的、平坦的流建模。这比把解析器的中间输出状态视为部分地构造树要容易多了,那种思路对于理解输出和对输出的检验都没什么帮助。

4. 超前 (Lookahead)

LL和LR解析器都是"在线的",意味着它们都能在输入正在进行时开始产生输出.  但是在许多情况下,在流的位置之前的tokens没有包含足够的信息,因此解析无法知道是否需要插入规则 (或者,如果需要插入规则,应该插入哪一条).因此,解析器得超前 (lookahead)到流的后面,看看下面的一些tokens是什么,以便做出决定。当你看到像LL(1)或者LR (0)这样的命令的时候,括号里的数字就是要超前的tokens的数量。

值得注意的是,超前是相对于规则将要插入的位置而言的,这个位置 (正如你记得的)对于LL解析器而言是在规则的tokens之前,而在LR解析器的规则tokens之后。这意味着,LL超前从规则的tokens的开头开始计数,LR从末尾开始计数。这带给LR解析器一个巨大的益处,因为在它们做出决定之前,他们能够看到规则的所有tokens (可能再超前一些),而LL解析器只能看到规则最初的几个tokens。



这就是为什么会有LR(0)解析器这种东西,而LL(0)解析器是不可能存在的;那样就根本不会有信息用来帮助决定接下来的tokens应该使用哪条规则。


5. 结果

根据上述对于LL和LR解析的比较的理解,我们能够得到几条重要的结论,有助于理解为什么有些当然的事是那样的。

(1) LR解析器能够处理更多的语法

这一点可由上一节超前 (lookahead)推得。既然LR超前开始于规则的末尾,在做决定的时候,LR(1)就确定地比LL(1)拥有更多的信息。进而,LR(1) 解析器确定地能比LL(1)解析器多解析一些语法 (杨注:原文接下来在括号里是modulo LL-only grammar extensions; see below。我不知道什么意思)。LR解析器可以处理左递归,LL解析器不能。

优势:LR

(2) (杨注:EBNF这一类的)

另一方面,既然LL解析器在开始解析规则的tokens之前就选定了使用哪条规则,并且无论LL解析器什么时候解析一个token的时候,它一定知道其token的上下文。这是一个更困难的任务 (既然它们拥有的能够继续的信息更少),这导致了一些重要的优势。

LL解析器在语法中能支持 像正则表达式 一样的操作符。

知道解析的上下文,这使得利用正则表达式形式的多种多样的操作符成为可能,比如重复 (杨注:*),比如alternation (杨注:|),而且可以用在任何地方,而不仅仅是顶层处。基本上,每条规则都能构成一个DFA状态机。对于自顶向下的解析,这是可能的,因为解析器知道它位于哪条规则之中,在解析进行的过程中可以按规则的状态机进行。我认为这对于自底向上的解析,这是不可能的 (甚至如果你以某种方法令解析表做正确的事,归约那一步也需要归约有固定不变的参数个数。杨注:不懂)。这对于LL真是个好优点,因为有这些丰富的语法扩展(杨注:指类似正则表达式的),语法容易读多了。事实上,这有利于使LL那种严格语法的局面有所缓和,因为许多你需要左递归的地方都可以使用重复 (*)操作符替代。

1 // LR语法: 不允许任何特殊的,alternation 只允许
2 // 在顶层出现
3 //
4 // 允许这一条是因为它等价于
5 // pairs → pair pairs_tail
6 // pairs → ε
7 pairs → pair pairs_tail | ε
8  
9 // 扩展的LL语法; 之所以可能,是因为你可以对把每条规则
10 // 构造成一个DFA
11 pairs → (pair (',' pair)*)?

后一条规则可以构造出像这样的DFA (绿色的状态表示接受状态) :



知道上下文,也使得在规则中间的动作成为可能 (定制代码,这些代码运行在规则里的任意两个元素之间。杨注:如antlr的 semantic action)。Bison支持这一点,是通过在内部重写了语法,这使得所有的可视化 (杨注:可能指语法定义的时候?)都更加复杂了。

优势:LL

(3) LL解析器支持上下文相关的扫描/词法分析

知道上下文,另一个好处是也使得上下文相关的扫描/词法分析成为可能。比如,许多程序设计语言不允许把关键词用于变量名,因为独立的词法分析器 (及自底向上的解析器)不知道出现在这个位置上的token是变量名还是关键字。但是自顶向下的解析器调用词法解析器的时候,可以轻易地把当前的上下文传递给它。

优势:LL

(4) LL解析器支持继承属性

知道上下文,也能够支持基于LL的应用程序在构造树的时候把属性/元数据传递给树 (这有时被称为继承属性。杨注原文:inherited attribute)。 (无论LL还是LR解析器都支持综合属性 (杨注:原文synthesized attributes),是由树向上传递的)。

优势:LL

6. 结论

我描述了一种另类的LL和LR解析器的模型,这种模型与大多数文献中提到的等价,但是更符合直觉 (至少对我而言是这样)。我们可以把解析器视为黑盒子,这个黑盒子输入输出与先序和后序表示法对应的token和规则的流。至目前为止,我们还没有探索这些解析器的内部工作原理;我们只是把它们视作黑盒,我们不清楚它们内部的工作。我们也没有探究它们能处理和不能处理何种语法的问题。我们也没有探索LL和LR的变形 (Strong-LL, SLR, LALR等等)。我希望在接下来的文章中会更完整地讨论它们,再包含上示例代码。

解密:LL与LR解析 1

解密:LL与LR解析

作者:Josh Haberman翻译:杨贵福

由于GFW,我无法联系到作者,所以没有授权,瞎翻译的。原文在这里[http://blog.reverberate.org/2013/07/ll-and-lr-parsing-demystified.html]。

2013年7月22日

我最初解析理论的经历来自大学时自学程序设计语言的时候。当我学到像LL,LR还有它们的变型 (比如Strong-LL, SLR, LALR等等)的时候,我迷惑了。我觉得正注视着的是艰深而强大的咒语,它的重要意义我尚不能领会,但是我确信,总有一天,像"从左至右导出""最右导出"这些术语会融汇贯通,于是我继续努力期待明白的一天。


现在我可以说,经过10年的时间再加上看了一整架解析类的书以后,我把这些算法理解得不错了。但是我看待它们的角度和我看过的文献都非常不同。我更多地从实现的角度,而不是数学的角度,数学的角度也起了一些作用 (杨注:瞎翻译的)。无论如何,我想解释一下我是如何看待这些算法的,希望有人也像我一样觉得这个角度更直观。

这篇文章只涉及到把解析器视为黑盒子这一角度:即解析器的输入/输出,及解析器的限制。后续的文章将打开黑盒子,把这些算法内部工作的更多的细节展示出来。

1. 解析 与 波兰表式法

如果你在大学学习计算机科学,或者甚至你要是有个惠普的计算器 (杨注:我从来没见过逆波兰的HP计算器,而且,空格在那上面如何表示啊?) ,你就见过波兰和逆波兰表示法。它们能不用符号,也不用四则运算顺序规则,就能写出数学运算表达式。我们习惯于把表达式写作中缀形式,在这种形式下,操作符置于操作数二者之间:

1 + 2 * 3

在这种形式下,你如何知道计算的优先级呢?你不得不按约定的规则 (四则混合运算的法则)。你如何想按不同的次邓,就必须用括号了,像这样:

1 (1 + 2) * 3

在波兰和逆波兰表示法中,你不必关心四则运算的优先级,也不必加括号,同样可以避免二义性。这是通过把操作符放在操作数之前(波兰表示法)或之后 (逆波兰表示法)实现的。它们也分别被称为前缀和后缀表示法。

// 第一个例子: 1 + 2 * 3 // 中缀+ 1 * 2 3 // 波兰表示法 (前缀) 1 2 3 * + // 逆波兰表示法 (后缀)
 
// 第二个例子: (1 + 2) * 3 // 中缀* + 1 2 3 // 波兰表示法 (前缀) 1 2 + 3 * // 逆波兰表示法 (后缀)


除了不需要括号,也不需要运算次序的约定以外,波兰和逆波兰表示法在写运算器 (求值)的时候也容易很多 (也许HP计算器的设计师用逆波兰表示法,就是为了能去巴哈马群岛度一周假) 。下面是一个Python实现的逆波兰的简单求值器。

1 # 函数定义了操作符,及如何依据操作符求值
2 # 本例假设操作符都是二值的,不过容易扩展为多值。
3 ops = {
4   "+": (lambda a, b: a + b),
5   "-": (lambda a, b: a - b)
6 }
7  
8 def eval(tokens):
9   stack = []
10  
11   for token in tokens:
12     if token in ops:
13       arg2 = stack.pop()
14       arg1 = stack.pop()
15       result = ops[token](arg1, arg2)
16       stack.append(result)
17     else:
18       stack.append(int(token))
19  
20   return stack.pop()
21  
22 print "Result:",  eval("7 2 3 + -".split())

波兰和逆波兰表示法,确实如通常所说的,需要事先知道所有操作符的参数数量。这里的参数数量,指的是操作符所作用的操作数的数量。这意味着,单值操作符负号和二值操作符减法,是两个不同的操作符。否则,我们在遇到操作符的时候,就不知道从栈中弹出多少个操作数。

一种避免了这个问题的类似表达方法,是Lisp语言的s-表达式。s-表达式 (还有类似的编码形式,比如XML)避免了固定操作符参数个数的需要,实现这一效果的方法是明确标记每个表达式的开始和结束之处。

1 ; Lisp风格的前缀表达式;
2 ; 同一个操作符可以有不同的参数数量
3 (+ 1 2)
4 (+ 1 2 3 4 5)
5
6 ; 我们前两个例子在Lisp中的等价表达方式
7 ; 前缀: + 1 * 2 3
8 (+ 1 (* 2 3))
9
10 ; 前缀: * + 1 2 3
11 (* (+ 1 2) 3)

Lisp这一表达法有不同于前述方法的妥协 (前面的方法中要使用固定数量的参数,Lisp需要括号),但是它们底层的解析/处理算法是非常类似的,因此通常我们把它们视为略有不同的前缀表达式。

看起来我好像有点跑题了,不过,其实我一直在偷偷地讨论LL和LR。按我的观点,LL和LR解析正分别与波兰和逆波兰表示法直接相关。不过为了完整地探索这个想法,我们需要先描述一下我们需要解析器输出什么。

作为一个有趣的练习,请尝试实现一个算法,用于把波兰表达式转化为逆波兰表达式。看看你是否可以不需要先把整个表式式转化为为一棵树;你可以只用一个栈实现这个效果。现在,比如你又要实现相反的过程 (从逆波兰到波兰)--你只需在输入上运行同一个算法,这回转换的方向就相反了。当然,你也可以构造一棵中间的树,但是这导致 O(输入长度) 的空间,而单使用一个栈的解决方案只需要 O(树的深度) 的空间。如何从中缀到后缀呢?有一个非常聪明和高效的算法,称为 调度场算法[http://en.wikipedia.org/wiki/Shunting-yard_algorithm]。

2. 解析器及输出

我们一致认可解析器的输入是token的一个流 (这个流极可能来自一个词法分析器,不过我们可以以后再讨论这一部分)。不过解析器的输出是什么?你可能倾向于说"一棵解析树"。当然你可以用解析器构造出一棵解析树,不过也可能不是这样,而是一种完全不构造解析树的输出。比如,这个Bison的例子[http://www.gnu.org/software/bison/manual/html_node/Infix-Calc.html#Infix-Calc] ,在解析的同时求值了算术表达式。每次当子表达式被识别出来,它立即被求值,直到最终的结果是一个单独的数。从来没有解析树显式地构造出来。

因此,说解析器的输出是一棵解析树不具有足够的一般性。相反地,我断言:解析器的输出,至少我们今天讨论的LL和LR的输出,是解析树的 *遍历*。


如果触动了哪位真理洁癖的神经,我在此道歉。我可以听到有人抗议道,树的遍历是一种算法,是你施加于一棵树上的操作。我怎么能说解析器输出了一棵树的遍历呢?答案在于,请回想一下刚才的波兰和逆波兰表式法。它们通常只是一种数学算式的表示法,不过我们也可以更一般性地把它们视为 对树的遍历的扁平和线性的 (序列化的)编码方式。


回想 下我们的第一个例子 1 + 2 * 3。下面是这个表达式的树形的写法:

    +
   / \
  1   *
     / \
    2   3



有三种方法遍历这个二叉树,如在维基百科上所给出的:中序遍历 (in-order) ,先序遍历 (pre-order) ,后序遍历 (post-order)。它们的不同只在于你访问父节点的时机,是在访问子节点之前 (先序),之后 (后序),或者左右子树之间(中序)。这三者正与中缀、波兰、逆波兰表示法对应。

1 + 2 * 3 // 中缀表达式,中序遍历+ 1 * 2 3 // 波兰 (前缀)表达式,先序遍历1 2 3 * + // 逆波兰 (后缀)表达式,后序遍历

所以,波兰和逆波兰表示法 完全地编码了一棵树结构,并且规定了你遍历它的步骤。在这些编码方法与一棵实际的解析树之间的主要区别,在于 波兰和逆波兰表示法 编码的访问并非随机的。对于一棵真实的树 (杨注:计算机里的真实,不是现实的真实,哈哈,所谓真实),你可以跟随一个内部节点到它的右子树,或者它的左子树,或者甚至 (对于许多树而言)它的父节点。在这些线性的编码方案中,就没有这种灵活性:你只能采用它已经这样编码了的那种遍历方法。

但是,好的一方面是,它使用解析树的输出是一个流,这个流是在解析行为发生的时候产生的。这也是Bison的那个例子,它如何在没有实现构造一棵树的情况下,就能够求值算术表达式。如果真的需要一棵不是扁平编码的树的话,从线性的树遍历中很容易就能构造出一棵来。不过,当不需要这棵真的树的话,构造它的代价就完全可以避免。

这就引出了关键点:

LL和LR解析器操作之主要不同在于,LL解析器输出解析树的先序遍历,而LR解析器输出后序遍历。

这等价于那些更传统,但是 (按我的观点)更易令人迷惑和不那么直观的关于区别的解释:

* "LL解析器产生一个最左导出,而LR解析器产生一个逆转最右导出。"

* "LL解析器自顶向下把树构造出来,而LR解析器自底向上构造。"

* LL解析器通常称为"带预测的解析器"(杨注:原文predictive parsers,这是不是有约定的翻译啊),而LR解析器称为归约解析器 (杨注:原文shift-reduce )。

今天先翻译到这里,原文后面还有。

20130721

昨天CSAPP上的疑问的解答

昨天CSAPP上的疑问的解答

今天整明白了。

CSAPP英文版第2版,826页,或者中文版第2版546页,有这么一段。关于多级页表的。

"But if we had a 32-bit address space, 4KB pages, and a 4-byte
PTE[page table entry, 杨注], then we would need a 4MB page table
resident in memory at all time..."

其中"32-bit address space"的意思是 2^32 bytes,而不是2^32 bits,因为内存是按字节而不是按比特寻址的。

根据公式:页表尺寸 = (地址空间 / 页尺寸) * PTE入口大小........公式1

32-bit address space: 2^32 bytes (昨天误作bits)
4KB pages: 4K bytes
a 4-byte: 4 bytes
B: bytes



K = 2^10
M = 2^22

代入公式1的右侧,得

(2^32 bytes / 4K bytes) * 4 bytes
= 2^32 * 2^2 / (2^2 * 2^10) bytes
= 2^22 bytes
= 2^2 M bytes
= 4MB

--------------------

博客会手工同步到以下地址:

[http://giftdotyoung.blogspot.com]

[http://blog.csdn.net/younggift]

20130720

你最近在读什么书,及CSAPP上的一个疑问

你最近在读什么书,及CSAPP上的一个疑问

"你最近在读什么书?"这句话我在两处看到过。一处是鲁迅先生关怀青少年成长,问某个孩子的,然后向他推荐了《表》这样的道德教育类少儿读物;另一处是贾宝玉问林黛玉,或者反过来,或者是薛宝钗问林黛玉,又或者是贾政问贾宝玉,也许是关心,也许是调情,也许是暗藏机锋,《红楼梦》里这种比生活还复杂的对话,我总也不敢说看懂了。反正有此一问。

最近在douban上看到某位地下书店店员的回忆,写得颇有大家风范,我深以为这是文艺工作者在体验生活之后交的报告。此地下书店中的地下,不是隐藏非常深而不得见的意思,而是真的就在地底下,可能是地铁,也可能是防空洞,我没注意。作者提到很多有意思的小细节,比如证明读者们都如何无知而装作有见识,讲到读者寻求推荐的时候问"最近得诺贝尔奖那个,他的书有没?",似乎并不知道"莫言"。生活在观察之中,作为店员生活得颇有情趣。他提到两件事很有趣,一个是午休的时候挤出时间看溜冰,溜冰的人像水里游泳的鱼,另一个是提到很多明星去买书,他们都买实用型的
(例子可能是,如何治疗拖延症?),只有周迅是个例外,她只买世界名著。

有人可能撇嘴了,"她们都是装的。"一则,人不能处处假装,比如在素不相识的书店店员面前,周迅如何得知这是位文学大家在卧底;二则,又如果周迅只钟看看微博传八卦,喜欢不超过三百字的贴子,但是她只买世界名著,这又不是她所钟爱的,那么她的生活得多么得痛苦啊。

有同学可能说,看看微博怎么了?看微博当然没什么,不过这语气总归有点像李某某的律师的语气,所有回答都是"这是俺们的合法权利"。看微博,就像有人喜欢吃方便面,喜欢吃方便粉丝,喜欢吃咸菜,总也不吃还非常想得慌。你可能会说,微博就方便面,世界名著就满汉全席。没错,我非常明确地认为,作品确实是分三六九等的,无论是思想境界,抽象的高度,还是什么。微博这样短小的文字,甚至包括博客这种篇幅,要是能让一个人进步,或者如某些人回忆到的看了读者知音故事会心灵鸡汤以后提着喷壶灌顶一般顿悟,那都怪了。

我们读那些短小的东西,只是为我们的观点、既有的知识结构找些佐证。就像小女孩左看看右看看,啊,原来大家都跟我一样胖,恩,放心了。这种感觉。颠覆我们观点的,让我们从另一个角度看自己,甚至否定自己的--这就是所谓成长--只能是足够厚的作品。或者偶尔,会有非常薄的作品起到这样的作用,比如离散数学,比如纯粹理性批判,比如爱因斯坦讲相对论的原始那张贴子,不过,无一例外,这种短贴子,非常之难看懂,你得花比看大部头还长的时间去读。

读短东西,我们不过是在自言自语,连反刍都算不上。

我固执地认为,程序员仍然是先进生产力的代表,一个重要原因是,他们在工作以后仍然保持读书。他们终日阅读,读的东西还都够长。

也许他们读的文字只是库函数手册,又或者需求书,但是他们在与别人进行相当精确和深入的交流。有些人也读了,但是只流于表面,用于证明关系,"啊,我也这么想,你看我们的关系多么铁",或者"我完全同意你说的,但是",或者双方各说各话,互无交集。程序员要精确地找出他反对的部分,然后与作者争辩,或者做实验,或者吵得面红耳赤。因为如果双方的观点完全相同,就连交流的必要都没有。这和我们变态的现实生活如此不同,在现实世界,往往观点相同,我们就要一万次确认,观点不同,我们甚至不再说一句话。在现实世界,我们竟然往往只与自己对话,这多么孤独和变态。还是做个程序员更正常。

他们所阅读的,并非自己或自己的同类,那些完全赞同自己观点的人,所产出的东西。不是有些人说,某某类的作品,口戚,我从来不看。以此给自己贴个值钱的标签,供人给些好的品评。毛泽东同志在瑞金的时候,据说曾有人说,你用孙子兵法指导革命战争,如何如何。毛同志说,你知道孙子兵法里面讲些什么,你知道孙子兵法一共有几章?不是有人只读我们自己的传统,不是有人只读非我们自己的传统的东西么。

同时,他们所阅读的,并非完全为了追求阅读当时的的和短暂的快乐,像有些文艺青年那样。他们的阅读是漫长而痛苦的,他们阅读的原因之一是为了追求阅读之后达成的共识,或者挖掘出的差异。这些共识和差异,可能是人与人的,也可能是我们的假想与真实世界之间的。所以,他们不只挑那些读起来爽的,听起来的好的。

这让我想起以前提到过的,小资们艳羡,李安有段时期由老婆供养,成天就是看片儿。看片儿之于李安,与小资们想像的是不同的,我相信,他一定不会只挑自己喜欢的看,还喝着汽水嗑着瓜子,他一定是把那些烦得不行的片子也要看了,看到吐,他一定是把自己喜欢得不行的片子也看了,品评分析很多遍,直到把骨头和肉和神经完全分开了,再也不是最初感情上肤浅地喜欢的那种。

程序员就是这样阅读的。而且,他们一直保持。

还有一些人,从成年 (成熟?腐烂?)开始,就再也不阅读,再也不阅读自己不"喜欢"的,再也不阅读长的,再也不阅读自己不认同或者不认同自己的,再也不阅读对业务
(比如宫斗或者宫斗)有用的任何书籍。他们少年时,读得最多的是考试辅导材料。他们成年时,读得最多的是他们的孩子的考试辅导材料。有些人,即使在工业社会,即使在后工业时代,仍然保持着光荣的传统的小农意识,除了圣经或者语录基本没有读过别的,除了家乡
(不管出生在多么大的城市)再没见过更广阔的土地。如此纯洁,不沾纤尘。

你最近阅读的,不是为了直接的短期见效的功利的动机,超过500页的作品,是什
么?

-----

附记:

今天读CSAPP,第9章。有一处卡住了一个小时,复核书上计算的结果怎么也不对。后来拿着书睡着了。拿着书睡着这件事,一点也不浪漫,它让我意识到衰老,也让我意识到没有读到什么好玩的东西,时光虚度。

CSAPP英文版第2版,826页,或者中文版第2版546页,有这么一段。关于多级页表的。

"But if we had a 32-bit address space, 4KB pages, and a 4-byte
PTE[page table entry, 杨注], then we would need a 4MB page table
resident in memory at all time..."

就这么一段,成了拦路虎。我跳过它,读了后面大半小节,没什么障碍。我是这
么翻译和理解的:

但是如果我们有一个32位的地址空间,每页长度4K字节,PTE每个为4字节,那么,我们将需要4M字节的页表一直驻留在内存中...

以上翻译,有几处需要解释。1.K是1024,不是1000,M是1024*1024,不是1000*1000。2. 4KB
pages,第一篇时我读错了,以为是4*1024页,又重读和读后面,发现作者习惯于这样措辞,其实是每页4KB这么长,即 "splitted
into pages of 4KB page size"。

然后,我按上述理解算了一个小时,没算明白。对不上。

其实这个公式很简单,我甚至google了一下以确认

页表尺寸 = (地址空间 / 页尺寸) * PTE入口大小........公式1

你按我上面的翻译手算一下左边和右边就知道了,不等。为什么不等呢?因为4KB中的B,还有4MB中的B,根本就不是"字节" byte,而是"比特" bit。

网络 (和中文?)中,习惯用 B 表示 字节,b表示 比特。但是CSAPP这段并没认可这个约定。

32-bit address space: 2^32 bit
4KB pages: 4K bytes
a 4-byte: 4 bytes



K = 2^10
M = 2^22

代入公式1的右侧,得

(2^32 bits / 4K bytes) * 4 bytes
= 2^32 * 2^2 / (2^2 * 2^10) bits
= 2^22 bits
= 2^2 M bits
= 4Mb

CSAPP原文和翻译均写作: 4MB

我是不是哪儿算错了啊,各位大师看出来的烦请告诉我。

--------------------

博客会手工同步到以下地址:

[http://giftdotyoung.blogspot.com]

[http://blog.csdn.net/younggift]

20130718

除了管道和重定向,还有命令行参数

除了管道和重定向,还有命令行参数

管道和重定向,在Unix Shell
Script入门教程里都要提到。在稍微深入一点的dos/windows批处理教程里也要提到。管道,一般在用前一个进程产生的输出,作为后一个进程的输入;重定向,一般用在把输出由控制台转到文件,或者用文件替代控制台输入。管道和重定向满足了进程的输入和输出的转向。

输入和输出,似乎本来就是进程跑起来以后唯一与外界的联系。根据与外界的联系判定那是个什么东西,而不是根据它的内心,这据说是萨特的观点,小资们不可不知。

不过,输入和输出,并非进程与外界唯一的联系。除了输入以外,命令行参数,也是设定进程行为的重要依据。在这一点上,如果把进程当成一个对象,命令行参数有点像构造函数的参数,虽然跑起来以后就跟它无关了。而且,unix程序一般地,只有命令行参数才是命令,影响进程的行为,而以后从标准输入读进来的所有东西,都只是数据而已,是被进程处理的东西,对进程本身没有影响。

shell (像python一样),是一种不错的粘合剂,它能组装一系的进程,让它们协同工作。管道和重定向,能让它们完成生产者-消费者这样的组合。

不过,如果我们需要一个进程的输出,不是作为另一个进程的输入,而是作为它的命令行参数呢?

下面的写法,
a | b
完成的,是把a的输出作为b的输入。

而如果我们希望下面这样,如何表达?
b -para <此处是a的输出>

有不止一种方法。

1. backtick

backtick,就是"`"。这不是单引号,而是键盘左上角,波浪线 (~)下面的那个小点,像个反向的单引号。

它的作用是,把括起来的命令执行了,并用执行结果中的每一行去替换命令所在的位置。

ls `echo \-l`

相当于

ls -l

我们把其中的一段拿出来单独执行一下。

1 $ echo \-l
2 -l

可见,"echo \-l"的结果,就是"-l"。其中的"\"中为了避免echo把"-l"当成自己
的参数。

而"-l"替换了"ls `echo \-l`"中反引号括起来的部分,所以"ls `echo \-l`"就
变成了"ls -l"。

再举个例子。

1 $ grep -w main `find . *c`
2 ./samples/hidraw/hid-example.c:int main(int argc, char **argv)
3 ./samples/trace_events/Makefile:# have that tracer file in its main
search path. This is because
4 ./Makefile:# $(vmlinux-main). Most are built-in.o files from
top-level directories
5 ./Makefile:# +--< $(vmlinux-main)
6 ./Makefile:vmlinux-main := $(core-y) $(libs-y) $(drivers-y) $(net-y)
7 ./Makefile:vmlinux-all := $(vmlinux-init) $(vmlinux-main)
8 ...

这条命令的作用是,先执行 "find . *c",找到当前目录下所有子目录中的 c文件,然后对每个符合条件的文件执行 "grep -w main"。

命令"grep -w main `find . *c`"中,`find . *c`部分将被替换为很多个匹配的文件名,然后每个文件名都作为
"grep -w main"的命令行参数,类似于:

grep -w main a.c
grep -w main b.c
grep -w main c.c

这样。

2. $(cmd)

backtick倒是挺方便,不过很多同学反映,"`"这个符号太丑陋了。最丑陋的特性之一就是,它跟单引号"'"长得太过地相似了。像我这样认人脸有困难的,本来就希望大家服饰发型更多样化一些,所以你能够理解我现在看到女演员们长得都越来越像,该是多么大的困惑。我指的不光是韩国的,小锥子脸大眼睛面孔白而无表情。backtick也存在这样的问题,跟别人像,本来就是毛病。

所以有别的写法,比如这样:

grep -w main $(find . *c)

这样的效果跟backtick是一样的。一样一样的。区别呢?多少也有一些。比如 $(cmd) 这样写法是可以嵌套的。

3. xargs

不过上述这些需要"代换"的,似乎有些程序员理解起来有困难?后来出现了一个命令,xargs,专门用来做这件事。

find . *c | xargs grep -w main {}

请注意到find和grep的顺序换了。find的输出结果,由xargs转给grep作为命令行参数。事实上,是xargs调用了grep,管道的末端不是grep,而是xargs。这不同于管道的末端是grep,如果是这样,就成了find的输出作为grep的输入,是管道应用的更一般的情况。args把管道的输出转向了grep的命令行参数,而不是作为grep的输入。

"{}"在这里,将被find的输出替代。如果命令行参数的位置不重要,或者在最末端,那么还可以把"{}"省略掉,效果是一样的。像这样:

find . *c | xargs grep -w main

4. -exec

似乎有了xargs以后,还是有些程序员觉得不够简单?又有些命令自带了"-exec"参数,意谓:如果匹配了,就把那些输出作为"-exec后面的进程的命令行参数"。话说,有些事情由于它的领域模型就那么复杂,是不太可能因为表达方式而变得简单的。

以下命令,效果是一样的:
find . *c -exec grep -w main {} -nH \;

行尾的"\;",是为了标识"-exec"部分结束,其中的"\"是因为";"是个特殊字符。grep需要"-nH"参数,是因为不然输出的匹配行里没有文件名和行号。grep在此前的几个命令里用的是别名,这里是真正的grep本身。

5. 总结

以下几个命令等价:
$ cat `which 20.sh`
$ cat ${which 20.sh}
$ which 20.sh | xargs cat

cat不支持"-exec"参数,那是find这样的复杂命令的特色,因此以上总结中未包括。

----------

本文的命令在 emacs eshell 不好使,因为 eshell 对管道支持不充分,shell-mode则没有问题。

--------------------

博客会手工同步到以下地址:

----
杨贵福
东北师范大学 计算机科学与信息技术学院
--
Sincerely,
YANG Guifu
School of Computer Science and Information Technology
Northeast Normal University
Changchun, P.R.China

重剑无锋,大巧不工。

无不大工。

20130713

如何永生

如何永生

本文介绍通过 守护进程 或 at提交作业
监控某个进程保持运行,本案例中被监控的进程是amule电驴。守护进程方案是李记者提出的,用一个进程看着amule没死,也是李记者提出的。

1. 问题,amule不知道什么时候退出了

李记者,记者二字并不是他的职业,而是名字。这名字是我起的。因为常需要他在故事里扮演角色,而他的本名"粲"字估计很多读者都不太认识,所以就叫李记者。有出租车司机很谨慎地问,"你是记者啊",我哈哈大笑,"他的名字就叫记者。"

李记者来看我,带个黑色的大塑料袋,装垃圾那种,吭哧吭哧扒开,露出里面两大瓶黑可乐。坐定,照例是"你近来一向可好。"

他说,他刚刚休假了一周,天天躺在床上。他说,"我也腰间盘突出了。"有那么一瞬间,我觉得眼泪在眼圈里,腰间盘突出的种种从眼前一闪而过。

我拍腿大笑,哈哈,你也有今天啊,老了吧。然后开始东扯西扯,我们认识的各位。中间准备酒的时候,我看看了机器,抱怨,"电驴不定什么时候就退出去了,真是烦人呐。"

关键就是,你不知道它什么时候死掉了。所以,得隔一会看一眼,看着它干活。可能你忙了一阵,或者开了一天机,回家一看,它死了--而且不知道什么时候死的。

2. 永生之法

李记者说,开个进程,看 (读作一声) 着amule,死了就再启动一次。你才老了呢。

我叹气,看来我确实是老了啊。

这是个标准方案,标准到连病毒和流氓软件都用它。它们一般都用这样的方案保证永生:开几个进程,一个是驱动,一个是应用程序,一个是服务,它们之间互相监视大家的存在,如果发现哪一个挂了,就再把它启动起来。

要求24X7服务的那种应用,一般也需要这样的机制,比如HA (High Ability)
。同时开两台以上的机器,其中一台机器对外提供服务,并向其他的机器发送心跳信号,意思就是我还活着。一旦备用的机器发现主服务器宕掉了,立马启动自己的服务。从用户的角度上看,根本不知道中间还换了个服务生。

这么长时间以来电驴莫名退出困扰着我,我居然没有想到这个标准方案。

3. 守护进程

它的基本机制是轮询,隔一会看看服务还在不在了。像电驴这样的任务,轮询时间2分钟左右就行,反正丢失2分钟也不是很重要。这一点,我和李记者很快达成一致意见。但是,对于使用什么方式轮询,我们各执一端。

他认为,应该开个脚本,作为守护进程,始终在后台。我不同意,觉得这不够酷。李记者说这是标准方案,我说那也白扯,这不够酷。我的意见一会儿再说,他的方案就像下面这样:

$ cat amule_monitor.sh
1 #!/bin/bash
2 amule_status=''
3 while true; do
4 amule_status=$(ps aux | grep -w amule | wc -l)
5 if [ $amule_status = '2' ]; then
6 echo 'amule running.' | tee /var/log/amule_monitor.log
7 else
8 echo 'amule starting.' | tee /var/log/amule_monitor.log
9 amule 2> /dev/null 1> /dev/null &
10 fi
11 sleep 60;
12 done

第1行是指定用哪个程序解释下面的东西。对于熟悉perl,python的同学,这种写法应不陌生。

第2行的 amule_status 是个变量,用来记录 amule 到底是否活着。

第3行 和 第12 之间,是个循环,死循环,没有跳出条件。说起来这是件好玩的事,要想永"生",就得使用"死"循环。

第4行,取得 amule 的状态。状态是这样取得的 $(ps aux | grep -w amule | wc -l),加上$ ()
以后,里面的命令执行的结果就成了个变量。其中,管道分隔的前面两段,执行结果类似于这样:

$ ps aux | grep -w amule
young 5488 14.3 2.4 204256 47632 ? Sl 20:51 2:25 amule
young 5730 0.0 0.0 3324 824 pts/0 S+ 21:08 0:00 grep --color=auto -w amule

其中后一行,是grep本身,前一行,就表明amule正执行。

"wc -l" 是对"ps aux | grep -w amule
"执行的结果统计一下行数。显然,如果一行,那就是amule挂掉了,两行,那就是amule还健在。

在循环之中判断条件,然后有选择地做一些事情--很多算法的核心思想都是这个路子。

现在,我们得到了用于判断的变量 amule_status,接着,我们就要判断了。上面那段代码的判断部分如下:

5 if [ $amule_status = '2' ]; then
6 echo 'amule running.' | tee /var/log/amule_monitor.log
7 else
8 echo 'amule starting.' | tee /var/log/amule_monitor.log
9 amule 2> /dev/null 1> /dev/null &
10 fi
11 sleep 60;

第5行,如果两行的话,那么,第6行,写个日志,说"健在着呢";第7行,否则的话,第8行,日志,"启动一次",然后在第9行启动一次。

其中有些奇怪的符号,都具有特殊的含义。"[];"是条件;"2>"是错误重写向;"1>"是标准输出重定向。fi就是if结束的地方。

第11行,睡60秒。

睡60秒以后呢,就又回到了上面提到的死循环之中。再检查一次amule是否运行着呢,如果没有,启运一次。

这跟你父母看着你学习看书练琴背英语是一个路子:每隔一分钟,露个头,看到你学习着,就说,"啊,我给你拿点水果进来",如果没学习,就咆哮体。这种行为甚是普遍,所以名之为
monitor。也用来称呼班长--替老师监控同学们的人。

当然,小资同学们不会明白,能拥有你自己的屋子,就表明你是生在红旗下长在蜜罐里身在福中不知福。

运行上述程序的方法是:

$ ./amule_monitor.sh &

用"&"代表要求它后台运行,少吱声。然后amule就启运了。因为循环第一圈的时候,发现amule没有启运。然后2分钟之后,日志变成了"amule
running"。不是增加,tee把日志覆盖了。如果增量的话,按李记者的说法,没有时间戳,这样的日志没啥意义,而且,一个多月以后得多少记录啊。这时,我们可以把amule杀了,退出,2分钟以内,monitor就又循环回来,并觉查到amule死了,所以再启动一次amule。

这样,amule就永生了。所以,永生的方法不是永远不被打倒,而是被打倒了以后,马上就爬起来。

3. at,作业

3.1 另一个脚本

虽然amule永生了,但是如上面提到的,我觉得这个方法不酷。我要用at作业的方法实现。

这个版本是 amule_at.sh,在每一次 shell script 执行结束前,执行at,要求2分钟后再启动一次这个 shell script,这样:

1 at now + 2 minutes 2>/dev/null <<EOF
2 amule_at.sh
3 EOF

然后,我们失败了好几次。李记者说,"你老啦,应该跟踪日志输出。"跟踪日志表明,脚本确实执行了很多次,amule活着与否也判断准确,但是,amule启动失败。

李记者又说,"你老啦,应该跟踪日志输出。"我们发现 at 之下执行 amule,失败。又是跟踪日志表明,amule给出了失败信息:

Error: Unable to initialize gtk, is DISPLAY set properly?

李记者说,"你真是老了,怎么不输出日志呢,非常有把握?"我说,"是啊,我本以为一定如此。"

然后我们开始了相对漫长的讨论,关于为什么 在at里amule启动不了,而在 eshell/shell-mode/xterm 下就能启动呢?

3.2 环境变量?

term下能启动amule,而at下不能启动amule。我们猜测 环境变量 没有传递从term传到at,查了一下。

(1) eshell/shell-mode/xterm 下的环境变量:

env | sort > env.log

(2) at 下的环境变量:

1 $ at now <<EOF
2 env | sort > at.log
3 EOF
4 > > warning: commands will be executed using /bin/sh
5 job 6065 at Sat Jul 13 22:02:00 2013

以上,在at下执行"env | sort > at.log"。

为什么要排序呢,因为term下和at下的env顺序可能不同,如果顺序不同,diff
起来就麻烦了。

(3) at 和 非at下的环境变量

1 diff env.log at.log
2
3 6d5
4 < DISPLAY=:0.0
5 26c25
6 < OLDPWD=/home/young/tools
7 ---
8 > OLDPWD=/
9 29c28
10 < PWD=/home/young
11 ---
12 > PWD=/home/young/tools
13 32d30
14 < SHELL=/bin/bash
15 38d35
16 < TERM=dumb
17 41d37
18 < _=/usr/bin/env

我们猜,极可能是第4行"DISPLAY=:0.0"。第4行中的"<",表明后面的这个环境变量只有左边的文件env.log存在,而在at.log中不存在。

我们在at之前置这个环境变量,在at里跑amule,启动成功。

3.3 at版的脚本

1 #!/bin/bash
2 # check if amule is running
3 export DISPLAY=:0.0
4 amule_status=$(ps aux | grep -w amule | wc -l)
5 if [ $amule_status = '2' ]; then
6 echo 'amule running.'
7 else
8 date >> /var/log/amule_monitor.log
9 echo 'amule starting/restarting.' >> /var/log/amule_monitor.log
10 amule 1> /dev/null 2> /dev/null &
11 fi
12
13 # next cycle
14 at now + 2 minutes 2>/dev/null <<EOF
15 amule_at.sh
16 EOF

(1) 环境变量

第3行,"export DISPLAY=:0.0",就是3.2测试的结果。

(2) amule的运行状态

第4行,
4 amule_status=$(ps aux | grep -w amule | wc -l)

这行的内容,其实与死循环的版本没有任何区别。连行号都一样。

(3) 判断

在死循环版本中,有一段判断amule的状态,如果不是两行,就启动amule。在at这一版本中,也有这样一个判断,就是第5行到第11行。

这几行的代码与死循环版本也非常相似,除了加入了时间戳和日志:

8 date >> /var/log/amule_monitor.log
9 echo 'amule starting/restarting.' >> /var/log/amule_monitor.log

但是,在at这一版本中,判断单独存在,并不像死循环版本中;在列循环版本
中,判断是在循环之中的。

(4) 没有死循环

没有死循环,如何实现"永生"的效果呢?这个shell脚本执行完毕,就要退出了,而不是隐藏在后台继续执行。退出以后,如果amule死了,谁来生列肉骨呢?

所谓永生,不外乎一遍一遍跑,发现死了就救活。除了死循环,我们也可以这么干,at版本的第13行至第15行:

13 # next cycle
14 at now + 2 minutes 2>/dev/null <<EOF
15 amule_at.sh
16 EOF

第14行可以逐词译为中文:在 此刻 以后 2 分钟,执行 <<EOF...EOF 括起的语句。

"2>/dev/null"仍是表示错误重定向,重定向给null设备。这个设备有个八卦。最初的unix系统是BSD (还是AT&T?)
开发的,他们发行的是源代码,并在磁带
(没错,不是光盘)的卷标上写着,如果你有啥意见,就发到/dev/null去吧。/dev/null,那是个黑洞,数据只入不出,你只管吐槽,它不起微澜。

在at中指定的作业恰恰就是 amule_at.sh,当前的这个脚本自己。所以说,递归和迭代是多么地相似。

第14行把 amule_at.sh 排在了 atq队列
中,2分钟后,又检查一遍amule是不是活着--同时也很重要的,把amule_at.sh又一次排在了atq中。

循环仍然在,它只是换了个面目,不在shell script中,而是在 atq队列中。

就像我们刚刚从DOS的程序开始学习windows消息循环一样,循环仍然在,只是不再由你来实施,而是由"系统"提供了。这也软件工程中一件可怕的事,系统越来越多地承担任务,最后我们就无事可做,因此无业可就了。

4. 还有一种死亡

amule除了活着运行中和列了不在运行两种状态外,还有一种状态,另一种死亡的状态。

它可能是僵尸--即没有退出,因此还在ps中,amule_status结果有两行;同时也不是在运行中,因为它不对添加任务或列任务清单做出任何反应。

你是不是想到了一些人?

有个命令行工具 amulecmd可以用来帮助检查amule的状态。

如果amule 运行着:

1 $ amulecmd -c status -Pyour_password
2 This is amulecmd 2.2.6
3
4 Creating client...
5 Succeeded! Connection established to aMule 2.2.6
6 > eD2k: Now connecting
7 > Kad: Connected (ok)
8 > Download: 72.73 kB/s
9 > Upload: 49.96 kB/s
10 > Clients in queue: 358
11 > Total sources: 278

如果amule没运行:

1 young@young-laptop:~/media$ amulecmd -v -c status
2 This is amulecmd 2.2.6
3
4 Creating client...
5 Connection Failed. Unable to connect to localhost:4712

如果 amule 僵死着呢?

1 young@young-laptop:~/media$ amulecmd -v -c status
2 This is amulecmd 2.2.6
3
4 Creating client...
5 C-c C-c

第5行的"C-c C-c"不是输出,而是amulecmd一直不结束,我按键中止它运行。

但是对于shell script就麻烦了,你一直不结束,我怎么知道你到底是什么状态呢?这让我们想起了图灵停机问题。

注意:以下代码未经过测试,不保证正确。因为僵死状态我现在没有能成功重现,所以没测试过。李记者说,为了让amule僵死,我可以拔网络摔硬盘砸机器,甚至诅咒...
注意结束。

我试图用下面的代码侦测amule是否僵死:

amule_status=$( (amulecmd -c status &) | (read -t 1; echo $?; killall
amulecmd 2> /dev/null 1> /dev/null))

"amule_status=$(...)"是取后面命令运行的结果,作为变量 amule_status 的值。这个命令是:

(amulecmd -c status &) | (read -t 1; echo $?; killall amulecmd 2>
/dev/null 1> /dev/null)

管道的前半段,用"()"开了一个子进程,后台执行amulecmd -c
status,所以无论amulecmd执行能否"卡住",后面都会继续进行。amulecmd的输出给了管道的后半段:

(read -t 1; echo $?; killall amulecmd 2> /dev/null 1> /dev/null)

这后半段,其中,"read -t 1"是延时1秒,读标准输入
(已被前面的管道转为amulecmd的输出);如果read读到了东西,"echo
$?"的结果是0,否则就是别的什么。"$?"是个变量,表示前一命令执行的错误号。read读到东西了,错误号就是0,否则就不是0。

然后,"echo $?"就变成为了 amule_status的值。后面的呢?后面的killall杀掉amulecmd,以防它"卡"住了。

接着,我们判断这个新的amule_status,如果是0,那么amule还活着,或者死透了。活着,就什么也不用管,死透了,2分钟后at会通过amule_at.sh启动它。都不用担心。如果amule_status不是0,杀死amule,等它死透,再次启动amule。像这样:

1 if [ $amule_status != '0' ]; then
2 date >> /var/log/amule_monitor.log
3 echo 'amule is dead.' >> /var/log/amule_monitor.log
4 killall amule
5 sleep 15
6 amule 1> /dev/null 2> /dev/null &
7 fi


综上所述,at + 处理僵死的 完整版 如下。

1 #!/bin/bash
2 # check if amule is running
3 export DISPLAY=:0.0
4 # echo 'in script.' >> /var/log/amule_monitor.log
5 amule_status=$(ps aux | grep -w amule | wc -l)
6 if [ $amule_status = '2' ]; then
7 # echo 'amule running.' >> /var/log/amule_monitor.log
8 echo 'amule running.'
9 else
10 date >> /var/log/amule_monitor.log
11 echo 'amule starting/restarting.' >> /var/log/amule_monitor.log
12 amule 1> /dev/null 2> /dev/null &
13 fi
14
15 # check if amule is alive
16 amule_status=$( (amulecmd -c status -Pyour_password &) | (read -t
1; echo $?; killall amulecmd 2> /dev/null 1> /dev/null))
17 if [ $amule_status != '0' ]; then
18 date >> /var/log/amule_monitor.log
19 echo 'amule is dead.' >> /var/log/amule_monitor.log
20 killall amule
21 sleep 15
22 amule 1> /dev/null 2> /dev/null &
23 fi
24
25 # next cycle
26 at now + 2 minutes 2>/dev/null <<EOF
27 amule_at.sh
28 EOF

5. 生存状态

(1) 有一种生存状态,是活着,它接受输入,对外输出,做出响应,我们把这种状态叫做活着;有一种生存状态,在进程列表里,它不存在,因此,系统迅速做出响应"此人已死,有事烧纸",这是死亡;还有一种生存状态,它活着,占着CPU和内存,有时还占着屏幕,但是不对外界做出任何响应,这种状态,叫做僵尸?

不过,我们有时称为禅定。有些人看到的是东方的智慧吧。我看到的,是对恶的姑息。

(2) 有同学可能纠结于永生和再生的区别。其实,这一只草履虫和那一只草履虫又有多大的区别呢?《自私的基因》里提到,DNA从产生起,就一直没有"死亡",而只有在一代代生物间遗传或变异,即使肉体死了,DNA还在继续。它还提到,即使肉体死了,你传递给别人的思想也会一直生存下去。有点像日本动画片里的话,"带着你的份儿活下去,把你的份儿也活出来。"

我们把Unix操作系统kernel以外的那部分叫做shell,那么shell里面的是什么呢?也有部动画片以题目回答了这个问题,"Ghost
in the Shell"。

----------

本文的命令在 emacs eshell 不好使,因为 eshell 对管道支持不充分,shell-mode则没有问题。

--------------------

博客会手工同步到以下地址:

[http://giftdotyoung.blogspot.com]

[http://blog.csdn.net/younggift]

20130712

如无必要,勿增实体:在很多移动硬盘中找到某个文件

本文简要介绍通过 管道使用 find,bzip2,grep,案例是把诸多硬盘的目录(和文件)结构压缩存储,用于离线查找硬盘上的文件;还涉及到流在通过管道时压缩和解压缩。
最近拍的照片,哈尔滨探望大毅,跟ZHUMAO出去玩,在这里 [http://www.douban.com/photos/album/106351444/]。


1. 问题

事实上,我没有"很多"移动硬盘,而是只有"一些"。我倒是有很多光盘,装在半米高的柜子里几乎塞满,里面都是文件,有的是软件,有的是我的笔记和资料。光盘全都用记号笔写了名字,每张光盘还都配了一张纸,打印整页的树状目录。当年盗版软件光盘能做的工作我都做了,就是为了什么时候需要某个文件的时候能一下子查出来。

但是,失败了。

文件太多,一页纸经常打不下,如果简略一些,日后就可能找不到;光盘太多,一张张找来也真是费劲。现在,移动硬盘又出现了类似的问题。当我查找某个东西的时候,经常需要把六七个移动硬盘挨个插上计算机,一顿搜索。有时候还可能忘了最佳的关键词,再重插重搜。

当年的光盘是这样解决的。用TotalCommander
(绝对一大利器,向用windows的同学强烈推荐)做每一张光盘的目录树压缩包,把这些压缩包放在机器的硬盘里。需要找某个文件的时候,搜索这个压缩包,而不用插光盘。找到文件在哪张光盘里,再按卷标找光盘。当然,这要求给文件起个有区分度的好名字。目录树压缩包,是TotalCommander的一个插件,就像ZIP或RAR一样压缩目录,只不过它的内容不是文件,只是文件名。

移动硬盘多了,也出现了当年光盘的问题。不过当年的方案不能用了,因为我现在的坐机是Linux,没用TotalCommander可用。不过,好在上述功能用简单的脚本也足够能完成,涉及到的命令也只有三个而已。

2. 索引和压缩

这一步,把移动硬盘插上,把目录树列出来,做成个压缩包。

比如,我的这块移动硬盘 mount 在 /media/Elements/ 之下,形成的目录树压缩
包的名字是Elements.dir.zip,命令如下:

$ find /media/Elements/ | bzip2 -c > Elements.dir.zip &&
timidity~/tools/tomato/unlock.mid

(1) "find /media/Elements/" 的作用是把硬盘的目录树列出来,因为后面是管道,所以没有任何输出。如果我们截获它的输出,应该类似于:
/media/Elements/
/media/Elements/
/media/Elements/files
/media/Elements/files/ted
/media/Elements/files/TOP250部电影
/media/Elements/files/video
/media/Elements/files/[沙丘].Dune_CN_01_11.mp3
/media/Elements/files/[沙丘].Dune_CN_01_12.mp3
/media/Elements/files/[沙丘].Dune_CN_01_13.mp3
/media/Elements/files/[沙丘].Dune_CN_01_14.mp3
/media/Elements/files/[沙丘].Dune_CN_01_15_A.mp3
/media/Elements/files/[沙丘].Dune_CN_01_15_B.mp3
/media/Elements/files/[沙丘].Dune_CN_01_16_A.mp3
/media/Elements/files/[沙丘].Dune_CN_01_16_B.mp3
/media/Elements/files/[沙丘].Dune_CN_01_21_A.mp3
/media/Elements/files/[沙丘].Dune_CN_01_21_B.mp3

这里之所以不用tree的原因是,tree会形成下面的效果,因而无法用grep查找到某个文件在哪个目录下。

| |-- Card
| | `-- Characters and Viewpoint Elements of Fiction Writing (33)
| | |-- Characters and Viewpoint Elements of Fiction Writing - Card.mobi
| | |-- Characters and Viewpoint Elements of Fiction Writing - Card.pdf
| | |-- cover.jpg
| | `-- metadata.opf

如上,用grep的时候会查到:
| | |-- cover.jpg

我们只知道cover.jpg在第三级,却不容易找到它所在的目录是 "(某个目录)/Card/Characters and Viewpoint
Elements of Fiction Writing (33)"。而根据后文我们会知道,用grep查找而不用眼睛一行行去看非常重要。

(2) "bzip2 -c > Elements.dir.zip"
的作用是把标准输入来的东西压缩为zip格式,命名为Elements.dir.zip。"bzip2
-c"的意思是把压缩的结果输出到标准输出,所以我们用">"把它重定向了。

在本命令中,标准输入就是 (1) 里面的 find 的输出,那个目录树结构。

(3) 后面的 "&& timidity~/tools/tomato/unlock.mid" 的用途是压缩完成以后让计算机叫一声,通知我。

压缩目录树的速度非常快,但是从一整块移动硬盘里获取目录树有时花的时间比较长,而一直盯着屏幕等程序退出绝非我辈之所为--尽可能把任务交给计算机,只要你能说明白了。

"&&"符合不同于";"之处是,"&&"要求之前的命令执行结果正确,无错误返回值,然后再叫,";"不管前面结果如何。

输完上述命令以后,我们就可以听歌看碟看书喝咖啡,等计算机通知我们这块硬盘压完了。然后换一块移动硬盘,改mount点,改压缩包的名字,回画,再去享受生活。

生活里令我们非常享受的一点是,我们没有把目录树先写成个文件,然后再压缩这个文件。我们使用了管道,而不是文件作为中介。这让我想起,不止一次,研究生同学在做项目的时候告诉我,不可能把摄像头啊数据啊什么的直接读出来,必须先写到硬盘上,或者这么做比较方便。我们不能那么做的原因,首要的原因是是这样的效率要比直接读低很多,因为硬盘比内存慢好几个数量级,另一个更重要的原因是:我们学计算机的,代码早有一天要被别人看,咱丢不起这个人呐。

如无必要,勿增实体。

3. 解压和查找

当哪天我们要查硬盘里有什么数据的时候,我们就这样:

$ bzip2 -cd *.dir.zip | grep -i justice
/media/Elements/emule/incoming/[公平:怎么做才正确?].Justice.What's.The.Right.Thing.To.Do.Episode.01.mp4
/media/Elements/emule/incoming/[公平:怎么做才正确?].Justice.What's.The.Right.Thing.To.Do.Episode.02.mp4
/media/Elements/emule/incoming/[公平:怎么做才正确?].Justice.What's.The.Right.Thing.To.Do.Episode.03.mp4
/media/Elements/emule/incoming/[公平:怎么做才正确?].Justice.What's.The.Right.Thing.To.Do.Episode.04.mp4
/media/Elements/emule/incoming/[公平:怎么做才正确?].Justice.What's.The.Right.Thing.To.Do.Episode.05.mp4
/media/Elements/emule/incoming/[公平:怎么做才正确?].Justice.What's.The.Right.Thing.To.Do.Episode.06.mp4
/media/Elements/emule/incoming/[公平:怎么做才正确?].Justice.What's.The.Right.Thing.To.Do.Episode.07.mp4
/media/Elements/emule/incoming/[公平:怎么做才正确?].Justice.What's.The.Right.Thing.To.Do.Episode.08.mp4
/media/Elements/emule/incoming/[公平:怎么做才正确?].Justice.What's.The.Right.Thing.To.Do.Episode.09.mp4
/media/Elements/emule/incoming/[公平:怎么做才正确?].Justice.What's.The.Right.Thing.To.Do.Episode.10.mp4
/media/Elements/emule/incoming/[公平:怎么做才正确?].Justice.What's.The.Right.Thing.To.Do.Episode.11.mp4
/media/Elements/emule/incoming/[公平:怎么做才正确?].Justice.What's.The.Right.Thing.To.Do.Episode.12.mp4
/media/Elements/emule/incoming/公平与正义.第06集.Justice.What's.The.Right.Thing.To.Do.EP06.HDTV.HALFCD-TLF.mkv
/media/Elements/emule/incoming/公平与正义.第07集.Justice.What's.The.Right.Thing.To.Do.EP07.HDTV.HALFCD-TLF.mkv
/media/Elements/emule/incoming/公平与正义.第10集.Justice.What's.The.Right.Thing.To.Do.EP10.HDTV.HALFCD-TLF.mkv
/media/Elements/emule/incoming/公平与正义.第11集.Justice.What's.The.Right.Thing.To.Do.EP11.HDTV.HALFCD-TLF.mkv
/media/Elements/emule/incoming/公平与正义.第12集.Justice.What's.The.Right.Thing.To.Do.EP12.HDTV.HALFCD-TLF.mkv
/media/Elements/emule/incoming/公平与正义.第1集.Justice.What.The.Right.Thing.To.Do.EP01.HDTV.HALFCD-TLF.mkv
/media/Elements/emule/incoming/公平与正义.第2集.Justice.What.The.Right.Thing.To.Do.EP02.HDTV.HALFCD-TLF.mkv
/media/Elements/emule/incoming/公平与正义.第3集.Justice.What.The.Right.Thing.To.Do.EP03.HDTV.HALFCD-TLF.mkv
/media/Elements/emule/incoming/公平与正义.第4集.Justice.What.The.Right.Thing.To.Do.EP4.HDTV.HALFCD-TLF.mkv
/media/Elements/emule/incoming/公平与正义.第5集.Justice.What.The.Right.Thing.To.Do.EP5.HDTV.HALFCD-TLF.mkv
/media/Elements/emule/incoming/公平与正义.第8集.Justice.What.The.Right.Thing.To.Do.EP08.HDTV.HALFCD-TLF.mkv
/media/Elements/emule/incoming/公平与正义.第9集.Justice.What.The.Right.Thing.To.Do.EP09.HDTV.HALFCD-TLF.mkv

命令中,管道的前半段, "bzip2 -cd
*.dir.zip"是把所有文件都解压了,然后输出到标准输出。所有文件,就是目录树的内容。我们没有真正地把这些内容显示在标准输出上,而是通过管道给了另一个程序。

这接收目录树内容的另一个程序,就是"grep -i justice"。其中的"-i"的含义如下:

$ grep --help | grep -w \-i
Example: /bin/grep -i 'hello world' menu.h main.c
-i, --ignore-case ignore case distinctions

有的同学可能觉得这样不能一行行看,只能去查,有点别扭。不过,事情是这样:
(1)如果你知道自己要找的东西的名字,那么grep的检索条件就是它。或者
(2)如果你不知道自己要找的东西的名字,你就应该仔细想,想完了再来查。大多数事情都可以委托给别人做,唯独找到自己想要什么,必须亲力亲为,不可假手他人。对于需要别人提示才知道这正是自己想要的,我总是想起老师诱导小学生,"你看,啥啥是不是挺好的。"然后,我们就只能相信。

对于这一点,不少人最初都不太容易接受。她们倾向于在讨论的过程中互相理解和支持,并达成一致意见,"啊,原来咱们要找的是这个。"又或者,他们习惯于在工程中提需求的时候说,"你先这么做着,然后看看不行再改。"这路子就跟敬酒的时候说,"我干了,你随意,随我的意。"我们当然可以随客户的意,如果他们为他们不知道自己想要什么的时候你所完成的将要必要抛弃的工作付钱的话。不过,大家通常都愿意只为自己最后见到的东西付钱。

软件工程的著名案例,对比土木工程,从来没人说,"你先把这桥建起来,不合适的话,再转90度试试。"人们往往还没认识到,软件工程跟刮大白一样,人工也是要钱的。又像下棋,你下错了子儿,就要付出代价,而不能撒娇耍赖。

所以,一定要知道--自己想要的是什么。记得当年外教mimi问我们大家,什么是幸福。众说纷芸,吃好吃的啦,能毕业啦,亲人健康啦。我当时正天天抑郁
(现在似乎也未稍减),所以答:知道自己想要什么,这就是最大的幸福。她老人家唯独觉得我说得挺在理的。不过最后我期末成绩也不怎么样,大概她觉得那也不是我所追求的幸福吧。

跟索引和压缩那步一样,我们没有先把zip里的东西解出来
(你列一下zip里的目录就知道了,里面根本没有文件),然后再去grep,而是通过管道把解压的结果传给了grep。

如无必要,勿增实体。

4. 管道

完成以上步骤就能够保存移动硬盘的目录树和检索了,这一小节只是做个游戏。

$ find . | bzip2 -c | bzip2 -cd
.
./250porcelain.dir.zip
./my_passport.dir.zip
./backup001.dir.zip
./Elements.dir.zip
./gold.dir.zip
./lniu.dir.zip

上述命令以管道分隔成了三个部分。第一部分find,列出目录树;第二部分把目录树的文本压缩了;第三部分把传来的压缩的东西解开,然后写到标准输出上。在管道里,目录树内容的文本先压缩了,然后又解压了。

熟悉windows下的C语言的同学可能会想到,这管道先是处理了ascii-text,然后又处理了二进制,到底它是二进制的啊,还是纯文本的呢?这个问题请你自己查查吧,挺有意思的。

5. 如无必要,勿增实体 以外

计算机就像所有的艺术一样,充满了相互矛盾的各种信条,比如这条就是。一方面,我们相信,在程序设计、脚本写作中,应该尽量避免中间的分支出去的东西。类似的思想,在程序设计中,我们就要减少变量,把表达式的值直接传递给函数或者下一个表达式。比如,不写成:

a = 10 + b;
printf ("%d", a);

而是写成:

printf ("%d", 10+b);

但是另一方面,我们有时候又相信这个信条的反面:过早优化是万恶之源。在这个时候,我们相信,应该先对问题建模,然后再归约。建模和归约两个步骤合并成一个,往往是造成问题的原因,归约后的模型通常不那么易读了。越是聪明人,越熟悉的技术路线
(或者只知道这一两种技术路线),越倾向于把归约视为理所当然,而我们又经常没有聪明到可以像控制直接映射的模型那样控制归约后的模型。典型的例子是,当你脱口而出,"这不就是ABCD嘛",尤其是语带不屑的时候。

所以,如无必要,勿增实体 之外,我们还得知道事情的反面--过早优化是万恶之源。

PS.
本文的命令在 emacs eshell 不好使,因为 eshell 对管道支持不充分,shell-mode则没有问题。

--------------------


博客会手工同步到以下地址:


[http://giftdotyoung.blogspot.com]


[http://blog.csdn.net/younggift]

20130704

补充 保持我们最初的理想,当面对无数歧路

补充 保持我们最初的理想,当面对无数歧路

本文继续精略介绍用sed批量修改,补充grep按词匹配。兼极精略讨论周朴园为什么是虚伪的,结论是没文化真可怕。

1. 修正一个错误,find

上文提到 "find ." 中的"."是当前目录,有误。在这里,"."是从当前目录向下递归遍历,而不仅仅是当前目录自己。

如运行:
$ find . -name "*.[h|c]" -exec grep -nH fexecv {} \;
./include/schily.h:107: /* 6th arg not const, fexecv forces av[ac] = NULL */
./include/schily.h:108:extern int fexecv __PR((const char *, FILE *,
FILE *, FILE *, int,
./include/schily.h:110:extern int fexecve __PR((const char *, FILE *,
FILE *, FILE *,
./calltree/calltree.c:232: fexecve (Argv[0], f, fpp[1], stderr,
./libschily/fexec.c:111: ret = fexecv(name, in, out, err, ac, av);
./libschily/fexec.c:168: ret = fexecve(name, in, out, err, av, env);
./libschily/fexec.c:175:fexecv(name, in, out, err, ac, av)
./libschily/fexec.c:182: return (fexecve(name, in, out, err, av, environ));
./libschily/fexec.c:186:fexecve(name, in, out, err, av, env)

搜索到的匹配的文件,全都不在当前目录下,而是在子目录include,lcalltree,libschily中。

2. 去掉杂音 grep找getline

上文中用grep找包含getline的文件,结果有些杂音。

$ find . -name "*.[h|c]" -exec grep -nH getline {} \;
./include/schily.h:117:extern int fgetline __PR((FILE *, char *, int));
./include/schily.h:186:extern int getline __PR((char *, int));
./calltree/calltree.c:852: while (fgetline(fp, fname, sizeof(fname)) >= 0)
./libschily/stdio/fgetline.c:1:/* @(#)fgetline.c 1.6 03/06/15
Copyright 1986, 1996-2003 J. Schilling */
./libschily/stdio/fgetline.c:29:fgetline(f, buf, len)
./libschily/stdio/fgetline.c:67:getline(buf, len)
./libschily/stdio/fgetline.c:71: return (fgetline(stdin, buf, len));

其中有5行不是我们想要的,是因为 fgetline 误伤到的。fgetline比我们要找的多个f。

这些杂音会干扰我们的视线,让我们迷失方向,忘掉最初的理想。解决的方法就是:忽略它们,想办法不去注意它们,让噪音消失。

如果你的意志不够坚强,我们可以借助工具,像下面这样,用"单词"匹配,就把 fgetline 这样的去掉了,同时保留 "getline(" 这样的:
$ find . -name "*.[h|c]" -exec grep -w -nH getline {} \;
./include/schily.h:186:extern int getline __PR((char *, int));
./libschily/stdio/fgetline.c:67:getline(buf, len)

上面多的"-w"参数,代表:

$ grep --help | grep \-w -w -w, --word-regexp force PATTERN to match
only whole words

3. sed的使用,批量修改

上文还提到,找到包含getline字样的文件,然后依次用文本编辑器打开,一个个修改。这样还是容易错,在这些细节中,我们也容易迷失理想。而保持理想的秘诀正是忽略现在。

我们可以用sed批量修改。

(1) 先验证一下修改策略。做批处理的计划最怕的是中间某个步骤做了,但这不是放弃使用批量的理由,我们可以在此处加观察验证。

$ find . -name "*.[h|c]" -exec sed 's/\<getline\>/getline_calltree/'
{} \; | grep getline
extern int fgetline __PR((FILE *, char *, int));
extern int getline_calltree __PR((char *, int));
while (fgetline(fp, fname, sizeof(fname)) >= 0)
/* @(#)fgetline.c 1.6 03/06/15 Copyright 1986, 1996-2003 J. Schilling */
fgetline(f, buf, len)
getline_calltree(buf, len)
return (fgetline(stdin, buf, len));

还是用find找到*.h和*.c文件,然后调用 sed 批量修改。

sed的意思是 stream editor,可以执行对文本的编辑命令。这些命令在命令行里给出,不仅跟IDE这样的图形界面不一样,甚至跟emacs/vi这样的全屏编辑也不一样。不知道sed和行编辑哪一个更早。

我们来看一下sed的这些参数。"sed 's/\<getline\>/getline_calltree/' {} "

's/\<getline\>/getline_calltree/'就是编辑的命令,它的意思是:查找 (search,
s)符合条件的文字"\<getline\>",改成"getline_calltree"。格式是"s/匹配条件/修改成什么样子"。

匹配条件"\<getline\>"中的"\<"和"\>"表示按词匹配,类似于grep中的-w。"\"是转义符,因为"<"">"是特殊字符。

所以sed这部分的作用是找到 (*.h和*.c中的)所有getline这样的整词,修改为getline_calltree。

上述命令行最后的 grep getline,是为了检验修改策略是正确的。我们观察结果,果然,所有的getline都变成了getline_calltree,而fgetline无一误伤。

(2) 实施
执行
$ find . -name "*.[h|c]" -exec sed -i 's/\<getline\>/getline_calltree/' {} \;

这里的"-i"参数的意思是:

-i[SUFFIX], --in-place[=SUFFIX]
edit files in place (makes backup if extension supplied)

(3) 验证

保险起见,可以再看看"-i"到底改了没有。

$ find . -name "*.[h|c]" -exec grep -w -nH getline {} \;
$

果然干干净净的了。

(4) 剩下的工作

然后呢?

find . -name "*.[h|c]" -exec sed -i 's/\<fexecve\>/fexecve_calltree/' {} \;

然后 make。

然后看看编译出来的东西 (object) 在哪里。

$ find . -name calltree
./calltree
./calltree/OBJ/i686-linux-cc/calltree

大功告成。

(5) 批量

这样,当你告诉别人如何修改 calltree
才能编译的时候,你不必写上一大篇"先找到什么,在哪几个文件里,再找什么,在哪几个文件里"。你可以提供一个脚本完成这个任务。

如下:
find . -name "*.[h|c]" -exec sed -i 's/\<getline\>/getline_calltree/' {} \;
find . -name "*.[h|c]" -exec sed -i 's/\<fexecve\>/fexecve_calltree/' {} \;

这两行里蕴含了上述所有要求的步骤。

科幻小说作家Ted姜曾经写过一个情节,两个智商非常高的牛人终于碰面,他们只说了一个字,里面就包含了千言万语,进行了猩猩相惜还有战争。牛人们之所以能进行这种对话的原因在于,话语中的每个词都包含了非常的丰富的约定了确定定义的信息。因为那些是已经知道的了,正如康德说的,分析得到的都不是知识,而综合的,把这些已知知识放在一起的微量的未知,才是知识。调用DLL的程序之所以那么短,就是因为很多动作流程的约定已经在DLL中了。

周朴园之所以可以定性为虚伪的原因,也在于他实施了具有精确约定含义的动作--没有娶四凤她妈,剩下的说啥也白扯。他的各种小动作只是用来表现自己具有何处情怀和愿望而已,于四凤她妈没有任何影响。正是周的这种又做坏事,又要表现自己是好人的的做法,可以性定他为虚伪。所以,有确切含义的约定的知识在判断中至关重要。所有某个知识的背后庞大的网络支撑和构成了这个知识本身。

所以说,没文化真可怕。

--------------------

博客会手工同步到以下地址:

[http://giftdotyoung.blogspot.com]

[http://blog.csdn.net/younggift]

20130703

保持我们最初的理想,当面对无数歧路

保持我们最初的理想,当面对无数歧路

本文以实例非常粗浅地介绍Linux下的工具 find, grep, tar
的使用,还有正则表达式。侯捷先生用这些工具帮助写了<STL源码剖析>和<深入浅出MFC>,我们将用这些工具帮助编译一个叫做calltree的小工具。

本文还讨论了如何保持最初的理想。

0. calltee

calltree是个静态分析C代码中的函数调用关系的工具,用来画 call
graph。为了找个工具帮助画几个模块间的依赖关系,找到了它。刚刚这句你看不懂也没关系,你知道calltree是个程序就行了。事实上,大部分文章中的大部分话你看不懂,都没关系。直到因为你不知道这段话所提供的事实影响了你的阅读,那才有关系了。

1. 多歧路

在你读某段话时,如果没有完全读懂,那么宇宙会因此而分裂成为无数条分支,每条分支对应这段话的一种含义的可能。但是,这没有什么影响,你大可以把这些分支都忘了。不过,当你继续读,后面某一段可能会用到刚刚那句话提供的信息了,此时,因为你的注视,所有那些分支宇宙就坍缩为唯一的一个。如果你不知道那句话的确切含义,随着一步步深入,分支就会呈爆炸状迅速增长。

初学者在涉足某个领域的时候,所面临的正是这个问题--在每一步中,可能性都太多了,稍有不慎就拐进了一个死胡同。而且越走越远,接下来全是无用功。正是因为这个,我们要在每一步中检查自己当前的状态,而不能等到最后。

经常有同学问到,为什么我这段程序编译通不过呢?你要来他的程序一看,好几百行,编译一下,错误在第十几行。如果前面的你都没有通过,为什么要继续向下走呢,后面那好几百行都是怎么写出来的啊。

这是理工类的一个重要特点,如果当前的一步没有处理好,未来很难弥补。事实上,能在未来弥补现在的错误,是个巨牛的活儿。一般地,如果你幼稚到现在会犯这样的错误,基本可以断定,你不具备在未来弥补的能力。

所以写代码的时候,如果你承认自己不够牛
(通常如此),那么你应该写一会代码就编译一下,让编译器帮助检查错误。有同学说,我还得一阵才能写到下一个"括回}"呢。你应该在写"{"的下一个字符就写"}",然后再写中间的部分。步子要保证足够小,能在足够短的时间内编译,从而得到检验。如果航海技术不够发达,就应该珍惜生命,不远离陆地,在能看到海岸的地方航行。铁子同学,你是不是想起了《文明II》?

为了回避失败感,初学者们经常想要计划得非常周全,按他们的话说,"我想等想好了的再动手"。他们太骄傲了,计划,这是世界上最难的事实,远远比动手再失败要难很多个数量级。尤其是,你计划这件事情的时候,你尚不知道未来会遇到哪些问题--如果你知道,那么你就是这个并非陌生的领域的专家了。所谓初学者,就是两眼一抹黑地往前走的人。你不走,就永远也不会熟悉这个领域。

2. 解压

你说什么,等专家引领?专家哪有那个功夫。

比如安装calltree。你随便搜索一下,就有人告诉你从哪个网址下载。你下载完了,文件名是 "calltree-2.3.tar.bz2"。

你可能认识不少扩展名,认识 tar.gz,认识 zip,认识 rar,甚至还认识7z。可是bz2是什么?

大家一般的选择:1.找个支持bz2解压的工具,2.搜索一下,3.QQ上找个好友,"bz2怎么解压?"
最后这种人后来就被QQ好友拉黑了。有位大侠在网上提到: tar jxvf
calltree-2.3.tar.bz2。这也可能是你的QQ好友告诉你的。在命令行下跑一遍,你得到了 calltree-2.3 目录。

看起来解压完成了,很多人以为这一节就结束了。不过,在这个时刻,你可能没有注意到,宇宙分裂了。 tar jxvf
是什么意思,你没有注意,它存在各种可能,等到你再遇到需要它的时候,世界将坍缩为"你还是不会"。

这段话的意思,你当然可以搜索一下,或者QQ (你永远可以QQ别人,因此以后这条选择略掉),不过Linux/Unix的习惯是手册里有主要的信息。

我们执行:
$ tar --help | grep \-j
-j, --bzip2 filter the archive through bzip2

然后我们就明白了,j的作用是"filter the archive through
bzip2",原来是用bzip2解压缩的。我们的文档刚好是bz2扩展名,合理合理。

"tar --help"会输出tar的所有帮助。有不少人习惯于把 tar --help 全输出来,然后用眼睛找想要的信息。

如果你知道自己想要什么,那么可以直接告诉计算机,而不用自己再亲力亲为。对大量数据的重复工作,计算机比我们擅长,只要我们指令明确。grep就是干这个用的。grep是一个过滤器,它把符合条件的留下来。"-j"前面的那个"\",是因为"-"是个特殊字符,它的后面是grep的参数,"\"的作用是避免grep把"-j"作为参数,而是作为过滤条件。

如果你不知道自己想要什么,就只能在歧路中摸索;如果你知道自己的目标,那么,就可以直接命中,无需犹豫。大毅同学问我,为什么要看康德呢。我说,因为我想要过毫不犹豫的生活。道理是一样的。

初学者和专家最大的区别在于,专家不必尝试,他知道应该如何做,知道这样做的结果如何,甚至还知道误差和出错的概率有多大,甚至还知道如果出错如何改善。这些"如何"的难度,从前向后,越来越大。

2. make失败

解压以后,按Linux下从源代码编译安装,惯例就是进目录,读INSTALL文件;或者不读,直接跑configure或者make。

我make,然后出了一大堆错误。有的同学可能就要一行行找错误了,用眼睛。这很难,因为make的输出信息长达511行。这个数据也不是我一行行查的,而是:

$ make | wc -l
511

你要到哪里找错误呢?先想想错误信息的特征是什么。没错,"error"。所以,我们再用 grep。

$ make | grep -i "error"
../include/schily.h:186: error: conflicting types for 'getline'
make[2]: *** [OBJ/i686-linux-cc/avoffset.o] Error 1
make[1]: *** [all] Error 2
../include/schily.h:110: error: conflicting types for 'fexecve'
../include/schily.h:186: error: conflicting types for 'getline'
make[2]: *** [OBJ/i686-linux-cc/cvmod.o] Error 1
make[1]: *** [all] Error 2
../include/schily.h:110: error: conflicting types for 'fexecve'
../include/schily.h:186: error: conflicting types for 'getline'
make[1]: *** [OBJ/i686-linux-cc/calltree.o] Error 1
~/Downloads/calltree-2.3 $

这错误有点让人感到莫名其妙,因为getline和fexecve是两个著名的函数,你甚至能man出来它们,是posix的一部分。又或者你根本不知道它们是什么也行,你就会觉得,"这源代码不是应该一编译就通过吗,搞什么..."

3. 修改源代码

搜索一下,我找到了EnuLL大侠的博客[http://www.3null.org/?p=439],他说,"在比较新的内核(glibc库)上编译,会出现编译不过的问题。具体现象大概像下面这个样子..."
这个样子,就是你上面看到的样子。

然后EnuLL大侠说,"具体解决办法有两种,一种就是给glibc打patch,另一种就麻烦点,把冲突的命名手动都改了。"

关于解决方案,这句话到这里就完了,初学者就也完了。打patch,怎么打啊,手动改命名,怎么改啊。此处说来话长,我略过吧。总之,我们就知道,应该这样手动命名:把calltree源代码里所有声明、定义、调用这两个函数的地方,都把这两个函数改个名字。只要新的名字不再与posix的重名,那就没冲突了,编译就能通过了。

好了,目标明确了,你打算怎么动手?

有同学可能又想到了,一个个打开文件,然后有可能一行行看,用眼睛找到它们。或者,如果你有个够好的IDE,能全工程全文搜索--但是有时候你正用的项目恰恰不能在这个IDE上打开。再好的IDE和恒久远的钻石都是浮云,只有纯文本才是永恒的。

我们这样:

$ find . -name "*.[c|h]" -exec grep getline -nH {} \;
./include/schily.h:117:extern int fgetline __PR((FILE *, char *, int));
./include/schily.h:186:extern int getline __PR((char *, int));
./calltree/calltree.c:852: while (fgetline(fp, fname, sizeof(fname)) >= 0)
./libschily/stdio/fgetline.c:1:/* @(#)fgetline.c 1.6 03/06/15
Copyright 1986, 1996-2003 J. Schilling */
./libschily/stdio/fgetline.c:29:fgetline(f, buf, len)
./libschily/stdio/fgetline.c:67:getline(buf, len)
./libschily/stdio/fgetline.c:71: return (fgetline(stdin, buf, len));

从输出结果中能够看到:
(1) 在 include/schily.h的186行,是getline的声明;
(2) libschily/stdio/fgetline.c第67行,也提到了getline,查看代码以后发现,这是getline的定义;
(3) 奇怪,我没有找到调用getline的地方,不调用为什么要声明和定义。
(4) 那些fgetline是误伤的。

再来看产生这个结果的命令,"find . -name "*.[c|h]" -exec grep getline -nH {} \;"。有点乱,我们一段一段看。

find是个命令,找符合条件的文件。

(1) "find . -name"的意思是在当前目录"."下,找文件名符合条件的。

(2) "*.[c|h]"就是文件名要符合的条件。这是个正则表达式,意思是文件名任意("*"),扩展名(从"."开始)是"c"或者是"h"。我对正则表达式的运用还不是那么本能,所以实践操作中,没有先想到用正则表达式,而是先找了文件名为"*.c"的,然后找了文件名为"*.h"的。这也是典型的幼推的初学者的表现--不能一次性全部地了解自己的想法。

(3) "-exec ... {}... \;"。"-exec"的作用是,对find到的符合条件的文件,都施加一个动作 (命令)
,在本例中,这个动作就是grep。"{}"就代表找到的文件在这个命令中的位置。";"的作用是标识"-exec"的命令部分结束了,"\"是避免shell把";"当作find这个命令和下一个命令分隔符。wikipedia说得更明白一些,"The
semicolon (backslashed to avoid the shell interpreting it as a command
separator) indicates the end of the command."

如果找到的文件是 gold.c,那么"-exec"以后的部分相当于:grep getline -nH gold.c。注意,gold.c刚好取代了"{}"。

(4)"grep getline -nH {}"。grep是按正则表达式
(或退化为字符串)在文本中找到符合条件的行。"getline"是要匹配的正则表达式,在本例中,是我们要找到的那个函数。"{}"的意思上面说过了,代表find找到的文件,"-nH"的意思是打印出文件名和行号,你可以这样知道:

$ grep --help | grep \-H
-H, --with-filename print the filename for each match
$ grep --help | grep \-n,
-n, --line-number print line number with output lines

(5) 以上连起来,就是 "find . -name "*.[c|h]" -exec grep getline -nH {} \;"。

含义是:在当前目录下,找到所有的*.c和*.h;然后在这些文本文件的正文中,找到存在"getline"字样的地方。

然后呢?然后我们用文本编辑器打开那几个文件,找到对应的地方。我把getline都改为 getline_calltree。

然后呢?然后把 fexecve 也都改了,我改成 fexecve_calltree。

4. 可以更自动化

本例中,要改的地方不过五六处而已。如果要改的地方特别多呢?有个工具,叫做sed。

5. 再make

再make,通过了。为什么知道通过了呢?

我们执行
$ make | grep -i "error"

没有输出。没有消息就是好消息。

在".../OBJ/"下,我们得到了 calltree 文件,是可执行的。


6. 回顾歧路

每一个步骤,如果我们不选用自动化的 (批量的)
工具,我们都可能更倾向于陷入细节当中,迷失方向。尤其当我们是初学者的时候,我们尚不知道眼睛该往哪里看。这些细节具有多种可能性,很多步骤的多种可能性叠加起来,我们的面前摆着的就是一张非常复杂的网,每个节点都通向好几个地方。

我们总觉得眼前的就是最重要的,"活在当下"。就这样,我们被眼前的细节引导向完全不同的没有预期的方向;就这样,我们忘掉了最初的理想。

--------------------

博客会手工同步到以下地址:

[http://giftdotyoung.blogspot.com]

[http://blog.csdn.net/younggift]