1.每个程序员都该有本翻烂的K&R

1.1 多次自学,不得其法

距离大学时学习C语言已有十个年头了。印象里最深的就是当时一位海归老师,在讲课时流露出对K&R的崇敬之情,以及用Hanoi塔的例子讲解递归。但当时的我还无法体会,也只是不走心的听听。那时的我还不知道K&R有多牛,递归有多重要。

十年间经历了很多项目,也业余时间自学了很多东西。温习过C、自学过汇编、尝试操作系统内核。看过不少推荐的好书,看语法看得不厌其烦。却始终感觉对C语言既熟悉又陌生,熟悉其语法,陌生的是:这真的就是C语言最精华的部分吗?

1.2 不期而遇,峰回路转

转机就在刚刚结束的一学期高强度的研究生学习。因为之前已经对C的基础知识比较熟悉了,所以这学期并未刻意去系统学习(也确实没有时间)。就在实践中摸爬滚打了一学期,这次让我对C语言有了重新的认识。深深感受到:如果说算法实现只是用C小试牛刀,操作系统内核等底层开发才是让C爆发出强大力量的地方

也许刷题和实现算法时我们还有很多更加现代化的选择,例如C++、Java甚至Python,C语言不过是简洁明了的一种选择罢了。但在像操作系统内核、网络编程、编译器设计等研究生课程中,C简直处于霸主地位。暑假了有时间好好总结了,赶紧趁着感觉还在再深入理解一下。

1.3 不是书不好,只是时候未到

拿着这一本《The C Programming Language》,感到非常惊奇!这样一本古老的、薄薄的书,竟然霸占了所有编程类推荐书目榜单的前列。个中原因,多少年来我一直找不到答案。最近重读K&R,满打满算应该是第三次了,终于被深深震撼到了:第一次读看到的是满篇的语法规则,第二次读看到的是各种巧妙的编程手法,而第三次重读看到的却哪里是C语言,这简直就是OS内核和编译原理嘛!

kr
“Everyone should have a copy of K+R. And it should look beaten up, like this one does.” – 《Operating Systems: Three Easy Pieces》


2.简洁至极的语法

按照K&R的内容编排来看,第一章是列举了C语言的所有核心知识点以及实用的小例子:C语言由变量(基本类型和结构)、函数、地址(指针)、控制结构、宏。没别的了,就这些!其他什么字符串相关的函数啊、输入输出啊、链表哈希表啊,统统没有,程序员你们自己搞定吧!正如第一章末尾所说,仔细看完第一章后完全可以停下来,用C写出很多实用的小程序了!而这些语法的详细介绍也不过是第二到第六章一共五章就说完了,真是简洁至极:

  1. Type + Operator = Expression
    • 基本数据类型(Type):char、int、float、double。其中,int可以加short/long修饰(可以省略int)。编译器只保证:short/int至少16位,long至少32位,并且short长度不大于int,int不大于long。此外,char和int还可以加signed或unsigned修饰。
    • 常量(Constants):l或L表示long、f或F或1.0e-2表示float、0表示八进制、0x或0X表示十六进制,u或者U表示unsigned、单引号表示字符常量(特殊转义字符)。常量间可以组成常量表达式,在编译时直接被解析。const可用于任何类型,甚至是数组,表示变量或数组元素不可变。
    • 枚举(Enumeration):相对于#define,枚举有三个优点:自动产生关联的值、提供类型检查机会、调试器能够识别变量名。(这学期调试OS内核时看不到各种#define定义的值……)
    • 操作符(Operator):赋值操作、算术运算、关系运算、逻辑运算、位运算。
  2. Control Flow
    • switch的fall-through:C为了支持多个case共享一个代码段,如果case中返回的话会自动进入下一个case的代码段中,但这也极易导致错误。这也是作者设计时的trade-off吧,后起之秀Golang就将默认行为改为自动退出switch。
    • 执行顺序:for循环的执行顺序是初始化=>测试=>循环体=>测试=>循环体……
    • while还是for:while适合没有初始化/重初始化(例如while((c=getchar()) == ’ ’ || c == ‘\n’))或者这两者比较复杂需要单独列出的情况,而for则适合这两者都很简单的情况。
  3. Function & Program Structure
    • 外部类型(External):C的函数不能嵌套定义其他函数,所以函数总是external的。external变量或函数的作用域是从定义处到文件末尾,所以如果要在定义前或者其他文件引用的话,就要使用extern关键字或函数原型声明。定义处(definition)同时起到声明和内存分配的作用,而其他引用处只是声明(declaration)让编译器产生符号而已,过后链接器会找到定义
    • 静态类型(Static):通过static关键字能将external变量或函数的作用域限制在定义处之后的当前文件内容。在函数内声明static变量,能够得到一个对当前函数私有并且持久存储的变量。
    • 寄存器类型(Register):慎用!因为编译器会根据当前硬件架构的寄存器数目决定是否真的会把变量保存到寄存器,也就是说我们只是建议编译器。但换来一个必然结果却是register类型的变量无法通过&操作符取地址,不管它最终是否保存在寄存器里。
    • 宏替换(Macro Substitution)
      • 替换只作用于实实在在的token,不会发生在引号中的字符串
      • 宏参数千万别忘了用括号括起来
      • 不像函数,宏对所有数据类型都有效,例如#define max(A,B) ((A) > (B) ? (A) : (B)),于是省掉了定义各种入参类型函数的麻烦
      • 一定避免宏入参的副作用,例如max(i++,j++)
      • 宏能避免运行时函数调用的开销
      • 宏参数能拼接字符串,例如#define dprint(expr) printf(#expr ” = %g\n”, expr)
      • 宏参数也能互相拼接产生新token,例如#define paste(a, b) a ## b
  4. Pointer
    • 声明习惯:指针变量的声明模仿了变量在表达式中使用时的样子,所以星号一定要紧贴变量名,而不是类型名。
    • 数组与指针:“数组+下标”的方式完全等同于“指针+偏移”的方式。格外注意一点:数组名不是变量,不能赋值给其他指针变量,也不能自增自减等操作。对数组、指针、地址运算的统一是C语言的一大优势,包括指针赋值、加减指针和整数、减去或比较两个同类型指针、赋值0或与0比较。还有些小技巧比如通过传入类似&a[2],函数就像在操作子数组一样,以及负数下表等。
    • 多维数组(Multi-dimensional Arrays):二维数组作为参数传入函数时必须包含列数,例如f(int daytab[][13])。更节省空间的做法是声明指针数组,这在字符串处理程序中很常见,例如char *name[10]。
    • 函数指针(Pointers to Functions):函数指针可用于赋值、保存与数组、作为函数入参或返回值。若想做成通用的函数模板,则参数可声明为void *,例如int (*comp)(void *, void *)。
  5. Structure
    • 结构名(Structure Tag):struct后的名字是可有可无,只是为了方便后面单独声明结构变量用的。
    • sizeof:是编译时指令,可用于任何变量类型,并且无运行时消耗。让编译器判断类型长度,这样代码有更好的移植性。也正因此,sizeof可用于#define,但不可用于#if条件编译,因为Preprocessor不解析类型名。
    • 自引用(Self-referential Structure):结构包含自己是非法的,但是包含指针同类型的指针却是合法的,例如struct node {struct node *left;}。
    • typedef:typedef只是为现有类型创建个别名,它并不会真正创建任何新类型。但使用typedef有两个好处:
      • 将代码参数化(Parameterize)从而提高可移植性。当移植时,只有typedef涉及的机器平台相关的代码需要改动。
      • 此外就是代码可读性更高。例如Treeptr要比普通的struct指针更好理解一些。
    • Unions:Union能容纳下我们声明的变量中最长的,但具体目前保存的是哪个,则是我们程序员的责任。如果存取不一致,那么就会出错。

第一次读此书,大概也就是这种程度了,眼中全是C语言的语法。初学时比较畅快,渐渐觉得这没有什么啊,很多地方跟Java都很像的。于是没有了新鲜感,对C的了解也停滞了……


3.经典的编程技巧

多年后再读K&R,发现其中有很多实用的实例程序。这些程序非常经典,涉及到了计算机科学的方方面面,从侧面反映出C语言应用之广。下面做一下简单的整理,页码对应英文原版:

  • P18-wc:统计字符数、字数、行数等,即命令行中的wc。
  • P62-Shell Sort:用C实现算法Shell排序,简洁明了!
  • P74-Reverse Polish:用栈实现一个逆波兰表达式的计算器。
  • P87-Binary Search:经典的二分查找实现。
  • P100-Bump Allocator:简单的内存管理器,这学期OS课正好学到,就叫Bump分配器。
  • P117-Cli Argument Parser:命令行参数解析的范例。
  • P122-Token Parser:解析一小段源代码中的符号。
  • P141-BST:经典的二叉查找树的递归实现。
  • P145-Chained Hashtable:简单的哈希表,用链表解决冲突。

但限于篇幅,本节只列举一些能够反映C语言编程特点和技巧的“迷你”实例,其他程序就不一一列举了,在遇到相关问题时再直接去翻书吧。

3.1 ASCII字符和数字转换

由于ASCII字符集的特点,’a’~’z’、’A’~’Z’、’0’~’9’都是连续的,并且根据转换规则,char作为小整数可以与int随意比较和运算,所以才有了下面代码中的小技巧。如果换做其他字符集的话,可就不一定了。所以书中推荐使用C标准库中的通用函数,例如isdigit(c)而不是自己判断c >= ‘0’ && c <= ‘9’。类似的例子有atoi、itoa、atof、ftoa等,可以参考学习。

/* atoi: convert s to integer */
int atoi(char s[])
{
    int i, n;

    n = 0;
    for (i = 0; s[i] >= '0' && s[i] <= '9'; ++i)
        n = 10 * n + (s[i] - '0');
    return n;
}

/* lower: convert c to lower case; ASCII only */
int lower(int c)
{
    if (c >= 'A' && c <= 'Z')
        return c + 'a' - 'A';
    else
        return c;
}

3.2 烧脑的位运算

一个小例子,注意类似~077这种写法移植性高,而且是编译时求值的,也就是说运行时没有任何额外消耗:

/* getbits: get n bits from position p */
unsigned getbits(unsigned x, int p, int n)
{
    return (x >> (p+1-n)) & ~(~0 << n);
}

第六章中提到了可读性更好的Bit-fields类型,例如声明一个三个Bit的变量flags,然后直接对flags中具体某一位进行操作:

阿里云-推广AD
struct {
    unsigned int is_keyword : 1;
    unsigned int is_extern  : 1;
    unsigned int is_static  : 1;
} flags;

flags.is_keyword = 0;
flags.is_extern = 1;

3.3 反向处理字符串

对于C老兵来说这肯定不算什么了,但个人觉得这还是值得一提的,因为我以前面试时就曾被问到过。思路很简单,先遍历到最末尾,再从后往前处理。此外,字符串以’\0’结尾,长度等于实际声明长度+1。

/* trim: remove trailing blanks, tabs, newlines */
int trim(char s[])
{
    int n;

    for (n = strlen(s)-1; n >= 0; n--)
        if (s[n] != ' ' && s[n] != '\t' && s[n] != '\n')
            break;
    s[n+1] = '\0';
    return n;
}

3.4 简洁指针操作

最传统的写法就是数组操作,在像Java等没有指针的语言里最常见不过了。而C的传统则是用指针,尽可能简洁地表达。这段代码展现三个重要的C-ism惯例:

  1. 在while条件部分同时进行变量初始化和更新,从而简化body
  2. 省略显示的条件比较,赋值表达式左侧变量值为结果,任何不为0都表示真
  3. 像*s++这种形式很常见,相当于先*s = *t后,再s++和t++
/* strcpy: copy t to s; array subscript version */
void strcpy(char *s, char *t)
{
    int i;

    i = 0;
    while ((s[i] = t[i]) != '\0')
        i++;
}

/* strcpy: copy t to s; pointer version 3 */
void strcpy(char *s, char *t)
{
    while (*s++ = *t++)
        ;
}

4.深层分析思考

上完研究生第一学期的课程后,三读K&R,开始有了些感觉。在刚过去的这一学期摸爬滚打地赶due,攒下了不少C语言方面的疑惑。终于到了暑假,买了本英文原版的K&R,好好拜读一下原作。结合之前积累的各种知识,深入观察一下C语言世界的整个面貌。

4.1 短路、控制结构、Goto和汇编语言

C的逻辑运算具有“短路”效果,只要能判断出整个表达式的真假后就立即停止执行。许多C程序都依赖这条特性,例如:

for (i=0; i<lim-1 && (c=getchar()) != '\n' && c != EOF; ++i)
    s[i] = c;

但你有没有想过这是为什么呢?之前在《六星经典CSAPP-笔记(3)程序的机器级表示》的“5.逻辑运算为什么要短路”中曾经分析过。其实不只是逻辑运算,像for和while循环、复杂的自增表达等等,在底层汇编语言中都是被“打碎”成了简单的线性执行+jmp。这也就是为什么在相对高级的C语言中不要使用Goto语句,因为这会使我们的代码又回归到了底层,变得难以理解。

4.2 操作符优先级和编译器

我们经常会写出类似上面for循环中的那种复杂的条件表达式,我们理所当然的认为它会按我们所想的去执行。其实深入一下会发现,支撑其正确执行的是语法的操作符优先级和求值顺序,算术运算符 高于 关系运算符 高于 逻辑运算符。因为还没有深入学习编译原理,所以这一部分先不展开说了。

4.3 类型转换与反码

强制类型转换就好比应用软件里删除等重要操作前弹出的对话框,软件与用户进行二次确认。同样地,C与程序员进行再确认,让程序员自己知道在做什么,有什么后果,然后C就放手不管了。类型转换的本质到底是什么,请移步至《六星经典CSAPP-笔记(3)程序的机器级表示》的“4.类型转换时发生了什么”中有详细的分析。这一部分目前理解的还不够深,准备在后续学习计算机体系结构时再好好总结一下。

4.4 变量初始化与加载器

external变量和static变量会被初始化为0,并且只在程序开始执行前初始化一次。因为这部分工作是加载器(Loader)在加载我们的可执行文件(如ELF)时完成的。详情请见稍后将发的,关于JOS及操作系统内核的文章。此外,external和static变量会一直存在于内存中,它们都有着更长的生命周期。所谓更长的生命,只是说它所占的那块内存地址会一直为它保留,直到程序退出。

4.6 函数传参与栈结构

automatic变量和register变量在每次调用函数都会分配空间,如果不初始化的话将会是“垃圾”值。这个很好理解了,因为函数栈是动态分配和销毁的。而所谓的分配和销毁也只是移动ebp和esp寄存器的值,去指向不同的栈顶和栈底位置而已。所以,如果我们不显示初始化的话,很可能变量保存的就是一个莫名其妙的值。在《六星经典CSAPP-笔记(3)程序的机器级表示》的“7.运行时的代码与栈”中有详细的分析。

4.7 作用域与链接器

extern和static能够控制函数和变量的作用域,其实控制的也是编译时Symbol的产生。链接时Linker再将占位用的Symbol替换成真正的地址。对编译链接有些概念后,碰到C语言编译方面的错误能有很大帮助。在《六星经典CSAPP-笔记(7)加载与链接(上)》中对编译、静态链接有详细的总结。


5.结束语:学习C语言是个长期过程

读完本文能够感受到C语言已经超出了单单一门语言的范畴,其背后的文化和底蕴,非一朝一夕就能够精通的。从计算机系统架构、操作系统内核、编译链接等知识的交汇,到Unix文化和设计思想,真的是博大精深!所以,在整个编程生涯中,对于如C语言这种经典的老技术,我们都应反反复复去琢磨、去领会。相信总有一天能悟到真理。想写一篇关于K&R和C语言的文章想很久了,迟迟不知该如何落笔,内容很散无从写起。这一篇总算是总结出了些干货,也还算让自己满意吧~