6 ms·

Exotic Programming Ideas: Module Systems

157 points by rwosync 6y ago

cultus 6y ago
Great read. It's too bad modules are pretty much an afterthought in most langs. I really like research language 1ML's approach to modules[0]. This allows monomorphic types to be treated like values, avoiding all of OCaml's module syntax (which can be a bit complex and verbose). https://people.mpi-sws.org/~rossberg/1ml/1ml-extended.pdf https://people.mpi-sws.org/~rossberg/1ml/1ml-extended.pdf
- eterps 6y ago
  Is there a 'readable' code sample of how that would work?
  - cultus 6y ago
    Not much I don't think. This has a few examples: https://github.com/rossberg/1ml https://github.com/rossberg/1ml There isn't special module syntax. Modules are more-or-less just structs, and the structs can contain types.
  - eterps 6y ago
    I just found this post: https://shonfeder.github.io/themata/programming/notes-on-1ml.html https://shonfeder.github.io/themata/programming/notes-on-1ml...
OkGoDoIt 6y ago
Other than the syntax, I’m not sure I understand how this is different from any other object-oriented class definition. I suppose the ability to project the module into the local or top-level scope, but that seems more like syntactic sugar than anything meaningful. What am I missing here?
- cultus 6y ago
  Module functors and first-class modules are probably the big feature. Those are more akin to allowing functions between classes, rather than just objects.
- Someone 6y ago
  A module, by definition, is a singleton (for parametrized modules, a “once per type” object) C has (unparametrized) modules, calling them “compilation unit”.
- sparkie 6y ago
  Except where first-class modules are used, the application of a functor to a module happens at at (or before) compile-time. You can have a fully resolved type before runtime, but which can still be abstract at design time. They can be seen as a zero-cost abstraction. Modules are structurally typed, so the more typical sub-typing behavior expected from mainstream OOP languages is not applicable to them.
- dan-robertson 6y ago
  Module signatures may contain types. So you can write a signature like: module type VectorSpace = sig module Field : Field type t val zero : t val (+) : t * t -> t val (*) : Field.t * t -> t end In OOP it becomes hard to write an interface like this simple example, and more complex examples become harder still.
  - horsawlarway 6y ago
    Can you give an example of the value this would provide that isn't provided by generics?
    - spopejoy 6y ago
      One thing the example shows is the classic problem with OO's mechanism, namely binary functions. For a given class, something like `+` is impossible to implement elegantly, it has to bias one operand over the other -- after any syntactic sugar, it's always `arg1.op(arg2)`. Module functors resemble true ADTs more, in that they do not dispatch from a live instance of the datatype.
pjmlp 6y ago
> Modules as a language feature were first developed in Modula-2 and Pascal, which were developed as a way to demarcate units of compilation. Actually Mesa.
- Rochus 6y ago
  Right. Wirth developed Modula after his first PARC sabbatical, where he worked with the Alto and Mesa. Modula supported even nested modules. And Pascal didn't have modules at all.
Drup 6y ago
Amusingly, I was precisely working today on extra-nice error messages for module type errors in OCaml. :) My reaction to the title was "But they are not exotic, I use them every day!" It's definitely the feature I miss the most every time I work in other languages, even presumable "advanced" ones, like Haskell. One notable attempt to add them elsewhere is "modular C"[1]. [1]: http://cmod.gforge.inria.fr/ http://cmod.gforge.inria.fr/
- jolux 6y ago
  Have you heard of Backpack for Haskell? https://gitlab.haskell.org/ghc/ghc/-/wikis/backpack https://gitlab.haskell.org/ghc/ghc/-/wikis/backpack
miki123211 6y ago
Zig's compile time execution lets you do similar things I believe. In Zig, structs and modules are equivalent, and type declarations can be manipulated at compile time just like any other value. That, among other things[1], lets you write: fn LinkedList(comptime T: type) type { return struct { pub const Node = struct { prev: ?*Node, next: ?*Node, data: T, }; first: ?*Node, last: ?*Node, len: usize, }; } I wonder if there's anything that OCaml functors can do but this can't. [1] for example, you can implement a very efficient printf that gives an error at compile time when the format string is invalid. See https://ziglang.org/documentation/master/#comptime https://ziglang.org/documentation/master/#comptime for more details.
- eterps 6y ago
  Nice! I also found these examples: https://www.reddit.com/r/Zig/comments/in8d6e/til_that_imported_zig_files_can_be_instantiated/ https://www.reddit.com/r/Zig/comments/in8d6e/til_that_import...
- a-nikolaev 6y ago
  One thing is that OCaml modules are first class objects, so can be constructed at runtime and passed around as variables. But this Zig example, I think, will cover the most common case of functors for creating generics. (I'm also not sure if Zig does compile-time check if the type T is compatible with LinkedList. OCaml does this type of check, making sure the signature of T fits the requirement of the functor LinkedList. The module T may have certain functions, for example a compare function associated with T to ensure sorting of the elements in your data structure.)
  - dilap 6y ago
    (Not even close to a zig expert, but I've been playing with it a little bit, find it very interesting, and think what I'm about to say is correct:) The zig equivalent of a module, a struct, is also a first-class object in zig, so should be the same as OCaml there. However, Zig does not have anything like a signature -- in that sense, it's "dynamically typed" at compile time (i.e., like type args to C++'s templates, however not nearly as bad because the errors you get are immediate and understandable -- think of it as more like "I fucked up the types and got a python-style error" than I "I fucked up the types and got a C++ templates error").
gnulinux 6y ago
I feel like I keep saying this every single PLT-related HN thread. Sorry for preaching, but I just can't resist. I think Agda is an excellent programming language, and it's a joy to write anything in. Its learning curve is steep at the beginning but once you gain experience how to write coinfinite programs, it's such a joy. I think its module system is a huge bonus. It makes code a lot easier to organize and reason. It forces toplevel module X to be defined in X.agda so there is no argument what the module should be named or where it should be found.
js8 6y ago
Looking forward to the series! I hope, in one of his "presents", he talks about Lisp conditions and signals, which have also inspired PL/I conditions, and go really back to the idea of an error handler in an operating system. Unfortunately, Unix (and C) really botched signals by limiting their number in the user space (in particular, they cannot be stacked), and so the idea largely fell out of favor as an error-handling paradigm.
- prirun 6y ago
  I worked for Prime (minicomputers) as a youngster in the early 80's. They supported PL/I and many parts of the OS (Primos) were written in a systems dialect of PL/I they called PLP. The PL/I condition mechanism was an integral part of the OS and fault handling. For example, a floating point exception or integer overflow was detected by hardware, caused a fault, the information from the fault was packaged into a condition frame (an extended stack frame), and a condition was raised. The OS looked backward through the stack looking for an "onunit" (aka condition handler) that handled this condition - basically like try & except. Condition handlers were very flexible, with the option to partially handle the condition then let it continue with older frames, ignore the condition in this handler and let it continue, or completely handle it. If no running program had a handler for a condition, the default OS handler would run, which often raised a new condition and printed an error message. If the problem causing the error was corrected (for example, some files were deleted from a full disk), you could use the REN (re-enter) command to return from the disk full condition and the system call causing the condition would be automatically re-tried, sort of like when EINTR occurs on a system call and it has to be (manually) retried. Instead of using numbers, conditions had arbitrary names and arbitrary data could be associated with a condition. In hindsight it was very similar to Python's try/except/finally error handling mechanism. There was a condition called "cleanup$", which was executed whenever a procedure was aborted because of a stack unwind to allow it to close files, delete temp files, etc. I wrote an emulator for the Prime and you can see all this with: telnet em.prirun.com 8001 There are all kinds of manuals online too, including a full PL/I implementation, all from the 80's and early 90's.
jlrubin 6y ago
You can do something similar in Rust to ML modules using traits and generic impls as module functors! https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=8bebb69fa7898b13c731ccef158c0e4b https://play.rust-lang.org/?version=stable&mode=debug&editio... This can be really useful especially as traits with differing concrete types diverge, you can create a unified interface trait object to allow trait objects for things like container classes.
horsawlarway 6y ago
Coming in without much OCaml experience, I don't really think this is a great demonstration of why this construct has value. I don't really want to read a long form description of the OCaml implementation of modules. I want a comparison to the languages he dismissed at the beginning of the article, and a discussion of why this feature has some value that isn't provided by those languages. Basically - This feels like a different take on generics to me. There might be a lot of value in how this is implemented when compared to generics in a language like Java/C#/Typescript, but I didn't find that content anywhere in the article...
- zcesur 6y ago
 Say you'd like to have an interface for things that are 'mappable'. For example, for arrays we could write: interface Mappable<Array> { map<A, B>(f: (a: A) => B, fa: Array<A>): Array } Likewise, for `Promise`s we could write: interface Mappable<Promise> { map<A, B>(f: (a: A) => B, fa: Promise<A>): Promise } But in order to generalize this interface to an arbitrary type constructor such that `F: * -> *`, we would need to write interface Mappable<F> { map<A, B>(f: (a: A) => B, fa: ?): ? } which is not possible in TypeScript since it does not support higher-kinded types or type parameters that take type parameters or parametrized modules.
 - karmakaze 6y ago
 Not possible, but an approximation: interface Mappable, T> { flatMap(f: (x: T) => Mappable<P, U>): Mappable<P, U>; } class Maybe<T> implements Mappable<Maybe<unknown>, T> { x: T | undefined; public flatMap(f: (x: T) => Maybe): Maybe { if (this.x) { return f(this.x); } return Maybe.nothing(); } }
 - zcesur 6y ago
 Yes, in fact this reminds me of the HKT implementation[1] found in fp-ts[2][3] interface HKT<F, A> { _URI: F _A: A } interface Mappable<F> { map<A, B>(f: (a: A) => B, fa: HKT<F, A>): HKT<F, B> } where F is a unique identifier representing the type constructor and A its type parameter. [1]: https://www.cl.cam.ac.uk/~jdy22/papers/lightweight-higher-kinded-polymorphism.pdf https://www.cl.cam.ac.uk/~jdy22/papers/lightweight-higher-ki... [2]: https://github.com/gcanti/fp-ts https://github.com/gcanti/fp-ts [3]: https://gist.github.com/gcanti/2b455c5008c2e1674ab3e8d5790cdad5 https://gist.github.com/gcanti/2b455c5008c2e1674ab3e8d5790cd...
shalabhc 6y ago
On the topic of modules, I recommend reading about modules in Newspeak: https://bracha.org/newspeak-modules.pdf https://bracha.org/newspeak-modules.pdf Modules (which are just top level classes and contain nested classes) have no import statement and no hard linked external dependencies. When you instantiate the module (~class) you pass in dependencies it needs.
ProfSarkov 6y ago
Nice (altered) Anna Karenina quote.
jandrese 6y ago
One thing I like about Perl is the module system. A big helper is when the module interface uses named parameters and has sensible defaults for unspecified parameters. This allows the module designer to add features without breaking existing code and makes it easier for someone to integrate the module in the first place. Having the documentation built into the module itself is also a huge win.
flavious 6y ago
I'm not your goto java guy, but the module system of java and how modules can provide implementations for interfaces is really great.
ellis0n 6y ago
Exotic Modules System looks like new C++

157 points by rwosync 6y ago

Great read. It's too bad modules are pretty much an afterthought in most langs. I really like research language 1ML's approach to modules[0]. This allows monomorphic types to be treated like values, avoiding all of OCaml's module syntax (which can be a bit complex and verbose). https://people.mpi-sws.org/~rossberg/1ml/1ml-extended.pdf https://people.mpi-sws.org/~rossberg/1ml/1ml-extended.pdf

eterps 6y ago
Is there a 'readable' code sample of how that would work?
- cultus 6y ago
  Not much I don't think. This has a few examples: https://github.com/rossberg/1ml https://github.com/rossberg/1ml There isn't special module syntax. Modules are more-or-less just structs, and the structs can contain types.
- eterps 6y ago
  I just found this post: https://shonfeder.github.io/themata/programming/notes-on-1ml.html https://shonfeder.github.io/themata/programming/notes-on-1ml...

OkGoDoIt 6y ago

Other than the syntax, I’m not sure I understand how this is different from any other object-oriented class definition. I suppose the ability to project the module into the local or top-level scope, but that seems more like syntactic sugar than anything meaningful. What am I missing here?

cultus 6y ago
Module functors and first-class modules are probably the big feature. Those are more akin to allowing functions between classes, rather than just objects.
Someone 6y ago
A module, by definition, is a singleton (for parametrized modules, a “once per type” object) C has (unparametrized) modules, calling them “compilation unit”.
sparkie 6y ago
Except where first-class modules are used, the application of a functor to a module happens at at (or before) compile-time. You can have a fully resolved type before runtime, but which can still be abstract at design time. They can be seen as a zero-cost abstraction. Modules are structurally typed, so the more typical sub-typing behavior expected from mainstream OOP languages is not applicable to them.
dan-robertson 6y ago
Module signatures may contain types. So you can write a signature like: module type VectorSpace = sig module Field : Field type t val zero : t val (+) : t * t -> t val (*) : Field.t * t -> t end In OOP it becomes hard to write an interface like this simple example, and more complex examples become harder still.
- horsawlarway 6y ago
  Can you give an example of the value this would provide that isn't provided by generics?
  - spopejoy 6y ago
    One thing the example shows is the classic problem with OO's mechanism, namely binary functions. For a given class, something like `+` is impossible to implement elegantly, it has to bias one operand over the other -- after any syntactic sugar, it's always `arg1.op(arg2)`. Module functors resemble true ADTs more, in that they do not dispatch from a live instance of the datatype.

pjmlp 6y ago

> Modules as a language feature were first developed in Modula-2 and Pascal, which were developed as a way to demarcate units of compilation. Actually Mesa.

Rochus 6y ago
Right. Wirth developed Modula after his first PARC sabbatical, where he worked with the Alto and Mesa. Modula supported even nested modules. And Pascal didn't have modules at all.

Drup 6y ago

Amusingly, I was precisely working today on extra-nice error messages for module type errors in OCaml. :) My reaction to the title was "But they are not exotic, I use them every day!" It's definitely the feature I miss the most every time I work in other languages, even presumable "advanced" ones, like Haskell. One notable attempt to add them elsewhere is "modular C"[1]. [1]: http://cmod.gforge.inria.fr/ http://cmod.gforge.inria.fr/

jolux 6y ago
Have you heard of Backpack for Haskell? https://gitlab.haskell.org/ghc/ghc/-/wikis/backpack https://gitlab.haskell.org/ghc/ghc/-/wikis/backpack

miki123211 6y ago

Zig's compile time execution lets you do similar things I believe. In Zig, structs and modules are equivalent, and type declarations can be manipulated at compile time just like any other value. That, among other things[1], lets you write: fn LinkedList(comptime T: type) type { return struct { pub const Node = struct { prev: ?*Node, next: ?*Node, data: T, }; first: ?*Node, last: ?*Node, len: usize, }; } I wonder if there's anything that OCaml functors can do but this can't. [1] for example, you can implement a very efficient printf that gives an error at compile time when the format string is invalid. See https://ziglang.org/documentation/master/#comptime https://ziglang.org/documentation/master/#comptime for more details.

eterps 6y ago
Nice! I also found these examples: https://www.reddit.com/r/Zig/comments/in8d6e/til_that_imported_zig_files_can_be_instantiated/ https://www.reddit.com/r/Zig/comments/in8d6e/til_that_import...
a-nikolaev 6y ago
One thing is that OCaml modules are first class objects, so can be constructed at runtime and passed around as variables. But this Zig example, I think, will cover the most common case of functors for creating generics. (I'm also not sure if Zig does compile-time check if the type T is compatible with LinkedList. OCaml does this type of check, making sure the signature of T fits the requirement of the functor LinkedList. The module T may have certain functions, for example a compare function associated with T to ensure sorting of the elements in your data structure.)
- dilap 6y ago
  (Not even close to a zig expert, but I've been playing with it a little bit, find it very interesting, and think what I'm about to say is correct:) The zig equivalent of a module, a struct, is also a first-class object in zig, so should be the same as OCaml there. However, Zig does not have anything like a signature -- in that sense, it's "dynamically typed" at compile time (i.e., like type args to C++'s templates, however not nearly as bad because the errors you get are immediate and understandable -- think of it as more like "I fucked up the types and got a python-style error" than I "I fucked up the types and got a C++ templates error").

gnulinux 6y ago

I feel like I keep saying this every single PLT-related HN thread. Sorry for preaching, but I just can't resist. I think Agda is an excellent programming language, and it's a joy to write anything in. Its learning curve is steep at the beginning but once you gain experience how to write coinfinite programs, it's such a joy. I think its module system is a huge bonus. It makes code a lot easier to organize and reason. It forces toplevel module X to be defined in X.agda so there is no argument what the module should be named or where it should be found.

js8 6y ago

Looking forward to the series! I hope, in one of his "presents", he talks about Lisp conditions and signals, which have also inspired PL/I conditions, and go really back to the idea of an error handler in an operating system. Unfortunately, Unix (and C) really botched signals by limiting their number in the user space (in particular, they cannot be stacked), and so the idea largely fell out of favor as an error-handling paradigm.

prirun 6y ago
I worked for Prime (minicomputers) as a youngster in the early 80's. They supported PL/I and many parts of the OS (Primos) were written in a systems dialect of PL/I they called PLP. The PL/I condition mechanism was an integral part of the OS and fault handling. For example, a floating point exception or integer overflow was detected by hardware, caused a fault, the information from the fault was packaged into a condition frame (an extended stack frame), and a condition was raised. The OS looked backward through the stack looking for an "onunit" (aka condition handler) that handled this condition - basically like try & except. Condition handlers were very flexible, with the option to partially handle the condition then let it continue with older frames, ignore the condition in this handler and let it continue, or completely handle it. If no running program had a handler for a condition, the default OS handler would run, which often raised a new condition and printed an error message. If the problem causing the error was corrected (for example, some files were deleted from a full disk), you could use the REN (re-enter) command to return from the disk full condition and the system call causing the condition would be automatically re-tried, sort of like when EINTR occurs on a system call and it has to be (manually) retried. Instead of using numbers, conditions had arbitrary names and arbitrary data could be associated with a condition. In hindsight it was very similar to Python's try/except/finally error handling mechanism. There was a condition called "cleanup$", which was executed whenever a procedure was aborted because of a stack unwind to allow it to close files, delete temp files, etc. I wrote an emulator for the Prime and you can see all this with: telnet em.prirun.com 8001 There are all kinds of manuals online too, including a full PL/I implementation, all from the 80's and early 90's.

jlrubin 6y ago

You can do something similar in Rust to ML modules using traits and generic impls as module functors! https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=8bebb69fa7898b13c731ccef158c0e4b https://play.rust-lang.org/?version=stable&mode=debug&editio... This can be really useful especially as traits with differing concrete types diverge, you can create a unified interface trait object to allow trait objects for things like container classes.

horsawlarway 6y ago

Coming in without much OCaml experience, I don't really think this is a great demonstration of why this construct has value. I don't really want to read a long form description of the OCaml implementation of modules. I want a comparison to the languages he dismissed at the beginning of the article, and a discussion of why this feature has some value that isn't provided by those languages. Basically - This feels like a different take on generics to me. There might be a lot of value in how this is implemented when compared to generics in a language like Java/C#/Typescript, but I didn't find that content anywhere in the article...

zcesur 6y ago
Say you'd like to have an interface for things that are 'mappable'. For example, for arrays we could write: interface Mappable<Array> { map<A, B>(f: (a: A) => B, fa: Array<A>): Array } Likewise, for `Promise`s we could write: interface Mappable<Promise> { map<A, B>(f: (a: A) => B, fa: Promise<A>): Promise } But in order to generalize this interface to an arbitrary type constructor such that `F: * -> *`, we would need to write interface Mappable<F> { map<A, B>(f: (a: A) => B, fa: ?): ? } which is not possible in TypeScript since it does not support higher-kinded types or type parameters that take type parameters or parametrized modules.
- karmakaze 6y ago
 Not possible, but an approximation: interface Mappable, T> { flatMap(f: (x: T) => Mappable<P, U>): Mappable<P, U>; } class Maybe<T> implements Mappable<Maybe<unknown>, T> { x: T | undefined; public flatMap(f: (x: T) => Maybe): Maybe { if (this.x) { return f(this.x); } return Maybe.nothing(); } }
 - zcesur 6y ago
 Yes, in fact this reminds me of the HKT implementation[1] found in fp-ts[2][3] interface HKT<F, A> { _URI: F _A: A } interface Mappable<F> { map<A, B>(f: (a: A) => B, fa: HKT<F, A>): HKT<F, B> } where F is a unique identifier representing the type constructor and A its type parameter. [1]: https://www.cl.cam.ac.uk/~jdy22/papers/lightweight-higher-kinded-polymorphism.pdf https://www.cl.cam.ac.uk/~jdy22/papers/lightweight-higher-ki... [2]: https://github.com/gcanti/fp-ts https://github.com/gcanti/fp-ts [3]: https://gist.github.com/gcanti/2b455c5008c2e1674ab3e8d5790cdad5 https://gist.github.com/gcanti/2b455c5008c2e1674ab3e8d5790cd...

shalabhc 6y ago

On the topic of modules, I recommend reading about modules in Newspeak: https://bracha.org/newspeak-modules.pdf https://bracha.org/newspeak-modules.pdf Modules (which are just top level classes and contain nested classes) have no import statement and no hard linked external dependencies. When you instantiate the module (~class) you pass in dependencies it needs.

ProfSarkov 6y ago

Nice (altered) Anna Karenina quote.

jandrese 6y ago

One thing I like about Perl is the module system. A big helper is when the module interface uses named parameters and has sensible defaults for unspecified parameters. This allows the module designer to add features without breaking existing code and makes it easier for someone to integrate the module in the first place. Having the documentation built into the module itself is also a huge win.

flavious 6y ago

I'm not your goto java guy, but the module system of java and how modules can provide implementations for interfaces is really great.

ellis0n 6y ago

Exotic Modules System looks like new C++