Text statistics as summaries

Darius Bacon mechanically summarizes the Lord of the Rings by determining the most anomalously frequent words in each chapter. The word lists are surprisingly evocative. It's obvious which chapter this is, for instance:

Gorbag Shelob Lugbúrz Shagrat Ladyship Ya hoi belly

Or this:

Parth Galen Rauros glade cloven boat fate bearer

Even those word lists that don't include important names or events are still recognizable. I would not expect to recognize this, but I do:

quality Númenóreans Damrod mistress squirrel wiser arts Mablung

Word frequency is sensitive to repetitive text, such as the songs Tolkien is so fond of. This can be a problem. This chapter, for instance, is less obvious:

fiddle inn cow local Mugwort diddle tray comer

Or this one, which is dominated by characters who aren't even in the story:

Tinúviel Beren Thingol Bob Lúthien hemlock midges Gil

But most stories don't include many songs or poems. (Whether this is a bad thing depends on how good you expect the marginal poem to be.)

This could be a great way to generate tables of contents. It's much more flexible than hand-written chapter titles, since it works on arbitrary chunks of text. Instead of summarizing only the chunks someone thought to write titles for, you could summarize arbitrary levels of coarseness: hundred-page chunks for a high-level TOC, and smaller ones as you zoom in on a specific section. It could also be helpful for navigating large files: when you're looking for a certain part of a file but don't have a good search term, it might be faster to read through an automatic summary than to manually skim through the text.

Darius' post includes code, so you can see how it works, and try it yourself.

Strings and lines

I was recently surprised by the behavior of the . regex operator in Perl: it matches any character except newline. This seems like the sort of thing I should have already known. It's right there in the documentation. But if I ever knew it, I've forgotten, which suggests I've never tried to match a regex against a multiline string.

Well, of course. How often do you do anything to strings containing newlines, except for printing them out intact?

For that matter, how often do you have such strings at all? Most strings, after all, are either 1) lines of files, which by definition don't contain newlines, or 2) names of some sort, which usually can't contain control characters of any kind. (Yes, filenames can theoretically contain control characters. But have you ever seen one, except for the time you created one to see if it worked?) Even strings that could in principle contain newlines, such as error messages, usually don't, because the possibility doesn't occur to programmers. Control characters aren't real characters, are they?

And, of course, many languages don't allow newlines in string literals. In those that do, they're rarely used.

It seems to me that I (and most programmers, probably) overgeneralize from this: I think of newlines, like nulls and other control characters, as not generally being valid in strings. Consciously, I know strings can contain arbitrary characters, but unconsciously, I think a string must be one line.

The inevitable interpreter

This must be the cutest code injection method ever. Hovav Shacham's paper The Geometry of Innocent Flesh on the Bone: Return-into-libc without Function Calls (on the x86) describes yet another method of injecting code into a process by clobbering its stack. The cute part isn't the title (although it did tempt me to read the paper). The cute part is that this method uses a Turing-complete language for which an interpreter already exists by accident.

It's a generalization of a well-known method called return-into-libc: if you can overwrite a function's return address, you can turn its return into a call to some existing function, such as one from a common library like libc. If you can arrange for the return address of that call to be another library function, you can call a series of them: it's threaded code, expressed through return addresses. This lets you run code of your choosing without injecting any machine code of your own, so it works even if you don't have write access to any executable memory.

But it's limited in its expressiveness, because it only calls the functions provided by the target library, and those usually don't form a complete basis for computation. The available libraries don't generally include functions for branching, looping, moving data around, and the other trivial operations that enable computation. (Languages whose standard libraries contain lots of high-order functions may be more vulnerable in this respect, but since they're not so widely used and most of them are memory-safe, they aren't very attractive attack targets.) Return-into-libc exploits an accidental threaded-code interpreter, but not a very flexible one: it can call arbitrary functions, but it can't compute much.

This paper removes this limitation by showing that the provided functions are not the only possible targets for return-into-libc. Any sequence of instructions ending in a ret can in principle be called as a function, and such sequences are common — they occur at every return site of every function! Furthermore, many such sequences perform useful operations such as arithmetic, conditionals, moves, and looping. These are the missing primitives needed to make return-into-libc Turing-complete. The necessary sequences occur quite frequently in real code, so any substantial x86 library contains a Turing-complete threaded-code interpreter.

The paper also argues that it's difficult for any x86 library to avoid accidentally providing such an interpreter. The architecture goes out of its way to provide convenient instructions for common operations, and to give the common instructions short representations. In particular it provides function return, the crucial operation for this attack, as the convenient one-byte ret instruction. Many other useful instructions are also only one or two bytes, so useful sequences can be quite short. This means they occur not only at intended return sites but as frame shifts inside other instructions, and even in literal constants. So even if a compiler carefully arranged for all return sites to be useless for return-into-libc purposes, the necessary sequences would still appear elsewhere. On x86, it's hard to avoid making the return-into-libc language Turing-complete.

It's not hard to make a Turing-complete language. Many language implementors have done so by accident, when they took languages not intended as programming languages and added convenient features like functions without realizing the implications. Many absurdly simple mathematical systems are also Turing-complete, including ones that don't look like languages, such as Fractran and Rule 110 and Conway's Game of Life. But this is the first case I've heard of where a Turing-complete language exists in the wild, without anyone intending to implement anything like an interpreter at all, as an inevitable consequence of a machine's architecture.

(Via Z-Bo on LtU. This is old news, but I hadn't heard of it, so maybe you haven't either.)

Thou art thyself, though not a Scheme

Is there any part of a language so obviously unimportant as its name? PLT Scheme was recently renamed to Racket, but it's just a name change; the language is the same as before (or at least isn't changing faster than usual). I was rather surprised to hear of this (I fleetingly thought it was April) since the old name is so well known, but apparently the PLTers think their language will be better off if it's not associated with other Schemes. Anyway, the change shouldn't affect anyone who knows, right?

But it does affect me. Yesterday I was lamenting how little of Scheme is portable across implementations, and found myself thinking, “wait, that doesn't apply to PLT Scheme any more, because it's Racket now”. Even though I know there's no difference, I tend to see PLT Scheme as a Scheme with nonportable extensions, and Racket as an independent language. The new name is working: it makes me take Racket more seriously as a platform, not just an implementation.

(However, I keep mistaking it for “Rocket”.)

“Dynamic programming” obscures a simple concept

I'm surprised at how many commenters on my previous post (here and at Reddit and HN) think it's a mistake to identify dynamic programming with memoization. I thought this was uncontroversial: that the central idea of DP is simply to make naive recursive algorithms efficient by memoizing. Evidently a lot of readers think otherwise.

I think they've been misled by the traditional presentation of DP, which bundles a lot of optimizations with that central idea. The recipe usually goes something like this:

1. Generate a naive recursive algorithm.
2. Memoize it by saving partial results in an array.
3. Invert control, so the table of results is explicity assembled bottom-up instead of as a byproduct of top-down recursion.
4. Analyze the dependencies among the partial results, and if possible, simplify the saved results to avoid storing unnecessary data.

Notice something wrong here? All the action happens in the first two steps. Well, semantically all the action happens in the first step; even the memoization is only an optimization. But what an optimization! It's what makes impractical algorithms practical; the remaining steps don't change much. The inversion of control usually contributes nothing, so I'm puzzled that some commenters describe it as the distinctive feature of DP; it looks like an artifact of the imperative past to me. Simplifying the results is valuable when it works (it can change the space complexity), but it only applies to some problems; usually it yields little or nothing. Memoization is the important part; the rest is optional.

Many programmers learn memoization only as a part of this recipe, and therefore call it by the same name. This is why, when people speak of “a dynamic programming algorithm”, they often mean a memoized one — the process has given its name to its main technique. This isn't very confusing; I wouldn't deprecate this common usage on this account. But I do think it's unfortunate that many programmers know the simple concept of memoization only as part of a larger, less coherent bundle.

What if the concepts were taught in a different order? Imagine you had learned memoization of recursive algorithms as an independent concept, before you had ever heard of dynamic programming. When you later meet the rest of the dynamic programming package — the iterativizing, the compact representations of partial results, the analysis of dependencies — what would you think of it? Would you see it as forming a single coherent idea, or as a collection of optimizations to memoized recursion — potentially useful, sure, but not intrinsic to the concept?

It would be the latter, of course: that's how you understand other complex groups of concepts. Take garbage collection, for example. It can fairly be described as just “finding the live objects by tracing the object graph”. There is much more to it, of course — many algorithms, some of which don't look much like tracing, and many optimizations and implementation tricks. But we don't define garbage collection as necessarily including all of these. We define it by its central concept, and treat the others as optional elaborations on that.

We should treat the concepts of dynamic programming the same way. Rather than try to include them all in one package, and refer to them only as a whole, we should let the central idea stand on its own, without reference to its optimizations. When you make a naive recursive algorithm practical by memoizing it, there's no need to describe the result as a “dynamic programming algorithm”; “memoized” already identifies the technique. Why use the vaguer term when you don't have to?

Some people see DP differently: not as a method of implementing algorithms but as a method of discovering them. To them, it's about analyzing dependencies in recursive algorithms, because this can lead to discovering a simpler or more efficient algorithm. The other concepts, like memoization, are optional. (If I understand correctly, from this point of view memoization is simply the general case of saving results blindly, regardless of how they're used — a useful tool, but not conceptually important.) This is a reasonable concept, but it's not the one I'm talking about; I'm more interested in implementing algorithms than discovering them. Maybe there's a divide here between theorists, who care more about discovery, and practitioners, who care more about handy tools. I'm on the practical side, so I see the algorithm discovery method as less interesting, because it's less often useful, than a simple tool for making naive algorithms efficient.

In an attempt to forestall the most obvious misunderstanding: I do not claim “dynamic programming”, as commonly used, refers only to memoization; it often refers to a recipe which happens to include memoization as its main ingredient. But that main ingredient is much more important than the rest of the recipe. We should give our attention not to the garnishes, but to the simple base on which the rest is optimizations.

Why “dynamic programming”?

I've always hated the term “dynamic programming”. It's big and imposing, making a simple concept sound far more intimidating than it should. And it's completely opaque: if you didn't know the term, would you ever guess that it meant memo functions? (Yes, memoization is the right concept; see the followup.)

I always supposed it was historical, and must have made sense, in some context, at some point. Groping for some way to remember the term, I came up with a fable: if you see the cached results as part of the program, then dynamic programming involves augmenting the program at runtime. So I imagined memoization had initially been seen (or even implemented) as a form of self-modifying code, and that explained the term.

But it turns out it never made even that much sense. Richard Bellman, who coined it, explains:

An interesting question is, ‘Where did the name, dynamic programming, come from?’ The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word, research. I’m not using the term lightly; I’m using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term, research, in his presence. You can imagine how he felt, then, about the term, mathematical. The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word, ‘programming.’ I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying—I thought, let’s kill two birds with one stone. Let’s take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense. It also has a very interesting property as an adjective, and that is it’s impossible to use the word, dynamic, in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It’s impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities.

“Dynamic programming” never meant anything; it was nothing but a political euphemism. But somehow it became attached to one of the useful concepts Bellman discovered, and to this day, students of computer science struggle to learn that simple idea, because it's burdened with a nonsense name.

Please call it “memoization” instead. And tell your students.

(Via Wikipedia, of all places. It's not usually a good source for CS information, but it's pretty good about linking to historical sources, or at least, as in this case, to an article quoting one.)

(“Dynamic” does have some negatively connoted uses nowadays, in particular in the static type theory community — partly from the perennial flamewar rivalry with dynamic typing, and partly because the main practical purpose of static analysis is to eliminate dynamic uncertainty, so “dynamic” suggests failure.)

Several people have quoted Russell and Norvig: “This cannot be strictly true, because his first paper using the term (Bellman, 1952) appeared before Wilson became Secretary of Defense in 1953.” Perhaps the antipathy to research did not originate with Wilson, or perhaps Bellman initially intended the term to make sense, and only later adopted it as camouflage.

Some things never change

Mike Taylor is having a bad initial experience with Scheme. In particular:

As I continue to work my way through the exercises (using Scheme itself at least for now), I run into a problem: for exercise 2.9.3 I need set-car!, which the purity-fascist maintainers of PLT Scheme removed in release 4.0. No doubt there is a secret incantation to undo this change, but I can’t immediately see what it is.

As he has already figured out, this is because he's using an R5RS book with an R6RS-ish implementation, and R6RS DrScheme's dialect is not a superset of R5RS — not even of the commonly taught parts of R5RS. Such conspicuous backward incompatibilities occasionally strike other languages (Perl, certainly, and hasn't it happened to Python at some point?) but it's more embarrassing in a language like Scheme, which is supposed to be old and elegant and stable.

Correction: as Eli Barzilay points out, it's supposed to be an R6RS book. The use of set-c*r! without the necessary (import (rnrs mutable-pairs)) is probably an oversight, made easy by the fact that it still works in most R6RS implementations. So part of the problem here is that the book is buggy: it uses features that aren't in the language it's teaching. Also, DrScheme's main language isn't R6RS but a different dialect which also happens to lack set-car!.

It's also unfortunate in a language which already has a reputation for being impractical. Mike correctly attributed the problem to “purity-fascist maintainers”, but how many other students, on seeing that Scheme's most popular educational implementation doesn't (by default) support the examples used in popular tutorials, have concluded (or confirmed their prejudice) that Lisp is not useful outside of the ivory tower?

(I don't particularly mind immutable lists, but they're a strange thing to break backward compatibility over.)