📄 preface.html.svn-base
字号:
<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN"><HTML><HEAD><LINKHREF="mailto:drh@cs.princeton.edu" 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 programminginterfaces, or APIs. Yet, while most programmers use APIs and the libraries thatimplement them in almost every application they write, relatively few create anddisemminate new, widely applicable, APIs. Indeed, programmers seem to prefer to"roll their own" instead of searching for a library that might meettheir needs, perhaps because it is easier to write application-specific codethan to craft well-designed APIs.</P><P>I'm as guilty as the next programmer:<A HREF="http://www.cs.princeton.edu/software/lcc/">lcc</A>, a compiler forANSI/ISO C written by Chris Fraser and myself, was built from the ground up. (<TT>lcc</TT>is described in C.W. Fraser and D. R. Hanson, <CITE>A Retargetable C Compiler:Design and Implementation</CITE>, Addison-Wesley, 1995.) A compiler exemplifiesthe kind of application for which it possible to use standard interfaces and tocreate interfaces that are useful elsewhere. Examples include interfaces formemory management, string and symbol tables, and list manipulation. But <TT>lcc</TT>uses only a few routines from the standard C library, and almost none of itscode can be used directly in other applications.</P><P>This book advocates a design methodology based on interfaces and theirimplementations, and it illustrates this methodology by describing 24 interfacesand their implementations in detail. These interfaces span a large part of thecomputing spectrum and include data structures, arithmetic, string processing,and concurrent programming. The implementations aren't toys — they'redesigned for use in production code. As described below, the source code isfreely available.</P><P>There's little support in the C programming language for the interface-baseddesign methodology. Object-oriented languages, like C++ and Modula-3, havelanguage features that encourage the separation of an interface from itsimplementation. Interface-based design is independent of any particularlanguage, but it does require more programmer willpower and vigilance inlanguages like C, because it's too easy to pollute an interface with implicitknowledge of its implementation and vice versa.</P><P>Once mastered, however, interface-based design can speed development time bybuilding upon a foundation of general-purpose interfaces that can serve manyapplications. The foundation class libraries in some C++ environments areexamples of this effect. Increased reuse of existing software — librariesof interface implementations — reduces initial development costs. It alsoreduces maintenance costs, because more of an application rests on well-testedimplementations of general-purpose interfaces.</P><P>The 24 interfaces come from several sources, and all have been revised forthis book. Some of the interfaces for data structures — abstract data types— originated in <CODE>lcc</CODE> code, and in implementations of the<A HREF="http://www.cs.arizona.edu/icon/www/">Icon programming language</A>done in the late 1970s and early 1980s (see R. E. Griswold and M. T. Griswold,<CITE>The Icon Programming Language</CITE>, Prentice Hall, 1990). Others comefrom the published work of other programmers; the "Further Reading"sections at the end of each chapter give the details.</P><P>Some of the interfaces are for data structures, but this is not a datastructures book, per se. The emphasis is more on algorithm engineering —packaging data structures for general use in applications — than ondata-structure algorithms. Good interface design does rely on appropriate datastructures and efficient algorithms, however, so this book complementstraditional data structure and algorithms texts like<A HREF="http://www.cs.princeton.edu/~rs/">Robert Sedgewick's</A> <CITE>Algorithmsin C</CITE> (Addison-Wesley, 1990).</P><P>Most chapters describe one interface and its implementation; a few describerelated interfaces. The "Interface" section in each chapter gives aconcise, detailed description of the interface alone. For programmers interestedonly in the interfaces, these sections form a reference manual. A few chaptersinclude "Example" sections, which illustrate the use of one or moreinterfaces in simple applications.</P><P>The "Implementation" section in each chapter is a detailed tour ofthe code that implements the chapter's interface. In a few cases, more than oneimplementation for the same interface is described, which illustrates anadvantage of interface-based design. These sections are most useful for thosemodifying or extending an interface or designing related interfaces. Many of theexercises explore design and implementation alternatives. It should not benecessary to read an "Implementation" section in order to understandhow to use an interface.</P><P>The interfaces, examples, and implementations are presented as <EM>literateprograms</EM>; that is, the source code is interleaved with its explanation inan order that best suits understanding the code. The code is extractedautomatically from the text files for this book and assembled into the orderdictated by the C programming language. Other book-length examples of literateprogramming in C include <CITE>A Retargetable C Compiler</CITE> and <CITE>TheStanford 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 andAssertions<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-LevelStrings</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, becausethese chapters form the framework for the rest of the book. The remainingchapters can be read in any order, although some of the later chapters refer totheir predecessors.</P><P>Chapter 1 covers literate programming and issues of programming style andefficiency. Chapter 2 motivates and describes the interface-based designmethodology, defines the relevant terminology, and tours two simple interfacesand their implementations. Chapter 3 describes the prototypical <TT>Atom</TT>interface, which is the simplest production-quality interface in this book. [<AHREF="atom.pdf">Download/view Chapter 3</A>, an Adobe Acrobat PDF file (52K).]Chapter 4 introduces exceptions and assertions, which are used in everyinterface. Chapters 5 and 6 describe the memory management interfaces used byalmost 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 undergraduateintroductory programming courses, and have a working understanding offundamental data structures at the level presented in texts like <CITE>Algorithmsin C</CITE>. At Princeton, the material in this book is used in systemsprogramming courses from the sophomore to first-year graduate levels. Many ofthe interfaces use advanced C programming techniques, such as opaque pointersand 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 oftenbuild a compiler for a toy language. Substantial projects are common in graphicscourses as well. Many of the interfaces can simplify the projects in these kindsof courses by eliminating some of the grunt programming needed to get such⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -