Conditional Dependencies in Compiler Semantic Analysis Passes

Question

Imagine that we have a been given an Excel spreadsheet with three columns, labeled COND, X and Y.

COND = TRUE or FALSE (user input)
X = if(COND == TRUE) then 0 else Y
Y = if(COND == TRUE) then X else 1;

These formulas evaluate perfectly fine in Excel, and Excel does not generate a Circular Dependency error.

I am writing a compiler that tries to convert these Excel formulas to C code. In my compiler, these formulas do generate a circular dependency error. The issue is that (naïvely) the expression of X depends on Y and the expression for Y depends on X and my compiler is unable to logically continue.

Excel is able to accomplish this feat because it is a lazy, interpreted language. Excel will just lazily evaluate the formulas at run-time (with user inputs), and since no circular dependency occurs at run-time Excel has no problem evaluating such logic.

Unfortunately, I need to convert these formulas to a compiled language (not an interpreted one). The actual formulas, in the actual spreadsheets, have more complicated dependencies between multiple cells/variables (involving up to over half a dozen different cells). This means that my compiler has to perform some kind of sophisticated static, semantic analysis of the formulas and be smart enough to detect that there are no circular references if we "look inside" the conditional branches. The compiler would then have to generate the following C code from the above Excel formulas:

bool COND;
int X, Y;
if(COND) { X = 0; Y = X; } else { Y = 1; X = Y; }

Notice that the order of the assignment instructions is different in each branch of the if-statement in C.

My question is, is there any established algorithm or literature on compilers that explains how to implement this type of analysis in a compiler? Do functional programming language compilers have to solve this problem?

Answer 1

In general, mutual recursion is the problem you are facing: some languages support it, some don't. The fact is that you can always compile mutual recursion away to simple recursion, using pairs of results instead of a simple result here is an explanation.

The laziness can also be compiled away, by creating thunks, or functions with void argument.

It turns out that in C, mutual recursion is allowed, so only the second trick is required.

int cond = 0;

int if_X(void){
  if(cond){return 0;} else {return Y();}
}

int X(void) {
  return if_X();
}

int if_Y(void){
  if(cond){return X();} else {return 1;}
}

int Y(void){
  return if_Y();
}