6
$\begingroup$

Mainly, I want to know what existing languages/implementations that use this sort of multi-file module structure do.

In my language, modules can consist of multiple files. (For now I don't plan on having the compiler operate on anything other than complete modules.) A module's effective source text is roughly* a concatenation of the text of the files. For the sake of this post, let's just say that the “top level” of a module contains declarations that may or may not be exported from the module. A module declaration is necessary for the compiler to associate a name with the module, which is used when referring to exported things. I haven't decided whether I want the files to be specified explicitly (in the module declaration) or if they are implicit (based on directory structure). The latter choice is more conventional but less portable (can't do it with the standard C library). Specifying files would solve the problem that this question is about, although I'm not aware of any languages that do it (except for Common Lisp if you consider ASDF to be its module system).

When a module has more than one file, the compiler needs to read all the files. In general in my language, the order of declarations doesn't matter, but there are edge cases when it does. In what order should the files be read/processed? Here are the choices I've thought of.

  • Leave it unspecified; portable code shouldn't depend on the order. Fine in concept but there are some issues. First, it is possible for declarations to have different semantics depending on the order in which they appear, and the compiler can't always tell when this is the case. Thus the user is left to enforce the requirement. The compiler still needs to decide on an order; directory order is probably the simplest.
  • Directory order, assuming the files are specified implicitly. It isn't portable and I believe means that a program's compilation might break if you move it to a different file system. It is also not easily controllable by users.
  • Specification order, if files are explicitly listed. This gives the user control over the order and means that source files can be located anywhere; it's also generally portable between most platforms, as long as the files aren't in system-specific locations.

I like the idea of specifying files, but again I believe it's uncommon. Perhaps it should be possible to specify the files if you need the control and the compiler defaults to directory order.

I'm glossing over details like where the module declaration goes. Also note that I'm not talking about the order of compilation of other modules.

If I understand correctly, Rust's module system is similar to what I want for my language. I couldn't find anything about the Rust compiler's file processing order.


* A related concern is whether the files are simplistically concatenated as with the C preprocessor's #include or parsed as complete sequences of declarations and then combined somehow. If I go with dumb concatenation, then constructing examples where order matters is much easier. However, I might require an “in module” declaration in each constituent file, which would effectively require files to be syntactically complete. I'm leaning towards parsing files separately, since it seems the more “modern” choice.

$\endgroup$
11
  • 1
    $\begingroup$ It seems like what you are describing is precisely the Go package system. What are you looking for an answer to provide here - existing analogous models, design research, general discussion? That is, what makes for a correct answer to this question? $\endgroup$
    – Michael Homer
    Commented Jun 21 at 3:59
  • 1
    $\begingroup$ Ok, I've made an edit to try to make that clear (so that it doesn't sound like a bikeshed, opinionated question, but looking for actual existing manifestations of this pattern). Please adjust if I've missed your meaning somewhere. $\endgroup$
    – Michael Homer
    Commented Jun 21 at 4:30
  • 2
    $\begingroup$ I'm not sure if I understand: is file processing order semantically meaningful in your language? Because if it is, you have to let the user choose and define that order. And if it is not, it is irrelevant whether you use directory order or not. $\endgroup$ Commented Jun 21 at 5:20
  • 1
    $\begingroup$ @EldritchConundrum Not necessarily, static initialization in Java depends on order but cannot be specified either. $\endgroup$
    – feldentm
    Commented Jun 21 at 13:34
  • 2
    $\begingroup$ @texdr.aft you should think about removing all properties of your language that make the order of declarations meaningful. It improves usability, simplifies refactorings and makes tool support easier to implement. $\endgroup$
    – feldentm
    Commented Jun 21 at 13:35

5 Answers 5

7
$\begingroup$

Frame challenge:

In general in my language, the order of declarations doesn't matter, but there are edge cases when it does.

That's not great. If "independent" units aren't independent, then it makes it hard for humans to make sense of things. If your compiler can't figure out what the semantics of loading the files in different orders should be, how would a programmer be able to do it? If the behavior is different depending on which order they're combined, how does the human reading the code know which behavior is the intended one?

This is a particular challenge if it's just "edge cases" where it matters. If 99+% of the time the combination is order independent, but there's strange 1% cases where it does, then a normal (non-expert) programmer will likely only be aware of the 99% behavior and wouldn't necessarily be on the lookout for the 1% edge case. They'll they'll possibly run into bugs where the compiler chose the one order, but they're implicitly expecting the other behavior.

Since you have control of the semantics of your programming language, I would highly recommend changing things such that you remove these edge cases. It's likely worth it to go through contortions (on the compiler side) to make that happen. You don't specify which edge cases you're running into, but approaches like having a two-phase parse (e.g. one phase just to pull out what definitions are available and then the second phase to actually use those definitions) might work for your issues. -- Again, think about how a programmer would determine what the intended behavior is, and try to make the compiler "intelligent" enough to pick that up.

If the order dependence is something more along the lines of multiple incompatible definitions for the same name (or something similar where there's contradictory programmer intent), then I'd highly recommend not trying to automatically resolve it. If the programmer isn't being clear, throw up a compiler error. Implicit rules where certain parts of the program are ignored or overwritten because of arbitrary order dependency issues are horrible to debug. (Why isn't the function returning the value it's supposed to? Because the compiler isn't calling that function, it's calling some other function you're not even aware of. Why? Because someone else renamed an unrelated file from user_account.xyz to customer_account.xyz, and since 'c' comes before most of the rest of the alphabet, the compiler is prioritizing those functions.) -- The compiler often doesn't need to determine an order, the compiler can simply kick the issue back to the programmer to resolve properly.

I'm guessing the issues you're having with order dependence can be resolved either by putting a bit more "intelligence" into your compiler, or by simply refusing to compile an order-dependent program. If, for some reason you can't resolve the issues in those cases (e.g. because there's no way for the programmer to rewrite the program to avoid them, or the compiler fundamentally can't be adjusted to support intelligent determination or error detection), then it's probably best to make the order dependence explicit in all cases, not just the edge cases. That way you don't have programmers who have standard work patterns for the 99+% cases, but then run into hairy debugging issues when the edge cases eventually pop up.

$\endgroup$
6
  • $\begingroup$ Hmm... good points here. I'll probably have a way for the programmer to say "hey I'm gonna shadow this binding" and otherwise the compiler will tell them "hey just so you know you're shadowing this binding". But how might initialization be handled in an order independent way? In x: int := f(); y: int := g(), if f and g can have side effects then it may make a difference to have x after y. Tracking dependencies isn't always possible. $\endgroup$
    – texdr.aft
    Commented Jun 21 at 18:04
  • 2
    $\begingroup$ @texdr.aft Again, if side effects matter, how does a human know what should happen? -- One is to require initializer functions like f() and g() be without side effects. This could be explicitly checked (by having special "pure" functions either in the language proper or in the compiler internals). Or you could require non-trivial initialization to happen explicitly in standard control flow. (Rather than implicitly "before the program starts".) Or you could take the C/C++ route and say "order-dependent static initialization is undefined behavior: don't count on either order." $\endgroup$
    – R.M.
    Commented Jun 21 at 18:30
  • 1
    $\begingroup$ @R.M. small correction, it's only a problem in C++, not C. C doesn't allow you to initialize static variables with just anything, just with constants. $\endgroup$ Commented Jun 21 at 22:05
  • $\begingroup$ Since the question is seeking instances of existing systems that do this, this is not an answer to it (if it were an answer, the question would likely be off-topic). It could be edited to give supporting evidence of such systems being tried without success, for example, and make this case. $\endgroup$
    – Michael Homer
    Commented Jun 21 at 22:57
  • $\begingroup$ @MichaelHomer I think C++'s "order-dependent static initialization" is a pretty good example of an existing system that does this, and it causes endless problems $\endgroup$ Commented Jun 26 at 3:40
3
$\begingroup$

I think that what you're describing is almost exactly the Go package system:

  • Declarations from multiple files are combined into a single unit.
  • Each file has a package header specifying which package it belongs to.
  • There is no defined ordering between files, and no way to specify one in the code.
  • Declarations from any file in the package are visible throughout all files.
  • Ordering is visible in two ways:
    • Declared variables are initialised in a topological order across all files, evaluating only after all manifest dependencies are initialised.
    • There may be multiple init functions, which are all executed after the variables are initialised.
  • The compiler identifies all available Go source files within the source root, and collates them by the package declaration.
    • Individual files have no meaning and cannot be processed apart from their module.
  • Directory structuring is conventional, but the package declaration is definitive.

In practice, the ordering between files will most often be lexically by filename, but as far as I know that is not required, and it can be overridden in the compiler invocation. The other steps make this order largely irrelevant, and are really how it is able to get away with this multiple-file approach. You can observe the file ordering with side-effecting initialisation code, but it's hard to have order-dependent problems. However, it isn't completely impossible to craft a scenario that goes wrong.

Subject to topological constraints, top-to-bottom initialisation is favoured. This means that if you have several variables, spread between files, some of which depend on some variable from another file, you'd expect the topmost variable with no dependencies in the lexicographically earliest file to evaluate first, then all the other zero-dependency variables, then the topmost variable in the earliest file that depended only on variables that have already been initialised, and so on. This topological ordering eliminates almost all of the potential ordering complications that could arise from any ordering of the module files.

init() functions are executed after all variables initialisations have run, in the same source order as zero-dependency variables. I believe that at one point their order was explicitly unspecified, so this has been a change (although I think it may codify what the reference compiler always did). They can rely on all declared variables with initialisers throughout the entire package having been evaluated already. It is possible to create bad orderings this way, but it's not going to happen in the typical cases.

Go's package model has had some controversy over time, both to do with potential variations in initialisation order and its insistence on tree-structured (acyclic) imports. There's also been a later module system overlaid on it at a higher level; a module is a collection of packages.

Notwithstanding that, this is a practical realisation of pretty much exactly the approach you're describing and it's been around for a while, so there is a lot of practical experience with it and plenty of code written using it. You can find the complaints people have about it and see whether they are impactful for you. Overall, it seems to work just fine for many or most cases.

$\endgroup$
4
  • $\begingroup$ So the compiler ends up figuring out the right order? Also, regarding "it can be overridden in the compiler invocation", could you explain how or point to documentation? I couldn't find a relevant option in the documentation of the go command. The GCC Go front-end's invocation description says that you have to pass it all the files. Is that how the order may be specified (with go giving gcc the files in whatever order by default)? $\endgroup$
    – texdr.aft
    Commented Jun 21 at 5:42
  • 1
    $\begingroup$ My understanding is that if you provide a list of filenames on the command line then those are taken in that order, but that is not a typical way to invoke it now — generally you just ask go to build and it finds all usable files within the source root (and sorts them). An alternative implementation would be permitted to do something different while complying with the specification if no order is specified. $\endgroup$
    – Michael Homer
    Commented Jun 21 at 5:49
  • 1
    $\begingroup$ @texdr.aft the normal thing is to use go build on a package or list of packages, in which case the files in each package get passed to the compiler in lexical order. However that's a tooling detail that's outside of the scope of the language spec, and you can invoke go build or go tool compile with a list of filenames. The spec only pins down behavior wrt the ordering which the compiler sees, but encourages build tools to make that order lexical filename order. It's just a wrinkle, not anything another language should reproduce exactly. $\endgroup$
    – hobbs
    Commented Jun 21 at 18:35
  • 1
    $\begingroup$ (it also only matters if you're doing weirdly cyclic things with variable initializations from functions with side-effects or multiple init()s in a package, which are probably not a great idea regardless). $\endgroup$
    – hobbs
    Commented Jun 21 at 18:37
2
$\begingroup$

For now I don't plan on having the compiler operate on anything other than complete modules.

Frame challenge: if the compiler has to read the complete source of a module every time any file in the module is changed, this will limit the size of modules, simply because people will get bored of waiting for them to compile, and will split them up.

This may sound like a good thing, but sometimes it will create artificial constraints that make the language less useful. I work with a domain-specific language that uses modularity in this kind of spirit. The language implementation transpiles source into C, which is then compiled. That forced us to have separate compilation.

Some modules in the product are small, and reading the entire source would not be a problem. But some of them have a couple of hundred large source files, and transpiling and compiling the whole module would take minutes, sometime tens of minutes. But all the files in a large module deal with the same, quite complicated, concepts and data structures in different ways. Splitting up such a module would create artificial divisions and make further development harder.

$\endgroup$
2
  • 1
    $\begingroup$ I generally agree. But my language is very dynamic and I feel it would be difficult to compile files in isolation without producing really slow code. Maybe I'm just not trying hard enough :) I think I would have to generate intermediate files rather than final object code. $\endgroup$
    – texdr.aft
    Commented Jun 21 at 22:21
  • $\begingroup$ An intermediate form sounds like the best approach. $\endgroup$ Commented Jun 22 at 6:17
1
$\begingroup$

Tyr has been like that from the very beginning. The definitions in files can be distributed amongst files in the same module without changing the semantics.

The solution here is to merge the ASTs from parsing individual files into a module AST before starting semantic analysis. The exact order of this is deliberately unspecified and the language is carefully designed to avoid all situations where this would make a difference. I.e. such a language must avoid top-down elaboration at compiletime and at runtime. For instance having init functions like in Go breaks this experience. The same issue arises with static initialization in Java which is also top-down.

Another benefit of Tyr's approach over Go's is that files (what Go calls packages) within a library can have cyclic dependencies. This is required in larger projects to structure large groups of data types.

The hardest part when avoiding top-down elaboration is that some sort of static dependency tracking must be implemented. This dependency tracking must be done at a granularity and precision that allows to express most common initializers. Otherwise, users will just workaround it and suffer as known from Ada's and Go's package-based elaboration.

C and C++ build systems in the past worked by enumerating files and I cannot remember anyone saying that that's a good thing. So, enumerating the files explicitly is likely perceived like a waste of time by most programmers. Also, from my experience, changing the semantics of a program by reordering the compilation order is not perceived as a good thing either. Instead, it is usually called an ODR violation even though it might not be in a strict sense.

$\endgroup$
1
$\begingroup$

Alsys Ada did this in two phases:

  1. Code was compiled with the information available, including generating calls to pieces of code expected to be supplied later in other modules.
  2. A special Ada linker - called the binder, and not to be confused with the system linker (provided by DOS, for Alsys Ada) - was run to "bind together" the entire program. It did all the final semantic checks - making sure all declarations/definitions in different modules lined up - and then generated code itself for things that couldn't be done until the whole program was available - such as instantiating generics for specific types, or providing implementations/tables for type attributes like 'Image and 'Value iff they were used in the code for specific types.

After the binder the system linker was run and it only had to work on one humungous object file + the separate Ada run-time library and then write the DOS-format executable.

(I do get that Alsys Ada isn't an "existing" language implementation as the OP requested - I mean, it exists but isn't current. But it was interesting enough - with its binder - that I thought I could mention it.)

$\endgroup$
8
  • 1
    $\begingroup$ You've seen my posts on Retrocomputing.SE—don't worry, age or obsolescence doesn't bother me! As a matter of fact, my language is a bit of an Algol 68 revival, with bold words, delimiters spelled backwards, and a huge character set. Your answer along with @feldentm's have led me to consider compiling files into stubs instead of all at once. (Not sure if I'll do that but I like the diversity of suggestions.) $\endgroup$
    – texdr.aft
    Commented Jun 21 at 16:56
  • 1
    $\begingroup$ I should also note that with this approach you generally have to accept a bit of pessimism in generated code - at the calling site to the separate module - since you can't inline that code you haven't seen. You the user or the alternative you the language implementor have to judge those costs vs the use cases. To go beyond that you're usually in the realm of full program LTCG. $\endgroup$
    – davidbak
    Commented Jun 21 at 17:25
  • 1
    $\begingroup$ I should also add (someday I'll edit the answer directly!) that in Ada these separate things could be quite extensive! E.g., a record could be declared - and used! - and only when the binder saw the implementation would the language system know that the record a) had dynamically sized components or b) included tasks (which required special initialization, finalization code at each site the record was created or deleted!). (Bonus for: dynamic-sized array of tasks ...). So each record decl/use in this way basically had to do the callouts if the defn was separate ... $\endgroup$
    – davidbak
    Commented Jun 21 at 17:28
  • $\begingroup$ Do you think it was done that way because of limited memory? $\endgroup$
    – texdr.aft
    Commented Jun 21 at 17:56
  • 2
    $\begingroup$ GNAT which is an active Ada compiler also has a binder - see 4.5. Binding with gnatbind. Part of the description is In particular, error messages are generated if a program uses inconsistent versions of a given unit. which is similar to that described for Alsys Ada. $\endgroup$ Commented Jun 23 at 11:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .