Re: Boolean As a Top Level Name

[Timothe Litt]

On 11-Sep-16 18:19, Lincoln A Baxter wrote:
> Having followed this discussion (more or less, I have no clue what the
> MiuneMcCluskey alorithm is), but I like Logic::Minimise
>
> Lincoln
Quine-McCluskey is used to simplify boolean functions.  It's similar to
Karnaugh maps, which may be familiar to more folks.  But if you think of
it as an expression optimizer similar to what compilers do, you have the
idea.

The problem is that QM is NP-hard O(3**n/n).  For non-toy problems, one
partitions the problem manually and/or uses something else: e.g.
EXPRESSO (BSD licensed, could be incorporated into a Perl module).

Logic::Minimize works for me.  (I won't get into the British vs. U.S.
spelling argument.)

I don't see much point in a pure QM implementation, except as an
educational exercise for students. 

I also don't see much point in separating the algorithm from
Logic::Minimize; as an implementation detail, you could have
Logic::Minimize::Expresso and/or Logic::Minimize::QM as internal
namespaces - mostly to allow for any breakthroughs in algorithms.  The
inputs and outputs of any such algorithm are stable, so changing under
the covers should not be hard.  Simply wrapping an algorithm to create
the Logic::Minimizer namespace doesn't add any value; there's no
additional (meaningful) level of abstraction.


Timothe Litt
ACM Distinguished Engineer
--
This communication may not represent the ACM or my employer's views,
if any, on the matters discussed. 





smime.p7s
Description: S/MIME Cryptographic Signature

Re: Boolean As a Top Level Name

[David Cantrell]

On Sat, Sep 10, 2016 at 02:46:18PM +0200, Paul Johnson wrote:

>  - The correct spelling is Logic::Minimise

Try searching for "minimise" at oed.com. See also
https://en.wikipedia.org/wiki/Oxford_spelling

But in summary, "minimise" is an acceptable alternative spelling for
"minimize", both are correct.

-- 
David Cantrell | http://www.cantrell.org.uk/david

There are two kinds of security, the one that keeps your sister
out, the one that keeps the government out and the one that
keeps Bruce Schneier out.

Re: Boolean As a Top Level Name

[Paul Johnson]

On Mon, Sep 12, 2016 at 12:44:13PM +0100, Smylers wrote:
> Paul Johnson writes:
> 
> > To be clear, my tongue was firmly in my cheek for that last
> > suggestion, but that doesn't seem to travel too well over SMTP.
> 
> Sure, I realized it was a cheeky suggestion.
> 
> But there are enough UK folk about who complain about -ize being “an
> Americanism” that there might've been readers who genuinely thought
> ‘minimize’ is wrong in the UK.
> 
> > And the myriad smileys which adorned my initial message seem to have
> > been similarly lost.
> 
> Since my previous mail, my MP3 player started playing this podcast at
> me, on the linguists of “maths”: http://relprime.com/thelexicon/
> 
> So maybe Math::Boolean::Minimise would be the best name, to annoy
> everybody equally?

If anyone, beyond Smylers and me, is interested in more of this stuff, I
recommend http://separatedbyacommonlanguage.blogspot.com/ by
@lynneguist, author of the podcast above.

But that's quite enough now for this forum...

-- 
Paul Johnson - p...@pjcj.net
http://www.pjcj.net

Re: Boolean As a Top Level Name

[Smylers]

Paul Johnson writes:

> To be clear, my tongue was firmly in my cheek for that last
> suggestion, but that doesn't seem to travel too well over SMTP.

Sure, I realized it was a cheeky suggestion.

But there are enough UK folk about who complain about -ize being “an
Americanism” that there might've been readers who genuinely thought
‘minimize’ is wrong in the UK.

> And the myriad smileys which adorned my initial message seem to have
> been similarly lost.

Since my previous mail, my MP3 player started playing this podcast at
me, on the linguists of “maths”: http://relprime.com/thelexicon/

So maybe Math::Boolean::Minimise would be the best name, to annoy
everybody equally?

Smylers
-- 
http://twitter.com/Smylers2

Re: Boolean As a Top Level Name

[Paul Johnson]

To be clear, my tongue was firmly in my cheek for that last suggestion,
but that doesn't seem to travel too well over SMTP.  And the myriad
smileys which adorned my initial message seem to have been similarly
lost.

3/10 must try harder

(Smylers, well done on avoiding the past participle of "spell".)

On Mon, Sep 12, 2016 at 11:55:07AM +0100, Smylers wrote:
> Paul Johnson writes:
> 
> >  - The Logic namespace looks like a mess, but I think this module would
> >fit better in there: Logic::Minimize
> >  - The correct spelling is Logic::Minimise
> 
> UK English allows both -ize and -ise endings on many verbs*; USA English
> only has -ize. So picking the one that's valid in both makes more sense.
> 
> There are plenty of cases (like ‘colour’/‘color’) where UK and USA
> spellings are disjoint and you just have to pick one which will be
> ‘wrong’ somewhere, but this isn't one of those cases.
> 
> Smylers
> 
> * I believe -ize was the original UK form, in use at the point when the
>   USA forked English. The UK later took on -ise as an alternative,
>   influenced by French, but the USA didn't cherry-pick that patch to
>   their branch.
> 
>   Oxford dictionaries use the -ize spellings in headwords and list -ise
>   as acceptable alternatives; other UK dictionaries tend to do it
>   t'other way round, but all allow both.
>   http://www.oxforddictionaries.com/definition/english/minimize
> 
> -- 
> http://twitter.com/Smylers2
> 

-- 
Paul Johnson - p...@pjcj.net
http://www.pjcj.net

Re: Boolean As a Top Level Name

[Smylers]

Paul Johnson writes:

>  - The Logic namespace looks like a mess, but I think this module would
>fit better in there: Logic::Minimize
>  - The correct spelling is Logic::Minimise

UK English allows both -ize and -ise endings on many verbs*; USA English
only has -ize. So picking the one that's valid in both makes more sense.

There are plenty of cases (like ‘colour’/‘color’) where UK and USA
spellings are disjoint and you just have to pick one which will be
‘wrong’ somewhere, but this isn't one of those cases.

Smylers

* I believe -ize was the original UK form, in use at the point when the
  USA forked English. The UK later took on -ise as an alternative,
  influenced by French, but the USA didn't cherry-pick that patch to
  their branch.

  Oxford dictionaries use the -ize spellings in headwords and list -ise
  as acceptable alternatives; other UK dictionaries tend to do it
  t'other way round, but all allow both.
  http://www.oxforddictionaries.com/definition/english/minimize

-- 
http://twitter.com/Smylers2

Re: Boolean As a Top Level Name

[Lincoln A Baxter]

On Sat, 2016-09-10 at 14:46 +0200, Paul Johnson wrote:
> On Sat, Sep 10, 2016 at 05:58:35AM +0200, Aristotle Pagaltzis wrote:
> > * John M. Gamble  [2016-09-09 22:12]:
> > > Technically it's math, but I suspect people would be more likely
> to use
> > > the keyword 'boolean', or perhaps 'digital logic', when looking
> for
> > > something like this.
> > >
> > > (For supporting evidence, the Wikipedia article on the Quine-
> McCluskey
> > > algorithm nowhere uses 'math' in the current version of the
> article.)
> > 
> > But “mathematical” is the first non-stop-word besides “truth table”
> in
> > the Wikipedia entry for “truth table”.
> > 
> > As for Boolean::Minimizer, I wouldn’t have the foggiest clue what
> that
> > module might be about from the name of it. Even after your
> explanation,
> > the foggiest clue is as much as I got. So I can’t really suggest
> better.
> > I vaguely suspect it’ll turn to be something best put in Data::,
> but who
> > knows.
> 
> I suppose there's a problem here in that without being aware of the
> problem being solved then no module name is going to be helpful.
> 
> If I have understood correctly then Boolean::Minimizer would use
> Algorithm::QuineMcCluskey, or the non-existent Algorithm::Espresso,
> for
> example, to do the actual minimisation.  I don't think
> Boolean::Minimizer is a bad name but, for what its worth, here are my
> naming suggestions:
> 
>  - I would take the R off the end, to have Boolean::Minimize
>  - The Logic namespace looks like a mess, but I think this module
> would
>    fit better in there: Logic::Minimize
>  - The correct spelling is Logic::Minimise
> 
> They are in order of preference, but I'd recommend the first two.

Having followed this discussion (more or less, I have no clue what the
MiuneMcCluskey alorithm is), but I like Logic::Minimise

Lincoln

Re: Boolean As a Top Level Name

[Paul Johnson]

On Sat, Sep 10, 2016 at 05:58:35AM +0200, Aristotle Pagaltzis wrote:
> * John M. Gamble  [2016-09-09 22:12]:
> > Technically it's math, but I suspect people would be more likely to use
> > the keyword 'boolean', or perhaps 'digital logic', when looking for
> > something like this.
> >
> > (For supporting evidence, the Wikipedia article on the Quine-McCluskey
> > algorithm nowhere uses 'math' in the current version of the article.)
> 
> But “mathematical” is the first non-stop-word besides “truth table” in
> the Wikipedia entry for “truth table”.
> 
> As for Boolean::Minimizer, I wouldn’t have the foggiest clue what that
> module might be about from the name of it. Even after your explanation,
> the foggiest clue is as much as I got. So I can’t really suggest better.
> I vaguely suspect it’ll turn to be something best put in Data::, but who
> knows.

I suppose there's a problem here in that without being aware of the
problem being solved then no module name is going to be helpful.

If I have understood correctly then Boolean::Minimizer would use
Algorithm::QuineMcCluskey, or the non-existent Algorithm::Espresso, for
example, to do the actual minimisation.  I don't think
Boolean::Minimizer is a bad name but, for what its worth, here are my
naming suggestions:

 - I would take the R off the end, to have Boolean::Minimize
 - The Logic namespace looks like a mess, but I think this module would
   fit better in there: Logic::Minimize
 - The correct spelling is Logic::Minimise

They are in order of preference, but I'd recommend the first two.

-- 
Paul Johnson - p...@pjcj.net
http://www.pjcj.net

Re: Boolean As a Top Level Name

[Aristotle Pagaltzis]

* John M. Gamble  [2016-09-09 22:12]:
> Technically it's math, but I suspect people would be more likely to use
> the keyword 'boolean', or perhaps 'digital logic', when looking for
> something like this.
>
> (For supporting evidence, the Wikipedia article on the Quine-McCluskey
> algorithm nowhere uses 'math' in the current version of the article.)

But “mathematical” is the first non-stop-word besides “truth table” in
the Wikipedia entry for “truth table”.

As for Boolean::Minimizer, I wouldn’t have the foggiest clue what that
module might be about from the name of it. Even after your explanation,
the foggiest clue is as much as I got. So I can’t really suggest better.
I vaguely suspect it’ll turn to be something best put in Data::, but who
knows.

To backtrack a bit here though – are these supposed to be in different
distributions? Sounds like Algorithm::QuineMcCluskey would be separate
but the others would ship together. If so, then one should probably be
a sub-namespace of the other.

Regards,
-- 
Aristotle Pagaltzis // 

Re: Boolean As a Top Level Name

[John M. Gamble]

Ah, no, sorry, I clearly didn't explain this well. A Boolean truth table
is not a matrix, and does not evaluate a Boolean expression (if anything,
it's the reverse. It takes the evaluations and re-creates the expression.
This gets complicated as the number of variables grows).

Technically it's math, but I suspect people would be more likely to use
the keyword 'boolean', or perhaps 'digital logic', when looking for
something like this.

(For supporting evidence, the Wikipedia article on the Quine-McCluskey
algorithm nowhere uses 'math' in the current version of the article.)

Thanks,
 -john


On Fri, September 9, 2016 2:50 pm, Karen Etheridge wrote:
> I think I'd look for such a module in the Math:: namespace.
>
> I also found these modules which may be similar:  Math::BooleanEval,
> Math::MatrixBool.
>
> On Fri, Sep 9, 2016 at 12:33 PM, John M. Gamble <jgam...@ripco.com> wrote:
>
>> A while back I was granted co-maintenance of Algorithm::QuineMcCluskey.
>> It
>> handles one Boolean expression at a time, and I decided that it would be
>> good to create a package that could manipulate a Boolean truth table.
>>
>> So Boolean::TruthTable is nearly ready to go (I have documentation to
>> complete).
>>
>> But, to handle the columns in the table, I created a base class.
>> Algorithm::QuineMcCluskey would become a child of this class (because
>> after all this is done, I'm going to explore other algorithms).
>>
>> Naming this class is a little trickier. It's not an algorithm, so I
>> don't
>> think using the Algorithm top level is appropriate. I'm settling on
>> Boolean::Minimizer (which is what the algorithms do).
>>
>> Now the potential problem is that Boolean isn't used much as a top-level
>> name. I can only find 'boolean', the pragma for using true and false
>> values, and Boolean-String, which has a 0.01 release and hasn't been
>> updated since.
>>
>> So are there any objections to my using Boolean as a top level name in
>> earnest?
>>
>>  -john
>>
>>
>

Re: Boolean As a Top Level Name

[Karen Etheridge]

I think I'd look for such a module in the Math:: namespace.

I also found these modules which may be similar:  Math::BooleanEval,
Math::MatrixBool.

On Fri, Sep 9, 2016 at 12:33 PM, John M. Gamble <jgam...@ripco.com> wrote:

> A while back I was granted co-maintenance of Algorithm::QuineMcCluskey. It
> handles one Boolean expression at a time, and I decided that it would be
> good to create a package that could manipulate a Boolean truth table.
>
> So Boolean::TruthTable is nearly ready to go (I have documentation to
> complete).
>
> But, to handle the columns in the table, I created a base class.
> Algorithm::QuineMcCluskey would become a child of this class (because
> after all this is done, I'm going to explore other algorithms).
>
> Naming this class is a little trickier. It's not an algorithm, so I don't
> think using the Algorithm top level is appropriate. I'm settling on
> Boolean::Minimizer (which is what the algorithms do).
>
> Now the potential problem is that Boolean isn't used much as a top-level
> name. I can only find 'boolean', the pragma for using true and false
> values, and Boolean-String, which has a 0.01 release and hasn't been
> updated since.
>
> So are there any objections to my using Boolean as a top level name in
> earnest?
>
>  -john
>
>

Boolean As a Top Level Name

[John M. Gamble]

A while back I was granted co-maintenance of Algorithm::QuineMcCluskey. It
handles one Boolean expression at a time, and I decided that it would be
good to create a package that could manipulate a Boolean truth table.

So Boolean::TruthTable is nearly ready to go (I have documentation to
complete).

But, to handle the columns in the table, I created a base class.
Algorithm::QuineMcCluskey would become a child of this class (because
after all this is done, I'm going to explore other algorithms).

Naming this class is a little trickier. It's not an algorithm, so I don't
think using the Algorithm top level is appropriate. I'm settling on
Boolean::Minimizer (which is what the algorithms do).

Now the potential problem is that Boolean isn't used much as a top-level
name. I can only find 'boolean', the pragma for using true and false
values, and Boolean-String, which has a 0.01 release and hasn't been
updated since.

So are there any objections to my using Boolean as a top level name in
earnest?

 -john