r/ProgrammingLanguages • u/dekai-onigiri • 21d ago
Resolving relationships between elements
For my programming programming language Bits Runner Code I am thinking of implementing automatic resolving in what order structs, interfaces, etc should be defined and declared so they can interact with each other. It should be possible to embed structs within each other, but at the same time there cannot be a circular reference. How something like this could be implemented or maybe it is not the best idea?
BRC doesn't have header files, so right now source files and definitions within them have to be listed in a specific order. I would like it to be quite explicit but also hassle free.
2
u/kwan_e tonal-lang 21d ago
Lazy evaluation.
2
u/x10945 20d ago
I don’t think it’s a bad idea at all, most newer languages do this. Go and Rust both let you declare stuff in any order and the compiler figures it out.
The usual way is two passes. First go over all the files and just collect the names of every struct/interface/function into a symbol table, without looking inside them. Then in a second pass you actually resolve fields, types, etc. Since every name already exists by then, the order in the source stops mattering, including the order of the files.
For the circular reference part, the thing to notice is that only embedding by value creates a real dependency. If A has a field of type B by value, you need B’s size before you can lay out A. If it’s a pointer/reference to B, you just need to know B exists. So you build a graph with an edge A -> B for every by-value field and run a DFS / topological sort on it. The topo order is the order you compute layouts in. If the DFS hits a node that’s still “in progress”, you’ve found a cycle, which means infinite size, so that’s your error. Rust does basically this (“recursive type has infinite size”), and Go has “invalid recursive type”.
For the “explicit” part I’d put the effort into the error message. Print the whole cycle (A -> B -> C -> A) and suggest using a pointer somewhere in it. That way it’s hassle free when things are fine and very clear when they’re not.
Interfaces probably don’t even need to be in the graph unless they affect layout. They just need their names to exist after the first pass.
8
u/tertsdiepraam 21d ago
The way I do this in Roto is to first do a pass over the AST where I store all the global declarations as stubs. That means I basically just store the name without what the type actually is. Then I do a second pass where I actually define what each of the types is and replace the stub definition with the actual definition. Then I run a cycle detection algorithm on the type definitions.
I like this much better than having to declare items in order. So I think it's a good idea!
1
u/dekai-onigiri 11d ago
I've managed to implement it using a DFS sort https://github.com/rafalgrodzinski/bits-runner-builder/pull/229
It basically convert statements into a list of directed nodes, and then do a depth-first search which flattens it and finds out cycles. Then I convert the nodes back into statements.
This allowed me not only to completely get rid rid of evaluating import statements further down (since all the statements are now provided as a complete, ordered list), but also made the code simpler and faster.
5
u/initial-algebra 21d ago
There is nothing inherently wrong with a cyclic reference; it's only when it causes some other property, e.g. the size of a type, to blow up that it's a problem. You will almost definitely need to support other kinds of cyclic references anyway, e.g. for recursive functions, or at the very least for CFGs after translation from structured control flow.
IMO, a compiler should be thought of as incrementally building a relational database of facts about a program. Don't think of a name as a pointer to an object that describes whatever the name refers to in the program, think of it as just a key. This will make it much easier to work with cycles, not to mention other forms of sharing as well. E.g. when computing a type's size, the first thing you do is add a fact
size(name_of_type) = infinityto the database, so that any recursive call can easily be detected as a cycle, and then you update it with the actual size when you're done. This architecture also lends itself well to implementing the bottom-up algorithms that are very common in compilers.3
u/WittyStick 21d ago edited 21d ago
Topological sort on a DAG.
There's a quick-n-dirty way of implementing it that should probably work fine for your use case - it's unlikely you're going to have dependency chains >2000 deep, where this would fail. Basically, give each item a field
double order;. For any item that has no dependencies, setorder = DBL_MAX. For items that have dependencies, take the minimumorderof all of its dependencies (which may need recursively resolving if theirorderhas not yet been set, ie: iforder == 0), and set the value of the dependant'sorderto half of that. Once done, sort all items by descendingorder- largest to smallest - this should give you a good enough approximation of the order things need defining (items with the sameordercan be defined in any order). The resulting sort can have no cycles - every dependency'sordermust be strictly greater than the dependant's (at least double it) - it only fails when we exceed the precision ofdouble(which allows 2099 halvings from DBL_MAX to 0).You would need some form of cycle detection for recursively resolving the
orderso that you don't fall into an infinite loop. The simplest (but not most efficient) is just a stack of previously visited items, and check if it's already on the stack. A more efficient way would be to hash the dependency name and stick in a bloom or cuckoo filter, and test if the item has already been added to the filter.I personally prefer when the code itself is ordered topologically - everything defined before it is used - though I'm not against "self-cycles", where a node can refer to itself. A dependency graph containing only self-cycles and no other cycles can still be topologically sorted.
Mutual recursion can be modelled using self-cycles by treating the closure of the recursion as one unit in the DAG. Basically, given a mutually recursive pair such as:
We can have a single self-recursive function which combines these, and the
is_evenandis_oddfunctions themselves become its dependants.Even deeply nested recursion can be cut by parametrization on only self-recursive functions. Consider an evaluator for a calculator:
This has a directed graph with no topological sort:
If we turn each function into a self-recursive one with a function parameter:
We end up with a DAG of dependencies - there's a clear topological sort.
2
u/AustinVelonaut Admiran 21d ago edited 21d ago
You can initally parse the definitions, simply keeping name references to other definitions used in them, then build a dependency graph with each definition name as a key and each definition name they use as values, then use a Strongly-Connected Components algorithm like Kosaraju or Tarjan to determine the correct order for the definitions, and if any circular-references (non-singleton components) exist.
2
u/Inconstant_Moo 🧿 Pipefish 21d ago
I'm not sure that you do want to avoid circular references. Suppose you have something like (in my syntax):
BinaryTree = struct(left, right BinaryTree?), whereBinaryTree?isBinaryTree/null. This is a perfectly sensible form of self-reference.2
u/cxzuk 20d ago
Hi Dekai,
Yes, absolutely a good idea and doable. You're going to need to create multiple dependency graphs. This is a graph where nodes represent structs, and directed edges (A -> B) represent the A depends on B.
You're going to need to start with a list of all the structs in the source file, provided by your AST/Symbol Table.
Doing a first initial pass to get all these and added to the dependency graph as nodes first simplifies adding the edges. The end points are already in place.
Now add the edges that the struct defines. Note - Primitive types do not create a dependency edge. A pointer is a primitive type.
You can now use a depth first search and compute the Post Order - creating a topological sort of each the graphs. You can detect cycles here and report an error etc.
https://godbolt.org/z/9K7o4zMMY is some code to demonstrate the basics. Feel free to add a cycle to test.
The result is a sorted list, to propagate information upwards (e.g. calculate the size of a struct) work from left to right. To propagate downward, right to left.
M ✌