Help with recursion.

B

bordemstirs

Member
Okay, so I'm starting to write the bones of an evaluator (essentially an extension of modifier_eval(); ). My problem is... difficult to explain, or even understand what's causing it.
Code: 
string replace(string o, int s, int f, string n){
 buffer b;
 append(b,o);
 replace(b,s,f,n);
 return to_string(b);
}

//eval function for strings containing math commands. Very much WIP.
//current restriction, all mathlib functions must be passed with square brackets
float mathlibeval(string x,string sp){
 int pdepth;
 string inner;
 string c;
 string n;
 int open;
 int close;
 while (contains_text(x,"(")){
  open=0;
  pdepth=1;
  while(substring(x,open,open+1)!="(")open=open+1;
  close=open+1;
  if(contains_text(substring(x,open),")"))
   while(close<length(x)){
    c=substring(x,close,close+1);
	if(c=="(") pdepth+=1;
	if(c==")") pdepth-=1;
	if(pdepth==0) break;
	close=close+1;
   }
  else close=length(x);
  inner=substring(x,open+1,close);
  print(sp+"B: "+x+" -- "+inner);
  n=replace(x,open,close+1,to_string(mathlibeval(inner,sp+"-")));
  print(sp+"A: "+n);
  x=n;
 }
 print(sp+"E: "+x);
 return modifier_eval(x);
}
The string replace() is just because conversion to buffer was... being kind of a hassle, and I had no idea how to clear a buffer once filled with data. (buffer a="" threw an error)
So, when testing with
Code: 
ash mathlibeval("(2+4)-(0+1)");
ash mathlibeval("((2+4)-(0+1))");
I'm getting results that I can't really follow.
The first line works as hoped.
The second, somehow, when it takes everything within the outer-most parentheses and evaluates (at this point that being "6.0-1.0") when it comes back down to the first instance of mathlibeval() somehow the "5.0" result is placed after "6.0-" and it executes again.
Adding more parentheses merely repeats the behavior further times.
The print()s and sp parameter were added for debugging, but I'm still at a loss as to where the string is getting extra information.
 
Last edited:
StDoodle

StDoodle

Minion
set_length(buffer,0) should reset your buffer for you. As for the rest... I warned you. ;) I'll try to look at it more closely later when I've recovered more from being at the *shudder* mall.
 
B

bordemstirs

Member
StDoodle said:
set_length(buffer,0) should reset your buffer for you. As for the rest... I warned you. ;) I'll try to look at it more closely later when I've recovered more from being at the *shudder* mall.
Click to expand...

The mall? TODAY? I weep for your soul.

P.S. How did you not know there would be PEOPLE out there? *sympathy shudder*
 
StDoodle

StDoodle

Minion
Oh, I knew that was inevitable, but my wife and I both desperately needed new shoes. Such is life. I'm starting to feel better though. ;)

Still not recovered enough to be of much help, but I'm going to post an excerpt from zarqon's zlib that uses his own wrapper for modifier_eval(), which may help.
 

Attachments

  • bordemstirs.ash
    1.4 KB · Views: 38
jasonharper

jasonharper

Developer
This is a mafia bug. Replacing:
PHP: 
  n=replace(x,open,close+1,to_string(mathlibeval(inner,sp+"-")));
with:
PHP: 
  string rep = to_string(mathlibeval(inner,sp+"-"));
  n=replace(x,open,close+1,rep);
is a work-around.

The problem is that the first three parameters to replace() in the outer call to mathlibeval() are being overwritten by the replace() in the recursive call to mathlibeval(). Basically, replace() needs to have its parameters saved just like those of a recursive function, even though that function is not recursive itself. This doesn't look like an easy fix, so avoiding the problem entirely (by doing recursive calls in a statement with no other calls) seems best for the moment.

EDIT: Your code could be made a lot more efficient by using index_of() to detect & locate the open parenthesis without having to examine each character individually. Or perhaps last_index_of() - doing the replacements in reverse order would probably reduce the recursion depth, and reduce the number of characters that had to be examined to find the matching close parenthesis.
 
Last edited:
jasonharper

jasonharper

Developer
Here's a minimal example of the problem:
PHP: 
void p2(int a, int b)
{
	print(a + " " + b);
}

int bad(int level)
{
	if (level > 0) {
		p2(level, bad(level - 1));
	}
	return level;
}

int good(int level)
{
	if (level > 0) {
		int temp = good(level - 1);
		p2(level, temp);
	}
	return level;
}

good(4);
print("");
bad(4);
Output is:
1 0
2 1
3 2
4 3

1 0
1 1
1 2
1 3
Click to expand...
 
B

bordemstirs

Member
jasonharper said:
EDIT: Your code could be made a lot more efficient by using index_of() to detect & locate the open parenthesis without having to examine each character individually. Or perhaps last_index_of() - doing the replacements in reverse order would probably reduce the recursion depth, and reduce the number of characters that had to be examined to find the matching close parenthesis.
Click to expand...

The way I have it now is just for the bare bones. It'll change a lot (the current method won't work at all for things like "sin(3,false)" so for now it's just a setup.) And even if I found open parentheses with index_of I'd still have to count characters to find the proper matching close.
I'm interested in reducing recursion depth, but I don't see how going end-backwards would be any more efficient than start-forwards... care to explain?
 
jasonharper

jasonharper

Developer
Now that I've thought about it some more, finding the open parens in reverse order would completely eliminate the need for recursion. The subexpression starting with the rightmost open paren obviously cannot contain any further parenthesized expressions; all you have to do is find the next close paren to locate the end of that subexpression. Assuming that the subexpression is replaced by something that does not itself contain parentheses, a single loop that finds the rightmost open paren on each iteration would do the entire job.

On the other hand, there's really no point in finding all subexpressions that are merely grouped by parentheses (modifier_eval() handles those already), just the ones that are parameters to the functions you're implementing. That might be better done by a regexp, something like "(sin|cos|tan)\\(" - group(1) gives you the function name, start() gives you the index to start replacing, end() gives you the index to start extracting the parameter subexpression. Unfortunately, there is no efficient "find rightmost match" operation for regexps, so you're back to full recursion in order to find all your function calls.

You can still use the string functions to find the matching close paren without examining each individual character, it's just a bit trickier. Not tested:
PHP: 
close = open + 1;
pdepth = 1;
nextopen = index_of(x, "(", close);
nextclose = index_of(x, ")", close);
while (pdepth != 0) {
    if (nextclose == -1) abort("unclosed parentheses");
    if (nextopen != -1 && nextopen < nextclose) {
        pdepth += 1;
        nextopen = index_of(x, "(", nextopen + 1);
    } else (    // nextclose < nextopen
        close = nextclose;
        pdepth -= 1;
        nextclose = index_of(x, ")", nextclose + 1);
    }
}
 
B

bordemstirs

Member
Find rightmost -open- parentheses... Okay. That makes way more sense. I could see how that would make recursion depth heavily reduced (to a max of one, if I'm not overlooking anything. And I could do it without the need for regex on any of my operations.

Super convenient for me that a new function called char_at was just implemented. My first attempts at just ndexing string were foiled.
 
StDoodle

StDoodle

Minion
Does anyone else find it amazing that no one has yet to respond with "For help with recursion, please look for help with recursion?" Oops.
 
You must log in or register to reply here.
Top