home *** CD-ROM | disk | FTP | other *** search
/ ftp.cse.unsw.edu.au / 2014.06.ftp.cse.unsw.edu.au.tar / ftp.cse.unsw.edu.au / pub / doc / papers / misc / cs.toronto.edu:programming / pikestyle.ms < prev    next >
Encoding:
Text File  |  1992-10-18  |  15.6 KB  |  501 lines

  1. .so CW.ms
  2. .TL
  3. Notes on Programming in C
  4. .AU
  5. Rob Pike
  6. .SH
  7. Introduction
  8. .PP
  9. Kernighan and Plauger's
  10. .I
  11. The Elements of Programming Style
  12. .R
  13. was an important and rightly influential book.
  14. But sometimes I feel its concise rules were taken as a cookbook
  15. approach to good style instead of the succinct expression of a philosophy
  16. they were meant to be.
  17. If the book claims that variable names should be chosen
  18. meaningfully, doesn't it then follow that variables whose names are
  19. small essays on their use are even better?
  20. Isn't
  21. .CW MaximumValueUntilOverflow
  22. a better name than
  23. .CW maxval ?
  24. I don't think so.
  25. .PP
  26. What follows is a set of short essays that collectively
  27. encourage a philosophy of clarity in programming rather than
  28. giving hard rules.
  29. I don't expect you to agree with all of them,
  30. because they are opinion and opinions change with the times.
  31. But they've been accumulating in my head, if not on paper
  32. until now, for a long time, and are based on a lot of experience,
  33. so I hope they help you understand
  34. how to plan the details of a program.
  35. (I've yet to see a good essay on how to plan the whole thing,
  36. but then that's partly what this course is about.)
  37. If you find them idiosyncratic, fine;
  38. if you disagree with them, fine;
  39. but if they make you think about why you disagree, that's better.
  40. Under no circumstances should you program the way I say to
  41. because I say to; program the way you think expresses best
  42. what you're trying to accomplish in the program.
  43. And do so consistently and ruthlessly.
  44. .PP
  45. Your comments are welcome.
  46. .SH
  47. Issues of typography
  48. .PP
  49. A program is a sort of publication.
  50. It's meant to be read by the programmer,
  51. another programmer (perhaps yourself a few days, weeks or years later),
  52. and lastly a machine.
  53. The machine doesn't care how pretty the program is \(em
  54. if the program compiles, the machine's happy \(em
  55. but people do, and they should.
  56. Sometimes they care too much: pretty printers
  57. mechanically produce pretty output that accentuates irrelevant detail in
  58. the program, which is
  59. .B as
  60. sensible
  61. .B as
  62. putting all the prepositions
  63. .B in
  64. English text
  65. .B in
  66. bold font.
  67. Although many people think programs should look like the Algol-68 report
  68. (and some systems even require you to edit programs in that style),
  69. a clear program is not made any clearer by such presentation,
  70. and a bad program is only made laughable.
  71. .PP
  72. Typographic conventions consistently held
  73. are important to clear presentation, of course \(em
  74. indentation is probably the best known and most useful example \(em
  75. but when the ink obscures the intent, typography has taken over.
  76. So even if you stick with plain old typewriter-like output, be conscious
  77. of typographic silliness.
  78. Avoid decoration; for instance,
  79. keep comments brief and banner-free.
  80. Say what you want to say in the program, neatly and consistently.
  81. Then move on.
  82. .SH
  83. Variable names
  84. .PP
  85. Ah, variable names.
  86. Length is not a virtue in a name;
  87. clarity of expression
  88. .I is.
  89. A global variable rarely used may deserve a long name,
  90. .CW maxphysaddr
  91. say.  An array index used on every line of a loop needn't be named
  92. any more elaborately than
  93. .CW i .
  94. Saying
  95. .CW index
  96. or
  97. .CW elementnumber
  98. is more to type (or calls upon your text editor) and obscures
  99. the details of the computation.
  100. When the variable names are huge, it's harder to see what's going on.
  101. This is partly a typographic issue; consider
  102. .P1
  103. for(i=0 to 100)
  104.         array[i]=0
  105. .P2
  106. .I vs.
  107. .P1
  108. for(elementnumber=0 to 100)
  109.         array[elementnumber]=0;
  110. .P2
  111. The problem gets worse fast with real examples.
  112. Indices are just notation, so treat them as such.
  113. .PP
  114. Pointers also require sensible notation.
  115. .CW np
  116. is just as mnemonic as
  117. .CW nodepointer
  118. .I if
  119. you consistently use a naming convention from which
  120. .CW np
  121. means ``node pointer'' is easily derived.
  122. More on this in the next essay.
  123. .PP
  124. As in all other aspects of readable programming, consistency is important
  125. in naming.  If you call one variable
  126. .CW maxphysaddr ,
  127. don't call its cousin
  128. .CW lowestaddress .
  129. .PP
  130. Finally, I prefer minimum-length but maximum-information names, and
  131. then let the context fill in the rest.
  132. Globals, for instance, typically have little context when they are used,
  133. so their names need to be relatively evocative.  Thus I say
  134. .CW maxphysaddr
  135. (not
  136. .CW MaximumPhysicalAddress )
  137. for a global variable, but
  138. .CW np
  139. not
  140. .CW NodePointer
  141. for a pointer locally defined and used.
  142. This is largely a matter of taste, but taste is relevant to clarity.
  143. .PP
  144. I eschew embedded capital letters in names; to my prose-oriented eyes,
  145. they are too awkward to read comfortably.  They jangle like bad typography.
  146. .SH
  147. The use of pointers.
  148. .PP
  149. C is unusual in that it allows pointers to point to anything.
  150. Pointers are sharp tools, and like any such tool, used well
  151. they can be delightfully productive, but used badly they can
  152. do great damage (I sunk a wood chisel into my thumb
  153. a few days before writing this).
  154. Pointers have a bad reputation in academia,
  155. because they are considered too dangerous, dirty somehow.
  156. But I think they are powerful
  157. .I notation,
  158. which means they can help us express ourselves clearly.
  159. .PP
  160. Consider: When you have a pointer to an object, it is a name for exactly
  161. that object and no other.  That sounds trivial, but look at the following
  162. two expressions:
  163. .P1
  164. np
  165. node[i]
  166. .P2
  167. The first points to a node, the second evaluates to (say) the same node.
  168. But the second form is an expression; it is not so simple.
  169. To interpret it, we must know what
  170. .CW node
  171. is, what
  172. .CW i
  173. is, and that
  174. .CW i
  175. and
  176. .CW node
  177. are related by the (probably unspecified) rules
  178. of the surrounding program.
  179. Nothing about the expression in isolation can show that
  180. .CW i
  181. is a valid index of
  182. .CW node ,
  183. let alone the index of the element we want.
  184. If
  185. .CW i
  186. and
  187. .CW j
  188. and
  189. .CW k
  190. are all indices into the node array, it's very easy to slip up,
  191. and the compiler cannot help.
  192. It's particularly easy to make mistakes when passing things to subroutines:
  193. a pointer is a single thing; an array and an index must be believed
  194. to belong together in the receiving subroutine.
  195. .PP
  196. An expression that evaluates to an object is inherently more subtle
  197. and error-prone than the address of that object.
  198. Correct use of pointers can simplify code:
  199. .P1
  200. parent->link[i].type
  201. .P2
  202. .I vs.
  203. .P1
  204. lp->type.
  205. .P2
  206. If we want the next element's type, it's
  207. .P1
  208. parent->link[++i].type
  209. .P2
  210. or
  211. .P1
  212. (++lp)->type.
  213. .P2
  214. .CW i
  215. advances but the rest of the expression must stay constant;
  216. with pointers, there's only one thing to advance.
  217. .PP
  218. Typographic considerations enter here, too.
  219. Stepping through structures using pointers can be much
  220. easier to read than with expressions: less ink is needed and
  221. less effort is expended by the compiler and computer.
  222. A related issue is that the type of the pointer affects how it
  223. can be used correctly, which allows some helpful compile-time error
  224. checking that array indices cannot share.
  225. Also, if the objects are structures, their tag fields are
  226. reminders of their type, so
  227. .P1
  228.     np->left
  229. .P2
  230. is sufficiently evocative; if an array is being indexed the array
  231. will have some well-chosen name and the expression will end up
  232. longer:
  233. .P1
  234.     node[i].left.
  235. .P2
  236. Again, the extra characters become more irritating as the examples
  237. become larger.
  238. .PP
  239. As a rule, if you find code containing many similar, complex expressions
  240. that evaluate to elements of a data structure, judicious use of
  241. pointers can clear things up.
  242. Consider what
  243. .P1
  244. if(goleft)
  245.     p->left=p->right->left;
  246. else
  247.     p->right=p->left->right;
  248. .P2
  249. would look like using a compound expression for
  250. .CW p .
  251. Sometimes it's worth a temporary variable (here
  252. .CW p )
  253. or a macro to distill the calculation.
  254. .SH
  255. Procedure names
  256. .PP
  257. Procedure names should reflect what they do; function names should
  258. reflect what they
  259. .I return.
  260. Functions are used in expressions, often in things like
  261. .CW if 's,
  262. so they need to read appropriately.
  263. .P1
  264. if(checksize(x))
  265. .P2
  266. is unhelpful because we can't deduce whether checksize returns true on
  267. error or non-error; instead
  268. .P1
  269. if(validsize(x))
  270. .P2
  271. makes the point clear and makes a future mistake in using the routine
  272. less likely.
  273. .SH
  274. Comments
  275. .PP
  276. A delicate matter, requiring taste and judgement.
  277. I tend to err on the side of eliminating comments, for several reasons.
  278. First, if the code is clear, and uses good type names and variable names,
  279. it should explain itself.
  280. Second, comments aren't checked by the compiler,
  281. so there is no guarantee they're right,
  282. especially after the code is modified.
  283. A misleading comment can be very confusing.
  284. Third, the issue of typography: comments clutter code.
  285. .PP
  286. But I do comment sometimes.
  287. Almost exclusively, I use them as an introduction to what follows.
  288. Examples: explaining the use of global variables and types
  289. (the one thing I always comment in large programs);
  290. as an introduction to an unusual or critical procedure;
  291. or to mark off sections of a large computation.
  292. .PP
  293. There is a famously bad comment style:
  294. .P1
  295. i=i+1;        /* Add one to i */
  296. .P2
  297. and there are worse ways to do it:
  298. .P1
  299. /**********************************
  300.  *                                *
  301.  *          Add one to i          *
  302.  *                                *
  303.  **********************************/
  304.  
  305.                i=i+1;
  306. .P2
  307. Don't laugh now, wait until you see it in real life.
  308. .PP
  309. Avoid cute typography in comments,
  310. avoid big blocks of comments except perhaps before vital
  311. sections like the declaration of the central data structure
  312. (comments on data are usually much more helpful than
  313. on algorithms);
  314. basically, avoid comments.
  315. If your code needs a comment to be understood, it would be better
  316. to rewrite it so it's easier to understand.
  317. Which brings us to
  318. .SH
  319. Complexity
  320. .PP
  321. Most programs are too complicated \(em that is,
  322. more complex than they need to be to solve their problems efficiently.
  323. Why?
  324. Mostly it's because of bad design,
  325. but I will skip that issue here because it's a big one.
  326. But programs are often complicated
  327. at the microscopic level,
  328. and that is something I can address here.
  329. .PP
  330. Rule 1.
  331. You can't tell where a program is going to spend its time.
  332. Bottlenecks occur in surprising places, so don't
  333. try to second guess and put in a speed hack until you've
  334. proven that's where the bottleneck is.
  335. .PP
  336. Rule 2.
  337. Measure.
  338. Don't tune for speed until you've measured,
  339. and even then don't unless one part of the code
  340. .I overwhelms
  341. the rest.
  342. .PP
  343. Rule 3.
  344. Fancy algorithms are slow when
  345. .I n
  346. is small, and
  347. .I n
  348. is usually small.
  349. Fancy algorithms have big constants.
  350. Until you know that
  351. .I n
  352. is frequently going to be big,
  353. don't get fancy.
  354. (Even if
  355. .I n
  356. does get big, use Rule 2 first.)
  357. For example, binary trees are always faster than splay trees for
  358. workaday problems.
  359. .PP
  360. Rule 4.
  361. Fancy algorithms are buggier than simple ones,
  362. and they're much harder to implement.
  363. Use simple algorithms as well as simple data structures.
  364. .PP
  365. The following data structures are a complete list for almost
  366. all practical programs:
  367. .DS
  368. array
  369. linked list
  370. hash table
  371. binary tree
  372. .DE
  373. Of course, you must also be prepared to collect these into compound
  374. data structures.
  375. For instance, a symbol table might be implemented as a hash table
  376. containing linked lists of arrays of characters.
  377. .PP
  378. Rule 5.
  379. Data dominates.
  380. If you've chosen the right data structures and organized things well,
  381. the algorithms will almost always be self-evident.
  382. Data structures, not algorithms, are central to programming.
  383. (See Brooks p. 102.)
  384. .PP
  385. Rule 6.
  386. There is no Rule 6.
  387. .SH
  388. Programming with data.
  389. .PP
  390. Algorithms, or details of algorithms,
  391. can often be encoded compactly, efficiently and expressively as data
  392. rather than, say, as lots of
  393. .CW if
  394. statements.
  395. The reason is that the
  396. .I complexity
  397. of the job at hand, if it is due to a combination of
  398. independent details,
  399. .I
  400. can be encoded.
  401. .R
  402. A classic example of this is parsing tables,
  403. which encode the grammar of a programming language
  404. in a form interpretable by a fixed, fairly simple
  405. piece of code.
  406. Finite state machines are particularly amenable to this
  407. form of attack, but almost any program that involves
  408. the `parsing' of some abstract sort of input into a sequence
  409. of some independent `actions' can be constructed profitably
  410. as a data-driven algorithm.
  411. .PP
  412. Perhaps the most intriguing aspect of this kind of design
  413. is that the tables can sometimes be generated by another
  414. program \(em a parser generator, in the classical case.
  415. As a more earthy example, if an operating system is driven
  416. by a set of tables that connect I/O requests to the appropriate
  417. device drivers, the system may be `configured'
  418. by a program that reads a description of the particular
  419. devices connected to the machine in question and prints
  420. the corresponding tables.
  421. .PP
  422. One of the reasons data-driven programs are not common, at least
  423. among beginners, is the tyranny of Pascal.
  424. Pascal, like its creator, believes firmly in the separation
  425. of code and data.
  426. It therefore (at least in its original form) has no ability to
  427. create initialized data.
  428. This flies in the face of the theories of Turing and von Neumann,
  429. which define the basic principles of the stored-program computer.
  430. Code and data
  431. .I are
  432. the same, or at least they can be.
  433. How else can you explain how a compiler works?
  434. (Functional languages have a similar problem with I/O.)
  435. .SH
  436. Function pointers
  437. .PP
  438. Another result of the tyranny of Pascal is that beginners don't use
  439. function pointers.
  440. (You can't have function-valued variables in Pascal.)
  441. Using function pointers to encode complexity has some interesting
  442. properties.
  443. .PP
  444. Some of the complexity is passed to the routine pointed to.
  445. The routine must obey some standard protocol \(em it's one of a set
  446. of routines invoked identically \(em but beyond that, what it
  447. does is its business alone.
  448. The complexity is
  449. .I distributed.
  450. .PP
  451. There is this idea of a protocol, in that all functions used similarly
  452. must behave similarly.  This makes for easy documentation, testing,
  453. growth and even making the program run distributed over a network \(em
  454. the protocol can be encoded as remote procedure calls.
  455. .PP
  456. I argue that clear use of function pointers is the heart of object-oriented
  457. programming.  Given a set of operations you want to perform on data,
  458. and a set of data types you want to respond to those operations,
  459. the easiest way to put the program together is with a group of function
  460. pointers for each type.
  461. This, in a nutshell, defines class and method.
  462. The O-O languages give you more of course \(em prettier syntax,
  463. derived types and so on \(em but conceptually they provide little extra.
  464. .PP
  465. Combining data-driven programs with function pointers leads to an
  466. astonishingly expressive way of working, a way that, in my experience,
  467. has often led to pleasant surprises.  Even without a special O-O
  468. language, you can get 90% of the benefit for no extra work and be
  469. more in control of the result.
  470. I cannot recommend an implementation style more highly.
  471. All the programs I have organized this way have survived comfortably
  472. after much development \(em far better than with less disciplined
  473. approaches.
  474. Maybe that's it: the discipline it forces pays off handsomely in the long run.
  475. .SH
  476. Include files
  477. .PP
  478. Simple rule: include files should never include include files.
  479. If instead they state (in comments or implicitly) what files they need to have
  480. included first, the problem of deciding which files to include
  481. is pushed to the user (programmer) but in a way that's easy to handle
  482. and that, by construction, avoids multiple inclusions.
  483. Multiple inclusions are a bane of systems programming.
  484. It's not rare to have files included five or more times to
  485. compile a single C source file.
  486. The Unix
  487. .CW /usr/include/sys
  488. stuff is terrible this way.
  489. .PP
  490. There's a little dance involving
  491. .CW #ifdef 's
  492. that can prevent a file being read twice, but it's usually done
  493. wrong in practice \(em the
  494. .CW #ifdef 's
  495. are in the file itself, not the file that includes it.
  496. The result is often thousands of needless lines of code
  497. passing through the lexical analyzer, which is (in good compilers)
  498. the most expensive phase.
  499. .PP
  500. Just follow the simple rule.
  501.