view release on metacpan or  search on metacpan

intro/more_tailcalls  view on Meta::CPAN

# main> opt_even 500000
# $VAR1 = 1;

# Now it runs with little (and constant) memory usage.

# ------------------------------------------------------------------
# Note: there's also trampolining as a potential solution:

use FP::Trampoline;
use Chj::time_this;

func tramp_odd($n) {
    if ($n == 0) {
        0
    } else {
        T { tramp_even($n - 1) }
    }
}

func tramp_even($n) {
    if ($n == 0) {
        1
    } else {
        T { tramp_odd($n - 1) }
    }
}

TEST {
    time_this { trampoline tramp_even 60000 } "T"
}
1;

# or

func tramp2_odd($n) {
    if ($n == 0) {
        0
    } else {
        TC \&tramp2_even, $n - 1
    }
}

func tramp2_even($n) {
    if ($n == 0) {
        1
    } else {
        TC \&tramp2_odd, $n - 1
    }
}

TEST {
    time_this { trampoline tramp2_even 60000 } "TC"
}
1;

# ------------------------------------------------------------------
# Also note: all of the above example are defining functions as
# package globals, which makes it trivial to call themselves
# recursively. If you need to define them as lexicals, then you need
# to heed the advice given in [[README]] with regards to self
# calls (recursive function definitions), either by way of weaken:

use Scalar::Util 'weaken';
use FP::Stream 'Weakened';    # XX should probably move to non-lazyness
                              # related place

func weakened_even($n) {
    my ($odd, $even);
    $odd = func($n) {
        if ($n == 0) {
            0
        } else {
            tail &$even($n - 1)
        }
    };
    $even = func($n) {
        if ($n == 0) {
            1
        } else {
            tail &$odd($n - 1)
        }
    };

    # do *not* make this a tail call or $even will become undef on
    # bleadperl at some point (not so on v5.14.2):
    # (XXX Perl issue, or what are the rules here?)
    Weakened($even)->($n)
}

TEST {
    ($^V->{version}[1] > 20)
        ? weakened_even 60000
        : warn "skipping test on older perl"
}
1;

# XXX this actually fails both on v5.14.2 and bleadperl for undefined
# subroutine call. Submit bug report?

# or by using the n-ary fixpoint combinator:

use FP::fix;

func fix_even($n) {
    my ($odd, $even) = fixn(
        func($odd, $even, $n)
        {
            if ($n == 0) {
                0
            } else {
                tail &$even($n - 1)
            }
        },
        func($odd, $even, $n)
        {
            if ($n == 0) {
                1
            } else {
                tail &$odd($n - 1)
            }
        }
    );
    tail &$even($n)
}

TEST { fix_even 60000 }
1;

# ------------------------------------------------------------------
# run tests if called as part of the test suite, or
# enter the repl for your experiments, see (0) in `basics`

perhaps_run_tests "main" or do {
    require FP::Repl;
    FP::Repl::repl();
};