1CPS(3) User Contributed Perl Documentation CPS(3)
2
6 "CPS" - manage flow of control in Continuation-Passing Style
7
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 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 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 read_stdin_line( \&on_line ); # wait on a line from STDIN, then pass it
36 # to the handler function
37 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 For CPS versions of data-flow functionals, such as "map" and "grep",
45 see also CPS::Functional.
46
48 use CPS qw( kloop );
49 kloop( sub {
51 my ( $knext, $klast ) = @_;
52 print "Enter a number, or q to quit: ";
54 read_stdin_line( sub {
56 my ( $first ) = @_;
57 chomp $first;
58 return $klast->() if $first eq "q";
60 print "Enter a second number: ";
62 read_stdin_line( sub {
64 my ( $second ) = @_;
65 print "The sum is " . ( $first + $second ) . "\n";
67 $knext->();
69 } );
70 } );
71 },
72 sub { exit }
73 );
74
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 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 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 $body->( $knext, $klast )
92 $knext->()
93 $klast->()
94 $k->()
96 If $knext is invoked, the body will be called again. If $klast is
98 invoked, the continuation $k is invoked.
99 kwhile( \&body, $k )
101 Compatibility synonym for "kloop"; it was renamed after version 0.10.
102 New code should use "kloop" instead.
103 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 $body->( $item, $knext, $klast )
110 $knext->()
111 $klast->()
112 $k->()
114 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 $body->( $node, $kmore )
121 $kmore->( @child_nodes )
122 $k->()
124 The first value to be passed into "body" is $root.
126 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 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 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 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 $body->( $kdone )
150 $kdone->()
151 $k->()
153 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 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 $body->( $item, $kdone )
166 $kdone->()
167 $k->()
169 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 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 $body->( $kdone )
181 $kdone->()
182 $k->()
184 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
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 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 kloop( \&body, $k )
202 gkloop( $gov, \&body, $k )
203 kforeach( \@items, \&body, $k )
205 gkforeach( $gov, \@items, \&body, $k )
206 etc...
208 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
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 $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 $kfunc->( @func_args, $k )
227 $k->( @func_ret )
228 The following are equivalent
230 print func( 1, 2, 3 );
232 my $kfunc = liftk( \&func );
234 $kfunc->( 1, 2, 3, sub { print @_ } );
235 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 $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 $kfunc->( @func_args, $k )
254 $k->( @func_ret )
255 $waitfunc->()
257 @func_ret = $func->( @func_args )
259 Given the following trivial CPS function:
261 $kadd = sub { $_[2]->( $_[0] + $_[1] ) };
263 The following are equivalent
265 $kadd->( 10, 20, sub { print "The total is $_[0]\n" } );
267 $add = dropk { } $kadd;
269 print "The total is ".$add->( 10, 20 )."\n";
270 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 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
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 my $bat;
289 my $ball;
290 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 sub {
302 $bat->hit( $ball );
303 },
304 );
305 The body function can set the value of a variable that it and its final
307 continuation both capture.
308 Using "kseq" For Conditionals
310 Consider the call/return style of code
311 A();
313 if( $maybe ) {
314 B();
315 }
316 C();
317 We cannot easily write this in CPS form without naming C twice
319 kA( sub {
321 $maybe ?
322 kB( sub { kC() } ) :
323 kC();
324 } );
325 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 Using "kseq" allows us to name the continuation so each arm of "kmaybe"
332 can invoke it indirectly.
333 kseq(
335 \&kA,
336 sub { my $k = shift; $maybe ? kB( $k ) : goto &$k; },
337 \&kC
338 );
339
341 · CPS::Functional - functional utilities in Continuation-Passing
342 Style
343 · <http://en.wikipedia.org/wiki/Continuation-passing_style> on
345 wikipedia
346 · Coro - co-routines in Perl
348
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
354 Paul Evans <leonerd@leonerd.org.uk>
355perl v5.28.1 2019-02-02 CPS(3)