how to debug?

[David Roundy]

On Sun, Oct 06, 2002 at 12:16:50PM +0100, Jon Fairbairn wrote:
> 
> > I have already isolated my bug within one function, but
> > that function has somewhat funky recursion, and uses an
> > array (which I'm none too familiar with in haskell), and
> > there aren't any smaller parts that I can see to test.  :(
> 
> More seriously: It seems to me likely that this function is
> too complicated for your current level of understanding
> (which probably means it's simply too complicated, full stop).

Indeed it was (and still is, to an extent).  The difficulty was that I was
trying to implement the Hunt-Szymanski LCS algorithm without really
understanding how it works, just by implementing the algorithm as original
1977 paper.

> Often, a better approach than trying to debug a function is
> to break the function into smaller parts using higher levels
> of abstraction. For example, you say that it involves
> "funky" recursion: perhaps it can be rewritten in terms of a
> fold or similar?

Actually, after looking at it again, I realized that the only funky
recursion was that I was implementing the equivalent of two nested
iterative loops with one recursive fuction.  When I broke this into two
functions (one of which was a one-liner, and the other almost an identical
copy of the code from the original non-working function), everything
started working.

I think this advice, together with a day of rest, was just what I needed!

It took a while to work out a few other bugs (mostly related to the fact
that Hunt and Szymanski assumed two strings of equal length for
simplicity), but I now have a working and reasonably fast LCS functions.
:) My "diff" command (written to use as a speed test) seems just about 10
to 15 times slower than GNU diff for a particular pair of files, which
isn't bad considering that I have done nothing to optimise for speed!

btw, thank you also to everyone else who gave me advice!
-- 
David Roundy
http://civet.berkeley.edu/droundy/