Parameterized Modules

[robinheghan]

We have previously discussed why Gren should support ad-hoc polymorphism (#37). This issue explores parameterized modules as a potential mechanism to deliver that feature.

Modules as a first class construct

The basic idea is to allow modules to depend on a reference to another module that has a specific signature, which can be specified at the import site.

This might best be explained through an example. Keep in mind that the following syntax is not a proposal, just something I made up along the way in order to explain this feature.

Let's say that we're going to implement a Dict type, and would like it to accept any type, as long as that type is comparable.

We could then define a module signature by creating a Comparable.gren module with the following content:

signature module Comparable

type alias T

comparable : T -> T -> Order

A module signature is a module that only contains signatures or names, no implementations.

This module can then be used in a Dict module like:

module Dict requires (Comparable) exposing (..)

type Dict Comparable.T v = ...

get : Comparable.T -> Dict Comparable.T v -> Maybe v
get key dict =
  case Comparable.compare key dict.key of
        ...

With this definition, you can import a Dict specialised to your specific type, like so:

module MyApp exposing (..)

import MyType
import Dict(MyType where { T = MyType.MyType }) as MyTypeDict

The above would only compile if MyType has a properly defined compare function defined.

The where { T = MyType.MyType } syntax is meant to give people the option "routing" some implementation to a value specified int he signature, in case the names don't match up. There are probably other ways of solving this that doesn't require as much boilerplate at the import site, but the examples above or only meant to get the idea across, not as a an actual proposal.

Benefits

The above scheme enables more flexibility in the Gren system, in that you can write code that works with modules you don't even know about, as long as they fulfil the signature you need.

At the same time, all modules used in such a way will be known at compile time, so it's possible to generate code in a way which avoids dynamic resolution entirely, meaning you don't sacrifice performance to use this feature.

Another benefit with this approach is that it doesn't require the author of a module to explicitly implement a signature. In other words, you can write a signature definition, and have those work with modules you haven't written and have no control over.

Does this support everything we want?

I'm now going to go through each section in #37 and see how this feature answers to each case.

Polymorphic functions and polymorphic data structures

The example above already shows how parametric modules solves the case of polymorphic data structures. The only downside is some added complexity at the import site, and that you'll need to import a parametric module once per unique set of parameters.

For single polymorphic functions, like Array.sort this might not be ideal.

It would be unreasonable for Array to require a Comparable module, when it's only really required for the sorting functions. It also feels a bit much to separate the sorting functions into it's own ArraySort module, or similar.

Of course, in these cases, you could always change the functions to take in the required functions as arguments instead, like Array.sortWith.

Magic functions

Parametric modules does little to serve as an implementation for "magic functions".

It would feel overly cumbersome to import operators like == using parametric modules every time you'd want to check the structural equality of two values, for example.

Of course, one could argue that such functions should remain magic, as those functions are typically not functions you'd want to implement yourself most of the time anyway. Or at the very least, that a different scheme should be explored for making these particular functions "better".

Mathy operators

Gren's math operators (+, -, * etc.) are currently polymorphic and work for both Int and Float.

Parametric modules can work here. We could change the definition of Gren's current math operators to rely on parametric modules, and have a default import of import MathOperators(Int) exposing ((+), (-), (*), ..). This default import might then be allowed to be overridden, so that people could "override" these operators to fit their own custom number types.

It would make it impossible to use the same operator for different types within the same module, but that might be a good thing from a readability perspective?

Effect modules

Parametric modules can be used to define the signature of effect modules, which could then be a little bit of logic we could remove from the compiler. This would then be coupled by a built-in API for initialising effect modules with a given signature.

Conclusion

Parametric modules answers some of the use cases listed in #37 quite well, but not all of them.

What I like about parametric modules is that it's made clear where implementations come from, and that you don't have to sacrifice performance to make use of it.

It does require some extra boilerplate at the use site though, but that's a price I'm willing to pay. There are worse things than being explicit...

[besquared]

What's an example implementation of MyType look like in this scenario?

[robinheghan]

module MyType exposing (MyType, compare)

type MyType =
    MyType String

compare : MyType -> MyType -> Order
compare (MyType str1) (MyType str2) =
    String.compare str1 str2

[besquared]

There's one other option I hadn't seen in #37 or here which is to have the signature function defined on the type directly. This is probably most similar to things like clojure protocols, rust traits, and the other similar systems. Signature modules play that part in this system. It would require a new declaration type but you could imagine:

module MyType exposing (MyType)

type MyType = MyType String

impl Comparable where { T = MyType }
  compare (MyType str1) (MyType str2) =
    String.compare str1 str2

It kind of inverts the some of the paradigm that exists in the language and so maybe doesn't really "fit in" in some sense.

For mathy operators and magic functions the rust compiler uses this system by labeling some traits as "magic traits" instead. If you implement things like std::ops::Add for a type (struct in rust) then the compiler will use that implementation during type checking and when monomorphizing + in expressions.

There's a lot I don't like about this too. You can't call compare separately (maybe?). It's unclear where Comparable comes from in this example. Presumably you'd have to import it but it's not quite an import like normal modules.

[robinheghan]

yeah, so what you're describing is the more common option for implementing ad-hoc polymorphism, and a seperate issue may be created on that in the future.

In Clojure, the protocol functions exist both in the module that defines the protocol, and in the module which implements the protocol on some type. Using the function defined along the protocol is the recomended approach.

The benefit of the approach outlined in this issue is that the functions isn't strictly bound to the type, so it's easy to provide a different comparison function for String, without having to wrap the String in my own custom type. This comes at the costof some extra syntax at the import site, though, so it's not a clear win.

[besquared]

In the first example above it's unclear to me how the compiler will find compare in MyType.gren since the only information it is provided is T = MyType.MyType. In what way is compare associated with MyType? How does the Dict module know how to find that function?

[besquared]

I see now, it's MyType where { T = MyType.MyType } so the module implements compare and we just need to tell it which type it implements compare for w.r.t. this dictionary specifically. We're giving it all of the instructions to stitch together the types and implementations.

It seems to me that this can be added separately from other ad-hoc polymorphism systems or separately from them. I feel like multiple systems could work together although it does introduce quite a bit of complexity, especially for new users.

[robinheghan]

I see now, it's MyType where { T = MyType.MyType } so the module implements compare and we just need to tell it which type it implements compare for w.r.t. this dictionary specifically. We're giving it all of the instructions to stitch together the types and implementations.

Exactly right.

It seems to me that this can be added separately from other ad-hoc polymorphism systems or separately from them. I feel like multiple systems could work together although it does introduce quite a bit of complexity, especially for new users.

Yeah. So, they could work together, but from a complexity standpoint it would be preferable to only have one.

[lue-bird]

Maybe it would be a bit simpler if we don't require a module alongside the type and just supply all necessary operations directly.

• as the module header:

  DictOrdered :
       ({ a : key, b : key } -> Order)
    -> (, map
        , element , elementAlter , elementRemove
        , insert
       )
  DictOrdered order =
  ..we can use `key` in types here and `order` values of that type..

• in a module that uses DictOrdered:

  ByUserNameHistory =
    import DictOrdered (Order.array (Order.by .name Order.string))
  
  Model =
    { users : ByUserNameHistory.Dict User
    , ... }

Together with an API like elm-linear-direction: Order, you wouldn't be required

• to create a new module for every key (which could be any array, record, choice, ...)
• to necessarily require the needed functions inside the type's module (like hash etc. which might very well not be present in every module)

more details in gren-language-design-discussions

Also, take the dict thing as an example. Solutions like key -> ComparableThatCanCasedOnAndHashed are actually probably better.

[robinheghan]

We don't actually require the type. The where syntax is proposed to allow some flexibility in the naming of types.

However, should this be implemented I fully expect all core types and packages to implement a type alias T (or whatever default type name we go for) so that in most cases you just do import Dict(String).

What you are proposing seems to require runtime resolution. Which is fine, and certainly very flexible, but the benefit of the module approach is that everything can be resolved at compile time. Meaning it allows for optimizations without relying on the JS JIT to make things fast.

Second point is that I believe your suggestion, while very flexible, would also quickly become cumbersome if a module would require more than a single function.

This is not me dismissing your proposal, just listing up the counter-arguments as I see them :)

[lue-bird]

Re: requiring runtime resolution: Get me on the same page as you (I've never used parameterized modules): How is supplying functions directly different from supplying them from a module?

[robinheghan]

Hmm, thinking about it more, it should be possible to do all the same analysis at compile time using your scheme, as I assume all function references have to be resolvable.

It would require more work than simply referencing function inside a specific module, though. For instance, figuring out if Order.array (Order.by .name Order.string) == Order.array Order.orderByName requires more work than figuring out if the .array function of Dict(Order) equals Dict(Order). You just have to look up the names, and not analyze the function.

Now, this might not matter, depending on how all of this is compiled. Monomorphism, for instance, would be very simple with minimal codegen when passing modules around, harder when passing individual functions.

[lue-bird]

Another idea demonstrated in an alternative to elm's Dict: KeySet which requires neither comparable nor any complex extra language features

Using the module system to hide constructors for a tag

module User exposing (..., ByName, byName)

type Name
    = Name

byName : Keys User ByName N1
byName =
    Keys.for (\name -> { name = name })
        |> Keys.by .name (Map.tag Name .name) (String.Order....)

type alias ByName = { name : Keys.Key ... }

allowing only that module to define the ordering associated with the structure

import User.By.Name

users : KeySet User User.ByName
users =
    KeySet.fromList User.byName [ ... ]

users |> KeySet.element User.byName "Robin"

[robinheghan]

@lue-bird That's interesting! Thanks for sharing.