Perl and XS: Example 2: Math::Ackermann

1. Introduction
2. Concepts
3. Example 1: Geometry
4. The typemap
5. Example 2: Math::Ackermann
6. Example 3: Set::Bit

Design

This article is an example of representing data in Perl. The next article is an example of representing data in C.

Example 1: Math::Ackermann

Ackermann's function is mostly used in computer language benchmarks. It is defined recursively as

A(0  , n  ) = n + 1
A(m+1, 0  ) = A(m, 1)
A(m+1, n+1) = A(m, A(m+1, n))

It consumes enormous amounts of RAM and CPU with very little code.

We want to compute the function in C and cache the results. Caching values is easy in Perl.

package Math::Ackermann;

sub new
{
    my $class = shift;
    bless [], $class
}

sub compute
{
    my($ackermann, $m, $n) = @_;

    defined $ackermann->[$m][$n] or
    	$ackermann->[$m][$n] = A($m, $n);

    $ackermann->[$m][$n]
}

We compute the value in C with

int A(int m, int n)
{
    if (m==0) return n+1;
    if (n==0) return A(m-1, 1);
    return A(m-1, A(m, n-1));
}

int
A(m, n)
        int m
        int n

Now we can compute values like this

my $ackermann = new Math::Ackermann;

print $ackermann->compute(1, 1);  # computes value
print $ackermann->compute(2, 2);  # computes value
print $ackermann->compute(1, 1),  # returns cached value

In this design, data is represented in Perl, and computation is done in C.

The XS describes the calling sequence for A(), and xsubpp generates the necessary calls to the Perl C API.

1. Introduction
2. Concepts
3. Example 1: Geometry
4. The typemap
5. Example 2: Math::Ackermann
6. Example 3: Set::Bit