Testing fuzzy approximation with Test::Deep

Maybe the title of this post is misleading, but I will explain what I mean.

Last year I wrote a series of LCS (longest common subsequence) modules for speed and rock solid quality. Then I had a need for smarter alignment and added similarity to the algorithm, now released as LCS::Similar on CPAN.

The hardest part in developing LCS and friends was sorting out bogus algorithms from a collection of nearly 100 publications with pseudocode and sometimes code. It needed some time to get all cornercases as testcases.

But how to test an algorithm which returns one of maybe more than one optimal ("longest") solutions? With a method allLCS() returning all solutions and comparing the single solution against them.

Here is what the output looks like:

my $cases = {
  'case_01' => {
    'allLCS' => [
      [ [ 0, 0 ], [ 2, 2 ] ],
      [ [ 1, 0 ], [ 2, 2 ] ]
    ],
    'LCS' =>
      [ [ 0, 0 ], [ 2, 2 ] ],
  },
  'case_02' => {
    'allLCS' => [
      [ [ 1, 1 ], [ 3, 2 ], [ 4, 3 ], [ 6, 4 ] ],
      [ [ 1, 1 ], [ 3, 2 ], [ 5, 3 ], [ 6, 4 ] ],
      [ [ 2, 0 ], [ 3, 2 ], [ 4, 3 ], [ 6, 4 ] ],
      [ [ 2, 0 ], [ 3, 2 ], [ 5, 3 ], [ 6, 4 ] ],
      [ [ 2, 0 ], [ 4, 1 ], [ 5, 3 ], [ 6, 4 ] ]
    ],
    'LCS' =>
      [ [ 1, 1 ], [ 3, 2 ], [ 5, 3 ], [ 6, 4 ] ]
  },
};

The result of LCS is valid if it is in the results of allLCS.

At first I wrote the comparison myself but Test::Deep already provides it:

  use Test::More;
  use Test::Deep

  use LCS::Tiny;

  cmp_deeply(
    LCS::Tiny->LCS(\@a,\@b),
    any(@{$object->allLCS(\@a,\@b)} ),
    "LCS::Tiny->LCS $a, $b"
  );

  done_testing;

That's how we can test approximation. But if the comparison in LCS changes from eq to a similarity function returning values between 0 and 1, than additional pairs matched with similarity appear in the result. For a comparison we need any of allLCS is a subset of LCS.

This was the first approach which works not reliable:

use Test::Deep;

# THIS DOES NOT WORK
sub cmp_any_superset {
    my ($got, $sets) = @_;

    for my $set (@$sets) {
      my $ok = cmp_deeply(
        $got, supersetof(@$set)
      );
      return $ok if $ok;
    }
};

Trying around and reading the documentation of Test::Deep again and again, nearly giving up and write it myself, I gave one possible interpretation of the docs a chance:

  cmp_deeply(
    $lcs,
    any(
      $lcs,
      supersetof( @{$all_lcs} )
    ),
    "Example $example, Threshold $threshold"
  );

It works.

How bad can code be - Part 1: The Gordian Knot

How bad can code be?

At the beginning of my career as a developer starting from scratch I became responsible for the maintenance of a package consisting of approximately 40 KLoCs (Lines of Code) Assembler. It was called "realtime controlling part", a sort of middleware controlling transactions, database recovery, asynchronity, and communication.

It existed in three variants for four different applications. First person A developed it for application AA, then he became datacenter manager. Then person B forked it for different requirements of HH and BB+CC. In summary 70 KLoCs, partly similar, but not exactly the same.

The BB+CC version was the most complicated with a special feature called pre-read. It guesses in the queue of incoming transactions, which records should be read in advance, waits for all of them, and puts them into the application queue. Same in reverse order with the inserts and updates in the answer of the application. And exactly this most complicated part was written by not-so-skilled person C.

The pre-read module had around 4000 lines and was hard to read. No subroutines. Variables uses as switches, i.e. store the result of conditions, check or change them somewhere in the code. Of course you need to init them. You need a good name within the allowed 8 characters. You must predefine them at the end of the source. But debugging is a hell, because the more switches you use, the more possible combinations of states you have. Combined with spaghetti style code, jumping around cross-cross it's a Gordian Knot. Lady programmer D removed two dozens bugs raising in production. In my period I also solved a similar amount. One bug was not solvable. Sometimes the whole thing got sleeping, waiting for nothing, hanging.

This was the worst code in production I had to work with.

Lessons learned:

• do not use the weakest skilled person for the most complicated task
• avoid switches
• no literals in the code, define them as constants
• use structured programming style (needs discipline in Assembler)
• subroutines should fit into a screen (24 x 80 at this time)
• code reentrant, even if it's not necessary

Fortunately I got 1 year time and budget to rewrite this package.

It was only necessary to change to another network technology, so just rewrite this part of handling incoming and outgoing messages. Second it was also necessary to refine restart and recovery as the architecture changed to distributed processing, i.e. the local organisations got all midrange servers, and the communication changed.

I started with the communication interface as an isolated module, but the network servers were not available, planned 6 months later for first integration tests. So I learned to test with stubs and drivers, simulating the other parts. In a team of 12 persons you speak with the others, even if you are working alone. One day person O, a genius, but nearly autistic developer said to me "The whole thing is crap and completely wrong." Why? What's wrong? Should I do it this way? "No, it should be this way." He always answered with one short sentence. We always had short and loud discussions. After the discussions I returned to my room for thinking about the design. And then I visited him again.

With this ideas I wrote a dispatcher, controlling queues, reqeuing ready tasks, queuing free tasks into the memory pool, activating the handlers. It had some 100 lines. This made possible to reduce the control logic in the handlers. The handlers could be reduced to wait for work, do some stuff, subrequests to other tasks and wait for the result, do some stuff, send result to requesting task, wait for new work. No need for variables, only maps to the control blocks in the queue, only constants in the task modules. Hey, this is reentrant.

Now the problem was to factor out the necessary logic from the old code, and clean away the control logic. I did this during the easter days at home. Imagine a living room with the compile printouts covering the whole floor, me using markers in two different colours, marking the good and the bad. Of course it was not finished in one step. I refactored my own code 12 times along the progress. The horrible pre-read module was reduced from 4000 lines to 100 lines nearly linear, straight ahead code. Others were also reduced in size and the variants disappeared.

This software was in production nearly 20 years, without an outage, and without change.

Lessons learned:

• you need 2 very good developers in a team
• not all developers in a team need good communication skills
• learn from critic, even from harsh critic
• advantage by restriction
• less is more
• refactor often
• conform to quality standards and best practices

Gordian Knots can be solved.

Next in this series: two huge Perl projects