Blog

Jon Bentley's "Programming Pearls" columns, and Van Wyk's "Literate Programming" columns in the CACM

Jon Bentley used to write a magazine column for the Communications of the ACM called “Programming Pearls” (later collected into two books). A spin-off was a column called “Literate Programming”, by Christopher J. Van Wyk.

It is hard to find a list of all these columns, so I’m compiling a list here.

Bentley’s book: “Writing Efficient Programs”

First, in 1982, Bentley wrote a book called “Writing Efficient Programs”. It appears that some content from this book was reproduced in the columns later (e.g. on the difficulty of implementing binary search correctly)… or maybe it was only in the Programming Pearls book.

Incidentally, note this from Chapter 1 (“Introduction”), section 1.4 (“A survey of other work”):

There is a treasure-house of information about writing efficient code in the works of Donald Knuth. His textbooks (Knuth [1968, 1969, 1973]) are classics in the fields of algorithms and data structures, and are laden with both examples and principles of writing efficient code. His empirical study of FORTRAN programs (Knuth [1971]) gave a precise perspective to the activity of writing efficient code; we will see in Chapter 3 how his study allows us to ignore efficiency most of the time and concentrate on it when it really matters. That paper also contains seventeen detailed examples of efficient translations of FORTRAN fragments into IBM System/360 assembly code. Knuth [1974] is an excellent study of the question of how programming language design and programming methodologies relate to writing efficient code. In fact, of the twenty-seven efficiency rules in Chapters 4 and 5, fifteen refer explicitly to the works of Knuth. In addition to his own works, many of the Stanford Ph.D. theses and other papers of Professor Knuth’s students are invaluable studies in writing efficient code; in later chapters we will see the works of Sedgewick [1975, 1978], Mont-Reynaud [1976], and Van Wyk [1981].

Bentley’s “Programming Pearls” columns

ACM’s search is broken: both this search and this search miss different subsets of data (plus the latter needs to be navigated by editing the URL).

Anyway, here’s a list. (If you don’t care about reading these columns in their original context, you’ll be better served reading the two books directly.)

We can mostly verify that nothing is missing, by looking at the table of contents on the CACM website, by looking at Nelson Beebe’s bibliographies (e.g. here), and (often, but not always) using an internal consistency check: by seeing whether the posted solutions in each column are those to the previous column’s problems.

Format: the first one below means “CACM August 1983 Volume 26 Number 8” – in general Volume X Number Y is Year (1957+X), Month Y.

  1. Bentley, J. (1983). Programming pearls: Cracking the oyster. Communications of the ACM, 26(8), 549–552. doi:10.1145/358161.358164 [Editor-in-Chief Peter J. Denning announces the series, then a story on sorting 27000 integers with not much memory available.]

  2. Bentley, J. (1983). Programming pearls: Aha algorithms. Communications of the ACM, 26(9), 623–628. doi:10.1145/358172.358176

  3. Bentley, J. (1983). Programming pearls: Data structures programs. Communications of the ACM, 26(10), 726–730. doi:10.1145/358413.383461

    • (Nothing in November 1983.)

  4. Bentley, J. (1983). Programming pearls: Writing correct programs. Communications of the ACM, 26(12), 1040–1045. doi:10.1145/358476.358484

  5. 27(1): doi:10.1145/69605.993447 – couldn’t find this one yet. DOI is broken. Also, misspelled as “Programming Perls” at https://cacm.acm.org/magazines/1984/1 – according to Beebe, “J. L. Bentley Programming Pearls: About the Column . . 12–13” so Pages 12 and 13 of Jan 1984 issue.

  6. Missing February 1984? The March column mentions solutions to February’s problems… but there’s no mention at https://cacm.acm.org/magazines/1984/2 but there’s a mention at http://ftp.math.utah.edu/pub/tex/bib/toc/cacm1980.html (pages 91 to 96): “Jon Louis Bentley Programming Pearls: Code Tuning . . . . 91–96”

  7. Bentley, J. (1984). Programming pearls: the back of the envelope. Communications of the ACM, 27(3), 180–184. doi:10.1145/357994.381168

  8. Bentley, J. (1984). Programming pearls: how to sort. Communications of the ACM, 27(4), 297–291. doi:10.1145/358027.381121

  9. Bentley, J. (1984). Programming pearls: squeezing space. Communications of the ACM, 27(5), 416–421. doi:10.1145/358189.381134

  10. Bentley, J. L. (1984). Programming pearls: graphic output. Communications of the ACM, 27(6), 529–536. doi:10.1145/358080.364565

  11. Bentley, J. (1984). Programming pearls: updates. Communications of the ACM, 27(7), 630–636. doi:10.1145/358105.381166

    • (Nothing in August 1984)

  12. Bentley, J. (1984). Programming pearls: algorithm design techniques. Communications of the ACM, 27(9), 865–873. doi:10.1145/358234.381162

    • (Nothing in October 1984)

  13. Bentley, J. (1984). Programming pearls: perspective on performance. Communications of the ACM, 27(11), 1087–1092. doi:10.1145/1968.381154

  14. Bentley, J. L. (1984). Programming Pearls: a Little Program, a Lot of Fun. Communications of the ACM, 27(12), 1179–1182. doi:10.1145/2135.381151

    • Nothing in Jan 1985.

  15. Bentley, J. (1985). Programming pearls: Tricks Of The Trade. Communications of the ACM, 28(2), 138–141. doi:10.1145/2786.314990

  16. Bentley, J. (1985). Programming pearls: Thanks, Heaps. Communications of the ACM, 28(3), 245–250. doi:10.1145/3166.315010

    • Nothing in April 1985.

  17. Bentley, J. (1985). Programming pearls: A Spelling Checker. Communications of the ACM, 28(5), 456–462. doi:10.1145/3532.315102

  18. Bentley, J. (1985). Programming pearls: Associative Arrays. Communications of the ACM, 28(6), 570–576. doi:10.1145/3812.315108

  19. Bentley, J. (1985). Programming pearls: Confessions of a Coder. Communications of the ACM, 28(7), 671–679. doi:10.1145/3894.315112

    • Nothing in August 1985… probably.

  20. Bentley, J. (1985). Programmimg pearls: Bumper-Sticker Computer Science. Communications of the ACM, 28(9), 896–901. doi:10.1145/4284.315122

    • Nothing in October 1985… probably.

  21. Bentley, J. (1985). Programming pearls: Selection. Communications of the ACM, 28(11), 1121–1127. doi:10.1145/4547.315131

    • Nothing in December 1986 – next (Feb 1986) issue has solutions to November’s problems.

    • Nothing in January 1986 – any references are to the book, published around this time.

  22. Bentley, J. (1986). Programming pearls: Cutting the Gordian Knot. Communications of the ACM, 29(2), 92–96. doi:10.1145/5657.315569

  23. Bentley, J. L. (1986). Programming pearls: The Envelope Is Back. Communications of the ACM, 29(3), 176–182. doi:10.1145/5666.315593

    • Nothing in April 1986 – probably.

  24. Bentley, J., & Knuth, D. (1986). Programming pearls: Literate Programming. Communications of the ACM, 29(5), 384–369. doi:10.1145/5689.315644

  25. Bentley, J., Knuth, D., & McIlroy, D. (1986). Programming pearls: A Literate Program. Communications of the ACM, 29(6), 471–483. doi:10.1145/5948.315654

    • Nothing in July 1986 – the August issue mentions June problems.

  26. Bentley, J. (1986). Programming pearls: Little Languages. Communications of the ACM, 29(8), 711–721. doi:10.1145/6424.315691

  27. Bentley, J. (1986). Programming pearls: Document Design. Communications of the ACM, 29(9), 832–839. doi:10.1145/6592.315696

    • Nothing in October 1986 and November 1986 – the December 1986 issue mentions Sepember’s problems.

  28. Bentley, J. (1986). Programming pearls: Birth of a Cruncher. Communications of the ACM, 29(12), 1155–1161. doi:10.1145/7902.315707

    • Nothing in Jan/Feb/Mar 1987.

  29. Bentley, J., & Gries, D. (1987). Programming pearls: Abstract Data Types. Communications of the ACM, 30(4), 284–290. doi:10.1145/32232.315727 BTW, this has some comments on Knuth’s May 1986 program, for random numbers – solving a problem from the December 1984 column. It has a solution by Gries for the problem. Also, its third problem mentions packaging the hash-trie as an abstract data type. It also ends with:

    Connoisseurs of literate programs will be able to enjoy several of them in forthcoming issues of Communications: Chris Van Wyk is editing a series of programs and reviews. The first installation will include comments on Knuth’s program in the June 1986 column, and an alternative program for the problem.

    • Nothing in May 1987 – probably.

  30. Bentley, J. (1987). Programming pearls: Self-Describing Data. Communications of the ACM, 30(6), 479–483. doi:10.1145/214762.315733

  31. Bentley, J. (1987). Programming pearls: Profilers. Communications of the ACM, 30(7), 587–592. doi:10.1145/28569.315737

  32. Bentley, J., & Floyd, B. (1987). Programming pearls: A Sample Of Brilliance. Communications of the ACM, 30(9), 754–757. doi:10.1145/30401.315746

    • Nothing in Oct/Nov 1987.

  33. Bentley, J. (1987). Programming pearls: The Furbelow Memorandum. Communications of the ACM, 30(12), 998–999. doi:10.1145/33447.315759 – continued on page 1010, part of the following “Literate Programming” column.

So looks like there were a total of 33 columns, of which 31 (all but 5 and 6) are accessible via the DOI (in the… “usual” way).

Van Wyck, Literate programming

  1. Van Wyk, C. J. (1987). Literate programming: Printing Common Words. Communications of the ACM, 30(7), 583–599. doi:10.1145/28569.315738 Announcing the column, etc. Also revisits the common words problem, with this from John Gilbert:

    What is a literate program, anyway? A program, like an essay, can be written for many purposes: to teach, to learn, to experiment with new forms, to solve an immediate problem, to sell refrigerators, or to sell workstations. The solutions to Jon Bentley’s problem by Knuth, McIlroy, and Hanson are all “literate programs,” but they differ in style to a startling degree.

    Architecture may be a better metaphor than writing for an endeavor that closely mixes art, science, craft, and engineering. “Put up a house on a creek near a waterfall,” we say, and look at what each artisan does:

    The artist, Frank Lloyd Wright (or Don Knuth), designs Fallingwater, a building beautiful within its setting, comfortable as a dwelling, audacious in technique, and masterful in execution.

    Doug McIlroy, consummate engineer, disdains to practice architecture at all on such a pedestrian task; he hauls in the pieces of a prefabricated house and has the roof up that afternoon. (After all, his firm makes the best prefabs in the business.) David Hanson puts together a roomy and craftsmanlike cabin, probably closest of the three to the spirit of the original commission.

    The programs differ not only in their proportions of art, engineering, and craftsmanship, but in their very intent. Of course the authors wrote them to solve a set problem, but each seems to have had a different purpose in mind. Knuth’s is art and exposition. McIlroy’s solves a one-shot problem. Hanson’s could be a piece of real-world software, perhaps inside some unusual word processing system.

  2. Van Wyk, C. J. (1987). Literate programming: Processing Transactions. Communications of the ACM, 30(12), 1000–1010. doi:10.1145/33447.315760 (also on last page has part of the last “Programming Pearls” column)

  3. Van Wyk, C. J. (1988). Literate programming: Expanding Generalized Regular Expressions. Communications of the ACM, 31(12), 1376–1395. doi:10.1145/53580.315830

  4. Van Wyk, C. J. (1989). Literate programming: A File Difference Program. Communications of the ACM, 32(6), 740–755. doi:10.1145/63526.315960 [Has a review by Thimbleby, that also goes into details of his Cweb.]

  5. Van Wyk, C. J. (1989). Literate programming: Weaving A Language-Independent WEB. Communications of the ACM, 32(9), 1051–1055. doi:10.1145/66451.315988 [Norman Ramsey introduces SPIDER]

  6. Van Wyk, C. J. (1990). Literate programming: An Assessment. Communications of the ACM, 33(3), 361–ff. doi:10.1145/77481.316051 Having, in the previous 5 columns, presented 4 literate programs and 1 literate-programming system, this one concludes with:

    Unfortunately, no one has yet volunteered to write a program using another’s system for literate programming. A fair conclusion from my mail would be that one must write one’s own system before one can write a literate program, and that makes me wonder how widespread literate programming is or will ever become. This column will continue only if I hear from people who use literate-programming systems that they have not designed themselves.

    and it did not continue.