Math::Symbolic::Custom::Pattern - Pattern matching on Math::Symbolic trees
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);
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.
This module does not export anything.
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.
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.
Steffen M�ller, <smueller@cpan.org>
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.