How to define circular logic or recursion in a specialized expression evaluator?

Question

I wrote an experimental function analyzer that allows me to bind simple functions together, so when changing variables, all functions that rely on these variables (and functions that rely on these functions, etc.) are updated at the same time. The way I do this, instead of immediately evaluating the function when it came in, I save this function. Only when the output value is requested to evaluate the function, and I evaluate it every time the output value is requested.

For instance:

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. Each time "pi" or "rad" changes, I expect the results of 'area' and "perim" to change in kind. Similarly, if there were any functions depending on 'area' or 'perim', the results of these changes would also change.

Everything works as expected. The problem here is when the user enters a recursion - random or deliberate. There is no logic in my grammar — it's just an evaluator, so I cannot provide the user with a way to “break out” of recursion. I would like to prevent it altogether, which means that I need a way to detect it and declare the abusive input invalid.

For instance:

 a = b b = c c = a 

Currently evaluating the last line throws a StackOverflowException (while the first two lines evaluate to "0" - the undeclared variable / function is 0). What I would like to do is to detect a cyclic logical situation and prevent the user from entering such an operator. I want to do this no matter how deeply circular logic is hidden, but I have no idea how to do this.

Behind the scenes, for example, input lines are converted to tokens through a simple scanner, then into an abstract syntax tree using a manual recursive descent analyzer, then AST is evaluated. C # language, but I'm not looking for a solution for the code - the logic itself will be fine.

Note: this is a personal project that I use to find out how parsers and compilers work, so it is not critical for the mission - however, the knowledge that I remove from this, I plan at some point to start working in real life, Any the help you guys can provide will be greatly appreciated. =)

Edit: In case anyone is interested, this blog post describes why I'm trying to find out, and what I'm going out of it.

Answer 1

I had a similar problem with this in the past. My solution was to push variable names onto the stack when I was returning through expressions to check the syntax, and popping up when I left the recursion level.

Before I moved each variable name onto the stack, I would check if it was already there. If that were the case, it would be a circular link. I could even display the names of variables in a round chain of links (since they would be on the stack and they could be popped out sequentially until I get an abusive name).

EDIT: Of course, that was for single formulas ... For your problem, a cyclic schedule of variable assignments would be the best option.

Answer 2

The solution (perhaps not the best) is to create a dependency graph.

Each time a function is added or changed, the dependency graph is checked for the number of cycles.

It can be reduced. Each time a function is added or changed, mark it. If evaluation results in calling a function that is labeled, you have a loop.

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 (marked) -> Loop, discard change to c!
• unflag c

Answer 3

In response to comment on answer two:

(Sorry, just messed up my open creation, so I will have to knit the old stuff later ...)

If you switch the “flag” to “push” and “unflag” to “pop”, this is almost the same :) The only advantage of using the stack is the simplicity with which you can provide detailed information about the loop, regardless of depth. (Useful for error messages :))

Andrew