NAME

Keyword::Treefold - Add keyword for an FP tree-fold.

SYNOPSIS

    use Keyword::TreeFold;

    # result of block is assigned to @_ while @_ > 1.
    # block consumes the stack.

    tree_fold tree_hash
    {
        my $last    = @_ / 2 - 1;

        (
            (
                map
                {
                    my $i   = 2 * $_;

                    sha256 @_[ $i, 1 + $i ]
                }
                ( 0 .. $last )
            ),
            @_ % 2
            ? $_[-1]
            : ()
        )
    }

    # same result as above with wrapper code extracting the
    # lexical variables. block can extract any number of 
    # variables > 1.

    tree_fold tree_hash ( $left, $rite )
    {
        $rite
        ? sha256 $left, $rite
        : $left
    }

    # in all cases an exception will be raised if the stack does
    # not shrink after each iteration (e.g., if a block with two
    # parameters outputs two values for each iteration).

DESCRIPTION

The "fold" pattern is common in FP languages. It is commonly seen as a "Right Fold" in the form of reduce, which takes a single value and iterates it with the stack to form a single value (e.g., with an addition to get a sum). A recursive solution to reduce combines the first two items from the stack (e.g., by adding them) and then calls itself with the result and the remaining stack. This chews through the stack one item at a time.

Tree Fold is a bit different in that it iterates the entire stack each time before recursing. For example the AWS "tree hash" used with Glacier uploads does an SHA of every pair of items on the stack then recurses a new stack half the size.

One issue with the recursive solution is consuming a huge amount of stack. The solution to this is tail call elimination, which is a built-in part of most FP lanuages. While quite doable in Perl5 the fix is somewhat ugly, requiring an assignment to @_ and use of goto to restart the current subroutine recycling the stack.

This module implements a tree_fold keyword which wraps the input block in code that checks the scak, re-assigns @_, and uses goto to recurse. This avoids the overhad of multiple stack frames with minimal overhead.

Simple Blocks

If the block using tree_fold does not include any parameters it gets wrapped in code like:

    sub $name
    {
        @_ > 1 or return $_[0];

        @_ = do { code block };

        goto __SUB__
    }

In this case it is up to the block to consume @_ for itself. For example, the glacier tree hash might look like:

    tree_fold glacier_hash
    {
        my $count
        = @_ % 2
        ? @_ / 2 + 1
        : @_ / 2
        ;
        
        map
        {
            @_ > 1
            ? sha256 splice @_, 0, 2
            : shift
        }
        ( 1 .. $count )
    }

which will convert the current stack into a set of SHA256 values for each pair of items on the stack.

Using Parameters

Instead of managing the stack itself, the block can use parameters. The glacier hash might look like:

    tree_fold glacier_hash( $left, $rite )
    {
        $rite
        ? sha256 $left, $rite
        : $left
    }

which leaves the wrapper produced by tree_fold to splice off the stack contents and assign them to $left & $rite for each iteration.

SEE ALSO

Keyword::Declare

Which describes how this module constructs the wrapper for each block.

List::Util

Examples of reduce.

Neatly Folding a Tree

Talk describing FP solution to a tree-hash including use of tail call elimination and constant values:

<http://www.slideshare.net/lembark/neatly-foldingatree-62637403>

Combined talk with Damian Conway on tail call elimination in Perl5 and Perl6:

<http://www.slideshare.net/lembark/neatly-hashing-a-tree-fp-treefold-in-perl5-perl6>

AUTHOR

Steven Lembark <lembark@wrkhors.com>

LICENSE

This module is licensed under the same terms as Perl-5.22 itself or any later version of Perl.