http:^^www.cs.princeton.edu^courses^cs217^etc^pike.html

This data set contains WWW-pages collected from computer science departments of various universities

<h2>Procedure names</h2>

Procedure names should reflect what they do; function names should
reflect what they
<em>return</em>.
Functions are used in expressions, often in things like
if's,
so they need to read appropriately.
<pre>if(checksize(x))
</pre>
is unhelpful because we can't deduce whether <tt>checksize</tt> returns true on
error or non-error; instead
<pre>if(validsize(x))
</pre>
makes the point clear and makes a future mistake in using the routine
less likely.<p>

<h2>Comments</h2>

A delicate matter, requiring taste and judgement.
I tend to err on the side of eliminating comments, for several reasons.
First, if the code is clear, and uses good type names and variable names,
it should explain itself.
Second, comments aren't checked by the compiler,
so there is no guarantee they're right,
especially after the code is modified.
A misleading comment can be very confusing.
Third, the issue of typography: comments clutter code.<p>

But I do comment sometimes.
Almost exclusively, I use them as an introduction to what follows.
Examples: explaining the use of global variables and types
(the one thing I always comment in large programs);
as an introduction to an unusual or critical procedure;
or to mark off sections of a large computation.<p>

There is a famously bad comment style:
<pre>i=i+1;        /* Add one to i */
</pre>
and there are worse ways to do it:
<pre>/**********************************
 *                                *
 *          Add one to i          *
 *                                *
 **********************************/

               i=i+1;
</pre>
Don't laugh now, wait until you see it in real life.<p>

Avoid cute typography in comments,
avoid big blocks of comments except perhaps before vital
sections like the declaration of the central data structure
(comments on data are usually much more helpful than
on algorithms);
basically, avoid comments.
If your code needs a comment to be understood, it would be better
to rewrite it so it's easier to understand.
Which brings us to<p>

<h2>Complexity</h2>

Most programs are too complicated - that is,
more complex than they need to be to solve their problems efficiently.
Why?
Mostly it's because of bad design,
but I will skip that issue here because it's a big one.
But programs are often complicated
at the microscopic level,
and that is something I can address here.<p>

<dl>
<dt>Rule 1.
You can't tell where a program is going to spend its time.
Bottlenecks occur in surprising places, so don't
try to second guess and put in a speed hack until you've
proven that's where the bottleneck is.<p>

<dt>Rule 2.
Measure.
Don't tune for speed until you've measured,
and even then don't unless one part of the code
<em>overwhelms</em>
the rest.<p>

<dt>Rule 3.
Fancy algorithms are slow when
<em>n</em>
is small, and
<em>n</em>
is usually small.
Fancy algorithms have big constants.
Until you know that
<em>n</em>
is frequently going to be big,
don't get fancy.
(Even if
<em>n</em>
does get big, use Rule 2 first.)
For example, binary trees are always faster than splay trees for
workaday problems.<p>

<dt>Rule 4.
Fancy algorithms are buggier than simple ones,
and they're much harder to implement.
Use simple algorithms as well as simple data structures.<p>

The following data structures are a complete list for almost
all practical programs:
<dl>
<dt>array
<dt>linked list
<dt>hash table
<dt>binary tree
</dl>
Of course, you must also be prepared to collect these into compound
data structures.
For instance, a symbol table might be implemented as a hash table
containing linked lists of arrays of characters.<p>

<dt>Rule 5.
Data dominates.
If you've chosen the right data structures and organized things well,
the algorithms will almost always be self-evident.
Data structures, not algorithms, are central to programming.
(See Brooks p. 102.)<p>

<dt>Rule 6.
There is no Rule 6.<p>
</dl>

<h2>Programming with data</h2>

Algorithms, or details of algorithms,
can often be encoded compactly, efficiently and expressively as data
rather than, say, as lots of
<tt>if</tt>
statements.
The reason is that the
<em>complexity</em>
of the job at hand, if it is due to a combination of
independent details,
<em>can be encoded</em>.
A classic example of this is parsing tables,
which encode the grammar of a programming language
in a form interpretable by a fixed, fairly simple
piece of code.
Finite state machines are particularly amenable to this
form of attack, but almost any program that involves
the `parsing' of some abstract sort of input into a sequence
of some independent `actions' can be constructed profitably
as a data-driven algorithm.<p>

Perhaps the most intriguing aspect of this kind of design
is that the tables can sometimes be generated by another
program - a parser generator, in the classical case.
As a more earthy example, if an operating system is driven
by a set of tables that connect I/O requests to the appropriate
device drivers, the system may be `configured'
by a program that reads a description of the particular
devices connected to the machine in question and prints
the corresponding tables.<p>

One of the reasons data-driven programs are not common, at least
among beginners, is the tyranny of Pascal.
Pascal, like its creator, believes firmly in the separation
of code and data.
It therefore (at least in its original form) has no ability to
create initialized data.
This flies in the face of the theories of Turing and von Neumann,
which define the basic principles of the stored-program computer.
Code and data
<em>are</em>
the same, or at least they can be.
How else can you explain how a compiler works?
(Functional languages have a similar problem with I/O.)<p>

<h2>Function pointers</h2>

Another result of the tyranny of Pascal is that beginners don't use
function pointers.
(You can't have function-valued variables in Pascal.)
Using function pointers to encode complexity has some interesting
properties.<p>

Some of the complexity is passed to the routine pointed to.
The routine must obey some standard protocol - it's one of a set
of routines invoked identically - but beyond that, what it
does is its business alone.
The complexity is
<em>distributed</em>.<p>

There is this idea of a protocol, in that all functions used similarly
must behave similarly. This makes for easy documentation, testing,
growth and even making the program run distributed over a network -
the protocol can be encoded as remote procedure calls.<p>

I argue that clear use of function pointers is the heart of object-oriented
programming. Given a set of operations you want to perform on data,
and a set of data types you want to respond to those operations,
the easiest way to put the program together is with a group of function
pointers for each type.
This, in a nutshell, defines class and method.
The O-O languages give you more of course - prettier syntax,
derived types and so on - but conceptually they provide little extra.<p>

Combining data-driven programs with function pointers leads to an
astonishingly expressive way of working, a way that, in my experience,
has often led to pleasant surprises. Even without a special O-O
language, you can get 90% of the benefit for no extra work and be
more in control of the result.
I cannot recommend an implementation style more highly.
All the programs I have organized this way have survived comfortably
after much development - far better than with less disciplined
approaches.
Maybe that's it: the discipline it forces pays off handsomely in the long run.<p>

<h2>Include files</h2>

Simple rule: include files should never include include files.
If instead they state (in comments or implicitly) what files they need to have
included first, the problem of deciding which files to include
is pushed to the user (programmer) but in a way that's easy to handle
and that, by construction, avoids multiple inclusions.
Multiple inclusions are a bane of systems programming.
It's not rare to have files included five or more times to
compile a single C source file.
The Unix
<tt>/usr/include/sys</tt>
stuff is terrible this way.<p>

There's a little dance involving
<tt>#ifdef</tt>'s
that can prevent a file being read twice, but it's usually done
wrong in practice - the
<tt>#ifdef</tt>'s
are in the file itself, not the file that includes it.
The result is often thousands of needless lines of code
passing through the lexical analyzer, which is (in good compilers)
the most expensive phase.<p>

Just follow the simple rule.<p>

<hr>
<address>
Rob Pike / [e-mail] / Sep. 1987
</address>
</BODY>