Literate programming

Print Print
Reading time 25:46

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

Literate programming is a programming paradigm introduced by Donald Knuth in which a computer program is given an explanation of its logic in a natural language, such as English, interspersed with snippets of macros and traditional source code, from which compilable source code can be generated.[1] The approach is used in scientific computing and in data science routinely for reproducible research and open access purposes.[2] Literate programming tools are used by millions of programmers today.[3]

The literate programming paradigm, as conceived by Knuth, represents a move away from writing computer 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.[4] 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 are included to hide abstractions and traditional source code.

Literate programming (LP) 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.[5] While the first generation of literate programming tools were computer language-specific, the later ones are language-agnostic and exist above the programming languages.

History and philosophy

Literate programming was first introduced by Knuth in 1984. The main intention behind this approach was to treat a program as literature understandable to human beings. This approach was implemented at Stanford University as a part of research on algorithms and digital typography. This implementation was called "WEB" by Knuth since he believed that it was one of the few three-letter words of English that hadn't already been applied to computing.[6] However, it correctly resembles the complicated nature of software delicately pieced together from simple materials.[1] The practice of literate programming has seen an important resurgence in the 2010s with the use of notebooks, especially in data science.

Concept

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",[7] 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.

Advantages

According to Knuth,[8][9] 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.[10] The resulting documentation allows the author to restart his 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.[8]

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.[11]

Contrast with documentation generation

Literate programming is very often misunderstood[12] 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.[12][13]

Critique

In 1986, Jon Bentley asked Knuth to demonstrate the concept of literate programming by writing a program in WEB. Knuth came up with an 8-pages long monolithic listing that was published together with a critique by Douglas McIlroy of Bell Labs. McIlroy praised the intricacy of Knuth's solution, his choice of a data structure (Frank M. Liang's hash trie), but noted that more practical, much faster to implement, debug and modify solution of the problem takes only six lines of shell script by reusing standard Unix utilities. McIlroy concluded:[14]

Knuth has shown us here how to program intelligibly, but not wisely. I buy the discipline. I do not buy the result. He has fashioned a sort of industrial-strength Faberge egg—intricate, wonderfully worked, refined beyond all ordinary desires, a museum piece from the start.

McIlroy later admitted that his critique was unfair, since he criticized Knuth's program on engineering grounds, while Knuth's purpose was only to demonstrate the literate programming technique.[15] In 1987, Communications of the ACM published a followup article which illustrated literate programming with a C program that combined artistic approach of Knuth with engineering approach of McIlroy, with a critique by John Gilbert.[16]

Workflow

Implementing literate programming consists of two steps:

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

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

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.[17] This example provides a good illustration of the basic elements of literate programming.

Creation of macros

The following snippet of the wc literate program[17] 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 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.

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>
    @

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 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" or "case". This is illustrated by the following snippet of the wc literate program.[17]

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 */
    }
    @

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.[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 "<<...>>=", 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 ("plus" is added by the document formatter for readability, and is not in the code).[17]

 The grand totals must be initialized to zero at the beginning of the program.
If we made these variables local to main, we would have to do this  initialization
explicitly; however, C globals are automatically zeroed. (Or rather,``statically
zeroed.'' (Get it?)

    <<Global variables>>+=
    long tot_word_count, tot_line_count,
         tot_char_count;
      /* total number of words, lines, chars */
    @

Record of the train of thought

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.[18]

Remarkable examples

  • 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 practices

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.[19] 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 (some of them don't have macros and hence violate the order of human logic principle):

Name Supported Languages Written in Markup Language Comments
WEB Pascal Pascal TeX The first published literate programming environment.
CWEB C++ and C C TeX Is WEB adapted for C and C++.
NoWEB Any C, AWK, and Icon LaTeX, TeX, HTML and troff It is well known for its simplicity and it allows for text formatting in HTML rather than going through the TeX system.
Literate Any D Markdown Supports TeX equations. Compatible with Vim (literate.vim)
FunnelWeb Any C HTML and TeX It has more complicated markup, but has many more flexible options
NuWEB Any C++ LaTeX It can translate a single LP source into any number of code files. It does it in a single invocation; it does not have separate weave and tangle commands. It does not have the extensibility of noweb
pyWeb Any Python ReStructuredText Respects indentation which makes usable for the languages like Python, though you can use it for any programming language.
Molly Any Perl HTML Aims to modernize and scale it with "folding HTML" and "virtual views" on code. It uses "noweb" markup for the literate source files.
Codnar Ruby It is an inverse literate programming tool available as a Ruby Gem. Instead of the machine-readable source code being extracted out of the literate documentation sources, the literate documentation is extracted out of the normal machine-readable source code files.
Emacs org-mode Any Emacs Lisp Plain text Requires Babel,[20] which allows embedding blocks of source code from multiple programming languages[21] 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.[22]
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.[23]
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."Maple Worksheets". www.maplesoft.com. Retrieved 2020-05-30.
Wolfram Notebooks Wolfram Language Wolfram Language Wolfram notebooks are a platform-agnostic literate programming method that combines text and graphics with live code.[24][25]
Playgrounds Swift (programming language) Provides an interactive programming environment that evaluates each statement and displays live results as the code is edited. Playgrounds also allow the user to add Markup language along with the code that provide headers, inline formatting and images.[26]
Jupyter Notebook, formerly IPython Notebook Python and any with a Jupyter Kernel HTML 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 you to develop a python library in Jupyter Notebooks, putting all your code, tests and documentation in one place.
Julia (programming language) Supports the iJulia mode of development which was inspired by iPython.
Agda (programming language) Supports a limited form of literate programming out of the box.[27]
Eve programming language Programs are primarily prose.[28] Eve combines variants of Datalog and Markdown with a live graphical development environment.
R Markdown Notebooks (or R Notebooks) R, Python, Julia and SQL PDF, Microsoft Word, LibreOffice and presentation or slide show formats plus interactive formats like HTML widgets [29]
Sweave R PDF [30][31]
Knitr R LaTeX, PDF, LyX, HTML, Markdown, AsciiDoc, and reStructuredText [32][33]
Codebraid Pandoc, Rust, Julia, Python, R, Bash
Pweave Python PDF

Other useful tools include

  • The Leo text editor is an outlining editor which supports optional noweb and CWEB markup. The author of Leo 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 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.[34]
  • The Haskell programming language has native support for semi-literate programming. The compiler/interpreter supports two file name extensions: .hs and .lhs; the latter stands for literate Haskell.
The literate scripts can be full LaTeX source text, at the same time it can be compiled, with no changes, because the interpreter only compiles the text in a code environment, for example
% here text describing the function:
\begin{code}
fact 0 = 1
fact (n+1) = (n+1) * fact n
\end{code}
here more text
The code can be also marked in the Richard Bird style, starting each line with a greater than symbol and a space, preceding and ending the piece of code with blank lines.
The LaTeX listings package provides a lstlisting environment which can be used to embellish the source code. It can be used to define a code environment to use within Haskell to print the symbols something like:
\newenvironment{code}{\lstlistings[language=Haskell]}{\endlstlistings}

\begin{code}
comp :: (beta -> gamma) -> (alpha -> beta) -> (alpha -> gamma)
(g `comp` f) x = g(f x)
\end{code}
can be configured to yield something like this:
Although the package does not provide means to organize chunks of code, one can split the LaTeX source code in different files. See listings manual for an overview.
  • The Web 68 Literate Programming system used Algol 68 as the underlying programming language, although there was nothing in the pre-processor 'tang' to force the use of that language.[35]
  • The customization mechanism of the Text Encoding Initiative which enables the constraining, modification, or extension of the TEI scheme enables users to mix prose documentation with fragments of schema specification in their One Document Does-it-all format. From this prose documentation, schemas, and processing model pipelines can be generated and Knuth's Literate Programming paradigm is cited as the inspiration for this way of working.[36]

See also

  • Documentation generator – the inverse on literate programming where documentation is embedded in and generated from source code
  • Notebook interface – virtual notebook environment used for literate programming
  • Sweave and Knitr – examples of use of the "noweb"-like Literate Programming tool inside the R language for creation of dynamic statistical reports
  • Self-documenting code – source code that can be easily understood without documentation

References

  1. ^ a b c v w x y z Knuth, Donald E. (1984). "Literate Programming" (PDF). The Computer Journal. British Computer Society. 27 (2): 97–111. doi:. Retrieved January 4, 2009.
  2. ^ Schulte, Eric (2012). "A Multi-Language Computing Environment for Literate Programming and Reproducible Research" (PDF). Journal of Statistical Software. 46 (3). doi:. Archived (PDF) from the original on 9 November 2014. Retrieved 30 May 2020.
  3. ^ Kery, Mary Beth (April 2018). "The Story in the Notebook: Exploratory Data Science using a Literate Programming Tool". CHI '18: Proceedings of the 2018 CHI Conference on Human Factors in Computing Systems. ACM. pp. 1–11. doi:10.1145/3173574.3173748.
  4. ^ "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 Programming[1]
  5. ^ 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 num 5 on p.365
  6. ^ "Literate Programming" (PDF). archive.computerhistory.org. Retrieved 2019-06-03.
  7. ^

    "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 Programming[1]
  8. ^ a b Knuth, Donald E.; Binstock, Andrew (April 25, 2008). "Interview with Donald Knuth". 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.
  9. ^

    "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 Programming[1]
  10. ^

    "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 Programming[1]
  11. ^ ""Oral History of Donald Knuth"- an Interview with Ed Feigenbaum" (PDF). archive.computerhistory.org. Retrieved 2018-12-07.
  12. ^ a b Dominus, Mark-Jason (March 20, 2000). "POD is not Literate Programming". Perl.com. Archived from the original on January 2, 2009.
  13. ^

    "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 Programming[1]
  14. ^ Bentley, Jon; D. E. Knuth; M. D. McIlroy (1986). "Programming pearls" (PDF). Communications of the ACM. 29 (6): 471–483. doi:10.1145/5948.315654. S2CID 10128137.
  15. ^ Mahoney, Michael S. (18 August 1989). "Interview with M. D. McIlroy".
  16. ^ Van Wyk, Christopher J.; Hanson, David R.; Gilbert, John (July 1987). "Literate programming" (PDF). Communications of the ACM. 30 (7): 593–599. doi:10.1145/28569.315738. S2CID 5328652.
  17. ^ a b c d Ramsey, Norman (May 13, 2008). "An Example of noweb". Retrieved January 4, 2009.
  18. ^ 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 Archived 2008-08-20 at the Wayback Machine.
  19. ^ de Marneffe, Pierre Arnoul (December 1973). "Holon Programming – Report PMAR 73-23". University de Liège, Service d'Informatique. Cite journal requires |journal= (help)
  20. ^ https://orgmode.org/worg/org-contrib/babel/intro.html
  21. ^ https://orgmode.org/worg/org-contrib/babel/languages.html#langs
  22. ^ https://orgmode.org/worg/org-contrib/babel/intro.html#literate-programming
  23. ^ Ashkenas, Jeremy. "Literate CoffeeScript". Retrieved 13 November 2014.
  24. ^ Milestones in Computer Science and Information Technology by Edwin D. Reilly, p. 157.
  25. ^ "Wolfram Notebooks". www.wolfram.com. Retrieved 2018-11-28.
  26. ^ "Markup Formatting Reference: Markup Overview". developer.apple.com. Retrieved 2015-11-15.
  27. ^ "Literate Agda". Agda Wiki. Retrieved 2017-03-26.
  28. ^ "Eve and Literate Progamming". Eve Handbook. Archived from the original on 2017-05-24. Retrieved 2017-05-25.
  29. ^ Yihui Xie; Joseph J. Allaire; Garrett Grolemund (2019), R Markdown: The Definitive Guide, Chapman & Hall, Wikidata Q76441281
  30. ^ Leisch, Friedrich (2002). "Sweave, Part I: Mixing R and LaTeX: A short introduction to the Sweave file format and corresponding R functions" (PDF). R News. 2 (3): 28–31. Retrieved 22 January 2012.
  31. ^ Pineda-Krch, Mario (17 January 2011). "The Joy of Sweave – A Beginner's Guide to Reproducible Research with Sweave" (PDF). Retrieved 22 Jan 2012.
  32. ^ Xie, Yihui (2015). Dynamic Documents with R and knitr, 2nd Edition. Chapman & Hall/CRC. ISBN 9781498716963.
  33. ^ Xie, Yihui. "knitr: A General-Purpose Tool for Dynamic Report Generation in R" (PDF).
  34. ^ Ream, Edward K. (September 2, 2008). "Leo's Home Page". Retrieved April 3, 2015.
  35. ^ Mountbatten, Sian. "Web 68: Literate programming with Algol 68". Archived from the original on 20 January 2013. Retrieved 1 January 2013.
  36. ^ "TEI Guidelines". TEI Consortium. Archived from the original on 2018-08-22. Retrieved 2018-08-23.

Further reading

External links

By: Wikipedia.org
Edited: 2021-06-18 19:24:27
Source: Wikipedia.org