📄 preface.html.svn-base
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN"><html><head><link HREF="mailto:drh@microsoft.com" REV="made" TITLE="David R. Hanson"><title>Preface for C Interfaces and Implementations</title></head><body><h1>Preface</h1><p>Programmers are inundated with information about application programming interfaces, orAPIs. Yet, while most programmers use APIs and the libraries that implement them in almostevery application they write, relatively few create and dissemminate new, widelyapplicable, APIs. Indeed, programmers seem to prefer to "roll their own" insteadof searching for a library that might meet their needs, perhaps because it is easier towrite application-specific code than to craft well-designed APIs.</p><p>I'm as guilty as the next programmer: <aHREF="http://www.cs.princeton.edu/software/lcc/">lcc</a>, a compiler for ANSI/ISO Cwritten by Chris Fraser and myself, was built from the ground up. (<tt>lcc</tt> isdescribed in C.W. Fraser and D. R. Hanson, <cite>A Retargetable C Compiler: Design andImplementation</cite>, Addison-Wesley, 1995.) A compiler exemplifies the kind ofapplication for which it possible to use standard interfaces and to create interfaces thatare useful elsewhere. Examples include interfaces for memory management, string and symboltables, and list manipulation. But <tt>lcc</tt> uses only a few routines from the standardC library, and almost none of its code can be used directly in other applications.</p><p>This book advocates a design methodology based on interfaces and their implementations,and it illustrates this methodology by describing 24 interfaces and their implementationsin detail. These interfaces span a large part of the computing spectrum and include datastructures, arithmetic, string processing, and concurrent programming. The implementationsaren't toys — they're designed for use in production code. As described below, thesource code is freely available.</p><p>There's little support in the C programming language for the interface-based designmethodology. Object-oriented languages, like C++ and Modula-3, have language features thatencourage the separation of an interface from its implementation. Interface-based designis independent of any particular language, but it does require more programmer willpowerand vigilance in languages like C, because it's too easy to pollute an interface withimplicit knowledge of its implementation and vice versa.</p><p>Once mastered, however, interface-based design can speed development time by buildingupon a foundation of general-purpose interfaces that can serve many applications. Thefoundation class libraries in some C++ environments are examples of this effect. Increasedreuse of existing software — libraries of interface implementations — reducesinitial development costs. It also reduces maintenance costs, because more of anapplication rests on well-tested implementations of general-purpose interfaces.</p><p>The 24 interfaces come from several sources, and all have been revised for this book.Some of the interfaces for data structures — abstract data types — originated in<code>lcc</code> code, and in implementations of the <aHREF="http://www.cs.arizona.edu/icon/">Icon programming language</a> done in the late1970s and early 1980s (see R. E. Griswold and M. T. Griswold, <cite>The Icon ProgrammingLanguage</cite>, Prentice Hall, 1990). Others come from the published work of otherprogrammers; the "Further Reading" sections at the end of each chapter give thedetails.</p><p>Some of the interfaces are for data structures, but this is not a data structures book,per se. The emphasis is more on algorithm engineering — packaging data structures forgeneral use in applications — than on data-structure algorithms. Good interfacedesign does rely on appropriate data structures and efficient algorithms, however, so thisbook complements traditional data structure and algorithms texts like <aHREF="http://www.cs.princeton.edu/~rs/">Robert Sedgewick's</a> <aHREF="http://www.awl.com/cseng/titles/0-201-31452-5/"><cite>Algorithms in C</cite></a>(Addison-Wesley, 1990).</p><p>Most chapters describe one interface and its implementation; a few describe relatedinterfaces. The "Interface" section in each chapter gives a concise, detaileddescription of the interface alone. For programmers interested only in the interfaces,these sections form a reference manual. A few chapters include "Example"sections, which illustrate the use of one or more interfaces in simple applications.</p><p>The "Implementation" section in each chapter is a detailed tour of the codethat implements the chapter's interface. In a few cases, more than one implementation forthe same interface is described, which illustrates an advantage of interface-based design.These sections are most useful for those modifying or extending an interface or designingrelated interfaces. Many of the exercises explore design and implementation alternatives.It should not be necessary to read an "Implementation" section in order tounderstand how to use an interface.</p><p>The interfaces, examples, and implementations are presented as <em>literate programs</em>;that is, the source code is interleaved with its explanation in an order that best suitsunderstanding the code. The code is extracted automatically from the text files for thisbook and assembled into the order dictated by the C programming language. Otherbook-length examples of literate programming in C include <cite>A Retargetable C Compiler</cite>and <cite>The Stanford GraphBase: A Platform for Combinatorial Computing</cite> by D.E.Knuth (Addison-Wesley, 1993).</p><h2>Organization</h2><p>The material in this book falls into the following broad categories:</p><blockquote> <table CELLPADDING="12"> <tr ALIGN="LEFT" VALIGN="TOP"> <td><i>Foundations</i></td> <td>1. Introduction<br> 2. Interfaces and Implementations<br> 4. Exceptions and Assertions<br> 5. Memory Management<br> 6. More Memory Management</td> </tr> <tr ALIGN="LEFT" VALIGN="TOP"> <td><i>Data Structures</i></td> <td>7. Lists<br> 8. Tables<br> 9. Sets<br> 10. Arrays<br> 11. Sequences<br> 12. Rings<br> 13. Bit Vectors</td> </tr> <tr ALIGN="LEFT" VALIGN="TOP"> <td><i>Strings</i></td> <td>3. Atoms<br> 14. Formatting<br> 15. Low-Level Strings<br> 16. High-Level Strings</td> </tr> <tr ALIGN="LEFT" VALIGN="TOP"> <td><i>Arithmetic</i></td> <td>17. Extended-Precision Arithmetic<br> 18. Arbitrary-Precision Arithmetic<br> 19. Multiple-Precision Arithmetic</td> </tr> <tr ALIGN="LEFT" VALIGN="TOP"> <td><i>Threads</i></td> <td>20. Threads</td> </tr> </table></blockquote><p>Most readers will benefit from reading all of Chapters 1 through 4, because thesechapters form the framework for the rest of the book. The remaining chapters can be readin any order, although some of the later chapters refer to their predecessors.</p><p>Chapter 1 covers literate programming and issues of programming style and efficiency.Chapter 2 motivates and describes the interface-based design methodology, defines therelevant terminology, and tours two simple interfaces and their implementations. Chapter 3describes the prototypical <tt>Atom</tt> interface, which is the simplestproduction-quality interface in this book. [<a HREF="doc/atom.pdf">Download/view Chapter 3</a>,an Adobe Acrobat PDF file (52K).] Chapter 4 introduces exceptions and assertions, whichare used in every interface. Chapters 5 and 6 describe the memory management interfacesused by almost all the implementations. The rest of the chapters each describe aninterface and its implementation.</p><h2>Instructional Use</h2><p>I assume that readers understand C at the level covered in undergraduate introductoryprogramming courses, and have a working understanding of fundamental data structures atthe level presented in texts like <cite>Algorithms in C</cite>. At Princeton, the materialin this book is used in systems programming courses from the sophomore to first-yeargraduate levels. Many of the interfaces use advanced C programming techniques, such asopaque pointers and pointers to pointers, and thus serve as nontrivial examples of thosetechniques, which are useful in systems programming and data structure courses.</p><p>This book can be used for courses in several ways, the simplest being inproject-oriented courses. In a compiler course, for example, students often build acompiler for a toy language. Substantial projects are common in graphics courses as well.Many of the interfaces can simplify the projects in these kinds of courses by eliminating⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -