C语言接口与实现:创建可重用软件的技术（英文版）（C语言程序员不可多得的好书）

4.2 Implementation 53
4.3 Assertions 59
Further Reading 63
Exercises 64
5 Memory Management 67
5.1 Interface 69
5.2 Production Implementation 73
5.3 Checking Implementation 76
Further Reading 85
Exercises 86
6 More Memory Management 89
6.1 Interface 90
6.2 Implementation 92
Further Reading 98
Exercises 100
7 Lists 103
7.1 Interface 103
7.2 Implementation 108
Further Reading 113
Exercises 114
8 Tables 115
8.1 Interface 115
8.2 Example: Word Frequencies 118
8.3 Implementation 12 5
Further Reading 132
Exercises 133
9 Sets 137
9.1 Interface 138
9.2 Example: Cross-Reference Listings 140
9.3 Implementation 148
9.3.1 Member Operations 150
9.3.2 Set Operations 154
Further Reading 158
Exercises 158
10 Dynamic Arrays
10.1 Interfaces 162
10.2 Implementation 165
Further Reading 169
Exercises 169
11 Sequences 171
11.1 Interface 171
11.2 Implementation 174
Further Reading 180
Exercises 180
12 Rings 183
12.1 Interface 183
12.2 Implementation 187
Further Reading 196
Exercises 197
13 Bit Vectors 199
13.1 Interface 199
13.2 Implementation 202
13.2.1 Member Operations 204
13.2.2 Comparisons 209
13.2.3 Set Operations 211
Further Reading 213
Exercises 21314 Formatting 215
14.1 Interface 216
14.1.1 Formatting Functions 216
14.1.2 Conversion Functions 219
14.2 Implementation 224
14.2.1 Formatting Functions 225
14.2.2 Conversion Functions 232
Further Reading 238
Exercises 239
15 Low-LevelStrings 241
15.1 Interface 243
15.2 Example: Printing Identifiers 249
15.3 Implementation 251
15.3.1 String Operations 252
15.3.2 Analyzing Strings 258
15.3.3 Conversion Functions 263
Further Reading 264
Exercises 265
16 High-LevelStrings 269
16.1 Interface 269
16.2 Implementation 276
16.2.1 String Operations 281
16.2.2 Memory Management 285
16.2.3 Analyzing Strings 288
16.2.4 Conversion Functions 293
Further Reading 293
Exercises 294
17 Extended-Precision Arithmetic 297
17.1 Interface 297
17.2 Implementation 303
17.2.1 Addition and Subtraction 305
17.2.2 Multiplication 307
17.2.3 Division and Comparison 309
17.2.4 Shifting 315
17.2.5 String Conversions 319
Further Reading 321
Exercises 322
18 Arbitrary-Precision Arithmetic 323
18.1 Interface 323
18.2 Example: A Calculator 327
18.3 Implementation 334
18.3.1 Negation and Multiplication 337
18.3.2 Addition and Subtraction 338
18.3.3 Division 342
18.3.4 Exponentiation 343
18.3.5 Comparisons 346
18.3.6 Convenience Functions 347
18.3.7 Shifting 349
18.3.8 String and Integer Conversions 350
Further Reading 353
Exercises 354
19 Multiple-Precision Arithmetic 357
19.1 Interface 358
19.2 Example: Another Calculator 365
19.3 Implementation 373
19.3.1 Conversions 377
19.3.2 Unsigned Arithmetic 380
19.3.3 Signed Arithmetic 383
19.3.4 Convenience Functions 388
19.3.5 Comparisons and Logical Operations 395
19.3.6 String Conversions 399
Further Reading 402
Exercises 402
20 Threads 405
20.1 Interfaces 408
20.1.1 Threads 409
20.1.2 General Semaphores 413
20.1.3 Synchronous Communication Channels 417
20.2 Examples 418
20.2.1 Sorting Concurrently 418
20.2.2 Critical Regions 423
20.2.3 Generating Primes 426
20.3 Implementations 431
20.3.1 Synchronous Communication Channels 431
20.3.2 Threads 434
20.3.3 Thread Creation and Context-Switching 446
20.3.4 Preemption 454
20.3.5 General Semaphores 457
20.3.6 Context-Switching on the MIPS and ALPHA 459
Further Reading 463
Exercises 465
Interface Summary 469
Bibliography 497
Index 505

.　　10. 动态数组
　　11. 序列
　　12. 环
　　13. 位向量
　　字符串 3. 原子
　　14. 格式化
　　15. 低级字符串
　　16. 高级字符串
　　算法 17. 扩展精度算法
　　18. 任意精度算法
　　19. 多精度算法
　　线程 20. 线程
　　建议大多数读者通读第1～4章的内容，因为这几章形成了本书其余部分的框架。对于剩下的5～20章，虽然某些章会参考其前面的内容，但影响不大，读者可以按任何顺序阅读。
　　第1章介绍了literate程序设计和编程风格与效率。第2章提出并描述了基于接口的设计方法，定义了相关的术语，并演示了两个简单的接口及其实现。第3章描述了Atom接口的实现原型，这是本书中最简单的具有产品质量的接口。第4章介绍了在每一个接口中都会用到的异常与断言。第5章和第6章描述了几乎所有的实现都会用到的内存管理接口。其余各章都分别描述了一个接口及其实现。
　　教学使用建议
　　我们假设本书的读者已经在大学介绍性的编程课程中了解了C语言，并且都实际了解了类似《C算法》一书中给出的基本数据结构。在普林斯顿，本书是大学二年级学生到研究生一年级的系统编程课程的教材。许多接口使用的都是高级C语言编程技巧，比如说不透明的指针和指向指针的指针等，因此这些接口都是学习这些内容非常好的实例，对于系统编程和数据结构课程非常有用。
　　这本书可以以多种方式在课堂上使用，最简单的就是用在面向项目的课程中。例如，在编译原理课程中，学生通常需要为一个玩具语言编写一个编译器。在图形学课程中同样也经常有一些实际的项目。本书中许多接口消除了新建项目所需要的一些令人厌烦的编程工作，从而简化了这类课程中的项目。这种用法可以帮助学生认识到在项目中重用代码可以节省大量劳动，并且引导学生在其项目中对自己所做的部分尝试使用基于接口的设计。后者在团队项目中特别有用，因为“现实世界”中的项目通常都是团队项目。
　　普林斯顿大学二年级系统编程课程的主要内容是接口与实现，其课外作业要求学生成为接口的用户、实现者和设计者。例如其中的一个作业是这样的，我给出了8.1节中描述的Table接口、它的实现的目标代码以及8.2节中描述的单词频率程序wf的说明，让学生只使用我们为Table设计的目标代码来实现wf。在下一个作业中，wf的目标代码就有了，他们必须实现Table。有时我会颠倒这些作业的顺序，但是这两种顺序对大部分学生来说都是很新颖的。他们不习惯在大部分程序中只使用目标代码，并且这些作业通常都是他们第一次接触到在接口和程序说明中使用半正式表示法。
　　最初布置的作业也介绍了作为接口说明必要组成部分的可检查的运行时错误和断言。同样，只有做过几次这样的作业之后，学生们才开始理解这些概念的意义。我禁止了突发性崩溃，即不是由断言错误的诊断所宣布的崩溃。运行崩溃的程序将被判为零分，这样做似乎过于苛刻，但是它能够引起学生们的注意，而且也能够让学生理解安全语言的好处，例如ML和Modula-3，在这些语言中，不会出现突发性崩溃。（这种评分方法实际上没有那么苛刻，因为在分成多个部分的作业中，只有产生冲突的那部分作业才会判为错误，而且不同的作业权重也不同。我给过许多0分，但是从来没有因此导致任何一个学生的课程总成绩降低达1分。）
　　一旦学生们有了自己的几个接口后，接下来就让他们设计新的接口并沿用以前的设计选择。例如，Andrew Appel最喜欢的一个作业是一个原始的测试程序。学生们以组为单位设计一个作业需要的任意算术精度的接口，作业的结果类似于第17章到第19章中描述的接口。不同的组设计的接口不同，完成后对这些接口进行比较，一个组对另一个组设计的接口进行评价，这样做很有启迪作用。Kai Li的那个需要一个学期来完成的项目也达到了同样的学习实践效果，该项目使用Tcl/Tk系统（参见J.K. Ousterhout所著的Tcl and the Tk Toolkit）以及学生们设计和实现的编辑程序专用的接口，构建了一个基于X的编辑程序。Tk本身就是一个很好的基于接口的设计。
　　在高级课程中，我通常把作业打包成接口，学生可以自行修改和改进，甚至改变作业的目标。给学生设置一个起点可以减少他们完成作业所需的时间，允许他们做一些实质性的修改鼓励了有创造性的学生去探索新的解决办法。通常，那些不成功的方法比成功的方法更让学生记忆深刻。学生不可避免地会走错路，为此也付出了更多的开发时间。但只有当他们事后再回过头来看，才会了解所犯的错误，也才会知道设计一个好的接口虽然很困难，但是值得付出努力，而且到最后，他们几乎都会转到基于接口的设计上来。
　　如何得到代码
　　本书中的代码已经在以下平台上通过了测试：
　　处 理 器 操作系统 编 译 器
　　SPARC SunOS 4.1 lcc 3.5
　　gcc 2.7.2
　　Alpha OSF/1 3.2A lcc 4.0
　　gcc 2.6.3
　　cc
　　MIPS R3000 IRIX 5.3 lcc 3.5
　　gcc 2.6.3
　　cc
　　MIPS R3000 Ultrix 4.3 lcc 3.5
　　gcc 2.5.7
　　Pentium Windows 95 Microsoft Visual C/C++ 4.0
　　Windows NT 3.51
　　其中几个实现是针对特定机器的。这些实现假设机器使用的是二进制补码表示的整数和IEEE浮点算术，并且无符号的长整数可以用来保存对象指针。
　　本书中所有的源代码在ftp.cs.princeton.edu的目录pub/packages/cii下，匿名登录就可以下载。使用ftp客户端软件连接到ftp.cs.princeton.edu，转到pub/packages/cii目录，下载README文件，文件中说明了目录的内容以及如何下载。
　　大多数最新的实现通常都是以ciixy.tar.gz或ciixy.zip的文件名存储的，其中xy是版本号，例如10是指版本1.0。ciixy.tar.gz是用gzip压缩的UNIX tar文件，而ciixy.zip是与PKZIP 2.04g版兼容的ZIP文件。ciixy.zip中的文件都是DOS/Windows下的文本文件，每行均以回车和换行符结束。ciixy.zip同时也可以在美国在线、CompuServe以及其他在线服务器上下载。
　　登录http://www.cs.princeton.edu/software/cii/上同样也可以得到相应的信息。该页面还解释了如何报告勘误。
　　致谢
　　自20世纪70年代末以来，在我的科研项目以及在亚利桑那大学和普林斯顿大学的讲课中，我就已经使用过本书中的一些接口。选这些课程的学生最早试用了我设计的这些接口。这些年来他们的反馈凝结在本书代码与说明之中。我要特别感谢普林斯顿大学选修COS 217和COS 596课程的学生，正是他们在不知不觉中参与了本书中大多数接口的初步设计。
　　利用接口开发是DEC公司1（DEC公司已被Compaq收购。——编者注）的系统研究中心（System Research Center，SRC）的主要工作方式，1992年和1993年暑假我在SRC从事Modula-3项目开发，亲身的工作经历消除了我对这种方法有效性的怀疑。我非常感谢SRC对我工作的支持，以及Bill Kalsow、Eric Muller和Greg Nelson与我进行的多次富有启迪的讨论。
　　我还要感谢IDA在普林斯顿的通信研究中心（Center for Communications Research，CCR）和La Jolla，感谢他们在1994年暑假和1995-1996整个休假年对我的支持。还要感谢CCR为我提供了一个理想的地方，让我从容规划并完成了本书。
　　与同事和学生的技术交流也在许多方面完善了本书。一些即使看上去不相关的讨论也促使我对代码及其说明做了改进。感谢Andrew Appel、Greg Astfalk、Jack Davidson、John Ellis、Mary Fernandez、Chris Fraser、Alex Gounares、Kai Li、Jacob Navia、Maylee Noah、Rob Pike、Bill Plauger、John Reppy、Anne Rogers和Richard Stevens。感谢Rex Jaeschke、Brian Kernighan、Taj Khattra、Richard O’Keefe、Norman Ramsey和David Spuler，他们仔细阅读了本书的代码和内容，为本书的成功做出了不可磨灭的贡献。