in reply to Weird syntax. What does this goto statement do?

A simple state machine (with information missing): 

         INITIAL_STATE  SOME_STATE     FINAL_STATE
         +-----+        +-----+        +-----+
start--->|     |---+--->|     |------->|     |--->accept
         +-----+   |    +-----+        +-----+
                   |       |
                   +-------+

[download]

We can imagine a state machine as a bunch of gotos. 

INITIAL_STATE: {
   ...
   goto SOME_STATE;
}

SOME_STATE: {
   ...
   if ( ... ) {
      goto SOME_STATE;
   } else {
      goto FINAL_STATE;
   }
}

FINAL_STATE: {
   ...
}

[download]
We could replace those gotos with sub calls. 
sub initial_state {
   ...
   return some_state();
}

sub some_state {
   ...
   if ( ... ) {
      return some_state();
   } else {
      return final_state()
   }
}

sub final_state {
   ...
   return;
}

initial_state();

[download]

The stack will keep growing and growing unless we perform tail call elimination, which can be done using goto &SUB 

sub initial_state {
   ...
   goto &some_state;
}

sub some_state {
   ...
   if ( ... ) {
      goto &some_state;
   } else {
      goto &final_state;
   }
}

sub final_state {
   ...
   return;
}

initial_state();

[download]

This is the approach used by the code in question. goto &sub is slow, though. (Slower than a sub call.) I think we could use a loop to speed things up. 

sub initial_state {
   ...
   return \&some_state;
}

sub some_state {
   ...
   if ( ... ) {
      return \&some_state;
   } else {
      return \&final_state;
   }
}

sub final_state {
   ...
   return undef;
}

my $state = \&initial_state;
while ( $state ) {
   $state = $state->();
}

[download]

The code in question appears to have some code place to support this. It "returns" the new handler sub (by assigning it to $_[0]->{state}), but it never ends up using it.

Replies are listed 'Best First'.
Re^2: Weird syntax. What does this goto statement do?
by LanX (Saint) on Jan 04, 2024 at 00:32 UTC
    I think tail call elimination aka optimization is wrong here , because it's not optimized in Perl (you noted it's slow)

    One can call it tail-call (without elimination)

    TCE in languages like LISP optimize calls to jumped and can replace the necessity for loop constructs.

    > by assigning it to $_[0]->{state}), but it never ends up using it.

    It does, but only once as Boolean test.

    > goto &sub is slower

    Really? I expected the same...

    But I kind of remember that the implementation is awkwardly cleaning the frame right after it was created...

    > I think we could use a loop

    I had a similar idea, but I would return names not references, and store current-state inside the loop. This would improve readability a lot and allow to easily trace/log the execution.

    Will add tested code tomorrow

      ... To be continued ...

    update
    use v5.14;
use warnings;


my ($state,$last);

sub initial_state {
    say "*** Initializing";
    return "some_state";
}

sub some_state {
  my $in = shift;
  if ( not $in ) {
    return "some_state";
  } else {
    return "final_state";
  }
}

sub final_state {
  say "*** Finalizing";
  return undef;
}


$state = "initial_state";

my @input = (0,0,0,1);
my $log = 1;
while ( $state ) {
  $last  = $state;
  my $in = shift @input;
  no strict 'refs';
  $state   = $state->($in);
  say "$last \t--($in)-> \t$state" if $log && $state;
}

    [download]
    --> 
    *** Initializing
initial_state     --(0)->     some_state
some_state     --(0)->     some_state
some_state     --(0)->     some_state
some_state     --(1)->     final_state
*** Finalizing

    [download]

    Cheers Rolf
    (addicted to the Perl Programming Language :)
    see Wikisyntax for the Monastery

[reply]
[d/l]
[select]

      I think tail call elimination aka optimization is wrong here , because it's not optimized in Perl (you noted it's slow)

      A slow tail call elimination is still a tail call elimination. While it may be used as a speed optimization in other languages, it has another benefit: Not generating a new stack frame. This optimization of memory usage could even be considered the main reason for using it (allowing recursion to be used to create loops without extra memory usage). This is the reason for using tail call elimination that's relevant here, as I mentioned.

      I would return names not references

      Also called symbolic references. So yeah, that works. One doesn't even need to turn off strict if you call them as methods ($self->$method()). I was keeping size and complexity minimal.

      It does, but only once as Boolean test.

      ah, I missed that. Still, the gist of what I said is still accurate.

[reply]
[d/l]

In Section Seekers of Perl Wisdom