Exploring computation graphs in Rust

This weekend I spent some time exploring a way of implementing computation graphs in Rust (writeup here]. I would love to hear if anyone has any suggestions on ways to improve my approach, or recommendations for anything relevant that I should read.

2 Likes

I don't entirely understand why Node needs to have the static lifetime. Hopefully that doesn't mean anything bad.

Trait objects (such as in Box<Node>) always default to the static lifetime (written as Node + 'static). Thus, if you want to support Nodes with borrowed data using dynamic polymorphism, you will need to unelide lifetimes in many signatures, or use a type alias (to add an elidable lifetime):

// Used as Box<DynNode<'_>> in fn signatures
type DynNode<'a> = Node + 'a;

The general rule of thumb regarding enums versus traits is to use enums for closed sets of things.

In practice, however, for internal types in high level code (where the set of types is technically closed, but changes often), I find that the code organization of some functions is cleaner when implemented on an enum, and others are cleaner when implemented on a trait. So be wary of the grass is greener effect! (But, starting out, it is good to try both to get a feel for them)

One place where enums are spectacularly better than traits is for parsing/deserialization. So even when I elect to use a trait, I will still sometimes have a separate enum type that exists solely as an intermediate form for file IO.

Thanks for the tip about the static lifetime!

That's a good point about enums and (de)serialization. I should probably write some (de)serialization code to see how it works with traits.

I took a similar approach when putting together a parser and runtime for a form of Basic we used at work for stuff like PLC logic (surprisingly, procedural Basic + goto is actually pretty good for this kind of stuff).

My approach was to represent the Abstract Syntax Tree (sometimes called a parse tree) using the normal structs + enums approach. This AST then gets lowered to a more useful acyclic directed graph which is represented using a bunch of maps from NodeId to Variables, BasicBlocks, and the various other constructs. My HIR approach was originally modeled on rustc's HIR and appears to be quite similar to what you did in your article, although not having homogeneous node types made my code more complex.

I've found this NodeId approach to be quite nice and pretty flexible, although you tend to lose a lot of the nice compile-time safety that comes with having direct references to other objects. The extra level of indirection from constantly doing table lookups is also a pain.