编程语言 | 酷壳 - CoolShell

一个“蝇量级” C 语言协程库

2014年01月28日 Leo 评论 54 条评论 105,449 人阅读

协程(coroutine)顾名思义就是“协作的例程”（co-operative routines）。跟具有操作系统概念的线程不一样，协程是在用户空间利用程序语言的语法语义就能实现逻辑上类似多任务的编程技巧。实际上协程的概念比线程还要早，按照 Knuth 的说法“子例程是协程的特例”，一个子例程就是一次子函数调用，那么实际上协程就是类函数一样的程序组件，你可以在一个线程里面轻松创建数十万个协程，就像数十万次函数调用一样。只不过子例程只有一个调用入口起始点，返回之后就结束了，而协程入口既可以是起始点，又可以从上一个返回点继续执行，也就是说协程之间可以通过 yield 方式转移执行权，对称（symmetric）、平级地调用对方，而不是像例程那样上下级调用关系。当然 Knuth 的“特例”指的是协程也可以模拟例程那样实现上下级调用关系，这就叫非对称协程（asymmetric coroutines）。

基于事件驱动模型

我们举一个例子来看看一种对称协程调用场景，大家最熟悉的“生产者-消费者”事件驱动模型，一个协程负责生产产品并将它们加入队列，另一个负责从队列中取出产品并使用它。为了提高效率，你想一次增加或删除多个产品。伪代码可以是这样的：

# producer coroutine
loop
while queue is not full
  create some new items
  add the items to queue
yield to consumer

# consumer coroutine
loop
while queue is not empty
  remove some items from queue
  use the items
yield to producer

…

阅读全文 Read More

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

函数式编程

2013年12月27日陈皓评论 193 条评论 210,164 人阅读

当我们说起函数式编程来说，我们会看到如下函数式编程的长相：

函数式编程的三大特性：
- immutable data 不可变数据：像Clojure一样，默认上变量是不可变的，如果你要改变变量，你需要把变量copy出去修改。这样一来，可以让你的程序少很多Bug。因为，程序中的状态不好维护，在并发的时候更不好维护。（你可以试想一下如果你的程序有个复杂的状态，当以后别人改你代码的时候，是很容易出bug的，在并行中这样的问题就更多了）
- first class functions：这个技术可以让你的函数就像变量一样来使用。也就是说，你的函数可以像变量一样被创建，修改，并当成变量一样传递，返回或是在函数中嵌套函数。这个有点像Javascript的Prototype（参看Javascript的面向对象编程）
- 尾递归优化：我们知道递归的害处，那就是如果递归很深的话，stack受不了，并会导致性能大幅度下降。所以，我们使用尾递归优化技术——每次递归时都会重用stack，这样一来能够提升性能，当然，这需要语言或编译器的支持。Python就不支持。

函数式编程的几个技术
- map & reduce ：这个技术不用多说了，函数式编程最常见的技术就是对一个集合做Map和Reduce操作。这比起过程式的语言来说，在代码上要更容易阅读。（传统过程式的语言需要使用for/while循环，然后在各种变量中把数据倒过来倒过去的）这个很像C++中的STL中的foreach，find_if，count_if之流的函数的玩法。
- pipeline：这个技术的意思是，把函数实例成一个一个的action，然后，把一组action放到一个数组或是列表中，然后把数据传给这个action list，数据就像一个pipeline一样顺序地被各个函数所操作，最终得到我们想要的结果。
- recursing 递归 ：递归最大的好处就简化代码，他可以把一个复杂的问题用很简单的代码描述出来。注意：递归的精髓是描述问题，而这正是函数式编程的精髓。
- currying：把一个函数的多个参数分解成多个函数，然后把函数多层封装起来，每层函数都返回一个函数去接收下一个参数这样，可以简化函数的多个参数。在C++中，这个很像STL中的bind_1st或是bind2nd。
- higher order function 高阶函数：所谓高阶函数就是函数当参数，把传入的函数做一个封装，然后返回这个封装函数。现象上就是函数传进传出，就像面向对象对象满天飞一样。

…

阅读全文 Read More

(87 人打了分，平均分： 4.64 )

Lua简明教程

2013年12月03日陈皓评论 124 条评论 263,101 人阅读

The Programming Language Lua 这几天系统地学习了一下Lua这个脚本语言，Lua脚本是一个很轻量级的脚本，也是号称性能最高的脚本，用在很多需要性能的地方，比如：游戏脚本，nginx，wireshark的脚本，当你把他的源码下下来编译后，你会发现解释器居然不到200k，这是多么地变态啊（/bin/sh都要1M，MacOS平台），而且能和C语言非常好的互动。我很好奇得浏览了一下Lua解释器的源码，这可能是我看过最干净的C的源码了。

我不想写一篇大而全的语言手册，一方面是因为已经有了（见本文后面的链接），重要的原因是，因为大篇幅的文章会挫败人的学习热情，我始终觉得好的文章读起来就像拉大便一样，能一口气很流畅地搞完，才会让人爽（这也是我为什么不想写书的原因）。所以，这必然又是一篇“入厕文章”，还是那句话，我希望本文能够让大家利用上下班，上厕所大便的时间学习一个技术。呵呵。

相信你现在已经在厕所里脱掉裤子露出屁股已经准备好大便了，那就让我们畅快地排泄吧……

运行

首先，我们需要知道，Lua是类C的，所以，他是大小写字符敏感的。

下面是Lua的Hello World。注意：Lua脚本的语句的分号是可选的，这个和GO语言很类似。

print("Hello World")

你可以像python一样，在命令行上运行lua命令后进入lua的shell中执行语句。

chenhao-air:lua chenhao$ lua
Lua 5.2.2  Copyright (C) 1994-2013 Lua.org, PUC-Rio
> print("Hello, World")
Hello, World
>

…

阅读全文 Read More

(86 人打了分，平均分： 4.55 )

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

2013年10月31日 Todd 评论 97 条评论 46,235 人阅读

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

组件复用技术的局限性

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

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

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

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

…

阅读全文 Read More

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

伙伴分配器的一个极简实现

2013年10月09日 Leo 评论 55 条评论 62,187 人阅读

（感谢网友 @我的上铺叫路遥 投稿）

提起buddy system相信很多人不会陌生，它是一种经典的内存分配算法，大名鼎鼎的Linux底层的内存管理用的就是它。这里不探讨内核这么复杂实现，而仅仅是将该算法抽象提取出来，同时给出一份及其简洁的源码实现，以便定制扩展。

伙伴分配的实质就是一种特殊的“分离适配”，即将内存按2的幂进行划分，相当于分离出若干个块大小一致的空闲链表，搜索该链表并给出同需求最佳匹配的大小。其优点是快速搜索合并（O(logN)时间复杂度）以及低外部碎片（最佳适配best-fit）；其缺点是内部碎片，因为按2的幂划分块，如果碰上66单位大小，那么必须划分128单位大小的块。但若需求本身就按2的幂分配，比如可以先分配若干个内存池，在其基础上进一步细分就很有吸引力了。

可以在维基百科上找到该算法的描述，大体如是：

分配内存：

1.寻找大小合适的内存块（大于等于所需大小并且最接近2的幂，比如需要27，实际分配32）

1.如果找到了，分配给应用程序。
2.如果没找到，分出合适的内存块。

1.对半分离出高于所需大小的空闲内存块
2.如果分到最低限度，分配这个大小。
3.回溯到步骤1（寻找合适大小的块）
4.重复该步骤直到一个合适的块

…

阅读全文 Read More

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

C++11的Lambda使用一例：华容道求解

2013年10月09日 Solstice 评论 12 条评论 39,908 人阅读

（感谢网友 @bnu_chenshuo 投稿）

华容道是一个有益的智力游戏，游戏规则不再赘述。用计算机求解华容道也是一道不错的编程练习题，为了寻求最少步数，求解程序一般用广度优先搜索算法。华容道的一种常见开局如图 1 所示。

广度优先搜索算法求解华容道的基本步骤：

准备两个“全局变量”，队列 Q 和和集合 S，S 代表“已知局面”。初时 Q 和 S 皆为空。
将初始局面加入队列 Q 的末尾，并将初始局面设为已知。
当队列不为空时，从 Q 的队首取出当前局面 curr。如果队列为空则结束搜索，表明无解。
如果 curr 是最终局面（曹操位于门口，图 2），则结束搜索，否则继续到第 5 步。
考虑 curr 中每个可以移动的棋子，试着上下左右移动一步，得到新局面 next，如果新局面未知（next ∉ S），则把它加入队列 Q，并设为已知。这一步可能产生多个新局面。
回到第2步。

其中“局面已知”并不要求每个棋子的位置相同，而是指棋子的投影的形状相同（代码中用 mask 表示），例如交换图 1 中的张飞和赵云并不产生新局面，这一规定可以大大缩小搜索空间。

以上步骤很容易转换为 C++ 代码，这篇文章重点关注的是第 5 步的实现。

…

阅读全文 Read More

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

C++面试中string类的一种正确写法

2013年10月09日 Solstice 评论 38 条评论 63,954 人阅读

（感谢网友 @bnu_chenshuo 投稿）

C++ 的一个常见面试题是让你实现一个 String 类，限于时间，不可能要求具备 std::string 的功能，但至少要求能正确管理资源。具体来说：

能像 int 类型那样定义变量，并且支持赋值、复制。
能用作函数的参数类型及返回类型。
能用作标准库容器的元素类型，即 vector/list/deque 的 value_type。（用作 std::map 的 key_type 是更进一步的要求，本文从略）。

换言之，你的 String 能让以下代码编译运行通过，并且没有内存方面的错误。

void foo(String x)
{
}

void bar(const String& x)
{
}

String baz()
{
  String ret("world");
  return ret;
}

int main()
{
  String s0;
  String s1("hello");
  String s2(s0);
  String s3 = s1;
  s2 = s1;

  foo(s1);
  bar(s1);
  foo("temporary");
  bar("temporary");
  String s4 = baz();

  std::vector<String> svec;
  svec.push_back(s0);
  svec.push_back(s1);
  svec.push_back(baz());
  svec.push_back("good job");
}

…

阅读全文 Read More

(34 人打了分，平均分： 3.76 )

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

2013年10月02日 Todd 评论 17 条评论 15,725 人阅读

（感谢 @文艺复兴记（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 条评论 56,633 人阅读

（感谢 @文艺复兴记（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,523 人阅读

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

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

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

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

类型的本质

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

…

阅读全文 Read More

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

酷壳 – CoolShell

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

Browsed by
分类：编程语言

一个“蝇量级” C 语言协程库

2014年01月28日 Leo 评论 54 条评论 105,449 人阅读

基于事件驱动模型

函数式编程

2013年12月27日陈皓评论 193 条评论 210,164 人阅读

Lua简明教程

2013年12月03日陈皓评论 124 条评论 263,101 人阅读

运行

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

2013年10月31日 Todd 评论 97 条评论 46,235 人阅读

组件复用技术的局限性

伙伴分配器的一个极简实现

2013年10月09日 Leo 评论 55 条评论 62,187 人阅读

C++11的Lambda使用一例：华容道求解

2013年10月09日 Solstice 评论 12 条评论 39,908 人阅读

C++面试中string类的一种正确写法

2013年10月09日 Solstice 评论 38 条评论 63,954 人阅读

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

2013年10月02日 Todd 评论 17 条评论 15,725 人阅读

数据即代码：元驱动编程

2013年08月09日 Todd 评论 77 条评论 56,633 人阅读

类型的本质和函数式实现

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

类型的本质