How do I detect circular logic or recursion in a custom expression evaluator?

Question

I've written an experimental function evaluator that allows me to bind simple functions together such that when the variables change, all functions that rely on those variables (and the functions that rely on those functions, etc.) are updated simultaneously. The way I do this is instead of evaluating the function immediately as it's entered in, I store the function. Only when an output value is requested to I evaluate the function, and I evaluate it each and every time an output value is requested.

For example:

pi = 3.14159
rad = 5
area = pi * rad * rad
perim = 2 * pi * rad

I define 'pi' and 'rad' as variables (well, functions that return a constant), and 'area' and 'perim' as functions. Any time either 'pi' or 'rad' change, I expect the results of 'area' and 'perim' to change in kind. Likewise, if there were any functions depending on 'area' or 'perim', the results of those would change as well.

This is all working as expected. The problem here is when the user introduces recursion - either accidental or intentional. There is no logic in my grammar - it's simply an evaluator - so I can't provide the user with a way to 'break out' of recursion. I'd like to prevent it from happening at all, which means I need a way to detect it and declare the offending input as invalid.

For example:

a = b
b = c
c = a

Right now evaluating the last line results in a StackOverflowException (while the first two lines evaluate to '0' - an undeclared variable/function is equal to 0). What I would like to do is detect the circular logic situation and forbid the user from inputing such a statement. I want to do this regardless of how deep the circular logic is hidden, but I have no idea how to go about doing so.

Behind the scenes, by the way, input strings are converted to tokens via a simple scanner, then to an abstract syntax tree via a hand-written recursive descent parser, then the AST is evaluated. The language is C#, but I'm not looking for a code solution - logic alone will be fine.

Note: this is a personal project I'm using to learn about how parsers and compilers work, so it's not mission critical - however the knowledge I take away from this I do plan to put to work in real life at some point. Any help you guys can provide would be appreciated greatly. =)

Edit: In case anyone's curious, this post on my blog describes why I'm trying to learn this, and what I'm getting out of it.

Answer 1

I've had a similar problem to this in the past. My solution was to push variable names onto a stack as I recursed through the expressions to check syntax, and pop them as I exited a recursion level.

Before I pushed each variable name onto the stack, I would check if it was already there. If it was, then this was a circular reference. I was even able to display the names of the variables in the circular reference chain (as they would be on the stack and could be popped off in sequence until I reached the offending name).

EDIT: Of course, this was for single formulae... For your problem, a cyclic graph of variable assignments would be the better way to go.

Answer 2

A solution (probably not the best) is to create a dependency graph.

Each time a function is added or changed, the dependency graph is checked for cylces.

This can be cut short. Each time a function is added, or changed, flag it. If the evaluation results in a call to the function that is flagged, you have a cycle.

Example:

a = b

• flag a
• eval b (not found)

• unflag a

  b = c

• flag b

• eval c (not found)

• unflag b

  c = a

  • flag c
  • eval a
  • eval b
  • eval c (flagged) -> Cycle, discard change to c!
  • unflag c

Answer 3

In reply to the comment on answer two:

(Sorry, just messed up my openid creation so I'll have to get the old stuff linked later...)

If you switch "flag" for "push" and "unflag" for "pop", it's pretty much the same thing :) The only advantage of using the stack is the ease of which you can provide detailed information on the cycle, no matter what the depth. (Useful for error messages :) )

Andrew

Answer 4

If I have somethig a bit diferent like:

A = B

B = C

C = D,B

D = C,A

Somebody have a problem like this?

Any solution???

Thanks and sorry by english.