What does Knuth mean by "literate programming"?
It is clearest if we look at actual examples.
Knuth has shared on on his website
many examples of literate programs he wrote (mostly for himself). But they are
in the CWEB format (.w files), and people with only a passing curiosity (or
none) in literate programming may not take the trouble to download and run them
through cweave and tex, to read them the way they were intended to be read.
So I've done that here.
From Knuth's website:
SHAM Enumerates symmetrical Hamiltonian cycles (December 1992) Needs SGB 8 pages 11 sections 6385 bytes in .w 1999-05-16 OBDD Enumerates perfect matchings of bipartite graphs (May 1996) Needs SGB 20 pages 30 sections 23569 bytes in .w 1996-05-06 REFLECT; also a change file for REFLECT Enumerates equivalence classes of reflection networks, aka CC systems (January 1991) Two versions, full and stripped-down 11 pages 25 sections 12469 bytes in reflect.w 1996-06-28 4 pages 5 sections [Smaller than reflect.w by 1724-byte reflect.ch.] 1996-06-28 HULL, HULLS, HULLT, HULLTR Programs used as examples in Axioms and Hulls; also change files for ngons, square deletion, and uniform input distribution TCALC Interactively calculates with humungous numbers (December 1994) Representing integers as binary trees. Note for instance that Section 4 is used only in Section 5. So we can do both bottom-up and top-down, without being tied to either. 28 pages 64 sections 34359 bytes in .w 1999-04-22 DECAGON; also a change file for DECAGON (stars); also a change file for DECAGON (color); also a change file for DECAGON (color stars) Packs golden triangles into decagons, stars, pentagons, etc. (September 1994) ANTISLIDE; also a change file for ANTISLIDE Finds solutions to Strijbos's antisliding block puzzle (November 1994) ANTISLIDE3 Improved version of ANTISLIDE, finds all nonisomorphic solutions (December 1996) SETSET Enumerates nonisomorphic unplayable hands in the game of SET® (February 2001) SETSET-ALL Improvement of SETSET---fifty times faster---when a huge automorphism group is considered (March 2001) SETSET-RANDOM Simple Monte Carlo routine to validate the previous two programs (March 2001) SLIDING Finds solutions to sliding block puzzles (November 2001; revised January 2009) 30 pages 58 sections 40808 bytes in .w 2009-01-30 STRAIGHTEN Computes irreducible matrix representations of permutations (August 2003) 11 pages 20 sections 11485 bytes in .w 2003-08-14 DOMINATION Computes the covering relation for an interesting partial ordering of multiset permutations (August 2003) 6 pages 7 sections 4043 bytes in .w 2003-08-14 FOG2MF Rudimentary conversion from Fontographer to METAFONT (August 1996) 7 pages 6 sections 5310 bytes in .w 1997-02-20 LAGFIB Calculator of weights related to the random number generator below (July 1997) 6 pages 9 sections 2646 bytes in .w 1997-07-29 GARSIA-WACHS Simple implementation of Algorithm 6.2.2G (January 1998, revised September 2004) HALFTONE Preprocessor for typeset halftones; also example input files lisa-64, lisa-rot, lisa-128, lin-64, lin-rot, lin-128, lib-64, lib-rot, lib-128 (June 1998) DOT-DIFF Preprocessor for halftones by dot diffusion; also an example input file lisa-512, and a change file for EPS output (June 1998) TOGPAP Generates examples of halftones for paper P116 on dot diffusion (June 1998) DANCE, POLYOMINOES, POLYIAMONDS, POLYSTICKS, QUEENS Generates examples for paper P159 on dancing links (July 1999); and another, SUDOKU (February 2005); also a change file for Monte Carlo estimates (corrected 25 Jan 07) GDANCE, MACMAHON-TRIANGLES-SYM-TILE, XGDANCE, GDANCE-CUTOFF Experimental extensions of the Dancing Links algorithm (November 2000) HAMDANCE A dancing-link-based program for Hamiltonian circuits (May 2001, slightly revised March 2010), which you might want to compare to the more traditional algorithm of HAM POLYNUM, POLYSLAVE, and their change files POLYNUM-RESTART and POLYSLAVE-RESTART for long runs Enumerates polyominoes with Iwan Jensen's algorithm, thousands of times faster than previous approaches (but is a memory hog); also notes from Jensen about potential further improvements and the probable value of t(48); also a MetaPost source file polyomino.mp to make an illustration for the documentation of both POLYNUM and a now-obsolete program POLYENUM ADVENT The original Crowther/Woods Adventure game, Version 1.0, translated into CWEB form (version of 09 October 2014); this program was published as Chapter 27 of my Fun and Games book, and errata can be in the corrections to pages 235--394 that appear on that webpage ROST Monte Carlo confirmation of exercise 5.1.4--40 (October 1998) RAN-PRIM Monte Carlo exploration of exercise 5.3.4--40 (October 1998) STRONGCHAIN finds shortest strong addition chains, also called Lucas chains or Chebyshev chains (August 2000) Looks like a good program to read. KODA-RUSKEY A fascinating generalized reflected Gray-code generator (new version, June 2001) LI-RUSKEY An even more fascinating, massive generalization of the previous program (June 2001); also a PostScript illustration li-ruskey.1 made by the MetaPost source file li-ruskey.mp SPIDERS A further improvement to the previous two (December 2001), and its PostScript illustration deco.5 TOPSWOPS and TOPSWOPS-FWD Two ways to find the longest plays of John Conway's "topswops" game (August 2001) CO-DEBRUIJN A quick-and-dirty implementation of the recursive coroutines Algorithms 7.2.1.1R and 7.2.1.1D, which generate a de Bruijn cycle; also a Mathematica program co-debruijn.m to check the ranking and unranking functions in exercises 7.2.1.1--97 through 99 POSETS0 and POSETS Two programs to evaluate the numbers in Sloane's sequence A006455, formerly M1805 (December 2001) ERECTION The algorithms described in my paper ``Random Matroids'' (March 2003) UNAVOIDABLE A longest word that avoids all n-letter subwords in an interesting minimal set constructed by Champernaud, Hansel, and Perrin (July 2003) UNAVOIDABLE2 A longest word that avoids all n-letter subwords in an interesting minimal set constructed by Mykkeltveit (August 2003) GRAYSPAN, SPSPAN, GRAYSPSPAN, and a MetaPost source file for SPSPAN, plus an auxiliary program SPGRAPH Three instructive ways to generate all spanning trees of a graph (August 2003) SAND A hastily written program to experiment with sandpiles as in exercise 7.2.1.6--103 (December 2004) ZEILBERGER, FRANÇON, VIENNOT, an explanatory introduction, and a MetaPost source file for VIENNOT Three Catalan bijections related to Strahler numbers, pruning orders, and Kepler towers (February 2005) LINKED-TREES An amazingly short program to generate linked trees with given node degrees (March 2005) VACILLATE A program to experiment with set partitions and vacillating tableau loops (May 2005) EMBED An algorithm of Hagauer, Imrich, and Klavžar to embed a median graph in a hypercube (June 2005) LP An expository implementation of linear programming (August 2005) I must read this. Maybe I'll finally understand the simplex method HORN-COUNT A program to enumerate Horn functions; also a change file krom-count.ch, which adapts it to Krom functions (aka 2SAT instances) (August 2005) 15PUZZLE-KORF0 and 15PUZZLE-KORF1 Two programs to solve 15-puzzle problems rather fast (but not state-of-the-art) (August 2005) ACHAIN0, ACHAIN1, ACHAIN2, ACHAIN3, ACHAIN4, and ACHAIN-ALL A series of programs to find minimal addition chains (September 2005), plus a trivial auxiliary program ACHAIN-DECODE. HYPERBOLIC and a MetaPost source file for HYPERBOLIC A program that analyzes and helps to draw the hyperbolic plane tiling made from 36-45-90 triangles (October 2005) BOOLCHAINS A suite of programs that find the complexity of almost all Boolean functions of five variables (December 2005) FCHAINS4X and and a change file for don't-cares Programs for interactive minimization of multiple-output 4-input Boolean functions using the `greedy footprint' method (February 2006, revised October 2010) TICTACTOE, a gzipped tar file tictactoe.tgz Various programs used when preparing the tic-tac-toe examples in Section 7.1.2 (March 2006) tictactoe0 (also tictactoe1) is basically just the full program in one section, followed by an index PRIME-SIEVE and its much faster (but more complex) cousin PRIME-SIEVE-SPARSE, plus a change file PRIME-SIEVE-BOOT to compute several million primes to be input by the other programs Programs for the segmented sieve of Eratosthenes on 64-bit machines, tuned for finding all large gaps between primes in the neighborhood of 10^18 (May 2006) MAXCLIQUES The Moody--Hollis algorithm for listing all maximal cliques, all maximal independent sets, and/or all minimal vertex covers (July 2006, corrected November 2008) ULAM and a change file for 64-bit machines Short program to compute the Ulam numbers 1, 2, 3, 4, 6, ... (September 2006) --- but see the vastly improved version below, dated July 2016! HWB-FAST Short program to compute the profile of the hidden weight function, given a permutation of the variables (April 2008) YPLAY Simple program to play with Schensted's Y function (April 2008) BDD12 A program to find the best and worst variable orderings for a given BDD (May 2008) BDD14 and a typical driver program to generate input for it Bare-bones BDD package that I used for practice when preparing Section 7.1.4 of TAOCP (May 2008; version of September 2011) BDD15 Bare-bones ZDD package that I used for practice when preparing Section 7.1.4 of TAOCP (August 2008) SIMPATH, SIMPATH-REDUCE, SIMPATH-EXAMPLE, and change files for cycles, Hamiltonian paths, and Hamiltonian paths with one endpoint given Several programs to make ZDDs for simple paths of graphs (August 2008) SIMPATH-DIRECTED-CYCLES And another for simple cycles in directed graphs (August 2008) EULER-TRAIL A simple algorithm that computes an Eulerian trail of a given connected graph (March 2010) CELTIC-PATHS A fun program to typeset certain Celtic knots, using special fonts CELTICA, CELTICA13, CELTICB, CELTICB13; you also need this simple illustration (August 2010) NNNCMBX.MF The font used for my paper ``N-ciphered texts'' (1981, 1987, 2010) DRAGON-CALC An interactive program to compute with and display generalized dragon curves (September 2010) SQUAREGRAPH Brute-force enumeration of all small squaregraphs --- an very interesting class of median graphs, generalizing polyominoes (August 2011) SQUAREGRAPH-RAND A short routine that generates more-or-less random pairs of chord edges, obtaining squaregraphs by "crocheting" them around the boundary TREEPROBS Computes probabilities in Bayesian binary tree networks (July 2011) GRAPH-SIG-V0 A simple program that helps find automorphisms of a graph (July 2015) SKEW-TERNARY-CALC and a MetaPost file for its illustrations Computes planar graphs that correspond to ternary trees in an amazing way; here's a PDF file for its documentation RANDOM-TERNARY Implementation of Panholzer and Prodinger's beautiful algorithm for generating random ternary trees
(see also the change files RANDOM-TERNARY-QUADS and SKEW-TERNARY-CALC-RAW with which you can use this with SKEW-TERNARY-CALC)DIMACS-TO-SAT and SAT-TO-DIMACS Filters to convert between DIMACS format for SAT problems and the symbolic semantically meaningful format used in the programs below SAT0 My implementation of Algorithm 7.2.2.2A (very basic SAT solver) SAT0W My implementation of Algorithm 7.2.2.2B (teeny tiny SAT solver) SAT8 My implementation of Algorithm 7.2.2.2W (WalkSAT) SAT9 My implementation of Algorithm 7.2.2.2S (survey propagation SAT solver) SAT10 My implementation of Algorithm 7.2.2.2D (Davis-Putnam SAT solver) SAT11 My implementation of Algorithm 7.2.2.2L (lookahead 3SAT solver) SAT11K Change file to adapt SAT11 to clauses of arbitrary length SAT12 and the companion program SAT12-ERP My implementation of a simple preprocessor for SAT SAT13 My implementation of Algorithm 7.2.2.2C (conflict-driven clause learning SAT solver) SAT-LIFE Various programs to formulate Game of Life problems as SAT problems (July 2013) SAT-NFA Produce a forcing encoding of regular languages into SAT via nondeterministic finite automata (April 2016) SATexamples Programs for various examples of SAT in Section 7.2.2.2 of TAOCP; also more than a hundred benchmarks (updated 08 July 2015) BACK-20Q and a change file for the paradoxical variant, and another A backtrack program to analyze Don Woods's Twenty Questions (August 2015) BACK-MXN-WORDS-NEW and BACK-MXN-WORDS-MXM. with some word lists Demonstration backtrack programs for word rectangles (August 2015) BACK-PDI A backtrack program to find perfect digital invariants (e.g. 153=1^3+5^3+3^3) (September 2015) COMMAFREE-EASTMAN and COMMAFREE-EASTMAN-NEW Eastman's encoding algorithm for commafree codes of odd block lengths (September 2015 and December 2015) SAT-COMMAFREE Clauses to construct binary commafree codes with one codeword per cycle class (September 2015) BACK-COMMAFREE4 Finds all commafree 4-letter codes of given size on small alphabets (September 2015) BACK-SKELETON-SHORTEST Finds potential skeleton multiplication puzzles whose special digits obey a given pixel pattern (January 2016) BACK-DISSECT Finds dissections of a square into a given shape (February 2016) ULAM-GIBBS and the auxiliary illustration file ulam-gibbs.1 Computes billions of Ulam numbers if you've got enough memory (July 2016) (read the documentation) DLX1 Algorithm 7.2.2.1D for exact cover via dancing links (September 2016, an update of the old DANCE program above) DLX2 Algorithm 7.2.2.1C, the extension to color-controlled covers (September 2016, an update of the old GDANCE program above)