03/07/22
Most programmers haven’t heard of literate programming, and the few that have tend to think it means writing a lot of comments around your code. However, simply explaining code with prose, does not constitute literate programming. Consider the following quote from it’s inventor:
Some of my major programs 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 – Donald Knuth
Does this extraordinary leap in effectiveness sound like something that comes from re-explaining what code does? I didn’t think so.
The real advantages of literate programming come from two principles:
Code should be written for humans not machines.
Program designers utilize many types of information, not just code.
Literate programming systems help programmers apply these principles by providing two standard operations tangle and weave which manipulate and organize source code.
Literate programs are written in plain text documents, but between the traditional prose, blocks of code (in any language) are interleaved. For example:
You can think of them like markdown documents, but with an important addition. In a literate program, blocks of code have identifiers, and they can reference each other. Each reference modifies the contents of a prior block, or includes it at the specificied location.
The operation tangle resolves all these references and produces normal source code to be read by the compiler.
Let’s try it out.
In the block above we introduced a subsets function, also known as the powerset:
\begin{equation} \mathcal{P}(A) = \{ S \text{ is a set } \colon S \subseteq A \}\end{equation}Implementing it can be a little bit tricky. If you have never done it before, I recommend you write out some examples on paper and see if you can figure it out.
\begin{align} \mathcal{P}(\{1, 2, 3\}) = \{ &\{1, 2, 3\}, \\
&\{1, 2\}, \{1, 3\}, \{2, 3\}, \\
&\{1\}, \{2\}, \{3\}, \\
&\emptyset \} \\\end{align}The key insight, is that if we take an element out of the original set, and all the subsets which contain it, we can get back the full subsets, by making a copy of each other subset and inserting the element back in. In other words, the number of subsets doubles with each element in the set:
\begin{equation} |\mathcal{P}(A)| = 2^{|A|}\end{equation}Here is rough outline in code:
function subsets(set) {
@{base case}
@{remove element and compute subsets of smaller set}
return @{subsets without element}
.concat( @{subsets with element} );
}
@{test subsets}
This a recursive function, so we need a base case. If the input set is empty, its only subset is the empty set:
We use recursion by removing one element and computing the subsets of that array:
const element = set.pop();
const smaller = subsets(set);
Used by 1
All the smaller subsets are still subsets of our original set, so we want to include those.
But, we are missing all the subsets involving element. We simply
add element in to each set.
That’s all! Applying tangle to the literate file produces a single source file subsets.js.
A typical literate file produces many source files. Block types aren’t limited to a single language either. Here is how to run it in your command line:
node subsets.js
Of course, the example above goes into more detail, and is separated into more blocks, than is helpful for most production code. It is just meant to illustrate how a little explanation, analysis, and division into logical parts, can make code significantly more readable.
At the micro-level we can overcome a lot of limitations imposed by the language syntax, kind of like a powerful macro system. In the example we break out small sub-expressions, even from the middle of statement, to explain further, or to make things more readable.
Some other use cases include:
C.More importantly, at the macro level we can control the overall presentation of the program. This is difficult to convey in a brief article, but think of it like writing code as a book or article. You can introduce your code with an overview, take time to develop the most important ideas and characters, gradually build up to the big picture, and then maybe fill in some extra details.
Consider the last time you started working on a large code base someone else wrote. It was probably overwhelming, especially considering how much of modern code is boiler plate, and interfacing between systems. You probably wanted to know:
A well-written README can point you to some files to get started, but it won’t isolate the core concepts from all the other code details surrounding them. Literate programs allow you to answer these questions naturally.
The weave operation generates documentation files from the literate file. This is a nicely formatted document like the one you are reading right now! This presents the code in a readable form,
If you are like me, you probably maintain some kind of design document recording decisions make during the project and data to provide justifications. Not, all of this content is appropriate to include in the source code, but a lot of it is, and the literate weave operation let’s you do just that.
Here are some examples of media you can include, as well as a specific use case I have desired in the past:
It’s important to note how this is different from tools which generate interface “documentation” from source code. Literate programs usually include the entire source, not just interfaces. Since it focuses on prose, it’s much more natural to include other media formats. You aren’t littering comments with awkward media references.
I have told you a bit about why I like Literate programming, but to really understand how it benefits your code read some examples, or better yet, try it on your next project. To get started you will need a literate programming tool of which there are many.
I recently wrote srcweave which was used to write this article you are reading now. See my article “Write your own Proof-of-Work Blockchain” for another example.
Literate is the system I used for several years, before writing my own. It is self hosting, which I find pretty cool, so you can read it’s own source code.
Donald Knuth wrote the original literate programming tools web and cweb. Of course, they output TeX instead of HTML for documentation. I don’t know anyone else who actually uses his tools, since TeX is more involved than most people need, but they are still worth learning from. The source for TeX is written in it, and is famous for having very few bugs and being extremely reliable.