LanX has asked for the wisdom of the Perl Monks concerning the following question:

Hi

Following a discussion about how to realize gather/take in perl5 as a lazy iterator (-> see in German perl-community.de) I wonder if it's possible to manipulate the callstack or respectively to switch between different callstacks.

Precisely, is it possible to make a call to a subroutine "take()" after entering act as if I did a "goto &take()" by poping the callinfos from the callstack to a different stack? And sometimes later I wood need to reestablish the callinfo in the stack to jump back to exactly the same position were I called take().

Maybe my English is not clear enough, look at this example: 

 {
    my $j=0;
    my $resume=0;

    sub gather {
	goto $resume if $resume;      # Dispatcher

	while (++$j<=5) {
	    $resume="getin", goto getout 
                 unless ( $j % 2 );   # Take
	  getin:
	}


	$resume=0;                    # Final exit
	return;

      getout:
	return $j;
    }
}


while ( my $a=gather() ) {
    print "<<$a>> ";                   # prints <<2>> <<4>>
}
would be much nicer to read and maintain if I was able to write kind of 
{
    my $resume=0;

    sub gather {
      unless ($resume) {                  # Dispatcher
	push @callstack,$resume;
	return;                
      }

	for my $j (1..5) {
	    take($j) unless  ( $j % 2 );   # Take even numbers
	}


	$resume=0;                         # Exit
	return;
    }

    sub take {
        $resume=shift @callstack;
        return @_;
    }

}

The "Dispatcher" and "Exit"-chunk of the gather-sub could be automatically added, and this behaviour would circumvent the problem that it's not possible to jump into foreach-loops.

This assembler-technique dates back to my 68000 programming and I'm well aware that the callstack in Perl has much more data then just the returnadress.

So once again: Are there any opcodes allowing manipulating the callstack in this manner? To make a sub-call act like a goto &sub afterwards without weird sideaffects???

This would lead to a general approach to continuations.

Thx

Rolf

Replies are listed 'Best First'.
Re: Callstack manipulation?
by plobsing (Friar) on Nov 01, 2008 at 19:19 UTC

    I'm pretty sure you can build what you're talking about out of Coro.

    AFAICT, it allows you to clone perl interpreters and jump between them, having only one active at a time. Since each perl interpreter has it's own callstack, this is, if I am not mistaken, analogous to your idea.

[reply]
      Well I saw coro, but "cloning the perl interpreter" sounds very expensive ... do you think this is a practical approach?

      Theoratically speaking: If it's possible to safely do a 'goto &sub' without leaving the call frame, why shouldn't it be possible to simulater this state of the engine right after the call ... it's just a "return" without moving the process-pointer.

      I'm not to fond about XS but maybe it would be possible to add this behaviour by intergrating special C Code manipulating the stack.

      Saying this a have only a superficial knowledge of the interpreter, maybe someone can point to serious sideeffects which strictly disallow this approach.

[reply]

        I'm sorry, I don't really know Coro all that well. Consulting the docs, it says that a coroutine consists of:

        • a callchain
        • a set of lexical variables
        • a C stack
        • @_, $_, $@, and $/

        Everything else is shared. I don't see how you could get around having the first three items kept seperate. The fourth item is likely to be small compared to the others.

        In terms of actually cloning the perl interpreter, a quick test (given bellow) shows that a new callchain is created rather than cloning the current one. So I guess I wouldn't describe the action as cloning

        Some benchmarking would probably be worthwhile to determine how much Coro actually costs in terms of time and space required. From there you can determine whether or not Coro is practical or not for your problem.

        use strict;
use warnings;

use Carp 'carp';
use Coro;

$\ = $/;

sub A {
    my $a = 1;
    async {
    print $a++;
    carp;
    cede;
    print $a++;
    }
    print $a++;
    carp;
    cede;
    print $a++;
}

A;

        [download]
[reply]
[d/l]
Re: Callstack manipulation?
by LanX (Saint) on Nov 01, 2008 at 21:53 UTC
    Motivation

    I think I should better motivate this, to show that it's not an entirely esoterical approach...

    With the following code I can easily simulate the semantics of List-Comprehensions which are quite popular in Python and Haskell. 

    
{
    my $list_ref=[];

    sub gather (&){
    my $code_ref=shift;

    my @list=();
    my $safe=$list_ref;
    $list_ref=\@list;

    &$code_ref;

    $list_ref=$safe;

    return @list;
    }

    sub take  {
    push @$list_ref, @_;
    return;
    }
}

@x= gather {
     for $c (1..10){   for $b (1..$c){   for $a (1..$b){  if ( $c**2 =
+= $b**2 + $a**2){
         take [$c,$b,$a]
     } } } }
 };
}

    [download]
    (OK that's an extreme example for generating Pythagorean triples, but I hope the idea is clear and you don't blame me for the perl's need for curlies)

    Now with the possibility to manipulate the call stack from within take(), it might be possible to use exactly the same syntax to produce a lazy iterator, just indicated by a switch. This could just be an additional attribute like @x=gather :lazy {...} to indicate a lazy generator.

    An alterbnate approach would be to transform every opcode for calling "take()" into a "goto take()" followed by a reentry label. I tried this using B::Deparse and reevaluating the changed code into the symbol table, but that's not straightforwardly done, because of many special cases in perl's syntax, where you can't simply put the reentry-label just after the call...

    That's why I beg for some peaces of the holy wisdom from the masters of opcodes ... ; )... before I start messing around by myself!

    The potential of manipulating the call stack in this way would not only simplify this task, but Perl5 could get coroutines for free not talking about the cheaper "yield"-semantic in python and ruby.

[reply]
[d/l]
[select]
      I don't quite see what's missing in Coro that wouldn't help already - and coroutine switches are cheaper than a method call (on GNU/Linux).
[reply]
        Saying that I'm mastering coro, would be a blatant lie!

        But for what I read in the pods, coro has it's own distinct variable space. So sharing variables and closures might be very complicated.

        And the docs from moritz for Perl6::GatherTake don't read as if he easily got along with coro.

        IMHO the solution I'm suggesting would be much simpler and lightweight. Why not a KISS approach?

        Cheers Rolf

[reply]

Back to Seekers of Perl Wisdom