# 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));
}
```
This XS code to connects the C to the Perl:
```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

### Notes on these adapted articles

These pages are an adaptation of articles written in 2000 by Steven W. McDougall. My goal in modifying these articles is to simplify and update them. I hope you find these adapted versions of the articles useful. You can find the original articles at the link at the bottom of this page. The major changes in this update are:

• h2xs is not used;
• XSLoader is used in place of DynaLoader;
• It is assumed that the reader understands the basic concepts of C and Perl programming.

This adaptation is a work in progress and many of the links on these pages may not work.