Hacker News Reader

Comment by erre | Hacker News Reader

For those who don't know, this is Rob Pike's chapter of Beautiful Code, a thoroughly enjoyable book: http://www.amazon.co.uk/Beautiful-Code-Leading-Programmers-P... . Every now and then I read a different chapter, and it's always interesting. I particularly liked Rob Pike's one, and the one about Python's dictionary implementation.

View on HN

This code is beautiful, but it's also busted [1] -- albeit only for extraordinarily pathological input. As to whether this ultimately dents its beauty is up to the beholder, presumably; for me personally, I confess to suffer from a utilitarian sense of beauty when it comes to software -- for me, broken code can't achieve absolute beauty.

[1] http://dtrace.org/blogs/bmc/2007/07/11/beautiful-code/

I believe Kernighan acknowledged that: "[snip] The depth of recursion is no more than the length of the pattern, which in normal use is quite short, so there is no danger of running out of space. [/snip]".

If you're going to judge this code based on both pathological haystacks but also pathological needle regexs, then you have to admit that this code, which has linear space usage in the pattern length is far better than PCRE, which has exponential time in the pattern length[1].

Considering its succinctness, I find that pretty impressive.

[1] http://swtch.com/~rsc/regexp/regexp1.html

Ah, and Jon Bentley's chapter about quicksort, along whose lines there's a (also very interesting) Google Tech Talk: http://www.youtube.com/watch?v=aMnn0Jq0J-E

Reply on news.ycombinator.com