you've alrady heard about CPS (continuation passing style). CPS is not
reserved to languages of the Lisp family. It works also for Perl,
including tail call elimination, which is nice for CPS, because
otherwise the stack may overflow. For example a complex tree can be
traversed and processed, and every moment you look at the stack, only
one of your self written procedures is there. That example would be
too confusing as a first example for CPS, so let me show a really
simple, maybe silly example: A small program reads lines from STDIN
until EOF or a line consisting of the string ``end'' is recognized.
The program converts the lines to upper case and writes it on STDOUT,
preceding it by the current line count.
Here it is:
- Code: Select all
sub convert_line {
my ($inpline, $k) = @_;
my $outpline = uc $inpline;
goto $k if @_ = ($outpline);
}
sub next_line {
my ($n, $k) = @_;
if (my $line = <>) {
goto &convert_line if @_ =
($line,
sub {
my ($res) = @_;
print "$n: $res";
if ($res =~ m{^END$}) {
goto $k if @_ = ("ended on user input");
}
goto &next_line if @_ = ($n + 1, $k);
});
} else {
goto $k if @_ = ("end of file reached");
}
}
next_line
(1,
sub {
my ($status) = @_;
print "status: $status\n";
});
Have a look at that source code line:
- Code: Select all
goto $k if @_ = ($outpline);
If you put a breakpoint there and look at the call stack every time
the breakpont is met, than the stack will contain exactly one entry,
even if the routing convert_line has been called several times. You
may replace that line by:
- Code: Select all
$k->($outpline);
Then tail call elimination is destroyed, and the stack will increase
line by line.
You can convert any procedure to CPS style. Let's assume there's a
procedure f perfoms some action A, then calls procedure g and
finally performes some action B:
- Code: Select all
sub f {
A;
g(x);
B;
}
Then the corresponding CPS style is somewhat like that:
- Code: Select all
sub f_cps {
A;
g_cps(x,
B_cps);
}
To achieve tail call elimination, the first idea is to write it like
that:
- Code: Select all
sub f_cps {
A;
@_=(x, B_cps);
goto &g_cps;
}
But now the B part (B_cps) has changed the source code position
relative to the g part (g_cps), that is from ``g above B'' to ``B
above g''. The latter isn't intuitive at all and contradicts to the
actual processing order. So I propose to regain the intuitive order by
introduce that strange if conditions, that you may have already
wondered about:
- Code: Select all
sub f_cps {
A;
goto &g_cps if @_=
(x,
B_cps);
}
Now the code parts are written in the original order again: first the
A part, than the g part and finally the B part.
I hope the Perl code is readable now, that I've explained that pattern
with ``if''.
Note that even when convert_line is currently the only function on the
stack, nevertheless the current state (e.g. the current line number)
is hold, whithout the loss of encapsulation (good information hiding,
that is: the function convert_line does not know about line counts at
all).
What do you thing about it?
