The Word Count Problem
blog.peterdonis.com
blog.peterdonis.com
If you had asked Knuth to solve this problem using any means in the whole world and do it within 10 minutes, I don't think he would have any trouble doing it.
And honestly, if the lesson is to teach us some really basic lesson of code reuse, not reinventing the wheel, or some such like that, I think this was a pretty convoluted way to deliver sort of a common sense lesson.
1) This was in 1986. That's about 4 lifetimes ago in computer programming.
2) This was an article specifically to demonstrate literate programming. It wasn't supposed to be "the most efficient way" possible. It's approximately the same argument as "why should I write a program to sort data in an interview; I'm not going to get paid to write sorting functions".
2) I have made the same argument, in interviews, many times. It's a good argument to make.
In fact, Knuth considers reusable code to be a "menace."
Probably Knuth misunderstood the concept
In my experience writing reusable code, unless you're writing a library, is usually a waste of time. Must code, even when written with intent to be reusable -- isn't. Maintainability and readability almost always trump reusability. Refactoring fast the point where reuse is needed typically is the better approach.
McIlroys approach is the less common approach of library/framework writers while Knuth is the approach of app devs.
In the sense you're using "library" here, the Unix utilities are libraries--more precisely, they are library functions; the whole set of utilities is the library. So McIlroy was a library/framework writer.
> Most code, even when written with intent to be reusable -- isn't.
I more or less agree with this; but fortunately, you don't have to look at "most" code to find code that is reusable. As witness, once again, the Unix utilities. Or, for that matter, the Python builtins and standard library that I used to build the Python versions of the "word count" program.
Moreover, even if you're in Knuth's position and don't have a good base of reusable code to draw on already, it still makes a big difference how you proceed from there. Do all app devs write big monolithic apps? I believe pg once wrote an essay about bottom-up vs. top-down programming, leaning heavily towards the former.
The essay: http://www.paulgraham.com/progbot.html ?
I think a lot of everyday reuse (by factoring commonly used code) happens at a level of programming which neither fits application nor library development but writing small tools to automate ad-hoc tasks (e.g. by scientists, admins, etc.) Environments like Python, the shell, or Lisps seem to be more suited to this kind of development than, say, Java.
In the case of the example, I could easily imagine that the "isolate words in input text"-part will turn out to show up again, and then one would factor it out to a function. When the first text containing unicode soft hyphen characters is encountered, only a single shared function has to be updated, and all little scripts using it will benefit!
A function extracting the text from xml-documents, skipping a configurable set of element types, might find similar reuse, etc.
Just an aside: I'm not familiar with Python, what I found disappointing was the mix of chained object method invocations and "outer" function calls - since replacing the built-in string class seems to be frowned upon, I was wondering how the example script would look like using pipe[1] :-)
One question about the Python code: is the first call to sorted needed, and if yes, why?
Yes, that's the one I was thinking of. Thanks for finding the link!
> the mix of chained object method invocations and "outer" function calls
Actually, you're right, I could have factored out the part that builds the dict of words vs. occurrences into its own function, so that the entire pipeline would be a single chain of calls. Now that you've put the thought into my head, I may go back and do that. :-)
> I was wondering how the example script would look like using pipe[1] :-)
That would certainly make the Python look more like the shell script. :-)
One of the constraints I imposed on myself when writing the Python version was to only use what comes with it--built in functions/syntax and the standard library, with no third-party packages, similar to how McIlroy only used "built-in" Unix commands that came with every Unix system.
> One question about the Python code: is the first call to sorted needed
You're right, it isn't. I've pushed an update to the github repo fixing this (in both versions).
Just did it. :-) Factored out a "uniq" function in both versions, so the "pipeline" function is now a single chain of method invocations (with the slicing at the end). Which means it could actually be put in the "if __name__ == '__main__'" stanza, but that seems less readable to me.
I somewhat agree when people say "code reuse has failed". When people set out to write "reusable code", it ends up not being reusable. Usually because they think of reuse as writing a bunch of classes that they can "import".
But writing tools is another way to reuse software. For example, in Unix, you reuse ssh for git and for scp. With the web, you can reuse a huge amount of work in Varnish and nginx by chaining components.
So library reuse is not all it's cracked up to be, but that's not what McIlroy is doing. His solution to the word count problem is fantastically and obviously better. It's real reuse.
To be clear, I think there's a distinction between writing a library for well known use cases. I wouldn't suggest stdio is a waste. But it's almost always a waste of time to emerge from a client project with a bunch of libraries for functionality that will likely never be used again.
And among good developers I think this is one of the biggest problems. I've encountered many times good programmers building elaborate frameworks that take as long as the main project itself, who then present the utility of this framework, which we never use again. They didn't understand the problem space well enough to know when reusability made sense and across what pivots.
So library reuse is not all it's cracked up to be, but that's not what McIlroy is doing. His solution to the word count problem is fantastically and obviously better. It's real reuse.
Knuth also reused. He reused a compiler. He reused input output capabilities. He reused subroutine abstraction capability.
IMO it's less what they used and more what they produced (as all developers reuse). Knuth didn't produce a bunch of reusable tools and I think that is justified and the right approach most of the time.
I went back and reread the paper just now and McIlroy even alludes to this:
"The utilities employed in this trivial solution are Unix staples. They grew up over the years as people noticed useful steps that tended to recur in real problems. Every one was written first for a particular need, but untangled from the specific application.
With time they accreted a few optional parameters to handle variant, but closely related, tasks. Sort, for example, did not at first admit reverse or numeric ordering, but these options were eventually identified as worth adding."
What he describes is the right approach -- and what Knuth wrote is the first step here. I'm fairly certain if Knuth was a systems developer and this came up over and over again you'd see refinement and tools/libraries that made certain aspects of this more reusable. But that's neither his domain nor the specific ask for this client.
McIlroy's rant here seems pretentious in light of this. A much better rant would be to show how Unix tools could in six lines replace LaTex for typesetting (without using anything provided by LaTex).
But it isn't contradicting the point of what McIlroy does -- it actually supports it. Unix tools are more reusable than libraries full of code.
I can't tell what the second part of your post is saying. It doesn't matter if Knuth "would have" done something; McIlroy already did it. The problem is solved with 6 lines. End of story. No pontificating. That's what Unix lets you do -- get on with your day :)
Knut's program's most glaring flaw isn't its length, but its monolithic architecture.
That I can agree with. But there's nothing stopping you from breaking up your program into small utilities that have a simple interface. Those utilities don't need to be generic or widely applicable. But separating them from the main program can help.
Just to give an example, I once had trouble writing a function that transformed a particular tree data structure. I ended up breaking it in two: the walking part, that took the transformation part as an argument. And of course the transformation part. Note that the walking part was fairly generic, and could have been use for other purposes (heck, one of its arguments where a function!). But I didn't write it for that. I wrote it to reduce the amount of brainpower I would need to finish my program, through dumb separation of concerns.
I liked Hughes paper. Funnily enough, the lack of laziness in Ocaml quite hindered me when I wrote and used my Parsec clone (again in USSM, but in the current version).
Additionally, I can't help but think that this essay (and others in this style) and subsequent reflections would make for a perfect seminar targeted towards final year CS students, as it merges perfectly academic reflection and real world engineering considerations, which is what many CS programs across the world sorely need.
I wrote in a literate programming style for years, to generate LaTeX documents and a world-scale build system for a multinational. But I'm past that, since it's intricate and unmaintainable by others. Instead, I'd rather generate documents in UTF-8 (an ASCII-compatible and increasingly universal format), and sets of small tools which call each other and expose their data in files for new tools to use. With this approach I can evolve the toolset in small, state-preserving steps, to minimize how much I have to code to meet current needs and implement new approaches.
If the problem warrants it, you can revisit it later to do something more ornate. In the meantime, you've got what you need to move on.
... can someone please point out what the problem is? I don't see it :-|
If unicode tr didn't exist, then by fixing tr you fix this problem for everybody, not just yourself. You're only in trouble if the source for `tr` isn't available. But the source for `tr` has always been available, even for proprietary unices.
As I understand it, that was the original spec, which both Knuth and McIlroy wrote to. I agree that it is limited as you say.
> The shell solution, built upon standard tools, can not be extended to work in an international context but a custom solution in Python (or even Pascal) quite concievably could.
As bryanlarsen pointed out, the shell solution can easily be extended by using an internationalized version of tr. The Python equivalent would be to use the built-in Unicode support. (If Pascal had that, you could do the same in Pascal.)
However, it's worth noting that by specifying the problem that way you still have the issue of how the input stream (which is going to be bytes) is encoded. Essentially, the original spec declared by fiat that the encoding was ASCII.
Also, btw, you can express non-English languages in ASCII (though certainly not as wide a variety as in Unicode); the program as written does assume that words are composed only of the 26 standard ASCII letters, but it could easily be extended to include the ASCII special characters. Another exercise for the reader. :-) Though if you're going to do this kind of extension, it might be better just to go the whole way and handle Unicode.
My new opinion is that great programmers will go beyond the spec and make their software handle Unicode in cases like this. It's the right thing to do. If the spec didn't require units tests does that mean you don't write unit tests? No, you do it anyway because it's the right way to do things. BTW I'm still working on being a great programmer myself.
> As bryanlarsen pointed out, the shell solution can easily be extended by using an internationalized version of tr.
You should try that and then blog about it. :) I've spent lots of time battling issues with ascii-centric libraries. My conclusion is that it is not easy at all which is not strange because tools like tr and sed were written decades before unicode support became a must have. I can't say that it is impossible to write a shell script to count words in a text written in Arabic script, but it doesn't seem easy.
Where did I assert that?
> I can't say that it is impossible to write a shell script to count words in a text written in Arabic script, but it doesn't seem easy.
Is there a definition of what counts as a "letter" in Arabic script? That is, which Unicode code points correspond to letters? And does Arabic share the convention that a "word" is a sequence of letters delimited by non-letters?
If the answers to those questions are "yes", then the extension of the algorithm already presented to handle Arabic is straightforward; it's just a matter of substituting the Arabic definition of "letters" for the ASCII definition. (With, as I said in my previous comment, the additional issue of determining the encoding of the input and output.)
If some of the answers to the above questions are "no", then you have an issue with the problem specification, not with the algorithm you're going to use to solve it.
(Btw, the Python version did not have the bug, since the split method of Python strings already ignores initial whitespace.)
At any rate, my point, though it wasn't really clear, was that pascal makes code reuse hard to such an extent that I don't think it's actually possible to have a general-purpose sort routine in the library that would be actually useful. Certainly nothing like qsort, anyway. It just can't be expressed.
(I'm sure modern versions of Pascal have this problem licked.)
The shell script is the same for disk and cpu, however, it is O(1) of RAM, and therefor can operate on input of size limited to disk, not RAM
The easily fixable issue is that the shell pipeline buffers reads, whereas my Python version just uses sys.stdin.read() for simplicity. I could have buffered the reads by using Python's generators/iterators instead. However, that alone isn't enough to get O(1) RAM usage.
The not so easily fixable issue is that the Unix sort command uses temporary files in order to not have to have all of its data in memory at once. See, for example, here:
http://vkundeti.blogspot.com/2008/03/tech-algorithmic-detail...
Python's sorted builtin doesn't work like this; it can take a generator as input, but it returns a list. This is one respect in which Python's built-in functionality lacks a feature that the Unix utilities have. I don't know if anyone has tried to re-implement the Python sorted function to use temporary files and return a generator to reduce memory usage.
[Edit: the Python version would also have to re-implement the uniq function to take a generator as input and return a generator, which would, I believe, also require temporary files.]
A superior solution in every way
If you were going to do this in Python (or another similar language), you need to write a sort function that operates on a file, not a Python collection, as the collection is always bound by RAM, which would at best be re-implementing the sort command. Once you can sort a file, everything else is trivial, as counts can be done line by line, or more siply, via uniq -c.
Of course, if you only care about things that fit in memory, you can do it in Python, but it is still far easier to use command line for these type of problems.
I agree; I was not trying to claim that my Python solution should be used in preference to the shell pipeline solution in any kind of "production" environment. As I noted in another comment, Knuth's Pascal solution appears to be open to the same criticism.
(BTW, who needs RSS anymore? Atom is so much cleaner designed and thus easiert to handle with. I'm even planing use Atom as main format and generating my website from that ...)
I generate everything from Markdown source using PyBlosxom's static rendering (which has some issues that may eventually drive me to switch to something else or roll my own). It auto-generates RSS and Atom feeds, so it costs me nothing to have both just in case someone prefers RSS or can't use Atom for some reason.
http://www.leancrew.com/all-this/2011/12/more-shell-less-egg...