I've been planning (for 2+ years now so it probably won't happen) writing a large blog post about this matter, which would be called “Tries, Packed Tries, and the Bentley–Knuth–McIlroy story”:
• Part 1 would introduce the trie data structure both abstractly (the tree structure) and concretely (how exactly to represent the children of a node), with the trade-offs: as a linked list (space-efficient, slow lookup), as an array (fast lookup, takes space), or as some more nontrivial tree structure itself (“yo dawg…”). Then we'd discuss the really cool idea of “packing” the array, as nicely described in Frank Liang's thesis https://tug.org/docs/liang/ (also mentioned in TAOCP Exercise 6.3:4 and answer, which incidentally refers to the CACM Bentley–Knuth–McIlroy article that we're talking about). We'd also illustrate how hyphenation is done in the TeX program using packed tries (maybe this can be a separate post).
• Part 2 would go into the Bentley–Knuth-McIlroy story:
• Part 2a ("Before"): Bentley's thesis/book on writing efficient programs, and the Programming Pearls column. Knuth writing TeX first for himself in SAIL in 1977–78. The instant interest and ports/rewrites it led to. Knuth responding by rewriting TeX into its current form in 1980–82, and how the goals of portable software (thus Pascal, and its limitations! see BWK rant) and of eventually publishing it as a book led him to the idea of literate programming, which he still considers the most important outcome of his years into the TeX project. Meanwhile, at Bell Labs, McIlroy's invention of Unix pipes, and the instant excitement of "pipe day". (“It was absorbed instantly into one's outlook on programming. And by the end of the week secretaries were piping the output of NROFF into the printer”) The Unix philosophy, and how it took a while to spread. How these three threads came together in 1986, when Bentley read Knuth's TeX, wrote about LP in his Pearls column, and published one program of Knuth's (the random-numbers one) and asked him to write another (the frequent words one).
• Part 2b (the program): How Knuth ingeniously combined the idea of packed tries with that of hashing with linear probing, to create the data structure especially for this problem (maybe we can call it a hash-packed trie?). Another look at his very nice idea/program, presented differently (maybe some illustrations of how the data structure works), and some design choices he made.
• Part 2c (the review and later): How Bentley got McIlroy to review it, a close reading of the review: its actual content and points about LP and Knuth's style, and finally the (first sentence and) last part where McIlroy used the review to advertise his own Unix philosophy and the short shell pipeline version. The further reactions to this, including Bentley's remarks in the same column, and later articles and reactions like the "prefabs" comment (https://news.ycombinator.com/item?id=22406070). The short-lived LP column in CACM that it spawned (https://shreevatsa.net/post/programming-pearls/) and how it fizzled out, how it turns out everyone wants to do LP in their own system. How the story got bastardized over time (the misleading "More shell less egg" blog post for example, and some other examples of people misunderstanding the history entirely).
• Part 3 would compare the two approaches (even though they are not meant to be compared!), mention how at https://codegolf.stackexchange.com/questions/188133/ I simply translated Knuth's program into C++ and beat the then-fastest Rust solution (since beaten again by translation from C++ back into Rust: still based on the trie idea though!), some words about cache misses and 32-bit “pointers” in a 64-bit world (and Knuth's rant about it).
Something like that: it's probably too long for me to ever get around to writing it (or for anyone to be interested in reading), though…
Write it as three self-contained blog posts, then you can get part of it out and even if you lose interest later people are still enriched by the first one or two!
The problem that our industry runs into (NB: not just this industry) with critiques like McIlroy's is that people remember the highlights ("Haha, LP is silly and makes fragile, Faberge eggs instead of robust systems.") instead of remembering the context (Knuth was asked to illustrate LP, he did, McIlroy critiqued the monolithic resulting program more than the LP style itself).
This happens repeatedly (not just this example, many others), and since the vast majority of people are never going to go back to the original sources we have a giant game of telephone. Generation after generation are given a variation on the summary theme, further and further removed from the original context. The speaker will elaborate on the criticism, but since they didn't read it themselves they're actually just bullshitting (semi-honest effort as they're pulling in the information they were given, but it's still bullshitting because they didn't bother to read).
Funny, I came in here to write this exact comment, but I was going to use Word. Wonder why our minds go to MS Office... First thing that comes to mind when we think "big and complicated?"
Let's schedule a scrum. Come ready with relevant user stories and appropriate story points. But maybe we need a powwow beforehand to decide on a theme. Either way I want us to settle on tasks an be ready to sprint by EOD.
I am super excited by https://observablehq.com which has made an out-of-the-box literate programming environment for Javascript zero configuration (like Knuth's it has a non-linear execution order). Since switching to literate programming I have found myself adopting a documentation-driven-development methodology, where I ponder about the purpose of the notebook in the introduction, and because I reread it every time I open the notebook, the clarity of the software goes up, which also feedbacks into the ongoing development process too.
It takes a little while before habits change, but I think I have learnt more in the last year at age 40 than I did in my first year of undergraduate aged 19.
An aspect of Observable which is particularly compelling since Knuth is the fact that inter-notebook dependencies are hyperlinks, so these are not standalone literate programming artifacts, but they are a graph of explanation too. You can learn a lot by surfing notebook dependencies. Bundling code with documentation is such a win.
The other thing about Observable is the cells are reactive, so your documentation is not necessarily static either. You can provide animated interactive explanations too.
More info on the different types of content you can embed
Kinda but observable is more because the notebooks cells reactively recompute. And it's written in javascript and ran in a browser so you have the languages proper development tooling integrated (e.g. chrome Dev tools). And you can easily share it as its the web.
Hm, that's really relative... on Babel, you can also have reactive cells, and while it's true that having Obervable run on the web + JS is great, I could say that Babel "is more" because it supports pretty much any language, not only JS, and does not require an internet connection to work.
If I was shilling webcode.run then I would think a disclosure would be appropriate, but as I was just talking about how great Observable is as a literate programming env, I do not think I have anything to disclose.
"non-linear execution order" ? I can't see how it's kind of spreadsheet moreover you don't really do metaprogramming BEFORE execution which is more what I understand about literate programming.
When I first started in this industry, I thought it was essentially immune to fads. "Does it work? Yes? Ship it!" Seems so naïve. Whole paradigms rise and fall for arbitrary reasons: a viral blog post, or an open letter, or the tech stack of that cool startup. Perhaps this blog post will lead to the reformation of the literate programming approach.
Yeah it's really surprising to see how supposedly scientifically educated people are driven completely by fads and basic social needs and personal gain, and don't bother to even try to motivate decisions with anything more than "I like it" etc.
Telling computers what to do and how to do it is an art, a craft, a practice, a discipline, a medium, a profession, and a science (and probably a few more categories besides). It is just isn't (usually) all of those things at once. Most of the difficulties we have in discussions about the subject have to do with category errors. Literate Programming has stylistic, technical, toolchain, and disciplinary aspects, and Knuth's exemplar demonstrated these. It was then critiqued on pragmatic grounds. I'm not sure if this counts as a bait and switch, rope a dope, or strawman.
I mean, if I was participating in a computer programming class and given the same problem as an assignment, I would write a program to satisfy the requirements. If then told that I should have written a few lines of shell script instead and given a poor grade, I would be livid at the instructor.
As an aside, I was interested to know if there are LP tools for shell scripting. A cursory search turned this up:
> As an aside, I was interested to know if there are LP tools for shell scripting.
jupyter + xon.sh kernel almost can do it too.
Well notebooks aren't exactly to explain programs but to experience with them, no weave or tangle, you can only execute them if your cells are in top-down order.
Anyhow, being able to save the experimentation fragments can lead to better documentation compared to when you experiment in a different terminal.
A near non-sequitur per your aside (I agree with the rest...): https://github.com/bashup/events is one of my favorite little things. I even blogged about it in January!
That's exactly because the only necessarily important thing is "does it work?" So the rest is open to interpretation and susceptible to religious behavior.
"does it work?" is also open to interpretation and susceptible to religious behavior.
There is a paper [0] which documents an interesting disagreement about a project: The developers considered it a huge success but management considers it a complete disaster. Very different interpretation. Does it work?
As an example for religious behavior we could look at Powerpoint. An application which is used with practically religious fervor. However, the application is mostly misused so badly that the goal of supporting the transfer of knowledge or persuading people is not achieved. Does it work?
Without agreement about the goal/requirements, you can not determine if the resulting software works. In my experience, precise goals/requirements are often missing, so a simple question like "does it work?" is also open to interpretation.
[0] Software Developer Perceptions about Software Project Failure: A Case Study by Kurt R Linberg, 1999
A scientific approach would be to have a large number of program requirement documents and a large number of programmers, and assign a methodology to half the programmers, forbid the method to to the other half, and then measure the output from the exercise along important axes like time to completion, correctness, and compute resource consumption. This has been approximated in studies a small number of times, but with too small sample sizes. Achieving robust results would be enormously expensive.
I'm actually interested in the sociology/economics of these dynamics. They're everywhere. We live in a blur and somehow things happen.. but the forces driving these moves are still difficult to grasp (for me).
Aren't these dynamics generally known as "fashion"?
There's probably tons of (academic and industry) research on the topic from sociological and economical aspects. Well, if not so much with a focus on how fashions emerge and manifest themselves within the field of programming, probably at least in many other fields.
Fashion is a simple way to describe it, I was looking for deeper analysis. Political influence, past fad fatigue and/or economic dry up (when the system has tried a new thing long enough it kinda wants to seek other paths, energy and belief flows naturally there, until a new slowdown occurs).
You may be interested in the idea of memetics. Whether it's really "correct" in any absolute sense, there are some interesting ideas and models there for things like this.
If you want to read a thoughtful and valid criticism of Knuth’s ideas, I recommend https://www.cs.tufts.edu/~nr/pubs/lpsimp-abstract.html by Norman Ramsey. The observation that rang most true for me was: literate programming should be written in the style of a car manual, not a novel.
Noweb was an amazing little tool. Very sweet clean architecture with a simple straightforward textual intermediate representation, accessible to simple pipelined processing, and a lovely community of add-ons.
And then? It was reimplemented in 'icon', incompatible Proteine, too, and the community feel apart.
That's a real pity because noweb got almost everything right.
However.
Imnsho the real challenge for literate programming is IDE support. Not only do you embed languages into each other. In addition you chip chop your code into fragments and distribute them all over your file...
The notebooks I saw so far are linear, single language and don't do the weaving (shuffle and embed the code chunks into full files)
For their purpose, incrementally derive some computation and data analysis, that's fine. For describing a complex system to both a human reader and a machine, in that order, that would not be enough.
It occurs to me that the root of the problem is that we have competing motivations. On the one side you have the desire to have well documented code, maximizing the benefit to those reading/studying it. On the other side you have the desire to get the most coding done in the least amount of time (something you can push to production, that correctly implements some task or purpose).
Both of these motivations are valid and good. The hard part is knowing at what level of each do we get the best balance of the two.
In one the situation, the "novel" analogy would be appropriate. For instance, I would be very interested in detailed explanations of something like PostgreSQL. A well-written book by someone (or "someones") with intimate knowledge of that code could be tremendously valuable. Here I have in mind something that actually walks through parts of the code, in a literate programming style.
On the other hand, maybe you don't want that much detail, but you still want some understanding of the code in order to do a small task - in that vein, something of the 'car manual' variety would be more appropriate.
I can imagine a full spectrum, from a multi-volume Knuth-like set to something on the order of a single-page cheat sheet. The problem is, it always comes down to how much time do you have to accomplish what you need to accomplish, and how much time will those writing the checks allow you to make informed choices on how things are documented (which, unfortunately, is all too often, ZERO).
It seems to me that both McIlroy’s original critique and this blog post miss the point by a mile. It’s completely meaningless to compare the relative merits of the two solutions, because Knuth’s ultimate goal isn’t to produce a solution.
Doing a presentation on literate programming has to deal with two more or less contradictory concerns — you need a sufficiently simple problem that your audience can follow along, but you need your solution to be complex enough that you can actually illustrate LP.
A sorted frequency table is a simple enough problem statement, a trie is a sufficiently elaborate solution that doesn’t feel too contrived while also being familiar enough that the audience can follow along. Knuth’s approach was pretty much the perfect way to hit both of those requirements!
> It seems to me that both McIlroy’s original critique and this blog post miss the point by a mile. It’s completely meaningless to compare the relative merits of the two solutions, because Knuth’s ultimate goal isn’t to produce a solution.
I don’t follow: aren’t you effectively restating the blog post’s argument? How did the blog post miss the point?
> A sorted frequency table is a simple enough problem statement, a trie is a sufficiently elaborate solution that doesn’t feel too contrived while also being familiar enough that the audience can follow along.
As one of the essays linked yesterday noted, Knuth did not pick the problem, he specifically asked the editor to do so, such that he would not necessarily select a problem perfectly suited to LP.
Also shell pipelines are very flexible, but there is a limit of what you can achieve with this approach. This complexity limit is the reason why they invented more flexible scripting languages like perl and python.
Python (and any other general purpose languages) shouldn't be considered a replacement for shell pipelines but rather an extension tool. Actually, the pipelines survived 50 years in big
part due to how easy to extend them: just define something that can read from stream of bytes, and write to another one (use what ever language you like).
The origin of composing simple programs that do one thing well is likely was originated as the consequence of the introduction of shell pipelines (or the genius pre-designed property).
Pipelines is a good example of "less is more" concept.
Perl was the other language mentioned and it was in fact marketed as the One Tool to Rule, with examples given of how to replace your "complex and brittle" shell pipelines with a few lines of Perl.
I think people genuinely get confused that the century that has dates like 19XX was the 20th century, so they say "1900s" to cover for it. But that has an established meaning, namely 1900-1909.
> But that has an established meaning, namely 1900-1909.
I'm not going to claim to know the history of how terminology develops. But I don't think I have ever come across someone using "XX00s" to refer solely to the first 10 years of that time period.
The general rule of thumb for reading numbers is to treat every trailing 0 as a marker of an insignificant figure, so a number like "1,000,000" is presumed to have 1 significant figure and not 6. By this rule, the most natural interpretation of 1900s is that it encompasses 1900-1999.
A word or phrase doesn't really have a single established meaning if enough people use it to mean something else. Unless we're talking about "literally", in which case the damn kids had better get off my lawn.
"But that has an established meaning, namely 1900-1909"
Not to anyone I have ever known. I have never before this post today heard anyone say that "the nineteen hundreds" means 1900-1909. It always refers to 1900-1999.
I've only ever heard of 1900-1909 referred to as "the aughts" ( https://en.wikipedia.org/wiki/Aughts ) - which, admittedly, always sounded weird to me, but I wasn't alive then.
I now realize that my motivations are same as literate programming. My focus is to get features integrated into codebase. A developer should only do incremental programming, which will insert code into centrally hosted codebase.
I don't know, isn't this kind of demonstrating a chain saw by chopping up a carrot, seems like it would be somewhat easier for the presenter since they don't need to get an actual log, but at the expense of really misleading the audience.
I’d say it’s more like demonstrating how a chainsaw is useful for felling a tree, by using a log as a stand-in so you don’t have to deal with all the other complexities of felling an actual tree.
Yeah maybe you're right, I just remember all those hello world examples with advanced design patterns and how that gets people all excited to overengineer and overcomplicate everything.
Edit: I'm a bit tired of all these "this is not something that you would actually ever do" caveats, well, don't show it then?
I think a key difference between what you’re describing and Knuth’s program is that those design patterns don’t actually serve a purpose, they don’t solve a problem and just add incidental complexity. Knuth’s trie is an actual solution to the word frequency problem that doesn’t add much incidental complexity — it just tackles the fundamental complexity from first principles, so all of that complexity is staring you in the face. Once you have well-motivated complexity to make sense of, you also have a well-motivated use for LP.
"Edit: I'm a bit tired of all these "this is not something that you would actually ever do" caveats, well, don't show it then?"
Because solving real world problems in a solid way is often too complicated for a presentation, but to show something special you sometimes have no other choice to come up with non real solution that show the principle. But I agree that you can do this in a bad or good way.
Yeah or is it like the infomercials where people show you these awesome gadgets that solve problems that you actually don't have, just to sell you a bunch of crap so that they can make money.
Yes. Literate programming is an incredibly useful tool, if you do happen to have the problem it solves, that is textual communicating with people with a very large difference in knowledge from yours.
But almost nobody has to solve this on practice. The ones that do have recreated the idea again and again (today's most common iteration are Jupyter notebooks), because it's a great idea. But they are always a waste of time for most people.
> Yeah or is it like the infomercials where people show you these awesome gadgets that solve problems that you actually don't have, just to sell you a bunch of crap so that they can make money.
Except that they do solve problems people have, just not problems you have. They are meant for, or at least often employed by, the disabled community.
McIlroy’s solution was to just use few programs Donald's Knuth's of the world previously wrote to hack together suboptimal solution to his current problem.
Ultimately his approach won and today >90% of programming is just stitching together the code someone else wrote so it sorta works for your problem.
Much maligned here nodejs ecosystem is implementation of his approach to web development.
I think this is overly negative. McLlroy solution, albeit maybe cheap / suboptimal, also shows a bit of algebraic, composable qualities. You have a simple model, and pipes to connect partial solutions. Iterating through different parameters allows to quickly adapt / converge to different solutions. Focus on reuse too.
Meanwhile Knuth's compiler techniques volume of TAOCP will be published when he is 145 years old?
We'd never get anything done if we programmed like Knuth. You can do good literate programming but you have to be living in a truly slow world to do it like Knuth does.
I don’t even understand what we’re comparing here. Is it lines of code? In that case, you must include all of the code from tr, sort, and any other shell commands used to perform the task at hand. By that standard, Knuth still wins by a long shot. Were this an actual coding contest (if such things exist anymore), one does not simply argue that instead of coding the solution in the given language, I’m going to just use five other people’s solutions and claim my trophy. Had the argument been who could most efficiently reuse all of the resources of an operating system to produce the laziest solution that will likely produce the highest number of obscure edge cases in the future, create unexpected dependencies, and likely scale the worst, then perhaps the shell script wins. But I think Knuth was trying to demonstrate quite the opposite - good coding praxis that can be maintainable, debuggable, and made to scale. I guess what I’m saying is that it’s difficult to see any comparison here, whatsoever, since the purposes were so markedly different. The shell script is not a solution any professional would ship in a product, and would only appeal to lazy one off tasks. Who would have been daft enough firstly, to not read Knuth’s paper, but secondly to think there is anything worth comparing in the first place? The script might be the quickest solution. Knuth’s code is the proper solution.
Fairly easily. Personally by this point I'd have long resorted to Perl, so the the usage of 'tr' and 'sed' in other than the most trivial ways aren't something that I'm very familiar with. But here's how I parse it without looking at man:
1. We're substituting characters and we're looking for is all word characters, and what we replace with is a newline. That doesn't seem terribly useful at a first glance, so either -c or -s is probably a negation. So this probably splits by words, producing newline separated words.
2. Change A-Z into a-z, that's obviously uppercase to lowercase. Confirms that text is what we're working with.
3. Sort alphabetically.
4. Remove duplicates and count.
5. Sort numerically.
6. Not entirely sure what 'sed ${N}q` does.
So yeah, I can get most of the way there without looking at the manual at all, making the reasonable guess that it results in a list of words sorted by frequency. My main point of confusion would be with sed, because it's hard to search manuals for the meaning of 'q' and I'd have used 'head' instead. Looking up what's the deal with 'tr' is about 5 seconds.
I'm pretty sure sed ${N}q is supposed to chose the N (or k) top choices, where N is given as an argument/variable.
(Going off of the fact that head is essentially sed 11q, where it quits on the 11th line.)
But yeah, head -n (--lines) would do the job here perfectly while being more readable, no clue why it wasn't used.
It occurs to me that part of this debate could be expressed in more modern terms as Declarative vs Imperitive programming.
In firstclass languages a complex problem can be solved by chaining together functions and can be written in a single statement (this depends on the implmentation of functions and types that are returned). Somtime 2 or three statements.
Versus using core language statements and packages to implement conditional logic, control structures, and operations. Relying less on packages that extend the launguage. Having full control over the implementation.
Personally I prefer declarative and wrapping it with verbose inline documentation.
One downside to this is maintaining the build environment. Packages are versioned and fucntions change overtime (deprecated in favor of new implmentations that replace the old function). Somtimes Declaritive implementations must be refactored to support newer version of packages.
Impertive implementations tend to be more durable and have fewer dependencies.
That’s an insightful take, and completely un-obvious, at least to me.
The idea of a company having its engineers livestream all their production work kind of terrifies me, but might also be kind of an interesting way to do business.
I wonder though if being able to write code and explain it at the same time is a skill like singing and playing guitar at the same time. I’ve never live-streamed though so couldn’t say. Any tips for trying it out, good reasons to do it or reasons not to?
We don’t do that, but we did a lot of pair programming when I started and my productivity was through the roof.
The equivalent in commercial settings should be pair programming. I was on the headset with another programmer who would realize some concepts only as he put them in words and explained them to me.
But the same thing was the case in academic settings. I could tackle some problems only in dialogue (again over headsets) and only in mutual we would even be able to come up with many solutions. I found that it only works in a pair settings and it breaks down in a setting of three.
I think once we engage the speaking part of our brain we unlock something that makes us find solutions instead of take ambiguous shortcuts.
This is why this seems like a strategy that is much more suited to an academic setting. If you're studying algorithm proofs, it sounds like you're often reading something like LP.
Advocating for LP in commercial product development sounds like dreaming. No way would someone who has to meet deadlines write these long, qualitative descriptions of what the code was doing. Martin's suggestion of building the 'narrative' into the code itself sounds much better in those cases.
The issue was simply a bad one, because we do not use computers as sport cars in a race, at least we shouldn't, we use as daily driver. As a daily driver who constantly change and adapt to changed needs and desire.
So Unix classic McIlroy's is good for quick run, daily driver who can't really evolve much, at least not at a little price. Knuth on it's side equally felled in the same trap on the opposite side of the spectrum.
The real outcome is that Unix model is wrong, and it's a well-known things behind the Unix Hater's Handbook simply when unix choose to through it's principles in a bin making GUIs from the first CDE and beyond where no small programs nor composability via efficient IPCs is there. Sole IPCs available cut/copy/paste. The right choice was done before: with Smalltalk systems at Xerox, with Lisp-based systems after them: which means a moderately literate and discoverable environment where anything can be easy integrate in code so where shell-scripting is actually the same of system programming and the literate part, based on literate code, is just literate composition not much different then the classic human notes compositions from Mundaneum to ZettelKasten. That's is. Unfortunately since NOBODY want to admit mistakes especially if they was made in the past and imply large areas of development nearly no one want to talk about those terms...
I don't know about you but GUI is at most 1% among all the programs I write (if we are talking in terms of applications, not lines of code). Most are tiny one-purpose CLI programs instead e.g., read OTP secret as an input and print corresponding 2FA code which can be used as:
The issue came from banks, for instance, who demand mandatory crapplications just to allow web logins from desktops with the excuse of "safety". I do not know if banks from your country have done that, it's a moderately recent idea in southern EU since around 4-5 years. Some arrive to the point of stating that's mandatory by law, witch is not only false but also the contrary since EU PSD 2 law they cite mandate that no single device can authenticate and operate, while most of such crapps do.
I know some have analyzed their (unsafe) protocols and now use desktop otp software, but that's not a thing should ever be needed in the first place: banks who mandate the usage of unsafe platforms (and the rise of Android banking malware is a nice proof) must be forbidden by law with sanctions severe enough no one ever try to push such systems just to grab more data from their customers.
A thing we already see for EV recharge and other activities.
? The point is: if we accept keeping evolving in this directions we will be not Citizens anymore but just "smartphones holders" pastured by smartphones real owners witch happen to be a small set of private companies.
The point is that in a near future our identity will be only provable by them, NOT by States [1] so a private company can say who you are or not, not your government. We will been able to pay things only if the new substantial de-fact dictator, the GAFAM, decide that we can, since all payments will pass through their platform [2], we will be weighted from the birth by bid data analysis on our DNA [3] having careers pre-defined by social scoring systems (witch means by bad choices and corruption, like in China and UK) well trapped in such dystopia.
I understand that casual citizens can't understand but on HN it should be a hot topic if we still have hope.
So the point is mandate a total ban of such practice, imposing and open IT for the profit of the whole society not of some big&powerful against all the rest. Witch means coming back to classic IT vision, because actual IT is born back then and distorted just to evolve in such limited, limiting and dangerous manners...
"He has fashioned a sort of industrial-strength Faberge egg—intricate, wonderfully worked, refined beyond all ordinary desires, a museum piece from the start."
That's what computer science in the 1970s and the 1980s was all about. Clever algorithms. Especially at MIT. Read the classic HAKMEM from 1972.[1]
It wasn't that at all. That's barking up the wrong tree. After all we are talking about the guy who said premature optimization is the root of all evil.
Sometimes I do "semi-literate" programming where I don't even bother with the commentary. I just use a tangler so I can write the code in the order I want to see it. I really think writing in "human-order" and tangling into "compiler-order" is the bigger benefit to the methodology. It stops you from (for example) writing a function just to break up the logic into manageable parts.
I do this when deconstructing (I call it "vivisecting") large under-documented programs. Slurp it into org-mode as one block per file, extract components and reorder. Possibly (usually in my case, but not always) adding documentation and links to other parts of the program. The program is always still in a running state (I tangle and do a git diff to see if anything, excluding the org files, has changed, then build and run if I want the extra confidence). Whether I add documentation or not, I'm able to provide better information locality, especially where information (for language reasons) is spread across files, but also makes logical sense (but not compiler sense) adjacent to each other.
Yeah the locality is another great point. It's really cool to have a file per major feature, and have interfaces, implementations, and unit tests all in one file co-located. And I do add documentation even in the "semi-literate" case; I just mean I don't worry about the weaver producing a proper-sounding article (since, frankly, I don't expect anyone to ever read it, anyway).
LP is basically the idea behind JN, yes. Though it's a bit limited in that sense; for example literate programming often allows arbitrary ordering of code snippets and extracting parts into separate code blocks (like `<<foo>>` in the linked post).
But Jupyter Notebooks does it more like a REPL where every code block can be executed separately, which is nice too. Afaik this is also possible in Emacs' org mode.
That’s actually a really good comparison. Jupiter adds interactivity that WEB didn’t do, but remove the ability to easily compile and distribute the finished product.
Another extremely important successor to Knuth’s ideas is the built-in documentation comment formats that most programming languages have. They tend to eschew linear narrative in favour of navigable hypertext, which is honestly a good idea for many purposes but sadly relegates the “overall vision” stuff to supplementary documentation.
This seems like as good a thread as any to point out that Inform, one of the largest literate programs to date, was recently published on GitHub.
https://github.com/ganelson/inform
I always disliked these comparisons to "shell" scripting that invariably end up comparing a collection of C (or whatever) tools and claiming to have solved the problem in steel script.
It's nonsense - the various shell scripting languages are more than capable of implementing those various tasks without simply shelling out to C, and so should be required to. Otherwise a C programmer has access to system() and start() and those support pipes even.
Yeah the comparison between the shell script and the Pascal/LP version is a little bit apples/oranges. Maybe a nice counter to that would have been to make an LP version of the script itself. Here's a quickly hacked together mashup of the Knuth/McIlroy solutions:
Given some text input via stdin, we want to find the word that appears most often. The main body of the shell script is as follows - each section uses plain shell utilities and has been developed and tested with (blah blah, maybe mention the version of the utils we used in case GNU versions work but BSD don't or something)
The first job is to isolate "words", defined here as groups of lower case latin alphabet characters (sorry to our international friends out there!) using `tr`. Importantly anything hyphenated will be treated as a separate words ("short-term" will be "short" and "term", for example), so modify the pattern if this isn't what you need.
<<makeLines>> = tr -cs A-Za-z '\n'
Next we'll make everything in the input lower-case:
<<convertToLowerCase>> = tr A-Z a-z
The next step is to sort the lines so exact words are next to each other, then pipe that into `uniq -c` to get counts for each adjacent line. This is a fairly common pattern so I've bunched these guys together.
<<sortAlphabeticallyAndCount>> = sort | uniq -c
Since we're interested in the most frequent we're sorting descending (-r aka --reverse. IMPORTANT: not -R aka --random-sort) and numerically (-n)
<<sortNumerically>> = sort -rn
And finally we can take the first line and print it. NOTE: I didn't use `head -n 1` here because blah stupid reason whatever
<<takeFirst>> = sed ${1}q
(fin)
This is the first time I'd ever written anything approaching LP (I just copied the style in the article) so I just quickly dashed it out with placeholder comments, though I'd maybe include a worked example of the program in action too showing the output at each step. Now obviously it's longer than the little shell snippet that was posted, but even though it is a relatively tiny problem to apply LP to, you can see that there is still some value to it - I've been able to make it clear that only the latin alphabet is considered, I've highlighted a potential oopsie in case someone inexperienced in tries to re-use it (-r/-R), I was able to state that there's an alternative approach to the final step and give a reason why I chose my way.
In shell (/bin/sh) ${1} gives you the first argument, which for simplicity in this context is trusted to be an integer, e.g., if the shell script name is most_freq_words, "most_freq_words 5" would put the five most frequent words, one per line, on stdout. If you want to use head instead of sed, you'd say "head ${1}"
I haven't gone back and read the original after all these years to check the specification, but it's perhaps worth noting that at least the McIlroy solution is only valid in the C locale. At least these days you can use character classes. In my experience locales regularly bite people -- even en_GB ones.
The literate programming is very under rated in Jupyter Notebook. It is mainly used for experiments. I hope that in the future there will be more applications in notebook for example in automation. Can you imagine notebooks replacing services like zapier?
Plain Jupyter Notebooks though offer only a fraction of what makes literate programming. They would need features like cell references, tangling and multi-lang in one notebook, to get close to other LP tools.
LP permits arbitrary reordering of the code and a text macro-ish ability to plug in code to any other block of code (when tangling). Most of the markdown-centric tools for "literate programming" I've seen don't permit that, instead they just allow a cleaner interleaving of document and code but the code is still ordered exactly as if written in a conventional style. In WEB/CWEB-derived literate programming you could do something like this (very quick sketch):
<<game-loop>> ==
while (!dead) {
<<get-input>>
<<update-world>>
<<display-world>>
}
And way down at the end of the program you can do this:
<<main.c>> ==
<<includes>>
<<globals>> // if appropriate
int main() {
<<initialize-game>>
<<game-loop>>
return 0;
}
Throw that in an appendix or something because it's such blindingly obvious code (for C) that you don't need to dwell on it. It's not critical to the discussion contained in the rest of the text unless you're also providing a tutorial on C programming.
And, you can (like I said, text macro-ish) reuse blocks of code in multiple places. Maybe you have some common header files, you could write this:
In order to have access to OpenGL capabilities, many of the .c files
will require this header block:
<<OpenGL-includes>> ==
#include<GL.h>
...
And now when you want to include them, you just reference this. Of course, in C you could just create a common.h file or something and tuck the includes into that, but not every language has text inclusion of that same sort. If, for instance, you were writing Java or C# or something you could use the above modified to call whatever appropriate package imports were needed. Then update it in one place and all of them get updated.
Yes, they do. They are not literate programming the way Knuth's CWEB does it (weaving mostly disjoint things together), but they are a good tool for LP.
I've been planning (for 2+ years now so it probably won't happen) writing a large blog post about this matter, which would be called “Tries, Packed Tries, and the Bentley–Knuth–McIlroy story”:
• Part 1 would introduce the trie data structure both abstractly (the tree structure) and concretely (how exactly to represent the children of a node), with the trade-offs: as a linked list (space-efficient, slow lookup), as an array (fast lookup, takes space), or as some more nontrivial tree structure itself (“yo dawg…”). Then we'd discuss the really cool idea of “packing” the array, as nicely described in Frank Liang's thesis https://tug.org/docs/liang/ (also mentioned in TAOCP Exercise 6.3:4 and answer, which incidentally refers to the CACM Bentley–Knuth–McIlroy article that we're talking about). We'd also illustrate how hyphenation is done in the TeX program using packed tries (maybe this can be a separate post).
• Part 2 would go into the Bentley–Knuth-McIlroy story:
• Part 2a ("Before"): Bentley's thesis/book on writing efficient programs, and the Programming Pearls column. Knuth writing TeX first for himself in SAIL in 1977–78. The instant interest and ports/rewrites it led to. Knuth responding by rewriting TeX into its current form in 1980–82, and how the goals of portable software (thus Pascal, and its limitations! see BWK rant) and of eventually publishing it as a book led him to the idea of literate programming, which he still considers the most important outcome of his years into the TeX project. Meanwhile, at Bell Labs, McIlroy's invention of Unix pipes, and the instant excitement of "pipe day". (“It was absorbed instantly into one's outlook on programming. And by the end of the week secretaries were piping the output of NROFF into the printer”) The Unix philosophy, and how it took a while to spread. How these three threads came together in 1986, when Bentley read Knuth's TeX, wrote about LP in his Pearls column, and published one program of Knuth's (the random-numbers one) and asked him to write another (the frequent words one).
• Part 2b (the program): How Knuth ingeniously combined the idea of packed tries with that of hashing with linear probing, to create the data structure especially for this problem (maybe we can call it a hash-packed trie?). Another look at his very nice idea/program, presented differently (maybe some illustrations of how the data structure works), and some design choices he made.
• Part 2c (the review and later): How Bentley got McIlroy to review it, a close reading of the review: its actual content and points about LP and Knuth's style, and finally the (first sentence and) last part where McIlroy used the review to advertise his own Unix philosophy and the short shell pipeline version. The further reactions to this, including Bentley's remarks in the same column, and later articles and reactions like the "prefabs" comment (https://news.ycombinator.com/item?id=22406070). The short-lived LP column in CACM that it spawned (https://shreevatsa.net/post/programming-pearls/) and how it fizzled out, how it turns out everyone wants to do LP in their own system. How the story got bastardized over time (the misleading "More shell less egg" blog post for example, and some other examples of people misunderstanding the history entirely).
• Part 3 would compare the two approaches (even though they are not meant to be compared!), mention how at https://codegolf.stackexchange.com/questions/188133/ I simply translated Knuth's program into C++ and beat the then-fastest Rust solution (since beaten again by translation from C++ back into Rust: still based on the trie idea though!), some words about cache misses and 32-bit “pointers” in a 64-bit world (and Knuth's rant about it).
Something like that: it's probably too long for me to ever get around to writing it (or for anyone to be interested in reading), though…