intro/.expansion-more_tailcalls

filter: Statementstmt 76.1% 150 / 197 Branchbran 36.3% 40 / 110 Conditioncond n/a MC/DCmcdc n/a Subroutinesub 86.2% 44 / 51 Podpod n/a totaltotal 65.3% 234 / 358 CC 55 SCAR 17.9
CC
55
Cov
62%
functional_fact_iter
24.0
opt_odd
14.4
opt_even
14.4
CRAP 6.0
« lib/FunctionalPerl.pm ↑ Summary lib/FP/Array.pm »
1 #!/usr/bin/env perl
2  
3 # Copyright (c) 2015-2020 Christian Jaeger, copying@christianjaeger.ch
4 # This is free software. See the file COPYING.md that came bundled
5 # with this file.
6  
7 # This file shows how to use syntactical sugar additions to Perl to
8 # make the code from the file `tailcalls` look better.
9  
10 # Also, there's some added material towards the end.
11  
12 # ------------------------------------------------------------------
13 1 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
14 1 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
15 1 ▶use warnings FATAL => 'uninitialized';
Subroutine BEGIN: called CC=1 SCAR=0.0
16  
17 1 ▶use Cwd 'abs_path';
Subroutine BEGIN: called CC=1 SCAR=0.0
18 1 our ($mydir, $myname);
19  
20 1 ▶BEGIN {
Subroutine BEGIN: called CC=3 SCAR=11.7
21 1 ▶ my $location = (-l $0) ? abs_path($0) : $0;
Branch: 1 branch
BranchTrueFalseTotal
-l $0 ? : 0 1 1
22 1 ▶ $location =~ /(.*?)([^\/]+?)_?\z/s or die "?";
Branch: 1 branch
BranchTrueFalseTotal
$location =~ m[(.*?)([^/]+?)_?\z]s or die "?" 1 0 1
23 1 ($mydir, $myname) = ($1, $2);
24 }
25 1 ▶use lib "$mydir/../lib";
Subroutine BEGIN: called CC=1 SCAR=0.0
26  
27 1 ▶use Chj::TEST;
Subroutine BEGIN: called CC=1 SCAR=0.0
28 1 ▶use Chj::Backtrace;
Subroutine BEGIN: called CC=1 SCAR=0.0
29  
30 # This needs `Method::Signatures`, which is likely packaged
31 # (libmethod-signatures-perl in Debian), and `Sub::Call::Tail` which
32 # you'll probably have to install from CPAN:
33  
34 # run `cpan`, then (perhaps after configuration, just say `yes`):
35 # [`install Method::Signatures` and] `install Sub::Call::Tail`
36  
37 # This gives the 'func' keyword, to avoid having to pick up arguments
38 # explicitely from @_
39 1 ▶use Method::Signatures;
Subroutine BEGIN: called CC=1 SCAR=0.0
40  
41 # This gives the 'tail' keyword, to avoid having to use 'goto' and @_
42 # assignments
43  
44  
45 # ------------------------------------------------------------------
46  
47 # again, see (4b) in `basics` for basic explanations
48  
49 0 ▶func functional_fact($x) {
Subroutine BEGIN: called CC=1 SCAR=3.9
Subroutine functional_fact: not called CC=3 SCAR=20.3
Branch: 2 branches
BranchTrueFalseTotal
unless scalar @_ > 0 0 0 0
if scalar @_ > 1 0 0 0
50 0 functional_fact_iter($x, 1)
51 }
52  
53 1 our @functional_inspect;
54  
55 0 ▶func functional_fact_iter($x, $res) {
Subroutine BEGIN: called CC=1 SCAR=4.7
Subroutine functional_fact_iter: not called CC=5 SCAR=31.8
Branch: 3 branches
BranchTrueFalseTotal
unless scalar @_ > 0 0 0 0
unless scalar @_ > 1 0 0 0
if scalar @_ > 2 0 0 0
56 0 ▶ push @functional_inspect, func { ($x, $res) };
Subroutine __ANON__: not called CC=2 SCAR=17.9
Branch: 1 branch
BranchTrueFalseTotal
if scalar @_ > 0 0 0 0
57 0 ▶ if ($x < 2) {
Branch: 1 branch
BranchTrueFalseTotal
if ($x < 2) { } 0 0 0
58 0 return $res;
59 } else {
60  
61  
62  
63 #
64 # functional_fact_iter($x - 1, $x * $res)
65 #
66 # we could be making use of Perl's goto &$subroutine feature (see
67 # `perldoc -f goto`):
68 #
69 # @_ = ($x - 1, $x * $res);
70 # goto \&functional_fact_iter
71 #
72 # or, with nicer looks, by using Sub::Call::Tail:
73 0 tail functional_fact_iter($x - 1, $x * $res)
74 }
75 }
76  
77 # To really see the difference, here's a function that we can usefully
78 # test for higher numbers of iterations:
79  
80 0 ▶func odd($n) {
Subroutine BEGIN: called CC=1 SCAR=3.9
Subroutine odd: not called CC=4 SCAR=26.4
Branch: 2 branches
BranchTrueFalseTotal
unless scalar @_ > 0 0 0 0
if scalar @_ > 1 0 0 0
81 0 ▶ if ($n == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n == 0) { } 0 0 0
82 0 0
83 } else {
84 0 even($n - 1)
85 }
86 }
87  
88 0 ▶func even($n) {
Subroutine BEGIN: called CC=1 SCAR=3.9
Subroutine even: not called CC=4 SCAR=26.4
Branch: 2 branches
BranchTrueFalseTotal
unless scalar @_ > 0 0 0 0
if scalar @_ > 1 0 0 0
89 0 ▶ if ($n == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n == 0) { } 0 0 0
90 0 1
91 } else {
92 0 odd($n - 1)
93 }
94 }
95  
96 # $ ulimit -S -v 20000; ./more_tailcalls
97 # main> even 4
98 # $VAR1 = 1;
99 # main> even 5
100 # $VAR1 = 0;
101 # main> even 500
102 # Deep recursion on subroutine "main::even" at ./more_tailcalls line 65.
103 # Deep recursion on subroutine "main::odd" at ./more_tailcalls line 74.
104 # $VAR1 = 1;
105 # main> even 50000
106 # Deep recursion on subroutine "main::even" at ./more_tailcalls line 65.
107 # Deep recursion on subroutine "main::odd" at ./more_tailcalls line 74.
108 # Out of memory!
109  
110 # You can see that Perl ran out of space for the stack.
111  
112 0 ▶func opt_odd($n) {
Subroutine BEGIN: called CC=1 SCAR=3.9
Subroutine opt_odd: not called CC=4 SCAR=26.7
Branch: 2 branches
BranchTrueFalseTotal
unless scalar @_ > 0 0 0 0
if scalar @_ > 1 0 0 0
113 0 ▶ if ($n == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n == 0) { } 0 0 0
114 0 0
115 } else {
116 0 @_=($n - 1); goto \&opt_even;
117 }
118 }
119  
120 0 ▶func opt_even($n) {
Subroutine BEGIN: called CC=1 SCAR=3.9
Subroutine opt_even: not called CC=4 SCAR=26.7
Branch: 2 branches
BranchTrueFalseTotal
unless scalar @_ > 0 0 0 0
if scalar @_ > 1 0 0 0
121 0 ▶ if ($n == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n == 0) { } 0 0 0
122 0 1
123 } else {
124 0 @_=($n - 1); goto \&opt_odd;
125 }
126 }
127  
128 # $ ulimit -S -v 20000; ./more_tailcalls
129 # main> opt_even 500000
130 # $VAR1 = 1;
131  
132 # Now it runs with little (and constant) memory usage.
133  
134 # ------------------------------------------------------------------
135 # Note: there's also trampolining as a potential solution:
136  
137 1 ▶use FP::Trampoline;
Subroutine BEGIN: called CC=1 SCAR=0.0
138 1 ▶use Chj::time_this;
Subroutine BEGIN: called CC=1 SCAR=0.0
139  
140 1 ▶func tramp_odd($n) {
Subroutine BEGIN: called CC=1 SCAR=0.1
Subroutine tramp_odd: called CC=4 SCAR=14.6
Branch: 2 branches
BranchTrueFalseTotal
unless scalar @_ > 0 0 30000 30000
if scalar @_ > 1 0 30000 30000
141 30000 ▶ if ($n == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n == 0) { } 0 30000 30000
142 0 0
143 } else {
144 30000 ▶ T { tramp_even($n - 1) }
Subroutine __ANON__: called CC=1 SCAR=0.0
145 30000 }
146 }
147  
148 1 ▶func tramp_even($n) {
Subroutine BEGIN: called CC=1 SCAR=0.1
Subroutine tramp_even: called CC=4 SCAR=14.0
Branch: 2 branches
BranchTrueFalseTotal
unless scalar @_ > 0 0 30001 30001
if scalar @_ > 1 0 30001 30001
149 30001 ▶ if ($n == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n == 0) { } 1 30000 30001
150 1 1
151 } else {
152 30000 ▶ T { tramp_odd($n - 1) }
Subroutine __ANON__: called CC=1 SCAR=0.0
153 30000 }
154 }
155  
156 1 ▶TEST {
Subroutine __ANON__: called CC=1 SCAR=0.0
157 1 ▶ time_this { trampoline tramp_even 60000 } "T"
Subroutine __ANON__: called CC=1 SCAR=0.0
158 }
159 1 1;
160  
161 # or
162  
163 1 ▶func tramp2_odd($n) {
Subroutine BEGIN: called CC=1 SCAR=0.1
Subroutine tramp2_odd: called CC=4 SCAR=14.8
Branch: 2 branches
BranchTrueFalseTotal
unless scalar @_ > 0 0 30000 30000
if scalar @_ > 1 0 30000 30000
164 30000 ▶ if ($n == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n == 0) { } 0 30000 30000
165 0 0
166 } else {
167 30000 TC \&tramp2_even, $n - 1
168 }
169 }
170  
171 1 ▶func tramp2_even($n) {
Subroutine BEGIN: called CC=1 SCAR=0.1
Subroutine tramp2_even: called CC=4 SCAR=14.0
Branch: 2 branches
BranchTrueFalseTotal
unless scalar @_ > 0 0 30001 30001
if scalar @_ > 1 0 30001 30001
172 30001 ▶ if ($n == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n == 0) { } 1 30000 30001
173 1 1
174 } else {
175 30000 TC \&tramp2_odd, $n - 1
176 }
177 }
178  
179 1 ▶TEST {
Subroutine __ANON__: called CC=1 SCAR=0.0
180 1 ▶ time_this { trampoline tramp2_even 60000 } "TC"
Subroutine __ANON__: called CC=1 SCAR=0.0
181 }
182 1 1;
183  
184 # ------------------------------------------------------------------
185 # Also note: all of the above example are defining functions as
186 # package globals, which makes it trivial to call themselves
187 # recursively. If you need to define them as lexicals, then you need
188 # to heed the advice given in [[README]] with regards to self
189 # calls (recursive function definitions), either by way of weaken:
190  
191 1 ▶use Scalar::Util 'weaken';
Subroutine BEGIN: called CC=1 SCAR=0.0
192 1 ▶use FP::Stream 'Weakened'; # XX should probably move to non-lazyness
Subroutine BEGIN: called CC=1 SCAR=0.0
193 # related place
194  
195 1 ▶func weakened_even($n) {
Subroutine BEGIN: called CC=1 SCAR=0.1
Subroutine weakened_even: called CC=3 SCAR=11.2
Branch: 2 branches
BranchTrueFalseTotal
unless scalar @_ > 0 0 1 1
if scalar @_ > 1 0 1 1
196 1 my ($odd, $even);
197 30000 ▶ $odd = func($n) {
Subroutine __ANON__: called CC=4 SCAR=15.0
Branch: 2 branches
BranchTrueFalseTotal
unless scalar @_ > 0 0 30000 30000
if scalar @_ > 1 0 30000 30000
198 30000 ▶ if ($n == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n == 0) { } 0 30000 30000
199 0 0
200 } else {
201 30000 @_=($n - 1); goto &$even
202 }
203 1 };
204 30001 ▶ $even = func($n) {
Subroutine __ANON__: called CC=4 SCAR=14.0
Branch: 2 branches
BranchTrueFalseTotal
unless scalar @_ > 0 0 30001 30001
if scalar @_ > 1 0 30001 30001
205 30001 ▶ if ($n == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n == 0) { } 1 30000 30001
206 1 1
207 } else {
208 30000 @_=($n - 1); goto &$odd
209 }
210 1 };
211  
212  
213  
214 # bleadperl at some point (not so on v5.14.2):
215 # (XXX Perl issue, or what are the rules here?)
216 1 Weakened($even)->($n)
217 }
218  
219 1 ▶TEST {
Subroutine __ANON__: called CC=2 SCAR=7.6
220 1 ▶ ($^V->{version}[1] > 20)
Branch: 1 branch
BranchTrueFalseTotal
$^V->{'version'}[1] > 20 ? : 1 0 1
221 ? weakened_even 60000
222 : warn "skipping test on older perl"
223 }
224 1 1;
225  
226 # XXX this actually fails both on v5.14.2 and bleadperl for undefined
227 # subroutine call. Submit bug report?
228  
229 # or by using the n-ary fixpoint combinator:
230  
231 1 ▶use FP::fix;
Subroutine BEGIN: called CC=1 SCAR=0.0
232  
233 1 ▶func fix_even($n) {
Subroutine BEGIN: called CC=1 SCAR=0.1
Subroutine fix_even: called CC=3 SCAR=11.3
Branch: 2 branches
BranchTrueFalseTotal
unless scalar @_ > 0 0 1 1
if scalar @_ > 1 0 1 1
234 my ($odd, $even) = fixn(
235 30000 ▶ func($odd, $even, $n)
Subroutine __ANON__: called CC=6 SCAR=19.2
Branch: 4 branches
BranchTrueFalseTotal
unless scalar @_ > 0 0 30000 30000
unless scalar @_ > 1 0 30000 30000
unless scalar @_ > 2 0 30000 30000
if scalar @_ > 3 0 30000 30000
236 30000 ▶ {
Branch: 1 branch
BranchTrueFalseTotal
if ($n == 0) { } 0 30000 30000
237 0 if ($n == 0) {
238 0
239 30000 } else {
240 @_=($n - 1); goto &$even
241 }
242 },
243 30001 ▶ func($odd, $even, $n)
Subroutine __ANON__: called CC=6 SCAR=18.3
Branch: 4 branches
BranchTrueFalseTotal
unless scalar @_ > 0 0 30001 30001
unless scalar @_ > 1 0 30001 30001
unless scalar @_ > 2 0 30001 30001
if scalar @_ > 3 0 30001 30001
244 30001 ▶ {
Branch: 1 branch
BranchTrueFalseTotal
if ($n == 0) { } 1 30000 30001
245 1 if ($n == 0) {
246 1
247 30000 } else {
248 @_=($n - 1); goto &$odd
249 }
250 1 }
251 1 );
252 @_=($n); goto &$even
253 }
254 1 ▶ 
Subroutine __ANON__: called CC=1 SCAR=0.0
255 1 TEST { fix_even 60000 }
256 1;
257  
258 # ------------------------------------------------------------------
259 # run tests if called as part of the test suite, or
260 # enter the repl for your experiments, see (0) in `basics`
261 1 ▶ 
Branch: 1 branch
BranchTrueFalseTotal
perhaps_run_tests("main") or do { require FP::Repl; FP::Repl::repl() } 1 0 1
262 0 perhaps_run_tests "main" or do {
263 0 require FP::Repl;
264 FP::Repl::repl();
265 };
266  
« lib/FunctionalPerl.pm ↑ Summary lib/FP/Array.pm »