Writing a fast pattern matcher, updates and questions

[James Crist]

All,

In my spare time, I've been working on implementing a fast pattern matcher that accounts for Associative and Commutative symbols. It's going to be a while before I'm ready to release the code (it needs some serious cleanup), but as of now it is "partly functional". Some notation:

T = set of known patterns. A trie like data structure is used to preprocess these patterns to aid in fast matching.
s = expression to be matched
x, y = variables
a, b, c = constants

Currently the matcher can determine what patterns in T match s, in the presence of associative and commutative symbols, as long as the pattern is "linear". By linear, I mean no repeated *variable* symbols (`x + y` is acceptable, `x + x` is not). If no associative and commutative symbols are present, it can also determine a match substitution to make `s` equivalent with the pattern.

Some design questions before I continue work:

- Is there any use for just determining what patterns match, without generating a match substitution? Determining if a match exists is faster than determining a specific substitution. However, in the presence of nonlinear patterns a substitution needs to be found to verify the match is valid. This decision determines how tightly coupled the two algorithms will be.

- Is there need for nonlinear patterns? I plan to account for them, but they make the algorithm a bit more complicated. Nonlinear, AC pattern matching is NP complete. Linear AC pattern matches can be found in polynomial time.

- In a general case, there can be many substitutions that match a specific pattern mod AC. For example, given `t = x*y`, and `s = a*b*c`, this can match with {x: a*b, y: c}, or {x:a, y: b*c}, etc... This is easy to account for, and can be done lazily. Api-wise, are there cases where generating more than one matching substitution are needed?

- The algorithm lazily determines matches. Currently preference is given to matching variables before constants, but it could go the other way around. i.e. if T = {a + b, x + b}, and s = a + b, then the matcher will find `x + b` before `a + b`. I'd rather not make this configurable, as it complicates things. The question is, do we want the most general match first, or the most specific?

- At the moment, the code is completely removed from dependence on sympy, and can function on its own. As such, I'm planning on making it a separate library that can be used by SymPy as a dependency. I understand we were against that in the past, but this may be changing? I'd rather not maintain two separate codebases.

- There's a `commutative` assumption in sympy, but there doesn't seem to be an `associative` one. How can I check if a function/operator is associative? Does this information need to be kept elsewhere?

- Jim

[Aaron Meurer]

On Wed, Nov 26, 2014 at 4:19 PM, James Crist <cris...@umn.edu> wrote:
> All,
>
> In my spare time, I've been working on implementing a fast pattern matcher
> that accounts for Associative and Commutative symbols. It's going to be a
> while before I'm ready to release the code (it needs some serious cleanup),
> but as of now it is "partly functional". Some notation:

This is awesome. Have you seen the previous discussions on pattern
matching on this mailing list (I think there are also wiki pages).
They focus more on features than performance, but it's worth looking
at.

>
> T = set of known patterns. A trie like data structure is used to preprocess
> these patterns to aid in fast matching.
> s = expression to be matched
> x, y = variables
> a, b, c = constants
>
> Currently the matcher can determine what patterns in T match s, in the
> presence of associative and commutative symbols, as long as the pattern is
> "linear". By linear, I mean no repeated *variable* symbols (`x + y` is
> acceptable, `x + x` is not). If no associative and commutative symbols are
> present, it can also determine a match substitution to make `s` equivalent
> with the pattern.
>
> Some design questions before I continue work:
>
> - Is there any use for just determining what patterns match, without
> generating a match substitution? Determining if a match exists is faster
> than determining a specific substitution. However, in the presence of
> nonlinear patterns a substitution needs to be found to verify the match is
> valid. This decision determines how tightly coupled the two algorithms will
> be.

I've never seen that, and skimming through 'git grep match' I don't
see any instances where the match isn't assigned to a variable
(although I didn't check the context to see if that variable is used
in a non-boolean context).

>
> - Is there need for nonlinear patterns? I plan to account for them, but they
> make the algorithm a bit more complicated. Nonlinear, AC pattern matching is
> NP complete. Linear AC pattern matches can be found in polynomial time.

Interesting. Why is that?

>
> - In a general case, there can be many substitutions that match a specific
> pattern mod AC. For example, given `t = x*y`, and `s = a*b*c`, this can
> match with {x: a*b, y: c}, or {x:a, y: b*c}, etc... This is easy to account
> for, and can be done lazily. Api-wise, are there cases where generating more
> than one matching substitution are needed?

I can't think of use-cases, but that doesn't mean that they aren't
there. The only case I can think of where you would want to look at
multiple matches is if you are looking for a match with a specific
structure, and ideally, the API for that would be to put that
structure on the Wild object somehow (like a boolean expression that
has to be true for the Wild to match) and the algorithm would check
this automatically.

>
> - The algorithm lazily determines matches. Currently preference is given to
> matching variables before constants, but it could go the other way around.
> i.e. if T = {a + b, x + b}, and s = a + b, then the matcher will find `x +
> b` before `a + b`. I'd rather not make this configurable, as it complicates
> things. The question is, do we want the most general match first, or the
> most specific?

Whichever one is the correct behavior for a dispatch system. I *think*
that means specific, but I could be getting it backwards.

I'm assuming that the whole point of having a set of patterns rather
than a single pattern at a time is so you can do this.

>
> - At the moment, the code is completely removed from dependence on sympy,
> and can function on its own. As such, I'm planning on making it a separate
> library that can be used by SymPy as a dependency. I understand we were
> against that in the past, but this may be changing? I'd rather not maintain
> two separate codebases.

Let's look at the code first, and then figure this out.

>
> - There's a `commutative` assumption in sympy, but there doesn't seem to be
> an `associative` one. How can I check if a function/operator is associative?
> Does this information need to be kept elsewhere?

The commutative assumption is a mess anyway. It's a very different
assumption than every other assumption in the assumptions system for a
few reasons. The main thing is that it's kind of strange to call a
symbol commutative or noncommutative as commutativity is a property of
two expressions and an operator (A, B, and * in A*B).

For associativity, we can add one if it helps, but I think for now
only operators that subclass from AssocOp automatically associate
(it's a bad situation, though, because one, we shouldn't force people
to subclass to mark objects as having a property, especially if that
class wants to add behavior, and two, AssocOp is really
AssocOpWithIdentity). And also, of course, the same issue applies here
that associativity is really a property of the operator *and* the
objects applied on that operator, especially if we dispatch operators
so that they mean different things depending on their arguments (for
instance, A*B*C is *not* associative if A, B, and C are matrices and
we care about computational complexity).

Aaron Meurer

>
> - Jim
>
> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sympy.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/sympy/42d9511d-e963-416f-9d4e-3e0435461422%40googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[Francesco Bonazzi]

On Thursday, November 27, 2014 12:19:04 AM UTC+1, James Crist wrote:

All,

In my spare time, I've been working on implementing a fast pattern matcher that accounts for Associative and Commutative symbols. It's going to be a while before I'm ready to release the code (it needs some serious cleanup), but as of now it is "partly functional". Some notation:

T = set of known patterns. A trie like data structure is used to preprocess these patterns to aid in fast matching.
s = expression to be matched
x, y = variables
a, b, c = constants

That's cool. Is it addressing this issue?
https://github.com/sympy/sympy/issues/7748

Currently the matcher can determine what patterns in T match s, in the presence of associative and commutative symbols, as long as the pattern is "linear". By linear, I mean no repeated *variable* symbols (`x + y` is acceptable, `x + x` is not). If no associative and commutative symbols are present, it can also determine a match substitution to make `s` equivalent with the pattern.

You mean expressions like Add(x, x, evaluate=False) ? I think there should be a way to check where an expression is in a canonical order.
 

Some design questions before I continue work:

- Is there any use for just determining what patterns match, without generating a match substitution? Determining if a match exists is faster than determining a specific substitution. However, in the presence of nonlinear patterns a substitution needs to be found to verify the match is valid. This decision determines how tightly coupled the two algorithms will be.

I guess the primary usage of patterns lies in expression transformations. SymPy has a .match( ) to solve for wilds, and .has( ) to find whether a subexpression is in the tree expression.
 

- Is there need for nonlinear patterns? I plan to account for them, but they make the algorithm a bit more complicated. Nonlinear, AC pattern matching is NP complete. Linear AC pattern matches can be found in polynomial time.

- In a general case, there can be many substitutions that match a specific pattern mod AC. For example, given `t = x*y`, and `s = a*b*c`, this can match with {x: a*b, y: c}, or {x:a, y: b*c}, etc... This is easy to account for, and can be done lazily. Api-wise, are there cases where generating more than one matching substitution are needed?

Maybe it is preferrable that the first lazily generated substitution appears in the same order as Mathematica's pattern matching. It would make Mathematica's code more easily portable to SymPy.
 

- The algorithm lazily determines matches. Currently preference is given to matching variables before constants, but it could go the other way around. i.e. if T = {a + b, x + b}, and s = a + b, then the matcher will find `x + b` before `a + b`. I'd rather not make this configurable, as it complicates things. The question is, do we want the most general match first, or the most specific?

I think that, given a set of matching expressions, we should get the first lazy occurrence of the most specific of the expressions in that set. That is, if a pattern expression A matches a proper subset of pattern expression B, B should be discarded completely whenever A matches.

- At the moment, the code is completely removed from dependence on sympy, and can function on its own. As such, I'm planning on making it a separate library that can be used by SymPy as a dependency. I understand we were against that in the past, but this may be changing? I'd rather not maintain two separate codebases.

What kind of AST are you matching?

In sympy.unify, there's a function to transform a SymPy expression to a special type of AST object:
https://github.com/sympy/sympy/blob/298bbdbafa26c45526c622374acd11ac05a357e6/sympy/unify/usympy.py#L44

- There's a `commutative` assumption in sympy, but there doesn't seem to be an `associative` one. How can I check if a function/operator is associative? Does this information need to be kept elsewhere?

Associativity is a property of the AST node, while commutativity is more complicated.

In Mathematica there is Times[ ... ], which is fully commutative, and Dot[ ... ] which is non-commutative. In general, AST nodes has an attribute "Orderless" to make all of their args commutative among each other. Similarly, Maxima has (mtimes ... ) and (mnctimes ... ) for commutative and non-commutative multiplication nodes.

SymPy associates commutativity with an assumption and/or the type of the argument. For example, two matrices usually do not commute. That is quite complicated to deal with.

One last complication: have you had any thought of how this could be extended to an AST node containing a PermutationGroup instance determining how its arguments commute/anticommute? That could have some applications in the tensor module, but I guess it's hard or impossible to find a polynomial algorithm for that.

By the way, are you using Wild objects, or are you specifying wilds by an extra parameter?
In unify.rewriterule, you just put in two expressions, and specify which ones are variables (i.e. wilds) in another parameter. Furthermore, there is an option to put a filtering lambda function and assumptions, so that matches should be compatible with a test function and/or SymPy's new-style assumptions.

https://github.com/sympy/sympy/blob/298bbdbafa26c45526c622374acd11ac05a357e6/sympy/unify/rewrite.py#L11

Assumptions awareness would be a desired feature.

Any considerations about nodes marked as one parameter identities? That is, Add(x) = x, Mul(x) = x, i.e. nodes that are identities if there is just one parameter.

[Matthew Rocklin]

Response in line

On Wed, Nov 26, 2014 at 3:19 PM, James Crist <cris...@umn.edu> wrote:

All,

In my spare time, I've been working on implementing a fast pattern matcher that accounts for Associative and Commutative symbols. It's going to be a while before I'm ready to release the code (it needs some serious cleanup), but as of now it is "partly functional". Some notation:

T = set of known patterns. A trie like data structure is used to preprocess these patterns to aid in fast matching.
s = expression to be matched
x, y = variables
a, b, c = constants

Awesome, thanks for doing this.

 

Currently the matcher can determine what patterns in T match s, in the presence of associative and commutative symbols, as long as the pattern is "linear". By linear, I mean no repeated *variable* symbols (`x + y` is acceptable, `x + x` is not). If no associative and commutative symbols are present, it can also determine a match substitution to make `s` equivalent with the pattern.

Some design questions before I continue work:

- Is there any use for just determining what patterns match, without generating a match substitution? Determining if a match exists is faster than determining a specific substitution. However, in the presence of nonlinear patterns a substitution needs to be found to verify the match is valid. This decision determines how tightly coupled the two algorithms will be.

I can think of use cases but they're secondary.  One might ask questions like "is this expression an element of known class of special functions?".

 

- Is there need for nonlinear patterns? I plan to account for them, but they make the algorithm a bit more complicated. Nonlinear, AC pattern matching is NP complete. Linear AC pattern matches can be found in polynomial time.

I haven't thought much about this.  Is X*X.T non-linear?

- In a general case, there can be many substitutions that match a specific pattern mod AC. For example, given `t = x*y`, and `s = a*b*c`, this can match with {x: a*b, y: c}, or {x:a, y: b*c}, etc... This is easy to account for, and can be done lazily. Api-wise, are there cases where generating more than one matching substitution are needed?

I believe so.  Sometimes we have a condition that can't be expressed in terms of patterns (e.g. pulling in assumptions) and so we fall back to python iteration and finding the first in the sequence that matches some python condition.  

Another major use case is selecting the "best" match.  In this case we might also want to control the order in which matches come out of the sequence so that matches that we think are best come first.

- The algorithm lazily determines matches. Currently preference is given to matching variables before constants, but it could go the other way around. i.e. if T = {a + b, x + b}, and s = a + b, then the matcher will find `x + b` before `a + b`. I'd rather not make this configurable, as it complicates things. The question is, do we want the most general match first, or the most specific?

In my ideal world I might be able to decide the order in which we traverse the tree of possible matches.  I don't know exactly how your algorithm works but, in some algorithms, we obtain a set of partial matches at each step and then have to decide which branch to pursue first.  I've found that accepting a user-provided objective function is useful.  It allows the user to specify a greedy search strategy.

More generally I've found that controlling the traversal midstream is of high-value.  This might have been in my particular use case though.

 

- At the moment, the code is completely removed from dependence on sympy, and can function on its own. As such, I'm planning on making it a separate library that can be used by SymPy as a dependency. I understand we were against that in the past, but this may be changing? I'd rather not maintain two separate codebases.

Hooray!

 

- There's a `commutative` assumption in sympy, but there doesn't seem to be an `associative` one. How can I check if a function/operator is associative? Does this information need to be kept elsewhere?

Aaron mentioned AssocOp.  FWIW I'm not sure that any Sets or MatrixExprs use this, despite being at times associative.  Perhaps they should.  If one wanted a hack they could just keep a set of known associative types somewhere.

[Joachim Durchholz]

Am 27.11.2014 um 16:47 schrieb Matthew Rocklin:
>> - Is there need for nonlinear patterns? I plan to account for them, but
>> they make the algorithm a bit more complicated. Nonlinear, AC pattern
>> matching is NP complete. Linear AC pattern matches can be found in
>> polynomial time.
>
> I haven't thought much about this. Is X*X.T non-linear?

From other mentions of "linear" and "nonlinear", I infer that patterns
with multiple occurrences of the same symbol are always nonlinear.

Might have to do with the fact that to check whether such a pattern
matches, you have to traverse the entire subtrees that you'd want to
match with X and see whether the subtrees are the same.

IIRC from my university time, matching nonlinear patterns like the above
is one of the key ingredients that makes a Prolog interpreter
Turing-complete.

[Joachim Durchholz]

Am 27.11.2014 um 00:19 schrieb James Crist:
> All,
>
> In my spare time, I've been working on implementing a fast pattern matcher
> that accounts for Associative and Commutative symbols. It's going to be a
> while before I'm ready to release the code (it needs some serious cleanup),
> but as of now it is "partly functional". Some notation:
>
> T = set of known patterns. A trie like data structure is used to preprocess
> these patterns to aid in fast matching.
> s = expression to be matched
> x, y = variables
> a, b, c = constants
>
> Currently the matcher can determine what patterns in T match s, in the
> presence of associative and commutative symbols, as long as the pattern is
> "linear". By linear, I mean no repeated *variable* symbols (`x + y` is
> acceptable, `x + x` is not).

That's an important restriction.
It's probably also what makes the pattern matcher fast enough to be
useful :-)

> - Is there any use for just determining what patterns match, without
> generating a match substitution? Determining if a match exists is faster
> than determining a specific substitution. However, in the presence of
> nonlinear patterns a substitution needs to be found to verify the match is
> valid. This decision determines how tightly coupled the two algorithms will
> be.

See the next remark.

> - Is there need for nonlinear patterns? I plan to account for them, but
> they make the algorithm a bit more complicated. Nonlinear, AC pattern
> matching is NP complete. Linear AC pattern matches can be found in
> polynomial time.

This depends on what you're aiming for.

Is it a basic building block for other algorithms to use? Then favor
predictable performance over features. Something that has unpredictable
performance isn't very attractive to an algorithm author.

Are you aiming for something that can solve as many situations as
possible? Then aim for more features.
I'm somewhat sceptical whether just pattern matching will be the right
approach, but I suspect you aren't after this one anyway :-)

> - In a general case, there can be many substitutions that match a specific
> pattern mod AC. For example, given `t = x*y`, and `s = a*b*c`, this can
> match with {x: a*b, y: c}, or {x:a, y: b*c}, etc... This is easy to account
> for, and can be done lazily. Api-wise, are there cases where generating
> more than one matching substitution are needed?

I'm not sure that such cases will actually come up, but if they do (and
I see a significant probability that they will), it would be a pity if
your code would have to be rewritten from scratch.

So I'd recommend doing that, or at least keeping the path to this kind
of stuff open if possible.

> - The algorithm lazily determines matches. Currently preference is given to
> matching variables before constants, but it could go the other way around.
> i.e. if T = {a + b, x + b}, and s = a + b, then the matcher will find `x +
> b` before `a + b`. I'd rather not make this configurable, as it complicates
> things. The question is, do we want the most general match first, or the
> most specific?

It's almost a given that anybody who writes an algorithm on top of the
pattern matcher will find that the first match found isn't suitable but
some other matching order would fit their needs *exactly*.

You could tackle the complication, or just complete your work and assume
somebody else will find a less intrusive way to make it configurable.
For that, your code would have to be simple and easily understood -
which is something that would make the code more useful in the long term
anyway.

> - At the moment, the code is completely removed from dependence on sympy,
> and can function on its own. As such, I'm planning on making it a separate
> library that can be used by SymPy as a dependency. I understand we were
> against that in the past, but this may be changing? I'd rather not maintain
> two separate codebases.

Heh. I'm seeing SymPy spin-offs of that kind happening lately.
I suspect SymPy could profit from rephrasing its "avoid external
dependencies" policy, but that's a different discussion, and possibly
one that can't be done before some more investigation has been done.

Regards,
Jo

[Richard Fateman]

There's a long history of pattern matching "fast" including work by Richard Jenks, 

(Scratchpad, predecessor of Axiom).  The general scheme is to take a collection

of patterns and compile them into a tree form so that partial results from pattern 1

can be used to improve speed on pattern 2, etc.

I don't know if your AC matcher is intended to be used for (say)  arithmetic expressions

or something else.  But if arithmetic -- your stuff also needs to deal with identities.

In that case if

you don't handle identities, your matcher becomes far less interesting.

In addition to Jenks' stuff, you should certainly look  at Mathematica's pattern

matching, and perhaps my own matcher in Macsyma/ Maxima  "semantic"

matching.

Good luck

RJF

[Joachim Durchholz]

Am 27.11.2014 um 20:52 schrieb Richard Fateman:
> I don't know if your AC matcher is intended to be used for (say)
> arithmetic expressions
> or something else. But if arithmetic -- your stuff also needs to deal with
> identities.
> In that case if
> you don't handle identities, your matcher becomes far less interesting.

What's the definition of "identity" in this context?

I'm asking because I'm wondering whether James' matcher might be useful
for building one if it doesn't cover identities yet, which hinges on
what an identity is and hence how it could be established or not.
(Identities in the true mathematical sense are undecidable, Goedel yadda
yadda; so you might be meaning something structural, is that so?)

Regards,
Jo

[James Crist]

Oh boy, this is going to be a big post. Responding to everyone in turn:

@Aaron:

> Nonlinear, AC pattern matching is NP complete. Linear AC pattern matches 

> can be found in polynomial time.

Interesting. Why is that?

Joachim got it right, having each match constrained by other matches, and a (potentially) combinatorially large set of available match combinations makes the nonlinear, associative-commutative problem much harder. This is a good paper on the subject: http://www.sciencedirect.com/science/article/pii/S0747717187800275

>The question is, do we want the most general match first, or the
> most specific?

Whichever one is the correct behavior for a dispatch system. I *think*
that means specific, but I could be getting it backwards.

I'm assuming that the whole point of having a set of patterns rather
than a single pattern at a time is so you can do this.

That's exactly the purpose. In that case, matching on constants rather than variables is the desired behavior (more specific patterns first, then more general). I'll think about ways to make this configurable, but right now I'm more interested in making it *work*.


@Francesco

That's cool. Is it addressing this issue?
https://github.com/sympy/sympy/issues/7748

Didn't know we had an issue on this, but yes - in part. The main purpose behind this was originally to get a good matcher for tiling the expression tree into computations for code generation, as there isn't necessarily a 1-to-1 match between nodes and C/Fortran functions. But since I had to write it for that, it made sense to make it general so it can be used everywhere else it's needed.

You mean expressions like Add(x, x, evaluate=False) ? I think there should be a way to check where an expression is in a canonical order.

No, I mean anything where a variable occurs in a pattern more than once. So even sin(x)*cos(x), where x is a variable is nonlinear.

Maybe it is preferrable that the first lazily generated substitution appears in the same order as Mathematica's pattern matching. It would make Mathematica's code more easily portable to SymPy.

I think that would be incredibly hard to do. Especially since I have no access to or experience with mathematica. It all depends on the ordering algorithm they use for generating the potential matches.

What kind of AST are you matching?

It only depends on a preorder-traversal structure. To use the code right now, one needs to define a class that has 4 methods - `current`, `sub_terms`, `next`, and `skip`, which give the current term, its subterms, advance the preorder-traversal, and skip over a branch, respectively. This should allow it to be used with any tree-like term. There might be a better abstraction, but that's what I have right now in my prototype.

One last complication: have you had any thought of how this could be extended to an AST node containing a PermutationGroup instance determining how its arguments commute/anticommute? That could have some applications in the tensor module, but I guess it's hard or impossible to find a polynomial algorithm for that.

I'm not sure what you mean by that. Can you explain?

By the way, are you using Wild objects, or are you specifying wilds by an extra parameter?
In unify.rewriterule, you just put in two expressions, and specify which ones are variables (i.e. wilds) in another parameter. Furthermore, there is an option to put a filtering lambda function and assumptions, so that matches should be compatible with a test function and/or SymPy's new-style assumptions.

I'm using a similar method to the unification code. So far only "match-all" variables are supported - once it works it should be simple to modify the post-processing step to match on type/assumptions.

 

@Matt

Awesome, thanks for doing this.

Well, thanks to you as well. This all started with the flatterms paper you sent me, along with the (ridiculously) long list of related papers to it I found.

Another major use case is selecting the "best" match.  In this case we might also want to control the order in which matches come out of the sequence so that matches that we think are best come first.

In my ideal world I might be able to decide the order in which we traverse the tree of possible matches.  I don't know exactly how your algorithm works but, in some algorithms, we obtain a set of partial matches at each step and then have to decide which branch to pursue first.  I've found that accepting a user-provided objective function is useful.  It allows the user to specify a greedy search strategy.

The algorithm uses a discrimination net to do a "filtering" of the set of patterns, down to those that (potentially) match the given query term. At each node there are only 2 possible choices - follow the current constant symbol (if such a branch exists), or follow the variable symbol (all variables are treated as the same variable at this point). Backtracking is then used to eventually traverse all possible branches and get the full set of matches. Given that there are only two choices at each node, a user defined function would either say "follow variables first" or "follow constants first".

After a the set of matches for the term is formed, then a matching substitution is determined. For non AC patterns, determining a matchset from the pattern is trivial, and is basically "done" after the discrimination net step. For AC, linear patterns, these can be simplified slightly based on prior known information from the discrimination net step, and then fed into a general, less efficient matching/unification routine. The nonlinear, AC patterns have to go right to this step.

The thought behind this process is that most patterns will be removed by the cheap first "filtering" step, leaving only a small subset which require an expensive calculation to determine a matching substitution on.

Given the above, a user defined "greedy" algorithm could generate the full set of potential matches, and then order them based on preference before diving into the expensive generation of a matching substitution. This may be a good idea.


@ Joachim

Covered some of your points elsewhere in this post.

Is it a basic building block for other algorithms to use? Then favor
predictable performance over features. Something that has unpredictable
performance isn't very attractive to an algorithm author.

Are you aiming for something that can solve as many situations as
possible? Then aim for more features.
I'm somewhat sceptical whether just pattern matching will be the right
approach, but I suspect you aren't after this one anyway :-)

Aiming for a building block. I have my use cases for such a thing (see above), but it should be generally useful elsewhere. From what I understand, pattern matching and rewrite rules are common features in most computer algebra systems (Mathematica, maxima, etc...). The main reason for these questions is that some added space complexity, we can save some notes on the matches in the filtering step, which can then be used to provide a slight speedup in the creation of matching substitions. Or in the case of non-ac patterns, completely solve them. Doing so by default slightly slows down the determination of the set of patterns, but speeds up the creation of matching substitions.

@Richard

I don't know if your AC matcher is intended to be used for (say)  arithmetic expressions

or something else.  But if arithmetic -- your stuff also needs to deal with identities.

In that case if

you don't handle identities, your matcher becomes far less interesting.

Based on what I've read on the subject, I gather by identities you mean:

pattern = x*y*z
query =  a*b

Should match with {x: a, y: b, z: 1}, or a different permutation of that, where 1 is the identity for the mulitplication function node. Similarly 0 would be that for addition. Is that correct? I'm a mechanical engineer, not a computer scientist, so this is all a bit foreign to me.

The literature accessible to me on Associative-Commutative-Identity many-to-one pattern matching is lacking, or I'm not the best at finding it. After some thinking, the formation of matches should still work mod identities, if they are as I described above. I'm not certain that the lack of this constitutes "far less interesting", but I can see how it could be useful.

There's a long history of pattern matching "fast" including work by Richard Jenks, (Scratchpad, predecessor of Axiom).

The papers I've read have been almost exclusively from the theorem proving world. The work of Jim Christian on HIPER and Leo Bachmair on REVEAL specifically, which only cover matching mod AC. I only found one relevant paper by Jenks, and it had only 3 paragraphs on pattern matching (just describing the syntax of it in his system). I'm sure the code in macsyma/maxima would be quite useful, but being as lisp-illiterate as I am, I can't make much use of it. Thanks for the tip though.

- Jim

[Aaron Meurer]

Union and Intersection ought to be sharing a lot of code with And and
Or. At the very least they should be subclassing from LatticeOp (which
subclasses from AssocOp).

Aaron Meurer

>
>>
>> - Jim
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "sympy" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to sympy+un...@googlegroups.com.
>> To post to this group, send email to sy...@googlegroups.com.
>> Visit this group at http://groups.google.com/group/sympy.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msgid/sympy/42d9511d-e963-416f-9d4e-3e0435461422%40googlegroups.com.
>> For more options, visit https://groups.google.com/d/optout.
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sympy.
> To view this discussion on the web visit

> https://groups.google.com/d/msgid/sympy/CAJ8oX-Gf%3DQc3EURr4trzKoXnbSkc8HNf6Y02Pxd7LcTEeo_NLg%40mail.gmail.com.

[Joachim Durchholz]

Awesome.

> The papers I've read have been almost exclusively from the theorem proving
> world.

I think you should be mostly fine working off these.
Essentially it's all tree matching of some kind. Things will start to
diverge as soon as domain specifics start to matter; it would be nice to
have a not too domain-specific basic building block and add the various
strategies on top of that.

Don't worry about not being too fluent with Lisp.
You'd need full Lisp mastery to identify what parts of the code can and
should be transferred 1:1, what parts need to be adapted to Python, and
what parts simply won't work or become unmaintainable.
Actually partial knowledge of Lisp might be worse than too little
knowledge :-)

[Richard Fateman]

That is the idea.

Also pattern x*y  can match  say   cos(a),    with x=cos(a) and y=1.

or y=cos(a), x=1.

 

The literature accessible to me on Associative-Commutative-Identity many-to-one pattern matching is lacking, or I'm not the best at finding it. After some thinking, the formation of matches should still work mod identities, if they are as I described above.

Probably not without an exponential increase in cost, worst case.

 

I'm not certain that the lack of this constitutes "far less interesting", but I can see how it could be useful.

I venture to say that matching arithmetic/algebraic expressions without identities 0, 1  for plus and times

would be nearly useless.

How many patterns would you need for "quadratic in x" ?

 

There's a long history of pattern matching "fast" including work by Richard Jenks, (Scratchpad, predecessor of Axiom).

The papers I've read have been almost exclusively from the theorem proving world. The work of Jim Christian on HIPER and Leo Bachmair on REVEAL specifically, which only cover matching mod AC. I only found one relevant paper by Jenks, and it had only 3 paragraphs on pattern matching (just describing the syntax of it in his system).

wrong paper

A pattern compiler Full Text: PDF Buy this Article Author: Richard D. Jenks Published in: · Proceeding SYMSAC '76 Proceedings of the third ACM symposium on Symbolic and algebraic computation Pages 60-65  ACM New York, NY, USA ©1976  table of contents doi>10.1145/800205.806324  1976 Article   Bibliometrics · Downloads (6 Weeks): 0 · Downloads (12 Months): 35 · Downloads (cumulative): 197 · Citation Count: 2

Tools and Resources Buy this Article Recommend the ACM DL to your organization Request Permissions TOC Service:   Email   RSS Save to Binder Export Formats: BibTeX   EndNote   ACM Ref Share: Share on emailShare on facebookShare on google_plusone_shareShare on twitterShare on researchgateShare on reddit|More Sharing Services Tags: algorithms compilersscratchpad theory

 Feedback | Switch to single page view (no tabs)

Abstract

Authors

References

Cited By

Index Terms

Publication

Reviews

Comments

Table of Contents

A pattern compiler for the SCRATCHPAD system provides an efficient implementation of sets of user-defined pattern-replacement rules for symbolic mathematical computation such as tables of integrals or summation identities. Rules are compiled together, with common search paths merged and factored out and with the resulting code optimized for efficient recognition over all patterns. Matching principally involves structural comparison of expression trees and evaluation of predicates. Pattern recognizers are “fully compiled” if values of match variables can be determined by solving equations at compile time. Recognition times for several pattern matchers are compared.

..... 

I'm sure the code in macsyma/maxima would be quite useful, but being as lisp-illiterate as I am, I can't make much use of it. Thanks for the tip though.

You could read my paper on semantic patterns instead of the code.

 

- Jim

[Richard Fateman]

On Thursday, November 27, 2014 10:35:34 PM UTC-8, Joachim Durchholz wrote:

Awesome.
> The papers I've read have been almost exclusively from the theorem proving
> world.

I think you should be mostly fine working off these.

I disagree, unless you are able to find much better papers than I have seen.

 

Essentially it's all tree matching of some kind. Things will start to
diverge as soon as domain specifics start to matter; it would be nice to
have a not too domain-specific basic building block and add the various
strategies on top of that.

I think the "various strategies" are very important, and not just add-ons.

There is a pattern matching program in Peter Norvig's book on Artificial

Intelligence Programming   ;  this book will also teach you Lisp.

I highly recommend it.  In fact, I would go further than that, and say

that I would expect you to re-invent much of what he writes out,

or alternatively, have a severely deficient program.

And so you might as well read it...

[Joachim Durchholz]

Am 29.11.2014 um 02:44 schrieb Richard Fateman:
>
>
> On Thursday, November 27, 2014 10:35:34 PM UTC-8, Joachim Durchholz wrote:
>>
>> Awesome.
>>> The papers I've read have been almost exclusively from the theorem
>> proving
>>> world.
>>
>> I think you should be mostly fine working off these.
>
> I disagree, unless you are able to find much better papers than I have seen.

Well, maybe not "just fine", but simply picking up Lisp code isn't going
to work *that* well (and would be quite pointless), so what alternatives
would be there?

>> Essentially it's all tree matching of some kind. Things will start to
>> diverge as soon as domain specifics start to matter; it would be nice to
>> have a not too domain-specific basic building block and add the various
>> strategies on top of that.
>
> I think the "various strategies" are very important, and not just add-ons.

Of course they are important.
It would still be nice to be able to use different strategies, depending
on what the particular algorithm tries to do, and on experiences with
speed and maintainability of Python code.

> There is a pattern matching program in Peter Norvig's book on Artificial
> Intelligence Programming ; this book will also teach you Lisp.

I agree that learning Lisp is a good idea. I'd recommend complementing
that with Haskell (e.g. "The Haskell School of Expression", though it's
a bit superficial), and http://www.info.ucl.ac.be/~pvr/book.html to see
what else is out there.

However, that's about learning programming. Which is a good thing to do
in general, but it does not really help with designing Python classes
for SymPy.

For that, firstly, you'd need to understand what exactly each design
decision in Peter's (or anybody else's) code was intended to achieve.
For that, merely learning Lisp is not enough, you need to have mastered
it - which is a few years of experience away for most of us (except for
you, I assume, and maybe the odd one or two lurkers on this list).

Second, you need to understand all about how to design the equivalents
in Python, dropping those design patterns that don't work in Python, and
replacing them with something that works as well. (For example,
everything macro would have to be replaced or redone; is there anything
relevant left if you take out macros in the useful Lisp work?) So you
need to be a Python master as well. Given your record I doubt that you
are, I certainly am not, and those people around here that I'd consider
Python masters, I doubt that any of them is also a Lisp master.

Third, the resulting code needs to be maintainable by people who do not
know anything about Lisp, and barely enough of Python to become a GSoC
student.
I have serious doubts that Lisp style is going to work for that, at all,
even if you let a Lisp And Python Master do the translation.

So right now, my point of view is that trying to get that (doubtlessly
very valuable) Lisp experience into SymPy, while it could do all kinds
of good, is probably not practically possible.
Unless somebody can delineate a clear path to overcame the various
obstacles I just enumerated.

> I highly recommend it. In fact, I would go further than that, and say
> that I would expect you to re-invent much of what he writes out,
> or alternatively, have a severely deficient program.

Sure, but if his book makes you learn Lisp, the presentation is heavily
biased towards Lisp, and much of what he writes won't be transferrable.

My recommendation would be to reinvent first (and discover how the
Python patterns for that particular field work), then read the Lisp
equivalents, then transfuse the ideas.
The point being that once enough experience with the Python patterns is
available, it's easier to see what to transfer and what to better leave
untransferred.

YMMV :-)

Regards,
Jo

[Aaron Meurer]

I agree this is important. For instance, if the ODE solver tries to match a*f(x).diff(x, x) + b*f(x).diff(x) + c*f(x) + d, where a, b, c, and d are wild symbols that should be independent of f(x), it should work even if a, b, c, or d are 1 or 0. I suspect getting them to match 1 is not difficult (a simple way if you can already make a*b match x*y*z with a = x*y and b = z, just treat every Mul as if it had extra 1s in it, one for each wild in the pattern).  I'm guessing making a*x match 0 with a = 0 is a bit more difficult, unless there is some other "trick" to make it work. 

Another question is, how can you teach the pattern matcher that a function maps to an identity, like cos(a)*x can match x with a = 0, or x**a*y can match y with a = 0?

Getting these "trivial" matching cases to work is very important. Otherwise, you have to write code that checks them all manually, which sort of defeats the purpose of using the pattern matcher. 

Aaron Meurer

 

--
You received this message because you are subscribed to the Google Groups "sympy" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sympy+un...@googlegroups.com.
To post to this group, send email to sy...@googlegroups.com.
Visit this group at http://groups.google.com/group/sympy.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/345a4a58-a44f-48a4-8f8e-64b920c1d65e%40googlegroups.com.

[James Crist]

@Richard,

Thanks for the Jenks paper, that was a good read. I also read your paper on semantic matching http://dl.acm.org.ezp2.lib.umn.edu/citation.cfm?id=806300, which only detailed the use of matching in Macsyma, and not its underlying workings. I failed to find anything on how it actually worked under the hood.

@Aaron

The Axiom system assumes variables shouldn't be identities, unless noted that they can be. Otherwise you may match patterns that you'd rather not. For example, given the set of patterns:

T = {a*x**2 + b*x + c, cos(x)}

where a, b, c, and x are variables. Both patterns will match cos(d) (the quadratic matches on {a: 0, b: 0, x: whatever, c: cos(d)}). The user probably only wants the second one to match. Assuming all variables are allowed to be 1 or 0 by default results in a combinatorially large number of potential matches.

The way the Axiom system does this is that if a variable is allowed to be an identity (1 or 0), additional patterns with the variable at these values are generated, and added to the ruleset. So specifying `cos(x)*a`, with x allowed to go to identity creates 2 patterns: {cos(x)*a, a}. This wouldn't be needed for simple cases, but for things like matching cos(x)*a -> a with {x: 1} this would be necessary.

I'm not certain how this system will be used in SymPy. Will there be multiple, small rulesets (a set of trig rules, a set of log rules, etc...), or will there be some giant ruleset? With the net structure I'm using, the cost of more rules in a ruleset is small (~none for non-AC patterns), but it does exist.

- Jim Crist

--
You received this message because you are subscribed to a topic in the Google Groups "sympy" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/sympy/-7lyMkiB5SY/unsubscribe.
To unsubscribe from this group and all its topics, send an email to sympy+un...@googlegroups.com.

To post to this group, send email to sy...@googlegroups.com.
Visit this group at http://groups.google.com/group/sympy.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAKgW%3D6LQqOTcs500bg6_RZFJkZEdGAObXmi01QKAHSO7nxs4gg%40mail.gmail.com.

[James Crist]

The system described in the Jenks paper would work better than what I've written if we plan to use relatively small sets of small patterns. Larger patterns, or larger rulesets will work better with what I'm writing, (I think), as they will have more potential paths, and generating specialized predicates for each path will get increasingly expensive.

[Joachim Durchholz]

Am 29.11.2014 um 18:52 schrieb James Crist:
> The system described in the Jenks paper would work better than what I've
> written if we plan to use relatively small sets of small patterns. Larger
> patterns, or larger rulesets will work better with what I'm writing, (I
> think), as they will have more potential paths, and generating specialized
> predicates for each path will get increasingly expensive.

If you're after how a "standard" set of patterns might look like, Rubi
might be a good start.
See http://www.apmaths.uwo.ca/~arich/ .

It's several thousand rules.
IIRC, they have been carefully constructed to be non-overlapping (you
can only apply a single rule at any time), so they might be "too easy"
to really test the algorithm's design.

[Matthew Rocklin]

Matching against identities can be valuable.  Writing out several variations for a intended single pattern feels like a hack.

Or at least, that was my experience with my matrix expressions system.  I wasn't able to cleanly add in identities so I shoved in lots more patterns.  Things worked.

The prototype, written in Maude, supported identities.  I found this pleasant (though reimplementing Maude seems hard).

--
You received this message because you are subscribed to the Google Groups "sympy" group.

To unsubscribe from this group and stop receiving emails from it, send an email to sympy+unsubscribe@googlegroups.com.

To post to this group, send email to sy...@googlegroups.com.
Visit this group at http://groups.google.com/group/sympy.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/547A4F57.6050902%40durchholz.org.

[Richard Fateman]

Sorry to be argumentative, but Norvig's book is teaching about how one

can go about solving certain problems common in "symbolic" artificial

intelligence, and that is relevant in any language.  The book probably

shows you how some of these ideas are more neatly encapsulated in

Lisp than some other languages,  but Python should not be so far off

in terms of complexity of code and expressiveness.  (Exceptions --

I don't know -- maybe the occasional use of first-class functions, or the

tiny use of macros for essentially abbreviating code segments. )

 

For that, firstly, you'd need to understand what exactly each design
decision in Peter's (or anybody else's) code was intended to achieve.

I think the book is pretty clear about that.

 

For that, merely learning Lisp is not enough, you need to have mastered
it - which is a few years of experience away for most of us (except for
you, I assume, and maybe the odd one or two lurkers on this list).

You do not need to master Lisp at the expense of years.  I have taught

undergrad classes where students get up to the level of Lisp in Norvig's

book after 3 assignments (writing pieces of a compiler for a language

like Java--  ). 

Second, you need to understand all about how to design the equivalents
in Python, dropping those design patterns that don't work in Python, and
replacing them with something that works as well.

This is unconvincing to me.  Norvig has written a cheat sheet for Lisp <--> Python.

 

(For example,
everything macro would have to be replaced or redone; is there anything
relevant left if you take out macros in the useful Lisp work?)

This is a boogie-man often thrown up as a barrier to understanding Lisp.

It isn't.

1. Macros are generally rare and easy to understand.

2. If they are not, it is probably a crappy unnecessary use of macros,

written by a naive programmer.  

3. Look at Norvig's book and see how often he uses macros. Rarely.

And see how long they are.  (2 lines?)

 

So you
need to be a Python master as well. Given your record I doubt that you
are, I certainly am not, and those people around here that I'd consider
Python masters, I doubt that any of them is also a Lisp master.

I am definitely not a Python master. 

 

Third, the resulting code needs to be maintainable by people who do not
know anything about Lisp, and barely enough of Python to become a GSoC
student.

This is a real problem.  If you have unskilled and unknowledgeable personnel

"maintaining" a code base, that's a tragedy in the works.  It means that someone

who is skilled and knowledgeable will have to go over the code and fix it.

 

I have serious doubts that Lisp style is going to work for that, at all,
even if you let a Lisp And Python Master do the translation.

I think that Lisp style is highly variable, and that someone used to writing

in Python, writes Python-Lisp, etc etc.

Can someone take Lisp and rewrite in Python "automatically"?  I think it

depends on the proclivities of the original programmer.   

You (and others) seem to think that Lisp programmers always use macros

and so it can't be done.  But you are wrong in that belief.

I suppose I could write programs that are challenging to understand and

to translate;  I understand Python is lacking functional objects with more

than one argument;  I could write stuff relying on multiprocessing which

presumably would differ.  But that's not run-of-the-mill.

So right now, my point of view is that trying to get that (doubtlessly
very valuable) Lisp experience into SymPy, while it could do all kinds
of good, is probably not practically possible.

All I can say is, try to read Norvig's book.  My sincere belief is that

even if you never write a single line of Lisp, it will improve your programming

in Python, because you will think about problems  (like pattern matching)

more clearly.

 

Unless somebody can delineate a clear path to overcame the various
obstacles I just enumerated.

> I highly recommend it.  In fact, I would go further than that, and say
> that I would expect you to re-invent much of what he writes out,
> or alternatively, have a severely deficient program.

Sure, but if his book makes you learn Lisp, the presentation is heavily
biased towards Lisp, and much of what he writes won't be transferrable.

Totally disagree.

 

My recommendation would be to reinvent first (and discover how the
Python patterns for that particular field work), then read the Lisp
equivalents, then transfuse the ideas.
The point being that once enough experience with the Python patterns is
available, it's easier to see what to transfer and what to better leave
untransferred.

There is an old saying,  2 weeks in the computer lab can save 1 hour in the library.

RJF 

YMMV :-)

Regards,
Jo

[Richard Fateman]

On Saturday, November 29, 2014 8:29:56 AM UTC-8, Aaron Meurer wrote:

<big snip>

 

. 

Another question is, how can you teach the pattern matcher that a function maps to an identity, like cos(a)*x can match x with a = 0, or x**a*y can match y with a = 0?

You can do this (trivially)  but no one does because it is too  expensive.  Simpler case

x is a pattern variable.

pattern is  f(x+1)

expression is f(4)

method.  f matches. Now to match x+1 to 4,  you call your solve program, and find out that x=3.

So "all" you need is solve.

Your example requires solving cos(a)=1 for a.  Unfortunately there are an infinite number of solutions, not just a=0.

<snip> 

[Richard Fateman]

Actually, my pattern matcher in Maxima DOES some "solving"... in particular the example I gave..

matchdeclare(a,true);

defrule(r1,f(a+1), g(a));

r1(f(4))  returns g(3)

but it only solves simple linear forms.

I think the lisp code for my matcher is fairly clear.  matcom.lisp  is the match "compiler" and matrun.lisp  is its

"runtime" support.

RJF

[Joachim Durchholz]

Am 30.11.2014 um 06:53 schrieb Richard Fateman:
>
> Sorry to be argumentative, but Norvig's book is teaching about how one
> can go about solving certain problems common in "symbolic" artificial
> intelligence, and that is relevant in any language.

Agreed.

> The book probably
> shows you how some of these ideas are more neatly encapsulated in
> Lisp than some other languages, but Python should not be so far off
> in terms of complexity of code and expressiveness. (Exceptions --
> I don't know -- maybe the occasional use of first-class functions, or the
> tiny use of macros for essentially abbreviating code segments. )

First-class functions are easy in Python (easier than in C/C++).

What you can't do easily is macros. There's a "lambda" construct but
it's a bit too clunkly to be useful for the small helpful things, so if
you can't do it in a function it's no more good Python design.

Partial evaluation isn't doable at all.

>> For that, firstly, you'd need to understand what exactly each design
>> decision in Peter's (or anybody else's) code was intended to achieve.
>
> I think the book is pretty clear about that.

That would make it a more valuable read then.
Though it's very easy to overlook implicit assumptions, particularly if
both author and reader share them. I suspect strongly that both Peter
and you "think in Lisp", and that there's a real risk that a reader of
the book will miss these assumptions as well.

>> For that, merely learning Lisp is not enough, you need to have mastered
>> it - which is a few years of experience away for most of us (except for
>> you, I assume, and maybe the odd one or two lurkers on this list).
>
> You do not need to master Lisp at the expense of years. I have taught
> undergrad classes where students get up to the level of Lisp in Norvig's
> book after 3 assignments (writing pieces of a compiler for a language
> like Java-- ).

I tend to disagree.
You can do working code with less than mastership, true. That's what all
the CS grads (Yours Truly included) did at university. However, creating
a framework that does not paint us into some corner without us even
noticing it - now that's an entirely different thing.

Let me put up an analogy: What I fear is that the Lisp patterns
presented are a shiny, working, elegant racing car. However, when doing
it in Python, the best design might be an SUV because the track is a bit
rougher, and we'd end up with something with a really good engine but it
would be difficult to put that power to actual use.
Like all analogies, this is going to break down at some point, so I
don't want to elaborate further. The general point is: I know from
several decades of experience that the value in each design lies in its
trade-offs. Things that are irrelevant or invisible to the designer tend
to degrade, or get lost entirely. A design honed to 100% perfection is
also 100% specialized, and usually nontransferrable; it's

>> Second, you need to understand all about how to design the equivalents
>> in Python, dropping those design patterns that don't work in Python, and
>> replacing them with something that works as well.
>
> This is unconvincing to me. Norvig has written a cheat sheet for Lisp <-->
> Python.

That cheat sheet is really good, I just read it and even took away some
things (being at a low Lisp and intermediate Python level).

Still... his use of Python is purely pedagogical, framework design
mastership is a different skill.
In fact he marks something in read as a Python misfeature that isn't (if
an assertion message should be the just the tested expression, simply
omit the message, it will get printed as part of the stack trace).

The salient point here is that Peter shows an excellent grasp of
Python-in-the-small, but what we're doing here is the design groundwork
for core features in the next iteration of SymPy (and hopefully more
iterations).

>> (For example,
>> everything macro would have to be replaced or redone; is there anything
>> relevant left if you take out macros in the useful Lisp work?)
>
> This is a boogie-man often thrown up as a barrier to understanding Lisp.
> It isn't.
> 1. Macros are generally rare and easy to understand.

The salient point being "generally" here.
I had several instances of MEGO trying to understand why the CL standard
library did what it does. (Particularly the parts that enable multiple
dispatch - those facilities made me think of a toolbox full of loaded
and unlocked guns.)

Also, you need to be 150% clear about the semantics of quote. I found it
extremely hard to deal with that - the theory was easy enough, yet in
practice I found myself tripping over it at every other opportunity, and
it didn't get better with practice.

> 2. If they are not, it is probably a crappy unnecessary use of macros,
> written by a naive programmer.

:-)

> 3. Look at Norvig's book and see how often he uses macros. Rarely.
> And see how long they are. (2 lines?)

I'm unconcerned about Peter's use of macros.
What I'm concerned about is the code that they replace, and how good
that code could be abstracted out on the Python side. What kind of
design we'd need, whether it would fit with the rest of the design. What
I fear most is a downhill creep in quality - each time you build a
workaround for a macro you can't do in Python, you lose just a small
amount of design quality, but if you have a dozen macros, the overall
design could have become so bad it's unusable.

>> Third, the resulting code needs to be maintainable by people who do not
>> know anything about Lisp, and barely enough of Python to become a GSoC
>> student.
>
> This is a real problem. If you have unskilled and unknowledgeable personnel
> "maintaining" a code base, that's a tragedy in the works. It means that
> someone
> who is skilled and knowledgeable will have to go over the code and fix it.

Fortunately, the unskilled people who do not become skilled tend to go
away in a volunteer project.
It's still something to look out for. Some of our codebase has become
unmaintainable already (I'm looking at you, runtests.py - though that
specific file does not suffer from design problems but from too many
feature additions and too little refactoring).

> I suppose I could write programs that are challenging to understand and
> to translate; I understand Python is lacking functional objects with more
> than one argument;

Actually that's not the case.

> I could write stuff relying on multiprocessing which
> presumably would differ. But that's not run-of-the-mill.

Agreed.

>> So right now, my point of view is that trying to get that (doubtlessly
>> very valuable) Lisp experience into SymPy, while it could do all kinds
>> of good, is probably not practically possible.
>
> All I can say is, try to read Norvig's book. My sincere belief is that
> even if you never write a single line of Lisp, it will improve your
> programming
> in Python, because you will think about problems (like pattern matching)
> more clearly.

Quite possible.
My suggestion would be to try one's hand, then read Peter's book, then
integrate the new ideas.
YMMV.

>> Sure, but if his book makes you learn Lisp, the presentation is heavily
>> biased towards Lisp, and much of what he writes won't be transferrable.
>>
> Totally disagree.

I can imagine.
Let me say the more it makes you learn Lisp, the less it's probably
going to be useful if you don't do Lisp. Maybe I was overestimating how
much it makes you learn Lisp - a dose of Lisp is certainly useful, the
full Kool-Aid can become a liability (due to overspecialization, and
because Kool-Aid is generally problematic unless you can switch entirely).

> There is an old saying, 2 weeks in the computer lab can save 1 hour in
> the library.

True when learning tried-and-true issues.
False when it comes to trying and judging whether it's true.

We can certainly benefit from algorithms.
Less so from "doing things the Lisp way" if we're working in Python.
The problem is that separating algorithms from "the Lisp way" isn't
always easy. And an important part of writing a framework in programming
language X is "doing it the X way" (says he who has participated in such
projects for multiple values of X).

Regards,
Jo

[Brian Granger]

Awesome! That is one of the missing pieces for sympy for sure!

I would definitely have a look at the pattern matching of Mathematica,
to see what kinds of things are useful and needed for that type of
thing.

Cheers,

Brian

On Wed, Nov 26, 2014 at 3:19 PM, James Crist <cris...@umn.edu> wrote:

> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an

> email to sympy+un...@googlegroups.com.

> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sympy.
> To view this discussion on the web visit

> https://groups.google.com/d/msgid/sympy/42d9511d-e963-416f-9d4e-3e0435461422%40googlegroups.com.

> For more options, visit https://groups.google.com/d/optout.

--
Brian E. Granger
Cal Poly State University, San Luis Obispo
@ellisonbg on Twitter and GitHub
bgra...@calpoly.edu and elli...@gmail.com

[Richard Fateman]

On Sunday, November 30, 2014 1:52:08 AM UTC-8, Joachim Durchholz wrote:

Am 30.11.2014 um 06:53 schrieb Richard Fateman:

First-class functions are easy in Python (easier than in C/C++).

OK, I thought I read somewhere about some limitations. 

What you can't do easily is macros. There's a "lambda" construct but
it's a bit too clunkly to be useful for the small helpful things, so if
you can't do it in a function it's no more good Python design.

I just don't understand this emphasis on the difficulty of macros.

Some people are happy to run their source code through a macro processor

like M6, just for the fun of it.  But I don't think that is at all necessary. 

Partial evaluation isn't doable at all.

I don't know what you mean by partial evaluation.  Is this something you

think that Lisp does?  Maybe confused about quote?

(+ 3 4)   evaluates to 7

'(+ 3 4) evaluates to a lisp list of 3 items, + , 3, 4 .      Is that what you mean?

That's not really what Norvig does.  Quite the contrary.  His programs are

a minimal framework to exhibit the performance that he wants to demonstrate,

for the most part.

Thus he has a chapter that shows how to do integration of symbolic expressions,

but it can be accused of being just a hack ...  no Risch algorithm etc.

Similarly for natural language understanding.  etc.

Doing a full-fledged efficient version of these would require much more

work. 

I give up.  If you are convinced that macros are a problem, then to you they

are a problem. 

The salient point being "generally" here.
I had several instances of MEGO trying to understand why the CL standard
library did what it does. (Particularly the parts that enable multiple
dispatch - those facilities made me think of a toolbox full of loaded
and unlocked guns.)

Also, you need to be 150% clear about the semantics of quote. I found it
extremely hard to deal with that - the theory was easy enough, yet in
practice I found myself tripping over it at every other opportunity, and
it didn't get better with practice.

I find this surprising.  You can read (in Norvig's book) a program that is

the Lisp evaluator  (actually, Scheme).  It shows what quote means.

If I recall correctly, Scheme originally did not have macros.  Maybe

still doesn't, just as an "extension".

  

> 2. If they are not, it is probably a crappy unnecessary use of macros,
> written by a naive programmer.

:-)

> 3. Look at Norvig's book and see how often he uses macros. Rarely.
> And see how long they are.  (2 lines?)

I'm unconcerned about Peter's use of macros.
What I'm concerned about is the code that they replace, and how good
that code could be abstracted out on the Python side.

Each time a piece of macro code is used in a Lisp program one can

replace it with a piece of regular code.  In fact that is exactly what macro

expansion does.  Presumably Python programmers could do the same

by hand.

 

What kind of
design we'd need, whether it would fit with the rest of the design. What
I fear most is a downhill creep in quality - each time you build a
workaround for a macro you can't do in Python, you lose just a small
amount of design quality, but if you have a dozen macros, the overall
design could have become so bad it's unusable.

Again, you assume that a lisp program is a tangle of macros. 

>> Third, the resulting code needs to be maintainable by people who do not
>> know anything about Lisp, and barely enough of Python to become a GSoC
>> student.
>
> This is a real problem.  If you have unskilled and unknowledgeable personnel
> "maintaining" a code base, that's a tragedy in the works.  It means that
> someone
> who is skilled and knowledgeable will have to go over the code and fix it.

Fortunately, the unskilled people who do not become skilled tend to go
away in a volunteer project.
It's still something to look out for. Some of our codebase has become
unmaintainable already (I'm looking at you, runtests.py - though that
specific file does not suffer from design problems but from too many
feature additions and too little refactoring).

I don't know about sympy code base, but I think the general belief in

my (computer science) department is that programs written by students

must be reworked by others before it is ready for prime-time (95%).

distribution outside our department.

 

> I suppose I could write programs that are challenging to understand and
> to translate;  I understand Python is lacking functional objects with more
> than one argument;

Actually that's not the case.

 > I could write stuff relying on multiprocessing which
> presumably would differ.  But that's not run-of-the-mill.

Agreed.

>> So right now, my point of view is that trying to get that (doubtlessly
>> very valuable) Lisp experience into SymPy, while it could do all kinds
>> of good, is probably not practically possible.

>
> All I can say is, try to read Norvig's book.  My sincere belief is that
> even if you never write a single line of Lisp, it will improve your
> programming
> in Python, because you will think about problems  (like pattern matching)
> more clearly.

Quite possible.
My suggestion would be to try one's hand, then read Peter's book, then
integrate the new ideas.
YMMV.

Well, I could repeat myself. 

>> Sure, but if his book makes you learn Lisp, the presentation is heavily
>> biased towards Lisp, and much of what he writes won't be transferrable.
>>
> Totally disagree.

I can imagine.
Let me say the more it makes you learn Lisp, the less it's probably
going to be useful if you don't do Lisp. Maybe I was overestimating how
much it makes you learn Lisp - a dose of Lisp is certainly useful, the
full Kool-Aid can become a liability (due to overspecialization, and
because Kool-Aid is generally problematic unless you can switch entirely).

> There is an old saying,  2 weeks in the computer lab can save 1 hour in
> the library.

True when learning tried-and-true issues.
False when it comes to trying and judging whether it's true.

I think that pattern matching is pretty well understood by some people.

 

We can certainly benefit from algorithms.
Less so from "doing things the Lisp way" if we're working in Python.
The problem is that separating algorithms from "the Lisp way" isn't
always easy. And an important part of writing a framework in programming
language X is "doing it the X way" (says he who has participated in such
projects for multiple values of X).

I think that writing programs in Lisp does not define 'a way' because there

are generally many ways of accomplishing the same task using different

"paradigms" ... e.g. functional, imperative, ... whereas it seems to me

that Python is supposed to have one way to do each thing.  (true?).

So maybe a lisp program that is heavily "functional programming" style

is hard to do in Python ?  But you insist that Python supports this,

so I don't know.

RJf

 

Regards,
Jo

[Joachim Durchholz]

Am 30.11.2014 um 20:18 schrieb Richard Fateman:
> I just don't understand this emphasis on the difficulty of macros.

Issue is that tools don't know about these preprocessors.
This affects IDEs when finding the definition of a name, or when
refactoring; also stack traces tend to not reflect what's in the file.

I have no problems with macros actually, it's just that going outside of
typical language usage means you lose a lot of infrastructure and tool
support.

> Some people are happy to run their source code through a macro processor
> like M6, just for the fun of it. But I don't think that is at all
> necessary.

Well, for fun experiments rarely go beyond three digits in LoC, so these
people never hit the actual problems.

>> Partial evaluation isn't doable at all.
>>
> I don't know what you mean by partial evaluation.

Difference between lazy and eager evaluation.

> Is this something you
> think that Lisp does? Maybe confused about quote?

Quote is Lisp's way of deferring evaluation, yes.
Well, sort of, unevaluated expressions are also lists.

>> Let me put up an analogy: What I fear is that the Lisp patterns
>> presented are a shiny, working, elegant racing car. However, when doing
>> it in Python, the best design might be an SUV because the track is a bit
>> rougher, and we'd end up with something with a really good engine but it
>> would be difficult to put that power to actual use.
>
> That's not really what Norvig does. Quite the contrary. His programs are
> a minimal framework to exhibit the performance that he wants to demonstrate,
> for the most part.

I'll leave that to the people who actually try his recipes out.

>> Also, you need to be 150% clear about the semantics of quote. I found it
>> extremely hard to deal with that - the theory was easy enough, yet in
>> practice I found myself tripping over it at every other opportunity, and
>> it didn't get better with practice.
>
> I find this surprising.

I can imagine.

> You can read (in Norvig's book) a program that is
> the Lisp evaluator (actually, Scheme).

Ah, that reminds me of my first real schooltime programming project.
Which happened to be a minimal Lisp interpreter :-)

> It shows what quote means.

As I said, I know fully well what quote means.
It's just that practical use somehow didn't work out. I kept quoting
stuff that shouldn't be quoted, and vice versa. Maybe I was too young
and didn't think clearly enough about them, maybe I have some thinking
defect that makes them hard on me, maybe I have a tendency to approaches
that simply do not work well for Lisp. Maybe the manuals I was using
simply didn't make clear enough which functions would unquote which
argument.
Frankly, I don't know - but I found it extremely refreshing that
Haskell, being all lazy evaluation, does not have this distinction :-)

Oh, Haskell does not need macros either. I think that's because lazy
evaluation means there is no difference between quoted and nonquoted,
but I can't be 100% sure about that.

> If I recall correctly, Scheme originally did not have macros. Maybe
> still doesn't, just as an "extension".

I'd be quite surprised if it didn't.
But then I haven't been following Scheme or CL in the past decade. Not
too closely anyway, I guess things have developed a bit in that time.

>>> 2. If they are not, it is probably a crappy unnecessary use of macros,
>>> written by a naive programmer.
>>
>> :-)
>>
>>> 3. Look at Norvig's book and see how often he uses macros. Rarely.
>>> And see how long they are. (2 lines?)
>>
>> I'm unconcerned about Peter's use of macros.
>> What I'm concerned about is the code that they replace, and how good
>> that code could be abstracted out on the Python side.
>
> Each time a piece of macro code is used in a Lisp program one can
> replace it with a piece of regular code. In fact that is exactly what macro
> expansion does.

Ah, but the point is that it is *not* the same, as then there would be
not reason to use a macro in the first place, right?

> Presumably Python programmers could do the same by hand.

Unless the code becomes too clunky that way.
Which is what I suspect will happen - unless Peter's macro usage is
really that superficial that it doesn't matter.

I guess that's something to check when applying that book's lessons to
Python.

>> What kind of
>> design we'd need, whether it would fit with the rest of the design. What
>> I fear most is a downhill creep in quality - each time you build a
>> workaround for a macro you can't do in Python, you lose just a small
>> amount of design quality, but if you have a dozen macros, the overall
>> design could have become so bad it's unusable.
>
> Again, you assume that a lisp program is a tangle of macros.

No, I'm assuming that Peter's code is at least a dozen macros.
And I fear that inlining all these macros might make the design too
clunky to work with - though as I said, if his macro usage is slight
then it might be a non-issue.
I do know it's very easy to overlook how much a macro changes. I have
done some experimenting with manual inlining of functions, and a
combination of innocuously-looking functions could become a tangled
mess, very quickly.

I'll leave that issue to real experimenting though, I do not think we
can find out more by arguing on a what-if basis.

>> Fortunately, the unskilled people who do not become skilled tend to go
>> away in a volunteer project.
>> It's still something to look out for. Some of our codebase has become
>> unmaintainable already (I'm looking at you, runtests.py - though that
>> specific file does not suffer from design problems but from too many
>> feature additions and too little refactoring).
>
> I don't know about sympy code base, but I think the general belief in
> my (computer science) department is that programs written by students
> must be reworked by others before it is ready for prime-time (95%).
> distribution outside our department.

The code base could certainly use some work, but I have seen worse
written by supposedly-senior programmers.

>> We can certainly benefit from algorithms.
>> Less so from "doing things the Lisp way" if we're working in Python.
>> The problem is that separating algorithms from "the Lisp way" isn't
>> always easy. And an important part of writing a framework in programming
>> language X is "doing it the X way" (says he who has participated in such
>> projects for multiple values of X).
>
> I think that writing programs in Lisp does not define 'a way' because there
> are generally many ways of accomplishing the same task using different
> "paradigms" ... e.g. functional, imperative, ... whereas it seems to me
> that Python is supposed to have one way to do each thing. (true?).

This is in fact Python philosophy, but it applies just to language
features, not API design.
Actually I'd be very surprised if any language design could enforce a
"one way to do each thing" paradigm at the API level, programmer jokes
like Intercal aside.

> So maybe a lisp program that is heavily "functional programming" style
> is hard to do in Python ? But you insist that Python supports this,
> so I don't know.

Python is functional all right, in the litmus test sense "can it
construct new functions at runtime".
However, to make the functional aspect clean and matter-of-fact, closure
construction needs to be easy and free of clunkiness, and Python
requires an extra "lambda" keyword, naming all parameters (instead of
just leaving them unbound variables), and an extra colon; it's not too
bad but I suspect nobody is going to build a monad transformer library
in Python, simply because that pattern would become so clunky that it's
useless. (A bit like the situation of template-based functional
programming in C++: Yes it can be done, but it's too ugly to live.)

[Aaron Meurer]

I guess solve() would do it, although this has the potential to make
the pattern matcher very slow, and also make it return results that
are all but useless (e.g., I wouldn't want the pattern matcher to
return the cubic formula because it technically makes the pattern
match some expression that looks nothing like a cubic).

There's another related point that should be brought up here, which is
that you should make a clear separation early on in the pattern
matcher between the pure structural matching and the different levels
of "mathematical" matching.

My main experience with the pattern matcher in SymPy is with dsolve(),
which basically works by matching the input ODE to a pattern and
plugging the values into a solution. For example, a first-order linear
ODE looks like f(x).diff(x) + P(x)*f(x) + Q(x), and the solution is an
expression that contains P(x) and Q(x) (there are a few solving
algorithms which are a bit more complicated than that, but they still
require pattern matching).

The main issue here is getting the input expression to "look" like the
pattern. This is currently done with preprocessing (mainly collect(),
because f(x) + x*f(x) won't match a*f(x) but (1 + x)*f(x) will). The
preprocessing is done manually and is hard-coded for each ODE (for
instance https://github.com/sympy/sympy/blob/e6fc53f27ee872b27bc79b96529fc4bf34d4f023/sympy/solvers/ode.py#L928-L929).

The most complicated example here is the separable ODE (any ODE that
can be written as dy/dx = P(y)*Q(x)). The separatevars() function was
written entirely for the purpose of handling all the possible ways an
expression can be split into a product with separated variables.

The point here, though, is that this would be useful, from an API
point of view, if this could be done automatically, at least to some
degree. In other words I should be able to just write a pattern like
a*x**2 + b*x + c and it should match things like y*x**2 + x**2 + 2*x -
1. But it should be implemented in a completely separate layer, so
that it is used only if explicitly needed. Otherwise, it will
unnecessarily slow down the pattern matching that doesn't need it, and
will make the matching code too complicated to maintain.

Aaron Meurer

> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sympy.
> To view this discussion on the web visit

> https://groups.google.com/d/msgid/sympy/36c7ae5f-3475-4c5e-b399-6a84c2703919%40googlegroups.com.

[Richard Fateman]

On Sunday, November 30, 2014 12:30:02 PM UTC-8, Joachim Durchholz wrote:

.... snip... 

>> Partial evaluation isn't doable at all.
>>
> I don't know what you mean by partial evaluation.

Difference between lazy and eager evaluation.

 > Is this something you
> think that Lisp does?  Maybe confused about quote?

Quote is Lisp's way of deferring evaluation, yes.
Well, sort of, unevaluated expressions are also lists.

 I don't think of quote that way at all.  '(a b c d) builds a list structure with

4 elements in it.  It does not mean there is a function named "a"  that is

going to be applied at some future time.  Maybe there is such a function

and you might later write  (eval s)  where s is (a b c d) but that is

highly unlikely.  Calls to eval are extremely rare.  There are hundreds of

thousands of lines of Lisp in Maxima.  I would be surprised if eval was

used even once.

There is also the thorny question of the environment to be used for evaluation.

e.g.

  what is to be done in

(let ((a '+)

       (b 43))

 (eval s) )

does a, b, have bindings from when one did (setq s '(a b c d))?

or the new lexical bindings.

Anyway, people don't use eval, and so a quoted expression 

is almost never a program, deferred.   The exception is in

macros, which construct a program, which is then inserted into

a program (where it is evaluated). 

Then the context is the one in which the macro is expanded.

Most people do not define macros, but it seems you were

burned by this or the possibility of doing this..

RJF

 

[Joachim Durchholz]

Am 01.12.2014 um 23:25 schrieb Richard Fateman:
> There is also the thorny question of the environment to be used for
> evaluation.
> e.g.
> what is to be done in
>
> (let ((a '+)
> (b 43))
> (eval s) )
>
> does a, b, have bindings from when one did (setq s '(a b c d))?
> or the new lexical bindings.

IIRC early Lisps used the new ones (Interlisp certainly did, it made my
code somewhat brittle and me quite unhappy).
If memory serves me right, Scheme took one decision and CL the other.

To the language design community, it's not a thorny question anymore,
the consensus there is that it should be the original environment. And
that you shouldn't use a lexical approach such as quoting anyway.
I agree with that stance, but then no language can redo its design at
such a core level. (That's why I'm so cautious about taking designs from
Lisp: IMO, macros are not the way to go for other languages, and
macro-based designs might be more dependent on that concept than its
users and proponents are aware.)

> Anyway, people don't use eval, and so a quoted expression
> is almost never a program, deferred.

Ah. I wasn't aware of this.
Though I can see how attractive anything would be if your main
metaprogramming tool is quote&eval, so I now understand why macros are
so important.

> The exception is in
> macros, which construct a program, which is then inserted into
> a program (where it is evaluated).
> Then the context is the one in which the macro is expanded.
> Most people do not define macros, but it seems you were
> burned by this or the possibility of doing this..

Not by macros, Interlisp didn't have these :-)
But certainly by quote&eval.

Regards,
Jo