in reply to Ackerman vs. Perl : KO in 3 rounds

In 5.005 I get that you are trying to modify a readonly value.

I think a better implementation of the function (at least it runs properly for me) is: 

sub A {
  BARE_BLOCK: {
    if (0 == $_[0]) {
      return 1 + $_[1];
    }
    
    @_=($_[0] - 1, $_[1] ? A($_[0], $_[1]-1) : 1);
    redo BARE_BLOCK;
  }
}

[download]
Note that this really does save stack space. Although, considering what Ackermann's function does, this is (I suspect) a losing battle. :-)

Replies are listed 'Best First'.
Re: Re (tilly) 1: Ackerman vs. Perl : KO in 3 rounds
by John M. Dlugosz (Monsignor) on Dec 18, 2001 at 03:34 UTC
    Nice, using redo to explicitly perform tail-end recursion optomization. I'm wondering if the optimizer can figure that out?

    Hmm, but yours gives the wrong answer for A(3,3). (61 instead of 65536)

    —John

[reply]
[d/l]
      When Perl calls a recursive function it does a huge amount of work saving state, optimizing the next time you call it, etc. For a sobering comparison, compare the implementation above with the following one where I manage a stack explicitly instead of having a stack of function calls: 
      sub A {
  my ($x, $y) = @_;
  my @stack = ();
  while (1) {
    if (0 == $x) {
      if (@stack) {
        $y++;
        $x = pop(@stack);
      }
      else {
        return 1 + $y;
      }
    }
    else {
      if (0 == $y) {
        $x--;
        $y = 1;
      }
      else {
        push @stack, $x-1;
        $y--;
      }
    }
  }
}

      [download]
      Impressed?
[reply]
[d/l]
        Performace is the same: (3,3) => instantanious, while (4,3) => seemingly forever. (though it hasn't crashed yet, and memory usage is not growing)

        Seriously, thanks for posting that. It is a good idea for recursion in general in Perl, knowing what I just learned here.

[reply]
      Sorry. Perl can't detect tail-end recursion for you. In fact Perl's handling of deep recursion is truly horrible.

      As for whether my answers are right or wrong, they agree with this page...

[reply]
        The version of the function I was using is expressed cleanly by VSarkiss in this node. It gives 65536.

        The Perl code reads exactly from the piece definition, adding a few $ symbols, a *, and semi's. It makes every condition explicit, and don't rely on narrowing constraints and order of definition. So I'm pretty sure that's a correct implementation.

        I suppose there are multiple versions of Ackerman's idea, all working in the same way, but different in detail.

        —John

[reply]

In Section Meditations