----- Original Message -----
From: "Sean L. Palmer" <palmer.sean@verizon.net>
Newsgroups: D
Sent: Tuesday, August 26, 2003 12:27 PM
Subject: Re: const / immutable [long]


>
> "Daniel Yokomiso" <daniel_yokomiso@yahoo.com.br> wrote in message news:bifhh6$1hb7$1@digitaldaemon.com...

[snip]

> >     But the issue here is that immutability, when you're dealing with
> > generic types, generates some dependency between the parameters and the
> > result types. Sometimes only one parameter will define the const issue,
> > sometimes more than one. If you make a templated function to find
> > statistical results from a array (min, max, average, etc.) you need a
way
> to
> > ensure that these functions won't: mutate the array, won't mutate the
> array
> > elements, the return types will have the same immutability status (yes
or
> > no) that the array element type. In your example the TMin version for mutable parameters allowed the min function to change them through any mutating methods they had.
>
> This is what I don't understand.  Why should Min return an immutable
value?
> Perhaps it can return a copy of a value that can be mutated.  That's probably lower performance though.  Is this the only reason?

    Here's an example that illustrates this.


class Cell {
    private int value;
    public this(int _value) {
        this.value = _value;
    }
    public int immutable get() {
        return this.value;
    }
    public void set(int _value) {
        this.value = _value;
    }
}
template TPair(T, U) {
    class Pair {
        private final T first;
        private final U second;
        public this(T _first, U _second) {
            this.first = _first;
            this.second = _second;
        }
        public T immutable first() {
            return this.first;
        }
        public T immutable second() {
            return this.second;
        }
    }
}
alias instance TPair(Cell, Cell) CellPair;
alias instance TPair(immutable Cell, immutable Cell) ImmutableCellPair;

ImmutableCellPair minMax(immutable Cell[immutable] array)
in {
    assert(array.length > 0);
} body {
    immutable Cell min = array[0], max = array[0]; // must be immutable
    for (int i = 1; i < array.length; i++) {
        if (array[i].get() < min.get()) {
            min = array[i];
        } else if (array[i].get() > max.get()) {
            max = array[i];
        }
    }
    return new ImmutableCellPair(min, max); // must be immutable
}
int main() {
    Cell[] array = [new Cell(1), new Cell(2), new Cell(3)];
    CellPair pair = minMax(array); // compiler error
    pair.first().set(0);
    pair.second().set(1000);
    return 0;
}


    Inside "minMax" we only have immutable references, so we must construct
a template to a "immutable Cell". Inside "main" we can access the array
elements as mutable references, but the result of the "minMax" function is
immutable, even if we are the "owners" of the object. That's the trick, a
way to define a function interface, specifying that it won't mutate the
parameters, but allowing the result immutability to depend upon the
parameter's mutability. Sometimes the result immutability depends on all
parameters, sometimes just on some of them, or even on none of them. Another
interesting example.


class Box : Cell {
    public this(int _value) {
        super(_value);
    }
    public Box self() {
        return this;
    }
}

int main() {
    Box b1 = new Box(1);
    immutable Box b2 = new Box(2);

// the following statement require that "self" return a immutable Box.
    printf("%d\r\n", b2.self().get());

// but if it's immutable the following code doesn't work
    b1.self().set(2);
    printf("%d\r\n", b1.self().get());

    return 0;
}


    The "self" method needs to be mutable when called through mutable
interfaces and immutable when called through immutable interfaces. It's just
a harmless method ;)

> Sean


---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.512 / Virus Database: 309 - Release Date: 19/8/2003

>
> Back to the min() problem. Ideas only keep getting wilder... well, do you remember how we did it in C times: Macro! Of course!
>
> #define min(x, y) ((x) < (y) ? (x) : (y))
>
> This actually works better (except for the side-effects of call-by-name parameter passing) than any of its C++ equivalents, since you can do things like
>
> int x = 5;
> const float y = 1.0;
>
> float z = min(x, y);
>
> No need for different "const" methods, overloading or anything! Amazing!

Then what we would like is is template with automatic return type deduction
(which will also require implicit instanciation). This would be a great plus
for
metaprogramming.

We may be able to uses standard template syntax for the function definition:

template (R, S, T)
R min(S s, T t)
{
    return s < t ? s : t;
}

or we might uses a syntax that compute the return type:

template (S, T)
min(S s, T t) returns typeof(expr(s, t))
{
}

where the returns type is obtained from an expression or from some other deduction like a typedef inside template class:

    instance MyClass(S, T).my_typedef

If we have otherwise about the same power as in C++
for templates (i.e. have the power to implement code
similar to boost, C++ Template (book) or Modern C++
Design (book) and Loki), those addition would make
metaprogramming far more powerfull that what we have
in C++...

We would have some new keyword like typeof, constnessof,
and a few boost style function and template that would allows
us to manipulate that information...


> Compare this with what Andrei Alexandrescu did to get the (nearly)
> similar effect with templates:
>
> http://www.cuj.com/documents/s=7996/cujcexp1904alexandr/
>
> By the way, he has an interesting comment: "Minimum and maximum are two simple concepts present both in math and in the real life.  If a programming language is unable to express simple concepts of math and life, then there is something deeply wrong with that language."
>
> Anyway - macros seem to work. Why is this possible? Well, because min() is not an actual function call but merely a textual substitution. Well, what language feature was introduced in C++ (and later, in C) to get rid of a certain usage of macros?
>
> Taking Andrei's challenge, let's bring forth the final solution: inline functions.
>
> I wouldn't mean to use inline functions as a means to perform premature optimization, a purpose which programmers are often accused of misusing. But I simply would want to take advantage of the fact that inline functions can "see" the context where they are used, and therefore they would also be able to provide different kinds of code than usual functions. Actually, after an inline function were expanded several times, the compiler could gather them to a single (if possible) function and optimize the inlined code to a function call :)
>
> One thing that inline functions could provide would be determining the
> return type based on argument types. In fact, the inline function could
> work directly on the symbolic environment of the caller;
> assume
>
> inline Symbol min(Symbol x, Symbol y) {
>     return x < y ? x : y;
> }
>
> This would expand similarly to the macro:
> void g(int x, float y) {
>     float z = min(x, y); // expands into:
>     // float z = x < y ? x : y;
> }
>
> It would have to have different specialisations; for non-symbol expressions, the following would be expanded:
>
> inline T min(T x, T y) {
>     // as usual
> }
>
> Inline functions would of course have to have some kind of template-like implicit instantiation mechanism (which D templates is soon going to get, I hope) and ability to specialize on different types. And they could naturally be used to implement variable-sized argument lists type-safely...
>
> Hmm, I think I got sidetracked a bit. Could be time for sleep.
>

"Philippe Mori" <philippe_mori@hotmail.com> escreveu na mensagem news:big4ek$2e9p$1@digitaldaemon.com...

[snip]

> maybe something like that would be OK:
>
> template stats(T)
> {
>     constnessof(array) T find_min(const T [const] array)
> }
>
> where we can indicate what to check for constness. The
> list can include this for member functions and for complex type
> we might allows a syntax similar to the one used for specialisation
>
>     constnessof(array : pattern)
>
> where patern would include the optional const
>
> or alternatively a syntax where we could name modifier: For the sample I will uses # symbol. There are probably better alternative. Makes your suggestions!!!
>
> template stats(T)
> {
>     constnessof(c1, c2) T find_min(const#c1 T [const#c2] array)
> }
>
> For non-virtual methods, we could support automatic constness detection which should not be hard for the compiler to implement (about the same complexity as generating an error in C++ when constness is not respected).
>
> template stats(T)
> {
>     autoconst T find_min(const T [const] array)
> }
>
> where const would be added if required.
>
> This would be usefull for generic code like the TMin template
> or for containers that wants to return constant reference to their
> elements if they are themself const...
>
>
> Automatic modifier would also have other uses that for constness support. They would be usefull for function calling convention for example (I don't know how those specifier are handled in D - that is the equivalent of cdecl, fastcall, pascal and similar in C++).
>
> For ex. in C++, mem_fun and related classes and functions only works when the default calling convention is used... but ideally the same code should be usable with any calling convention.

Yes, this "constnessof" and "autoconst" would solve the issues I was talking
about. I think they might open new cans of worms, but there's another issue.
In Eon I started doing something like that, later generalizing the idea of
dependent mutability to dependent typing, which is just a few steps ahead,
but improves the expressiveness by an order of magnitude.
"Philippe Mori" <philippe_mori@hotmail.com> escreveu na mensagem
news:big4ek$2e9p$1@digitaldaemon.com...

[snip]

> maybe something like that would be OK:
>
> template stats(T)
> {
>     constnessof(array) T find_min(const T [const] array)
> }
>
> where we can indicate what to check for constness. The
> list can include this for member functions and for complex type
> we might allows a syntax similar to the one used for specialisation
>
>     constnessof(array : pattern)
>
> where patern would include the optional const
>
> or alternatively a syntax where we could name modifier: For the sample I will uses # symbol. There are probably better alternative. Makes your suggestions!!!
>
> template stats(T)
> {
>     constnessof(c1, c2) T find_min(const#c1 T [const#c2] array)
> }
>
> For non-virtual methods, we could support automatic constness detection which should not be hard for the compiler to implement (about the same complexity as generating an error in C++ when constness is not respected).
>
> template stats(T)
> {
>     autoconst T find_min(const T [const] array)
> }
>
> where const would be added if required.
>
> This would be usefull for generic code like the TMin template
> or for containers that wants to return constant reference to their
> elements if they are themself const...
>
>
> Automatic modifier would also have other uses that for constness support. They would be usefull for function calling convention for example (I don't know how those specifier are handled in D - that is the equivalent of cdecl, fastcall, pascal and similar in C++).
>
> For ex. in C++, mem_fun and related classes and functions only works when the default calling convention is used... but ideally the same code should be usable with any calling convention.

Yes, this "constnessof" and "autoconst" would solve the issues I was talking about. I think they might open new cans of worms, but there's another issue. In Eon I started doing something like that, later generalizing the idea of dependent mutability to dependent typing, which is just a few steps ahead, but improves the expressiveness by an order of magnitude.

"Antti Sykäri" <jsykari@gamma.hut.fi> escreveu na mensagem news:slrnbkntuv.83p.jsykari@pulu.hut.fi...
> Ok, let's drop immutable and just talk about const.

    But I like immutable so much... ;)

[snip]

> Okay, now I think I have an idea about the fundamental problem. The min() function can be used as an example of the general idea. The function must return one of its arguments, whether mutable or immutable. At the same time it must provide the guarantee that it won't modify its arguments -- we'd like the type system to ensure that the only thing that "min(T, T)" is allowed to do is to pass one of its arguments back to the caller.

    That's it.

> One way to ensure this is to make its arguments const; but then you'd have to make its return type const, as well, or the following wouldn't compile: (Let's leave the bodies away -- everybody probably knows what "min" looks like if he or she has read this far :)
>
> I'll drop the template syntax because it has nothing to do with const really. Assume that T is an int or actually, reference type would be better to illustrate the const semantics.

[snip]

> Don't use "const" as a type modifier at all, but merely as a way of documenting the function's behavior (as in "I won't change this parameter"). Enter contracts. Like so:
>
> T min(const T x, const T y) {
>     // implementation...
> }
> out() {
>     // mathematical properties of min(x,y)
>     assert(result <= x);
>     assert(result <= y);
>     // it's one of them
>     assert(result === x || result === y);
>     // I didn't change my parameters, I promise; these would be
>     // generated by "const"
>     assert(old x == x);
>     assert(old y == y); // Here we would actually have to rely on
>     // deep_clone or similar, as you mentioned below. Tricky notion,
>     // comparing something that exists now to something that existed
>     // earlier in time
> }
>
> Side note: Don't you just love when the function's postconditions actually describe perfectly what the function does! Reminds of me of the good old combinator function in purely functional languages. It takes a function of type ('a -> 'b) and a function of type ('b -> 'c) and returns a function of type ('a -> 'c). Now what could a function of this type do? The notation "'something" means generic type parameter, so it cannot assume anything about its types.  Well, what else can it do, then, than create a function that first calls the first function and then calls the second function on the result? So the function's type is a complete description of the function itself.

    That would probably be a good compromise. But we still need a way to
"attach constness" to a reference, so I can give to my caller a const
reference. Otherwise we just solve one half of the problem.


[snip interesting things about inline functions]

    Inline functions also solve just one part of the problem. Besides
sometimes you can't inline the definitions (e.g. virtual functions).

>
> >      Some issues regarding mutability are discussed here
>
><http://lambda.weblogs.com/discuss/msgReader$8378?mode=topic&y=2003&m=8&d=2
5
> >> Tim Sweeney has some pretty good thoughts.
>
> An interesting discussion. BTW, the guy who he was talking with, Vesa Karvonen, I used to work with some time ago. He's a smart guy; taught me a lot about programming. It's a small world, and particularly small in the area of functional languages and type theory :)

    Yes, it's a very small world :)

> >> Uh, could you give an example of one hard case?
> >
> >     Sorry I meant: 'Also it's very hard to write "ensure" clauses on
> > contracts of methods that have side-effects (i.e. methods that mutate
the
> > instance)'.
> >
> > Set(T) {
> >     void remove(T item)
> >     out () {
> >         if (old this.contains(item)) {
> >             assert(this.size + 1 == (old this.size()));
> >         }
> >         assert(!this.contains(item));
> > // so far so good.
> >        for (T each; old this) {
> >            if (each != item) {
> >                assert(this.contains(item));
> >            }
> >        }
> > /* ops, it won't work because the "old this" expression will yield a
> > reference
> >  * to the this object, and here it's already mutated. The correct
expression
> > is
> >  * "(old this.clone())" ensuring that we get a snapshot of the this
object
> > from
> >  * before the method execution.
> >  */
> >     };
> > }
>
> Well, that's what you get if you really want to compare two sets, only one of which is available at a time. I'd really just leave it, settle with simpler preconditions and place some trust on the programmer...
>
> I wouldn't find very complicated examples in Eiffel's libraries, either; in particular, no clone()'s in old expressions. I looked at, for example, the equivalent BINARY_SEARCH_TREE_SET at
>
>
http://docs.eiffel.com/libraries/base/reference/structures/set/binary_search
> _tree_set.html#f_prune
>
> which has the similar postcondition
>
> removed_count_change: old has (v) implies (count = old count - 1)
>
> but does not have the last check.
>
> -Antti

There are better contracts in the ELKS standards. They are pretty comprehensive (the String slicing includes more than 10 ensure clauses IIRC) and has to deal with some of these issues. Also there are papers only about this, specially one author talks about specifying mutability in contracts, to ensure that Set.put don't change the old contents of a Set, ditto for Stacks, Queues, etc., generalizing the notion to Observer design pattern. I don't seem to have the paper here, but if you're interested I can look around. It was about Eiffel, and using special deconstructors to decompose the object (in Stack he described an "item" operation returning the top of the stack and a "rest" operation giving everything except the top, in set he used a "choice" and "rest" pair of operations).


---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.512 / Virus Database: 309 - Release Date: 19/8/2003

In article <bhmc8c$h12$1@digitaldaemon.com>, Fabian Giesen says...
>
>> So the standard says that if we've got pointer to a const object, we can't change it, but does not indeed say the object would be immutable. Which is quite convenient: when you call a function with signature void f(const T*); you can be certain that it won't change your argument.
>
>Unless someone casts your donstness away, which anyone can do without you ever knowing.
>
>Which means that const is really just a vague promise.
>

Remember that const is type information.  The same could be argued of any ability of the programmer to overrule the static type system (non-dynamic downcasting, anyone?).  Does the existence of such mechanisms negate the value of static type checking?  Certainly not.

As has been pointed out, C++ const is not an enabler for compiler optimizations, nor is it meant to be.  What it does do is enable a programmer to say something about how an object should be used or how he uses an object and have the compiler enforce it.  (Maybe I'm just lazy, but I like it when I'm able to get the computer to do grunt work so I don't have to.  It's better at that sort of thing anyway.)  And, just like with other forms of static type checking, there exist mechanisms (casts) to allow you to explicitly lie to the compiler, albeit at your own risk.

Lastly, the idea that const should always imply bitwise immutability is a misconception IMO.  The usual example is of an object that does some computationally expensive operation.  If the externally visible state of the object cannot be changed by the operation, then the operation is logically const and should be labeled so even if the implementation does something mutable internally (say, caching the results).  The operations on the cache may not be const, but if it's entirely an implementation detail then it makes no difference to the constness of the operation.

Scott McCaskill

>
> Lastly, the idea that const should always imply bitwise immutability is a misconception IMO.  The usual example is of an object that does some computationally expensive operation.  If the externally visible state of
the
> object cannot be changed by the operation, then the operation is logically
const
> and should be labeled so even if the implementation does something mutable internally (say, caching the results).  The operations on the cache may
not be
> const, but if it's entirely an implementation detail then it makes no
difference
> to the constness of the operation.
>

Then your have mutable members for thinks that should not appears const (in worst case scenario) all members would end-up as being mutable... so your external state can be what you want it to be anyway.

We might also need mutable function that would be allowed to be called from a const object but would be allowed to only changes mutable members and this should help remove the need to cast away constness in more situations that C++ does....

The real problem is when using code that cannot be modified and for which constness is not properly done.... but I think that if we uses mutable for those objects where some functions aren't const when they should, it would help...

Also for parameters, since in is the default, we have implicit constness for those arguments... which should also help to get it right from the beginning and have properly written libraries...

If more control is needed, then we might add immutable keyword in addition to const...

"Bill Cox" <bill@viasic.com> wrote in message news:bhaupl$12t1$1@digitaldaemon.com...
> Why not just have the compiler try to prove that constant data is never modified, rather than having me put 'const' keywords in all my parameter declarations?  Is this what you're getting at?  If so, I'm for it.  It would eliminate all the cast nonsense 'const' creates when we use eachother's code.

Frankly, I think the way to do this is to put const data into a 'read only' data segment. Then, the hardware does the checking for you. There would be no way to use clever casting, mutable, or other gymnastics to defeat it. And there'd be no need whatsoever to use const as a type modifier. Compilers for embedded systems tend to do this already, as the const data gets burned into a ROM.

That's another big reason why I prefer const as a storage class.

"Antti Sykäri" <jsykari@gamma.hut.fi> wrote in message news:slrnbjq9vr.mtu.jsykari@pulu.hut.fi...
> So the standard says that if we've got pointer to a const object, we can't change it, but does not indeed say the object would be immutable. Which is quite convenient: when you call a function with signature void f(const T*); you can be certain that it won't change your argument.

The problem is that the standard doesn't preclude anyone *else* from changing the const data. For example:

void f(int *p1, const int *p2)
{
     int i = *p1;
    (*p2)++;
    int j = *p1;        // oops! j != i
}

    int *a;
    ...
    f(a, a);

This is perfectly legal and defined behavior. This is one reason why const as a type modifier is useless for optimizers. And yes, this kind of code (in obfuscated ways) happens in real code. I know, because I found out about it the hard way :-(

"Fabian Giesen" <rygNO@SPAMgmx.net> wrote in message news:bhrn8p$251q$1@digitaldaemon.com...
> I agree that such limitations can always be worked around with inline
assembler
> or union hacks or stuff like that, but that's not of interest to me; if
you have
> to go into the realm of undefined behavior in the first place to do
something,
> it's perfectly okay if you get undefined behavior in return. :)

Yet you can break const using legal and defined Standard-conforming code, as I posted in this thread. The optimizer could make use of const if breaking it was only in the realm of undefined behavior. But it is not, and so const is useless.

Not that I don't have a strong opinion about it <g>.

> Yet you can break const using legal and defined Standard-conforming code,
as
> I posted in this thread. The optimizer could make use of const if breaking it was only in the realm of undefined behavior. But it is not, and so
const
> is useless.

It's only useless from the perspective of a compiler writer. For professional programmers (by which I mean those that observe the "contracts" of the libraries that they are using), it is anything but.

I've found this whole debate quite perplexing. People are expending huge efforts to prove that const is useless from a strict point of view. I don't really think anyone would disagree with that proposition. (It'd be pretty hard to when we have "mutable" and "const_cast".) But no-one's argued successfully against the real value of const (which should have been named "readonly") which serves as Jiminy Cricket to the user.

This is in just the same way that, say, speed limits on roads serve a useful function. They present an informed context within which you can exercise free will. You may choose to drive at 100mph on a winding mountain pass that has 50mph limit, but you bear the risk. I for one would not want to have engine-limiting mechanisms that prevent me from breaking the speed limit, even though most of the time I drive to it, in case I had some kind of emergency. In the same way, I'm quite happy as a coder (not a compiler writer) that const can be broken. Although such action is frowned upon, there are rare occasions where it is necessary. The majority of cases it is very good to have the (C++) compiler tell us that we cannot do something, albeit that we may recklessly choose to overwrite it.

Yesterday you raised the issue of the deblank() function having the wrong semantics. If we had a readonly keyword in D, the issue would be moot.

I want code to be self-documenting, and the compiler to help enforce that (to a reasonable degree). If we had "readonly", that could be achieved. I don't give a fig for optimisations based on putative vs actual read-only, and all that other guff, and will be thoroughly unperturbed if that is left out as it stands currently. But I remain strongly unconvinced that its absence from D is a +ve step. I'd be very interested to hear anyone to put forth an argument for such in response to what I (and others, who've commented similarly) want from a readonly/const keyword, rather than countering with the optimisation arguments.