Wednesday, May 30, 2007

Interlude: Functional Programming with a side of Perl 6

This article is a quick tangent away from the Rounds series; an attempt to investigate Functional Programming with Perl 6. There're a lot of new things to look at, so this post will act more as an investigation rather than a lesson.

Note this article is an interlude; things here may (or probably not) have been covered in the previous articles I've posted, up to this point. So if you don't necessarily understand what's going on here, it's fine. You may just have to wait a while before my explanatory post comes out (but then again, you could help yourself.) Anything I've posted here will most likely (hopefully) be explained at some later point, when it need be (for example, we may do things with subs I didn't cover; but remember, I didn't promise to cover all the details.)

Let's begin.

(Also note this now: I'm coming from a Haskell background, so code examples may be posted in Haskell to explain a point.)

Higher Order Functions
Higher order functions are functions that take other functions as arguments, basically. An example of this is the map function. map would have the following type (Haskell):
Prelude> :t map
map :: (a -> b) -> [a] -> [b]
Example of usage could be like this:
Prelude> map even [1..10]

As you can see, this would return a list of Bool's saying which are even and which are not; if you actually wanted the values, you'd have to use the filter function (filter is similar to map, except it returns a new list based on the old one, filtered by a predicate,) ex:
Prelude> filter even [1..10]

So, as an exercise, let's implement these functions.

In Perl 6, subs can be passed Closure parameters. This means you can treat said parameters as lexically scoped subs. These closure parameters are prefixed with the & sigil. For example:
[altair@stormwind diveintoperl6]$ cat > higher-order.p6
#!/usr/bin/env pugs
use v6;

sub hiordr(&b,$v) {
b $v;

hiordr({ say $_; },"asdf");
[altair@stormwind diveintoperl6]$ pugs higher-order.p6
[altair@stormwind diveintoperl6]$
It's worth noting that, you could rewrite the above call to hiordr as simply hiorder(&say,"asdf");
Obviously though, if you need to do something other than just use one function (such as use a user-defined predicate like we'll see below in filter2's example) or you don't want to define a sub to use, an anonymous block will probably suffice.

So our implementation should, therefore, be reasonably sane given what we know now:

[altair@stormwind diveintoperl6]$ cat map-filter.p6
#!/usr/bin/env pugs
use v6;

sub map2(&b,@l) {
my @r = <>;
for @l -> $v {
@r.push(b $v);
return @r;

sub filter2(&p,@l) {
my @r = <>;
for @l -> $v {
my $x = p $v;
@r.push($v) if $x;
return @r;

say map2({ .uc; },<a b c d>).join(' ');
say filter2({ $_ % 2 == 0; },1..10).join(' ');
[altair@stormwind diveintoperl6]$ pugs map-filter.p6
2 4 6 8 10
[altair@stormwind diveintoperl6]$

As you can see, not too difficult to implement at all. You now have the power of Higher-order functions: give them a shot every once in a while.

Lists and pattern matching
In Perl 6, lists are just like they are in a language like Haskell (or, well, any language pretty much.) They're even lazy (although don't try my @a = 1...; just yet; the infinite generators in Pugs are not yet implemented.)

In Perl 6, thanks to some of the new semantics, it's a bit easier to express some more functional-style expressions. Thanks to multi subroutines, it's also possible to pattern match your functions so you don't get errs when calling a function with a list that may break down over the course of the computation (in haskell: you get an exhaustive pattern match.)

For example, here is a basic definition of reverse in Haskell, followed by the same definition in Perl 6:

rev [] = []
rev (x:xs) = rev xs ++ [x]

perl 6:
multi sub rev () { () }
multi sub rev($x,*@xs) { (rev(|@xs),$x) }

Now, given, the haskell function may be a bit more flexible, for example, you could not use the perl 6 version and do "rev('asdf');' while you could in the haskell version; this is due to the fact that in haskell, data String = [Char], while in Perl 6, a String is it's own type. This could be accomplished however, doing:

my @a = "asdf".split('');

This is besides the point, however.

Somewhat tangential: Monads
A lot of people wonder exactly what a monad is (you may not grok this if you're not from a Haskell background.) The word is intriguing and the idea powerful, yet there seems to be a loss of words to describe exactly what they are or do.
Monad's are basically a computation environment. To add onto that, they're a computation environment in which you get to make up the rules of evaluation order. This abstraction is what makes Monad's so delicious; it is easy to abstract away things like boilerplate between your expressions. For more info, you may wish to check out this topic.

Another plus is that a monad is really just a library. This makes them language-agnostic (although Haskell is obviously the leading-man in the area of Monad usage.) There are monads for all sorts of languages (which is why this is 'somewhat tangential': it's not directly related to functional programming per se, but I'm deciding to cover it anyway just due to the principle and idea. Feel free to skip if you like.)

Here we'll just be trying to reduce a Haskell Monad to a Perl 6 Monad. We will use a fairly contrived Monad for the purpose of the explanation. This monad is known as 'Click.' Click is a pretty simple Monad -- actually, it's pretty much identical to Maybe; both in type and usage (the main difference is we aren't handling fail.) Click simply returns either a Silence or a Clicked a where a is essentially any arbitrary type. Using this Monad you can basically have expressions which are 'Silent' or they 'Click.' Let's look at the definition of this Monad:

data Click a = Clicked a | Silence
deriving Show

instance Monad Click where
return = Clicked
Silence >>= _ = Silence
Clicked a >>= f = f a
Easy enough. Here's a function and a few tests to show how exactly this monad works:

noise :: (Num a) => a -> Click a
noise 0 = Silence
noise x = Clicked x

t1 = do
a <- noise 10
b <- noise 5
return (a + b)

t2 = do
a <- noise 10
b <- noise 0
return (a + b)

t3 = do
a <- noise 10
b <- noise 0
c <- noise 5
return (a + c)
Running these:
[altair@stormwind monads]$ ghci

Prelude> :l Click.hs
[1 of 1] Compiling Click ( Click.hs, interpreted )
Ok, modules loaded: Click.
*Click> t1
Clicked 15
*Click> t2
*Click> t3

Well, it works pretty easily! Thanks to the do notation, our expressions are de-sugared and fed to each other via the bind operator (>>=) automatically; this is why even when you get a Silence in an expression like b <- noise 0 which seems just like a pattern match, your whole expression is Silent: every 'sequential action' is de-sugared down to >>= in essence. That would be why t2 and t3 would be Silent themselves, as given by our Monad instance.

Let's see if we can define a reasonable goal as to what our end result should look like in Perl. Since this is essentially just a 'conversion,' we may need to translate a few notations. This is (hopefully) what our end result with our Monad code in Perl 6 should look like:

my $t1 = monaddo ({ my $a = noise 10; },
{ my $b = noise 5; },
{ return $a + $b; });

I realize, this doesn't look too pretty; but I guess that's just a bi-product. However, looking at it reveals that the do-notation is reletively sound; we're just evaluating a list of expression's and doing a little more under the scenes. Here's a first version of our monaddo notation:
pugs> sub monaddo(&b,*@a) {
....> my $x = b();
....> $x = $_($x) for @a;
....> }

And an example of the usage:
pugs> monaddo({ 1; },{ .say; });

Woo! it works fine. Actually, we can effectively 'axe' the semicolons, since all our expressions in our monadic notation are treated as just blocks.
Quickly into our celebration though, we find things like this do not work:
pugs> monaddo({ my $a = 1 },{my $b = 2 },{ .say});

This is due to the fact that monaddo expects every block in the list of blocks to accept one parameter (excluding the first.) Also, if a variable is declared in one block, it is lexically seperated from the previous block, so sharing data can only be done via the 'inbetween pass.'

Regardless if you may hate me, right now, I think this is enough for this post, and at this point I believe this 'monads-in-perl6' topic is worth it's own post entirely. :)
So we'll stop here (boo hoo,) as I am a very, very fickle person (actually, I need more time to collect my thoughts on this topic; I don't wish to make post this 'all about monads' either, so you'll have to excuse me there.) We'll continue in this venture a little later on; maybe after my initial Rounds series is done, or maybe in 3 years.

(The premature) Conclusion
This was just an investigation post, mainly. With Perl 6 a lot of things are going to be much more expressive, much more easily. The influence of functional programming on my brain seems to have that effect, I've found; might as well apply it to what I'm going to use.
That's what programming is about, isn't it?