Literate programming

Document license.

(C) Copyright various Wikipedia Contributors. This text is taken from Wikipedia, the free encyclopedia1 , presented here under the Creative Commons Attribution-Share Alike 3.0 Unported license.

This license is acceptable for Free Cultural Works.

You are free:

to Share — to copy, distribute and transmit the work

to Remix — to adapt the work

Under the following conditions:

Attribution

You must attribute the work in the manner specified by the author or licensor (but not in any way that suggests that they endorse you or your use of the work).

SharexAlike

If you alter, transform, or build upon this work, you may distribute the resulting work only under the same, similar or a compatible license.

Literate Programming Literate programming is an approach to programming introduced by Donald Knuth as an alternative to the structured programming paradigm of the 1970s.2

The literate programming paradigm, as conceived by Knuth, represents a move away from writing programs in the manner and order imposed by the computer, and instead enables programmers to develop programs in the order demanded by the logic and flow of their thoughts.3 Literate programs are written as an uninterrupted exposition of logic in an ordinary human language, much like the text of an essay, in which macros which hide abstractions and traditional source code are included. Literate programming tools are used to obtain two representations from a literate source file: one suitable for further compilation or execution by a computer, the “tangled” code, and another for viewing as formatted documentation, which is said to be “woven” from the literate source. (If one remembers that the first version of the tool was called WEB, the amusing literary reference hidden by Knuth in these names becomes obvious: “Oh, what a tangled web we weave when first we practise to deceive” — Sir Walter Scott, in Canto VI, Stanza 17 of “Marmion” (1808) an epic poem about the Battle of Flodden Field in 1513.). While the first generation of literate programming tools were computer language-specific, the later ones are language-agnostic and exist above the programming languages.

Contents

Contents

1 Concept

x1.1 Advantages of the method

x1.2 Misconceptions

2 Example

3 Creation of macros

4 Program as a Web - Macros are not just section names x4.1 Order of human logic, not that of the compiler

x4.2 Record of the train of thought creates superior documentation

5 Literate programming tools

6 See also

7 Further reading

8 External links

1 Concept

A literate program is an explanation of the program logic in a natural language, such as English, interspersed with snippets of macros and traditional source code. Macros in a literate source file are simply title-like or explanatory phrases in a human language that describe human abstractions created while solving the programming problem, and hiding chunks of code or lower-level macros. These macros are similar to the algorithms in pseudocode typically used in teaching computer science. These arbitrary explanatory phrases become precise new operators, created on the fly by the programmer, forming a meta-language on top of the underlying programming language.

A preprocessor is used to substitute arbitrary hierarchies, or rather “interconnected ’webs’ of macros”,4 to produce the compilable source code with one command (“tangle”), and documentation with another (“weave”). The preprocessor also provides an ability to write out the content of the macros and to add to already created macros in any place in the text of the literate program source file, thereby disposing of the need to keep in mind the restrictions imposed by traditional programming languages or to interrupt the flow of thought.

1.1 Advantages of the method According to Knuth,5 6 literate programming provides for higher-quality programs, since it forces programmers to explicitly state the thoughts behind the program, making poorly thought-out design decisions more obvious. Knuth also claims that literate programming provides a first-rate documentation system, which is not an add-on, but is grown naturally in the process of exposition of one’s thoughts during a program creation.7 The resulting documentation allows authors to restart their own thought processes at any later time, and allows other programmers to more easily understand the construction of the program. This differs from traditional documentation, in which a programmer is presented with source code that follows a compiler-imposed order, and must decipher the thought process behind the program from the code and its associated comments. The meta-language capabilities of literate programming are also claimed to facilitate thinking in general, giving a higher “bird’s eye view” of the code and increasing the number of concepts the mind can successfully retain and process. Applicability of the concept to programming on a large scale, that of commercial-grade programs is proven by an edition of TEX code as a literate program.

1.2 Misconceptions

Literate programming is very often misunderstood8 to refer only to formatted documentation produced from a common file with both source code and comments, or to voluminous commentaries included with code. This misconception has led to claims that comment-extraction tools, such as the Perl Plain Old Documentation system, are “literate programming tools”. However, because these tools do not implement the “web of abstract concepts” hiding behind the system of natural-language macros, or provide an ability to change the order of the source code from a machine-imposed sequence to one convenient to the human mind, they cannot properly be called literate programming tools in the sense intended by Knuth.89

2 Example

A classic example of literate programming is the literate implementation of the standard Unix wc word counting program. Knuth presented a CWEB version of this example in Chapter 12 of his Literate Programming book. The same example was later rewritten for the noweb literate programming tool.10 This example provides a good illustration of the basic elements of literate programming.

3 Creation of macros

The following snippet of the wc literate program10 shows how arbitrary descriptive phrases in a natural language are used in a literate program to create macros, which act as new “operators” in the literate programming language, and hide chunks of code or other macros. The mark-up notation consists of double angle brackets (“<<x>>”) that indicate macros, the “@” symbol which indicates the end of the code section in a noweb file. The “<<*>>” symbol stands for the “root”, topmost node the literate programming tool will start expanding the web of macros from. Actually, writing out the expanded source code can be done from any section or subsection (i.e. a piece of code designated as ”<<name of the chunk>>=”, with the equal sign), so one literate program file can contain several files with machine source code.

1 Thexpurposexofxwcxisxtoxcountxlines,xwords,xand/orxcharactersxinxaxlistxofxfiles.xThex 2 numberxofxlinesxinxaxfilexisx......../morexexplanations/x 3 x 4 Here,xthen,xisxanxoverviewxofxthexfilexwc.cxthatxisxdefinedxbyxthexnowebxprogramxwc.nw:x 5 xxxxxx<<*>>=x 6 xxxxxx<<Headerxfilesxtoxinclude>>x 7 xxxxxx<<Definitions>>x 8 xxxxxx<<Globalxvariables>>x 9 xxxxxx<<Functions>>x 10 xxxxxx<<Thexmainxprogram>>x 11 @x 12 x 13 WexmustxincludexthexstandardxI/Oxdefinitions,xsincexwexwantxtoxsendxformattedxoutputx 14 toxstdoutxandxstderr.x 15 xxxxxx<<Headerxfilesxtoxinclude>>=x 16 xxxxxx#includex<stdio.h>x 17 xxxxxx@

Note also that the unraveling of the chunks can be done in any place in the literate program text file, not necessarily in the order they are sequenced in the enclosing chunk, but as is demanded by the logic reflected in the explanatory text that envelops the whole program.

4 Program as a Web - Macros are not just section names

Macros are not the same as “section names” in standard documentation. Literate programming macros can hide any chunk of code behind themselves, and be used inside any low-level machine language operators, often inside logical operators such as “if”, “while”, “case”. This is illustrated by the following snippet of the wc literate program.10

1 x 2 Thexpresentxchunk,xwhichxdoesxthexcountingxthatxisxwc's␣raison␣d'etre,xwasxactuallyxonexofx 3 thexsimplestxtoxwrite.xWexlookxatxeachxcharacterxandxchangexstatexifxitxbeginsxorxendsx 4 axword.x 5 x 6 xxxxxx<<scanxfile>>=x 7 xxxxxxwhilex(1)x{x 8 xxxxxxxxxxxx<<Fillxbufferxifxitxisxempty;xbreakxatxendxofxfile>>x 9 xxxxxxxxxxxxcx=x*ptr++;x 10 xxxxxxxxxxxxifx(cx>x'␣'x&&xcx<x0177)x{x 11 xxxxxxxxxxxxxxxxxx/*xvisiblexASCIIxcodesx*/x 12 xxxxxxxxxxxxxxxxxxifx(!inword)x{x 13 xxxxxxxxxxxxxxxxxxxxxxxxwordcount++;x 14 xxxxxxxxxxxxxxxxxxxxxxxxinwordx=x1;x 15 xxxxxxxxxxxxxxxxxx}x 16 xxxxxxxxxxxxxxxxxxcontinue;x 17 xxxxxxxxxxxx}x 18 xxxxxxxxxxxxifx(cx==x'\n')xlinecount++;x 19 xxxxxxxxxxxxelsexifx(cx!=x'␣'x&&xcx!=x'\t')xcontinue;x 20 xxxxxxxxxxxxinwordx=x0;x 21 xxxxxxxxxxxx/*xcxisxnewline,xspace,xorxtabx*/x 22 xxxxxx}x 23 xxxxxx@

In fact, macros can stand for any arbitrary chunk of code or other macros, and are thus more general than top-down or bottom-up “chunking”, or than subsectioning. Knuth says that when he realized this, he began to think of a program as a web of various parts.2

4.1 Order of human logic, not that of the compiler

In a noweb literate program besides the free order of their exposition, the chunks behind macros, once introduced with “<<x>>=”, can be grown later in any place in the file by simply writing “<<name of the chunk>>=” and adding more content to it, as the following snippet illustrates.2

1 Thexgrandxtotalsxmustxbexinitializedxtoxzeroxatxthexbeginningxofxthexprogram.x 2 Ifxwexmadexthesexvariablesxlocalxtoxmain,xwexwouldxhavextoxdoxthisxinitializationx 3 explicitly;xhowever,xCxglobalsxarexautomaticallyxzeroed.x(Orxrather,staticallyx 4 zeroed.x(Getxit?)x 5 xxxxxx<<Globalxvariables>>+=x 6 xxxxxxlongxtotwordcount,xtotlinecount,x 7 xxxxxxxxxxxxtotcharcount;x 8 xxxxxxxxxxxx/*xtotalxnumberxofxwords,xlines,xcharsx*/x 9 xxxxxx@

4.2 Record of the train of thought creates superior documentation

The documentation for a literate program is produced as part of writing the program. Instead of comments provided as side notes to source code a literate program contains the explanation of concepts on each level, with lower level concepts deferred to their appropriate place, which allows for better communication of thought. The snippets of the literate wc above show how an explanation of the program and its source code are interwoven. Such exposition of ideas creates the flow of thought that is like a literary work. Knuth famously wrote a “novel” which explains the code of the computer strategy game Colossal Cave Adventure, perfectly readable.11 5 Literate programming tools

The first published literate programming environment was WEB, introduced by Donald Knuth in 1981 for his TEX typesetting system; it uses Pascal as its underlying programming language and TEX for typesetting of the documentation. The complete commented TEX source code was published in Knuth’s TEX: The program, volume B of his 5-volume Computers and Typesetting. Knuth had privately used a literate programming system called DOC as early as 1979. He was inspired by the ideas of Pierre-Arnoul de Marneffe12 . The free CWEB, written by Knuth and Silvio Levy, is WEB adapted for C and C++, runs on most operating systems and can produce TEX and PDF documentation.

Other implementations of the literate programming concept are noweb and FunnelWeb, both of which are independent of the programming language of the source code. Noweb is well-known for its simplicity: just 2 text markup conventions and 2 tool invocations are needed to use it, and it allows for text formatting in HTML rather than going through the TEX system. FunnelWeb is another program without dependency on TEX which can produce HTML documentation output. It has more complicated markup (with “@” escaping any FunnelWeb command), but has many more flexible options.

The Leo text editor is an outlining editor which supports optional noweb and CWEB markup. The author of Leo actually mixes two different approaches: first, Leo is an outlining editor, which helps with management of large texts, second, Leo incorporates some of the ideas of literate programming, which in its pure form (i.e. the way it is used by Knuth Web tool and/or tools like “noweb”) is possible only with some degree of inventiveness and the use of the editor in a way not exactly envisioned by its author (in modified @root nodes). However this and other extensions (@file nodes) make outline programming and text management successful and easy and in some ways similar to literate programming.13

The Haskell programming language has native support for semi-literate programming, inspired by CWEB but with a simpler implementation. When aiming for TEX output, one writes a plain LATEX file where source code is marked by a given surrounding environment; LATEX can be set up to handle that environment, while the Haskell compiler looks for the right markers to identify Haskell statements to compile, removing the TEX documentation as if they were comments. However, as described above, this is not literate programming in the sense intended by Knuth. Haskell’s functional, modular nature14 makes literate programming directly in the language somewhat easier, but it is not nearly as powerful as one of the a WEB tools where “tangle” can reorganize in arbitrary ways.

6 See also Sweave - an example of use of the “noweb”-like Literate Programming tool inside the R language for creation of dynamic statistical reports

7 Further reading Knuth, Donald E. (1992). Literate Programming. , California: Stanford University Center for the Study of Language and Information. ISBN 978-0937073803.x Guari, Eitan M. (1994). TEX & LATEX: Drawing and Literate Programming. McGraw Hill. ISBN 0-07-911616-7.x (includes software). Nørmark, Kurt (August 13, 1998). "Literate Programming - Issues and Problems". University of Aalborg. http://www.cs.aau.dk/xnormark/litpro/issues-and-problems.html.x

8 External links comp.programming.literate FAQ at Internet FAQ Archives Literate Programming newsgroup LiteratePrograms a literate programming wiki. Select A literate programming example using noweb Softpanorama page on literate programming Haskell literate programming Specification of literate programming in the Haskell Report the accepted Haskell standard Noweb — A Simple, Extensible Tool for Literate Programming Lp4all — A Simple Literate Programming Tool with a wiki-like markup syntax

1http://en.wikipedia.org/wiki/Literate_programming

2Knuth, Donald E. (1984). "Literate Programming" (PDF). The Computer Journal (British Computer Society) 27 (2): 97-111. doi:10.1093/comjnl/27.2.97. http://www.literateprogramming.com/knuthweb.pdf. Retrieved January 4, 2009.

3“I had the feeling that top-down and bottom-up were opposing methodologies: one more suitable for program exposition and the other more suitable for program creation. But after gaining experience with WEB, I have come to realize that there is no need to choose once and for all between top-down and bottom-up, because a program is best thought of as a web instead of a tree. A hierarchical structure is present, but the most important thing about a program is its structural relationships. A complex piece of software consists of simple parts and simple relations between those parts; the programmer’s task is to state those parts and those relationships, in whatever order is best for human comprehension not in some rigidly determined order like top-down or bottom-up.” — Donald E. Knuth, Literate Programming2

4“WEB’s macros are allowed to have at most one parameter. Again, I did this in the interests of simplicity, because I noticed that most applications of multiple parameters could in fact be reduced to the one-parameter case. For example, suppose that you want to define something like... In other words, the name of one macro can usefully be a parameter to another macro. This particular trick makes it possible to...” — Donald E. Knuth, Literate Programming2

5Knuth, Donald E.; Andrew Binstock (April 25, 2008). "Interview with Donald Knuth". http://www.informit.com/articles/article.aspx?p=1193856. Retrieved January 4, 2009. "Yet to me, literate programming is certainly the most important thing that came out of the TEX project. Not only has it enabled me to write and maintain programs faster and more reliably than ever before, and been one of my greatest sources of joy since the 1980s-it has actually been indispensable at times. Some of my major programs, such as the MMIX meta-simulator, could not have been written with any other methodology that I’ve ever heard of. The complexity was simply too daunting for my limited brain to handle; without literate programming, the whole enterprise would have flopped miserably. ... Literate programming is what you need to rise above the ordinary level of achievement."

6"Another surprising thing that I learned while using WEB was that traditional programming languages had been causing me to write inferior programs, although I hadn’t realized what I was doing. My original idea was that WEB would be merely a tool for documentation, but I actually found that my WEB programs were better than the programs I had been writing in other languages." — Donald E. Knuth, Literate Programming2

7“Thus the WEB language allows a person to express programs in a "stream of consciousness" order. TANGLE is able to scramble everything up into the arrangement that a PASCAL compiler demands. This feature of WEB is perhaps its greatest asset; it makes a WEB-written program much more readable than the same program written purely in PASCAL, even if the latter program is well commented. And the fact that there’s no need to be hung up on the question of top-down versus bottom-up, since a programmer can now view a large program as a web, to be explored in a psychologically correct order is perhaps the greatest lesson I have learned from my recent experiences.” — Donald E. Knuth, Literate Programming2

8Dominus, Mark-Jason (March 20, 2000). “POD is not Literate Programming”. Perl.com. http://www.perl.com/pub/a/tchrist/litprog.html. Retrieved January 3, 2009.

9“I chose the name WEB partly because it was one of the few three-letter words of English that hadn’t already been applied to computers. But as time went on, I’ve become extremely pleased with the name, because I think that a complex piece of software is, indeed, best regarded as a web that has been delicately pieced together from simple materials. We understand a complicated system by understanding its simple parts, and by understanding the simple relations between those parts and their immediate neighbors. If we express a program as a web of ideas, we can emphasize its structural properties in a natural and satisfying way.” — Donald E. Knuth, Literate Programming2

10Ramsey, Norman (May 13, 2008). “An Example of noweb”. http://www.cs.tufts.edu/xnr/noweb/examples/wc.html. Retrieved January 4, 2009.

11The game, also known as ADVENT, was originally written by Crowther in about 700 lines of FORTRAN code; Knuth recast it into the WEB idiom. It is available at literateprogramming.com or on Knuth’s website.

12de Marneffe, Pierre Arnoul (December 1973). Holon Programming - Report PMAR 73-23. University de Lixge, Service d’Informatique.

13Ream, Edward K. (September 2, 2008). "Leo’s Home Page". http://webpages.charter.net/edreamleo/front.html. Retrieved January 4, 2009.

14Hughes, John (January 9, 2002). Why Functional Programming Matters. Institutionen fxr Datavetenskap, Chalmers Tekniska Hxgskola,. http://www.cs.chalmers.se/xrjmh/Papers/whyfp.pdf. Retrieved January 4, 2009.