Fear Not the Association of Types | Hacker News Reader

Fear Not the Association of Types

gavinleroy.com

55 pointstodsacerdoti15 comments

I didn't really understand the Java comparison. As far as I understand, the Rust `Iter` trait is essentially a generic interface with one type parameter, the type implementing the interface. If that understanding is correct, than this is essentially identical to Java's Iterator<T> interface, except that Java interfaces are not implicitly generic on the type that implements them. But in both cases, the Iterator has one and only one generic type parameter.

In Java, if Iterator had been a non-generic interface, then Vector<A>.Iterator.Next() would have had to return an Object instead of an A, as would all other implementations of Iterator for any collection type. Even if you defined a member type, Iterator.Result, it would still be the exact same type for all Iterator implementations.

The whole thing about dynamic vs static dispatch seems to be a bit of an unnecessary detour. I'm not even 100% sure that in practice Java would rely on dynamic dispatch to find the right method there, it may well be that it can be optimized to do static dispatch (the bigger help there is that all Java objects have the same size on the stack, sizeof(pointer), so a single method can always handle any object, whereas in Rust you need different methods for different objects regardless of logic).

In Java you can't have a class implement both Iterator<Foo> and Iterator<Bar> (type erasure; or maybe my Java is out of date...). Anyway if you could, the for loop would not know which to use.

In Rust you could have both Iterators if it had a type parameter.

Yes, this is the actual reason. In Java you're restricted to one implementation of an interface for a type by syntactic construction (classes list their interfaces in their header and each interface can only appear once). In Rust there is a similar restriction (called coherence), but it takes into account all of the parameters to a trait, including its generics.

An illustrative example of the difference: `AsRef<T>` and `Deref` have almost identical signatures, except that the target type for `AsRef` is a parameter and for `Deref` is an associated type. `String` implements `AsRef<str>`, `AsRef<Path>`, and so on, but only `Deref<Target = str>`.

The blog post's meandering description the difference between static and dynamic dispatch has no relevance whatsoever.

So basically, Java's generic interfaces are equivalent to Rust's traits with associated types, and Java has no equivalent for a Rust trait with type parameters, at least in terms of this part of the language.

I'm not sure how or if Rust traits can be used as function parameters - can I have a function that takes a parameter of type Iter? Can it take any implementation of Iter than, regardless of what item type that returns? How would I define a function that only accepts iterators that return, say, i32 items?

You'd write it as a type parameter with a type bound. There's a couple of different ways to write it, but one example:

fn foo<I>(it: I) where I : Iterator<Item = i32> {}

> can I have a function that takes a parameter of type Iter?

  fn example<I: Iterator>(iter: I) { ... }
  // or:
  fn example<I>(iter: I) where I: Iterator { ... }
  // or:
  fn example(iter: impl Iterator) { ... }

> Can it take any implementation of Iter than, regardless of what item type that returns?

Yes, in the above example. Then, the item type can be referred to as "<I as Iterator>::Item", or "I::Item" for short, unless you use the "impl Trait" syntax. You can also give the item type a name by giving it its own type parameter:

  fn example<T, I: Iterator<Item = T>>(iter: I) { ... }

> How would I define a function that only accepts iterators that return, say, i32 items?

  fn example<I: Iterator<Item = i32>>(iter: I) { ... }
  // etc., just write Iterator<Item = i32> in place of Iterator

Does that matter for Iterator? You can have

    class FooIterator implements Iterator<Foo>{…}
    class BarIterator implements Iterator<Bar>{…}
    class MyCollection {
        public Iterator<Foo> foos { return new FooIterator(this); };
        public Iterator<Foo> bars { return new BarIterator(this); };
    }

It would matter for Iterable. You cannot have this:

    class MyCollection implements Iterable<Foo>, Iterable<Bar>{…}

, but there, there’s a second problem: in Java, you can’t have overloads that only differ in their return type.

It's not useful to have a type implement Iterator for multiple element types. But in Rust, if Iterator took the element type as a generic parameter, it would be possible. The fact that it's not useful is precisely why Rust makes the element type an associated type instead.

The benefits of using an associated type (compared to using a generic parameter in Rust, not compared to Java) include clarity, possibly improving type inference, and avoiding issues with crate coherence by requiring that the Iterator impl live in the crate that defines the input type, rather than the one that defines the output type.

Associated type:

    pub trait Iterator {
        type Item;
        [...]
    }

vs generic type:

    pub trait Iterator<Item> {}

The associated type version can only be implemented once per MyType.

    impl Iterator for MyType { 
        type Item = i32;
    }

The generic version can be implemented multiple times. For example:

    impl Iterator<String> for MyType
    impl Iterator<i32> for MyType

https://doc.rust-lang.org/book/ch19-03-advanced-traits.html

I understand that part. But the comparison with Java is still bizarre, or perhaps just wrong.

Java has nothing similar to this:

    impl Iterator for MyType { 
        type Item = i32;
    }

If you defined Iterator like this:

  interface Iterator {
    interface Item{}
    public Item next();
    ...
  }

Then Iterator.Item is the same type for all implementations, each implementation doesn't get to define its own type.

Furthermore, a Java type can't implement both Iterator<Integer> and Iterator<String>: it has to implement a single one. So Java's Iterator<T> is in almost all ways equivalent to Rust's Iter, with its one associated type, and not to a Rust BadIter<T>.

And this has nothing to do with how methods are dispatched, it has everything to do with the semantics of their respective type systems.

Java has a pattern that is a superset of this, which is the self-recursive generic type:

    interface Foo<T extends Foo<T>>

    class Bar implements Foo<Bar>

This is used to implement associated-type and Self-type behavior, at the expense of boilerplate. You can have multiple levels of associated types, though, which is murderous on the pinkies (or whatever finger types the angle bracket keys in your layout).

What would be a good example of a type the follows the rule from the article but where the associated type is not the return type?

Good question. Technically, ToOwned counts:

  pub trait ToOwned {
    type Owned: Borrow<Self>;
    fn clone_into(&self, target: &mut Self::Owned) { ... }
  }

Here the `Owned` is technically an input to `clone_into`, but of course semantically it's still an output.

A more subtle one is `StreamExt`:

  pub trait StreamExt: Stream {
    type Item;
    fn map<T, F>(self, f: F) -> Map<Self, F>
       where F: FnMut(Self::Item) -> T,
             Self: Sized { ... }
  }

Here, the associated type `Item` is the input to the mapping function, and since the mapping function is an input to the map function, it is an input-to-an-input - which basically makes it an output. i.e. the stream "outputs" the items into the mapping function. (aka two contravariants make a covariant).

I couldn't find any more direct examples.

It seems weird to me that the response to identifying a part of the language that’s hard for people to use and correctly understand is to assert that we just need to not be afraid of it harder.

To clarify things a bit further, I find it helpful to think of traits as open compile-time functions that input types (including Self) and output both types and functions.

  pub trait Mul<Rhs> {
      type Output;
  
      fn mul(self, rhs: Rhs) -> Self::Output;
  }

This begins the open declaration of the compile-time `Mul` function. It has two inputs: `Rhs` and `Self`. It has two outputs: `Output` and `mul` (the top-level runtime function).

Note that we haven't defined the compile-time `Mul` function yet. We've only opened its definition. It's sort of like writing down the type of a function before we write down its implementation.

The implementation is never written down, though, because it is always the same: a lookup in a table that is constructed at compile-time. Every impl fills in one cell of the compile-time table.

  impl Mul<f32> for i32 {
    type Output = f32;
  
    fn mul(self, rhs: f32) -> Self::Output {
      self as f32 * rhs
    }
  }

This adds a single cell to the `Mul` table. In psuedo-code, it's like we are saying:

  Mul[(i32,f32)] = (Output=f32, mul={self as f32 * rhs})

The cell is a pair of a type and a function. For traits with lots of functions, the cell is going to be mostly functions.

The main thing I'm pointing out (that the author didn't already say) is that `mul={self as f32 * rhs}` is also part of the compile-time table, not just `Output=f32`. The author says that associated types are no more than the return of a type-level function, and I want to clarify that this isn't a metaphor or mental short-hand. Traits ALWAYS HAVE BEEN type-level functions. They input types and output mostly functions. Associated types just allow them to output types in addition to outputting functions. Notice how associated types are defined inside the curly braces of an `impl`, just like the functions are.

Once you realize this, it's all very simple. I think there are a few things that obscure this simplicity from beginners:

1. `Self` is an implicit input to the compile-time function, with its own special syntax, and for many traits it is the ONLY input. When reading a book on rust, the first examples you encounter won't have (other) type parameters, and so it's easy to overlook the fact that traits are compile-time functions.

2. Rust traits are syntactically similar to object-oriented polymorphism, but semantically duals of each other, so experienced OO programmers can jump to wrong conclusions about rust traits. Rust traits are compile-time and universally typed. Object-oriented polymorphism is run-time and existentially typed.

3. Because the trait-as-compile-time-function's implementation is so highly structured (it's just a table), it can actually be run backwards as well as forwards. Like a prolog predicate, there are 2^(#inputs+#outputs) ways to "invoke" it, and the type-inference engine behaves more like a logical language than a functional language, so from a certain perspective associated types can sometimes look like inputs and type parameters can sometimes look like outputs. The reason we call them functions and not merely relations is because they conform to the rule "unique inputs determine unique outputs".

Reply on news.ycombinator.com