[HN Gopher] Knuth and McIlroy Approach a Problem (2021)
___________________________________________________________________
Knuth and McIlroy Approach a Problem (2021)
Author : ingve
Score : 52 points
Date : 2023-05-12 12:24 UTC (2 days ago)
(HTM) web link (matt-rickard.com)
(TXT) w3m dump (matt-rickard.com)
| mordae wrote:
| Evolution of Haskell Programmer[1] comes to mind.
|
| [1]: http://www.willamette.edu/~fruehr/haskell/evolution.html
| KRAKRISMOTT wrote:
| When did they hold the competition? I believe the textbook
| solution to this is using a heap.
| abecedarius wrote:
| It wasn't a competition. As I remember it, Jon Bentley asked
| Knuth to write an introductory example of literate programming,
| and McIlroy to review it in something like the way a literary
| critic would critique an essay. Both responses were thoughtful.
| I learned more from the Knuth, but then I was already familiar
| with the Unix philosophy.
|
| To use the heap you still need to look up the words
| efficiently.
| bombcar wrote:
| It's reprinted in Knuth collections so even he notes the
| point - there's a time and place for everything.
|
| And one requires WEB and the other requires the entire Unix
| tool chain.
|
| (And the only reason the Unix critique is ever mentioned is
| because of the literate programming version. Which would
| programmatical archeologists love to find in 2525 - if man is
| still alive?)
| KRAKRISMOTT wrote:
| > _To use the heap you still need to look up the words
| efficiently._
|
| Why? Just split the text and put everything into the heap,
| the heap algorithm will maintain the sorted order by
| rebalancing during insertion
| abecedarius wrote:
| The textbook solution I assume you meant, to find the most
| common k elements of a list, uses an updatable priority
| queue (heap). This orders the (key, count) pairs by the
| _count_. But that 's a separate question from how you look
| up the key (i.e. given a word, find the pair whose count
| you want to increment), which is what Knuth's hash tries
| were for here.
| KRAKRISMOTT wrote:
| Thanks for the clarification
| [deleted]
| donkeybeer wrote:
| It seems the date was 1986. What I find surprising is McIlroy's
| solution feels completely modern still, one could still solve
| the problem more or less in the same manner today when writing
| a command pipeline on a unix derived os. Even the names and
| syntax of the commands hasn't changed.
| Avshalom wrote:
| Once again: this does not demonstrate Knuth's approach to solving
| a problem, it demonstrates Knuth's approach to pedagogy.
|
| also it was not a 'competition'
| thr-nrg wrote:
| I'm reminded of the old adage about playing chess with a
| pigeon. It knocks down the pieces, shits on the board and flies
| off.
| luispauloml wrote:
| What made you remind of it?
| phtrivier wrote:
| Every few years, I contemplate the idea of trying out literate
| programming. I get that notebooks have continued to trends of
| "mixing prose and code" to great success ; however, I really
| wonder how the "out of order programming" works out in practice.
|
| Sadly, I never managed to go passed the "my editor cannot show
| syntax highlighting for a mix of languages." :/
| iib wrote:
| This is doable in Emacs, using org-mode and org-babel.
| phtrivier wrote:
| You're right, I should have mentioned org-babel as the
| closest thing to something that would work for me.
|
| However, as soon as I start using noweb syntax for "out of
| order" programming, I stumble into long standing bugs
| (references are not always found, links in the tangled code
| are broken, detangling does not work, etc...)
| wolfgang42 wrote:
| Not sure what editor you use, but most syntax highlighters
| these days can mix languages: you see this e.g. in HTML <style>
| tags and Markdown fenced code blocks.
|
| As for 'out of order programming', I think that TANGLE-style
| reordering is a lot less important with modern programming
| languages: they don't do one-pass compilation and so can deal
| with forward references. Note that most of the cross-references
| in Knuth's program could be replaced with function calls or
| constant names, rather than the semiautomatic inlining that WEB
| performs.
|
| I've had some success in writing literate programs in a
| Markdown file, with a small script to extract the code blocks
| into a file for execution. This seems to work fine, at least on
| a small scale, and is very easy to implement and then extend if
| needed.
|
| Edit: and by "small script" I mean: import
| sys code = False for line in
| sys.stdin.read().splitlines(): if line == '```':
| code = False # End block if code: print(line) #
| Only output block contents if line == '```md': code
| = True # Start block
|
| It also seems worth noting that you can get much the same
| result just by writing a lot of comments; this technique is
| mainly useful when you also want more formatting than can be
| reasonably squeezed into plain text. /edit
| ranting-moth wrote:
| That unfortunate remark by McIlroy did more harm to himself that
| Knuth.
| benj111 wrote:
| Only because you agree with Knuth.
|
| Both McIlroy and Knuth have valid points. There's a reason that
| not all shell scripts are written in the literate style.
| There's also a good reason why large programs aren't written
| like shell scripts
| Jtsummers wrote:
| > Both McIlroy and Knuth have valid points.
|
| Knuth was asked to write a program illustrating his technique
| of literate programming, which he did. He was not making a
| "point". He was making an example. Very different things.
| McIlroy came in and made a point in his review. Other people,
| presumably illiterate because the source is available and we
| can know what was written, made it into a competition or
| debate. Which it was not.
| Avshalom wrote:
| There's nothing to "agree" with Knuth here. He wrote it to
| demonstrate WEB and literate programming, not because he
| thought it was the best-fit solution to this task.
| benj111 wrote:
| Ok, but McIlroy was asked to critique it. I suppose you
| could say that he was asked to critique a literate program,
| but that seems to me like complaining to Mr Ford, because
| you asked for a faster horse, and he came back with a car.
| Literate program is meant to solve a problem. The goal
| should be finding the best way to solve that problem. Not
| solving the problem based on some preconceived notion.
|
| Perhaps "agree" was the wrong word, but this exchange is
| remembered for a reason.
| brudgers wrote:
| If you want to understand McIlroy's code, you can always read the
| what McIlroy wrote in what McIlroy wrote in _Communications of
| the ACM._
|
| If you want to understand Knuth's code, you can always read what
| Knuth wrote in the code Knuth wrote.
|
| To the degree "programs must be written for people to read, and
| only incidentally for machines to execute" McIlroy's code traded
| incidental complexity for brevity. Considering his ordinary
| expectation that readers would be "old Unix hands" at Bell Labs,
| this is probably an entirely reasonable engineering tradeoff.
|
| Knuth's intended audience has always included at least his future
| self. To the degree "debugging is twice as hard as writing code
| in the first place" verbosity is also an entirely reasonable
| engineering tradeoff. He's been working with some of some of his
| algorithms for sixty years.
|
| If I had a criticism of McIlroy's response -- and I say "had"
| because it's been forty years more or less -- it's the either or
| approach. Literate programming is a not-for-me for a lot of
| people. That doesn't make it bad or good. Just a not-for-me.
|
| But hell, forty years ago we didn't have so many chances to
| scratch itches to argument. Arguments always drive engagement for
| publishers.
|
| Some things don't change very much.
| pieterr wrote:
| See also:
|
| https://news.ycombinator.com/item?id=3329668
|
| https://news.ycombinator.com/item?id=18699342
___________________________________________________________________
(page generated 2023-05-14 23:02 UTC)