| 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
| |||||||||||||||
| 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
| |||||||||||||||
| 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
| |||||||||||||||
| 103 | $v = ( | ||||||||||||||
| 104 | $r eq "FP::Trampoline::Continuation" | ||||||||||||||
| 105 | ? &$v | ||||||||||||||
| 106 | 120023 | ▶ | : $r eq "FP::Trampoline::Call" ? do { | ||||||||||||
|
Branch: 2 branches
| |||||||||||||||
| 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 | |||||||||||||