ezyang's research log

What I did today. High volume, low context. Sometimes nonsense. (Archive)

Scott Kilpatrick - Backpack: Retrofitting Haskell with Interfaces

Talking about a stronger module system for Haskell, i.e. with (1) interfaces, (2) reuse, (3) recursive linking. Currently Haskell’s module system is weak: implementation depends on implementation, at the module level as well as the package level.

"Why not just use the ML module system?" (i.e. functors) 25-30 years. Signatures and reuse for functors. So the problem is this: functors don’t give recursive linking, and it’s not compatible with weak modules. Also, functors are ill-suited for separate compilation; ML need an additional system of separate compilation.

Key features of Backpack: package level, uses mixins, elaborates into weak Haskell modules, separate typechecking (though not separate compilation, mostly because the existing tools don’t have that anyway.)

(description of modules today, including boot files, which GHC uses to get recursive modules work. http://www.haskell.org/ghc/docs/latest/html/users_guide/separate-compilation.html#mutual-recursion)

Now, packages define a number of “boot-file” like interfaces (generalized).

    package partial-server where
        Socket :: [ -- SIGNATURE! (defined later)
            data SocketT
            open :: Int -> SocketT
        ]
        Server = [ -- traditional module
            import Socket
            data ServerT = ... SocketT ...
        ]

New ‘include’ keyword which dumps bindings of package into scope.

"So now, let’s poke a hole in this"

Instead of functor application causing linking, linking happens automatically (by name). This covers INTERFACES.

REUSE? Well, we can namespace includes (preventing them from trying to be linked together). Shared reuse or “applicativity” of module systems. Backpack can tell when a module hierarchy is the same and only load up one.

RECURSIVE LINKING? Define the interface in one go, and then just include the signature.

Claim: Backpack is a pretty small language (and we can still do module name aliases, thinning (package level import/export lists))

A design goals for semantics: base it on MixML (ICFP’08, subsumes ML module system). But MixML doesn’t work, since it targets LTG. “We’re targeting Haskell, a very simple…” (laughter) Additionally, MixML does not support shared reuse. MixML is pretty complicated.

Another goal: retrofit to Haskell; compile semantics to Haskell modules. Well, Haskell modules are like abstract data types.

Idea: Represent “names” as “dependency graphs”. So have a module identity language, which can accomodate holes, module expressions and recursive bindings. (EZY: Is it possible to have iso but not structurally identical dep graphs?) Necessary for type system and elaboration. (EZY: nominal versus structural…)

Compared MixML linking and Backpack linking

Elaboration: code is duplicated (C++); imports refer to particular identities.

(EZY: I’m pretty sure module identity seems related to issues of naming that show up in ML systems; it’s simple, but is it adequate?)

53-page appendix

BIG PROBLEM: type classes (since it’s Haskell-specific; claim, this would work for other languages). (Also, integrate this with Cabal.)

Claim: targeting existing weak module languages is interesting (scientifically)

Q: (Oleg) Of course the Haskell module system, is very weak. But Haskell has many other features like typeclasses. When you add typeclasses, you can implement all of your examples, in existing Haskell, as it is. Plus separate compilation. It’s interesting to see how it relates to the formalization, but I don’t want to see Haskell slighted; it has a strong module system. The core idea is each interface is defined by the type class, put it in a separate module, etc.

A: I have two comments. First, a lot of these approaches don’t talk about type classes that have other type classes? The second, is that it makes the same mistake of OOP, of combining the core language with the module language. Also, at the package level, I haven’t seen anything that does it at the package level.

Q: Well, I agree theoretically it’s nice to separate concerns. But if you want to play with modularity in Haskell, it’s already possible. Also, modules refer to type-classes? It’s possible. The example I implemented is similar to your example. It’s on scalac. It’s a very complex example and all possible.

Q: (Wadler) I buy the conclusion on the last slide. One nice result, here is something like MixML but simpler. Do you actually follow through in the paper? Is it more powerful? Less powerful?

A: It’s really hard to compare, because the core languages are different. We have a detailed comparison of simplified parts of the MixML, e.g. for the

Q: Well, let’s just ask Derek!

A: (Derek) Uhhhh, it depends. It depends on the goal. The goal is to retrofit Haskell.

Q: If I’m starting from scratch?

A: Well, I wouldn’t start with a weak module system.

Q: Well, can I use this system instead of a weak module system?

A: Well, can you take these ideas and backport them to MixML. We haven’t tried doing that. I’d be interested.

Q: Bob Harper is not here to stick up for himself. When you were tlaking about why not functors, and one reason was, you can’t take two functors and tie them together recursively, I’m pretty sure that’s wrong. Why do you say that?

A: Well, the recursion is all about mutually recursive definitions. rec mod A = B, and B = A. But they’re tied to the same compilation unit.

Q: Well, in the original paper, we defined the two things recursively; we did it separately as functors and then wrote a little glue code to put them together.

Dreyer: The problem is the double-vision problem.

Q: Well, that is far more nuanced complaint. And didn’t you write a thesis on how to solve it?

A: Well, this is another way, and it’s simpler.