| 1 | # | ||||||||||
| 2 | # Copyright (c) 2015-2021 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::fix -- recurse with the fix point combinator | ||||||||||
| 13 | |||||||||||
| 14 | =head1 SYNOPSIS | ||||||||||
| 15 | |||||||||||
| 16 | 1 | ▶ | use FP::fix; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 17 | |||||||||||
| 18 | 1 | ▶ | sub fact { | ||||||||
|
Subroutine
fact: called CC=1 SCAR=0.0
| |||||||||||
| 19 | 1 | my ($z) = @_; | |||||||||
| 20 | 6 | ▶ | my $f = fix sub { | ||||||||
|
Subroutine
__ANON__: called CC=2 SCAR=6.9
| |||||||||||
| 21 | 6 | my ($f, $x, $y) = @_; | |||||||||
| 22 | 6 | ▶ | $x > 0 ? $f->($x-1, $x*$y) : $y | ||||||||
|
Branch: 1 branch
| |||||||||||
| 23 | 1 | }; | |||||||||
| 24 | 1 | $f->($z, 1) | |||||||||
| 25 | } | ||||||||||
| 26 | is fact(5), 120; | ||||||||||
| 27 | |||||||||||
| 28 | |||||||||||
| 29 | =head1 DESCRIPTION | ||||||||||
| 30 | |||||||||||
| 31 | fix takes a function and returns another function that when called | ||||||||||
| 32 | calls the original function and gives it the fix'ed function as first | ||||||||||
| 33 | argument and then the original arguments. | ||||||||||
| 34 | |||||||||||
| 35 | This allows to write self-recursive local functions without having to | ||||||||||
| 36 | deal with the problem of reference cycles that self-referencing | ||||||||||
| 37 | closures would run into. | ||||||||||
| 38 | |||||||||||
| 39 | The example from the synopsis is equivalent to: | ||||||||||
| 40 | |||||||||||
| 41 | 1 | ▶ | use Scalar::Util 'weaken'; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 42 | |||||||||||
| 43 | 1 | ▶ | sub fact2 { | ||||||||
|
Subroutine
fact2: called CC=1 SCAR=0.0
| |||||||||||
| 44 | 1 | my ($z) = @_; | |||||||||
| 45 | 1 | ▶ | my $f; $f = sub { | ||||||||
|
Subroutine
__ANON__: called CC=2 SCAR=6.9
| |||||||||||
| 46 | 6 | my ($x, $y) = @_; | |||||||||
| 47 | 6 | ▶ | $x > 0 ? $f->($x-1, $x*$y) : $y | ||||||||
|
Branch: 1 branch
| |||||||||||
| 48 | 1 | }; | |||||||||
| 49 | 1 | my $_f = $f; weaken $f; | |||||||||
| 50 | 1 | $f->($z, 1) | |||||||||
| 51 | } | ||||||||||
| 52 | is fact2(5), 120; | ||||||||||
| 53 | |||||||||||
| 54 | |||||||||||
| 55 | =head1 NOTE | ||||||||||
| 56 | |||||||||||
| 57 | This is alpha software! Read the status section in the package README | ||||||||||
| 58 | or on the L<website|http://functional-perl.org/>. | ||||||||||
| 59 | |||||||||||
| 60 | =cut | ||||||||||
| 61 | |||||||||||
| 62 | package FP::fix; | ||||||||||
| 63 | 45 | ▶ | use strict; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 64 | 45 | ▶ | use warnings; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 65 | 45 | ▶ | use warnings FATAL => 'uninitialized'; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 66 | 45 | ▶ | use Exporter "import"; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 67 | |||||||||||
| 68 | 45 | our @EXPORT = qw(fix fixn); | |||||||||
| 69 | 45 | our @EXPORT_OK = qw(); | |||||||||
| 70 | 45 | our %EXPORT_TAGS = (all => [@EXPORT, @EXPORT_OK]); | |||||||||
| 71 | |||||||||||
| 72 | 45 | ▶ | use FP::Carp; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 73 | |||||||||||
| 74 | # Alternative implementations: | ||||||||||
| 75 | |||||||||||
| 76 | # Y combinator | ||||||||||
| 77 | 45 | *Y = do { | |||||||||
| 78 | 1604 | ▶ | my $fix0 = sub { | ||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||
| 79 | 1604 | my ($fix0, $f) = @_; | |||||||||
| 80 | 1602 | ▶ | sub { | ||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||
| 81 | 1602 | @_ = (&$fix0($fix0, $f), @_); | |||||||||
| 82 | 1602 | goto &$f; | |||||||||
| 83 | } | ||||||||||
| 84 | 1604 | }; | |||||||||
| 85 | |||||||||||
| 86 | 2 | ▶ | sub { | ||||||||
|
Subroutine
__ANON__: called CC=2 SCAR=7.1
| |||||||||||
| 87 | 2 | ▶ | @_ == 1 or fp_croak_arity 1; | ||||||||
|
Branch: 1 branch
| |||||||||||
| 88 | 2 | my ($f) = @_; | |||||||||
| 89 | 2 | &$fix0($fix0, $f) | |||||||||
| 90 | } | ||||||||||
| 91 | 45 | }; | |||||||||
| 92 | |||||||||||
| 93 | # Haskell recursive let based implementation: | ||||||||||
| 94 | # XXX move this code to separate file to avoid dependencies | ||||||||||
| 95 | |||||||||||
| 96 | # fix f = let x = f x in x | ||||||||||
| 97 | |||||||||||
| 98 | 45 | ▶ | use FP::TransparentLazy qw(lazy lazyLight); | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 99 | |||||||||||
| 100 | # this variant is different since it requires $f to be curried | ||||||||||
| 101 | 1 | ▶ | *haskell_curried = sub { | ||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||
| 102 | 1 | my ($f) = @_; | |||||||||
| 103 | 1 | my $x; | |||||||||
| 104 | 1 | ▶ | $x = &$f(lazy {$x}); # can't use lazyLight here, why? | ||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||
| 105 | 1 | $x | |||||||||
| 106 | 45 | }; | |||||||||
| 107 | |||||||||||
| 108 | 45 | ▶ | use Chj::TEST; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 109 | 1 | ▶ | TEST { | ||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||
| 110 | my $f = haskell_curried( | ||||||||||
| 111 | 1 | ▶ | sub { | ||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||
| 112 | 1 | my ($self) = @_; | |||||||||
| 113 | 5 | ▶ | sub { | ||||||||
|
Subroutine
__ANON__: called CC=2 SCAR=6.9
| |||||||||||
| 114 | 5 | my ($x) = @_; | |||||||||
| 115 | 5 | ▶ | $x > 0 ? $x * &$self($x - 1) : 1 | ||||||||
|
Branch: 1 branch
| |||||||||||
| 116 | } | ||||||||||
| 117 | 1 | } | |||||||||
| 118 | 1 | ); | |||||||||
| 119 | 1 | [&$f(0), &$f(3)] | |||||||||
| 120 | } | ||||||||||
| 121 | 45 | [1, 6]; | |||||||||
| 122 | |||||||||||
| 123 | 2 | ▶ | *haskell_uncurried = sub { | ||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||
| 124 | 2 | my ($f) = @_; | |||||||||
| 125 | 2 | ▶ | my $fc = sub { | ||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||
| 126 | 2 | my ($fc) = @_; | |||||||||
| 127 | 1602 | ▶ | sub { | ||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||
| 128 | 1602 | unshift @_, $fc; | |||||||||
| 129 | 1602 | goto &$f; | |||||||||
| 130 | 2 | }; | |||||||||
| 131 | 2 | }; | |||||||||
| 132 | 2 | my $x; | |||||||||
| 133 | 2 | ▶ | $x = &$fc(lazy {$x}); # can't use lazyLight here, why? | ||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||
| 134 | 2 | $x | |||||||||
| 135 | 45 | }; | |||||||||
| 136 | |||||||||||
| 137 | # indirectly self-referencing through package variable | ||||||||||
| 138 | 2 | ▶ | *rec = sub { | ||||||||
|
Subroutine
__ANON__: called CC=2 SCAR=7.0
| |||||||||||
| 139 | 2 | ▶ | @_ == 1 or fp_croak_arity 1; | ||||||||
|
Branch: 1 branch
| |||||||||||
| 140 | 2 | my ($f) = @_; | |||||||||
| 141 | 2 | ▶ | sub { | ||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||
| 142 | #@_ = (fix ($f), @_); goto &$f; | ||||||||||
| 143 | 2 | unshift @_, fix($f); | |||||||||
| 144 | 2 | goto &$f; | |||||||||
| 145 | } | ||||||||||
| 146 | 2 | }; | |||||||||
| 147 | |||||||||||
| 148 | # directly locally self-referencing | ||||||||||
| 149 | |||||||||||
| 150 | 45 | ▶ | use Scalar::Util 'weaken'; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 151 | 45 | ▶ | use FP::Carp; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 152 | |||||||||||
| 153 | 13 | ▶ | *weakcycle = sub { | ||||||||
|
Subroutine
__ANON__: called CC=2 SCAR=6.9
| |||||||||||
| 154 | 13 | ▶ | @_ == 1 or fp_croak_arity 1; | ||||||||
|
Branch: 1 branch
| |||||||||||
| 155 | 13 | my ($f) = @_; | |||||||||
| 156 | 13 | my $f2; | |||||||||
| 157 | 3249 | ▶ | $f2 = sub { | ||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||
| 158 | 3249 | unshift @_, $f2; | |||||||||
| 159 | 3249 | goto &$f | |||||||||
| 160 | 13 | }; | |||||||||
| 161 | 13 | my $f2_ = $f2; | |||||||||
| 162 | 13 | weaken $f2; | |||||||||
| 163 | 13 | $f2_ | |||||||||
| 164 | 45 | }; | |||||||||
| 165 | |||||||||||
| 166 | # choose implementation: | ||||||||||
| 167 | |||||||||||
| 168 | sub fix; | ||||||||||
| 169 | |||||||||||
| 170 | 45 | *fix = \&weakcycle; | |||||||||
| 171 | |||||||||||
| 172 | # n-ary version: | ||||||||||
| 173 | |||||||||||
| 174 | 1 | ▶ | sub fixn { | ||||||||
|
Subroutine
fixn: called CC=4 SCAR=14.8
Pod
undocumented
| |||||||||||
| 175 | 1 | my (@f) = @_; | |||||||||
| 176 | 1 | my @ff; | |||||||||
| 177 | 1 | ▶ | for (my $i = 0; $i < @f; $i++) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 178 | 2 | my $f = $f[$i]; | |||||||||
| 179 | 60001 | ▶ | $ff[$i] = sub { | ||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||
| 180 | 60001 | unshift @_, @ff; | |||||||||
| 181 | 60001 | goto &$f; | |||||||||
| 182 | } | ||||||||||
| 183 | 2 | } | |||||||||
| 184 | 1 | my @ff_ = @ff; | |||||||||
| 185 | |||||||||||
| 186 | # weaken $_ for @ff; | ||||||||||
| 187 | # ^ XXX: releases too early, same issue as | ||||||||||
| 188 | # mentioned in `intro/more_tailcalls` | ||||||||||
| 189 | 1 | ▶ | wantarray ? @ff_ : do { ## no critic | ||||||||
|
Branch: 1 branch
| |||||||||||
| 190 | 0 | ▶ | @ff == 1 or die "fixn: got multiple arguments, but scalar context"; | ||||||||
|
Branch: 1 branch
| |||||||||||
| 191 | 0 | $ff_[0] | |||||||||
| 192 | } | ||||||||||
| 193 | } | ||||||||||
| 194 | |||||||||||
| 195 | 45 | 1 | |||||||||