Algebraic code generation

I'm writing this article to document my design and implementation of a project I'm calling firebird named after the Phoenix Architecture by @chadfowler.com .

It started life as me messing with the original codebase and eventually grew into an entirely orthogonal beast after a couple weeks of experimentation.

It's an early proof-of-concept pre-alpha. I just wanted to get the concept out there to people since they might be interested in this.

Ok, here we go.

The thesis is that it is possible to create a code generation platform using category theory and data morphisms without using llms.

I want to note that I am not anti-llm, I just think that deterministic, algebraically provable, code generation may have some positive tradeoffs when compared to llm generated code.

The network consists of modules that are standalone and written in nickel lang . Nickel is inspired by nix. There is a good rationale page comparing it to other config languages and why you should use it.

update: experimentally using .nix files since you can't read other files inside functions at runtime with nickel.

The generator reads the spec.md file and creates a fully hydrated application stack.

#show spec.md here

The tensor network

warning: maths ahead

disclaimer: I don't have a formal background in mathematics. however, I throw highly mathematical concepts around a lot. I am probably wrong. Please, kindly, ignore my ignorance in places where I am obviously incorrect.

In order to assemble an application stack, I create what I'm calling a "tensor network". This term is inspired by my current understanding of tensor algebra. Tensor algebra is linear algebra's older brother essentially. In linear algebra you have concepts like matrices and vectors. In tensor algebra you just have tensors.

Here is a table mapping linear algebra concepts to tensor algebra concepts to make it obvious what I'll be talking about0

A vector is written in tensor form like so: 0

vi

The superscript i means there is an upper-index. If our little v guy meets someone special with a lower-index, it contracts and we get a little baby scalar. The lower-index v is shown below:

vi​

Lower-index values, also called covectors, are often seen as "inputs" in a tensor network. Upper-index values are seen as outputs.

A matrix is just a vector with multiple indices. eg.

Aij​

This is a matrix with a upper-index and a lower-index. You can have two upper or two lowers as well. It just need two indices total, hence, rank-2.

When you do matrix-vector multiplication you get a vector0. We see this is an obvious outcome when looking at tensor algebra

wi=Aij​vj

Matrix A has an upper-index and a lower-index. We multiply by v who just has an upper. the upper and lower cancel each other out and we are left with a vector.

In my model, I would say that A provides something (upper index) and requires something (lower index). When we apply v we are saying that our requirement is met (upper index satisfies lower index requirement) and that the resulting network now is just a provider of a capability.

I apologize that it's such a long winded way to talk about capabilities and I probably lost half my audience with the maths, but I wanted to include it because this stuff uses a lot of formalisms under the hood.

The spec parser

I'm working on writing a spec parser0 that takes a spec.md (just a plain text file in mostly-natural0 language) that generates a capability tensor network. It works by using a mathematical framework called DisCoCat0 (Categorical Compositional Distributional) that does the heavy lifting of converting natural language to a tensor network.

Status command

There is a status command to show the output of the tensor network capability/requirements map generated by the spec file.

Here is the status response from an example app:

App: apps/example
Framework: elenajs
============================================================

[UNFULFILLED]
Logging (0 providers, 1 consumer)
Consumers:
- hono-server [optional] -> NO PROVIDER
WARNING: 1 consumer(s) need this but no providers exist!

HttpMiddleware (0 providers, 1 consumer)
Consumers:
- hono-server [optional] -> NO PROVIDER
WARNING: 1 consumer(s) need this but no providers exist!

[ACTIVE]
Database (2 providers, 1 consumer)
[USED]:
[INFRA] sqlite (type=sqlite, embedded=true, runtime=bun, file_based=true)
[AVAILABLE]:
[INFRA] postgres (type=postgres, embedded=false, connection=tcp, features=["pooling")
Consumers:
- hono-server -> uses any of: sqlite, postgres

WebFramework (2 providers, 3 consumers)
[USED]:
[INFRA] elenajs-core (type=web-components, features=["reactive", framework=elenajs)
[AVAILABLE]:
[INFRA] lit-core (type=web-components, features=["reactive", framework=lit)
Consumers:
- user-card -> uses any of: lit-core, elenajs-core
- todo-list -> uses any of: lit-core, elenajs-core
- welcome-card -> uses any of: lit-core, elenajs-core

HttpFramework (1 provider, 1 consumer)
[USED]:
[COMP] hono-core (name=hono, paradigm=middleware)
Consumers:
- hono-server -> matches [name=hono]: hono-core

The module system

The module system is capability based. For example there is a Database capability that any module can implement. So e.g. we can have a sqlite module that provides that capability.

Modules can also require capabilities. For example, we can make a WebServer capability require Database. Then we can implement the webserver capability using something like hono.

When we do the parsing step of app generation we look at what modules are available to us and what capabilities they provide.

The requirements and capabilities are configured in .nix files.

My original system had

Category Theory

panproto has a tree-sitter parser for hundreds of languages. One of the interesting things about firebird is we are using panproto to generate code using generalized algebraic theories.

Ok here's how it works: a protocol is defined by two theories

Theories in panproto are just Struct s so dont worry about the word "theory" too much.

theory one: the schema theory

this defines the "shape" of the protocol

theory two: the instance theory

this defines what the actual data is for the protocol

so instance theory + schema theory = protocol. cool.

now we can connect protocols together and panproto will automagically transform one protocol to another using the magic of category theory

Earlier when we were constructing our tensor network from parsing the spec, we were also extracting configuration info from the spec to pass to the modules. We take this configuration info and use it to assemble our own protocol.

There is a function called emit_with_protocol inside panproto that allows us to pass in a language protocol e.g. typescript and automatically generate code by lensing our custom protocol with a language protocol. This allows our configuration from the spec [written in natural language] to be isomorphic with the generated code

The end [for now]

That pretty much sums up how it works. The concept, while being mathematically complicated is actually not that complicated once the maths are abstracted. Stay tuned next time for more updates on how my development is progressing.0