really, really bored?

Posts you want to find years later go here.

really, really bored?

Postby Peijen » Wed Jul 12, 2006 2:00 pm

what does this do? Let # be some operator, and iter be some implementation of iterator.
Code: Select all
f(iter, p)
{
  if (iter == null)
  {
    ();
  }
  else
  {
    f(iter++, {iter#p;});
  }
}

And how is it different than
Code: Select all
f(iter, p)
{
  if (iter == null)
  {
    ();
  }
  else
  {
    f(iter, {iter++#p;});
  }
}
Last edited by Peijen on Thu Jul 13, 2006 2:25 am, edited 1 time in total.
Peijen
Minion to the Exalted Pooh-Bah
 
Posts: 2778
Joined: Fri Jul 18, 2003 1:28 pm
Location: Irvine, CA

Postby quantus » Thu Jul 13, 2006 1:56 am

What is iter? I'll assume it's some class that implements an iterator...

I think that f(iter++, {iter#p;}) increments iter after the function returns while f(iter, {iter++#p;}) increments iter after exiting the innermost {}'s which is kinda like saying f(++iter, {iter#p;}).

I don't think the first version of the code works because it doesn't actually increment iter leaving you stuck on the first element, but the second one should.

What the function does is dependent on what iter is overloaded to do with # typeof(p).
Have you clicked today? Check status, then: People, Jobs or Roads
User avatar
quantus
Tenth Dan Procrastinator
 
Posts: 4653
Joined: Fri Jul 18, 2003 2:09 am
Location: San Jose, CA

Postby Peijen » Thu Jul 13, 2006 2:25 am

quantus wrote:What is iter? I'll assume it's some class that implements an iterator...

Yeah sorry, I should've mentioned that.

As for the rest of your post, I am pretty sure neither version works correctly as intended. But I wasn't sure if iter++ increments before or after the function returns.

I will post what I think would happend Friday in case the others who would've an idea what's going on wanted to answer.
Peijen
Minion to the Exalted Pooh-Bah
 
Posts: 2778
Joined: Fri Jul 18, 2003 1:28 pm
Location: Irvine, CA

Postby quantus » Thu Jul 13, 2006 6:20 pm

Peijen wrote:I am pretty sure neither version works correctly as intended.

So, does this mean you didn't know what the code was supposed to do either? How do you know what was intended then?
Have you clicked today? Check status, then: People, Jobs or Roads
User avatar
quantus
Tenth Dan Procrastinator
 
Posts: 4653
Joined: Fri Jul 18, 2003 2:09 am
Location: San Jose, CA

Postby Peijen » Fri Jul 14, 2006 6:38 pm

Assume the collection, c, has n element, the goal of the code is to produce.
c[0]#...#c[n-1]#p();

The first code doesn't work because as Joe points out, iter++ does not increment until the recursive call returns which is never. Although I wasn't sure if that's the case or not (that was the original question I had).

The other issue to consider is if we replace the line with f(++iter, {iter#p}); Does {iter#p} passes c[i]#p or simply iter#p to the next recursive call? This makes a difference because the end result would looks like one of these, assume 3 elements:
iter#iter#iter#p();
c[0]#c[1]#c[2]#p();
The first case iter is null and does not produce the desire result, while the second one does. My guess is it depeneds on the language you are using.

The second code doesn't work because {iter++#p} does not get evaluated until iter==null which never happends.
Peijen
Minion to the Exalted Pooh-Bah
 
Posts: 2778
Joined: Fri Jul 18, 2003 1:28 pm
Location: Irvine, CA

Postby quantus » Fri Jul 14, 2006 10:40 pm

Peijen wrote:The second code doesn't work because {iter++#p} does not get evaluated until iter==null which never happends.

Is this true? Did you try it? I would think it had to evaluate the {} before making the next function call, which means that iter is getting incremented. Also, I was wrong in saying that f(++iter,{iter#p}) is kinda the same as f(iter,{iter++#p}) because the ++iter means that iter gets incremented before the {} part which would skip the first element in iter. By using {iter++#p}, you put the increment after the calculation, but before the actual function call.

Really, this is poor style since the order of operations is obfuscated by wrapping values in {}. Really, the {} is computed previous to the function call and should be written to reflect this ordering. It should not be burried within the function call itself even though it is less typing to do so.

One issue is, where are you storing your result? It looks to me like nothing actually gets returned by this function since it eventually evaluates to () and that's what it returns. I think what you meant to do is return p at the end...

I think there's also another bigger problem here in that the order of execution is different than what you wrote in your explanation.

You're doing c[2]#(c[1]#(c[0]#p)) and not c[0]#c[1]#c[2]#p. If # is not an associative operation, then the results will be different!
Have you clicked today? Check status, then: People, Jobs or Roads
User avatar
quantus
Tenth Dan Procrastinator
 
Posts: 4653
Joined: Fri Jul 18, 2003 2:09 am
Location: San Jose, CA

Postby Peijen » Sat Jul 15, 2006 6:32 pm

look up continuation passing style
Peijen
Minion to the Exalted Pooh-Bah
 
Posts: 2778
Joined: Fri Jul 18, 2003 1:28 pm
Location: Irvine, CA

Postby quantus » Tue Jul 18, 2006 3:01 am

Ok, so this is done to use tail call optimization which essentially turns a recursive function into an iterative function? You don't have to embeb all of the work into the function call itself. The following should work just fine even if it is considered less elegant, I think it's way easier to read:
Code: Select all
f(iter, p)
{
  if (iter == null)
  {
    ();
  }
  else
  {
    k = iter++#p;
    f(iter, k);
\\ or you can do the following with the same effect.
\\  k = iter#p;
\\  f(++iter, k);
  }
}

Either way, there's no ambiguity of what happens when.

Also, I believe there's still the issue of order of operations.
Have you clicked today? Check status, then: People, Jobs or Roads
User avatar
quantus
Tenth Dan Procrastinator
 
Posts: 4653
Joined: Fri Jul 18, 2003 2:09 am
Location: San Jose, CA


Return to The Vault

Who is online

Users browsing this forum: No registered users and 1 guest

cron