Feedback on Átila's Vision for D

[Paul Backus]

On Tuesday, 15 October 2019 at 17:50:52 UTC, jmh530 wrote:
> On Tuesday, 15 October 2019 at 16:39:47 UTC, Paul Backus wrote:
>> [snip]
>>
>> The one advantage C++ concepts have over D's template 
>> predicates is that they're transparent to the compiler. As a 
>> result, the compiler is able to determine a partial order on 
>> template constraints [1], and use that order to resolve 
>> overloads (just like D does with regular function overloads 
>> [2]). D can't do this, so we're stuck writing awkward things 
>> like this:
>>
>> auto myAlgorithm(R)(R r) if (isInputRange!R && 
>> !isRandomAccessRange!R) { ... }
>> auto myAlgorithm(R)(R r) if (isRandomAccessRange!R) { ... }
>>
>> .[snip]
>
> That's an interesting point. The problem is the template 
> constraints aren't considered for the overloading, right? 
> However, if they were expressed as in something like below
>
> auto myAlgorithm(T)(InputRange!T r) { ... }
> auto myAlgorithm(T)(RandomAccessRange!T r) { ... }
>
> then I presume that it wouldn't be an issue.

You misunderstand.

The problem isn't that template constraints aren't considered for 
overloading--they are. It's that, if two overloads both have 
constraints that match, the compiler has no way of telling which 
one is "more specific".

In other words, if you pass an input range to the above overload 
set, it will satisfy *both* isInputRange and isRandomAccessRange, 
because all random access ranges are also input ranges, and 
you'll get an ambiguity error. Ideally, we would like the 
compiler to understand that isRandomAccessRange is "more 
specific" than isInputRange, and choose the correct overload 
without requiring any additional disambiguation.

Because templates are Turing-complete, it is undecidable, in the 
general case, whether one template predicate is "more specific" 
than another (i.e., whether A!T == true implies B!T == true for 
all T). So there's no way to have the compiler do what we want 
unless we replace template predicates like isInputRange with 
something else that the compiler can understand without needing 
to solve the halting problem.

Some possible solutions:
   - Designate a particular subset of templates--for example, 
those whose body
     consists of a single boolean expression--as "concepts", and 
add code in the
     compiler to analyze them.
   - Add C++-style concepts as a language construct distinct from 
templates.
   - Change predicates like isInputRange to return strings instead 
of boolean
     values, and use mixin to inject their expressions directly 
into template
     constraints without evaluating them first.
   - Add AST macros to D, and change predicates like isInputRange 
into macros
     that return unevaluated expressions instead of boolean values.