Ackermann Challenge

This week’s first Perl Weekly Challenge is to produce reductions of Ackermann functions. If you’ve never run into the Ackermann function, it’s a mathematical construct (actually a family of them, but we’ll focus on the one in the challenge) that is described as a function that takes two integers. Its result is either an integer or some combinations of Ackermann functions. Here is the statement of the puzzle that explains a bit:

Perl Weekly Challenge 017.1

Create a script to demonstrate Ackermann function. The Ackermann function is defined as below, m and n are positive number:

  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

Example expansions as shown in wiki page.

 A(1, 2) = A(0, A(1, 1))
         = A(0, A(0, A(1, 0)))
         = A(0, A(0, A(0, 1)))
         = A(0, A(0, 2))
         = A(0, 3)
         = 4

Grammar

Okay, so our goal is to take in something that looks like A(m, n) and step through the reduction rules until we reach an integer result. My first thought, here, was that this sounds like a parsing problem, and indeed, there’s quite a lot of meat on the bones of that approach. It allows us to dig into Perl’s parsing tools a bit, too.

So, let’s start with a grammar that matches the Ackermann function:

grammar Ackermann {
	rule TOP {^ <ackermann> $}
	rule ackermann { <number> | <function> }
	token number { "-"? \d+ }
	rule function {
		'A' '(' $<m> = <ackermann> ',' $<n> = <ackermann> ')'
	}
}

This can be used directly to match any valid Ackermann function:

if Ackermann.parse("A(1, A(2, 3))") {
	say "We have Ackermann!"
}

Resolution

But that is just the first step. To reduce an Ackermann function, we need to know what parts of it are currently reducible. So we can add a rule to the grammar that matches when a function just has two integer parameters:

	rule resolvable {
		'A' '(' $<m> = <number> ',' $<n> = <number> ')'
	}

Notice the extra variables, there? Those are storing the numbers for easy access.

Now, all we need to do is write the function that executes the match and does the reduction:

sub regexA(UInt $m, UInt $n, :$verbose=False --> UInt) {
	my $ack = "A($m, $n)";
	say $ack if $verbose;
	while $ack !~~ /^ <Ackermann::number> $/ {
		$ack .= subst(
			/$<A> = <Ackermann::resolvable>/, 
			-> $/ {
				when $<A><m> eq "0" { $<A><n> + 1 }
				when $<A><n> eq "0" { "A({$<A><m> - 1}, 1)" }
				default { "A({$<A><m> - 1}, A($<A><m>, {$<A><n> - 1}))" }
			},
			:global);
		say "\t = $ack" if $verbose;
	}
	+$ack;
}

Analysis

When our replacement block (the second parameter to .subst) is called, we get the special variable ($/) populated for us. I’m taking it as a parameter, here, explicitly, just to make it clear that that’s what’s going on, but this code works equally well if we take out the -> $/.

This special variable can be indexed normally as $/<name> to get the named match within the angel-brackets, but there’s a special case for $/ that lets us just refer to $<name>. Here, I use this to access $<A><m> and $<A><n>, which is to say, what Ackermann::resolvable matched (stored into $<A>, explicitly) and within that match, what the first and second <number> matched (stored, respectively into $<m> and $<n>).

Next up, notice that our strings contain code. Any string or regex in Perl 6 can contain a block of code, delineated by {...} and it will cause the block of code to be executed and its value interpolated (in a string) or ignored (in a regex, in which it’s used solely for side effects like failing the match). So, all we have to do to format an Ackermann function is to put it in a string:

"A({$m - 1}, 1)"

That’s it. Our $m gets decremented and the stringification of that number is interpolated into the resulting string, giving something like "A(0, 1)".

Finally, note that when $verbose is set, this function will print its progress, per the rules of the challenge, like so:

$ ackermann.p6 --regex --verbose 2 1
A(2, 1)
	 = A(1, A(2, 0))
	 = A(1, A(1, 1))
	 = A(1, A(0, A(1, 0)))
	 = A(1, A(0, A(0, 1)))
	 = A(1, A(0, 2))
	 = A(1, 3)
	 = A(0, A(1, 2))
	 = A(0, A(0, A(1, 1)))
	 = A(0, A(0, A(0, A(1, 0))))
	 = A(0, A(0, A(0, A(0, 1))))
	 = A(0, A(0, A(0, 2)))
	 = A(0, A(0, 3))
	 = A(0, 4)
	 = 5
5

The full version of my solution, which includes five separate solutions, each invoked via a different command-line option, can be found here:

ackerman.p6

Here is a quick timing comparison of the various methods:

$ for mode in given multi iterative regex array ; do \
   echo "Mode: $mode"; \
   time ackermann.p6 --count=50 --$mode 3 1 >/dev/null \
     || break; \
  done

Mode: given

real	0m0.468s
user	0m0.707s
sys	0m0.036s

Mode: multi

real	0m0.612s
user	0m0.865s
sys	0m0.029s

Mode: iterative

real	0m0.559s
user	0m0.886s
sys	0m0.057s

Mode: regex

real	0m1.969s
user	0m2.313s
sys	0m0.032s

Mode: array

real	0m0.529s
user	0m0.889s
sys	0m0.024s