4 ms·

Nice examples - you can also have languages (like SML) where monomorphization is simply an implementation detail. Some compilers (e.g., MLton) perform monomorph

Nice examples - you can also have languages (like SML) where monomorphization is simply an implementation detail. Some compilers (e.g., MLton) perform monomorphization and others don't.

codeflo 4y ago
I only recently realized that certain type system features, like polymorphic recursion, make monomorphization impossible in the general case. In Haskell for example, it’s by necessity only an optimization that’s used where applicable, and not the general strategy.
yakubin 4y ago
That depends on what you mean. SML has "polymorphism" boiling down to being able to plug an arbitrary type in some places, which is denoted like 'a. But when people talk about generics, they more often talk about C++ templates, Java generics, Rust traits, etc. whose SML equivalent are signatures, structs and functors. Signatures are a bit like Rust traits, structs are a bit like Rust implementations of traits, whereas functors are like Rust's "templates", i.e. wherever you swap angle brackets to parametrise something with types constrained by traits, or values constrained by types. Except in Rust this parametrisation can be slapped on a bunch of things. It can be on structs, on functions, on traits, on implementations of traits etc. In SML you need to group all the "parametrised" things into a struct (and a corresponding signature), which is going to be returned by a functor. And now the thing is: with transparent signature ascriptions, functors are monomorphised in SML, instead of everything being hidden behind signatures (as is in the case of Rust with traits when you use dyn), which has semantic consequences. E.g. a struct returned by a functor may contain a type. You can't perform proper type-checking without monomorphising, because you don't know what the exact type is. E.g. in the following program, the final line couldn't be type-checked without monomorphisation: signature ITERABLE = sig type ElemT type SrcT val new_iter: SrcT -> unit -> ElemT option end signature LIST_ELEM_TYPE = sig type T end functor ListIterFun (ListElemType: LIST_ELEM_TYPE): ITERABLE = struct type ElemT = ListElemType.T type SrcT = ElemT list fun new_iter l = let val lr = ref l in fn () => case !lr of nil => NONE | (x::xs) => (lr := xs; SOME x) end end structure IntElemType: LIST_ELEM_TYPE = struct type T = int end structure IntListIter = ListIterFun(IntElemType) val next = IntListIter.new_iter [1, 2, 3, 4, 5] If I change the signature ascription on ListIterFun to an opaque ascription (:> ITERABLE), the final line won't type-check, because it's not obvious from the signature, that ElemT is int. So transparent signature ascriptions require monomorphisation (Rust traits without dyn), and opaque signature ascriptions free the compiler from having to do monomorphisation (Rust traits with dyn*). There was a lot of discussion of this issue when Go was settling on a design for its generics, under the phrase "reified generics".

Nice examples - you can also have languages (like SML) where monomorphization is simply an implementation detail. Some compilers (e.g., MLton) perform monomorphization and others don't.

codeflo 4y ago

I only recently realized that certain type system features, like polymorphic recursion, make monomorphization impossible in the general case. In Haskell for example, it’s by necessity only an optimization that’s used where applicable, and not the general strategy.

yakubin 4y ago

That depends on what you mean. SML has "polymorphism" boiling down to being able to plug an arbitrary type in some places, which is denoted like 'a. But when people talk about generics, they more often talk about C++ templates, Java generics, Rust traits, etc. whose SML equivalent are signatures, structs and functors. Signatures are a bit like Rust traits, structs are a bit like Rust implementations of traits, whereas functors are like Rust's "templates", i.e. wherever you swap angle brackets to parametrise something with types constrained by traits, or values constrained by types. Except in Rust this parametrisation can be slapped on a bunch of things. It can be on structs, on functions, on traits, on implementations of traits etc. In SML you need to group all the "parametrised" things into a struct (and a corresponding signature), which is going to be returned by a functor. And now the thing is: with transparent signature ascriptions, functors are monomorphised in SML, instead of everything being hidden behind signatures (as is in the case of Rust with traits when you use dyn), which has semantic consequences. E.g. a struct returned by a functor may contain a type. You can't perform proper type-checking without monomorphising, because you don't know what the exact type is. E.g. in the following program, the final line couldn't be type-checked without monomorphisation: signature ITERABLE = sig type ElemT type SrcT val new_iter: SrcT -> unit -> ElemT option end signature LIST_ELEM_TYPE = sig type T end functor ListIterFun (ListElemType: LIST_ELEM_TYPE): ITERABLE = struct type ElemT = ListElemType.T type SrcT = ElemT list fun new_iter l = let val lr = ref l in fn () => case !lr of nil => NONE | (x::xs) => (lr := xs; SOME x) end end structure IntElemType: LIST_ELEM_TYPE = struct type T = int end structure IntListIter = ListIterFun(IntElemType) val next = IntListIter.new_iter [1, 2, 3, 4, 5] If I change the signature ascription on ListIterFun to an opaque ascription (:> ITERABLE), the final line won't type-check, because it's not obvious from the signature, that ElemT is int. So transparent signature ascriptions require monomorphisation (Rust traits without dyn), and opaque signature ascriptions free the compiler from having to do monomorphisation (Rust traits with dyn*). There was a lot of discussion of this issue when Go was settling on a design for its generics, under the phrase "reified generics".