Graph Grammars -- and Failure in Language Design

by Mark Gritter | at Minnebar 15

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 Vault Advisor at HashiCorp, his third startup experience. Previously, Mark co-founded Tintri, an enterprise storage company, in 2008 and helped grow it to a 2017 IPO (and, unfortunately, a 2018 bankruptcy.) Before that he worked 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.

Similar Sessions

Does this session sound interesting? You may also like these:

Are you interested in this session?

This will add your name to the list of interested participants. It will help us gauge interest for scheduling purposes.

Interested Participants