lib/FP/Trampoline.pm

filter: Statementstmt 100% 40 / 40 Branchbran 80.0% 8 / 10 Conditioncond n/a MC/DCmcdc n/a Subroutinesub 100% 13 / 13 Podpod 100% 3 / 3 totaltotal 96.9% 64 / 66 CC 6 SCAR 8.0
CC
6
Cov
96%
trampoline
5.0
iterative_fact
2.0
BEGIN
1.0
CRAP 2.2
« lib/FP/url_.pm ↑ Summary lib/FP/Combinators.pm »
1 #
2 # Copyright (c) 2015-2020 Christian Jaeger, copying@christianjaeger.ch
3 #
4 # This is free software, offered under either the same terms as perl 5
5 # or the terms of the Artistic License version 2 or the terms of the
6 # MIT License (Expat version). See the file COPYING.md that came
7 # bundled with this file.
8 #
9  
10 =head1 NAME
11  
12 FP::Trampoline -- tail call optimization without reliance on goto
13  
14 =head1 SYNOPSIS
15  
16 1 ▶ use FP::Trampoline; # exports `T` and `trampoline`
Subroutine BEGIN: called CC=1 SCAR=0.0
17  
18 25 ▶ sub iterative_fact {
Subroutine iterative_fact: called CC=2 SCAR=6.9
19 25 my ($n,$tot) = @_;
20 25 ▶ $n > 1 ? T{ iterative_fact ($n-1, $tot*$n) } : $tot
Subroutine __ANON__: called CC=1 SCAR=0.0
Branch: 1 branch
BranchTrueFalseTotal
$n > 1 ? : 23 2 25
21 # or
22 # $n > 1 ? TC \&iterative_fact, $n-1, $tot*$n : $tot
23 }
24 2 ▶ sub fact {
Subroutine fact: called CC=1 SCAR=0.0
25 2 my ($n) = @_;
26 2 trampoline iterative_fact ($n, 1)
27 }
28 is fact(5), 120;
29  
30 1 ▶ use FP::Stream;
Subroutine BEGIN: called CC=1 SCAR=0.0
31 is( fact(20), stream_iota(2)->take(19)->product );
32  
33  
34 =head1 DESCRIPTION
35  
36 Perl has direct support for optimized (i.e. non-stack-eating) tail
37 calls, by way of `goto &$subref`, but there are still bugs in current
38 versions of Perl with regards to memory handling in certain situations
39 (see L<t/perl/goto-leak>). Trampolining is a technique that works
40 without reliance on any tail call optimization support by the host
41 language. Its drawbacks are more overhead and the requirement to put a
42 `trampoline`ing call around any function that employs trampolining.
43  
44 =head1 FUNCTIONS
45  
46 =over 4
47  
48 =item T { ... }
49  
50 Returns a closure blessed into the `FP::Trampoline::Continuation`
51 namespace, which represents a trampolining continuation.
52  
53 =item TC $fn, $arg1...
54  
55 Returns a `FP::Trampoline::Call` object, which represents the same
56 thing, but can only be used for a call ('Trampoline Call'). The
57 advantage is that the arguments for the call are evaluated eagerly,
58 which makes it work for dynamic variables, too (like `$_` or
59 local'ized globals). It may also be a bit faster.
60  
61 =item trampoline ($value)
62  
63 The trampoline that bounces back as long as it receives a trampolining
64 continuation: if so, the continuation is run, and the result passed to
65 the `trampoline` again, otherwise it is returned directly.
66  
67 =back
68  
69 =head1 NOTE
70  
71 This is alpha software! Read the status section in the package README
72 or on the L<website|http://functional-perl.org/>.
73  
74 =cut
75  
76 package FP::Trampoline;
77 3 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
78 3 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
79 3 ▶use warnings FATAL => 'uninitialized';
Subroutine BEGIN: called CC=1 SCAR=0.0
80 3 ▶use Exporter "import";
Subroutine BEGIN: called CC=1 SCAR=0.0
81  
82 3 our @EXPORT = qw(T TC trampoline);
83 3 our @EXPORT_OK = qw();
84 3 our %EXPORT_TAGS = (all => [@EXPORT, @EXPORT_OK]);
85  
86 3 ▶use FP::Carp;
Subroutine BEGIN: called CC=1 SCAR=0.0
87  
88 60023 ▶sub T (&) {
Subroutine T: called CC=1 SCAR=0.0
Pod documented
89 60023 bless $_[0], "FP::Trampoline::Continuation"
90 }
91  
92 60000 ▶sub TC {
Subroutine TC: called CC=1 SCAR=0.0
Pod documented
93 60000 bless [@_], "FP::Trampoline::Call"
94 }
95  
96 4 ▶sub trampoline {
Subroutine trampoline: called CC=5 SCAR=16.2
Pod documented
97 4 ▶ @_ == 1 or fp_croak_arity 1;
Branch: 1 branch
BranchTrueFalseTotal
@_ == 1 or fp_croak_arity(1) 4 0 4
98 4 my ($v) = @_;
99 4 @_ = (); # so that calling a continuation does not need () (possible
100 # speedup)
101 4 while (1) {
102 120027 ▶ if (my $r = ref $v) {
Branch: 1 branch
BranchTrueFalseTotal
if (my $r = ref $v) { } 120023 4 120027
103 $v = (
104 $r eq "FP::Trampoline::Continuation"
105 ? &$v
106 120023 ▶ : $r eq "FP::Trampoline::Call" ? do {
Branch: 2 branches
BranchTrueFalseTotal
$r eq 'FP::Trampoline::Continuation' ? : 60023 60000 120023
$r eq 'FP::Trampoline::Call' ? : 60000 0 60000
107 60000 $$v[0]->(@$v[1 .. $#$v])
108 }
109 : return $v
110 );
111 } else {
112 4 return $v
113 }
114 }
115 }
116  
117 3 1
« lib/FP/url_.pm ↑ Summary lib/FP/Combinators.pm »