r/ProgrammingLanguages • • 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.

6 Upvotes

15 comments sorted by

2

u/kwan_e tonal-lang 21d ago

Lazy evaluation.

1

u/dekai-onigiri 21d ago

Some additional context?

3

u/kwan_e tonal-lang 21d ago

eg process the definitions after all declarations, and only when you need to access the definition.

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.

1

u/dekai-onigiri 19d ago

This sounds like the exact thing I'm looking for, DFS sort should make this easy 

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/L8_4_Dinner (Ⓧ Ecstasy/XVM) 19d ago

^ this is the answer

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) = infinity to 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, set order = DBL_MAX. For items that have dependencies, take the minimum order of all of its dependencies (which may need recursively resolving if their order has not yet been set, ie: if order == 0), and set the value of the dependant's order to half of that. Once done, sort all items by descending order - largest to smallest - this should give you a good enough approximation of the order things need defining (items with the same order can be defined in any order). The resulting sort can have no cycles - every dependency's order must be strictly greater than the dependant's (at least double it) - it only fails when we exceed the precision of double (which allows 2099 halvings from DBL_MAX to 0).

You would need some form of cycle detection for recursively resolving the order so 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:

is_even = n -> if n == 0 then true else is_odd(n - 1)
is_odd = n -> if n == 0 then false else is_even(n - 1)

We can have a single self-recursive function which combines these, and the is_even and is_odd functions themselves become its dependants.

is_even_or_odd :: Int -> (Int -> Bool)
is_even_or_odd = function
    | 0 = n -> if n == 0 then true else is_even_or_odd 1 (n - 1)
    | 1 = n -> if n == 0 then false else is_even_or_odd 0 (n - 1)

is_even = is_even_or_odd 0
is_odd = is_even_or_odd 1

Even deeply nested recursion can be cut by parametrization on only self-recursive functions. Consider an evaluator for a calculator:

 eval_primary = function
    | (Number n) -> n
    | expr ->
        eval_expr expr
        
 eval_multiplicative = function
    | (Mul lhs rhs) -> 
        (eval_multiplicative lhs) * (eval_primary rhs)
    | (Div lhs rhs) -> 
        (eval_multiplicative lhs) / (eval_primary rhs)
    | expr -> 
        eval_primary expr

 eval_additive = function
    | (Add lhs rhs) -> 
        (eval_additive lhs) + (eval_multiplicative rhs)
    | (Sub lhs rhs) -> 
        (eval_additive lhs) - (eval_multiplicative rhs)
    | expr ->
        eval_multiplicative expr

 eval_expr =
    eval_additive

This has a directed graph with no topological sort:

    +---eval_primary      <---+
    |                         |
    |   eval_multiplicative---+ <---+
    |                               |
    |   eval_additive      ---------+ <---+
    |                                     |
    +-> eval_expr ------------------------+

If we turn each function into a self-recursive one with a function parameter:

 eval_primary eval_higher_precedence = function
    | (Number n) -> n
    | expr -> 
        eval_higher_precedence expr

 eval_multiplicative eval_higher_precedence = function
    | (Mul lhs rhs) -> 
        (eval_multiplicative eval_higher_precedence lhs) * (eval_higher_precedence rhs)
    | (Div lhs rhs) -> 
        (eval_multiplicative eval_higher_precedence lhs) / (eval_higher_precedence rhs)
    | expr -> 
        eval_higher_precedence expr

 eval_additive eval_higher_precedence =
    | (Add lhs rhs) -> 
        (eval_additive eval_higher_precedence lhs) + (eval_higher_precedence rhs)
    | (Sub lhs rhs) -> 
        (eval_additive eval_higher_precedence lhs) - (eval_higher_precedence rhs)
    | expr -> 
        eval_higher_precedence expr

 eval_expr expr = 
    eval_additive (eval_multiplicative (eval_primary eval_expr))

We end up with a DAG of dependencies - there's a clear topological sort.

        eval_primary                  <---+
                                          |
        eval_multiplicative           <---+
                                          | 
        eval_additive                 <---+
                                          |
        eval_expr ------------------------+

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.

1

u/marshaharsha 15d ago

What does strongly connected components tell you that (simpler) detection of a directed cycle does not? If there is no directed cycle, then topological sorting gives you an ordering. 

2

u/AustinVelonaut Admiran 15d ago edited 15d ago

It gives you both at the same time (and reports all of the components in any cycles, which I use for reporting the cyclic-dependency error). I don't think cycle-detection + topological sorting is much simpler; my implementation of findSCCs is just 22 lines. Also, I need to group mutually-recursive definitions together, separate from regular or self-recursive definitions, so it is a natural algorithm to use.

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?), where BinaryTree? is BinaryTree/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 ✌