developer.* Blogs - Brian Kernighan's Beautiful Code? - Comments

Pike and Kernighan: .6 secs: C Sharp: 2.7

Edward G Nilges — Wed, 02 Jan 2008 22:46:26 -0800

...for a long string, AFTER one million iterations.

See main blog post.

((((poot)))*)

Edward G Nilges — Sun, 30 Dec 2007 04:53:46 -0800

I also failed to realize that the test variable in Pike's "Beautiful" code isn't at all updated in matchhere() or matchstar() on behalf of match(): as in match() itself, the copy of test on the stack is used as a working variable. Basically, no effort at all was made by the Pikester to return the position of the satisfying string, and in the so-called real world, isn't this exactly your next question?

(((poot)))

Edward G Nilges — Fri, 28 Dec 2007 04:15:24 -0800

Sorry, hopefully only one more error: I imply that you DO get the address IF you pass the test string in a variable. This is incorrect since value parameters in C are copied to the stack and, if modified, that modification is lost.

Which means that the original objection stands. The code isn't at all useful for finding WHERE the string, that satisfies the regular expression, exists in test. It merely finds WHETHER it occurs.

Is such spare functionality Beautiful? I don't know. It sure isn't Reusable.

Nonsense prevails, modesty fails
Grace and virtue turn into stupidity
While the calendar fades almost all barricades to a pale compromise
And our leaders have feasts on the backsides of beasts
They still think they're the gods of antiquity
If something you missed didn't even exist
It was just an ideal -- is it such a surprise?

What shall we do, what shall we do with all this useless beauty?
All this useless beauty

kscaldef's comment on the Kernighan code in reddit

Edward G Nilges — Thu, 27 Dec 2007 10:47:04 -0800

kscaldef points out, with respect to my point (1), that you don't need in a minimal implementation to support a+ where + means one or more times: you just use aa*!

But I add at reddit that the code doesn't support nesting in the regular expression as in (a+c)*.

It's syntactic sugar to insist that Rob should have supported postfixable strings as well as characters (although the failure to support international characters is significant). But by allowing parentheses Rob could have had strings for free as in (abc)*.

I'm on admittedly shaky ground. A pure mathematician would ACCEPT only character processing, equating the char with a symbol on a Turing Machine square, and assume that any string could be represented as any one of an infinity of possible characters, as Chinese ideograms represent thousands of ideas.

A programmer like Rob simply restricts himself to the problem statement, so Rob did good.

What remains for me unforgiveable is that this hack is considered Beautiful Code by Brian, at least without a considerable discussion of its limitations. I'd accept it as neo-Primitive art if only Brian had done so.

Recursive brain fart ((poot)*)

Edward G Nilges — Thu, 27 Dec 2007 08:21:19 -0800

Of course, most users of the Pike code will pass a string literal as the "test" parameter, thereby losing the address of the satisfier.

(poot)*

Summary of the flaws I think are in the Kernighan and Pike code

Edward G Nilges — Thu, 27 Dec 2007 08:19:27 -0800

A discussion of the above blog post has started on programming.reddit.com in the usual way, with complaints about literary style rather than technical remarks, because, as one poster says, pointer arithmetic is hard.

Because the reddit posters complained about the political observations, I posted the following technical discussion at http://programming.reddit.com/info/63vc1/comments/.

Here is a summary of what I think are the flaws in the code Rob Pike wrote for Brian Kernighan, and which Brian presents as Beautful Code in a book of that name, published this year by O'Reilly, on page 3 (an unindented copy of Rob's code as keyed by me, and wrapped in a C++ class, is at my developerDotStar blog). I read C but have long since abandoned it because I don't think Beautiful Code can be written in C: the Pike code, I think, is an example of code that only seems Beautiful.

I won't include any postmodern theory in this particular post despite the fact that aesthetics is political.

(1) Pike's code doesn't implement a regular expression interpreter insofar as "regular expressions" have a formal, mathematical meaning. For example, it makes no provision for a character which must occur at least once.

(2) It is idiomatic C, which uses a parameter passed by value as the changeable index into the string it points-at and it expects the user to grok the fact that she has a useful value in that value parameter (the start of the text conforming to the regular expression), something unexpected outside of C. If the user passes the text as a string literal, the useful point at which the regular expression occurs is lost.

(3) While advertised as a string processor, it does not handle modern Unicode or double-byte strings containing international input.

(4) Its comments are unilluminating especially as regards need-to-know the fact that its value parameter contains a useful result (the start position of the regular expression), and Brian's discussion in Beautiful Code is unhelpful. Of course, as noted above, this address is lost when a string literal is passed.

(5) The length of the substring of characters that satisfies the regular expression is lost.

(6) Kernighan does express, in the text of the essay, the concern that the code, which does heavy recursion proportional to the string length, might run slowly or overrun stack limits.

But no consideration exists in the code that a semi-beautiful way exists to avoid most recursion. If the regular expression does not start with a string start carat or string end dollar sign, its first character, if not followed by an asterisk, is a "handle" which which can be scanned-for in a nonrecursive loop or by a strcspn function.

Even if the first character (that's not dollar or carat) is followed by an asterisk, if the asterisked character occurs frequently, the code can search for the first character, and return a match immediately upon finding it, or, entering the recursive code upon failure.

What would be Beautiful about this? The fact that it's not the sort of thing an optimizing compiler would "think" of, whereas the apparent efficiency of Pike's code is often discovered by an optimizing compiler (although an optimizing compiler would not "see" the utility of recursion in an iterative solution, to be sure).

It would, I think, amortize the cost of using a platform, whether Java or C Sharp, that handles real strings through an abstraction.

Please feel free to point out where I've gone off the rails, since I have such respect for Kernighan that I'm astonished that he feels that this snippet is Beautiful Code.

Brain Fart

Edward G Nilges — Wed, 26 Dec 2007 23:50:42 -0800

It wasn't until I posted to comp.programming that in an exchange with Malcolm McLean that I realized that you DO know where the string occurs when you use the Rob Pike code.

Because the "test" variable is used as an index-address, it contains the start of the regular expression's occurence on exit from a successful search or a null length "string", in the case of failure.

Is this "elegant"? No, since you're not given the length of the string that satisfies the regular expression, and this cannot be determined from very simple regular expressions such as C*!

Furthermore, although it was sorta dumb of me not to see that the test value is a result as well as input, and to recall to mind that C "value" parameters can contain results, Brian should have spelled this out.

No, Brian, I'm not saying "Don't Make Me Think!" I am saying I would have spelled this out and not assumed a knowledge of C, because shibboleths (using idioms to select an audience) are tribal.

Primitive art linked to magic and ritual is beautiful, but it isn't beautiful to in effect celebrate 1971 as a computing year in which the theory of parameter types was in its infancy.

It is said that elegance is in the mind of the beholder, and a reputable literary theory, reader-response, affirms that in part literary elegance depends on an audience.

But this means that the very word, "elegance", has to be subscripted with the name of the audience.

The C expert no doubt gets a *frisson* of delight when he sees, a lot faster than I, that (1) test is used as a work area and (2) test gives back the starting address of the satisfier string.

However, what's missing is an acknowledgement that there's an audience out there of intelligent professional programmers who don't use C, or who used to, but then got help. What's missing is a true computing cosmopolitanism, that of the Algol publication language, that was short-changed by IBM's development of Fortran, and the Eisenhower administration's post-Marshall Plan desire to let the Western Europeans know that they were junior partners.

Brian Kernighan's Beautiful Code?

Edward G Nilges — Tue, 25 Dec 2007 22:06:40 -0800