Lambda the Ultimate on "Coders at Work"

http://lambda-the-ultimate.org/node/3613

by hvs • 17 years ago

67 10 17 years ago

I've always found Knuth's views curious. Is it just that he's from a different generation, or am I too much of an amateur to understand his wisdom? I don't know.

A couple of days ago he gave me a copy of his paper on Leaper graphs (On dead trees.. quaint :-) His office is a few doors from mine.) Along with a charming note about rewards for finding bugs. Anyway, Leaper graphs are the graphs that describe the moves of a generalized Knight on generalized chessboard. So I researched this some more, and found that Knuth was the first to enumerate all the Knight's tours that are invariant under 180° rotation.

At this point I'm thinking, this sounds like it could be an ICFP problem, and a language like Haskell would be ideally suited for it. Nope, turns out he wrote the program in his C variant. http://sunburn.stanford.edu/~knuth/programs/sham.w I'm amazed you can write that in C and have it turn out as short as it was. It also looks like it has goto's.

I really don't know what to take away from it.

mhansen2• 17 years ago

The chessboard has rotational symmetry: if you turn it 180 degrees it is the same. Would not all tours be invariant under 180 degree rotation?

EDIT: Sorry, I understand now. If the knight's tour ends directly opposite it's starting position, it is invariant under 180 degree rotation.

randomwalker2• 17 years ago

This might help: http://www.mathpuzzle.com/leapers.htm

As you can see from those examples, a symmetric tour is a rather regular-looking object; a random tour has an extremely low probability of being symmetric.

access_denied• 17 years ago

I take away from it that real programmers do not have an emotional attachment to one or other tool/ language. They are interested to solve a problem with maths and logic and the computer and his language are just the butler; a layer that has to be abstracted away.

Obviously Knuth thinks that books as a medium are still valid. (I am with him on this one.)

I have not read the book nor do I have any clue about Leaper graphs, but for some reason he thought it could help to research this. How can this research / knowledge help? Maybe it's just fun, I don't know.

eru• 17 years ago

"I am more comfortable doing it with labels and goto statements than with while loops, but some day I may learn my lesson." (http://sunburn.stanford.edu/~knuth/programs/sham.w)

sb• 17 years ago

having sources of important systems widely (and publicly!) available as "common goods" would be a very good idea for people to learn and read what has been done in the past and how they did it.

it is admittedly very difficult to effectively grasp what has been done more than 25 years ago (even from research papers), i.e., it is hard to deduce from the papers only how APL was implemented or what boyer-moore implemented (heck, douglas comer even has a joke on "critizing" theoretical work by mentioning work by hartmanis)

EDIT: on further reflection, i think that without such an archive, there is no way around "those who do not understand history, are doomed to repeat it." which is particularly sad, since in computer science we do not face many physical problems from conservation science...

jacquesm2• 17 years ago

This is the main reason for so many people being busy with re-inventing the wheel.

To some extent that's the programmers mentality of 'I can do that better', but plenty of times it actually isn't better and the 'oldies' got it solved quite nicely.

The one thing that came by recently where I thought that there actually was something new happening was the thread on improving on quicksort (I can't seem to find the thread :( ).

Another instance that comes to mind is the ever improving compression ratio of lossless compressors, just when you thought the lemon was really empty someone comes up with something extremely clever.

bad_user• 17 years ago

> This is the main reason for so many people being busy with re-inventing the wheel.

I don't know about other people, but I'm reinventing the wheel to learn better.

An algorithm you reinvented only to discover a better version later will stick to your head. And it's also fun doing it.

Also, a library or a tool you "reinvent" is many times better for your needs considering that assembling software pieces is not actually like putting together Lego blocks (although corporates are still trying).

Quicksort reinvention is also useful, because that standard qsort you've got laying around there might not behave as you expect (like glib's qsort that uses merge-sort instead) or it might not be optimized for your datasets (because you know, depending on the partitioning function you might end up in the worst-case scenario quite a lot).

Lambda the Ultimate on "Coders at Work"

Related Stories