use strict;
use warnings;

# we now do the same thing, but in Perl, so we can show how the tail
# recursion can be replaced by a goto.

sub AtBase {
    my ($x) = @_;
    return $x <= 1;
    }

sub BaseCase {
    my ($x) = @_;
    return 1;
    }

sub Decomp {
    my ($x) = @_;
    return $x - 1;
    }

sub Combine {
    my ($x, $rec_result) = @_;
    return $x * $rec_result;
    } 

sub fn {
    my ($x) = @_;
    my $result;

    if ( AtBase($x) ) {
        return BaseCase($x);
        }
    else {
        return Combine($x, fn( Decomp($x) ));
        }
    }

print "fn: ", fn(5), "\n";

sub fn_r {
    my ($x, $cc) = @_;
    if ( AtBase($x) ) {
        # apply the builder to the base case
        return $cc->(BaseCase($x));
        }
    else {
        return fn_r(Decomp($x), 
            # this is the new builder
            sub { my ($smaller_result) = @_; 
                  $cc->(Combine($x, $smaller_result));
                }
            );
        }
    }

sub fn_cc {
    my ($x) = @_;
    return fn_r($x, sub { my ($x) = @_; return $x; });
    }

print "fn_cc: ", fn_cc(5), "\n";

sub fn_loop {
    my ($x) = @_;

    my $cc = sub { my ($x) = @_; return $x; };

fn_invoke:
    if ( AtBase($x) ) {
        return $cc->(BaseCase($x));
        }
    else {
        my $old_x = $x;
        my $old_cc = $cc;

        $x = Decomp($x);
        $cc = sub { my ($smaller_result) = @_; 
                  $old_cc->(Combine($old_x, $smaller_result));
                };

        goto fn_invoke;
        }
    }

print "fn_loop: ", fn_loop(5), "\n";
