Interviews: Alexander Stepanov and Daniel E. Rose Answer Your Questions

[H. S. Teoh via Digitalmars-d]

On Mon, Jan 19, 2015 at 08:19:58PM +0000, NA via Digitalmars-d wrote:
> Interesting Interview.
> 
> http://interviews.slashdot.org/story/15/01/19/159242/interviews-alexander-stepanov-and-daniel-e-rose-answer-your-questions
[...]

What I found extremely interesting, was that Alexander's original vision
of iterators wasn't so much iterators, but a kind of generalized linear
coordinate, and apparently, he did also have designs for other kinds of
coordinates, like multidimensional, graph, and tree coordinates.

This gives me lots of ideas about how we might be able to generalize the
concept of ranges to non-linear traversals over data structures along
analogous lines.

A quick off-the-top-of-my-head example would be a "tree range" (not sure
what the best terminology would be) whose methods allow you to choose
one of the current node's n children. A "forward tree range" would allow
you to save a previous position on the tree, so that you can return to
an ancestor node without needing to use a stack, and a "bidirectional
tree range" would add a "toParent" method that goes back to the parent
node.

In terms of implementation, I think D's ranges are equivalent to
Alexander's original conception of linear coordinates. The problems with
C++'s iterator design is the choice of using an iterator pair to
determine the endpoint of iteration, but this seems to be an artifact of
implementation choice rather something inherent in Alexander's
conception. In particular, had C++ iterators been implemented with a
method for determining the endpoint of iteration (akin to D's .empty),
none of the well-known problems would have arisen.

The multidimensional coordinate concept is particularly interesting to
me, though, because it's not obvious how to implement it either as an
"iterator pair" using C++'s choice of implementation (there is no unique
endpoint to serve as .end()), or as a D-style range, because how would
you determine if something is empty if it can be traversed in multiple
non-parallel directions? So in this case, it would seem to make more
sense to go back to Alexander's original conception of a Coordinate that
has abstract methods for navigation. Add to that a method for
determining whether it falls within its bounding region, and you have
something that subsumes both C++ iterators and D ranges, and also
extensible to more powerful notions like multidimensional traversals,
tree traversals, and graph traversals.

Furthermore, there's also the extremely interesting topic of generic
functions that can translate between coordinate kinds. For example,
given a linear coordinate, you can "fold it up" into a multidimensional
coordinate by "wrapping it" around every n items, much like an
n-dimensional compact array is actually constructed from wrapping around
the linear memory addresses into rows or columns. Since linear
coordinates and n-dimensional coordinates are completely generic, you
can have a generic function that, given the linear coordinate to some
data structure, returns an n-dimensional coordinate that presents an
"n-dimensional view" of the underlying data -- all without requiring
manual support for multidimensional traversal from the underlying
container!

Similarly, one could implement a tree structure in a linear array by
having a suitable transformation of the array's linear coordinates into
a tree-traversal coordinate. Again, this can be done in a fully generic
way that does not require custom support from the underlying array type.

In the same vein, one could present a tree-like view of an underlying
graph object by a suitable transformation of graph coordinates into tree
coordinates corresponding to, say, a minimum-spanning tree of the graph,
or a DFS/BFS traversal of the graph, etc..

This is powerful stuff, indeed! I think it's worth our consideration for
D. D's support for generics make it the ideal playground for developing
these ideas into working, useful implementations.


T

-- 
Genius may have its limitations, but stupidity is not thus handicapped. -- Elbert Hubbard