Pepper: Reviving Cayenne Part 1 - 2026/07/06

Recently, I've been (haltingly) working on the Cayenne language. For those not familiar, It's an academic programming language from a number of years ago, interesting primarily because it features dependent types. It was designed and implemented by Lennart Augustsson. https://doi.org/10.1145/289423.289451 It's generally quite similar to Haskell in appearance and feel (and is implemented in Haskell), but trades type classes and stronger inference for dependent types and a more elegant record/module design.

Recently I had the thought that I would like my next language project to be on some existing language rather than trying to write my own entirely from the ground up (and likely not finishing). I had failed to make as much forward progress in my last several language projects, due mostly to the large and diverse amount of work to implement a complete language. It's easy enough to put together a little integer calculator or the like, but implementing garbage collection and side effects brings the complexity up considerably. I'm still proud of some of that previous work, and indeed may return to at least one of them that I felt like had the possibility of growing legs at some point, but for the moment they will remain in the graveyard with the others.

So I'm interested in languages, specifically functional ones, and I want to work on something that exists already. Easy enough, there are no shortage out there. I landed on Cayenne for a combination of reasons. The first among them, paradoxically, is that as far as I can tell it has been entirely abandoned. The last official release was more than a decade ago, and a few github forks and the like lie scattered around in the name of reviving it, but none significantly more recent than the last release. The fact that there isn't an ecosystem means that should I decide to make some breaking change, I don't need to do much convincing and only need to alter/update the core bits I need rather than worrying about breaking a diverse library ecosystem. The second is that it was implemented in Haskell, which I enjoy writing, and am curious about in the context of writing a compiler. The third is that it's an Augustsson creation, which was a pleasant surprise since I didn't know the name when I had read the paper several years ago.

Direction in mind, and armed with only the original paper, and the final release (1.7) that I could find, I set off to work. After acquainting myself a bit with the code base (all non-builtin dependencies included directly as source in the tarball? How lovely, why can't everyone do this?), I called my shot: to implement a runtime backend by generating C in the style of Baker. https://doi.org/10.1145/214448.214454 I've wanted to write a Baker style CPS compiler for a while, and generating C as compiler output has always appealed to me. It also has major pedigree in the space, since SPJ and co have a number of excellent papers about compiling Haskell's STG representation to C--.

The lack of tail-calls in C is a major limitation, but Baker's method is simple and elegant, if deeply anti-"modern" in its use of alloca and longjmp. I suppose the use of that bit of the standard library is "considered harmful", but so is generating assembly or even worse machine code yourself. I think I'll take my chances managing a stack manually rather than trying to generate valid x86 machine code.

Stylistic quibbles aside, I think Baker's method of compilation by way of C is a very good fit for Cayenne. First class in the language is module level separate compilation, matching C translation units exactly, and the current solution of compiling Cayenne into Haskell that has a unsafeCoerce every two feet is effective if a tad silly. Not to mention it requires an at least semi-functional Haskell ecosystem, no small ask! So I dubbed by work "Pepper" in the hope of making Cayenne more generally accessible, and got started. The first thing to do was make the compiler compile at all. Haskell has changed a fair bit in the decade plus since this project was last released, so a lot of tweaking standard library imports and updating names was in order to make it run. I also took the chance to remove all the references to LazyML, since it has been entirely supplanted by Haskell in the public world and I don't want to even make an attempt at maintaining a LML ecosystem. The syntax is basically the same as Haskell anyway, so it's no real loss.

Jumping ahead slightly, work has been progressing slowly but steadily. It oscillates between writing new Haskell for the backed or new C for the runtime system, and doing archaeology to understand what the current semantics and authorial intent around the existing Haskell code. This generally takes the form of consulting the paper, writing very small test programs, and poring over verbose compiler output to try and understand the relationship between the surface language and the internal representation. At a high level this is extremely easy. There's a single algebraic data type for an expression AST, and with types and modules also being terms or expressions, the whole language is there. The difficulty comes in that very generality. For instance when do you know the type of an expression? Even putting aside fancy dependent ones, types are not included at every node of the tree in general. You can cart around an environment and query it to reconstruct the type of a sub-expression, or you can hope that your particular bit is tagged explicitly with an IHasType e t wrapper. The digging is mostly to answer questions like "when can I rely on having an explicit type in the tree?".

In general Haskell seems like a lovely language to write a compiler in. Nice types and pure functions certainly make reasoning easier. Beyond taking a complete parser and type checker (basically) off the shelf, Cayenne has the benefit that it comes with a description from the paper proving that types are not required at runtime, and further that to call a function or use a thunk from across a module boundary it suffices to know its type. I have structured my backend as a series of transformations, adding or removing assumptions or properties until I have something easier to generate C from. In the most ideological version of this pattern, the compiler's types themselves prevent you from mistaking levels between transformations. GHC is a refined example of this, with their "Trees that Grow" style AST representation. I have chosen not to encode my transformation information in types, mostly because I don't want to have to retool the existing code around new type parameters, but also don't want to rewrite all the basic plumbing logic for no reason on new types (i.e. collecting free variables, folding definitions into the environment, etc). This is both laziness on my part and a stylistic choice to match the existing code.

Tangentially, this exact restraint with regard to fancy abstractions is one of the things I really admire in Augustsson's work. He is certainly capable of and knowledgeable about them, but in some slightly conservative sense he writes "reasonable" Haskell, though the term might be an oxymoron to the average programmer. The Trees that Grow stuff is beautiful and powerful, but also requires some sophisticated machinery like type families and thus brings in the subtleties of the most overgrown corners of GHC's type inference and instance resolution algorithms. Not to imply that type families or indeed Trees that Grow are so arcane, but when compared to the simple "we have values and we apply functions to them" style of Augustsson's stuff, it seems a tad convoluted. Though were I writing at scale with hundreds of other programmers, I would take the complexity for the stronger compiler support without a doubt. Not every tool needs to feature all the bells and whistles, and similarly, sometimes you really just want a sharp knife and not safety scissors, though they may technically suffice. I wish the Rust zealots would internalize this idea, but that is neither here nor there.

The other reason I have been trying to embody Augustsson's more direct style is that I have found this project to be grossly interconnected. Not on an explicit call graph way, it's easy enough to make layers or whatever other code organization scheme you want, but in complicated trade offs between subproblem solutions producing constraints on other subproblem solutions. These in spirit represent breaches of layering etc., but expressing them in types or other formalism is far too brittle for a project still very much in development by exactly one young and foolish developer. To give a sense, lets talk about pointers.

Each machine word in play at runtime is (basically) either an integer or a pointer. When doing garbage collection, where you trace the live parts of the heap, you need to be able to distinguish them, and neither false negatives nor positives are acceptable, since upon recursion problems compound. You can tag them, so they can be distinguished by a low or high bit. This is pleasingly simple, but extremely slow for code that does a lot of manipulating numbers, which is exactly what the machine should be the fastest at (think a nested several parameter integer calculation. It should really be within a small multiplicative constant of doing it in assembly.) Ok so not tags then, Instead we can continue our theft from SPJ and co, and use info tables, which are pointed to from a value and contain among other things a map of where the pointers are in the object. The garbage collector can consult the map and only recurse where appropriate. Great! Problem solved?

The other reason to like tagless numbers is that it means for function calls, you can pass an integer argument directly in a register (for us as a C parameter) directly rather than passing a pointer to a heap value containing the integer. So that's nice. Remember in Baker style systems, you make C call after C call until you overflow and then rescue the live stuff from the stack and reset to the bottom before restarting the frame that went over. To restart it, it suffices to write down the arguments to the last call and then call it again post garbage collection. but where to store the arguments? Probably not on the heap, since we are doing garbage collection, it doesn't sound good to start by trying to allocate more space. We could save finite headroom on the heap for that, but at that point we can just have a static memory region (naturally of fixed size) where we write it down.

But wait, if its fixed size, there's a (small) max number of arguments to a given function. That's fine, we can fold earlier arguments into a tree and only pass the root and then unfold inside the function. This is a language that encourages currying. So we need either closures from lambdas or partial applications on the heap that are callable. I chose the later cause it's simpler and better aligned to what I want. It's also what GHC does. But that means that any lambda will have all its free variables converted to parameters while lambda lifting. So now maybe the argument max is a problem.

I can reasonably yell at the programmer for having a function with more than 32 arguments, but it's less intuitive to do the same about arguments+captures. Most programmers don't track or think about the free variables in use, and asking the programmer to fix it on the source end is a problem because she will only be able to directly effect one of those, manually compacting arguments together thereby ruining whatever nice and meaningful signature it would have in a vacuum. Even worse, between the various transformations, a lot of things that weren't lambdas end up as lambdas, so now you would be complaining about things not even visible in the source that the programmer has only the most indirect control over. So clearly the compiler has to do it, and it needs to happen on the captures and not the regular arguments so it doesn't change the calling convention. Now they need to be distinguished from formal arguments, and generalized folding logic needs inserted everywhere (can't be too general though, that's a performance hit), and it needs to elegantly handle multiple levels of free variables, from repeated lifting of lambdas inside lambdas inside lambdas. Phew. That's a lot to get right in order to add and multiply integers fast.

I ramble on not because any of this is impossible or couldn't be sidestepped by deciding that a 15% performance cut is fine for a language no one will ever run or several other solutions, but to try to give a sense that things are deeply connected in very hard to predict ways. I remember in some interview with Johnathan Blow, he talks about games been grossly connected under the hood. Basically his point is that interesting games, or games that feel good tend to require their parts to be in constant contact and communication, and thus formalism that try to limit that in the name of safety etc. tend not to be worth their weight because they are disproportionately frictional in that kind of context. I don't think this is quite as endemic as it could be in games or elsewhere, but I was personally surprised about how interconnected these seemingly small decisions tended to be.

I wish I could say "And here it is!" and have a functional thing to put here, but this work is still ongoing, and my time for it liable to shrink significantly in the coming year. I'm sure I'll keep at it for a while, and it will appear on my git at some point. Until then!