Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I'm currently writing a compiler for a new language and I'm struggling with the linking aspect of new Types when there exists a circular reference.

I've created a dependency tree so that I can compile the Types in the order of their dependencies which seemed to have fixed my problem... that is until I hit circular references like an example below (posted in c#):

public class A
{
  public A() {  var b = new B(); }
}

public class B
{
  public B() { var a = new A(); }
}

My limitation is that I can only create 1 Type at a time, and in the case of circular references, either A needs to be created first, or B needs to be created first, both of which poses the problem that I can't create either unless it's dependencies are first created!

How do compilers overcome this?

share|improve this question
3  
I don't quite see what this has to do with the traditional meaning of the word linking. You might want to use a term that belongs to the compile phase, as linking has a strong connotation of being after every module or translation unit has been compiled. –  Lars Viklund Jul 25 '12 at 13:49
    
Either you have to do it like C and require declarations early, or you have to write a more complex logic, first look for all declarations, then in a later step, actually look at the details. Hard to answer how that fits to your design. –  johannes Jul 25 '12 at 13:54

3 Answers 3

In general, you create A and add it to the scope. When you get to resolve B, you go and build B. When that gets to resolving A, it finds a (partially) constructed type and grabs that reference. Then you return back to building A.

There are other situations that are more problematic (like cyclical inheritence, dll references, recursive type declarations) that often require placeholder types or are simply not viable given other design constraints. In general, keeping each compilation phase thin helps prevent issues. For example, you can only do the partial type trick if nothing needs to know the members of A in B.

share|improve this answer

I think you're trying to solve in the compiler something that should be resolved by the linker. Both A and B should compile to whatever intermediate code they use (traditionally an object file) and just list the other type as an external symbol. When you generate the executable form, you go through the symbol table for each object file and resolve the external references. See this for a good introduction to traditional linkers.

share|improve this answer

How do compilers overcome this?

Some languages (C++, Objective-C) allow forward declarations which introduce the type but don't define it. It'd go something like:

public class B;  // now the compiler knows that B is a class that will be defined later

public class A
{
  public A() {  var b = new B(); }
}

public class B
{
  public B() { var a = new A(); }
}

That said, even a forward declaration won't solve the circular problem in your example: Creating a new A will create a new B, which in turn will create another A, which will create another B, and so on. If you want one A and one B that point to each other, you'll need to create constructors that take a reference to an existing object, like:

public class A
{
  public A(B _b) { var b = _b; }
  public A()     { var b = new B(this); }  // 'this' is a C++-style pointer to the current object
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.