Discussion Thread: DIP 1041--Attributes for Higher-Order Functions--Community Review Round 1

[Timon Gehr]

On 14.04.21 13:43, jmh530 wrote:
> On Monday, 12 April 2021 at 18:14:30 UTC, Timon Gehr wrote:
>> [snip]
>>
>> Unfortunately that's the nature of the chosen approach: 
>> non-compositional type system design is a game of whack-a-mole 
>> resulting in progressively more complexity while often maintaining a 
>> lack of soundness.
> 
> Sorry, when you say non-compositional type system, what precisely do you 
> mean?
Types in a program are usually syntactically generated from some 
recursive grammar. For example, if you have types `T` and `S`, then 
`T[]` and `T delegate(S)` are also types.

Basically, the semantics of types is "compositional" when the meaning of 
the constituent types does not implicitly depend on the context in which 
they are plugged and the meaning of the context does not depend on the 
constituent types.

For example, above, the semantics of `T[]` and `T delegate(S)` are not 
fully compositional, because they have special cases for `T = void`.

Instances of such designs (here taken from C) tend to have ripple 
effects, slowly adding special cases in other corners of the language. 
For example, the compiler treats `return exp;` where exp is of type 
`void` like `exp; return;`. This is an improvement and I would not want 
to miss it, but it would not have been necessary nor needed any special 
documentation if `void` had not been special-cased in the first place. 
(In many languages, `void` is just treated like an ordinary type that 
has just one value, often identified with the empty tuple.)

The DIP is a bit like that, but on steroids, and it already proposes 
some of the ripple effects. All the while, it is not very powerful. For 
example, it does not even attempt to solve this case:

---
int apply(int delegate(int delegate(int)) f, int delegate(int) g){
     return f(g);
}
---

We want `apply` to have the same qualifiers as `f` and the argument of 
`f` to have the same qualifiers as `g`.

With proper attribute polymorphism, one can just state that in code:

---
int apply[qual a,qual b](int delegate(int delegate(int)a)b f, int 
delegate(int)a g)b{
     return f(g);
}
---

This solution is simple and more general, but most importantly, it does 
not redefine the meaning of existing types in non-compositional ways and 
the language does not paint itself into a corner by adopting such a 
solution. It does not break existing code nor prevent additional 
features to be added later.