Math::Expression::Evaluator::Optimizer - Math::Expression::Evaluator::Optimizer documentation

Math-Expression-Evaluator documentation Contained in the Math-Expression-Evaluator distribution.

Index

Code Index:

NAME

Top

Math::Expression::Evaluator::Optimizer - Optimize Math::Expression::Evaluator ASTs

SYNOPSIS

Top

    use Math::Expression::Evaluator;
    my $m = Math::Expression::Evaluator->new("2 + 4*f");
    $m->optimize();
    for (0..100){
        print $m->val({f => $_}), "\n";
    }

DESCRIPTION

Top

Math::Expression::Evaluator::Optimizer performs simple optimizations on the abstract syntax tree from Math::Expression::Evaluator.

You should not use this module directly, but interface it via Math::Expression::Evaluator.

The following optimizations are implemented:

PERFORMANCE CONSIDERATIONS

Top

optimize() currently takes two full loops through the AST, copying and recreating it. If you execute val() only once, calling optimize() is in fact a performance loss.

If the expression is optimizable, and you execute it $n times, you usually have a net gain over unoptimized execution if $n > 15.

Of course that value depends on the complexity of the expression, and how well it can be reduced by the implemented optimizations.

Your best is to always benchmark what you do. Most of the time the compiled version returned by ->compiled is much faster than the optimized (and not compiled) form. =cut

Math-Expression-Evaluator documentation Contained in the Math-Expression-Evaluator distribution. 
package Math::Expression::Evaluator::Optimizer;
use strict;
use warnings;


my %is_commutative = (
            '+' => 1,
            '*' => 1,
        );

sub _optimize {
    my ($expr, $ast) = @_;
    return _partial_execute($expr, _flatten($ast));
}

# Note: if you ever want to introduce some kind of scoping that is 
# tied to blocks, remove the '{' here.
my %flattable = map { $_ => 1 } ('{', '+', '*');

sub _flatten {
    my ($ast) = @_;
    return $ast unless ref $ast;

    my $type = shift @$ast;
    my @new_nodes = ($type);
    if ($flattable{$type}){
        # interpolate AST nodes with the same type
        # e.g. ['+', 2, ['+', 3, 4]] into ['+', 2, 3, 4]
        for (map { _flatten($_) } @$ast){
            if (ref $_ and $_->[0] eq $type){
                my @inner_nodes = @$_;
                shift @inner_nodes;
                push @new_nodes, @inner_nodes;
            } else {
                push @new_nodes, $_;
            }
        }
    } else {
        push @new_nodes, map { _flatten($_) } @$ast;
    }
    return \@new_nodes;
}


# _parital_execute reduces constant subexpressions to a minimal form.
sub _partial_execute {
    my ($expr, $ast) = @_;
    if (ref $ast){
        my @nodes = @$ast;
        my $type = shift @nodes;
        if ($type eq '=' || $type eq '$'){
            # XXX what to do about assignments? more thoughts needed
            return $ast;
        }
        my @new_nodes = ($type);
        my $tainted = 0;
        for my $n (@nodes){
            push @new_nodes, _optimize($expr, $n);
            if (ref $new_nodes[-1]){
                $tainted = 1;
            }
        }
        if ($tainted){
            # try to optimize things like '2 + a +3' into 'a + 5'
            # is only allowed for commutative ops
            if ($is_commutative{$type}){
#                print STDERR "Trying commutative optimization\n";
                my @untainted = ($type);
                my @tainted = ($type);
                for (1..$#new_nodes) {
                    if (ref $new_nodes[$_]){
                        push @tainted, $new_nodes[$_];
                    } else {
                        push @untainted, $new_nodes[$_];
                    }
                }

                if (@untainted > 2) {
                    # there is something to optimize
                    push @tainted, $expr->_execute(\@untainted);
                    return \@tainted;
                } else {
                    # 'twas all in vain
                    return \@new_nodes;
                }
            } else {
                return \@new_nodes;
            }
        } else {
            return $expr->_execute(\@new_nodes);
        }
    } else {
        return $ast;
    }

}

1;

# vim: sw=4 ts=4 expandtab