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

[Alexandre Duret-Lutz]

>>> "Raja" == Raja R Harinath <address@hidden> writes:

[...]

 >> BTW, I wonder if it's even possible to use so much conditionals
 >> in Automake.  

 Raja> Exactly.  I don't think it's worth it.  

Ok, for now I'll just change simplify() to return the input
as-is when this happens.

[...]

 >> Calling A::CS::permutations with 25 conditionals seems somewhat
 >> memory-consuming.  (Maybe it could help -- not in worst cases -- to
 >> always call A::CS::simplify before A::CS::invert)

 Raja> And, you could switch to a more compact representation for
 Raja> A::Conditional: move %var_rank and @rank_var from A::CS::simplify
 Raja> into A::Conditional, and represent conditionals directly as bitsets.

This sounds like a good idea.  However to do this we really need
a bitset implementation (because %var_rank and @rank_var would
apply to the whole project, instead of just one ConditionalSet).

[...]

 Raja> If you really want to worry about scalability, A::CS::invert would be
 Raja> better written as a product-of-sums to sum-of-products converter,
 Raja> rather than explicitly enumerating every truth-value candidate.

Indeed.  I'll do this.

 >> 2002-11-17  Alexandre Duret-Lutz  <address@hidden>
 >> 
 >> * lib/Automake/ConditionalSet.pm (simplify): New method.
 >> (string): Call string for each Conditional.
 >> * automake.in (variable_not_always_defined_in_cond): Return
 >> a simplified ConditionalSet.
 >> (macro_define, require_variables): Adjust.
 >> * tests/Makefile.am (TEST): Add library3.test.
 >> * tests/library3.test: New file.
 >> * tests/pluseq9.test: Adjust.

While writing test cases, I've found a formula which is not
correctly simplified.
   A_FALSE or (A_TRUE and B_TRUE) 
is output as-is, although it could be simplified to 
   A_FALSE or B_TRUE

It's my understanding that Quine-McCluskey's algorithm wouldn't
accept such input.  It only takes input products involving all
variables.  (I might as well be wrong: I've just read a few
slides found on the Internet after you mentioned that name.)
So one solution would be to transform this into
   (A_FALSE and B_TRUE) or (A_FALSE or B_TRUE) or (A_TRUE and B_TRUE)
and things would work.
However in the general case this is memory consuming just 
like A::CS::permutations().

Avoiding these "permutations" is why we have and additional loop,
"filter-out implied terms", after the combination step.  
It transforms
   F or (F and G) 
into
   F
(where F and G are products of variables)

Maybe we should have a similar transformation, 
*before* the combination step, to transform
   F or ((not F) and G)
into
   F or G or ((not F) and G)
(not removing the last and-term, so it can be 
used in other combinations).

The question is how to match `(not F) and G'.
First, `not F' is a sum: NF1 or NF2 or ... or NFn
So given F we should look if we have the following n 
Conditionals before we can add G:
   NF1 and G
   NF2 and G
   ...
   NFn and G
Searching for these doesn't seem easy because we don't know G.

Second, `not F', means calling invert() for all Conditional in
the ConditionalSet.  Ouch.

At worst we could do this when F involves only one variable
(then it's easy to match `(not F) and G'), and ignore the other
cases.

Any thoughts?
-- 
Alexandre Duret-Lutz