Fine-grained versioning of entities in programming languages

Question

I have a question related to design, implementation of programming languages. I hope it fits here and apologize if it doesn't.

All or most programming languages version modules (aka packages, libraries, crates). All the entities in a module (types, functions, variables and other information) share the same version with the module. However usually only some parts of a module change between a version and the next.

When two different modules use different versions of the same third module, this creates an incompatibility.

• Some programming languages (for instance C and C++) ignore the problem altogether. They don't care about the version but only about the name and signature of entities. They accept programs that may crash or misbehave when executed, if different pieces of such programs expected different versions of a same entity that changed.

• Other programming languages (for instance Rust or Node.js) trait different versions of the same entity as two completely different entities. This avoid crashes, but introduces unnecessary incompatibilities between entities that did not change.

This can be a big problem for modules that define many different entities and that lots of other modules depend on, for instance the standard library of a programming language. Most programming languages use special tricks for their standard libraries: for instance they tie the standard library's version to the compiler version and require to recompile everything when the compiler version changes.

A better solution to this problem could be versioning every entity independently instead of whole modules. The GNU implementation of the standard library of C and C++ do this. I have seen some Rust crates do this too by importing their previous version and re-exposing all the symbols that didn't change. But these processes are very tedious and easy to get wrong, hence very few pieces of software adopt similar practices.

Do we know of any good way to version entities in a fine-grained way?

Has there been any research on this problem?

A practical example

If the problem I described isn't clear, let me explain it with a practical example.

A module "time 1.0.0" defines loads of entities related to time. Among many others, it defines these two types:

type UnixTime   = uint32_t; # seconds from 1970 Jan 1
type UnixTimeNS = uint32_t; # nanoseconds from 1970 Jan 1

After "time 1.0.0" is out, we realize that UnixTimeNS is too small: it needs to be an uint64_t. We change that type and release "time 2.0.0" since we did an incompatible API change. Nothing else changed in the whole "time" module besides that UnixTimeNS type.

Two other modules "logger" and "totp" depend on "time". The former was developed on "time 1.0.0", while the latter uses "time 2.0.0". They both only use time::UnixTime and nothing else. This type did not change between the two version. But the compiler can't know that and treats time_1.0.0::UnixTime and time_2.0.0::UnixTime as different, incompatible types. It's now very hard to use both "logger" and "totp".

Imagine if they make a similar change to the standard library of any existing language: it could result in a tremendous split between new and existing modules, something as catastrophic as the switch from Python 2 to Python 3. All for a very minor change that affects 0.1% of the existing code.

I developed a rust crate (https://github.com/BlueNebulaDev/rust-version-test) and a Node.js package (https://github.com/BlueNebulaDev/node-version-test/) to show this problem in action. The names used in these projects differ from the ones in the example described here, but the meaning is the same.

Answer 1

The Unison programming language is based around two simple fundamental ideas:

• code is immutable
• code is content-addressed

What does that mean? Code being immutable means just what it sounds like: since code is immutable, it will never change. You can only ever add new code to the system, but you can never change or remove existing code.

Code being content-addressed means that all addresses (references) are based on the content of the code, not any names. And computing the content address is invariant under α-conversion by using De Bruijn indices in the code database.

This has some interesting implications: since you only reference functions, types, modules, variables, etc. by their content address and the content address is based on a name-less representation, you can rename anything and everything to your heart's desire, and never break any code. Also, since all references are based on content, and content never changes (remember, code is immutable), code that works at one time, will always continue to work until all eternity.

This poses an interesting question, though: How do you fix bugs?

One part of the puzzle is how names are handled in Unison. I wrote above that Unison's code model is based on addresses, but that doesn't mean that there are no names at all. It would be very annoying to write code like

#1uekd4 = #lle0xy #5q17cp #h8i067

instead of

fullName = concat firstName lastName

and having to remember all the addresses.

Instead, Unison also stores a mapping of names to addresses in its code database. This is similar to how Unix filesystems work: in a Unix filesystem, a file has no name, it only has a file serial number. However, there are directories (which are also files) which map names to serial numbers (which could point to regular files or to another directory). Also, Git works in a similar fashion. There are blobs, which only have content, and there are trees which assign names to addresses (which could be blobs or trees).

If you want to fix a bug, then you create a new version of the buggy function which doesn't have the bug. But all existing code still references the old function! (Remember, all addressing is based on content, not names.) So, you have to update every function that references the old function. And you have to update every function that references a function that references the old function.

Obviously, this gets tedious really fast. This is where names come in. After updating the function (really creating a new function), you also update the name database (really creating a new database) with a version where the name now points to the new, fixed, function.

Unison will notice this update, and will automatically propagate this name change through all existing functions. So, it will automatically update all functions that reference the buggy function to now reference the fixed function, then it will update the functions which reference the functions it just updated, and so on.

Where "automatically propagate" can mean one of two things:

• If the new function has the same type as the old one, Unison will automatically apply the update.
• If the new function has an incompatible type, Unison will create a to-do list with all the places that need to be changed.

Once the change is made, regardless of whether it was done aumatically or it required manual intervention, this change is recorded in a patch and becomes part of the code database as well. So, anybody else who pulls in the changes will benefit from the fact that you already resolved the issue and they can pull in the patch as well.

Bringing this to your example: since the content of time::UnixTime hasn't changed, it still has the same address, and since code is immutable, it is guaranteed that this address will refer to this type for all eternity. And since both logger and totp only refer to it by its address, which will never change, they, too, will continue to work unchanged for all eternity.