Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical
 
PerlMonks  

Re^8: Who's a thief? (No memory growth with magic goto)

by demerphq (Chancellor)
on Jan 15, 2005 at 09:54 UTC ( #422487=note: print w/replies, xml ) Need Help??


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

Well, thats true I suppose but im not sure its entirely relevent, the tail recursion optimization only applies to subs which call themselves as the last statement. So insofar as the mutually recursive routines are tail recursive as well this optimization pattern still applies.

For those that dont know, (not you BrowserUK) tail optimization is really only _important_ in languages without looping constructs, in any language with looping constructs its just a nice bonus.

---
demerphq

  • Comment on Re^8: Who's a thief? (No memory growth with magic goto)

Replies are listed 'Best First'.
Re^9: Who's a thief? (No memory growth with magic goto)
by BrowserUk (Pope) on Jan 15, 2005 at 15:50 UTC

    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

    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.

      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";

      Makeshifts last the longest.

        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

        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 ] }

        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.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://422487]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (7)
As of 2019-11-13 19:50 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Strict and warnings: which comes first?



    Results (74 votes). Check out past polls.

    Notices?