digitalmars.D - Interviews: Alexander Stepanov and Daniel E. Rose Answer Your
- NA (3/3) Jan 19 2015 Interesting Interview.
- bearophile (10/11) Jan 19 2015 I am glad to see that the field of programming languages is far
- H. S. Teoh via Digitalmars-d (62/65) Jan 21 2015 [...]
- Vlad Levenfeld (26/28) Feb 25 2015 Stepanov's book only goes so far as to describe coordinates for
- Rikki Cattermole (6/31) Feb 25 2015 If you are able to, create a e.g. github repository with your code /
Interesting Interview. http://interviews.slashdot.org/story/15/01/19/159242/interviews-alexander-stepanov-and-daniel-e-rose-answer-your-questions NA
Jan 19 2015
"bearophile" <bearophileHUGS lycos.com> NA:http://interviews.slashdot.org/story/15/01/19/159242/interviews-alexander-stepanov-and-daniel-e-rose-answer-your-questionsI am glad to see that the field of programming languages is far from done :-) Alex>After STL was accepted into the standard in 1994, I started thinking about designing a minimal programming language that will allow even more intimate access to hardware than C/C++ and also provide support for concepts and generic programming.< Rust? :-) Bye, bearophile
Jan 19 2015
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
Jan 21 2015
On Wednesday, 21 January 2015 at 22:21:57 UTC, H. S. Teoh wrote:... TStepanov's book only goes so far as to describe coordinates for traversing a binary tree, but the extension to n-trees is pretty straightforward. Have you given any more thought to these topics? I've built a few of the solutions you mentioned over the last few months but now I'm working on putting it on more rigorous foundations. So far its come down to defining a notion of spaces (distinct from ranges though many structures are both ranges and spaces), classifying data structures by their topologies (e.g. traversal by links, by modifying a coordinate and passing it to opIndex, by incrementing and dereferencing an iterator, etc), and characterizing the various topology-transforming functors on ranges and spaces (like flattening a tree into a singly-linked-list or calling .array to transform an input range into a random-access range), but its pulling me in a lot of different directions and I'm having a hard time culling the options down. I do have a nearly complete space package that I use for general projects, but otherwise nothing too concrete yet; just pages of scribbled notes. Anyway this is the topic of my thesis (senior research project for discrete math) and, since I'm implementing it in D, it would be cool if some of the work I do can contribute to the ecosystem. If there's interest I'll keep you apprised of updates and if you're willing I'd like to pick your brain about use cases and feedback sometime.
Feb 25 2015
On 25/02/2015 9:28 p.m., Vlad Levenfeld wrote:On Wednesday, 21 January 2015 at 22:21:57 UTC, H. S. Teoh wrote:If you are able to, create a e.g. github repository with your code / notes ext. That way anyone that wants to keep updated can follow it and read the changes as they happen. After all, version control isn't just for source code ;)... TStepanov's book only goes so far as to describe coordinates for traversing a binary tree, but the extension to n-trees is pretty straightforward. Have you given any more thought to these topics? I've built a few of the solutions you mentioned over the last few months but now I'm working on putting it on more rigorous foundations. So far its come down to defining a notion of spaces (distinct from ranges though many structures are both ranges and spaces), classifying data structures by their topologies (e.g. traversal by links, by modifying a coordinate and passing it to opIndex, by incrementing and dereferencing an iterator, etc), and characterizing the various topology-transforming functors on ranges and spaces (like flattening a tree into a singly-linked-list or calling .array to transform an input range into a random-access range), but its pulling me in a lot of different directions and I'm having a hard time culling the options down. I do have a nearly complete space package that I use for general projects, but otherwise nothing too concrete yet; just pages of scribbled notes. Anyway this is the topic of my thesis (senior research project for discrete math) and, since I'm implementing it in D, it would be cool if some of the work I do can contribute to the ecosystem. If there's interest I'll keep you apprised of updates and if you're willing I'd like to pick your brain about use cases and feedback sometime.
Feb 25 2015