Home › Blogs › John Fredsted's blog

Expression trees

John Fredsted's picture
Posted on 2007-11-12 10:18 By John Fredsted (Maple Rating 4 566)
Categories:

Note added: As correctly pointed out by Joe Riel in his post below, my function fromTree fails doing what it is supposed to do for expressions which contain lists and/or sets. For a version of fromTree which behaves properly (I believe) also for expressions containing lists and/or sets, see my post below.

Consider the following two functions:

toTree   := x -> `if`(op(x) = x,x,[op(0,x),map(toTree,[op(x)])[]]):
fromTree := x -> `if`(op(x) = x,x,x[1](seq(fromTree(x[i]),i=2..nops(x)))):

They can be used to transform between an expression itself and its equivalent expression tree (here implemented as nested lists). Among other things, this functionality is useful for gaining some insight into the way Maple internally represent various expressions. Some examples:

1. The complex imaginary unit:

> toTree(I);
                          [Complex, 1]

This shows that internally to Maple the complex imaginary unit I is implemented as

> Complex(1);
                               I

2. A general complex number:

> tree := toTree(a + I*b);
              tree := [+, a, [*, [Complex, 1], b]]

This tree may be translated back to the original complex number:

> fromTree(tree);
                            a + I b

3. An unsolvable integral:

> expr := int(exp(cos(x)),x):
> tree := toTree(expr);
> fromTree(tree);
               tree := [int, [exp, [cos, x]], x]
                      int(exp(cos(x)), x)

4. A 'solvable' integral (quite complicated, just for the fun of it):

expr := int(exp(x^3),x):
tree := toTree(expr);
fromTree(tree);

tree := [`*`, [Fraction, -1, 3], [`^`, -1, [Fraction, 2, 3]], [`+`, [`*`, [Fraction, 2, 3], x, [`^`, -1, [Fraction, 1, 3]], Pi, [`^`, 3, [Fraction, 1, 2]], [`^`, [GAMMA, [Fraction, 2, 3]], -1], [`^`, [`*`, -1, [`^`, x, 3]], [Fraction, -1, 3]]], [`*`, -1, x, [`^`, -1, [Fraction, 1, 3]], [`^`, [`*`, -1, [`^`, x, 3]], [Fraction, -1, 3]], [GAMMA, [Fraction, 1, 3], [`*`, -1, [`^`, x, 3]]]]]]
<br /> -1/3*(-1)^(2/3)*(2/3*x*(-1)^(1/3)*Pi*3^(1/2)/(GAMMA(2/3)*(-x^3)^(1/3))-x*(-1)^(1/3)*GAMMA(1/3, -x^3)/(-x^3)^(1/3))<br />

Comments

acer's picture

ToInert & FromInert

Comment on 2007-11-12 10:38 from acer (Maple Rating 4 1356)

What sort of functionality would this give over and above what ToInert & FromInert give?

acer

John Fredsted's picture

I do not care

Comment on 2007-11-12 10:45 from John Fredsted (Maple Rating 4 566)

I do not know, and I do not care.

acer's picture

ok

Comment on 2007-11-12 16:18 from acer (Maple Rating 4 1356)

For those who are interested, ToInert and FromInert allow pretty much the same sort of programmatic inspection and manipulation of expression trees.

Except that ToInert and FromInert, which are provided as part of Maple itself, can do more. They can also handle procedures, more datastructures such as tables, rare (at the top-level) objects of type SDMPolynom, etc.

acer

What I can see

Comment on 2007-11-12 12:13 from Schivnorr (Maple Rating 2 147)

The only functionality I see over ToInert & FromInert is readability. Then again, dismantle is quite readable.

JacquesC's picture

And simplicity too

Comment on 2007-11-12 19:10 from JacquesC (Maple Rating 4 1697)

I am an extremely heavy user of ToInert/FromInert. However, toTree and fromTree are incomparably simpler [and thus relatively weaker]. One can easily understand these functions and what they do. A full understanding of ToInert/FromInert takes months.

clso's picture

Semantics?

Comment on 2007-11-13 12:20 from clso (Maple Rating 1 16)

Jacques,

Have you been able to formalize the semantics of ToInert/FromInert?

JacquesC's picture

Semantics of ToInert/FromInert

Comment on 2007-11-13 15:29 from JacquesC (Maple Rating 4 1697)

The semantics of FromInert is in some sense easy: it is simply 'denotation', in the sense of denotational semantics. In other words, it takes a representation of a term and returns a term. ToInert is defined as being its pseudo-inverse. Pseudo because the only equations that are guaranteed to hold is that for
TF := ToInert@FromInert and FT := FromInert@ToInert then
1) FT is operationally equivalent to the identity (but is not necessarily equal to it)
2) FT and TF are both idempotent (ie FT@FT = FT and TF@TF = TF)

Basically, one round-trip may modify the routine (but not its meaning), while 2 or more round-trips do nothing at all (is the identity).

The harder part of doing this is to carefully describe the "type" of expression that is the output of ToInert (and the input to FromInert). It is very closely related to the DAG representation internal to Maple (documented in an appendix to the advanced programming guide) but modified a bit for programming convenience.

John Fredsted's picture

Alfa male behaviour?

Comment on 2007-11-13 05:29 from John Fredsted (Maple Rating 4 566)

Thank you guys for putting down my contribution.

I think I will spend some time thinking over whether I want to make further contributions to this forum in which there seems to be going on an alfa male fight for intellectual supremacy, a behaviour which to me is quite dispiriting.

thanks for the contribution

Comment on 2007-11-13 08:31 from Tim Van Dusen (Maple Rating 3 212)

I think it's neat when someone unknowingly does something that provides functionality which is the same as or similar to something which has already been done. That sort of thing happens all the time and is certainly nothing to become discouraged about. I gained a little both from your contribution, and the information concerning the existance of "ToInert & FromInert".

It's a very good thing, in my opinion, that you provide this kind of material here.

Thanks for your contribution.

John Fredsted's picture

Clarification

Comment on 2007-11-13 11:30 from John Fredsted (Maple Rating 4 566)

Thanks for your kindness.

I want to point out, though, that what discourages me is not that it turns out that there is nothing novel about my contribution but solely the way this fact is being delivered.

acer's picture

discourse

Comment on 2007-11-13 12:48 from acer (Maple Rating 4 1356)

Maple didn't have ToInert/FromInert for many years. Now, inspection shows that it is used in many places, internal to various packages. So you have (re)discovered a very useful piece of Maple. There's nothing wrong with that. It shows that you are using Maple more fully than do most.

My original question was honestly put. I wondered whether you had done it for some special reason. I also half-expected someone else to point out some difference, good or bad. This forum is made better by discourse. Jacques pointed out that the simplicity of your form means that it's easier to understand than what ToInert gives. I also mentioned ToInert/FromInert so that other readers might get a fuller picture, and because it's natural to mention it. I saw no disparagment of your idea.

acer

John Fredsted's picture

I apologize

Comment on 2007-11-13 15:31 from John Fredsted (Maple Rating 4 566)

I apologize for having behaved unreasonably.

I guess I reacted the way I did because I had hoped for some (obvious, to me) recognition as I felt that I had made something a little cool. Maybe a bit childish of me!? On the other hand, do we not all need a little recognition once in a while?

Axel Vogt's picture

.

Comment on 2007-11-13 17:34 from Axel Vogt (Maple Rating 4 948)

this is a great answer! whenever come to Munich ... let's have a beer (or better) ...

Munich or Wisconsin?

Comment on 2007-11-13 22:33 from Alex Smith (Maple Rating 3 289)

What I thought was interesting about John Fredsted's ToTree and FromTree was this:

Many times over the last few years I would want to get the tree for a Maple expression. When you enter "tree" into the Maple help text search, nothing useful comes. Or if it does, it does not standout. So "help" was of no help.

Thus I would randomly poke around with "op" to randomly figure out tree. This was a rather pitiful enterprise.

After all this, now I know how to get the tree effectively.

Axel offers a beer if you are in Munich. Alex offers a beer if you are ever in Wisconsin. Wisconsin is noted for its beer, and some of it is good. I don't know if we can compete with Munich, but Wisconsin beer does has its own niche.

John Fredsted's picture

Beers

Comment on 2007-11-14 04:05 from John Fredsted (Maple Rating 4 566)

Thank you guys.

I will have to be careful not to switch in my address book the "l" and "x" of your names, otherwise I would end up in the wrong town :-), as also Alex seems to be aware of.

Munich is famous for its Oktoberfest. I have once visited it. I was very much impressed with the waitresses carrying around so many large beer mugs. What is the record, Axel?

Axel Vogt's picture

Beers, 2nd

Comment on 2007-11-14 07:17 from Axel Vogt (Maple Rating 4 948)

hm ... do not know, never carried around waitresses ...
(no ... do not know the record ...)

have not been at the fest for dozend years, not so much my thing
the nicer and more typical places in Bavaria are smaller gardens
where one aims to relax (and you almost never will meet drunken
ones there, they mostly will not any more alcohol ...), one even
can bring ones own bread, bacon and cheese with you

John Fredsted's picture

Beers, 3rd

Comment on 2007-11-14 09:28 from John Fredsted (Maple Rating 4 566)

Sounds nice. I also prefer small quiet places (with no noisy drunken people present).

Doing things in different ways

Comment on 2007-11-13 14:23 from pchin (Maple Rating 2 163)

In Maple, you can do a task in so many different ways. Sometimes this can cause confusion because it's not always obvious which is the best way. However, I see this as one of the great benefits of using Maple. It allows one to provide options to users, depending on ease-of-use, functionality and efficiency requirements.

We use ToInert in our own code to analyze Maple expressions. This is the full-powered way to take apart expressions as it gives every bit of information you need to know. As others have pointed out, the output is not particularly readable and most users don't need all the information ToInert gives. To answer acer's question, ToInert/FromInert will probably provide all the functionality you'll ever need. However, John's offering a simplified version that might be more useful to some is a good contribution.

Paulina

John Fredsted's picture

Thanks

Comment on 2007-11-14 09:24 from John Fredsted (Maple Rating 4 566)

Thanks for your kind words.

compact variations on a theme

Comment on 2007-11-14 03:24 from Joe Riel (Maple Rating 4 1248)

I like the simple, compact code you wrote.

There is a minor problem. In general, op(0,expr) is not a constructor for expr. For example, list(1,2,3) does not produce the list [1,2,3]. So fromTree fails with expressions consisting of lists or sets.

A minor bug, easily correctible, is the use of i (a global) in the call to seq in fromTree. There are some situations where that can cause weird problems. One way to avoid it is to use proc and declare i as a local. Another way is to use map:

fromTree := x -> `if`(op(x) = x, x, x[1](map(procname, x[2..-1])[])):

Because it seems clearer to test for a list, I prefer

fromTree := x -> `if`(x::list, x[1](map(procname, x[2..-1])[]), x);

While no better, the little used builtin `?()`, normally used in an overload, could be used here,

fromTree := x -> `if`(x::list, `?()`(x[1], map(procname, x[2..-1])), x);

Here's a very compact, but somewhat less efficient technique (an unneeded call to fromTree is made):

fromTree := x -> `if`(x::list, apply(map(procname, x)[]), x);
John Fredsted's picture

Improvement

Comment on 2007-11-14 05:33 from John Fredsted (Maple Rating 4 566)

You are quite right that fromTree fails for expressions which contains lists and/or sets. I was not aware of that. Thanks for pointing that out to me.

Maybe it is just me fooling around or misreading your post, but I cannot get any of the four versions of improvement your suggest to work for a list or a set.

I think I have improved fromTree as follows (implementing at the same time your tip concerning seq and the global variable i):

fromTree := x -> `if`(op(x) = x, x,
	subs({`list`=`[]`,`set`=`{}`},x[1])(map(fromTree,x[2..-1])[])
):

An example:

> expr := {[1,2,{3,4}],int(exp(cos(x)),x)}:
> tree := toTree(expr);
> fromTree(tree);
tree := [set, [list, 1, 2, [set, 3, 4]], [int, [exp, [cos, x]], x]]
             {[1, 2, {3, 4}], int(exp(cos(x)), x)}

backquotes

Comment on 2007-11-14 11:28 from Joe Riel (Maple Rating 4 1248)

Sorry, I wasn't clear. My "improvements" didn't solve the set/list problem; they were mere variations demonstrating some minor Maple coding technique. To fix the set/list issue, you'll have to handle them explicity (as you do above), which reduces the simplicity and beauty of your original code. Note that backquotes around set and list serve no purpose. Using the `[]` and `{}` operators is nice technique.

John Fredsted's picture

Lesser beauty

Comment on 2007-11-14 12:29 from John Fredsted (Maple Rating 4 566)

Thanks for your comment concerning the superfluous backquotes, which I actually did consider leaving out.

I agree with you that the new specially tailored fromTree has less beauty than the original one has.

tree to numeral expression

Comment on 2008-06-27 03:59 from sanny (5)

hi all,

 

i have tree expression and i wanna convert it to numeral expression. for simple example, i have this tree expression:

/ ( * (x1,x1) , + (x1,x1) )

then i wanna get this numeral expression:

x1*x1 / x1+x1

 

what should i do?

prefix commands

Comment on 2008-06-27 09:58 from Joe Riel (Maple Rating 4 1248)

What form is the input?  That is, is it a string that needs to be parsed?  Note that Maple has prefix command for the arithmetic operators, so you could do

`/`(`*`(a,b),`+`(c,d));       
                                                                  a b
                                                                 -----
                                                                 c + d

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
}