The Word Count Problem

http://blog.peterdonis.com/opinions/still-another-nerd-interlude.html

by pdonis • 14 years ago

69 59 14 years ago

blog.peterdonis.com

pdonis14• 14 years ago

Inspired by reading this:

http://www.leancrew.com/all-this/2011/12/more-shell-less-egg...

GuiA• 14 years ago

This is fascinating, and should be a source of reflection for anyone writing code for a living or being involved with programming on any serious level.

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.

kenjackson2• 14 years ago

Against all conventional wisdom I actually think McIlroy was wrong.

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.

pdonis14• 14 years ago

> In my experience writing reusable code, unless you're writing a library, is usually a waste of time.

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.

kaiwetzel• 14 years ago

(largely agreement here, can't say much about Knuth, though)

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?

[1] http://pypi.python.org/pypi/pipe

chubot2• 14 years ago

I don't agree -- you're papering over an enormous distinction. Unix tools and the shell are the biggest success story in software reuse that we have. (I would argue that it is why nearly everything we use today is Unix -- servers, iOS and MacOS, Android, etc.)

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.

kenjackson2• 14 years ago

I don't agree -- you're papering over an enormous distinction. Unix tools and the shell are the biggest success story in software reuse that we have.

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).

squires• 14 years ago

I won't dispute the utility and versatility of UNIX tools, but your comment that "nearly everything we use today is Unix" is wildly off the mark. According to the following article, it's estimated that Windows is installed on 36% of servers and 92% of desktop systems: http://en.wikipedia.org/wiki/Usage_share_of_operating_system...

ken• 14 years ago

OK, forget reusability. Is a 10-page program written in WEB more maintainable and readable than a 6-line shell script?

loup-vaillant3• 14 years ago

Uh uh. We could assume the Pascal program was written in an environment which lacked UNIX utilities. The 6-line shell script is only better if you can run it at all.

Knut's program's most glaring flaw isn't its length, but its monolithic architecture.

loup-vaillant3• 14 years ago

Going out of your way to write reusable code, unless you're writing a library, is usually a waste of time.

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.

eru• 14 years ago

Have you tried functional programming, yet? John Hughes argues in "Why functional programming matters" (http://www.cse.chalmers.se/~rjmh/Papers/whyfp.html) that enabling exactly this separation and subsequent gluing together is exactly what makes FP worth looking at.

dinkumthinkum• 14 years ago

I want to be charitable but I find the criticism here of Knuth of be quite childish. Was the point to solve the problem with as little work as possible? If that's the case, there's probably some plugin for your favorite text editor that already does this. So what? What was the point exactly? You could just have easily built a library function that does all of this and then write a Pascal program that calls the library in one line of code, state the library is not part of your solution, and say the solution is better than the one with UNIX utilities. So what? Is the point to illustrate that Knuth is unaware of elementary concepts such as code reuse, come on that is just sort of ridiculous.

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.

powera• 14 years ago

Some other points from the linked-to article that back up that the criticism here is a bit ridiculous:

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".

zacharyvoase2• 14 years ago

1) I'd like to see you say the same about differential calculus, which actually was several lifetimes ago.

2) I have made the same argument, in interviews, many times. It's a good argument to make.

pmiller2• 14 years ago

Is the point to illustrate that Knuth is unaware of elementary concepts such as code reuse....

In fact, Knuth considers reusable code to be a "menace."

http://www.informit.com/articles/article.aspx?p=1193856

neopba2• 14 years ago

> To me, "re-editable code" is much, much better than an untouchable black box or toolkit. (Knuth)

Probably Knuth misunderstood the concept

geon• 14 years ago

I would argue that more code is a better solution in this case. The purpose was not to write short, clear code, but to illustrate a certain programming style. How am I supposed to "get" the style in 5 lines? A short solution would have been a failure.

ajanuary• 14 years ago

The same code in composable and reusable units would have demonstrated just as much.

yk• 14 years ago

The point, imho, is to illustrate literate programming, a technique designed to write easily understandable code. And the rebuttal is, that with high level tools and a good documentation you can build as easily understandable code in about 20 lines including comments. (To be fair, one would need to understand all the tools used for comparison to Knuths program).

zacharyvoase2• 14 years ago

I think I found a copy of the original Knuth/McIlroy paper itself: http://people.mokk.bme.hu/~kornai/AzkellHaskell/bentley_1986...

andreasvc2• 14 years ago

If the problem is simple enough to be solved by a shell script, then obviously literate programming is going to be overkill. Algorithmic problems such as data-structures are well suited for literate programming.

catenate2• 14 years ago

Having reusable tools in the first place, to make it a problem simple enough to solve with a shell script, is the accomplishment that advances the state of our art. It reduces a complex data structure to passing data through a pipe, which makes the algorithm more usable for more people.

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.

andreasvc2• 14 years ago

The re-usable tools in this example are only applicable because the problem is simplistic. If you were required to extend the solution to cover say language specific definitions of word boundaries, the literate style would be a definite win. The shell solution looks elegant but really it's just a quick and dirty hack as far as generality is concerned.

bjourne2• 14 years ago

I haven't checked out the original paper, but the solution presented on the blog is a non-solution. It only works for ascii characters and words composed out of ascii. When you reuse someone elses code, you always get stuck with someone elses assumptions. In this case, that English is the only language and that the regular expression [A-Za-z] encompasses all possible letters in the world. 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.

bryanlarsen• 14 years ago

In my opinion, you've got that backwards. To fix the shell script, just make sure you're using an [i18n version of tr](http://heirloom.sourceforge.net/), and then use [:alpha:] instead of [A-Za-z].

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.

pdonis14• 14 years ago

> I haven't checked out the original paper, but the solution presented on the blog is a non-solution. It only works for ascii characters and words composed out of ascii.

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.

nwhitehead• 14 years ago

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

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.

bjourne2• 14 years ago

But your assertion was that this was an easy problem solved with just a few lines of shell code. That assertion is only true in an extremely limited context where the only language possible is English and the only character encoding is ascii. That's where the Unix tools shines because they are great at handling problems easily expressable as regular expressions. But it is not a very realistic example, nor a fair comparison.

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

Tichy2• 14 years ago

Doesn't Pascal have libraries for sorting? I find that hard to believe. So there must have been another reason why Knuth chose to implement everything from scratch. Probably to demonstrate programming techniques. You don't learn that much about algorithms by stringing together a couple of shell commands.

to3m2• 14 years ago

Pascal makes code reuse hard. http://www.lysator.liu.se/c/bwk-on-pascal.html puts it better than I could. And when I used Pascal in the early 1990s - and this was Borland Pascal, one of the better ones - it even had strings! - things had not improved massively.

Tichy2• 14 years ago

When did that comparison take place anyway? I don't think anybody is still using Pascal in this day and age?

ralph2• 14 years ago

Both the article's improved pipeline and Doug McIlroy's original have a bug. I've just written about it on +Ade Oshineye's post about the original article. https://plus.google.com/105037104815911535953/posts/KuXczyiw...

pdonis14• 14 years ago

Good catch! I've implemented your suggested fix of adding a sed '/^$/d' at the beginning of McIlroy's pipeline. The github code is updated, along with an updated test file and expected output.

(Btw, the Python version did not have the bug, since the split method of Python strings already ignores initial whitespace.)

ralph2• 14 years ago

Your bug fix is broken; it makes no sense to place it there. I suggest increasing the number of test inputs to first show the problem.

vog2• 14 years ago

I like that article very much, so I wanted to monitor the blog. However, I found neither an Atom feed nor an RSS feed. That's a pretty good way to turn off potential regular readers.

pdonis14• 14 years ago

I do have feeds set up, but I just realized they aren't linked to or autodiscoverable. :redface: I'll fix that ASAP. Thanks for the feedback!

pdonis14• 14 years ago

Fixed--added links on the home page to RSS 2.0 and Atom feeds. Also feed autodiscovery should work now.

Shish2k• 14 years ago

"Program specifically designed to demonstrate literate programming turns out to be a good demonstration of literate programming, not a good demonstration of library creation"

... can someone please point out what the problem is? I don't see it :-|

TazeTSchnitzel• 14 years ago

The problem is that it isn't what they wanted it to be.

websiteguy2• 14 years ago

Maybe I am missing something here, but The python version is: O(N) sequential disk access O(NlogN) cpu O(N) RAM

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

pdonis14• 14 years ago

You're correct, the Python version is O(N) instead of O(1) in RAM usage for two reasons, one easily fixed and one not. Sorry if I'm belaboring the point, but I think it's worth going into a little more detail.

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

pdonis14• 14 years ago

Looking at the original paper that was linked to elsewhere in the comments here, it appears that Knuth's original Pascal program is, like my Python version, O(N) in RAM. It keeps everything in memory and uses no temporary files, as far as I can tell.

websiteguy2• 14 years ago

Unix sort is a merge sort, using fixed RAM uniq -c is line by line sed is line by line

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.

indubitably• 14 years ago

Neither Knuth’s nor McIlroy’s solution handles Unicode, so they both suck.

The Word Count Problem

Related Stories