Todd | 酷壳 - CoolShell

程序的本质复杂性和元语言抽象

2013年10月31日 Todd 评论 97 条评论 47,193 人阅读

（感谢 @文艺复兴记（todd）投递此文）

组件复用技术的局限性

常听到有人讲“我写代码很讲究，一直严格遵循DRY原则，把重复使用的功能都封装成可复用的组件，使得代码简短优雅，同时也易于理解和维护”。显然，DRY原则和组件复用技术是最常见的改善代码质量的方法，不过，在我看来以这类方法为指导，能帮助我们写出“不错的程序”，但还不足以帮助我们写出简短、优雅、易理解、易维护的“好程序”。对于熟悉Martin Fowler《重构》和GoF《设计模式》的程序员，我常常提出这样一个问题帮助他们进一步加深对程序的理解：

如果目标是代码“简短、优雅、易理解、易维护”，组件复用技术是最好的方法吗？这种方法有没有根本性的局限？

虽然基于函数、类等形式的组件复用技术从一定程度上消除了冗余，提升了代码的抽象层次，但是这种技术却有着本质的局限性，其根源在于 每种组件形式都代表了特定的抽象维度，组件复用只能在其维度上进行抽象层次的提升。比如，我们可以把常用的HashMap等功能封装为类库，但是不管怎么封装复用类永远是类，封装虽然提升了代码的抽象层次，但是它永远不会变成Lambda，而实际问题所代表的抽象维度往往与之并不匹配。

以常见的二进制消息的解析为例，组件复用技术所能做到的只是把读取字节，检查约束，计算CRC等功能封装成函数，这是远远不够的。比如，下面的表格定义了二进制消息X的格式：

…

阅读全文 Read More

(37 人打了分，平均分： 4.11 )

C++模板”>>”编译问题与词法消歧设计

2013年10月02日 Todd 评论 17 条评论 16,833 人阅读

（感谢 @文艺复兴记（todd）投递此文）

在编译理论中，通常将编译过程抽象为5个主要阶段：词法分析(Lexical Analysis)，语法分析(Parsing)，语义分析(Semantic Analysis)，优化(Optimization)，代码生成(Code Generation)。这5个阶段类似Unix管道模型，上一个阶段的输出作为下一个阶段的输入。其中，词法分析是根据输入源代码文本流，分割出词，识别类别，产生词法元素(Token)流，如：

int a = 10;

经过词法分析会得到[(Type, “int”), (Identifier, “a”), (AssignOperator, “=”), (IntLiteral, 10)]，在后续的语法分析阶段，就会根据这些词法元素匹配相应的语法规则。在我学习编译原理时，教科书中对于词法分析的介绍主要是基于正则表达式的，言下之意就是普通语言的词法规则是可以通过正则表达式描述的。比如，C语言的变量名规则是“包含字母、数字或下划线，并且以字母或下划线开头”，这就可以用正则表达式[a-zA-Z_][a-zA-Z0-9_]*表达。但是，在实践中我发现不管是主流语言，还是自己设计的DSL都大量存在不能简单通过正则表达式进行词法分析的例子。来看C++98的模版例子：

map<int, vector<int>>

上面这段代码会被C++98编译器中报语法错误，原因在于它把“>>”识别成了位右移运算符而不是两个模版右括号，在C++98中必须在两个括号中间加空格，写成

…

阅读全文 Read More

(25 人打了分，平均分： 3.84 )

数据即代码：元驱动编程

2013年08月09日 Todd 评论 77 条评论 58,176 人阅读

（感谢 @文艺复兴记（todd）投递此文）

几个小伙伴在考虑下面这个各个语言都会遇到的问题：

问题：设计一个命令行参数解析API

一个好的命令行参数解析库一般涉及到这几个常见的方面：

1) 支持方便地生成帮助信息

2) 支持子命令，比如：git包含了push, pull, commit等多种子命令

3) 支持单字符选项、多字符选项、标志选项、参数选项等多种选项和位置参数

4) 支持选项默认值，比如：–port选项若未指定认为5037

5) 支持使用模式，比如：tar命令的-c和-x是互斥选项，属于不同的使用模式

经过一番考察，小伙伴们发现了这个几个有代表性的API设计：

1. getopt()：

getopt()是libc的标准函数，很多语言中都能找到它的移植版本。

…

阅读全文 Read More

(58 人打了分，平均分： 4.03 )

类型的本质和函数式实现

2013年07月22日 Todd 评论 32 条评论 28,966 人阅读

（感谢 @文艺复兴记（todd）投递此文）

在上一篇文章《二叉树迭代器算法》中，我介绍了一种基于栈的二叉树迭代器实现。程序设计语言和Haskell大牛@九瓜在看过之后评论到：

这里用了 stack 来做，有点偷懒，所以错失了一个抽象思考机会。如果我们能够理解二叉树到线性表的转换过程，完全可以把 Iterator 当作抽象的线性表来看，只要定义了关于 Iterator 的 empty, singleton, 还有 append 操作，实现二叉树的 Iterator 就变得非常直观。

“错失了一个抽象思考机会”是什么意思呢？我理解九瓜的意思是基于栈的实现虽然是正确的，但它缺乏对于迭代器类型本质的理解，不具有通用性。如果能对迭代器进行合适地抽象就可以像二叉树递归遍历一样自然地得出二叉树迭代器，甚至其他更复杂的数据结构，只要我们能写出它的遍历算法，迭代器算法都可以自然推出。

类型的本质

九瓜提到了通过empty, singleton和append操作对Iterator进行抽象，我本来打算直接根据这个思路介绍函数式的二叉树迭代器实现，但是考虑到其实首要的问题在于理解类型的本质，而并不是所有人都具备这个基础，不如先普及一下类型基础再进入具体实现。那么下面我们就先来认识一下类型到底是什么？我们先以来看看表示元素对的Pair类型，可能有人一提到Pair类型马上就会在脑海中浮现出下面的结构：

…

阅读全文 Read More

(23 人打了分，平均分： 3.61 )

二叉树迭代器算法

2013年07月14日 Todd 评论 54 条评论 41,235 人阅读

（感谢 @文艺复兴记（todd）投递此文）

二叉树(Binary Tree)的前序、中序和后续遍历是算法和数据结构中的基本问题，基于递归的二叉树遍历算法更是递归的经典应用。

假设二叉树结点定义如下：

// C++
struct Node {
    int value;
    Node *left;
    Node *right;
}

中序递归遍历算法：

// C++
void inorder_traverse(Node *node) {
    if (NULL != node->left) {
        inorder_traverse(node->left);
    }
    do_something(node);
    if (NULL != node->right) {
        inorder_traverse(node->right);
    }
}

前序和后序遍历算法类似。

但是，仅有遍历算法是不够的，在许多应用中，我们还需要对遍历本身进行抽象。假如有一个求和的函数sum，我们希望它能应用于链表，数组，二叉树等等不同的数据结构。这时，我们可以抽象出迭代器(Iterator)的概念，通过迭代器把算法和数据结构解耦了，使得通用算法能应用于不同类型的数据结构。我们可以把sum函数定义为：

…

阅读全文 Read More

(24 人打了分，平均分： 3.13 )

TF-IDF模型的概率解释

2012年10月24日 Todd 评论 51 条评论 52,832 人阅读

（感谢 @猫叔shiro（以前的todd）投递此文）

信息检索概述

信息检索是当前应用十分广泛的一种技术，论文检索、搜索引擎都属于信息检索的范畴。通常，人们把信息检索问题抽象为：在文档集合D上，对于由关键词w[1] … w[k]组成的查询串q，返回一个按查询q和文档d匹配度relevance(q, d)排序的相关文档列表D’。

对于这一问题，先后出现了布尔模型、向量模型等各种经典的信息检索模型，它们从不同的角度提出了自己的一套解决方案。布尔模型以集合的布尔运算为基础，查询效率高，但模型过于简单，无法有效地对不同文档进行排序，查询效果不佳。向量模型把文档和查询串都视为词所构成的多维向量，而文档与查询的相关性即对应于向量间的夹角。不过，由于通常词的数量巨大，向量维度非常高，而大量的维度都是0，计算向量夹角的效果并不好。另外，庞大的计算量也使得向量模型几乎不具有在互联网搜索引擎这样海量数据集上实施的可行性。

tf-idf模型

目前，真正在搜索引擎等实际应用中广泛使用的是tf-idf模型。tf-idf模型的主要思想是：如果词w在一篇文档d中出现的频率高，并且在其他文档中很少出现，则认为词w具有很好的区分能力，适合用来把文章d和其他文章区分开来。该模型主要包含了两个因素：

…

阅读全文 Read More

(21 人打了分，平均分： 3.71 )

Lisp的永恒之道

2012年06月04日 Todd 评论 93 条评论 71,253 人阅读

【感谢 Todd投递本文 – 微博帐号：weidagang 】

Lisp之魅

长久以来，Lisp一直被许多人视为史上最非凡的编程语言。它不仅在50多年前诞生的时候带来了诸多革命性的创新并极大地影响了后来编程语言的发展，即使在一大批现代语言不断涌现的今天，Lisp的诸多特性仍然未被超越。当各式各样的编程语言摆在面前，我们可以从运行效率、学习曲线、社区活跃度、厂商支持等多种不同的角度进行评判和选择，但我特别看中的一点在于语言能否有效地表达编程者的设计思想。学习C意味着学习如何用过程来表达设计思想，学习Java意味着学习如何用对象来表达设计思想，而虽然Lisp与函数式编程有很大的关系，但学习Lisp绝不仅仅是学习如何用函数表达设计思想。实际上，函数式编程并非Lisp的本质，在已经掌握了lambda、高阶函数、闭包、惰性求值等函数式编程概念之后，学习Lisp仍然大大加深了我对编程的理解。学习Lisp所收获的是如何“自由地”表达你的思想，这正是Lisp最大的魅力所在，也是这门古老的语言仍然具有很强的生命力的根本原因。

Lisp之源

Lisp意为表处理(List Processing)，源自设计者John McCarthy于1960年发表的一篇论文《符号表达式的递归函数及其机器计算》。McCarthy在这篇论文中向我们展示了用一种简单的数据结构S表达式(S-expression)来表示代码和数据，并在此基础上构建一种完整的语言。Lisp语言形式简单、内涵深刻，Paul Graham在《Lisp之根源》中将其对编程的贡献与欧几里德对几何的贡献相提并论。

Lisp之形

然而，与数学世界中简单易懂的欧氏几何形成鲜明对比，程序世界中的Lisp却一直是一种古老而又神秘的存在，真正理解其精妙的人还是少数。从表面上看，Lisp最明显的特征是它“古怪”的S表达式语法。S表达式是一个原子(atom)，或者若干S表达式组成的列表(list)，表达式之间用空格分开，放入一对括号中。“列表“这个术语可能会容易让人联想到数据结构中的链表之类的线形结构，实际上，Lisp的列表是一种可嵌套的树形结构。下面是一些S表达式的例子:

foo

()

(a b (c d) e)

(+ (* 2 3) 5)

(defun factorial (N)
    (if (= N 1)
        1
        (* N (factorial (- N 1)))
    )
)

…

阅读全文 Read More

(27 人打了分，平均分： 4.33 )

需求变化与IoC

2012年03月26日 Todd 评论 73 条评论 42,353 人阅读

【感谢 Todd投递本文 – 微博帐号：@weidagang 】

需求又变了，怎么办？

先上一个轻松的段子：

程序员XX遭遇车祸成植物人，医生说活下来的希望只有万分之一，唤醒更为渺茫。可他的Lead和亲人没有放弃，他们根据XX工作如命的作风，每天都在他身边念：“XX，需求又改了，该干活了，你快来呀！”，奇迹终于发生了，XX醒来了，第一句话：“需求又改了？”。

这个段子用幽默的方式反映了需求变化是每一个程序员、架构师或项目经理都会经常遇到的问题。面对这个问题，不同的人有不同的应对之道，最近微博上有一段关于需求变化的讨论：

@假装刺猬的猪：我们在软件开发过程中，会持续碰到客户需求变更的情况。如果没有领域建模，我们单纯将问题使用直觉将问题解决，那么等到客户需求变更或者有新的需求时，就会面临一个僵硬的前设计！无法在以前的设计上持续深入的优化模型，导致需求变更无法及时深化。设计实现均滞后与变更！

@高煥堂: <碰到客户需求变更的情况>是合理的；但<领域建模>不是美好的手段!!!

@weidagang: 要不被客户牵着鼻子走，需要自己有很强的设计能力，反过来让客户跟着你的设计来满足你的要求。能做到这点的公司很少，但这是软件行业唯一有希望的出路。

@高煥堂: <这是软件行业唯一有希望的出路>。 Great!!

如何应对需求变化？ @假装刺猬的猪的答案是领域建模，并持续优化模型，适应需求的变化。@高煥堂则认为领域建模不是美好的手段。我进一步补充，应该“反过来”让自己在需求变化中处于主导地位，而不是被动地适应。

…

阅读全文 Read More

(25 人打了分，平均分： 3.88 )

多版本并发控制(MVCC)在分布式系统中的应用

2012年03月13日 Todd 评论 98 条评论 59,912 人阅读

【感谢 Todd投递本文 – 微博帐号：weidagang 】

问题

最近项目中遇到了一个分布式系统的并发控制问题。该问题可以抽象为：某分布式系统由一个数据中心D和若干业务处理中心L1，L2 … Ln组成；D本质上是一个key-value存储，它对外提供基于HTTP协议的CRUD操作接口。L的业务逻辑可以抽象为下面3个步骤：

read: 根据keySet {k1, … kn}从D获取keyValueSet {k1:v1, … kn:vn}
do: 根据keyValueSet进行业务处理，得到需要更新的数据集keyValueSet’ {k1′:v1′, … km’:vm’} (注：读取的keySet和更新的keySet’可能不同)
update: 把keyValueSet’更新到D （注：D保证在一次调用更新多个key的原子性）

在没有事务支持的情况下，多个L进行并发处理可能会导致数据一致性问题。比如，考虑L1和L2的如下执行顺序：

L1从D读取key:123对应的值100
L2从D读取key:123对应的100
L1将key:123更新为100 + 1
L2将key:123更新为100 + 2

如果L1和L2串行执行，key:123对应的值将为103，但上面并发执行中L1的执行效果完全被L2所覆盖，实际key:123所对应的值变成了102。

…

阅读全文 Read More

(25 人打了分，平均分： 3.56 )

API设计：用流畅接口构造内部DSL

2011年10月31日 Todd 评论 32 条评论 33,461 人阅读

感谢@weidagang （Todd）向酷壳投递本文。

程序设计语言的抽象机制包含了两个最基本的方面：一是语言关注的基本元素/语义；另一个是从基本元素/语义到复合元素/语义的构造规则。在C、C++、Java、C#、Python等通用语言中，语言的基本元素/语义往往离问题域较远，通过API库的形式进行层层抽象是降低问题难度最常用的方法。比如，在C语言中最常见的方式是提供函数库来封装复杂逻辑，方便外部调用。

不过普通的API设计方法存在一种天然的陷阱，那就是不管怎样封装，大过程虽然比小过程抽象层次更高，但本质上还是过程，受到过程语义的制约。也就是说，通过基本元素/语义构造更高级抽象元素/语义的时候，语言的构造规则很大程度上限制了抽象的维度，我们很难跳出这个维度去，甚至可能根本意识不到这个限制。而SQL、HTML、CSS、make等DSL（领域特定语言）的抽象维度是为特定领域量身定做的，从这些抽象角度看问题往往最为简单，所以DSL在解决其特定领域的问题时比通用程序设计语言更加方便。通常，SQL等非通用语言被称为外部DSL（External DSL）；在通用语言中，我们其实也可以在一定程度上突破语言构造规则的抽象维度限制，定义内部DSL（Internal DSL）。

本文将介绍一种被称为流畅接口（Fluent Interface）的内部DSL设计方法。Wikipedia上Fluent Interface的定义是：

A fluent interface (as first coined by Eric Evans and Martin Fowler) is an implementation of an object oriented API that aims to provide for more readable code. A fluent interface is normally implemented by using method chaining to relay the instruction context of a subsequent call (but a fluent interface entails more than just method chaining).

下面将分4个部分来逐步说明流畅接口在构造内部DSL中的典型应用。

1. 基本语义抽象

如果要输出0..4这5个数，我们一般会首先想到类似这样的代码：

//Java
for (int i = 0; i < 5; ++i) {
    system.out.println(i);
}

…

阅读全文 Read More

(19 人打了分，平均分： 2.74 )

酷壳 – CoolShell

享受编程和技术所带来的快乐 – Coding Your Ambition

Browsed by
作者： Todd

程序的本质复杂性和元语言抽象

2013年10月31日 Todd 评论 97 条评论 47,193 人阅读

组件复用技术的局限性

C++模板”>>”编译问题与词法消歧设计

2013年10月02日 Todd 评论 17 条评论 16,833 人阅读

数据即代码：元驱动编程

2013年08月09日 Todd 评论 77 条评论 58,176 人阅读

类型的本质和函数式实现

2013年07月22日 Todd 评论 32 条评论 28,966 人阅读

类型的本质

二叉树迭代器算法

2013年07月14日 Todd 评论 54 条评论 41,235 人阅读

TF-IDF模型的概率解释

2012年10月24日 Todd 评论 51 条评论 52,832 人阅读

信息检索概述

tf-idf模型

Lisp的永恒之道

2012年06月04日 Todd 评论 93 条评论 71,253 人阅读

Lisp之魅

Lisp之源

Lisp之形

需求变化与IoC

2012年03月26日 Todd 评论 73 条评论 42,353 人阅读

需求又变了，怎么办？

多版本并发控制(MVCC)在分布式系统中的应用

2012年03月13日 Todd 评论 98 条评论 59,912 人阅读

问题

API设计：用流畅接口构造内部DSL

2011年10月31日 Todd 评论 32 条评论 33,461 人阅读

1. 基本语义抽象