[HN Gopher] Fear Not the Association of Types
___________________________________________________________________
Fear Not the Association of Types
Author : todsacerdoti
Score : 37 points
Date : 2024-08-18 16:39 UTC (6 hours ago)
(HTM) web link (gavinleroy.com)
(TXT) w3m dump (gavinleroy.com)
| tsimionescu wrote:
| 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).
| mmoskal wrote:
| 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.
| withoutboats3 wrote:
| 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.
| tsimionescu wrote:
| 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?
| AlotOfReading wrote:
| 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> {}
| LegionMammal978 wrote:
| > 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
| bombela wrote:
| 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
| tsimionescu wrote:
| 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.
| tadfisher wrote:
| 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).
| sciolizer wrote:
| 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".
| weinzierl wrote:
| 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?
___________________________________________________________________
(page generated 2024-08-18 23:00 UTC)