Design for the build system

Inspired by buildsome, the awesome build system, we can outline what a new build system would look like. The main technology is FUSE, as suggested in this issue, because it's the only reasonable way to globally hook filesystem access. We mount a basic pass-through FUSE file system over / and then just run whatever commands we want. FUSE traps all requests and then we can get the pid of the process using fuse_req_ctx or fuse_get_context which then through /proc gives us more useful information like process start time (pid + start time is unique), process command line (/proc/PID/cmdline), process environment (/proc/PID/environ), and process working directory (/proc/PID/cwd - this last is only valid before the process changes it, but the first thing any program does is read its executable files so we can trap it early). We also can get the parent process id, to recover the tree of subprocesses.

But just running commands isn't enough, we also have to handle rebuilds. When re-executing a process we must first roll back all the changes it and its sub-processes made, in order to ensure a clean build. To ensure an isolated build, we must also hide all the changes that were made by other processes that run after the re-executed process. These two steps should suffice for most purposes to enable deterministic builds, but of course more work can be done.

Next we introduce caching; as opposed to rebuilding, caching means that we can skip the build in the first place by downloading the pre-built result instead. For this we need a content-addressed store for all of the build files etc. and to store the metadata on which commands use which files. Also we need a special tool to run commands with, which checks if the command is cached before running it.

Finally we have to solve the problem of dependency hell. To summarize this is the situation where you have a library that gets updated but an application that depends on the library breaks on the update. The easiest solution is to do like Nix and install libraries into their own hashed directories, so that the new library goes in a new directory while the old directory sticks around and has the application still use it. But this breaks compatibility with a lot of software because the directory paths have to be hard-coded into the application somehow. A better solution is to use filesystem traps: a process that accesses the application files has a special label applied to it, so that when it later on accesses the library the label makes it see the old version of the library rather than the new library. This might(?) be implementable as another FUSE filesystem but an easier method is to just replace all executables with setcap CAP_SYS_ADMIN wrappers that mount an overlayfs on top and then exec the process.

Nix pros and cons

Pros

• Sandboxed builds
• Cross-compile support
• Run-time dependency information via hash-scanning
• not unique, e.g. NuTyX (cards) scans dependencies in the Elf header. 
• Multiple software versions don't conflict 
• Non-destructive updates
• Automated builds/tests with Hydra
• Single config file for NixOS

Cons

• Non-FHS layout
• Repeated dependency information
• Slow to evaluate
• Manual version bumps, cluttering VCS

Continuations and type systems

How do we get a programming language which combines all the type features we have seen? Linear types, dependent types, subtypes, continuations rather than functions, jumbo types,and so on?

First we must recall the purpose of a type system: at least at a low level, types are calling conventions. The type of a function, module, etc. is its interface, its API. A function may have multiple types and hence multiple calling conventions; but at runtime presumably only a few of these will be used. For efficiency reasons it makes sense to have only one true type and construct all the other types as wrappers, but this is by no means necessary.

When we have a C type, for example int main(int argc, char **argv), this is actually a very strong type; the C standard and implementation specify many details of memory layout, stack usage, etc. that are assumed to hold. The interface with the kernel is a cleaner type; execve simply loads the proper memory layout and jumps to the starting address. To represent this API we must use continuations instead of functions, as they never return a value. After looking at IL we might denote this as the type ¬kernel. Expanding the type kernel out it might look more like ¬(stack pointer -> {argc, argv, env}), at least on Linux. Continuations map nicely to the power of assembly language, where jumping to an unknown code segment gives up all control. If a C 'function' calls exit() it will never return. In IL, there is also a 0 type, the type of 'enterable locations'. From the rules the only values of type 0 look like (λ x.F) T, where F is another value of type 0, and the only values of type ¬T look like λ x.(E1 E2). It's not clear what this is useful for.

At a high level, though, the idea of contracts remains. We have properties of our programs that we wish to remain true, like memory safety. Linear types are one method of enforcing these; we reject programs that don't use resources linearly. Dependent types are another form of contract, allowing us to write pre- and post- conditions on values.

Following the IL paper, and its related cousin TACC, we can define types of continuations - roughly, the type of a continuation is the argument layout it expects to have. We extend our data types to the Jumbo Connectives of arbitrary records and sum types (the Pi type can be ignored, continuations are more powerful than functions as an intermediate language). And also we have to generalize negation to delimited continuations, following Zeilberger and a more recent paper. We can implement these on LLVM in two ways: first, by translating them away into standard function calls, and second by using a special calling convention, jump-with-argument.

How do we combine linear types with continuations? Following this paper we might introduce multiple types of continuations, e.g. the paper's lowered negation ↓¬ and boxed negation !¬. Then linear function types translate as !¬(τ1 & ↓¬τ2) while normal function types translate as !¬(τ1 & !¬τ2). But this hides the Rig (semiring) structure of the context. Maybe instead we could use a numbered continuation, k¬, where k is from our Rig. Then adding dependent types is easy, and subtypes are just polarizing all the information flow. Simple!

Papers by Appel (1, 2 , 3, 4) describe a closure strategy analysis, wherein known functions are compiled using registers but unknown functions use the heap. They do not use the stack because it inefficiently holds on to values even after they are not being used; deallocation would require making holes in the stack. But of course nothing in life is free; as soon as one gives up the stack, one needs it again for interfacing with other (C) code.

Incremental build farms

Build farms are expensive to setup and maintain. Or are they? Amazon gives away free instance-years, and services such as Travis and Appveyor build open-source projects for free. Can these services be used to bootstrap a Linux distribution?

The Nix answer to these questions is to use a binary cache - a server in the middle that stores cryptographically-signed binaries. It can start as simple as a single node, with a Nix store, then expand to use Amazon S3 or another large-scale filesystem.
But why start there? We could instead start with a distributed filesystem, like Bittorrent's DHT or IPFS. Then sharing files is as easy as sharing the root location hash, and all we need is a simple GitHub Pages site that gives out the root hash for everyone to synchronize on.

The issue of trust still remains though. Who builds what? How does the hash get calculated? Is there a cryptocoin (filecoin)?

Another approach starts from a single moderately-powerful system; Gentoo is a source-based Linux distribution that can usually be compiled and installed overnight. Speeding up Gentoo (re)compilations is a worthy goal. But then how do we go from one system to a network of systems sharing binaries? Gentoo (portage) actually supports binary packages, but in practice this seems like it is never used publicly; instead it has a centralized system of mirrors for distfiles. This is probably due to culture and limitations in compatibility of binary packages; it seems like Gentoo is usually set up to compile packages for the specific CPU it's running on, as a side-effect of too many USE flags ("Gentoo is for ricers"). But doing some sane defaults like Arch shouldn't be too hard, and proper dependency management should alleviate all the compatibility / configurability concerns.

Continuous delivery and distribution

Software development suffers from lag; every change must be made, then compiled, then tested in few dozen ways, before the next change can be made. The faster this process completes, the faster development can move forward. Non-incremental development, where changes are made without testing or compiling, leads to slower development times overall due to the numerous regressions that are introduced and have to be tracked down later.

Nix encourages incremental development by making it easy to download and use software; it creates a uniform interface for adding libraries and other dependencies, in the .nix file. But it also slows down development because the build process itself is non-incremental; it has to pull down every source file every single build which adds significant overhead (1.5 minutes for a simple Java app). Part of this is necessary overhead; in a cluster, a build file has to be replicated among the machines. And dependencies have to be expire every so often to ensure they don't get stale. Nix's insistence on knowing the hash of every source dependency before it's fetched means that you can't implement automatic updates without updating your Nix files automatically. But the whole point of Nix is to be a human-readable and human-editable description of your configuration; updating them automatically makes them just another intermediate file format.

A cardinal rule of source control is to never check generated files into the repository; Nixpkgs has been violating this rule, with the consequent ballooning of repository size as a result. Hence the need to start over with a newer, cleaner distro - solve both the incremental build problem, via a new package manager and build tool, and the repository problem, via a more principled approach to dependency management.

The place to start is a small prototype to prove that it works; I only program in Haskell these days. For monitoring file dependencies we can use hs-watchman, although it needs to be updated for 2017. For logging we can use GZipped JSON as the file format and the pipes-zlib library. For process tracing we can re-use the command infrastructure from Shake.