; operator: Monads in PerlSo-called ``functional'' programming languages like Haskell and ML offer several advantage of conventional languages like Perl and C. They're easier to reason about and easier to automatically optimize. But they've historically had trouble with several very important areas.
Let's consider this perl function:
# Perl
sub aloop {
my $sum = 0;
for my $i (1 .. 1000000) {
my $x = sqrt(2);
$sum += $x * $i;
}
return $sum;
}
An optimizing compiler might notice that the my $x = sqrt(2) is
being done one million times and is redundant. A smart compiler could
hoist the constant expression out of the loop, getting this:
# Optimized perl
sub aloop {
my $sum = 0;
* my $x = sqrt(2);
for my $i (1 .. 1000000) {
$sum += $x * $i;
}
return $sum;
}
But to do this, it needs to have special knowledge about the behavior of the sqrt function. Specifically, it needs to know that sqrt has no side effects. The corresponding optimization wouldn't work correctly if the sqrt were replaced by a print, because the ``optimized'' code only prints one of the million desired outputs.
Similarly, a user-defined function may or may not be hoistable. If instead of sqrt we have myfunc, can we hoist it? Maybe, maybe not. What if myfunc looks like this?
sub myfunc {
return unless ++$GLOBAL_VAR == 579183;
die "Too many calls to myfunc()!";
}
Hoisting the call out of the loop changes the behavior of the program; it no longer aborts with an error message.
If you know that none of your functions have side effects, all sorts of program transformations become simple. Loop hoisting is only one example. Here's another:
sub i_like_carrots {
my $arg = shift;
my $a = do_this();
my $b = do_that();
if ($arg) { return $a + $b }
else { return $b }
}
The do_this() function is called, but sometimes its result is never
used. A clever compiler might postpone the call to do_this until
after testing $arg, calling do_this() only if necessary.
This works fine, as long as do_this() has no side effects. If
do_this() has side effects, such as printing a message, throwing an
exception, writing a file, or setting a global variable, havoc will
ensue. One final example:
sub do_two_things {
my $a = first_thing();
my $b = second_thing();
return $a + $b;
}
If your program is running on a multiprocessor computer, a clever compiler can arrange to have first_thing() and second_thing() run in parallel, on seprate processors---but only if they have no side effects. If they have side effects, parallel execution could cause all sorts of havoc. What if the two functions printed messages to the terminal? Parallel execution might cause the messages to come out in the wrong order. What if first_thing() created a file that second_thing() tried to read back? If second_thing() is executing at the same time as first_thing(), it might try to read the file before first_thing() was finished writing it.
Early attempts at functional languages tried to forbid all side effects. This enables many compiler optimizations, reordering code, lazy evaluation, and all sorts of other techniques that will make the programs run better.
Unfortunately, forbidding side effects removes a lot of valuable functionality from a programming language. Valuable functionality that you really can't get along without, such as input and output. We might like to forbid global variables, but we might be less willing to forbid their second cousins, references. And a lot of people would be sad if we forbade exceptions.
Pure functional programs with no side effects live in a sort of timeless void in which everything happens at once, or at least in no particular order. Unfortunately, programmers live in the real universe, in which time is always ticking away and it makes a big difference whether you finish the project before the deadline or vice versa.
What we'd like is some way to tell the compiler that some functions do have side effects, and what sort of side effects they might have, so that it will know when it is safe to reorder, to parallelize, to postpone, and to omit. Functional programming research has invented a lot of ways to do this, but most of them were ad-hoc. In recent years, though, a really brilliant technique has been invented that solves a lot of the problems in a very general way. The technique involves a data structure called a monad.
A monad is a data structure that encapsulates a function's return value, possibly bundled up with a representation of some sort of side effect that the function could have. You use different kinds of monads depending on what sort of side effect you're interested in talking about.
Think of monads as an abstract base class. The monad objects contain an ordinary data value, and possibly some other data as well; the extra data represents some kind of side effect. A monad class always supports at least two methods. The first one is a constructor, which we'll call result. It takes a value and manufactures a monad object that represents that value with no associated side effects.
The other required monad method represents sequencing of two
operations. We will call this andThen. Say you have two monad
values, say A and B. Each represents some value, possibly plus
some side effect. A-\andThen(B)> returns a new monad, whose value
is the same as B's, but hose side effect is the combination of the
effects of A and B. (A's value is thrown away.)
All that may sound a little abstruse, so let's see an example. Let's supose that our side effect is printing text. A function that wants to print will instead return a monad containing its return value, bundled with a representation of what it wanted to print---that is, a string.
The result operation takes a value and builds a monad which contains that value and does not want to have printed anything. We might implement it like this:
sub result {
my ($class, $value) = @_;
bless { VAL => $value, OUTPUT => "" } => $class;
}
The andThen operation takes two monads and combines them into one.
It throws away the value of the first monad, but sequences the two
side effects:
sub andThen {
my ($a, $b) = @_;
bless { VAL => $b->{VAL},
OUTPUT => $a->{OUTPUT} . $b->{OUTPUT} }
=> ref $a;
}
The output produced by combining $a and $b, in that order, is
just the concatenation of the outputs produced by $a and $b
individually.
With this implementation, we would probably want to add a couple of accessor methods:
sub value_of {
my $self = shift;
return $self->{VAL};
}
sub output_of {
my $self = shift;
return $self->{OUTPUT};
}
We also need a method that actually tries to print something. This manufactures a monad whose value is unimportant, but whose bundled side effect indicates that a given string was output:
# Monad->do_print("some string");
sub do_print {
my ($class, $string) = @_;
my $string = shift;
return { VAL => undef, OUTPUT => $string } => $class;
}
Now how do we use this? Let's write a function that evaluates simple expressions. An expression will be an array. It will either have the form:
["Con", 12.3]
representing the constant 12.3, or else it will have the form:
["Div", $e1, $e2]
which represents the expression $e1/$e2. We could represent
expressions with more operators than just division, but let's keep the
example simple. A typical expression looks like this:
["Div", ["Con", 3],
["Div", ["Con", 4], ["Con", 5]]]
This represents the expression 3/(4/5).
Here's an evaluator (``Version 1'') for these expressions:
sub Eval {
my $expr = shift;
my ($op, $e1, $e2) = @$expr;
if ($op eq "Con") {
return $e1;
} else {
my $v1 = Eval($e1);
my $v2 = Eval($e2);
return $v1/$v2;
}
}
This function has no side effects. A smart compiler would be free to
evaluate $e1 and $e2 in parallel, or to maintain a cache of
previously-seen expressions and the results of evaluating them, and
skip the execution of Eval entirely when the expression was already
in the cache.
Now we'll add side effects. Let's say we would like the evaluator to print out the expression in a pretty format. That's not hard:
sub Eval {
my $expr = shift;
my ($op, $e1, $e2) = @$expr;
if ($op eq "Con") {
* print $e1;
return $e1;
} else {
* print "[ ";
my $v1 = Eval($e1);
* print " divided by ";
my $v2 = Eval($e2);
* print " ]";
return $v1/$v2;
}
}
(``Version 2'') For the example expression, this will print
[ 3 divided by [ 4 divided by 5 ] ]
The function now has side effects---it is not correct to
parallelize the two calls to Eval, or to maintain a cache of the
return values of Eval.
But we can rewrite the function to use the printing monad of the previous section:
sub Eval {
my $expr = shift;
my ($op, $e1, $e2) = @$expr;
if ($op eq "Con") {
Monad->do_print($e1)
->andThen(Monad->result($e1));
} else {
my ($v1, $v2);
Monad->do_print("[ ")
->andThen($v1 = Eval($e1))
->andThen(Monad->do_print(" divided by "))
->andThen($v2 = Eval($e2))
->andThen(Monad->do_print(" ]"))
->andThen(Monad->result($v1->value_of / $v2->value_of));
}
}
This is ``Version 3''.
(This looks rather awful. Functional languages where monadic programming is common use syntactic sugar to make it look better. But in this article, it may be a good thing that we have to expose all the machinery this way, because it keeps the whole thing from being too magical.)
Let's look at this slowly. If the expression is a constant, then
$e1 is a plain number. Eval calls Monad-\do_print> to print
this value, and then Monad-\result($e1)> returns the result $e1
without printing anything else. The interstitial -\andThen> call
composes the two monads into a single one that reflects the aggregate
side effects of both, and that returns the value $e1. (The return
value from the first monad is discarded, remember.)
The else clause is similar. The function calls do_print when it
wants to print, calls andThen when it wants to perform two
operations in sequence, and calls Eval recursively to process the
two subexpressions. The return values from the recursive calls are
captured in private variables $v1 and $v2. The function's final
return value is a monad whose value is the quotient of the two
subexpression values and whose bundled side effect is the result of
all the printing performed by the three calls to do_print and the
two recursive calls to Eval, all in the right order.
Let's try an example:
my $expr = ["Div", ["Con", 3],
["Div", ["Con", 4], ["Con", 5]]];
my $res = Eval($expr);
$res is a monad. It contains the normal returned value of Eval,
plus the bundled information about its side effects. We can query either:
print "Returned value: ", $res->value_of, "\n";
print "Output: ", $res->output_of, "\n";
For the example, we get:
Returned value: 3.75
Output: [ 3 divided by [ 4 divided by 5 ] ]
Well, big deal. That's just what we got from the simple version with no monads.
But the monads add power and flexibility. They are an abstraction of side effects and sequencing. With Perl's built-in print function, we only get to print things the way Perl wants them to. By eliminting all the implicit side effects and implicit sequencing, we've opened up the possibility of redefining these fundamental notions.
For example, suppose we would like to run the program backwards in time?
The function return values don't change. The only thing that changes
is the order of the side effects, which is controlled by andThen:
sub andThen {
my ($a, $b) = @_;
bless { VAL => $b->{VAL},
OUTPUT => $a->{OUTPUT} . $b->{OUTPUT} }
=> ref $a;
}
This says that if $a happens before $b, the side effect is to
print whatever $a printed, followed by whatever $b printed. To
run the program backwards, just change the definition of andThen to
reverse the order of the side effects:
sub andThen {
my ($a, $b) = @_;
bless { VAL => $b->{VAL},
* OUTPUT => $b->{OUTPUT} . $a->{OUTPUT} }
=> ref $a;
}
The result is now
Returned value: 3.75
Output: ] ]5 divided by 4[ divided by 3[
The same 7 strings were printed, but in reverse order.
If we want to reverse the entire output, we wil need to change the
definition of do_print as well:
sub do_print {
my ($class, $string) = @_;
bless { VAL => undef,
* OUTPUT => scalar reverse $string }
=> $class;
}
Now the output is:
Returned value: 3.75
Output: ] ] 5 yb dedivid 4 [ yb dedivid 3 [
Version 2 was simpler to write, but less flexible. If we wanted to alter version 2 so that it generated its output in backwards order, we'd probably have to build machinery into it very similar to the machinery we built for the monads for version 3.
Version 3 has no side effects itself. The compiler is free to reorder anything it wants, subject only to the law that values must be computed before they are used. In this function, that does not leave it a lot of scope for reordering, but this function has a lot of sequential dependencies.
Sometimes division doesn't work. When we try to divide by zero, Perl throws a fatal exception. This is a side effect. If you have
$a = func_1();
$b = func_2();
you cannot reorder the two calls if they might throw exceptions. How might we implement an exception if Perl didn't have them built in? Monads can do this also.
Our monads now have a return value, possibly bundled with a representation of an exception that was thrown during its calculation. A monad representing a successful calculation with an ordinary return value will look like this:
[ "RESULT", $value ]
A monad representing a computation that failed because it threw an exception will look like this:
[ "EXCEPTION", $message ]
We'll have a utility function that tests to see if a particular monad value is an exception:
sub is_exception {
my $self = shift;
$self->[0] eq "EXCEPTION";
}
And the usual accessors:
# Extract message from an exception
sub message {
my $self = shift;
$self->[1];
}
# Extract the returned value from a normal result
sub value_of {
my $self = shift;
return $self->[1];
}
As usual, we will have a result operation that manufactures a monad
that contains a return value and no side effect--that is, no
exception:
sub result {
my ($class, $val) = @_;
bless [ "RESULT", $val ] => $class;
}
And we must have the all-important andThen operation:
sub andThen {
my ($a, $b) = @_;
if ($a->is_exception) { return $a }
else { return $b }
}
To sequence two monads, $a and $b, we first check to see if the
calculation of $a threw an exception. If so, we ignore $b and
propagate the exception. Otherwise, we discard $a (the return
value of the first monad is always discarded) and yield the result of
the second computation, whether it succeeds or fails.
The exceptions will not be useful unless we give our programs some way to raise them:
sub raise {
my ($class, $message) = @_;
bless [ "EXCEPTION", $message ] => $class;
}
Here's version 4 of our evaluator:
sub Eval {
my $expr = shift;
my ($op, $e1, $e2) = @$expr;
if ($op eq "Con") {
Monad->result($e1);
} else {
my ($v1, $v2);
($v1 = Eval($e1))
->andThen($v2 = Eval($e2))
->andThen(do {
if ($v2->value_of == 0) {
Monad->raise("Division by zero");
} else {
Monad->result($v1->value_of / $v2->value_of);
}
});
}
}
If the expression is a constant, the function just returns the value as its result, without throwing any exceptions. But if the expression contains a division, it first calls itself recursively on the first subexpresion, and then on the second subexpression, and then if the second subexpression is zero, it raises an exception, and if not it returns the result of the division.
To demonstrate this, we will use this wrapper code:
my $res = Eval($expr);
if ($res->is_exception) {
warn "Calculation failed: ", $res->message, "\n";
} else {
print "Result: ", $res->value_of, "\n";
}
For our original expression example, there are no divisions by zero:
my $expr = ["Div", ["Con", 3],
["Div", ["Con", 4], ["Con", 5]]];
The result is:
Result: 3.75
But if we change the 4 to a 0, we get:
Calculation failed: Division by zero