Re^4: Sorting, recursion, and tail-call optimizations

BrowserUk,
I am not sure I agree. The user defined sub is getting called in both cases as a comparator and there doesn't appear to be any ambiguity. By putting a print statement inside the sub, I can count how many times it is called. 52 for the working version and 2 for the b0rk version before it blows up.

Now here is where it gets interesting, if I include $a and $b in the print statement I discover that in the first call both variables are set to two different array refs (as expected). On the second call (the one that blows up), neither variable is defined???

sub my_sort {
    print "hello there $a $b\n";
    my $i = $_[0] || 0;
    ...
}
__END__
hello there ARRAY(0x1868244) ARRAY(0x1868298)
Use of uninitialized value in concatenation (.) or string at ...
Use of uninitialized value in concatenation (.) or string at ...
hello there

*** BOOOOM ***
[download]

Cheers - L~R

Comment on Re^4: Sorting, recursion, and tail-call optimizations Download Code

Replies are listed 'Best First'.
Re^5: Sorting, recursion, and tail-call optimizations by BrowserUk (Patriarch) on Jan 06, 2006 at 17:47 UTC
Ah! Where does the value/variable in `$_[0]` that you are incrementing come from? If the comparator sub/block is not passed anything, then you are messing with a random lump of 'stack'. Better to use a closure there perhaps?. Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal? "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice.	[reply] [d/l]
Re^6: Sorting, recursion, and tail-call optimizations by Limbic~Region (Chancellor) on Jan 06, 2006 at 18:00 UTC
BrowserUk, While $a and $b shouldn't have anything to do with @_, let me explain anyway: The 1st time the function is called with no arguments, $i become 0 to compare the first value of the array. If the values of both arrays are equal at index $i, $_[0] is incremented by 1 which auto-vivifies into existence if necessary When goto &sub is invoked subsequently, @_ has a value which is used for $i After explaining, I verified that $_[0] is behaving correctly in the b0rk version using the print statements. It still doesn't explain why $a and $b are undefined on the second invocation or why it blows up? Cheers - L~R	[reply]
Re^7: Sorting, recursion, and tail-call optimizations by BrowserUk (Patriarch) on Jan 06, 2006 at 18:33 UTC
You miss my point. I'm not talking about $a & $b. When the comparator is first called, if no parameters are passed, then @_ should be empty and $_[0] is "undefined". That's not undefined, but undefined in the non-useful, undefinable, implementation dependant, DO NOT USE sense. $_[0] obviously is pointing (aliasing) somewhere, but where? My best guess is that @_ contains the contents of the previous stack frame. Ie. the contents of @_ when the comparator is called, are the same as those passed to the function that is calling the comparator. which would be sort. In which case, you are probably incrementing the address of the comparator itself--which would at least explain why it blows up! Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal? "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice.	[reply]
Re^8: Sorting, recursion, and tail-call optimizations by Limbic~Region (Chancellor) on Jan 06, 2006 at 18:45 UTC
Re^9: Sorting, recursion, and tail-call optimizations by BrowserUk (Patriarch) on Jan 06, 2006 at 19:07 UTC
Some notes below your chosen depth have not been shown here
Re^5: Sorting, recursion, and tail-call optimizations by kwaping (Priest) on Jan 06, 2006 at 18:29 UTC
I wonder if this might have something to do with it... If the subroutine's prototype is "($$)", the elements to be compared are passed by reference in @_, as for a normal subrou- tine. This is slower than unprototyped subroutines, where the elements to be compared are passed into the subroutine as the package global variables $a and $b (see example below). Maybe a prototype is being applied to the "borked" sub call?	[reply]
Re^6: Sorting, recursion, and tail-call optimizations by Limbic~Region (Chancellor) on Jan 06, 2006 at 18:34 UTC
kwaping, You can see in the code that I am not using any prototypes. Additionally, it would be really wacky if when sort called it the first time it didn't see it as a prototyped sub (used $a and $b) but when it got recursed the first time it did (using references in @_). I know this is not the case because I printed the values of @_ and they are correct. It is the undefined $a and $b and the mysterious blowing up that has me baffled. Cheers - L~R	[reply]
Re^7: Sorting, recursion, and tail-call optimizations by kwaping (Priest) on Jan 06, 2006 at 18:36 UTC
I know you're not implicitly prototyping the sub, just wondering if maybe there was some mysterious under-the-hood process that was applying one. But then, I (obviously?) have no idea about any of what I've posted in this thread. :)	[reply]