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

SYNOPSIS

59        use CPS qw( kloop );
60
61        kloop( sub {
62           my ( $knext, $klast ) = @_;
63
64           print "Enter a number, or q to quit: ";
65
66           read_stdin_line( sub {
67              my ( $first ) = @_;
68              chomp $first;
69
70              return $klast->() if $first eq "q";
71
72              print "Enter a second number: ";
73
74              read_stdin_line( sub {
75                 my ( $second ) = @_;
76
77                 print "The sum is " . ( $first + $second ) . "\n";
78
79                 $knext->();
80              } );
81           } );
82        },
83        sub { exit }
84        );
85

FUNCTIONS

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

GOVERNORS

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

CPS UTILITIES

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

EXAMPLES

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

SEE ALSO

352       ·   Future - represent an operation awaiting completion
353
354       ·   Future::AsyncAwait - deferred subroutine syntax for futures
355
356       ·   CPS::Functional - functional utilities in Continuation-Passing
357           Style
358
359       ·   <http://en.wikipedia.org/wiki/Continuation-passing_style> on
360           wikipedia
361

ACKNOWLEDGEMENTS

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

AUTHOR

367       Paul Evans <leonerd@leonerd.org.uk>
368
369
370
371perl v5.30.1                      2020-01-29                            CPS(3)
Impressum