[swift-evolution] [Review] SE-0065 A New Model for Collections and Indices

[Howard Lovatt]

A Scala like new-Iterator pattern, using path-dependent typing, might be:

struct Range<T: Comparable> { ... }
func ..< <T: Comparable>(lowest: T, highest: T) { ... }

struct Array<T>: Collection {

static struct Iterator { ... } // Note static

...

func next(iterator: inout Iterator) -> Element? { ... }

subscript(range: Range<Int>) -> [E] { ... }

}


With new iterators, Scala style, the following is legal:

let a = [Int]()
let b = [Int]()
let i = a.Iterator() // Create an instance of an inner type, type
associated with an instance of its outer type
let aE = a.next(&i)
let r = 1 ..< 2
let aS = a[r]
let bS = b[r] // OK since `r` is not associated with `a` because `Range` is
not nested within `Array`


but not

let bE = b.next(&i) // Type error because `i` is associated with `a` not `b`


The type `Iterator` is static because it does not capture the enclosing
type instance, the enclosing type instance, `a` in the example, is solely
used for typing. Non-static inner types capture an instance of their outer
type.

The other interesting pattern using inner types is old-style
iterators, conventional external iterators:


struct Array<T>: Collection {

struct Iterator { ... } // Note *not* static, therefore captures outer
instance when created

...

}


With external iterators, Scala style, the following is legal:

let a = [Int]()
let i = a.Iterator() // Create an instance of an inner type, *capturing*
and type associating with an instance of its outer type
let aE = i.next()

Whilst this pattern in use is very similar to what Swift currently does it
is a lot easier to optimise because an escape analysis can tell if the
capture of `a` by `i` needs to increment the reference counting or not. The
compiler knows that `i` has captured `a` which allows this optimisation. I
*think* that Java's JVM's escape analysis does this optimisation.

Assuming that Swift could optimise inner types then this would allow
retention of traditional external iterators.

On Monday, 18 April 2016, Dmitri Gribenko via swift-evolution <
swift-evolution at swift.org> wrote:

> On Sun, Apr 17, 2016 at 11:14 PM, Thorsten Seitz <tseitz42 at icloud.com>
> wrote:
> > Preventing indices of one collection being used by another collection
> can be done by using path dependent types like in Scala.
> >
> > Then 'i' would have type a.Index (where 'a' is the instance!) and
> therefore b[i] would not typecheck as it would require an index of type
> b.Index
>
> This is an interesting concept!  Would this work with slices?  You
> should be able to use indices from slices with the base collection,
> and vice-versa (when indices are in range).
>
> 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>*/
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160419/e99ceb5b/attachment.html>