in reply to Re^8: Who's a thief? (No memory growth with magic goto)
in thread Who's a thief? -- the follow up

I simply meant that I don't see any easy way of avoiding the goto in these mutually recursive routines: 

#! perl -slw
use strict;

my( $count1, $count2 );

sub a1 {
    b1( $_ [ 1 ] );
    goto &a2;
}

sub a2 {
    $count1++;
    $_[ 0 ]-- and goto &b2;
}


sub b1 {
    $_[ 0 ]-- and goto &b2;
}

sub b2 {
    $count2++;
    goto &a2;
}

my( $n1, $n2 ) = ( 100, 50 );
a1( $n1, $n2 );

print "c1: $count1; c2: $count2";

__END__
[15:37:55.16] P:\test>mutrec
c1: 151; c2: 150

[download]

This is not a particularly useful example, but imagine that one (pair) are reading a huge XML file for instance, and the other is validating it.

Rather than having to read the whole file, the first reads a bit and the second processes a bit and the first reads a bit more and so on. Both retain their own state across calls to the other. Think coroutines; a consumer and producer that each retain their running state, whilst switching control between themselves

Examine what is said, not who speaks.
Silence betokens consent.
Love the truth but pardon error.

Replies are listed 'Best First'.
Re^10: Who's a thief? (No memory growth with magic goto)
by Aristotle (Chancellor) on Jan 18, 2005 at 07:08 UTC

    If you're not afraid to call it like it is, then it sure is possible. It did take three refactors until I got it as clear as this, though:

    #!/usr/bin/perl
use strict;
use warnings;

my( $count1, $count2 );

sub a1 {
    a2b2( --$_[ 1 ],  1 );
    a2b2(   $_[ 0 ], !1 );
}

sub a2b2 {
    $_[ 1 ] or goto a2;
    {
        b2: $count2++;
        a2: $count1++;
        $_[ 0 ]-- and redo;
    }
}

my( $n1, $n2 ) = ( 100, 50 );
a1( $n1, $n2 );

print "c1: $count1; c2: $count2\n";

    [download]

    Makeshifts last the longest.

[reply]
[d/l]

      My first reaction was "Wow!" :)

      My second was that I did say "...easy way...", which I think you proved, and "...without the goto...", which you still have, albeit not the magic form.

      The origins of the thoughts come from my experiments with Haskell, where a (perlised) architypical example might be: 

      #! perl -slw
use strict;

sub even { $_[ 0 ]-- and goto &odd; 1; }
sub odd { $_[ 0 ]-- and goto &even; 0 }

while( my $i = int rand 1000000 ) {
    print "$i is ", odd( $i ) ? 'odd' : 'even';
}

__END__
P:\test>mutrec2.pl
535003 is odd
775573 is odd
663116 is even
945678 is even
443572 is even
869659 is odd

      [download]

      Which I hate to post because (a) it seems like a particularly stupid and inefficeint way to do this, and (b) I am entirely unconvinced, despite the obvious similarities between this and the mathematical formulations, that these are any more "proveably correct", than 

      sub odd { $_[ 0 ] & 1 }
sub even { !odd( $_[ 0 ] }

      [download]

      And I know which I prefer to write, read or use.

      However, the notion of mutual recursion in Haskell, and that of coroutines (some thing else I've a facination for) came together mind.

      The idea that I tried to capture--but failed I think--with the snippet of paired coroutines above is:

      • You enter the "outer" sub of the first pair, it has a stack frame, sets up local vars etc.
      • At some point, it makes a normal call to the "outer" of the second pair of routines, therebye setting up a stack frame and context for that pair.
      • The "outer" of the second pair, does a magic goto to the "inner" of that pair, thereby transering the outer context to the inner pair and avoiding setting up another level of stack frame.
      • It then does some processing with the context of it's outer sibling, before transfering control to the inner of the first pair via magic goto.
      • The inner routine of the first pair now does some processing within the context of it's outer sibling, before transfering control back to the inner of the second pair.
      • The cycle of the inners doing something and swaping control until one of them is finished, at which point it returns control to it's outer sibling to finish up and the recursion ends.

      Note: The snippet I posted does not achieve this. It requires nesting the inner subs (anonymously) so that the close over the outer subs local vars and stack frame. I kind of have something working but its messy and complicated. I think I can simplify it given enough thinking time.

      Much of this comes about from following the parrot list and trying to understand how they intend to provide coroutines (for iterators and the like) by using ubiquitous continuations.

      Coroutines aren't the only use for continuations, but they do seem to be a fairly major and desirable reason for having them. However, having followed (as best I could) some of the discussions regarding the difficulties and costs of providing ubiquitous continuations, I got to thinking about how you could provide for coroutines without using continuations.

      In essence, I think that this mechanism does that, though as I said, it still needs (lots?) work. All that is speculative, ill-thought through and probably shows up the limits of my understanding of continuations; but that's where the original thought stems from.

      Examine what is said, not who speaks.
      Silence betokens consent.
      Love the truth but pardon error.
[reply]
[d/l]
[select]

        Yeah, I could see roughly what you were getting at. That is, after all, why I left the control flow as is (and even preserved all the side effects!) rather than doing this particular example the straightforward O(1) way.

        Makeshifts last the longest.

[reply]

In Section Meditations