Non-pipeline component programming

[H. S. Teoh via Digitalmars-d]

Sorry for the very late reply; my internet connection was down for 2
weeks and only came back yesterday.


On Thu, Sep 04, 2014 at 08:03:51AM +0000, David Ledez via Digitalmars-d wrote:
> Dear T,
> 
> I've read with a great attention your reply regarding ECS and OOP. You
> mention that you work on high-dimensional polytope and a data
> structure able to support fast topological query with compact storage.
> I would be very interested in having a look to your data structure. Do
> you have any document about your design and the concepts? Any github?

I'm sorry to disappoint, but I was merely alluding to the fact that
separating the range-based interface from the container allows one to
freely choose the most suitable structure to represent the polytope,
while using a proxy type to expose a range interface to allow generic
algorithms to work with it. My code is currently still very much a work
in progress, and I don't really have very much to show for it yet.

The basic design, however, is along these lines:

- A Polytope interface representing any abstract polytope-like structure
  in the program (see below for details);

- A ConcretePolytope class (implementing a Polytope) that stores a face
  lattice, represented as a graph, the nodes of which are obtained by
  running a convex hull + lattice enumeration algorithm on the source
  data.

- The Polytope interface has abstract methods for enumerating
  sub-polytopes (as input/forward ranges), which concrete classes like
  ConcretePolytope implement; the idea being that a face of a Polytope
  is also a Polytope, and while the underlying implementation may be
  different (e.g., the range of Polytopes representing the
  (n-1)-dimensional facets may have a different representation from,
  say, the 1-dimensional edges), they implement the same interface so
  generic algorithms can work with them without special-casing. This is,
  of course, just plain old OO, except perhaps for the range API part.

  The sub-polytope enumeration methods return proxy types that implement
  the range API, with Polytope as the element type, so you can use the
  usual std.algorithm / std.range tools on them -- .find, .filter,
  .chain, .cycle, .takeN, etc.. The proxy types are themselves
  interfaces, meaning that you can write a proxy Polytope implementation
  that performs some complex query over the lattice structure of
  ConcretePolytope, and still present a nice range API over its
  elements, and you can pass this to any of the usual range-based
  algorithms for searching, filtering, composing, etc., with no code
  change required in the algorithms. Again, this is just plain ole OO
  (Liskov substitution, in particular), seasoned with some D-flavored
  range-styled code. So you could, in theory ('cos I haven't actually
  implemented this part yet), construct some complex query over the
  polytope, and ask the program to enumerate, say, all 5D faces subject
  to some given filter, say they must have a certain number of 3D
  subfaces. In code, it could be as simple as:

	ConcretePolytope p = ...;
  	auto query = new PolyQuery(...) // construct complex proxy Polytope from p

	// The query proxy object is still a Polytope
	assert(is(typeof(query) : Polytope));

	query.faces(5)	// get range of faces of dimension 5
	     .filter!((p) => p.faces(3).count > 10) // filter by faces with more than 10 3D faces
	     .copy((p) {
		// print a list of face ID's in the result
	 	writefln("%s", p.id);
	     });

  Notice how the second block of code can actually apply directly to
  ConcretePolytope (since it implements the Polytope interface), or to a
  PolyQuery object (which represents some subset of the
  ConcretePolytope's surface), or to anything, really, that implements
  the Polytope interface -- perhaps a specific face of a
  ConcretePolytope. Due to the range API implemented by the .faces
  method, you can then process this range downstream using all of the
  usual range-based algorithms.

Also note that by abstracting the implementation details of
ConcretePolytope away, it is also possible to implement a different kind
of concrete polytope, say one where the full face lattice isn't computed
beforehand, like I'm doing now, but which is lazily computed depending
on what kind of queries you run on it -- i.e., if you call faces(6),
then it will lazily construct the 6-dimensional faces of the polytope on
the fly as you iterate over the range, and if you iterate over, say, the
5-dimensional faces of a subset of the 6D faces, then the lattice
enumeration algorithm will only be run for those subset of faces, rather
than the entire polytope. As you probably know, the face lattice of a
general polytope can be exponential in the size of its initial
vertex/hyperplane representation, so allowing this kind of lazy
evaluation *without needing to change any downstream code* is a big
advantage.

It is also possible to implement a polytope whose faces are
mathematically-generated, allowing compact storage. For example, you
could generate it from a symmetry group, which alleviates the need to
store all vertices / hyperplanes (you can generate everything from the
vertex figures, for example). Again, none of the downstream code needs
to change; they will Just Work(tm). This isn't anything radically new,
really, it's just basic OO design, but just with a little range-based
spice added to it. :)


T

-- 
They say that "guns don't kill people, people kill people." Well I think the gun helps. If you just stood there and yelled BANG, I don't think you'd kill too many people. -- Eddie Izzard, Dressed to Kill