Hi Claude,
Thank you for the detailed reply :-) A few comments below.
On 2024/04/30 06:29:38 Claude Warren wrote:
> I will see if I can clarify the javadocs and make things clearer.
>
> What I think I specifically heard is:
>
> - Be clear that producers are fast fail iterators with predicate tests.
> - Rename CellConsumer to CellPredicate (?)
Agreed (as suggested by Albert)
> - The semantic nomenclature:
> - Bitmaps are arrays of bits not a BitMap object.
> - Indexes are ints and not an instance of a Collection object.
> - Cells are pairs of ints representing an index and a value. They
> are not Pair<> objects.
> - Producers iterate over collections of the object (Bitmap, Index,
> Cell) applying a predicate to do work and stop the iteration early if
> necessary. They are carriers/transporters of Bloom filter enabled bits.
> They allow us to query the contents of the Bloom filter in an
> implementation agnostic way.
As you say naming is hard. The above is a great example and a good exercise
I've gone through at work and in other FOSS projects: "Producers iterate over
collections of the object...". In general when I see or write a Javadoc of the
form "Foo bars" or "Runners walk" or "Walkers run", you get the idea ;-) I know
that either the class (or method) name is bad or the Javadoc/documentation is
bad; not _wrong_, just bad in the sense that it's confusing (to me).
I am not advocating for a specific change ATM but I want to discuss the option
because it is possible the current name is not as good as it could be. It could
end up as an acceptable compromise if we cannot use more Java friendly terms
though.
Whenever I see a class that implements a "forEach"-kind of method, I think
"Iterable".
Note the difference with "Iterator", and I had to lookup the difference since
the former implements "forEach" and the later "forEachRemaining"! "Iterable"
is also a factory of "Iterator"s.
Should the Producers ever be implementations of Iterable or Iterator? Right
now, the answer is no because of the short-circuit aspect of using a predicate.
I'm not using the term fail-fast here because I don't think of the iteration
being in error (please tell me if I'm wrong).
If not iterable, then we should not use that name as part of the class name.
Generally, the short-circuit aspect of Producers do not make a bad candidates
for implementations of Iterable since it can throw (unchecked) exceptions.
Different for call sites granted, but I'm just mentioning it for fun.
So maybe there's nothing to do. I just want to be clear about it. For example,
I think of "factory" and "producer" as synonyms but in this case, this is not a
traditional application of the factory pattern.
As an aside I can see that Producers would not be Streams out of the box
because Stream#filter(Predicate) filters but does not short-circuit iteration.
While Stream#findAny() and #findFirst() don't fit the short-circuit bill, we
could implement a #findLast() in a Stream implementation. What I do not know is
if Streams otherwise fit the bill of Bloom filters.
>
> Does that basically cover the confusion? If there are better terms, let's
> hash them out now before I update the javadocs.
>
> As an aside, Cells and Bitmaps are referenced in the literature. For the
> most part the rest is made up out of whole cloth. So we could change
> "Producer" to something else but we would need a good name.
We have a class called BitMap and methods that use "BitMap" in the same but I
think I am more comfortable with the term reuse now.
The question that remains is must it be public? Since the Javadoc mentions it
is about indices and bit positions, could all these methods be moved to the
package-private IndexUtils? My concern is to reduce the public and protected
API surface we will have to support and keep for the lifetime of the 4.x code
base.
>
> Semantically:
>
> - As Hasher generates an IndexProducer once it knows what the range of
> the values are and how many values it should produce (as defined in the
> Shape). That index producer can be used multiple times and will produce
> the same set of values in the same order.
> - A Bloom filter generates an IndexProducer that enumerates the enabled
> bits in the filter.
> - A CellProducer generates an IndexProducer that reports all the index
> values that it contains.
>
> In implementing stable Bloom filters I had to create a RandomHasher that
> generates an IndexProducer that will generate values in the range and
> number specified by the Shape but that does not produce the same values
> every time (obviously).
>
> We could change Producer to a term that means a representation: Ideogram,
> but then we have to introduce the term and explain what it means. Producer
> starts at a common point.
>
> All of this just goes to show that "Naming things is hard". But then we
> all knew that anyway.
> Claude
Thank you Claude! :-)
Gary
>
>
>
>
> On Sun, Apr 28, 2024 at 11:00 PM Gary Gregory <garydgreg...@gmail.com>
> wrote:
>
> > Thank you for your thoughtful reply. See my comments below.
> >
> > On Sun, Apr 28, 2024 at 11:10 AM Alex Herbert <alex.d.herb...@gmail.com>
> > wrote:
> > >
> > > Hi Gary,
> > >
> > > I am in favour of using nomenclature and patterns that will be familiar
> > to
> > > a Java developer. But only if they match the familiar JDK use patterns.
> > The
> > > Bloom filter package has some atypical use patterns that have driven the
> > > current API to where it is. I'll try and describe these below.
> > >
> > > On Sun, 28 Apr 2024 at 14:16, Gary Gregory <garydgreg...@gmail.com>
> > wrote:
> > >
> > > > Hi Clause, Albert, and all,
> > > >
> > > > Since the introduction of lambdas in Java 8, Java has a well-defined
> > > > terminology around the classic producer-consumer paradigm but (for
> > > > reasons unknown to me) realized in the functional interfaces *Supplier
> > > > and *Consumer. In addition, as of Java 5, we have the Iterable
> > > > interface.
> > > >
> > > > In our new Bloom filter package we have new interfaces called
> > > > *Producer (as opposed to *Supplier), where some of these new
> > > > interfaces are formally annotated with @FunctionalInterface and some
> > > > not (for example, BloomFilterProducer).
> > > >
> > > > My question is: Why call these "Producers" instead of "Suppliers"? Is
> > > > the formal Bloom filter literature tied to the "Producer" terminology
> > > > in a way that would make adapting to the Java term confusing? I know I
> > > > brought up a similar topic recently, but I would like to revisit it
> > > > now that I've started to read Claude's blog drafts. Even without
> > > > making the current "Producers" formal suppliers by extending Supplier,
> > > > would it be worth using the Java terminology?
> > > >
> > >
> > > Claude is familiar with the literature and can comment on that. I would
> > > defer to the literature if it is a common term.
> > >
> > > There is one notable distinction to JDK suppliers. Suppliers only supply
> > 1
> > > element and must be repeatedly called to generate more. The Producers in
> > > the BloomFilter package will supply multiple values. They are invoked
> > using
> > > a forEach pattern with the intention of supplying all the elements to a
> > > predicate, not a consumer. If any of those elements is rejected by the
> > > predicate then the rest of the elements are not supplied. So this is a
> > > fail-fast bulk supplier.
> >
> > Ah, this sounds like a special Iterator, fail-fast as you mention, and
> > Java does not have that in Java 8 at least.
> > The Producer class suffix still confuses me since this is neither a
> > factory nor a traditional supplier. If the classes were called
> > *Iterator and not extend iterator, then it would also be confusing.
> > The question is whether it would be useful to extend Iterator or if
> > the class would never be used as a traditional Iterator. I'll that to
> > an SME ;-)
> >
> > >
> > >
> > > >
> > > > My second observation is that some might neither be "Producers" or
> > > > "Suppliers" but instead be extensions of Iterable. For example,
> > > > BitMapProducer is not a factory for instances of BitMap; the BitMap
> > > > does not appear in the signatures of BitMapProducer methods. From a
> > > > strict Java POV, this is (slightly) perplexing.
> > > >
> > >
> > > Iterable was suggested in an earlier API, particular for the
> > IndexProducer.
> > > IIRC it was rejected on the basis of simplifying the code for the caller
> > in
> > > the fail-fast case. Otherwise every user of the iterator must implement
> > > fail-fast loops over the elements. There may have been other reasons so
> > it
> > > could be worth a check in the mailing list archives. It would require
> > going
> > > back a few years but it was discussed on the dev list.
> > >
> > > The term BitMap refers to a long that holds 64-consecutive indices as
> > > either present or absent. You can consider the sequential bitmaps
> > > containing all indices from [0, n) as the serialized state of a Bloom
> > > filter with n bits. This is essentially a BitSet as you can see from the
> > > SimpleBloomFilter implementation. This originally wrapped a BitSet; it
> > was
> > > converted to directly implement the required read/write bit functionality
> > > on the grounds of performance (no memory reallocation; no index checks).
> > >
> > > We do not have a BitMap class since we use a long primitive.
> >
> > Yes, we do; it's right here:
> > org.apache.commons.collections4.bloomfilter.BitMap
> >
> > This makes it hard for a non-expert to groke IMO. If we use terms in
> > class names and discussions that are... what? Mismatched or misnamed.
> >
> > A rename would
> > > be to LongProducer causing a name clash with the JDK. Renaming to
> > something
> > > else is possible but I believe BitMap is a term from the literature.
> > >
> > >
> > > >
> > > > Instead (forgetting the class name issue for now), we could have:
> > > >
> > > > @FunctionalInterface
> > > > public interface BitMapProducer extends Iterable<LongPredicate> {...}
> > > >
> > > > Which would let implementations define:
> > > >
> > > > Iterator<LongPredicate> iterator();
> > > >
> > > > Instead of:
> > > >
> > > > boolean forEachBitMap(LongPredicate predicate);
> > > >
> > >
> > > The BitMapProducer is not iterating LongPredicates. It is iterating longs
> > > to be accepted by a single LongPredicate. The boolean return allows
> > > signalling to stop the forEach loop. There is no primitive specialisation
> > > of Iterator for long. There is a Spliterator.OfLong but that bundles some
> > > other API that we do not wish to support, namely parallel streaming via
> > > split and the ability to advance element by element (tryAdvance).
> > Currently
> > > we only implement the equivalent of the forEachRemaining pattern from
> > > Spliterator. That accepts a consumer and so fail-fast would be done via
> > > raising a runtime exception. Given that fail-fast is a key feature of a
> > > Bloom filter then we do not want this to be implemented via exceptions.
> > >
> > > The primary use case for fail-fast is to stop as soon as a bit index is
> > > found, or not found (case dependent). Consider a Bloom filter that has 20
> > > indices per hashed item. You have populated the filter with items, each
> > has
> > > 20 random indices. You then check if a new item is not contained in the
> > > filter by creating indices for the new item with your hash function and
> > > checking each index against those already in the filter. If your new
> > > element has an index not in the filter, then you have not seen this
> > element
> > > before. This process can be done by creating all the indices by hashing
> > as
> > > the first step, then comparing each to the filter. Or you can generate
> > > indices lazily, only creating the next index if the current one is
> > present
> > > in the filter. This requires fail-fast index iteration and dynamic index
> > > generation by the hasher. You can walk through this looking at
> > > the EnhancedDoubleHasher. This is what takes a byte[] (capturing
> > > information on the item) and creates indices. But it only creates indices
> > > until it is triggered to stop.
> > >
> > > Note that the filter can only tell you with 100% confidence that an item
> > > has not been observed. It cannot tell you with 100% confidence it has
> > been
> > > observed, as the random indices created by hashing the item may all be
> > > present in the collective indices from all items added to the filter. The
> > > Shape class has the standard computations to create a filter with enough
> > > bits to control the false-positive rate for the expected number of items
> > > you wish to store.
> >
> > OK, it is now clear that this is a fail-fast (or breakable, or some
> > term) iterator. I'd would like to see the Javadoc clearer for those
> > classes and forEach* methods. What about something like: "The first
> > predicate that returns false causes the iteration to stop."?
> >
> > >
> > >
> > > >
> > > > Same comment for IndexProducer.
> > > > Same comment for BloomFilterProducer.
> > > > Is this too much Java-ness?
> > > >
> > > > CellConsumer looks like a Predicate, not a traditional Java *Consumer.
> > > > We have a specialization called LongBiPredicate so I propose we rename
> > > > and extract CellConsumer as IntBiPredicate.
> > > >
> > >
> > > Cell is a term from the literature. A cell is an index and a count. So
> > > although you are accepting two int values, they are actually only one
> > cell.
> > > A rename to CellPredicate would be more appropriate to imitate
> > > Predicate<Cell> where the Cell is a pair of int primitives.
> >
> > I agree that reusing the predicate term works here.
> >
> > >
> > > In contrast the LongBiPredicate is used to accept two BitMaps that have
> > > been paired by iterating over two filters with the same shape. This is
> > not
> > > an extensible design as you can only iterate over a pair of filters, and
> > > not n filters of the same shape. The use case is in standard set
> > operations
> > > such as union and intersect which are used to generate metrics used in
> > the
> > > literature (see the SetOperations class). This could be renamed to
> > > BitMapBiPredicate. However I think the current name was chosen to be in
> > > keeping with the JDK j.u.function package.
> >
> > And that's a good thing :)
> > >
> > > Hope that helps set some background.
> >
> > Absolutely and thank you. I hope you or Clause will take the time to
> > clarify the Javadoc here and there for non-SMEs! :-) See my suggestion
> > above.
> >
> > Gary
> >
> > >
> > > Alex
> > >
> > >
> > >
> > > >
> > > > TY!
> > > > Gary
> > > >
> > > > ---------------------------------------------------------------------
> > > > To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
> > > > For additional commands, e-mail: dev-h...@commons.apache.org
> > > >
> > > >
> >
> > ---------------------------------------------------------------------
> > To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
> > For additional commands, e-mail: dev-h...@commons.apache.org
> >
> >
>
> --
> LinkedIn: http://www.linkedin.com/in/claudewarren
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
