I've gone down a rabbit hole attempting to formalise ICM. I need some help.

Hey everyone.

I've had too much free time this week so I've been trying to formalise ICM, and it sent me into a paper called "Build Systems à la Carte." I think it points straight at something we need to build, and I'd like to poke holes in it with you.

Start with the gaps ICM names about itself. The paper is honest that it has two problems it doesn't solve:

- Staleness (§6.1). A stage declares which files it reads in its Inputs table. Change one of those files and the stage's output might now be stale, but nothing makes that concrete. The paper explicitly leaves "dependency tracking and change propagation" as future compiler-theory work.

- Self-tracking edits (§6.3). Editing a stage's output is like patching a binary, it fixes this one run. Editing the source fixes every future run. And recurring edits to the same place are debugging information a future ICM could track, but doesn't yet.

Both of those are build-system problems. Which is exactly what "à la carte" formalises.

The paper's move is to take the vague idea of a "build system" and split it into two independent parts:

- a scheduler: what order tasks run in.

- a rebuilder: whether a task actually needs rerunning, or its result is already current.

ICM already has the scheduler. Numbered stages running in a set order is exactly that, you decide what runs when. What it doesn't have is the rebuilder, the part that answers "is this stale." The mechanism it uses is a verifying trace: you store the hashes of the inputs a task used last time, and on the next run you re-hash. Anything different means the task is dirty and reruns. Nothing different means you skip it. It's the build system's memory.

That is the staleness fix, almost directly. A verifying trace over a stage's Inputs table means you hash the files a stage reads, and when one of them changes you know exactly which stage went stale. §6.1, handled.

The rebuilder has a second trick that lines up with §6.3. You don't only track the inputs, you track changes to the tasks themselves, the rules. The paper calls this self-tracking. For ICM I think that means treating a stage's instruction file as a tracked dependency too, so editing a stage re-triggers exactly what depends on it, and recurring edits to the same file become visible signal instead of lost effort. That is §6.3's "recurring edits are debugging information," made concrete.

I want to be honest that this is me connecting dots, not something either paper says outright. And the hard part is still ahead. I haven't worked out the concrete design: what counts as a "key" in an ICM stage, what exactly you hash, where the trace lives.

So that's where I've got to. The rebuilder mapping is the bet I'm least sure of, and I'd rather find the hole now rather than spending weeks chasing ghosts. If you can see where it breaks, that would be super useful. Cheers.

Here is a URL to the paper if you're interested: https://simon.peytonjones.org/assets/pdfs/build-systems-jfp.pdf

3 comments

I've gone down a rabbit hole attempting to formalise ICM. I need some help.