Graph Grammars -- and Failure in Language Design

by Mark Gritter | at Minnebar 15 | Sat, Oct 10 • 11:30 – 11:55 in Nokomis Track | View Schedule

A graph grammar, or a graph rewriting system, is a set of production rules that modify graphs, just like a formal grammar modifies strings. Graph grammars have found applications in procedural content generation (like the game Unexplored), software verification, and Quantum Field Theory. We won't be covering that last one.

Sadly, most graph rewriting systems suck. They're quite hard to use, often with custom IDEs that make them unsuitable for embedding in a larger project. I tried to do better, and introduced a language called Soffit as a ProcJam project in 2018. In 2019 I pushed the boundaries of what Soffit could do by participating in the Advent of Code. You can try Soffit through an online front end.

Unfortunately, Soffit mostly fails at its goals.

But hopefully you can learn something about graph grammars, constraint programming, category theory, and language design from my failure!


Mark Gritter

Mark Gritter is a Founding Engineer at Akita Software, his fourth startup experience, building API observability. Mark formerly worked at HashiCorp on the Vault team; co-founded Tintri, an enterprise storage company that IPOed in 2017; and was a day-one employee at Kealia, a video streaming startup acquired by Sun Microsystems in 2004.

Mark's previous Minnebar presentations have covered topics such as correctness of algorithms, combinatorial auctions, scaling a startup, building a file system, and procedural content generation.