Comment by jez | Hacker News Reader

Comment by jez | Hacker News Reader

Parent Full thread

Grayson's very first answer to "what's next" is "ML modules," a language feature probably few people have experienced first hand. We're talking about ML-style modules here, which are quite precisely defined alongside a language (as opposed to a "module" as more commonly exists in a language, which is just a heap of somewhat related identifiers). ML modules can be found in the mainstream ML family languages (Standard ML, Ocaml) as well as some lesser known languages (1ML, Manticore, RAML, and many more).

It's really hard to do justice explaining how amazing modules are. They capture the essence of abstraction incredibly well, giving you plenty of expressive power (alongside an equally powerful type system). Importantly, they compose; you can write functions from modules to modules!

(This is even more impressive than you think: modules have runtime (dynamic) AND compile time (static) components. You've certainly written functions on runtime values before, and you may have even written functions on static types before. But have you written one function that operates on both a static and a dynamic thing at the same time? And what kind of power does this give you? Basically, creating abstractions is effortless.)

To learn more, I recommend you read Danny Gratzer's "A Crash Course on ML Modules"[1]. It's a good jumping off point. From there, try your hand at learning SML or Ocaml and tinker. ML modules are great!

[1]: https://jozefg.bitbucket.io/posts/2015-01-08-modules.html

1ML just shows that advanced (first-class) ML modules are really just System F_omega. That's just barely more than Haskell! More languages need to expose it nicely. But we already have most if not all the technology we need to make them efficient and worthwhile, vs just possible. This isn't a research problem. This is a design/HCI problem.

ML modules are great, but I'm not convinced that making them first-class (1ML) will be equally great. ML hits a sweet spot between automation (full type inference) and expressiveness that is only possible because the type language is first-order. This is IMO the point that most extensions on top of Hindley-Milner completely miss.

So, if anything, what I'd like to see is a dependently typed language whose type language is a first-order, computation-free (no non-constructor function application) subset of the value language.

The 1ML papers discuss this, ML implementations in reality are already incomplete with regard to Hindley-Milner, a quote:

"We show how Damas/Milner-style type inference can be integrated into such a language; it is incomplete, but only in ways that are already present in existing ML implementations."

1ML is a conservative extension of HM - all valid ML programs are typable in 1ML without extra annotations.

Furthermore, OCaml essentially already has first-class modules - just the syntax is much more awkward than is possible with 1ML.

https://news.ycombinator.com/item?id=15053706

Do you think Backpack solved that problem for Haskell?

One of the things Graydon doesn't mention is versioning. Supporting multiple different versions of the same module at the same time is a wee-bit hairy and has only been done well enough (OSGi) to give an idea of the potential.

Abstract types are a fundamental part of modularity (at least in the ML sense), and it's not clear how a module system that allows “multiple versions of the same module at the same time” should handle the abstract type components (not to be confused with abstract classes, which are just uninstantiatable classes) of such versions.

In ML, you can have multiple modules (structures) conforming to a common interface (signature), but their abstract type components are in general not identifiable - with good reason. For instance, let's say you have an API for heaps:

    (* For algorithmic reasons, it is useful to distinguish between
     * heaps whose underlying data structure is a tree (e.g. pairing
     * heaps) and heaps whose underlying data structure is a forest
     * (e.g. binomial heaps). I will only use the former in this
     * example. *)
    signature TREE_HEAP :
    sig
      type key (* abstract *)
      type 'a entry = key * 'a
      type 'a heap (* again abstract *)
      val pure : 'a entry -> 'a heap
      val head : 'a heap -> 'a entry
      val tail : 'a heap -> 'a heap option
      val merge : 'a heap * 'a heap -> 'a heap
    end

Of course, there are multiple ways to implement this API. For example, pairing heaps and Brodal-Okasaki's asymptotically optimal heaps:

    signature ORD_KEY :
    sig
      type key
      val <= : key * key -> bool
    end
    
    functor PairingHeap (K : ORD_KEY) : TREE_HEAP =
    struct
      (* blah blah blah *)
    end
    
    functor BrodalOkasakiHeap (K : ORD_KEY) : TREE_HEAP =
    struct
      (* blah blah blah *)
    end
    
    structure H1 = PairingHeap (IntKey)
    structure H2 = BrodalOkasakiHeap (IntKey)

However, `H1.heap` and `H2.heap` are two different abstract types. That is, for example, you can't attempt to merge a pairing heap with a Brodal-Okasaki heap - that would be a (static!) type error.

That is indeed a problem, and unifying abstract types is probably not even meaningful, much less possible.

But, can you use multiple implementations of the TREE_HEAP in the same code? (I think so, but it's been a long while.) Can you use two versions of BrodalOkasakiHeap in the same code? (Probably not.) Can module A use one version of BrodalOkasakiHeap while module B uses another, in the same program?

> But, can you use multiple implementations of TREE_HEAP in the same code?

Yes.

> Can you use two versions of BrodalOkasakiHeap in the same code?

ML doesn't have a notion of “version”, but of course you can provide two different implementations of the same API if you so desire. However, these implementations, while interchangeable (a client can swap either implementation with the other, as long as this is done consistently), are not compatible (a client can't treat both implementations as if they were the same).

As far as I know, most of the version work comes from Java-land, particularly OSGi, along with "semantic versioning".

For example, the difference between a minor version increment and a micro version increment is whether client code implements an interface provided by the module or uses an implementation coming from the module. (If you use an interface that has had methods added, you won't know about those methods; but if you implement the interface, you have to provide implementations for those methods.)

So, for example, if you are using "modules" A and B, where A uses a module C and B uses C' (which has a bumped micro number), you won't have a problem simultaneously using an instance c from C (returned by A) and an instance c' from C' (returned by B).

On the other hand, if you create an instance c (as from C) and pass it to C' through B, things don't work out. (Execution blows up. Did I mention that the rest of Java's modularization story sucks?)

Type soundness is one of the main attraction points to using a language like Standard ML, so, for an MLer, if versioning support requires sacrificing type soundness, then it's a no-go.

I may be missing something here but isn't this the same Graydon that wrote the Rust bootstrap compiler in Ocaml? Wouldn't that have exposed him to the ML Modules?

Graydon is clearly aware and links to some relevant stuff in that post, I assume this is just an elaboration for other commenters' sake.

Yep, in case anyone thinks "Module systems are solved: use npm"

Reply on news.ycombinator.com