contiguous ranges

[Vlad Levenfeld via Digitalmars-d]

I feel the bigger picture is being missed amid the focus on 
blitting.

On Thursday, 19 February 2015 at 11:20:13 UTC, Guillaume Chatelet 
wrote:
> From this discussion I understand you mainly want to be able to 
> BitBlt ranges

BitBlit is useful, yes, but not the main point. Interfacing with 
C APIs and supporting in-place transformations is also important.

On Thursday, 19 February 2015 at 19:32:26 UTC, Andrei 
Alexandrescu wrote:
> I don't see a need for contiguous ranges if the only embodiment 
> is T[]. -- Andrei

Agreed. I don't think that defining contiguous ranges as 
implicitly convertible to T[] is useful - in this case, you could 
just write functions to take a T[], and forget the original range 
type entirely. For a range concept to be useful for generic 
programming, it needs to enable templates to lift algorithms to 
the argument type's category. Instead, lowering a range to T[] 
loses the capabilities and constraints defined in the original 
range and obviates the need for the category in the first place.

On Friday, 20 February 2015 at 01:25:34 UTC, deadalnix wrote:
> Isn't it what a slice is already ?

Yes. A slice is the simplest realization of a contiguous range. I 
argue that it is useful to have structures which have slice-like 
behavior without actually being slices.

On Friday, 20 February 2015 at 08:20:50 UTC, Ola Fosheim Grøstad 
wrote:
> So that you can assess whether "a pointer" (iterator) is in a 
> range on or not at O(1)?

Hadn't thought of that, it could be useful.

On Friday, 20 February 2015 at 08:22:38 UTC, John Colvin wrote:
> I don't see anything here that isn't already covered by 
> built-in slices, opSlice, opSliceAssign and put.

opSlice.* and put are defined in the data structure, whereas 
range concepts inform the algorithm.

//////////////////////////

I claim that the practical benefit of range concepts as type 
predicates is:
   1) to make overloading logic more succinct and uniform.
   2) to concentrate implementation decisions in the appropriate 
abstraction layer.
both of which serve to make generic code more robust, expressive 
and efficient.

Sometimes you want something like a slice (in that it guarantees 
contiguous memory layout) but with additional capabilities and 
constraints which you would like to have preserved under certain 
transformations. This can be encapsulated in a contiguous range 
concept.

Let me illustrate with an example:

   struct AudioClip {
     float[2][] samples;
     uint sampling_rate;
     this (string path) {load (path, samples);}
     void play () {some_C_audio_lib_call (samples.ptr, 
samples.length, sampling_rate);}
   }

   // we'll start with an audio clip with contiguous layout in 
memory
   auto ac = AudioClip ("90 minutes of screaming cats.flac");

   // now we define two implementations of the same filter
   auto ref declaw_filter1 (R)(R r) if (isContiguousRange!R) {
     // pattern match to get the size of the sample
     static if (is (ElementType!R == float[stride], uint stride)) 
{}

     // i know the gsl functions don't work like this, just bear 
with me
     gsl_fft (ptr, stride, r.length);
     gsl_fgemm (/*pretend this is sensible*/);
     gsl_fft_inverse (ptr, stride, r.length);

     return r;
   }

   auto declaw_filter2 (uint n)(float[n][] slice) {
     // like declaw_filter1 but without the contiguous stuff
   }

   // now, we can finish this one of two ways
   // the easy way:
   ac.declaw_filter1.play; // UFCS all day
   // or, if we passed a T[] made from AudioClip or defined 
AudioClip to be implicitly convertible to T[]:
   AudioClip ac2;
   ac2.samples = ac.declaw_filter2;
   ac2.sampling_rate = ac.sampling_rate; // this could 
desynchronize after the code is refactored, opening us up for bugs
   ac2.play;

THE UPSHOT:
Both variants of declaw_filter are generic - they'll operate on 
data in an arbitrary number of channels, it could be an audio 
file or voltages from a DAQ or whatever.
Variant 1 lifts the algorithm to accommodate the range, while 
variant 2 lowers the range to accommodate the algorithm.
The use of variant 2 is more verbose, error-prone, and bubbles 
implementation details up to a layer where they don't belong.
Variant 1 uses the concept of a contiguous range to keep the 
knowledge of its implementation (specifically, that it calls 
functions which expect pointers) encapsulated.

THE DOWNSIDE:
Slicing and in-place transformations are pretty much the only 
things that will preserve contiguity. Piping ac through map or 
something will take us back to manually propagating the sampling 
rate. In general, deciding how and when to preserve what 
information under which transformations is tough. Lazily mapping, 
say, to increase the volume could meaningfully preserve sampling 
rate, but under filtering, zipping or striding it doesn't make 
sense.