const debacle

[Janice Caron]

On 24/03/2008, Walter Bright <newshound1 at digitalmars.com> wrote:
> Ok, I see what you mean. But what the template gives us is:
>
>  const(T)[] f(const(T)[] t) { ... }
>  T[] f(T[] t) { ... }
>
>  whereas what Steven is asking for is:
>
>  T[] f(const(T)[] t) { ... }

I've thought this through pretty deeply in the last few hours, and it
seems to me that everyone's right, in a sense. But I do believe you
are wrong in one aspect, which is that the concept is /not/
fundamentally broken, and I believe I can prove it.

First off, nobody is asking for

    T[] f(const(T)[] t) { ... }

That really would be fundamentally broken, as you say. In fact, lets
be explicit here - we want to return a slice of the original, so let's
write it as

    T[] f(T)(const(T)[] a) { return a[X..Y]; }

Broken, as you say, but *it's still not what's being asked for*.
What's being asked for is

    K(T)[] f(T)(const(T)[] a) { return cast(K(T)[]) a[X..Y]; }

where K is the constancy of a at the caller site. I claim that I can
prove that this is not fundamentally broken, and specifically that it
does not violate const correctness.

As the first step of the proof, let us rewrite the function to return
a pair of indeces. I don't think D can return multiple values yet, so
we'll assume the existence of a Slice struct:

    struct Indeces
    {
        uint begin;
        uint end;
    }

So now we rewrite the function as

    Indeces f(T)(const(T)[] a) { return Indeces(X,Y); }

Hopefully, you can clearly see that nothing is amiss here. The
function gets a read-only view of a, and does not modify it. All is
well. What it returns is two integers. Next, at the call-site, the
caller does:

    char[] a,b;
    Indeces t;

    t = f(a);
    b = a[t.begin..t.end];

This does exactly what is required, and again, I hope you'll agree
that const correctness has not been violated. Now recall Stephen's
example code from earlier:

    auto tmp = f(t);
    g(tmp);

Observe that I can now easily rewrite this as:

    auto tmp = f(t);
    g(t[tmp.begin..tmp.end]);

And again, no const correctness has been violated.

The reason that everything works is that "const" means "I have a
read-only view". In particular, the function f has a read-only view of
the array a - however, the /caller/ has a read/write view of that
array. It follows logically that the caller (who has a read/write
view) is always going to be able to modify the array through that
read/write view, even though the callee (who only has a read-only
view) cannot.

With that understanding, it follows that it /must/ be safe to pass a
read/write view of a slice of an array to someone *who already has* a
read-write view of the whole array.

QED

Now, with all that said, returning indeces is simpler and cleaner than
having to generate three versions of the function, so I believe that
returning indeces is the way to go.

We are told that in the future, D will have macros. When that day
comes, Stephen will be able to create his desired signature as a macro
instead of a function (because the slicing happens at the call-site,
not within the function body).

So I would like to suggest that the struct Indeces be added to the
standard library. (It's just too simple to expect functions to have to
reinvent the wheel over and over again.) Then everybody wins.