NDim-slicing

Norbert Nemec Norbert_member at pathlink.com
Fri Mar 10 07:30:23 PST 2006


Hi there,

after two years of silence, I just found a little time to return my thoughts to
D and the issues of NDim-arrays I started back then. (No, I never completely
forgot about D, I just had other things that I had to give priority.)

My design proposal for NDim arrays needs a complete overhaul before discussion
of details makes sense. However, there is one cucial issue that needs to be
solved and I have no idea how it could be done:

Currently we have OpIndex and OpIndexAssign fit for overloading multidimensional
indexing. OpSlice and OpSliceAssign, however, work only for one dimension. I've
been thinking how to generalize these, but it turns out to be extremely tricky.
First though is: Why not simply extend OpSlice to take N pairs of boundaries?
But then, what about mixed expressions like 'a[1,4..7]' ?

Working with Python, I use expressions like that all the time, and I think it is
crucial that Ndim-arrays in D allow this kind of slicing as well. For native
Ndim arrays, it should be straightforward to handle such expressions in the
compiler. However, how should they be overloaded?!?

Python goes the way of taking a tuple of objects as indices where '4..7' would
then be translated into a "slice object". The indexing-overloading routine then
goes through all the objects at run-time and decides whether each one is a
slicing or an indexing operation. All of this is rather simple with dynamic
typing and accepting the run-time overhead.

In D, this is not an option. Indexing/Slicing has to be type-safe and the
resulting type has to be known at compile time.

One rather clumsy solution that I came up so far is to split the resolve the
expression into two consecutive function calls:
a[1,4..7]
would become
a.OpIndexPartial(0,1).OpSlice(4,7)
where the first function is defined as
OpIndexPartial(int dim,int idx)
and returns an array one rank lower.

The assignment expression:
a[1,4..7] = b[0..3]
would turn into
a.OpIndexPartial(0,1).OpSliceAssign(b[0..3],4,7)

The ugly thing about this solution is, that some kind of marshal-object is
needed which is returned from OpIndexAssign.


Another possibility would be to change
OpSlice(size_t start, size_t end)
into
OpIndex(size_t[2] slc)
and interpret a complex expression like
a[1,3..5,2,6..3]
as a call to
OpIndex(size_t idx0, size_t[2] slc1, size_t idx2, size_t[2] slc3)
I don't know, however, whether D templates would allow to implement the long
list of routines in some comfortable way.

All the really clean solution that I could think of would demand for tuple-types
and list-handling at compile time, both things that have been discussed before
but are at best a topic for the very far future.

Any ideas?





More information about the Digitalmars-d mailing list