Literate programming

Template:Short description Template:Use American English Template:Use mdy dates

File:Literate Programming book cover.jpg

Literate Programming by Donald Knuth is the seminal book on literate programming.

Literate programming is a programming paradigm introduced in 1984 by Donald Knuth in which a computer program is given as an explanation of how it works in a natural language, such as English, interspersed (embedded) with snippets of macros and traditional source code, from which compilable source code can be generated.<ref name="TCJ_LP">Template:Note label Template:Note label Template:Note label Template:Note label Template:Note label Template:Cite journal</ref> The approach is used in scientific computing and in data science routinely for reproducible research and open access purposes.<ref>Template:Cite journal</ref> Literate programming tools are used by millions of programmers today.<ref>Template:Cite conference</ref>

The literate programming paradigm, as conceived by Donald Knuth, represents a move away from writing computer programs in the manner and order imposed by the compiler, and instead gives programmers macros to develop programs in the order demanded by the logic and flow of their thoughts.<ref>Template:Block quote</ref> Literate programs are written as an exposition of logic in more natural language in which macros are used to hide abstractions and traditional source code, more like the text of an essay.

Literate programming (LP) tools are used to obtain two representations from a source file: one understandable by a compiler or interpreter, the "tangled" code, and another for viewing as formatted documentation, which is said to be "woven" from the literate source.<ref name="ObliqueScottReference">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 in 1513. – the actual citation appeared as an epigraph in a May 1986 article by Jon Bentley and Donald Knuth in one of the classical "Programming Pearls" columns in Communications of the ACM, vol. 29, no. 5, p. 365.</ref> While the first generation of literate programming tools were computer language-specific, the later ones are language-agnostic and exist beyond the individual programming languages.

History and philosophyEdit

Literate programming was first introduced in 1984 by Donald Knuth, who intended it to create programs that were suitable literature for human beings. He implemented it at Stanford University as a part of his research on algorithms and digital typography. The implementation was called "WEB" since he believed that it was one of the few three-letter words of English that had not yet been applied to computing.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> However, it resembles the complicated nature of software delicately pieced together from simple materials.<ref name="TCJ_LP" /> The practice of literate programming has seen an important resurgence in the 2010s with the use of computational notebooks, especially in data science.

ConceptEdit

Literate programming is writing out the program logic in a human language with included (separated by a primitive markup) code snippets and macros. 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",<ref>Template:Block quote</ref> 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.

AdvantagesEdit

According to Knuth,<ref name="Knuth">{{#invoke:citation/CS1|citation |CitationClass=web }}</ref><ref>Template:Block quote</ref> literate programming provides 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's creation.<ref>Template:Block quote</ref> The resulting documentation allows the author to restart their own thought processes at any later time, and allows other programmers to understand the construction of the program more easily. 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, 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.<ref name="Knuth" />

Knuth also claims that literate programming can lead to easy porting of software to multiple environments, and even cites the implementation of TeX as an example.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>

Contrast with documentation generationEdit

Literate programming is very often misunderstood<ref name="MJD2000">{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> to refer only to formatted documentation produced from a common file with both source code and comments – which is properly called documentation generation – or to voluminous commentaries included with code. This is the converse of literate programming: well-documented code or documentation extracted from code follows the structure of the code, with documentation embedded in the code; while in literate programming, code is embedded in documentation, with the code following the structure of the documentation.

This misconception has led to claims that comment-extraction tools, such as the Perl Plain Old Documentation or Java Javadoc systems, 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.<ref name="MJD2000" /><ref>Template:Block quote</ref>

WorkflowEdit

Implementing literate programming consists of two steps:

Weaving: Generating a comprehensive document about the program and its maintenance.
Tangling: Generating machine executable code

Weaving and tangling are done on the same source so that they are consistent with each other.

ExampleEdit

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.<ref name="noweb-wc">{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> This example provides a good illustration of the basic elements of literate programming.

Creation of macrosEdit

The following snippet of the wc literate program<ref name="noweb-wc" /> 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 (<<...>>) that indicate macros. The @ symbol which, in a noweb file, indicates the beginning of a documentation chunk. 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. <syntaxhighlight lang="c"> The purpose of wc is to count lines, words, and/or characters in a list of files. The number of lines in a file is ......../more explanations/

Here, then, is an overview of the file wc.c that is defined by the noweb program wc.nw:

   <<*>>=
   <<Header files to include>>
   <<Definitions>>
   <<Global variables>>
   <<Functions>>
   <<The main program>>
   @

We must include the standard I/O definitions, since we want to send formatted output to stdout and stderr.

   <<Header files to include>>=
   #include <stdio.h>
   @

</syntaxhighlight> 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.

Program as a webEdit

Macros are not the same as "section names" in standard documentation. Literate programming macros hide the real code behind themselves, and be used inside any low-level machine language operators, often inside logical operators such as if, while or case. This can be seen in the following wc literate program.<ref name="noweb-wc" />

<syntaxhighlight lang="c"> The present chunk, which does the counting, was actually one of the simplest to write. We look at each character and change state if it begins or ends a word.

   <<Scan file>>=
   while (1) {
     <<Fill buffer if it is empty; break at end of file>>
     c = *ptr++;
     if (c > ' ' && c < 0177) {
       /* visible ASCII codes */
       if (!in_word) {
         word_count++;
         in_word = 1;
       }
       continue;
     }
     if (c == '\n') line_count++;
     else if (c != ' ' && c != '\t') continue;
     in_word = 0;
       /* c is newline, space, or tab */
   }
   @

</syntaxhighlight>

The macros stand for any chunk of code or other macros, and are more general than top-down or bottom-up "chunking", or than subsectioning. Donald Knuth said that when he realized this, he began to think of a program as a web of various parts.<ref name="TCJ_LP" />

Order of human logic, not that of the compilerEdit

In a noweb literate program besides the free order of their exposition, the chunks behind macros, once introduced with <<...>>=, 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 (+ is added by the document formatter for readability, and is not in the code).<ref name="noweb-wc" />

Template:Pre

Record of the train of thoughtEdit

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 wrote a "novel" which explains the code of the interactive fiction game Colossal Cave Adventure.<ref>The 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 Template:Webarchive.</ref>

Remarkable examplesEdit

Axiom, which is evolved from scratchpad, a computer algebra system developed by IBM. It is now being developed by Tim Daly, one of the developers of scratchpad, Axiom is totally written as a literate program.

Literate programming practicesEdit

The first published literate programming environment was WEB, introduced by 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 Marneffe.<ref>Template:Cite report</ref> 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.

There are various other implementations of the literate programming concept as given below. Many of the newer among these do not have macros and hence do not comply with the order of human logic principle, which makes them perhaps "semi-literate" tools. These, however, allow cellular execution of code which makes them more along the lines of exploratory programming tools.

Name	Supported languages	Written in	Markup language	Macros & custom order	Cellular execution	Comments
WEB	Pascal	Pascal	TeX	Template:Yes	Template:No	The first published literate programming environment.
CWEB	C++ and C	C	TeX	Template:Yes	Template:No	Is WEB adapted for C and C++.
NoWEB	Any	C, AWK, and Icon	LaTeX, TeX, HTML and troff	Template:Yes	Template:No	It is well known for its simplicity and it allows for text formatting in HTML rather than going through the TeX system.
Emacs org-mode	Any	Emacs Lisp	Plain text			citation	CitationClass=web }}</ref> which allows embedding blocks of source code from multiple programming languages<ref>{{#invoke:citation/CS1\|citation	CitationClass=web }}</ref> within a single text document. Blocks of code can share data with each other, display images inline, or be parsed into pure source code using the noweb reference syntax.<ref>{{#invoke:citation/CS1\|citation	CitationClass=web }}</ref>
CoffeeScript	CoffeeScript	CoffeeScript, JavaScript	Markdown			CoffeeScript supports a "literate" mode, which enables programs to be compiled from a source document written in Markdown with indented blocks of code.<ref>{{#invoke:citation/CS1\|citation	CitationClass=web }}</ref>
Maple worksheets	Maple (software)		XML			Maple worksheets are a platform-agnostic literate programming environment that combines text and graphics with live code for symbolic computation.{{#invoke:citation/CS1\|citation	CitationClass=web }}
Wolfram Notebooks	Wolfram Language		Wolfram Language			Wolfram notebooks are a platform-agnostic literate programming method that combines text and graphics with live code.<ref>Milestones in Computer Science and Information Technology by Edwin D. Reilly, p. 157.</ref><ref>{{#invoke:citation/CS1\|citation	CitationClass=web }}</ref>
Jupyter Notebook, formerly IPython Notebook	Python and any with a Jupyter Kernel		JSON format Specification for ipynb	Template:No	Template:Yes	Works in the format of notebooks, which combine headings, text (including LaTeX), plots, etc. with the written code.
nbdev	Python and Jupyter Notebook		`nbdev` is a library that allows one to develop a python library in Jupyter Notebooks, putting all code, tests and documentation in one place.
Julia (programming language)				Pluto.jl is a reactive notebook environment allowing custom order. But web-like macros aren't supported.	Template:Yes	Supports the iJulia mode of development which was inspired by iPython.
Agda (programming language)						citation	CitationClass=web }}</ref>
Sweave	R		PDF			<ref name="Leisch2002">Template:Cite journal</ref><ref name="Pineda-Krch2011">{{#invoke:citation/CS1\|citation	CitationClass=web }}</ref>
Knitr	R		LaTeX, PDF, LyX, HTML, Markdown, AsciiDoc, and reStructuredText			<ref>Template:Cite book</ref><ref>{{#invoke:citation/CS1\|citation	CitationClass=web }}</ref>
Literate	Any	D	Markdown	Template:Yes	Template:No	Supports TeX equations. Compatible with Vim.

Other useful tools include:

Template:Bulleted list

ReferencesEdit

Template:Reflist

External linksEdit

Template:Programming paradigms navbox Template:Donald Knuth navbox