RE: [boost] discrete_set class

From: David Bergman (davidb_at_[hidden])
Date: 2002-08-28 13:07:40

Victor,

I hope you were not including me in that crowd of "all-too-concrete" C
junkies... I am as abstract as they come.

I just know that your "C junkies" expect certain behavior from what they
call sets. I wish people would  be more interested in abstracts instead
of "neat language tricks". But, unfortunately, the attractive power of
certain C++ constructs, such as templates, sometimes lead to clever
tricks instead of proper abstraction.

And, yes, the STL set is definitely more than a set with its "implicit"
order. Unfortunately.

/David

-----Original Message-----
From: boost-bounces_at_[hidden]
[mailto:boost-bounces_at_[hidden]] On Behalf Of Victor A. Wagner,
Jr.
Sent: Wednesday, August 28, 2002 12:33 PM
To: boost_at_[hidden]
Subject: RE: [boost] discrete_set class

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"

_______________________________________________
Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost