1CPS(3)                User Contributed Perl Documentation               CPS(3)
2
3
4

NAME

6       "CPS" - manage flow of control in Continuation-Passing Style
7

OVERVIEW

9       The functions in this module implement or assist the writing of
10       programs, or parts of them, in Continuation Passing Style (CPS).
11       Briefly, CPS is a style of writing code where the normal call/return
12       mechanism is replaced by explicit "continuations", values passed in to
13       functions which they should invoke, to implement return behaviour. For
14       more detail on CPS, see the SEE ALSO section.
15
16       What this module implements is not in fact true CPS, as Perl does not
17       natively support the idea of a real continuation (such as is created by
18       a co-routine).  Furthermore, for CPS to be efficient in languages that
19       natively support it, their runtimes typically implement a lot of
20       optimisation of CPS code, which the Perl interpreter would be unable to
21       perform. Instead, CODE references are passed around to stand in their
22       place. While not particularly useful for most regular cases, this
23       becomes very useful whenever some form of asynchronous or event-based
24       programming is being used. Continuations passed in to the body function
25       of a control structure can be stored in the event handlers of the
26       asynchronous or event-driven framework, so that when they are invoked
27       later, the code continues, eventually arriving at its final answer at
28       some point in the future.
29
30       In order for these examples to make sense, a fictional and simple
31       asynchronisation framework has been invented. The exact details of
32       operation should not be important, as it simply stands to illustrate
33       the point. I hope its general intention should be obvious. :)
34
35        read_stdin_line( \&on_line ); # wait on a line from STDIN, then pass it
36                                      # to the handler function
37
38       This module itself provides functions that manage the flow of control
39       through a continuation passing program. They do not directly facilitate
40       the flow of data through a program. That can be managed by lexical
41       variables captured by the closures passed around. See the EXAMPLES
42       section.
43
44       For CPS versions of data-flow functionals, such as "map" and "grep",
45       see also CPS::Functional.
46

SYNOPSIS

48        use CPS qw( kloop );
49
50        kloop( sub {
51           my ( $knext, $klast ) = @_;
52
53           print "Enter a number, or q to quit: ";
54
55           read_stdin_line( sub {
56              my ( $first ) = @_;
57              chomp $first;
58
59              return $klast->() if $first eq "q";
60
61              print "Enter a second number: ";
62
63              read_stdin_line( sub {
64                 my ( $second ) = @_;
65
66                 print "The sum is " . ( $first + $second ) . "\n";
67
68                 $knext->();
69              } );
70           } );
71        },
72        sub { exit }
73        );
74

FUNCTIONS

76       In all of the following functions, the "\&body" function can provide
77       results by invoking its continuation / one of its continuations, either
78       synchronously or asynchronously at some point later (via some event
79       handling or other mechanism); the next invocation of "\&body" will not
80       take place until the previous one exits if it is done synchronously.
81
82       They all take the prefix "k" before the name of the regular perl
83       keyword or function they aim to replace. It is common in CPS code in
84       other languages, such as Scheme or Haskell, to store a continuation in
85       a variable called "k".  This convention is followed here.
86
87   kloop( \&body, $k )
88       CPS version of perl's "while(true)" loop. Repeatedly calls the "body"
89       code until it indicates the end of the loop, then invoke $k.
90
91        $body->( $knext, $klast )
92           $knext->()
93           $klast->()
94
95        $k->()
96
97       If $knext is invoked, the body will be called again. If $klast is
98       invoked, the continuation $k is invoked.
99
100   kwhile( \&body, $k )
101       Compatibility synonym for "kloop"; it was renamed after version 0.10.
102       New code should use "kloop" instead.
103
104   kforeach( \@items, \&body, $k )
105       CPS version of perl's "foreach" loop. Calls the "body" code once for
106       each element in @items, until either the items are exhausted or the
107       "body" invokes its $klast continuation, then invoke $k.
108
109        $body->( $item, $knext, $klast )
110           $knext->()
111           $klast->()
112
113        $k->()
114
115   kdescendd( $root, \&body, $k )
116       CPS version of recursive descent on a tree-like structure, defined by a
117       function, "body", which when given a node in the tree, yields a list of
118       child nodes.
119
120        $body->( $node, $kmore )
121           $kmore->( @child_nodes )
122
123        $k->()
124
125       The first value to be passed into "body" is $root.
126
127       At each iteration, a node is given to the "body" function, and it is
128       expected to pass a list of child nodes into its $kmore continuation.
129       These will then be iterated over, in the order given. The tree-like
130       structure is visited depth-first, descending fully into one subtree of
131       a node before moving on to the next.
132
133       This function does not provide a way for the body to accumulate a
134       resultant data structure to pass into its own continuation. The body is
135       executed simply for its side-effects and its continuation is invoked
136       with no arguments. A variable of some sort should be shared between the
137       body and the continuation if this is required.
138
139   kdescendb( $root, \&body, $k )
140       A breadth-first variation of "kdescendd". This function visits each
141       child node of the parent, before iterating over all of these nodes's
142       children, recursively until the bottom of the tree.
143
144   kpar( @bodies, $k )
145       This CPS function takes a list of function bodies and calls them all
146       immediately. Each is given its own continuation. Once every body has
147       invoked its continuation, the main continuation $k is invoked.
148
149        $body->( $kdone )
150          $kdone->()
151
152        $k->()
153
154       This allows running multiple operations in parallel, and waiting for
155       them all to complete before continuing. It provides in a CPS form
156       functionality similar to that provided in a more object-oriented
157       fashion by modules such as Async::MergePoint or Event::Join.
158
159   kpareach( \@items, \&body, $k )
160       This CPS function takes a list of items and a function body, and calls
161       the body immediately once for each item in the list. Each invocation is
162       given its own continuation. Once every body has invoked its
163       continuation, the main continuation $k is invoked.
164
165        $body->( $item, $kdone )
166          $kdone->()
167
168        $k->()
169
170       This is similar to "kforeach", except that the body is started
171       concurrently for all items in the list list, rather than each item
172       waiting for the previous to finish.
173
174   kseq( @bodies, $k )
175       This CPS function takes a list of function bodies and calls them each,
176       one at a time in sequence. Each is given a continuation to invoke,
177       which will cause the next body to be invoked. When the last body has
178       invoked its continuation, the main continuation $k is invoked.
179
180        $body->( $kdone )
181          $kdone->()
182
183        $k->()
184
185       A benefit of this is that it allows a long operation that uses many
186       continuation "pauses", to be written without code indenting further and
187       further to the right. Another is that it allows easy skipping of
188       conditional parts of a computation, which would otherwise be tricky to
189       write in a CPS form. See the EXAMPLES section.
190

GOVERNORS

192       All of the above functions are implemented using a loop which
193       repeatedly calls the body function until some terminating condition. By
194       controlling the way this loop re-invokes itself, a program can control
195       the behaviour of the functions.
196
197       For every one of the above functions, there also exists a variant which
198       takes a CPS::Governor object as its first argument. These functions use
199       the governor object to control their iteration.
200
201        kloop( \&body, $k )
202        gkloop( $gov, \&body, $k )
203
204        kforeach( \@items, \&body, $k )
205        gkforeach( $gov, \@items, \&body, $k )
206
207        etc...
208
209       In this way, other governor objects can be constructed which have
210       different running properties; such as interleaving iterations of their
211       loop with other IO activity in an event-driven framework, or giving
212       rate-limitation control on the speed of iteration of the loop.
213

CPS UTILITIES

215       These function names do not begin with "k" because they are not
216       themselves CPS primatives, but may be useful in CPS-oriented code.
217
218   $kfunc = liftk { BLOCK }
219   $kfunc = liftk( \&func )
220       Returns a new CODE reference to a CPS-wrapped version of the code block
221       or passed CODE reference. When $kfunc is invoked, the function &func is
222       called in list context, being passed all the arguments given to $kfunc
223       apart from the last, expected to be its continuation. When &func
224       returns, the result is passed into the continuation.
225
226        $kfunc->( @func_args, $k )
227           $k->( @func_ret )
228
229       The following are equivalent
230
231        print func( 1, 2, 3 );
232
233        my $kfunc = liftk( \&func );
234        $kfunc->( 1, 2, 3, sub { print @_ } );
235
236       Note that the returned wrapper function only has one continuation slot
237       in its arguments. It therefore cannot be used as the body for
238       "kloop()", "kforeach()" or "kgenerate()", because these pass two
239       continuations. There does not exist a "natural" way to lift a normal
240       call/return function into a CPS function which requires more than one
241       continuation, because there is no way to distinguish the different
242       named returns.
243
244   $func = dropk { BLOCK } $kfunc
245   $func = dropk $waitfunc, $kfunc
246       Returns a new CODE reference to a plain call/return version of the
247       passed CPS-style CODE reference. When the returned ("dropped") function
248       is called, it invokes the passed CPS function, then waits for it to
249       invoke its continuation. When it does, the list that was passed to the
250       continuation is returned by the dropped function. If called in scalar
251       context, only the first value in the list is returned.
252
253        $kfunc->( @func_args, $k )
254           $k->( @func_ret )
255
256        $waitfunc->()
257
258        @func_ret = $func->( @func_args )
259
260       Given the following trivial CPS function:
261
262        $kadd = sub { $_[2]->( $_[0] + $_[1] ) };
263
264       The following are equivalent
265
266        $kadd->( 10, 20, sub { print "The total is $_[0]\n" } );
267
268        $add = dropk { } $kadd;
269        print "The total is ".$add->( 10, 20 )."\n";
270
271       In the general case the CPS function hasn't yet invoked its
272       continuation by the time it returns (such as would be the case when
273       using any sort of asynchronisation or event-driven framework). For
274       "dropk" to actually work in this situation, it requires a way to run
275       the event framework, to cause it to process events until the
276       continuation has been invoked.
277
278       This is provided by the block, or the first passed CODE reference. When
279       the returned function is invoked, it repeatedly calls the block or wait
280       function, until the CPS function has invoked its continuation.
281

EXAMPLES

283   Returning Data From Functions
284       No facilities are provided directly to return data from CPS body
285       functions in "kloop", "kpar" and "kseq". Instead, normal lexical
286       variable capture may be used here.
287
288        my $bat;
289        my $ball;
290
291        kpar(
292           sub {
293              my ( $k ) = @_;
294              get_bat( on_bat => sub { $bat = shift; goto &$k } );
295           },
296           sub {
297              my ( $k ) = @_;
298              serve_ball( on_ball => sub { $ball = shift; goto &$k } );
299           },
300
301           sub {
302              $bat->hit( $ball );
303           },
304        );
305
306       The body function can set the value of a variable that it and its final
307       continuation both capture.
308
309   Using "kseq" For Conditionals
310       Consider the call/return style of code
311
312        A();
313        if( $maybe ) {
314           B();
315        }
316        C();
317
318       We cannot easily write this in CPS form without naming C twice
319
320        kA( sub {
321           $maybe ?
322              kB( sub { kC() } ) :
323              kC();
324        } );
325
326       While not so problematic here, it could get awkward if C were in fact a
327       large code block, or if more than a single conditional were employed in
328       the logic; a likely scenario. A further issue is that the logical
329       structure becomes much harder to read.
330
331       Using "kseq" allows us to name the continuation so each arm of "kmaybe"
332       can invoke it indirectly.
333
334        kseq(
335           \&kA,
336           sub { my $k = shift; $maybe ? kB( $k ) : goto &$k; },
337           \&kC
338        );
339

SEE ALSO

341       ·   CPS::Functional - functional utilities in Continuation-Passing
342           Style
343
344       ·   <http://en.wikipedia.org/wiki/Continuation-passing_style> on
345           wikipedia
346
347       ·   Coro - co-routines in Perl
348

ACKNOWLEDGEMENTS

350       Matt S. Trout (mst) <mst@shadowcat.co.uk> - for the inspiration of
351       "kpareach" and with apologies to for naming of the said. ;)
352

AUTHOR

354       Paul Evans <leonerd@leonerd.org.uk>
355
356
357
358perl v5.28.1                      2019-02-02                            CPS(3)
Impressum