2
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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();
}         
$\endgroup$
  • $\begingroup$ This does identify and address the general concept (mutual recursion). Thank you for the C example as well, it was very helpful. $\endgroup$ – n00b101 Jan 20 '14 at 17:13
  • $\begingroup$ However, I should point out that I was trying to identify a special case of the concept, where there appears to be mutual recursion between two functions but if you "look inside" the branches of the conditional statements of each function then it is seen that in fact thee is no mutual recursion at all. This particular case is of interest because I would like to be able to generate recursion-free code (not all hardware supports recursion and there are performance concerns related to function call overhead). $\endgroup$ – n00b101 Jan 20 '14 at 17:16
  • $\begingroup$ Well, in this case, inlining X and performing dead code analysis would result in the answer you are looking for (first inline X into Y, eliminate unreachable code, using e.g. constant propagation, then inline Y into X). In general this only works if there is no "real" recursion though, which you can't find out before removing dead code. $\endgroup$ – cody Jan 20 '14 at 22:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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