O'REILLY 哪本书封面动物是海鸥?

概况

《代码之美》是一本论文集,她汇集33篇技术文章,讲述了38位作者认为最漂亮的代码。

试列举部分作者:(对你来说,有几位是耳熟能详的?)

  • Brian Kernighan:《C程序设计语言》、《程序设计实践》作者,前一本书也称K&R
  • Charles Petzold:《Windows程序设计》、《编码的奥秘》作者,Windows专家
  • John Bentley:《编程珠玑》作者,贝尔实验室前研究员,普林斯顿大学访问教授
  • Yukihiro Matsumoto(松本行弘):Ruby之父,是一位日本籍的开源倡导者
  • Simon Peyton Jones:Haskell主要设计者,GHC编译器首席设计师
  • Douglas Crockford:JSON数据格式发明者,JavaScript领域大牛

《代码之美》中文版有七篇推荐序(孟岩、韩磊、熊节、霍泰稳、周爱民、潘加宇、徐继哲),两篇译者序(刘未鹏、聂雪军),加上目录共占据前xxxiv页篇幅。(似乎很有一部分读者诟病推荐序太多)

我于2008年10月24日在网上书店购得《代码之美》,有趣的是,版权页印着“2009年1月第1版第1次印刷”(出版社此举有何深意,不解ing)。购书当日在CSDN论坛推荐,见文末的参考资料1

有一幅当时某电商搞笑风格的宣传海报(似乎改编自《代码大全》的海报),可点击参考资料2查看。

正则表达式匹配器

Brian Kernigham、Rob Pike 合著的《程序设计实践》第9章 记法,收录了许多代码示例,很好地说明了优良的记法将产生更好的程序以及更好的设计。(顺便说一句,《程序设计实践》是一本极好的书,强烈推荐)

《代码之美》第1章 正则表达式匹配器讲述了当时的情景:Brain 提议用一个最小的正则表达式包作为《程序设计实践》9.2节的代码示例,它可以很好地诠释正则表达式的基本思想,并且能够识别出一组有用且重要的模式。Rob 听了提议后马上回到他的办公室。一两个小时后他回来了,实现一个正则表达式匹配器:

字符  含义
 c   匹配任意的字符 c
 .   匹配任意的单个字符
 ^   匹配输入字符串的开头
 $   匹配输入字符串的结尾
 *   匹配前一个字符的零个或多个出现

只用了不到30行C代码:

/* match: 在 text 中查找 regexp */
int match(char *regexp, char *text)
{
  if (regexp[0] == '^') return matchhere(regexp+1, text);
  do { /* 即使字符串为空时也必须检查 */
    if (matchhere(regexp, text)) return 1;
  } while (*text++ != '\0');
  return 0;
}

/* matchhere: 在 text 的开头查找 regexp */
int matchhere(char *regexp, char *text)
{
  if (regexp[0] == '\0') return 1;
  if (regexp[1] == '*' ) return matchstar(regexp[0], regexp+2, text);
  if (regexp[0] == '$' && regexp[1] == '\0') return *text == '\0';
  if (*text != '\0' &&  (regexp[0] == '.' || regexp[0] == *text))
    return matchhere(regexp+1, text+1);
  return 0;
}

/* matchstar: 在 text 的开头查找 c*regexp */
int matchstar(int c, char *regexp, char *text)
{
  do { /* 通配符 * 匹配零个或多个实例 */
    if (matchhere(regexp, text)) return 1;
  } while (*text != '\0' && (*text++ == c || c == '.'));
  return 0;
}

如此少的代码实现如此多的功能,同时还提供丰富的内涵和深层次的思想。Brian 认为这是漂亮代码的一个极佳示例:紧凑,优雅,高效,实用。也是绝好的递归示例。还展示了C指针的强大功能。(熟悉C语言的读者可自行补上main()函数,写出测试代码)

为“The Book”编写程序

《代码之美》最后一章说到:数学家 Paul Erdős 经常会谈到“The book”,这是一本传说中的书(在地球上任何一家图书馆里都找不到),在这本书中记录了所有数学定理的最优证明。(见参考资料6,推荐数学爱好者阅读)

Brian Hayes 源于某位朋友的灵感,获得一个可以写入算法艺术领域“The Book”的程序。

这个程序所要解决的是一个非常基本的问题:假定平面内有三个点,那么这三点是否共线?

Hayes 使用 Lisp 语言编写代码。最初的程序通过比较直线的斜率和截距来判断共线:

(defun naive-collinear (px py qx qy rx ry)
  (let ((m (slope px py qx qy))
        (b (y-intercept px py qx qy)))
    (= ry (+ (* m rx) b))))

(defun slope (px py qx qy)
  (if (= px qx)
      nil
      (/ (- qy py) (- qx px))))

(defun y-intercept (px py qx qy)
  (let ((m (slope px py qx qy)))
    (if (not m)
        nil
        (- py (* m px)))))

(defun less-naive-collinearp (px py qx qy rx ry)
  (let ((m (slope px py qx qy))
        (b (y-intercept px py qx qy)))
    (if (numberp m)
        (= ry (+ (* m rx) b))
        (= px rx))))

上述程序不够优雅,对平行于纵坐标轴的直线需要特别判断。

后来,Hayes 阅读了 Jonathan Richard Shewchuk 的论文,通过计算三角形面积巧妙地解决了三点共线问题。最终版的程序如下:(虽然只有廖廖三行,其丰富的内涵足以写入“The Book”)

(defun area-collinear (px py qx qy rx ry)
  (= (* (- px rx) (- qy ry))
     (* (- qx rx) (- py ry))))

题外话:C 和 Lisp

《代码之美》第一章和最后一章分别用 C 和 Lisp 语言阐述作者认为最漂亮的程序。《实用 Common Lisp 编程》译者田春在译者序末尾说:

C 和 Lisp 是编程语言的两个极端,大多数人已经熟悉了 C 的那一端,但如果他们还熟悉另一端的话,那么迅速理解几乎所有其他的编程语言将不再是问题。

我的O'REILLY书架

我的其他藏书见参考资料7

参考资料

  1. 推荐《代码之美》的CSDN论坛旧贴
  2. 某电商的《代码之美》宣传海报
  3. 豆瓣: Beautiful Code
  4. 豆瓣:《代码之美》
  5. 豆瓣:《程序设计实践》
  6. 豆瓣: Proofs from THE BOOK
  7. 图灵社区:晒晒我的部分藏书