Veesh

This week's perl weekly challenge was a lot of fun. First of all, challenge number 2 was a breeze. The challenge was to parse and print the components of a URL. That was easy...

use Mojo::URL;

my $url = Mojo::URL->new(shift);
say <<"ANSWER"
scheme:   ${\$url->scheme}
userinfo: ${\$url->userinfo}
host:     ${\$url->host}
port:     ${\$url->port}
path:     ${\$url->path} 
query:    ${\$url->query}
fragment: ${\$url->fragment}
ANSWER

To be fair, you're supposed to come up with an answer yourself, but come on, Mojolicious is fun! To print, I use an interpolating here-doc, and use a cool dereferencing trick to be able to print method calls in an interpolation.

The real interesting part was challenge number 1. I never went to school for programming, so I wasn't familiar with the concept of an Ackermann function. Looking at the problem, I immediately saw that I could easily translate the description:

A(m, n) = n + 1                  if m = 0
A(m, n) = A(m - 1, 1)            if m > 0 and n = 0
A(m, n) = A(m - 1, A(m, n - 1))  if m > 0 and n > 0

into fully functional perl6 code, making it my first perl6 script!

multi sub A( $m where 0, $n ) { $n + 1 }
multi sub A( $m, $n where 0 ) { A($m - 1, 1) }
multi sub A( $m, $n )         { A($m - 1, A($m, $n - 1)) }

sub MAIN ( Int $m, Int $n ) { say A($m, $n) }

All we needed to do was translate the constraints to the right place, and put multi sub before each function definition and BAM, we're off.

But......

I quickly (rather slowly, actually) discovered that the ackermann function grows ridiculously fast. It only took 0.198 seconds to run the A(1,2), but trying to run something bigger, like A(4,1), took upwards of an hour and a half, I stopped waiting for it...

Which is way too long.

Fine, so let's try and solve that. The problem here is that we're making a ridiculous amount of recursive calls. Many of those calls are calculated numerous times, for example, in the expansion of A(4,1), it calls many values from the A(3) series repeatedly, which in turn call more repeated values from the A(2) series, etcetera.

This is because every time there's an expansion where $m (our first variable) is greater than 1, it expands to every value up until $n in the $m-1 series. And then does it again with the total from the calculation until it goes down an $m. And then does it again for the $m-2 series.

So the simple solution to this problem is memoization, which means storing the values that get returned in a hash, to be recovered later if the same arguments are passed to the function. That looks very simply like this.

sub A ($m, $n) { state %memoize; %memoize{$m}{$n} //= _A($m, $n) }

where we renamed our old function to _A, and replaced it with a new function, which declares a hash for itself, and then checks for and returns an already found value, or runs our inner _A function.

That takes the time from forever, down to about 8.5 seconds. Which isn't so bad at all. But let's see if we can make this thing EVEN FASTER!

It takes time to do multiple dispatch, so let's do away with that and implement it all in one function: sub _A ( $m, $n ) { return $n + 1 unless $m; return A( $m - 1, 1 ) unless $n; return A( $m - 1, A($m, $n - 1) ) }

That's basically the same idea, just using postconditionals. This takes our running time further down to 1.6 seconds, which is much nicer. Now, if you'd take that same script (with sigils properly adjusted) to perl5:

use v5.22;
use bigint;

sub A {
  my ($m, $n) = @_;
  state %memoize;
  $memoize{$m}{$n} //= _A($m, $n)
}

sub _A {
  my ($m, $n) = @_;
  return $n + 1 unless $m;
  return A( $m - 1, 1 ) unless $n;
  return A( $m - 1, A($m, $n - 1) )
}

say A( shift, shift );

You'd see that the perl5 version only runs in 6.5 seconds. Which is... surprising. The perl6 version is a good 5 times faster.

Now, part of that discrepancy is because the perl5 version is using bigint, which p6 uses by default. Why do we use bigint? Because the next part, calculating A(4,2), results in a number that's, ehm... 19,728 digits long.

By perusal of the wikipedia page, I see that there's a formula for calculating the numbers from the function:

Apparently, the arrow is a hyperoperator (not the same as the perl6 type though). A hyperoperator repeats the operator one dimension below itself for a specified amount of times. The first ↑ (Knuth up arrow) means repeated multiplication, meaning 2 ↑ 3 is the same as 2 ^ 2 ^ 2. Every additional ↑ makes it that the previous operator is repeated. This means that 2 ↑↑↑ 3 is the same as 2 ↑↑ 2 ↑↑ 2, which is 2 ↑↑ (2 ↑ 2), which is 2 ↑↑ 4, which is 2 ^ 2 ^ 2 ^ 2, which is 65536.

So let's try to implement THAT, which hopefully will allow us to at least think we printed A(4,2) correctly. And in decent time.

sub arrow ( Int $base, Int $times, Int $arrows ) {
  return $base ** $times if $arrows == 1;
  ($base xx $times).reduce: { arrow($^base, $^accumulator, $arrows - 1) }
}

sub A ( $m, $n ) {
  return $n + 1     if $m == 0;
  return $n + 2     if $m == 1;
  return 2 * $n + 3 if $m == 2;
  arrow( 2, $n + 3, $m - 2 ) - 3
}

multi sub MAIN ( Int $m, Int $n ) {
  say A($m, $n)
}

First, we define our hyperoperator. It takes first the base, then the amount of times to apply the arrows, and then the number of arrows. We then make a list of $times bases, and then use the reduce function to repeat the same for every item on the list, just with one less arrow this time. It continues until there's only one arrow, which is simple exponentiation.

This function is based on the one I found in Math::Arrow, except I cleaned it up a little, by using twigils inside of the reduce block. These allow me to name the variables to be clearer. They pull values off of the list in alphabetical (unicode) order, so $^accumulator is the first argument, very aptly named, and $^base is the next base pulled off of the list.

Then we apply the formula from Wikipedia in our new A function, where we add some edge cases that the arrow function can't cover.

This version calculates A(4,1) in .2 seconds, and gasp A(4,2) in .5 seconds. Not bad at all. And it's still better than the p5 version, which clocks in at .6 seconds.

I tried A(4,3), but that needs to calculate 2^A(4,2), so I'm not sure if that'll ever happen.

EDIT:

I figured out what was wrong with my perl5 version, and here it is:

use v5.22;
use List::Util qw/reduce/;
use bigint;

sub arrow  {
  my ($base, $times, $arrows) = @_;
  return $base ** $times if $arrows == 1;
  reduce { arrow($b, $a, $arrows - 1) } ($base) x $times
}

sub A  {
  my ($m, $n) = @_;
  return $n + 1     if $m == 0;
  return $n + 2     if $m == 1;
  return 2 * $n + 3 if $m == 2;
  arrow( 2, $n + 3, $m - 2 ) - 3
}

say A(shift, shift)

The only real differences here are that perl5 doesn't have a built in reduce function, so I need to import it, and the explicit use of bigint. Also, p6 has a xx operator which repeats the left operand as a list, whereas in p5, you need to explicitly give the x operator a list to repeat.

The takeaways:

1. I'm very stubborn. It was my goal this week to get A(4,2) to print.
2. Perl6 can run even faster than perl5 sometimes
3. Math can be fun, too. I finally got to understand what Knuth Up Arrows are!