Excellent post, but I do have one medium-sized nitpick. C has an excellent, strong module system. Header files are annoying to work with in the small, but, in the large, they make a comparatively OK hard system boundary! I actually haven’t released this before, but now it seems that a significant part of C success as systems programming language can be attributed to existence of header files. System programming is like 90% about defining the boundary interface, and 10% providing the actual implementation.
In particular,
Arguably its even more complex because a module can conform to multiple signatures, not just one header like in C.
I think is not entirely correct. Every time I write
in Rust when I am reluctant to depend on someone else FFI binding, I make libc conform to a new, my-project-local signature.
What C lacks is namespacing — it’s on the author of the code to prefix their symbols with mylib_ to avoid naming conflicts. But OCaml doesn’t have proper namespaces either! Module1.foo and Module2.foo only work if Module1 and Module2 are different names. But if they are Foo, version 1.1.0 and Foo, version 2.0.0, it’s game over. Rust does have proper namespacing, where there’s no global, shared namespace of symbols, and names belong not to units of code themselves, but to the edges connecting units of code, so it is always possible to do a local rename in the downstream unit to avoid a naming conflict
I would say C header files can be used as a strong module system, but “C has an excellent, strong module system” is a stretch. It takes considerable effort / education / continued discipline. The gotchas are myriad:
(1) 90% of the time that you’re using header files, you arguably don’t want any modules.
I think a good size of a strong module is more like 10K to 100K lines, whereas a good size for a C source file is 500 to 5K lines. (This relates to what Ousterhout calls “narrow vs. deep interfaces” – you don’t want your interfaces to over-run the program. The program has to do stuff too!)
Also pretty related to the two-level hierarchy of modules you wrote about, I believe (cyclic and acyclic). C header files often have a tangle of mutual recursion that is broken by #include guards, so in that sense people may think of them as at the finer-grained level. I guess they can be used at both levels, but it’s often extremely unclear in practice.
(2) Conversely, many common styles of C don’t use header files as modules.
It took me awhile to understand C’s modularity, because at the first two jobs I worked at (spanning 14 years), the convention was to put the header file next to the C file. Header files were just annoying maintenance in those cases.
Also, modularity strongly implies using opaque pointer style (not putting structs in headers, PIMPL in C++) – and that is not a universal practice either.
I didn’t quite understand /usr/include for awhile – it’s distributing the interface definition without the source code. But that’s not common in applications; it’s mainly for kernels and extensible languages like CPython.
(3) C++ features often appear in headers and are often anti-modular. This isn’t to say they are bad – they are that way because you want speed, and (all else being equal) speed is good!
Although I guess this is not necessarily an argument against header files as modules, which leads to the next point
(5) Even within strong modules, you have at least two policies with regard to versions.
Most BSD kernels, CPython: Users are expected to compile against a specific version of header. CPython was like this for ~30 years; only recently has it been moving toward a stable ABI for extention modules
Linux kernel - there is a stable ABI. So arguably this is stronger than strong modularity. Hm so I guess that is one possible answer to my question above, and on Reddit:
So now I think that dynamic composition (long-lived protocols, narrow waists) is the strongest kind of modularity :) Not only do you not need the source code to compile, you don’t need the interface definitions to compile :) You simply repeat the interface in the code, because it’s so well known. e.g. it is OK to just write
HTTP_NOT_FOUND = 404
in your source code; you don’t need to link a library to get that constant.
Thinking about this a bit more, there is a weird irony
From the perspective of a C programmer, header files are not a good or strong module system. You think of them as more of a maintenance hazard, a mess.
From the perspective of C++, Rust, Zig, and maybe Go and Swift programmers, C headers could be a great module
system! [1] It’s the lowest common denominator. It’s an IDL for data.
The weak modules can be written in the monoglot style of each language: C++, Rust, etc.
The strong modules can be written in C, the lowest common denominator.
All these languages have mutually incompatible type systems, but they can, and need to, exchange data. And C headers are a a minimal language for describing data (with respect to a particular CPU / OS, which is often what you want.)
[1] Windows COM is arguably a better module system which is sort of built on C headers, but it’s somewhat out of favor, since it doesn’t exist on OS X or Unix. There was also XPCOM from Mozilla, which didn’t seem to go anywhere. So we are back with C as the lowest common denominator! Seem like the Lindy effect at work
The way this is usually done, each module defines it’s own name. This is problematic. Suppose you write an awesome library, and that library has a Foo module. Now, I write a completely unrelated library, but I also have a module called Foo. So far this is all fine. But now, if someone else decides to use both of our libraries, they are in for a trouble, because it would be unclear which Foo they are talking about. As describe, this problem is actually not very likely, genuine name conflicts are rare. What happens all the time though, is when “two different libraries” are actually “two different versions of the same library”.
An alternative to this system is somewhat radical. You just forbid modules to have names. How can you use anything then? Well, if you are inside a module, you can have some keyword which denotes the module itself. In Rust, that would be crate::. And if someone else is using the module, we could allow them to specify whichever name they want. Comming back to the original example, usually people would import our libraries using the Foo name, but for the person who needs them both at the same time, they can use FooAssymmetric for your version, and FooMatklad for mine.
More abstractly, if we look at the graph where nodes are libraries, and edges are “foo uses bar” dependencies, then we can place labels (names) either on the nodes, or on the edges. The second solution is immune to name conflicts, because the names are defined at the point where the edge originates, and that’s a single compilation unit that can easily choose a different name.
Even without the import maps, JavaScript also doesn’t suffer from the single global namespace problem. What’s more, due to dynamic nature of the language, you can often even pass values between different versions of a module.
As soon as I saw this post citing Derek Dreyer, I knew it was going to be real.
One oversight: Java since Java 9 has modules which are different from Java packages (Project Jigsaw). They are strong modules if you squint at them right, but they are very coarse, wrapping entire multi-package projects.
Backpack modules are decent, but Backpack’s momentum was killed by Stack not supporting it.
Still been aching to have real modules in the languages I use.
Note that OCaml also has a nifty thing called first-class modules which allows modules to be constructed at runtime. So it’s more “Compile-time/Run-time” in the case of OCaml.
Interestingly Haskell and Rust have type classes, which are a bit like implicit ‘strong’ modules (and were in fact originally inspired by them), but without the ability to make abstract datatypes and to construct arbitrary modules. I’m hopeful that one day OCaml’s modular implicits might close the gap on this, allowing modules to be implicitly passed to functions, but the developers seem to be lacking the bandwidth to push that proposal forward right now.
It gets worse from there. SML/OCaml also have abstract types, sharing constraints, and generative module instantiation. All of these features are powerful sure, but we pay a steep complexity cost for that power.
A “shadow language” is basically where you need to reinvent conditionals, looping, function abstraction for types as well as data, e.g. exactly what happened with C++ templates.
Biformity – the shadow language is two forms / duplication that can’t be reconciled
In addition to this inconsistency, we have the feature biformity. In such languages as C++, Haskell, and Rust, this biformity amounts to the most perverse forms; you can think of any so-called “expressive” programming language as of two or more smaller languages put together: C++ the language and C++ templates/macros, Rust the language and type-level Rust + declarative macros, etc. With this approach, each time you write something at a meta-level, you cannot reuse it in the host language and vice versa, thus violating the DRY principle
Yeah! This is what has led me to being interested in dependently typed programming languages, i.e. to help keep the type, module and term languages as similar as possible and stuff reusable between them (less so the theorem proving stuff). Going down this road does lead to other complexities however, and there’s still lots of work to be done to make it viable.
It seeks to simplify modules by combining structures and signatures into one construct, and using a linking mechanism to avoid a lot of the boilerplate around functors.
I think sml# has gone partway there with its notion of separate compilation and interface files.
What’s the relationship between dynamic M x N composition (I’ve been calling them narrow waists) and static M x N composition (strong modules) ? Harper insists that modularity is M x N, and only with respect to static types. This seems a bit myopic, considering that the Internet exists, and networked software exists :)
What’s the relationship between the expression problem (another M x N issue) and strong modules? Is there still a problem to be solved there?
Excellent post, but I do have one medium-sized nitpick. C has an excellent, strong module system. Header files are annoying to work with in the small, but, in the large, they make a comparatively OK hard system boundary! I actually haven’t released this before, but now it seems that a significant part of C success as systems programming language can be attributed to existence of header files. System programming is like 90% about defining the boundary interface, and 10% providing the actual implementation.
In particular,
I think is not entirely correct. Every time I write
in Rust when I am reluctant to depend on someone else FFI binding, I make
libcconform to a new, my-project-local signature.What C lacks is namespacing — it’s on the author of the code to prefix their symbols with
mylib_to avoid naming conflicts. But OCaml doesn’t have proper namespaces either!Module1.fooandModule2.fooonly work ifModule1andModule2are different names. But if they areFoo, version 1.1.0 andFoo, version 2.0.0, it’s game over. Rust does have proper namespacing, where there’s no global, shared namespace of symbols, and names belong not to units of code themselves, but to the edges connecting units of code, so it is always possible to do a local rename in the downstream unit to avoid a naming conflictI would say C header files can be used as a strong module system, but “C has an excellent, strong module system” is a stretch. It takes considerable effort / education / continued discipline. The gotchas are myriad:
(1) 90% of the time that you’re using header files, you arguably don’t want any modules.
I think a good size of a strong module is more like 10K to 100K lines, whereas a good size for a C source file is 500 to 5K lines. (This relates to what Ousterhout calls “narrow vs. deep interfaces” – you don’t want your interfaces to over-run the program. The program has to do stuff too!)
Also pretty related to the two-level hierarchy of modules you wrote about, I believe (cyclic and acyclic). C header files often have a tangle of mutual recursion that is broken by
#includeguards, so in that sense people may think of them as at the finer-grained level. I guess they can be used at both levels, but it’s often extremely unclear in practice.(2) Conversely, many common styles of C don’t use header files as modules.
It took me awhile to understand C’s modularity, because at the first two jobs I worked at (spanning 14 years), the convention was to put the header file next to the C file. Header files were just annoying maintenance in those cases.
Also, modularity strongly implies using opaque pointer style (not putting structs in headers, PIMPL in C++) – and that is not a universal practice either.
I didn’t quite understand
/usr/includefor awhile – it’s distributing the interface definition without the source code. But that’s not common in applications; it’s mainly for kernels and extensible languages like CPython.(3) C++ features often appear in headers and are often anti-modular. This isn’t to say they are bad – they are that way because you want speed, and (all else being equal) speed is good!
Recent comment, which you probably saw - more related to this post than to that one! https://lobste.rs/s/z2qhlm/on_modularity_lexical_analysis#c_xmfhpm
(4) ABIs are “extra-linguistic” (outside the language)
They’re not documented in C language books, because they sit at the awkward boundary between the language and the CPU/OS.
Although I guess this is not necessarily an argument against header files as modules, which leads to the next point
(5) Even within strong modules, you have at least two policies with regard to versions.
Most BSD kernels, CPython: Users are expected to compile against a specific version of header. CPython was like this for ~30 years; only recently has it been moving toward a stable ABI for extention modules
Linux kernel - there is a stable ABI. So arguably this is stronger than strong modularity. Hm so I guess that is one possible answer to my question above, and on Reddit:
https://lobste.rs/s/eccv1g/what_s_module#c_tbf6ms
So now I think that dynamic composition (long-lived protocols, narrow waists) is the strongest kind of modularity :) Not only do you not need the source code to compile, you don’t need the interface definitions to compile :) You simply repeat the interface in the code, because it’s so well known. e.g. it is OK to just write
HTTP_NOT_FOUND = 404in your source code; you don’t need to link a library to get that constant.
I mentioned syscall emulation as an instance of this here - https://www.oilshell.org/blog/2022/03/backlog-arch.html#emulation-of-waists
Thinking about this a bit more, there is a weird irony
From the perspective of a C programmer, header files are not a good or strong module system. You think of them as more of a maintenance hazard, a mess.
From the perspective of C++, Rust, Zig, and maybe Go and Swift programmers, C headers could be a great module system! [1] It’s the lowest common denominator. It’s an IDL for data.
All these languages have mutually incompatible type systems, but they can, and need to, exchange data. And C headers are a a minimal language for describing data (with respect to a particular CPU / OS, which is often what you want.)
[1] Windows COM is arguably a better module system which is sort of built on C headers, but it’s somewhat out of favor, since it doesn’t exist on OS X or Unix. There was also XPCOM from Mozilla, which didn’t seem to go anywhere. So we are back with C as the lowest common denominator! Seem like the Lindy effect at work
What do you mean by this?
The way this is usually done, each module defines it’s own name. This is problematic. Suppose you write an awesome library, and that library has a
Foomodule. Now, I write a completely unrelated library, but I also have a module calledFoo. So far this is all fine. But now, if someone else decides to use both of our libraries, they are in for a trouble, because it would be unclear whichFoothey are talking about. As describe, this problem is actually not very likely, genuine name conflicts are rare. What happens all the time though, is when “two different libraries” are actually “two different versions of the same library”.An alternative to this system is somewhat radical. You just forbid modules to have names. How can you use anything then? Well, if you are inside a module, you can have some keyword which denotes the module itself. In Rust, that would be
crate::. And if someone else is using the module, we could allow them to specify whichever name they want. Comming back to the original example, usually people would import our libraries using theFooname, but for the person who needs them both at the same time, they can useFooAssymmetricfor your version, andFooMatkladfor mine.More abstractly, if we look at the graph where nodes are libraries, and edges are “foo uses bar” dependencies, then we can place labels (names) either on the nodes, or on the edges. The second solution is immune to name conflicts, because the names are defined at the point where the edge originates, and that’s a single compilation unit that can easily choose a different name.
Your anonymous import seems to be what JS import maps are doing.
https://html.spec.whatwg.org/multipage/webappapis.html#import-maps
Even without the import maps, JavaScript also doesn’t suffer from the single global namespace problem. What’s more, due to dynamic nature of the language, you can often even pass values between different versions of a module.
As soon as I saw this post citing Derek Dreyer, I knew it was going to be real.
One oversight: Java since Java 9 has modules which are different from Java packages (Project Jigsaw). They are strong modules if you squint at them right, but they are very coarse, wrapping entire multi-package projects.
Backpack modules are decent, but Backpack’s momentum was killed by Stack not supporting it.
Still been aching to have real modules in the languages I use.
If you want to understand modules better, shameless plug: https://www.pathsensitive.com/2023/03/modules-matter-most-for-masses.html
Note that OCaml also has a nifty thing called first-class modules which allows modules to be constructed at runtime. So it’s more “Compile-time/Run-time” in the case of OCaml.
Interestingly Haskell and Rust have type classes, which are a bit like implicit ‘strong’ modules (and were in fact originally inspired by them), but without the ability to make abstract datatypes and to construct arbitrary modules. I’m hopeful that one day OCaml’s modular implicits might close the gap on this, allowing modules to be implicitly passed to functions, but the developers seem to be lacking the bandwidth to push that proposal forward right now.
Some more terms to describe the “complexity” of strong modules:
Shadow Language from Gilad Bracha:
https://gbracha.blogspot.com/2014/09/a-domain-of-shadows.html
A “shadow language” is basically where you need to reinvent conditionals, looping, function abstraction for types as well as data, e.g. exactly what happened with C++ templates.
Biformity – the shadow language is two forms / duplication that can’t be reconciled
https://hirrolot.github.io/posts/why-static-languages-suffer-from-complexity
(copy of Reddit comment)
Yeah! This is what has led me to being interested in dependently typed programming languages, i.e. to help keep the type, module and term languages as similar as possible and stuff reusable between them (less so the theorem proving stuff). Going down this road does lead to other complexities however, and there’s still lots of work to be done to make it viable.
Zig is remarkably easy. It doesn’t even need unification for type inference!
Regarding this bit:
I think sml# has gone partway there with its notion of separate compilation and interface files.
Great post! I like the definition of strong and weak modules – I will start using that.
I posed a couple questions for the author, and would be interested in lobste.rs opinions as well - https://old.reddit.com/r/ProgrammingLanguages/comments/15fgh6b/whats_in_a_module/
What’s the relationship between dynamic M x N composition (I’ve been calling them narrow waists) and static M x N composition (strong modules) ? Harper insists that modularity is M x N, and only with respect to static types. This seems a bit myopic, considering that the Internet exists, and networked software exists :)
What’s the relationship between the expression problem (another M x N issue) and strong modules? Is there still a problem to be solved there?