There's a conceptual flaw in your sub. The splice would increase the number of elements in the array, but your alen variable isn't going up, so there will be a number of elements you never get to.

Let's start by translating your function into a pure Perl version that does what you want. I'm going to ignore package considerations for the present.

sub contentToString {
    my $list = shift; 
    my $result = '';

    if (ref($list) eq 'ARRAY' and @$list) {
        my $i;
        while ($i < $#$list) {
            my $list_entry = $list[$i];
            if (ref($list_entry)) {
                if (ref($list_entry) eq 'ARRAY') {
                    splice(@list, $i, 0, @$list_entry);
                }
                elsif (ref($list_entry) eq 'HASH') {
                    $output_string .= tagToString($list_entry);
                }
            }
            else {
                $result .= $list_entry;
            }
            $i++;
        }
    }
    return $result . "\n";
}
[download]

1) If nth element of list is an arrayref $r, replace $r in the original list with @$r.

Is there a possibility that the data structure will be more than two levels deep? If so, you'll need a recursive function. UPDATE: Oh wait, as I look at the Perl function again, I see that it will work, and you don't need recursion.

2) If nth element of list is an hashref $r, append result of perl function F($r) to the result scalar string.

You're going to need to take a look at the perlcall docs in order to figure out how to make callbacks from XS to Perl work. It's a little complicated because you need to put in some stack manipulation stuff that xsubpp normally does behind the scenes for your XSUB.