RE: [boost] discrete_set class

From: Victor A. Wagner, Jr. (vawjr_at_[hidden])
Date: 2002-08-28 11:33:05

Don't feel defensive, tho I think all the C junkies around here never 
actually  USED a language w/ an "abstract" (well as abstract as you can get 
it given that computers have to actually represent stuff w/ actual 
patterns) set, and seem to think that "enum" is "just some way to name 
constants conveniently".  It is complaints from this sector that are 
causing the problem.  I have FAR more problems concerning "any possible 
subset" of a fixed domain than they'll EVER have of "an ordered collection 
(they call it set in STL) of an arbitrarily large collection of 
things".  And if I DID have a solution to such a problem, I sure as heck 
wouldn't call it "set".

At Tuesday 2002/08/27 12:39, you wrote:
>I'm sorry.  Friends tell me my correspondence always sounds defensive, 
>though I
>rarely take offense and I welcome constructive criticism.  I'm just trying to
>get a handle on what you are saying.  You obviously have a better 
>background in
>this area than I.  I took mostly Calculus in college, with some courses in 
>such
>things as Discrete Logic and First Order Predicate Calculus.
>
>Actually, my set is stored internally the same way Pascal's set is usually
>stored (for better or worse).
>
>I get the impression that you think the class requires a "small" set of
>elements, such as maybe the number of bits in a machine word (if I'm 
>wrong, skip
>over my blather).  This is not the case.  You are only limited by memory 
>and the
>limits of the int type (2^31 - 1 elements possible on a 32-bit machine).
>
>I also get the impression that you think adding iterators to the class (a
>project for later) would be ill-advised.  I would love to hear you 
>thoughts on this.
>
>Thanks,
>
>Rich Herrick
>
> > Rich,
> >
> > I am not saying that you have a "bad" set. In fact, your type is a very
> > versatile and useful one. And, admittedly, the Pascal Set type was not
> > the best example, since that too is bounded...
> >
> > And, you hit the point:
> >
> >       "Neither std::set<>, no Pascal's set of, implement a "universal
> > set." "
> >
> > Exactly! But yours do, which is good. But programmers have to realize
> > that they are dealing with selections (or constraints) with regards to a
> > finite domain. And, that realization could lead to further useful
> > operations, such as (pardon the syntax bending...)
> >
> >       typedef domain<1, 9> digits;
> >
> >       constraint<digits> evenNumbers(2,4,6,8);
> >       constraint<digits> prime(2);
> >       constraint_variable<digits> n;
> >       for_each((evenNumbers & !prime) -> n)
> >               std::cout << n; // For each even number not being a
> > prime...
> >
> > There is syntax to be borrowed from the FP community, as done in other
> > Boost libraries. Such as the list comprehensions from Haskell:
> >
> >       [ exp | cond1, ..., condn]
> >
> > Or
> >
> >       n <- exp.
> >
> > As suggested elsewhere, one would need to replace the "<-" by "<" or the
> > reverse, "->", which could then alternatively be interpreted as "set
> > membership" or "generated by". I tend to view your sets as constraints
> > or generators...
> >
> > One would then have (I reverse the arrow):
> >
> >       (evenNumbers & prime) -> n
> >
> > Again, your type is not less in any aspect than the Pascal Set. Neither
> > is it less powerful than STL set for the kind of applications where
> > "small sets" are wanted, in which case the generic traversal proposed by
> > the iterator pattern might not be the preferred variant.
> >
> > I.e., I am actually defending your type against "STL comparisons", by
> > trying to lure the programmers out of the "programmers' set" mindset.
> >
> > What I could do is to detail a possible extension of your set to a
> > Finite Domain Constraint system, but that is probably totally
> > uninteresting as a development tool, and might not meet the low-level
> > efficiency demands of Boost.
> >
> > Regards,
> >
> > David
> >
> > -----Original Message-----
> > From: boost-bounces_at_[hidden]
> > [mailto:boost-bounces_at_[hidden]] On Behalf Of spamjunk_at_[hidden]
> > Sent: Tuesday, August 27, 2002 2:29 PM
> > To: boost_at_[hidden]
> > Subject: RE: [boost] discrete_set class
> >
> >
> > There is no order requirement to discrete_set, ie Set(e1, e2, e3, e4) ==
> > Set(e3, e4, e2, e1) is true.  The discrete set is just as versatile as
> > the Pascal Set.
> > Pascal's set is only allowed for ordinal (integral) types.  As with the
> > Pascal Set, mine will work correctly with int, char, enums.  You can
> > define a set of {'A'..'Z'} if you want to.  Neither std::set<>, no
> > Pascal's set of, implement a "universal set."  I cannot make a
> > std::set<int> and ask about membership of a float or some class X.  As
> > with discrete_set, std::set and the Pascal set are restricted to
> > elements in the domain it was defined for.
> >
> >
> > > Rich,
> > >
> > > Mathematically it is obviously a set (although ordered), I was more
> > > worried about programmer's conception of a set, such as the STL set
> > > (which is not an unstructured set..), Pascal's set etc. All those
> > > concepts are open, in that any element of the correct type (where type
> >
> > > is different from a simple, often short, enumeration) can be added.
> > > Thus, there is no "universal set" embedding all possible sets.
> > >
> > > Your construct does have a universal superset, and is in that case
> > > bounded (more than discrete, which holds for most (or all if you are
> > > bit-inclined) computer set concepts).
> > >
> > > Thus, your "discrete_set" type is more aligned with the "domain" and
> > > "constraint" concepts found in (Finite Domain) Constraint Programming.
> > >
> > > I do not want people to expect the common set properties from your
> > > type, since your set is more of a "selection" (or constraint, if one
> > > prefers that nomenclature) of/on a finite "domain". If programmers get
> >
> > > the right mindset, your type is an extremely valuable addition to
> > > Bosst.
> > >
> > > /David
> > >
> > > -----Original Message-----
> > > From: boost-bounces_at_[hidden]
> > > [mailto:boost-bounces_at_[hidden]] On Behalf Of
> > > spamjunk_at_[hidden]
> > > Sent: Tuesday, August 27, 2002 1:07 PM
> > > To: boost_at_[hidden]
> > > Subject: RE: [boost] discrete_set class
> > >
> > >
> > > David:
> > >
> > > Pardon my ignorance, as my degrees are not in math.  Other than a
> > > restriction on the element type, in what ways is this not a set.
> > >
> > >
> > > Regards,
> > >
> > > Rich Herrick
> > >
> > >
> > > > People are thinking about your construct as a set, which is "open"
> > > > in
> > > > its nature.
> > > >
> > > > I suggested to borrow some terms and ideas from the area of Finite
> > > > Domain Constraint-solving. That proposal was apparently ignored, due
> >
> > > > to the introduction of unknowns and overall whimsical appearance ;-)
> > > >
> > > > I think that using terms like "domain" or "finite_domain" with the
> > > > semantics from Constraint solving would clarify that this construct,
> >
> > > > although being extremely useful, is not a regular "set".
> > > >
> > > > /David
> > > >
> > > > -----Original Message-----
> > > > From: boost-bounces_at_[hidden]
> > > > [mailto:boost-bounces_at_[hidden]] On Behalf Of
> > > > spamjunk_at_[hidden]
> > > > Sent: Tuesday, August 27, 2002 8:47 AM
> > > > To: boost_at_[hidden]
> > > > Subject: RE: [boost] discrete_set class
> > > >
> > > >
> > > > Ok, this is my fault.  As Joel has pointed out, I neglected to
> > > > provide
> > >
> > > > documentation.  I apologize and will upload some as soon as I can.
> > > > For now, the problem with your examples is the class expects the
> > > > values of the elements to be in the range [LO, HI].  You are trying
> > to
> > >
> > > > use values outside the range.  My understanding of C++ is that it is
> > > > undefined behavior to convert an int to an enum when it is outside
> > the
> > >
> > > > enum's range.
> > > >
> > > > pop-server.stny.rr.com
> > > >
> > > > _______________________________________________
> > > > Unsubscribe & other changes:
> > > > http://lists.boost.org/mailman/listinfo.cgi/boost
> > > >
> > > > _______________________________________________
> > > > Unsubscribe & other changes:
> > > > http://lists.boost.org/mailman/listinfo.cgi/boost
> > >
> > > pop-server.stny.rr.com
> > >
> > > _______________________________________________
> > > Unsubscribe & other changes:
> > > http://lists.boost.org/mailman/listinfo.cgi/boost
> > >
> > > _______________________________________________
> > > Unsubscribe & other changes:
> > > http://lists.boost.org/mailman/listinfo.cgi/boost
> >
> > pop-server.stny.rr.com
> >
> > _______________________________________________
> > Unsubscribe & other changes:
> > http://lists.boost.org/mailman/listinfo.cgi/boost
> >
> > _______________________________________________
> > Unsubscribe & other changes: 
> http://lists.boost.org/mailman/listinfo.cgi/boost
>
>pop-server.stny.rr.com
>
>_______________________________________________
>Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Victor A. Wagner Jr.      http://rudbek.com
PGP RSA fingerprint = 4D20 EBF6 0101 B069 3817 8DBF C846 E47A
PGP D-H fingerprint = 98BC 65E3 1A19 43EC 3908 65B9 F755 E6F4 63BB 9D93
The five most dangerous words in the English language:
               "There oughta be a law"