Church Numerals

As it is Sunday morning and I am avoiding the children’s musical service, let’s talk about Church Numerals in Perl 6. The basic notion is to represent the natural numbers in the lambda calculus in a simple, straightforward manner. Actually, the Wikipedia definition is probably better than any explaining I could do — if you don’t know them already, go and check that out.

So anyway, I decided to try to port the Haskell implementation to Perl 6. Here’s my first stab at the basic functions:

# church 0 = \f -> \x -> x

multi church(0) {
    -> &f { -> $x { $x } };
}

# church n = \f -> \x -> f (church (n-1) f x)

multi church($n) {
    -> &f { -> $x { &f(church($n - 1)(&f)($x)); } };
}

# unchurch n = n (\x -> x + 1) 0

sub unchurch(&c) {
    &c(-> $x { $x + 1 })(0);
}

> say unchurch(church(0));
0
> say unchurch(church(1));
1
> say unchurch(church(2));
2
> say unchurch(church(11));
11

This is a pretty straightforward translation of the Haskell version, and seems to work okay. Obviously the Perl 6 version is a tad more verbose -- Haskell is optimized for this sort of thing, whereas the Perl 6 syntax falls out of the new for loop syntax. (Maybe not quite the best way to say that, but if you did Perl 6 for loops with the Haskell lambda syntax, for loops would be nearly unreadable, IMO.)

Maybe I'm misunderstanding something, but this function, at least as it is in Perl 6, seems like something of a cheat. That is, when you say church(4), you don't get back the Perl 6 equivalent of f(f(f(f(x)))). Rather, you get f(church(3)(f)(x)).

At least, that's what I think happens. I have to admit I still find reasoning about lambda functions like this very confusing. And this equally straightforward conversion doesn't work:

# plus m n = \f -> \x -> m f (n f x)

multi plus(&m, &n) {
    -> &f { -> $x { &m(&f)(&n(&f)($x)) }}
}

> say unchurch(plus(church(2), church(3)));
4
> say unchurch(plus(church(2), church(13)));
14
> say unchurch(plus(church(2), church(1)));
2
> say unchurch(plus(church(2), church(0)));
2

If anyone has a notion what is wrong there, I'd love to hear it. Unfortunately, these functions aren't the easiest thing in the world to debug, either.

Or wait, maybe they are!

sub church-to-Str(&c) {
    &c(-> $x { "f($x)" })("x");
}

> say church-to-Str(church(3));
f(f(f(x)))
> say church-to-Str(church(1));
f(x)
> say church-to-Str(church(0));
x
> say church-to-Str(plus(church(2), church(1)));
f(f(x))

Okay, that doesn't offer me any particular insight at the moment, but maybe it will eventually...

About these ads

One Response to “Church Numerals”

  1. colomon Says:

    masak++ provides the following version which works: http://gist.github.com/378479

    Looks like I have fallen victim to a closure bug, then.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

%d bloggers like this: