equivariant functions

[Andrei Alexandrescu]

Benji Smith wrote:
> Andrei Alexandrescu wrote:
>> Benji Smith wrote:
>>> I really don't see what all the fuss is about with the equivariance 
>>> stuff, except that it introduces a lot of confusing rules to fix the 
>>> holes in the (already complex and confusing) const system.
>>
>> Please stop perpetuating misunderstanding and apprehension about the 
>> const system through statements strong on opinion and vague on detail. 
>> If you're willing to mention holes, complexity, and confusion about 
>> the const system, please explain where the holes are, where the 
>> complexities lie, and what aspects you are confused about. Suggestions 
>> for fixing said issues would also be welcome.
> 
> Fair enough. Here are the reasons I describe the const system as "complex":

I see where you're coming from. If your opinion is that the const system 
does not bring enough benefits to justify its learning, you are of 
course entitled to it. But talking about complexity implies that there 
would be simpler ways to achieve its charter that we missed, and talking 
about holes that we made mistakes of principle that go beyond bugs in 
the compiler or incompleteness of implementation.

> * Comparable code without const qualifiers contains quantatitively fewer 
> semantic constructs than code that uses those qualifiers. Smaller 
> function prototypes are easier to read and comprehend:
> 
>    char[] join(char[] str2, char[] str2) { ... }
> 
>    const(char)[] join(const(char)[] str1, const(char)[] str1) { ... }

Complexity should be judged in proportion to the goal achieved. Of 
course an AM radio will be less complex than an AM/FM radio; that does 
not reveal an intrinsic problem with the latter. And the more complex 
signature tells you that join will not change its arguments. As Gide 
mentioned, one source of bugs in a D program is that attention must be 
paid to duplicating aliased slices properly. That wouldn't be bad if 
such mistakes were easily detected. Unfortunately, forgetting to call 
.dup causes long-distance coupling that make changing one piece of data 
in one place influence the change in an unrelated part, just because 
they share some history.

> * Nestable const type constructors require me to keep a more detailed 
> mental model of the type system. Am I using a "const(char)[]" or a 
> "const(char[])"?

You don't need to keep a more detailed mental model of the type system - 
whatever that is :o). On the contrary, const allows you to free your 
mind of many details about the data flow in your application. If you 
make a mistake regarding const(char)[] vs. const(char[]), the compiler 
will tell you about it, not one night of debugging.

> * Remembering the difference between "const" and "invariant" requires 
> more mental energy than using a system (D1) where such distinctions 
> don't exist.

I think this reflects a misunderstanding of what constness is supposed 
to do for you. It's exactly the contrary. Invariant reduces the amount 
of mental energy you need to expend. I think you owe it to yourself to 
use D2. You will see that using invariant strings is a huge improvement 
and it alone is worth introducing constness. Literally all bugs caused 
by undue aliasing disappear if you use string. You will see that the net 
result is that your programs are easier to write and understand, not harder.

> * The idea that "const" is a supertype of "mutable" and "invariant" is 
> utterly bizarre to me, since it violates the "is a" rule of type 
> hierarchies. I understand that, for the sake of overloading, both 
> "mutable" and "invariant"  can be implicitly cast to "const", but the 
> other implications of that relationship are beyond my grasp at the moment.

You may want to reframe this as an opportunity to improve your 
understanding of subtyping. I recommend a classic paper by Cardelli and 
Wegner "On understanding Types, Data Abstraction, and Polymorphism" 
(http://lucacardelli.name/Papers/OnUnderstanding.A4.pdf). It's a 
classic. Reading through section 1.5 does not require much background 
and is very rewarding.

That's not to say using const and invariant requires formal background. 
Most people would just use them for their benefits and have them just 
work. But if you want to lift the hood and see exactly why they work, 
you have to get your hands greasy a bit.

> * The transitivity of const qualifiers requires me to consider not just 
> the object I'm passing around, but the references to other objects 
> contained within the const-qualified object.

This is backwards, too. If const didn't exist or weren't transitive, 
you'd be required to keep in mind for mutation and aliasing bugs not 
just the object you're passing around, but the references to other objects.

> * Both "const" and "invariant" can apply to value-type objects. But 
> "const" doesn't make any sense in that context, so in my mind I have to 
> use the "invariant" concept instead whenever applying the concept to a 
> primitive value.

Of course it does make sense. The address of a const int has a different 
type than the address of a mutable int. Again the pattern is that you 
have less, not more to keep in mind. The type "keeps it in its mind" for 
you.

> * The equivariance proposal, at least in some of its forms, requires me 
> to imagine the existence of implicit typedefs at the function-call site, 
> and to know that the declared type in my method signature might not be 
> the actual type of the arguments received by the function.

Not at all. On this group many people have high competency and willing 
to discuss the most minute implementation details of a language feature, 
and my understanding is that you also engage in such discussions. On 
occasion, therefore, there will be discussion on exactly how sausages 
are being made. Do not confuse those discussions with things that 
complicate the experience of eating sausages.

Much of the problems caused by const equivariance is just that Walter is 
leery of implementing aliases bound to qualifiers. If he would, there 
would be no problem to talk about. The issues with const equivariance, 
in that case, would be exactly the same as with supporting equivariance 
for any types in general.

> The "holes" I described in the const system are the symptoms being 
> addressed by the equivariance proposal.

You did not describe any hole above. In fact, on first reading, at this 
point I was expecting you'd start describing the actual holes that I 
know about - e.g. the impossibility of creating invariant objects 
without a cast. (That will be fixed.)

> Without equivariance, the const 
> system sometimes requires verbatim duplication of code within function 
> bodies whose only difference is their signature. Without the const 
> system, the equivariance proposal wouldn't be necessary.

No. Without equivariance, you'd be required to duplicate bodies of 
functions that need it, such as clone. It is true that const makes that 
need more frequent, but that does not reveal a problem intrinsic to it 
or a mistake in defining it.

> And the reason I describe the const system as "confusing"?
> 
> Because it confuses me.

This is a fair point. One problem is that right now no good description 
of const exists. Worse, trying to infer it from discussions on this 
group is bound to scare one away because here mostly problems are 
discussed.

> I understand some of the allure of having a robust, provably correct 
> const system. Automatic memoization would be cool. Automatic parallel 
> execution would be nice. And, in theory, it'd be nice to avoid errors 
> that occur when a piece of code modifies a piece of data that it shouldn't.
> 
> But in my experience (using languages that lack any sort of const 
> system, except for enum-style declarations), it just doesn't matter 
> much. When I need memoization or parallel execution, I write the code 
> explicitly. And when I need an immutable object, I design its interface 
> to make external mutation impossible (see also: java.lang.String).

There's been a pretty incredible resurgence in interest in functional 
programming languages. At ACCU 2008 (www.accu.org), previously a 
"no-quarters" hardcore C++ conference, who do you think gave keynotes 
and talks? Simon Peyton-Jones, the inventor of Haskell, and Joe 
Armstrong, inventor of Erlang. To better understand the size of that 
change, you must browse through previous years' conference programs. 
Only 2-3 years ago that very concept would have been unbelievable. ACCU 
stands for Association of C and C++ Users! Use of Haskell and Erlang is 
increasing exponentially. Even mainstream companies started using them. 
Others (big, big companies that shall not be named) are designing their 
own languages. And guess what - they _all_ have a notion of immutability.

What do functional languages have? Do you think people like them for the 
monads? It's the immutability. They've been embracing and dealing with 
it for years. And that gives them a ready answer to today's 2000-lbs 
pink elephant in the room - the manycores. Having made a resolute step 
towards classic, deadlock-oriented programming, Java is now in the 
unpleasant position of having invested it money in the wrong stock, just 
like it did with UTF-16. So when people think manycores, they look away 
from Java.

> It's indisputable that the D2 const system is measurably more complex 
> than the D1 const system.
> 
> For me, the cost of that complexity significantly outweighs the benefit.

It is fair to hold such a belief. I think it would be helpful to 
reevaluate it in wake of the above.


Andrei