www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Proposal for scoped const contracts

reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
This idea has come from the discussion on the const debacle thread.

It is basically an idea for scoped const.  The main goal is so that one can 
specify that a function does not modify an argument without affecting the 
constness of the input.

The main problem to solve would be that I have a function with an argument 
that returns a subset of the argument.  The easiest function to help explain 
the problem is strchr.  Please please do NOT tell me that my design is 
fundamentally unsound because you can return a range or pair, and then slice 
the original arg based on that pair.  There are other examples that cannot 
be solved this way, this is just the easiest to explain with.  Everyone who 
uses C should know about strchr:

char *strchr(char const *source, char const *pattern);

The result of strchr is meant to be a pointer into source where pattern 
exists.

Note that this is not even close to const-correct in C, because if you pass 
in a const source, the const is inhernetly cast away.

So let's move to the D version, which I'll specify with const to begin with:

const(char)[] strchr(const(char)[] source, const(char)[] pattern);

Note that const(char)[] MUST be the return value, because otherwise we 
cannot return a slice into source.  So far so good, but now, if I am using 
strchr to search for a pattern in a mutable string, and then I want to 
MODIFY the original string, I must cast away const, because the return value 
is const.  OK, so you might say let's add an overload (or templatize 
strchr):

char[] strchr(char[] source, const(char)[] pattern);

Which compiles and works, but I cannot specify with the signature that 
source will not be modified.  Therefore, the compiler is not able to take 
advantage of optimizations, and the caller is not guaranteed his source 
array will be untouched.

So, how do we specify this?  I propose a keyword is used to specify "scoped 
const", which basically means, "this variable is const within this function, 
but reverts to it's original const-ness when returned", let's call it foo 
(as a generic name for now):

foo(char)[] strchr(foo(char)[] source, const(char)[] pattern);

Note that foo only specifies source and not pattern because we are not 
returning anything from pattern, so it can be fully const.

What does this mean?  foo(char)[] source is not modifiable within strchr, 
but is implicitly castable to the type of the argument at the call site.  So 
if we call strchr with a char[], foo(char)[] is essentially an alias to 
const(char)[] while inside strchr, but upon return is implicitly castable 
back to char[].  This does not violate any const contracts because the 
argument was mutable to begin with.  If we call strchr with a const(char)[], 
foo(char)[] cannot be implicitly cast to char[] because the call site 
version was not mutable, and implicitly removing const would violate const 
rules.  These rules can easily be checked by the compiler at the call site, 
and so the function source does not need to be available.

So why must we have a keyword specification?  Because of the expressive 
nature of const types, you must be able to match exactly where the const 
comes into play.  For example, const(char)* is different than const(char*), 
and so foo must be just as expressive.  And in addition, the type returned 
may not be exactly the parameter passed in, but the const-ness must be 
upheld.

For example, what if the argument was a class, and the return type was 
unrelated:

foo(membertype) getMember(foo(classtype ct)) { foo(membertype) return 
ct.member;}

Note that if member is a function, it must also be foo, or else the contract 
could be violated.

You should be able to declare intermediate variables of type foo(x):

foo(membertype) = ct.member;

What if there are multiple arguments, and the result may come from any of 
them:

foo(T) min(T)(foo(T) val1, foo(T) val2);

what if one calls min with a mutable, and an invariant type?  The answer is 
that foo should map to the least common denominator.  If all of the foo's 
are identical (invariant, const, or mutable), then the resulting foo would 
be identical.  If any of them differ, the resulting foo must be const to 
uphold const-correctness.

In any case, val1, and val2 are const for the body of the function.

There are other benefits.  For example, to implement a min function that 
allows a mutable return for mutable arguments, you must define min as a 
template, which can generate up to 6 variations (for all the different 
argument const types), but with the foo notation, the function generated is 
always identical.  The only check for const-correctness is at the call site.

Note that this idea is very similar to Janice's idea of:

K(T) f(const K, T)(K(T) t);

The differences are:
  - This idea does not require a different template instantiation for 
identical code, and in fact is not a template, so it does not require source 
or generate bloat.
  - This idea ensures that the argument remains const inside the function 
even if the argument at the call site is mutable.  It enforces the contract 
that the caller is making that the argument will never be modified inside 
the function.

------------------- PROPOSAL FOR KEYWORD -------------------

That is my general proposal for scoped const, and as an orthogonal 
suggestion, which should by no means take away from my above proposal, I 
suggest we use the argument keywords 'in' and 'out' to specify foo:

out(char)[] strchr(in(char)[] source, const(char)[] pattern);

So arguments are implicitly castable to 'in', no matter if they are mutable, 
const, or invariant.
'in' types are implicitly castable to 'out' types.
'in' arguments cannot be modified inside the function (i.e. they are 
essentially const, but with the additional specification that they can be 
cast to 'out').
'out' is an alias for the constness at the call site defined by the 
following rules:
    -  if all of the 'in' parameters are of one constancy, (i.e. all are 
mutable, all are invariant, or all are const), then out is defined to be the 
same constancy.
    -  if there are two different constancy values for 'in', then 'out' is 
defined to be const.
These type declarations are made at the call site, not inside the function. 
The function is compiled the same for all versions of 'in' and 'out'.

And for functions that are members of a class:

in out(T) func() {...} // essentially, in(this)
or
out(T) func() in {...}

Rationale:  I think in and out are pretty much defunct keywords in this 
context (out replaced by ref, in replaced by const), and so are fair game 
for this syntax.  They are also very good english descriptions of what I am 
trying to do.

-Steve
Mar 24 2008
next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Steven Schveighoffer" wrote in message

 This idea has come from the discussion on the const debacle thread.

 It is basically an idea for scoped const.  The main goal is so that one 
 can specify that a function does not modify an argument without affecting 
 the constness of the input.
 ...


I have thought of an additional specification that I've left out, regarding 
calling functions from within a scoped const function.

If a function with scoped const calls another function, the following rules 
apply:

 - if the second function is a scoped const function, and the parameters 
passed to the scoped const function are declared with 'in', then the 
resulting 'out' of the second function can be returned from the outer 
function, or can be assigned to another 'in' variable.
 - if the second function is not a scoped const function, or the parameters 
passed to the second function are not declared with 'in', then the result of 
the second function cannot be assigned to an 'in' variable.

For example:

out(T) g(in(T) t){...}
const(T) h(const(T) t) {...}

out(T) f(in(T) t)
{
  t = g(t); // OK, g is scoped const
  in(T) a = g(t); // ok, assigning to scoped const variable
  const(T) b = g(t); // ok, in(T) is implicitly castable to const.
  in(T) c = h(t); // Error, cannot implicitly cast const to in.
  in(T) d = h(b); // Error, b is not in(T), so the result is the type of b, 
even if f was called with a const(T)
  const(T) d = h(t); // OK, can cast in(T) to const(T) before calling h
  return a; // OK
}

-Steve
Mar 24 2008
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Steven Schveighoffer" wrote

 This idea has come from the discussion on the const debacle thread.

 It is basically an idea for scoped const.  The main goal is so that one 
 can specify that a function does not modify an argument without affecting 
 the constness of the input.

 The main problem to solve would be that I have a function with an argument 
 that returns a subset of the argument.  The easiest function to help 
 explain the problem is strchr.  Please please do NOT tell me that my 
 design is fundamentally unsound because you can return a range or pair, 
 and then slice the original arg based on that pair.  There are other 
 examples that cannot be solved this way, this is just the easiest to 
 explain with.  Everyone who uses C should know about strchr:

 char *strchr(char const *source, char const *pattern);


GAH!!! I meant this to be strstr.  Sorry everyone, please assume I meant 
strstr everywhere I wrote strchr.

-Steve
Mar 24 2008
prev sibling next sibling parent reply Walter Bright <newshound1 digitalmars.com> writes:
Steven Schveighoffer wrote:

 It is basically an idea for scoped const.  The main goal is so that one can 
 specify that a function does not modify an argument without affecting the 
 constness of the input.


I understand what you're asking for, and it does solve some issues. It's 
almost exactly the same as the "return" qualifier I'd bandied about last 
summer:

	T foo(return T t);

where the 'constness' of the argument for t is transmitted to foo's 
return type at the point of call of foo(), not at the point of 
definition of foo. This implies, of course, that foo cannot change t itself.

For me, the question is is solving these issues a large enough problem 
that justifies adding a rather confusing new variation on const?
Mar 24 2008
next sibling parent "Janice Caron" <caron800 googlemail.com> writes:
On 24/03/2008, Walter Bright <newshound1 digitalmars.com> wrote:

  For me, the question is is solving these issues a large enough problem
  that justifies adding a rather confusing new variation on const?


We can trade! :-)

We could drop "in" as a function parameter attribute. I find the
difference between "in" and "const" to be somewhat unfathomable.
Removing "in" would simplify the const system, with, as far as I can
see, no real loss.

See - you can add variations with one hand, and take them away with
the other! :-)

However, I can see a problem with the "return" syntax, exemplified by
the following example.

    const(char)[] g = "hello"; // global variable

    char[] f(return char[] s)
    {
        return g;
    }

    char[] s;
    s = f(s);
    s[0] = 'x';

It's not just the constancy you have to worry about. You also have to
prove that you are actually returning what you claim you're returning.
As in, the actual variable. That's why I earlier suggested

    sliceof(t) foo(const(T) t)

...although "sliceof" is clearly the wrong word, since [] is not
defined for all types.
Mar 24 2008
prev sibling next sibling parent "Janice Caron" <caron800 googlemail.com> writes:
That said, for min(), you'd want to return /any/ of the input
parameters, so I guess that means your syntax is better than mine.
Mar 24 2008
prev sibling next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Walter Bright" wrote

 Steven Schveighoffer wrote:

 It is basically an idea for scoped const.  The main goal is so that one 
 can specify that a function does not modify an argument without affecting 
 the constness of the input.


 I understand what you're asking for, and it does solve some issues. It's 
 almost exactly the same as the "return" qualifier I'd bandied about last 
 summer:

 T foo(return T t);

 where the 'constness' of the argument for t is transmitted to foo's return 
 type at the point of call of foo(), not at the point of definition of foo. 
 This implies, of course, that foo cannot change t itself.


This is sort of a subset of what I am proposing, as for my solution, the 
return type may be not just of type T, but must be of the same constness. 
This is important if you have a function that returns a member of a struct 
or class, that you want to carry the same constness factor (think 
properties).


 For me, the question is is solving these issues a large enough problem 
 that justifies adding a rather confusing new variation on const?


To me, many functions that would be a good candidate for const are now 
removed from being fully-const.  I have mentioned in my post strstr, and 
min/max.  There are a whole slew of functions that would benefit, but must 
now be either re-implemented for each version of const, or cannot be 
implemented with const at all.  Think of properties.  Only one function is 
required for const, invariant, and mutable.  Think of text processing, only 
one function for all these constancies, plus the mutable versions can return 
mutable values while promising that the function is const.  Without this, 
string processing functions that take 2 arguments would generate potentially 
3^2 x 3 = 18 variations, the 3^2 being const invariant and mutable for each 
argument independently, and the x 3 factor for char, wchar, and dchar.  With 
this change, only 3 functions for char, wchar, and dchar. This can also have 
optimization and functional programming benefits.

As for being confusing, I don't see it to be any more confusing than const 
or mixin was to me to begin with.  Like any feature that does not have a 
precedent, this will take some learning, but the resulting code will be so 
much more maintainable, readable, and functional.  I am biased of course, 
since I proposed the idea :)  But I know of at least one other person that 
thinks this is needed.

Couple that with the fact that the 'in' parameter syntax already exists! 
Just add the 'out' for the return value, and allow 'in' variables.  IMO, 
'in' and 'out' are very understandable, already used words in programming to 
mean 'input only' and 'output only'.  Well, I guess 'out' in this context 
doesn't really mean that, but it is necessary to have a keyword to show how 
const would apply to the output type in case it doesn't match the input 
type.  Like I said in my original post, any keyword is fine with me as long 
as the functionality is there.

If at the end of having const permeated throughout the language, nobody uses 
it because it's too unwieldly, then it's not a good feature, no matter how 
many theoretical problems it solves in special case programming.

-Steve
Mar 24 2008
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Steven Schveighoffer" wrote

 Without this, string processing functions that take 2 arguments would 
 generate potentially 3^2 x 3 = 18 variations, the 3^2 being const 
 invariant and mutable for each argument independently, and the x 3 factor 
 for char, wchar, and dchar.


OK, first things first, I need to get my basic math skills right :)

that should have read *27* variations.

-Steve
Mar 24 2008
prev sibling next sibling parent "Janice Caron" <caron800 googlemail.com> writes:
On 24/03/2008, Walter Bright <newshound1 digitalmars.com> wrote:

         T foo(return T t);


Actually, I do find that confusing, because any return statement
inside the body of the function would have to return a const(T), not a
T. Watch:

    T foo(return T t)
    {
        T u = t; /* Whoops - won't compile */
        const(T) u = t; /* OK */
        return u;
    }

It would be less confusing if it were declared as

    const(T) foo(return T t)
Mar 24 2008
prev sibling parent reply Roberto Mariottini <rmariottini mail.com> writes:
Walter Bright wrote:

 Steven Schveighoffer wrote:

 It is basically an idea for scoped const.  The main goal is so that 
 one can specify that a function does not modify an argument without 
 affecting the constness of the input.


 
 I understand what you're asking for, and it does solve some issues. It's 
 almost exactly the same as the "return" qualifier I'd bandied about last 
 summer:
 
     T foo(return T t);
 
 where the 'constness' of the argument for t is transmitted to foo's 
 return type at the point of call of foo(), not at the point of 
 definition of foo. This implies, of course, that foo cannot change t 
 itself.
 
 For me, the question is is solving these issues a large enough problem 
 that justifies adding a rather confusing new variation on const?


If I understand correctly this could be achieved with the plain old 
'final' keyword. Am I right?

Ciao
-- 
Roberto Mariottini, http://www.mariottini.net/roberto/
SuperbCalc, a free tape calculator: 
http://www.mariottini.net/roberto/superbcalc/
Mar 26 2008
parent "Janice Caron" <caron800 googlemail.com> writes:
On 26/03/2008, Roberto Mariottini <rmariottini mail.com> wrote:

 If I understand correctly this could be achieved with the plain old
  'final' keyword. Am I right?


It could equally be achieved with the "heffalump" keyword, if we
defined one, and made it do exactly we want. :-)

However, if you're asking whether or not there is an /existing/ way of
achieving the desired goal, there isn't. So no, I think you are not
right.
Mar 26 2008
prev sibling next sibling parent reply Jason House <jason.james.house gmail.com> writes:
Steven Schveighoffer Wrote:


 So, how do we specify this?


I'm not a D 2.x user yet, but wouldn't it simply be the following?

char[] strchr(return char[] source, const char[] pattern);

Note that pattern can always be const by the very nature of the function.  Only
the source argument needs to be coupled with the return type.  I think this
compactly reduces the various const forms into a simple and easy to define
function.  Having the return type be naked kind of bugs me a bit, but it if I
can get away with writing just one function like that, I'm all for it.
Mar 24 2008
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Jason House" wrote

 Steven Schveighoffer Wrote:


 So, how do we specify this?


 I'm not a D 2.x user yet, but wouldn't it simply be the following?

 char[] strchr(return char[] source, const char[] pattern);

 Note that pattern can always be const by the very nature of the function. 
 Only the source argument needs to be coupled with the return type.  I 
 think this compactly reduces the various const forms into a simple and 
 easy to define function.  Having the return type be naked kind of bugs me 
 a bit, but it if I can get away with writing just one function like that, 
 I'm all for it.


This works for simple functions like the one you gave.

But there are other places where this does not work.  For example, the min 
function would require 2 return parameters.  If you wanted to return a 
member of a class that was an input value.  This is really important with 
properties, because you are generally tagging the 'this' pointer for const 
variance, and so you most likely will not be returning an instance of a 
class from a member function, but rather a member.

-Steve
Mar 24 2008
prev sibling next sibling parent reply Edward Diener <eddielee_no_spam_here tropicsoft.com> writes:
Steven Schveighoffer wrote:

 This idea has come from the discussion on the const debacle thread.
 
 It is basically an idea for scoped const.  The main goal is so that one can 
 specify that a function does not modify an argument without affecting the 
 constness of the input.
 
 The main problem to solve would be that I have a function with an argument 
 that returns a subset of the argument.  The easiest function to help explain 
 the problem is strchr.  Please please do NOT tell me that my design is 
 fundamentally unsound because you can return a range or pair, and then slice 
 the original arg based on that pair.  There are other examples that cannot 
 be solved this way, this is just the easiest to explain with.  Everyone who 
 uses C should know about strchr:
 
 char *strchr(char const *source, char const *pattern);


In C++, assuming you meant strstr, this is:

char const * strstr(char const *source, char const * pattern);

I believe C++ has this right. I do not understand why D programmers want 
to return a non-const from a const input, even in the face of D slicing.
Mar 24 2008
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Edward Diener" wrote

 Steven Schveighoffer wrote:

 This idea has come from the discussion on the const debacle thread.

 It is basically an idea for scoped const.  The main goal is so that one 
 can specify that a function does not modify an argument without affecting 
 the constness of the input.

 The main problem to solve would be that I have a function with an 
 argument that returns a subset of the argument.  The easiest function to 
 help explain the problem is strchr.  Please please do NOT tell me that my 
 design is fundamentally unsound because you can return a range or pair, 
 and then slice the original arg based on that pair.  There are other 
 examples that cannot be solved this way, this is just the easiest to 
 explain with.  Everyone who uses C should know about strchr:

 char *strchr(char const *source, char const *pattern);


 In C++, assuming you meant strstr, this is:


Yes, I did mean strstr, sorry about that.


 char const * strstr(char const *source, char const * pattern);

 I believe C++ has this right. I do not understand why D programmers want 
 to return a non-const from a const input, even in the face of D slicing.


According to online docs, it is sometimes const, sometimes not, sometimes 
both (2 versions, one in which both return and arg are const, one in which 
both are mutable).

The problem with your version is that it is not very useful for mutable 
strings.  If you wanted, for instance, to replace all instances of "hello" 
with "jello", in order to use strstr, you would need to either cast away 
const, or do pointer arithmetic with the result.

-Steve
Mar 24 2008
parent reply "Janice Caron" <caron800 googlemail.com> writes:
The more I think about this, the more I find I have to agree with
Stephen completely. I think I might be able to come up with a better
syntax though.

Instead of

    out(T) min(T)(in(T) x, in(T) y)
    {
        return x < y ? x : y;
    }

which is what Stephen suggested, I think this works better:

    inout(U=T) U min(T)(U x, U y)
    {
        return x < y ? x : y;
    }

It's a pretty straightforward enhancement really. Just preceed a
function definition with the attribute inout(U=T), and then within the
function definition, all U's are in/out types. Here's the same idea
used with strstr

    inout(U=char) U[] strstr(U[]s, const(char)[] pattern)
    {
        int n = s.find(pattern);
        return n == -1 ? null : s[n..$];
    }

The reason I like this better is that it means we only have to define
the "in/out" type once, instead of multiple times. Also - it means we
don't have to ditch the existing uses of "in" and "out".

We can also use it for member functions, except with a slightly modified syntax

    class String
    {
        inout(this) strstr(const(String) pattern)
        {
            /*...*/
        }
    }

I like the idea of only having to express the inout type only once per
function declaration, and I like the idea of not having to completely
change the existing meanings of "in" and "out" in a way which would
break old code.

Another advantage of my syntax is that you could use inout(U=T) as an
attribute to bracket multiple functions. e.g.

    inout(U=char)
    {
        U[] strchr(U[]s, char c);
        U[] strstr(U[]s, const(char)[] pattern);
    }

Stephen, what do you think? Have I missed anything?
Mar 25 2008
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Janice Caron" wrote

 The more I think about this, the more I find I have to agree with
 Stephen completely. I think I might be able to come up with a better
 syntax though.

 Instead of

    out(T) min(T)(in(T) x, in(T) y)
    {
        return x < y ? x : y;
    }

 which is what Stephen suggested, I think this works better:

    inout(U=T) U min(T)(U x, U y)
    {
        return x < y ? x : y;
    }

 It's a pretty straightforward enhancement really. Just preceed a
 function definition with the attribute inout(U=T), and then within the
 function definition, all U's are in/out types. Here's the same idea
 used with strstr

    inout(U=char) U[] strstr(U[]s, const(char)[] pattern)
    {
        int n = s.find(pattern);
        return n == -1 ? null : s[n..$];
    }

 The reason I like this better is that it means we only have to define
 the "in/out" type once, instead of multiple times. Also - it means we
 don't have to ditch the existing uses of "in" and "out".

 We can also use it for member functions, except with a slightly modified 
 syntax

    class String
    {
        inout(this) strstr(const(String) pattern)
        {
            /*...*/
        }
    }

 I like the idea of only having to express the inout type only once per
 function declaration, and I like the idea of not having to completely
 change the existing meanings of "in" and "out" in a way which would
 break old code.

 Another advantage of my syntax is that you could use inout(U=T) as an
 attribute to bracket multiple functions. e.g.

    inout(U=char)
    {
        U[] strchr(U[]s, char c);
        U[] strstr(U[]s, const(char)[] pattern);
    }

 Stephen, what do you think? Have I missed anything?


First, I'll say that I'm not a huge fan of my out() syntax.  However, I do 
like being able to tag exactly what is variably const on the arguments, and 
I think it is necessary to tag the output, otherwise you lose expressiveness 
and limit the syntax to certain types of functions.

So I'm glad that you are trying to find a better syntax, but I don't think 
this is it.  First, you are only allowing one type to be considered 'in' and 
'out', where it must be different for properties (in that the return type 
should be variably const based on the constancy of the 'this' pointer, but 
the return type usually is not the same type as the 'this' pointer). 
Second, I'd much rather have the 'char' in the argument declaration rather 
than aliasing it to some other symbol ('U') at the beginning.  I actually 
think it's less clear the way you have it.  Third, there is no way to 
declare another variable of the same constancy as the input but of a 
different type.  In my scheme, in(x), means the type x that is somehow 
derived from the input.  So at any time you can declare any type and tag it 
with 'in', which means it is based on the input (and therefore, should carry 
the same constancy).

I have found there are more issues that my solution doesn't solve exactly, 
so these need to be figured out.

For example, a linked list of mutable classes might be a template defined 
as:

LinkList(T)
{
   void append(T t) {...}
}

for the append function, the t argument is not modified during the function, 
but the link list node added should be not const.  So if a LinkList node is 
Node(T), then how do you write the signature and body of this function?  Is 
it important to declare t as an 'in' parameter?  I'm almost thinking that 
there is no real way to have the compiler be able to prove that an argument 
is not modified for all types of functions.

In addition, going back to the same example, append should only accept a 
mutable object for t, otherwise, it cannot construct a proper node to add to 
the list.  So how is this information communicated to the compiler?  If we 
use:

void append(in(T) t);

Then a const or invariant t could be passed to the function, which would be 
no good.

Is this even a concern that we should worry about?

-Steve
Mar 25 2008
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Steven Schveighoffer" wrote

 I have found there are more issues that my solution doesn't solve exactly, 
 so these need to be figured out.

 For example, a linked list of mutable classes might be a template defined 
 as:

 LinkList(T)
 {
   void append(T t) {...}
 }

 for the append function, the t argument is not modified during the 
 function, but the link list node added should be not const.  So if a 
 LinkList node is Node(T), then how do you write the signature and body of 
 this function?  Is it important to declare t as an 'in' parameter?  I'm 
 almost thinking that there is no real way to have the compiler be able to 
 prove that an argument is not modified for all types of functions.

 In addition, going back to the same example, append should only accept a 
 mutable object for t, otherwise, it cannot construct a proper node to add 
 to the list.  So how is this information communicated to the compiler?  If 
 we use:

 void append(in(T) t);

 Then a const or invariant t could be passed to the function, which would 
 be no good.

 Is this even a concern that we should worry about?


This is a great case of over-analyzing :)

I now realize that this is a non-issue, because the append function cannot 
use an in modifier for t, because t might be modified later as a result of 
it being added to the list through append.  So append should not be 
modified.

I think this whole scheme should really be restricted to returning a subset 
of a given input type, not building something out of the input type.

-Steve
Mar 26 2008
prev sibling parent reply Oliver Dathe <o.dathe gmx.de> writes:
The following is some kind of superset of what I have proposed in [1]

Example for syntax (*):

     char[] f(char[] p : const(char)[]) { }
                 ^               ^
    Least restrictive type Tmin  |
                      Contract type Tcontract

Basic discussion:
a.) f may only compile if it accomplishes the contract regarding p.
b.) It is an error if Tmin is not implicitly castable to Tcontract.
c.) For the syntax regarding the contract I used ":" at the moment. For 
further syntax proposals, see (*)
d.) At the moment we may call the example f with parameters of type 
char[] and const(char)[]. const(char[]) is not covered by the contract 
and therefor may have to be rejected. More on that (**)
e.) It is still nothing said what the typeof(p) is inside the function. 
I assume it has to be the type of the passed parameter.
f.) If we want to return some slice of p, we get stuck again. Walter and 
Andrei have presented a solution in [2] up to some degree (***).
   char[] f(return char[] p : const(char)[]) { return p[17..42]; }
g.) f can be virtual, because no templates are required.

If static type checking is used inside f we may come out with up to N 
possible binary versions of f, where N is the number of possible 
const-levels between Tmin and Tcontract. It is not 2^N because of 
transitive const. e.g.
   void foo(char[][][][] x : const(char[][][])[]) {...}
may generate N=5 different versions up to:
   const(char[][][])[],
   const(char[][])[][],
   const(char[])[][][],
   const(char)[][][][],
   char[][][][]
Maybe more if invariant is distinguished. However we remain at one 
single sourcecode version and up to ~N binary versions. I think this is 
an acceptable behaviour.


Contract declaration syntax:

(*) Currently some variants come to my mind:

   f(Tmin p : Tcontract)  // a.)
   f(Tmin p Tcontract)    // b.)
   f(Tcontract Tmin p)    // c.)
   f(Tmin..Tcontract p)   // d.)

I think none of these would interfere with something already present. Is 
that right?

I personally would prefer a.) or b.) because a.) naturally signals the 
implicit convertibility with ":" but you may confuse with template list. 
b.) reminds to "Tail" const methods but here at parameter level [1]. 
Both have semantic similarty to what we do with parameter const contracts.

As well we could have a short handle of contract_type for the case when 
we want Tcontract=const(Tmin), a /full const contract/.

   f(Tmin p : const)          // for a.)
   f(Tmin p const)            // for b.)
   f(const Tmin p)            // for c.)
   ?                          // for d.)

That is pretty much what I proposed in [1].


Explicit, Forced and Implict Contracts:

(**) In my very first example passing an argument of type const(char[]) 
fails, because we could not directly sign the contract when we're just 
looking at the declaration.
a.) Nonetheless the compiler may be capable of signing the contract for 
the function if it can prove the function's ability to do so.
b.) We may be able to make a /request for contract/ of the function when 
calling it. Example:
   char[] x = ...;
   foo(x : const(char)); // request for contract when calling foo()
The compiler may then reject or prove&warant the offer.
c.) With this we may be able to reuse large amounts of D1 code with D2 
stylish const types. The returntype issue remains, but that does not 
apply to all functions.
d.) The compiler could try to establish the contract even if neither the 
function offers one nor the call. Maybe this also could be of help for 
the optimizer.


Return type:

(***) The return before the parameter means, that the const level of the 
type of parameter p is applied to the return value. Right now I'm not 
sure what to do if we wanted to return e.g. an element of p.

One idea would be to return "auto", meaning it returns the type of the 
value that is actually returned by the returning return statement ;) 
This goes consistent with the meaning of auto. E.g.

   auto foo(char[][] x : const(char[][])) {
     return x[17];
   }
   unittest {
     char[][]        a = ...;
     const(char)[][] b = ...;
     const(char[])[] c = ...;
     auto ya = foo(a);
     static assert (is(typeof(ya)==char[]));
     auto yb = foo(b);
     static assert (is(typeof(yb)==const(char)[]));
     auto yc = foo(c);
     static assert (is(typeof(yc)==const(char[])));
   }

But you may run into trouble elsewhere like "return found?it:other;", 
maybe. Another attempt:

   char foo(return(char[])[] p : const(char[][])) { ... }

or

   typeof(p[0]) foo(char[] p : const(char[])) {
     return p[42];
   }
   ...
   const(char)[] x = ...;
   auto y = foo(x);
   static assert (is(typeof(y)==const(char)));

[1] 
http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmar
.D&article_id=68137 

http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=68248
[2] http://s3.amazonaws.com/dconf2007/WalterAndrei.pdf p.38/39
Mar 25 2008
next sibling parent reply "Janice Caron" <caron800 googlemail.com> writes:
On 25/03/2008, Oliver Dathe <o.dathe gmx.de> wrote:

 The following is some kind of superset of what I have proposed in [1]

  Example for syntax (*):

      char[] f(char[] p : const(char)[]) { }


I don't think I'd like to have to specify the type twice for every
affected parameter.

I don't have a better idea though! :-(
(But I'm still thinking about it)
Mar 25 2008
parent Oliver Dathe <o.dathe gmx.de> writes:
Janice Caron wrote:

      char[] f(char[] p : const(char)[]) { }


 
 I don't think I'd like to have to specify the type twice for every
 affected parameter.


I'm pretty sure, that most of the time you could stick with some 
shorthand version like

     char[] f(char[] p const) { } // or
     char[] f(char[] p : const) { }

However, it seems like the leading problem is to bring the const level 
of parameters to the return type in an appropriate, expressive way. I 
think that is solved in 90% of the time with

     char[] f(return char[] p const) { }

Not yet sure if that is satisfying enough.
Mar 25 2008
prev sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Oliver Dathe" wrote

 The following is some kind of superset of what I have proposed in [1]

 Example for syntax (*):

     char[] f(char[] p : const(char)[]) { }
                 ^               ^
    Least restrictive type Tmin  |
                      Contract type Tcontract

 Basic discussion:
 a.) f may only compile if it accomplishes the contract regarding p.
 b.) It is an error if Tmin is not implicitly castable to Tcontract.
 c.) For the syntax regarding the contract I used ":" at the moment. For 
 further syntax proposals, see (*)
 d.) At the moment we may call the example f with parameters of type char[] 
 and const(char)[]. const(char[]) is not covered by the contract and 
 therefor may have to be rejected. More on that (**)
 e.) It is still nothing said what the typeof(p) is inside the function. I 
 assume it has to be the type of the passed parameter.
 f.) If we want to return some slice of p, we get stuck again. Walter and 
 Andrei have presented a solution in [2] up to some degree (***).
   char[] f(return char[] p : const(char)[]) { return p[17..42]; }
 g.) f can be virtual, because no templates are required.


I'm not exactly sure what this accomplishes, because of point f) above, this 
seems like it is the same as:

char[] f(const(char)[] p) {...}

Meaning, f cannot modify p or return a slice of p.

-Steve
Mar 26 2008
parent Oliver Dathe <o.dathe gmx.de> writes:
Steven Schveighoffer wrote:

 Example for syntax (*):

     char[] f(char[] p : const(char)[]) { }
                 ^               ^
    Least restrictive type Tmin  |
                      Contract type Tcontract
 [...]
 f.) If we want to return some slice of p, we get stuck again. Walter and 
 Andrei have presented a solution in [2] up to some degree (***).
   char[] f(return char[] p : const(char)[]) { return p[17..42]; }
 g.) f can be virtual, because no templates are required.


 
 I'm not exactly sure what this accomplishes, because of point f) above, this 
 seems like it is the same as:
 
 char[] f(const(char)[] p) {...}
 
 Meaning, f cannot modify p or return a slice of p.


The very first example was just to illustrate the syntax proposal for 
parameter const contracts. The aim is to provide the desired levels of 
const between Tmin and Tcontract. The passed parameter

Imho some more central problem is to apply the const level of the 
parameter (if desired) to the return value. I think in 90% of the time 
this could be solved by Walter/Andreis return storage class (if I got 
that thing right).

Examples:

   char[] f(return char[] p : const(char)[]) {  // p with return&contract
     static if (is(typeof(p)==const(char)[]))
       writefln("const(char)[]");
     else static if (is(typeof(p)==char[]))
       writefln("char[]");
     else
       static assert (false);
     return p[17..42];
   }
   ...
   char[] x = ...;
   auto y = f(x);                               // prints char[]
   static assert (is(typeof(y)==char[]);        // see p's return decl.
   ...
   char[] x = ...;
   auto y = f(cast(const(char)[])x);            // prints const(char)[]
   static assert (is(typeof(z)==const(char)[]); // see p's return decl.
   ...
   const(char)[] x;
   auto y = f(x);                               // prints const(char)[]
   static assert (is(typeof(y)==const(char)[]); // see p's return decl.
   ...
   const(char[]) x;
   auto y = f(x);              // error, f cannot sign the contract
   ...
   void g(int[] p : const(int)[]) {
     p.length = 17;            // ok
     p[42] = '17';             // error, breaks contract, may not compile
   }
   ...
   void h(char[] p const) {...}// short for Tcontract is const(char[])
                               // full contract, p is left invariant by h
   ...
   void i(char[] p) {          // some D1 code, does not know of const
     if (p.length)
       p.length=p.length-1;
   }
   ...
   char[] x = ...;
   i(x const(char)[]);         // call+request4contract => proven&signed
   i(x const(char[]));         // call+request4contract => fails
Mar 27 2008