Re: Automake::Conditional::simplify (Quine-McCluskey)

[Raja R Harinath]

Hi,

Alexandre Duret-Lutz <address@hidden> writes:

>>>> "Raja" == Raja R Harinath <address@hidden> writes:
>
>  Raja> And, dare I say, implement Quine-McCluskey minimization ;-)
>
> You've just won another patch to review :)

Man, that was quick :-)

[snip]
> Index: automake.in
> ===================================================================
> RCS file: /cvs/automake/automake/automake.in,v
> retrieving revision 1.1388
> diff -u -r1.1388 automake.in
> --- automake.in       14 Nov 2002 22:37:29 -0000      1.1388
> +++ automake.in       16 Nov 2002 12:31:04 -0000
> @@ -6184,7 +6184,7 @@
>        push @res, $icond
>       if ($cond->true_when ($icond)); # (3)
>      }
> -  return @res;
> +  return (new Automake::ConditionalSet @res)->simplify;
>  }

This is for later cleanup...  But, it would be nice if more of the
functionality of variable_not_always_defined_in_cond() is moved into
Automake::Conditional[Set].

If A::CS had two methods 'sub_conditions':

  new A::CS("A_FALSE B_TRUE", "A_TRUE C_TRUE", "A_TRUE D_FALSE")
   ->sub_conditions("A_TRUE")
   == new A::CS("C_TRUE", "D_FALSE")

and 'mult_cond':

  new A::CS("C_TRUE D_FALSE", "E_FALSE")->mult_cond("F_TRUE G_FALSE")
   == new A::CS("C_TRUE D_FALSE F_TRUE G_FALSE", "E_FALSE F_TRUE G_FALSE")

Then v_n_a_d_i_c($var, $cond) would be

  $variable_conditions($var)
  ->sub_conditions($cond)
    ->invert
      ->simplify
        ->mult_cond($cond)

Almost self-documenting :-)

[snip]
> Index: lib/Automake/ConditionalSet.pm
> ===================================================================
[snip]
> +sub simplify ($)             # Based on Quime-McCluskey's algorithm.

That should be 'Quine'.

> +       # Fire the relevant bit in the strings.
> +       if ($2 eq 'FALSE')
> +         {
> +           $false |= 1 << $rank;
> +         }
> +       else
> +         {
> +           $true |= 1 << $rank;
> +         }
> +     }

This means that you're limited to ~25 conditionals, or you need

  use Math::BigInt;

on top, or use a custom bitset.  We can revisit this later, I guess.
But, we may have to put in a warning in here if $rank >
significant_bits_in_float.

> +  # Real work.  Let's combine terms.
> +
> +  # Process terms in diminishing size order.  Those
> +  # involving the maximum number of variables first.
> +  for (my $m = $#subcubes; $m > 0; --$m)
> +    {
> +      my $m_subcubes = $#{$subcubes[$m]};
> +      # Consider all terms with $m variables.
> +      for (my $j = 0; $j <= $m_subcubes; ++$j)
> +     {
> +       my $tj = $subcubes[$m][$j];
> +       next unless $tj;      # Skip deleted terms.

Given your loop below, how can $tj be deleted?

> +       my $jtrue = $tj->[0];
> +       my $jfalse = $tj->[1];
> +
> +       # Compare them with all other terms with $m variables.
> +     COMBINATION:
> +       for (my $k = $j + 1; $k <= $m_subcubes; ++$k)
> +         {
> +           my $tk = $subcubes[$m][$k];
> +           next COMBINATION unless $tk; # Skip deleted terms.

Likewise with $tk.

> +       # Filter-out implied terms.
[snip]

(BTW, is almost equivalent to Automake::Conditional::reduce).

> +       next if $tj->[2];     # Skip covered terms.  (If $tj covers some
> +                             # terms, they will be filtered out when
> +                             # we later process the term that covers $tj.)

See below:

> +       for (my $n = $m + 1; $n <= $#subcubes; ++$n)
> +         {
> +           my $n_subcubes = $#{$subcubes[$n]};
> +
> +           for (my $k = 0; $k <= $n_subcubes; ++$k)
> +             {
> +               my $tk = $subcubes[$n][$k];
> +               next if $tk->[2]; # Skip covered terms.

Don't you need a

  next unless $tk;

> +               my $ktrue = $tk->[0];
> +               my $kfalse = $tk->[1];
> +
> +               next unless $ktrue == ($ktrue | $jtrue);
> +               next unless $kfalse == ($kfalse | $jfalse);
> +
> +               delete $subcubes[$n][$k];
> +             }
> +         }
> +     }

Might as well delete all covered $tj here.  You're going to skip over
them all the time, anyway.

> + }

Actually, this whole part can be pulled out, and done in a separate
(nested-)loop, a la stage 2 of QM.  You can even do somewhat less work
if $m ranges from 1 upwards rather than downwards to 1, and this can
even be combined with the next loop that collects the or_conds.

- Hari
-- 
Raja R Harinath ------------------------------ address@hidden