NAME

Math::Symbolic::Custom::Pattern - Pattern matching on Math::Symbolic trees

SYNOPSIS

  use Math::Symbolic qw/parse_from_string/;
  use Math::Symbolic::Custom::Pattern;
  my $patternstring = "VAR_foo + sin(CONST * VAR_foo)"
  my $pattern = Math::Symbolic::Custom::Pattern->new( $patternstring );
  
  my $formula = parse_from_string("a + sin(5 * a)");
  
  if ($pattern->match($formula)) {
    print "The pattern matches the formula.\n";
  }
  else {
    print "The pattern does not match the formula.\n";
  }

  # will print "The pattern matches the formula" since "a" is
  # found to be "VAR_foo" and 5 is a constant.
  # "a + sin(5 * b)" would not match since VAR_foo is already "a"
  # when the "b" is encountered. "VAR" would match any variable.
  # "TREE" matches any tree. "TREE_name" and "CONST_name" work as
  # you would expect.
  
  # Alternatively:
  my $pattern = $some_formula->to_pattern();
  
  print "yes\n" if $formula->is_of_form($pattern); # fast-ish
  # This has syntactic sugar, too:
  print "yes\n" if $formula->is_of_form("VAR + TREE"); # slow!
  print "yes\n" if $formula->is_of_form($another_formula); # semi-slow...
  
  # Finally, when creating a pattern, one can specify that addition and
  # product should match commutatively:
  my $pattern = Math::Symbolic::Custom::Pattern->new(
    parse_from_string("a + b"), commutation => 1,
  );
  my $formula = parse_from_string("b + a");
  # does match even though "a+b" <=> "b+a" aren't the same
  # internal tree representations
  print "yes\n" if $pattern->match($formula);

DESCRIPTION

This module is an extension to the Math::Symbolic module. A basic familiarity with that module is required.

The Math::Symbolic::Custom::Pattern module implements pattern matching routines on Math::Symbolic trees. The patterns itself are constructed from Math::Symbolic trees with just a few variables which have a special meaning.

The module provides two interfaces. You can use the new() and match() methods this class provides, or you can use the to_pattern() and is_of_form() methods on any Math::Symbolic tree. (Exported by the Math::Symbolic::Custom::Pattern::Export module. Refer to that module for details on is_of_form().)

You can construct a pattern from any Math::Symbolic tree. For sake of simplicity, we will talk about a tree "a+(b*c)" even if that's just its string representation. The tree is really what is returned by Math::Symbolic->parse_from_string("a+(b*c)").

Suppose you call

  my $pattern = Math::Symbolic::Custom::Pattern->new("a+(b*c)");

That creates a pattern that matches this exact tree. Calling

  my $boolean = $pattern->match($tree);

on any Math::Symbolic tree $tree will result in $boolean being false except if it is "a+(b*c)".

So far so good. This isn't impressive and the is_identical() method of all Math::Symbolic trees does the same. (Except that the pattern matching is about twice as fast.)

If you create a pattern from the following string, however, you get different behaviour: "VAR + (VAR*VAR)". Now, any variable may be in place of a, b, and c. ("a + (x*x)", b + (b*b), ...)

You can match with named (but not literal) variables with the following pattern string: "VAR_first + (VAR_first*VAR_second)" This matches the tree "a + (a*b)", but not "a + (c*b)" since the first variable in the parenthesis of the second tree is not the same as the one outside the parenthesis. Note that the variable "b" in both examples could have been any variable, since VAR_second occurrs only once in the pattern.

Analogous to the general VAR and named VAR_foo pattern elements, you may use TREE to match any subtree whatsoever or TREE_foo to match a named tree. Example: The pattern "TREE_a + 5*TREE_a" matches the tree "sin(b+c) + 5*sin(b+c)", but not "sin(b+c) + 5*cos(b+c)". Beware of the fact that the trees "sin(b+c)" and "sin(c+b)" would not be the same either. Though mathematically equivalent, they do not have the same internal representation. Canonicalizing the internal representation is simple in this example, but is impossible in the general case, so just take care.

Finally, what works with variables and general trees also works with constants. You may specify the pattern "CONST_foo * a + atan(CONST_foo)". This matches "0.5*a + atan(0.5)", but does not match "2*a + atan(0.5)" since the named constants are not equal. The general form CONST works as a wildcard for any constants.

EXPORT

This module does not export anything.

METHODS

This is a list of public methods.

new

new() is the constructor for Math::Symbolic::Custom::Pattern objects. It takes a Math::Symbolic tree as first argument which will be transformed into a pattern. See the match() method documentation.

After the Math::Symbolic tree, a list of key/value pairs can be passed in as options for the pattern construction.

The only currently supported option is commutation indicating whether or not the pattern should match sums and products commutatively. Please note that this does not match recursively and does not recognize associativity: The commutative pattern of (a + b) + c matches the expression (b + a) + c and c + (b + a), but not a + (b + c)! This means that if the tree to match is built from a string such as a + b + c, then it is not defined whether (a + b) + c matches that expression. It does so if the internal tree representation happens to be (a + b) + c and it doesn't if it happens to be a + (b + c). This may be fixed at a later point.

match

This method takes a Math::Symbolic tree as first argument. It throws a fatal error if this is not the case.

It returns a true value if the pattern matches the tree and a false value if the pattern does not match. Please have a look at the DESCRIPTION to find out what matching means in this context.

As a matter of fact, if you need to know what subtrees were matched by the various VAR_foo, TREE_bar, and CONST_baz identifiers, you can find out by inspecting the return value of a successful match. It will be a reference to a hash containing three key/value pairs with the keys trees, vars, and constants. Each of these will again point to a hash. These hashes contain the names of the matched subtrees. For example, if your pattern is TREE_x + TREE_x and it matches foo*bar + foo*bar, then the return value will be:

  {
    constants => {},
    trees     => {},
    vars      => {
      'x' => 'foo*bar',
    }
  }

Except that foo*bar will actually be the corresponding Math::Symbolic tree and not a string. Please note that the subtrees are real subtrees. Modifying them will result in a modified original tree as well.

to_string

Returns a string representation of the pattern.

SEE ALSO

New versions of this module can be found on http://steffen-mueller.net or CPAN.

Math::Symbolic::Custom::Pattern::Export implements the is_of_form() and to_pattern() methods.

Math::Symbolic

Math::Symbolic::Custom and Math::Symbolic::Custom::Base for details on enhancing Math::Symbolic.

AUTHOR

Steffen M�ller, <smueller@cpan.org>

COPYRIGHT AND LICENSE

Copyright (C) 2005, 2006, 2008, 2009, 2013 by Steffen Mueller

This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself, either Perl version 5.8.4 or, at your option, any later version of Perl 5 you may have available.

cpanm Math::Symbolic::Custom::Pattern

perl -MCPAN -e shell
install Math::Symbolic::Custom::Pattern