For the past few months I’ve been working on Akku.scm, a language package manager for R6RS Scheme. It’s not the first one for Scheme and it’s not even the first for R6RS. But it’s here, it’s yet another package manager, it works and I’m using it.

Language package managers are specialized to some specific set of programming languages. They are not general tools to distribute any kind of software. The purpose is to aid developers in managing the dependencies of their code. Here’s a quick demo:

As the demonstration shows, there are three parts: manifest, lock and install. I started writing Akku.scm in reverse order. I first wrote the installer, then applied it to manually written lockfiles, and then wrote the code that computed the lockfile automatically.

Installing a locked set of projects

The lockfile contains specifications of projects to download and install. Any code pulled in by Akku.scm’s installer will come from a lock specification in the lockfile. Currently Akku can clone git repositories and install R6RS libraries/programs, but the format is flexible enough to support anything.

The lockfile will always contain some cryptographic checksums. Today this is the sha1 commit id to checkout in git. Even when a git tag is used to checkout, it is verified against the sha1 commit id. This is because git tags can be replaced and are not cryptographically secure by themselves. When file downloads are later added they will have their sha256 digests in the lock, and so on. The locks come from the package index and that is signed with an OpenPGP signature.

Other than code locations and checksums, the lockfile can also contain instructions for what to do with the downloaded projects. By default everything is treated the same, as R6RS libraries and programs. Reasonable future extensions include: library name prefixing, library filtering (to split a project into multiple packages), build instructions for code loaded via FFIs, and conversion of R7RS libraries.

Installation is not as simple as just copying files that match *.sls. Akku has a repository scanner that analyzes all files to locate and categorize libraries, programs, included files and license notices. It furthermore has code to recreate the pathnames of libraries based on the library names and the various rules used in different Scheme implementations. Example: (srfi :1 lists) is loaded from srfi/:1/lists.sls in Chez Scheme, srfi/1/lists.sls in IronScheme and srfi/%3a1/lists.sls in Ikarus. Akku installs it at all these locations.

The result is that you can simply point the installer at a repository and it automatically figures out what code there is and how to install it in the library path.

Solving

I’ve briskly ripped out the dependency solver from Andreas Rottmann’s Dorodango. The solver is a Scheme port of the one in Debian’s aptitude. Its inputs are the dependencies listed in the package manifest in combination with the package index. The output is a set of package versions that go into the lockfile.

All packages have SemVer versions and package dependencies are listed as ranges with a syntax borrowed from npm. Essentially SemVer means that versions are written as X.Y.Z, where X is incremented when breaking backwards compatibility, Y when adding features and Z when fixing bugs. Usually 0.x.x implies that compatibility is not guaranteed.

The solver’s job is to take the package’s direct dependencies and select a set of compatible package versions that pulls in not just the immediate dependencies, but also their dependencies, and then the next level of dependencies. You need package A and package A needs package B, so the lockfile must have both A and B. The trick for the solver is to get the highest versions which are all compatible with each other. This is in general a difficult problem, NP-complete actually.

For now the solver is working beautifully, but that might change as the package index grows and dependencies grow more complex. The way out of the NP trap is to switch to a simpler problem. Akku can later be extended to do what npm does: if the dependencies want to use package A both in version X and Y, then npm will install both X and Y at the same time. I think that with proper care this will mostly work in R6RS.

Infrastructure - not there yet

The next natural steps for Akku involve infrastructure for publishing and discovering packages. These are in progress. Currently the package index can be updated with akku update, but there also needs to be commands to publish packages and securely bind an OpenPGP key to the publisher and the package names.

To make the situation complete there also needs to be a web site connected with the package index. Package documentation and testing needs to be handled as well. There must also be support for publishing tarballs rather than git repos.

Epilogue

I have mentioned npm a few times, but don’t be led to believe that I think npm is a good example of a package manager. It seems that every few months there’s a scandal about npm or some other popular package manager. It has become something of a fashion to publicize package manager failures. Everyone has heard of left-pad and recently it would even chmod your filesystem into chaos. So now everyone should switch to Yarn, which is advertised as… Mega Secure? Golang’s go get uses GitHub URLs without any commit ids and someone thinks it’s GitHub’s fault that things can go wrong. Okay. It’s the new normal. (Russ Cox writes about vgo where these problems are fixed).

I have been wanting to get a package manager going for a while, but it was only after reading Sam Boyer’s article So you want to write a package manager that the final pieces fell in place. Sam’s work is for Golang, which is somewhat more popular than R6RS. Akku has an easier problem to solve.

“Python is popular; we’re not! We have an advantage!”

— Abdulaziz Ghuloum

For even more opinions about package managers and Scheme in general, see the next article: So many package managers.