[swift-evolution] [Pitch] Remove type inference for associated types

[Dmitri Gribenko]

On Fri, Jun 24, 2016 at 10:50 PM, Austin Zheng via swift-evolution
<swift-evolution at swift.org> wrote:
> Hello all,
>
> Per Chris Lattner's list of open Swift 3 design topics
> (http://article.gmane.org/gmane.comp.lang.swift.evolution/21369), I've put
> together a proposal for removing type inference for associated types.

Hi Austin,

Thank you for starting this discussion!  There's one other alternative
that I mentioned in one of the previous threads on this subject.  The
idea is to limit the inference so that the sizes and the complexity of
the problems that the type checker has to solve become tractable with
a simple algorithm, not a full constrain solver.

Currently, as far as I understand, the type checker solves for all
associated types for a protocol conformance in a single giant step,
during which every decision can affect every other decision.  My
suggestion is that we keep associated type inference for the simple
cases where it is obvious what the user meant.  The author of the
protocol would be able to identify these simple cases and define how
exactly the inference should happen.  For example:

protocol Collection {
  associatedtype Index

  @infers(Index)
  var startIndex: Index

  // Does not affect associated type inference, types have to match
with decisions made by other declarations.
  var endIndex: Index

  // Does not affect associated type inference.
  subscript(i: Index) -> Iterator.Element

  associatedtype Iterator

  @infers(Iterator)
  func iterator() -> Iterator
}

Under the current system, every declaration in a conforming type that
matches a requirement that mentions 'Index' can affect the inference.
That is, 'Index' is inferred from all declarations in the conforming
type.   But there is no reason to make it that general -- the protocol
author knows that 'var startIndex' in the conforming type has be of
the right type, and there is no reason for other declaration to affect
the decision about what 'Index' is resolved to.  Under the proposed
rule, there is at most one declaration that the protocol author is
allowed to designate with @infers, that is allowed to affect the
inference.  If there is no @infers for a certain associated type, then
it is never inferred and should always be specified explicitly.

This is the basic idea, I'm sure there are corner cases I haven't
thought about (e.g., how does this interact with constrained
extension, can we still solve everything with a simple algorithm?)
But the reason why I'm suggesting this alternative is that I'm
concerned that in simple cases like inferring the 'Index' and
'Iterator' typealiases having to specify them manually is just
boilerplate, that does not add to clarity, and, I believe, can be
inferred by the type checker without involving a heavy constrain
solver.

Dmitri

-- 
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr at gmail.com>*/