help: custom walk to collect sub expressions

[Benjamin Gaidioz]

Hello,

I am afraid I need advices in designing a strategy to walk a tree in a specific way in view of collecting sub-expressions.

But maybe I am overengineering it too, I don't know. Let me explain you my intention, it is quite straightforward I think: I have an exp tree with duplicated sub-expressions which I consider computationally expensive (below I use "sqrt" or "*" as expensive nodes) and I intend to rewrite that whole exp as a block with variables being assigned the value of the expensive exps, while a simpler expression reusing these variables is computed eventually.

def f(x) = { (sqrt(x*x) + sqrt(x*x)) * sqrt(x*x) - sqrt(x*x) }
would be rewritten as
def f(x) = { v := sqrt(x*x) ; (v + v) * v - v }

Note that it optimally chose to declare a variable for sqrt but not for x*x since it is not needed. My implementation works as follows: First I run a collect[Seq, Exp] to get all the complex sub-expressions. It means, the binary exp '+', '-' and '*', and the calls to 'sqrt'. They are all in a list. Then I figure out which ones are duplicated. In the case above there are both "sqrt(x*x)" and "x*x". Then I prepare a Map[Exp, Idn] to associate them to variables if needed later.

Then I rewrite the original exp tree using sometd: rewrite(sometd(rule[Exp] { case e if map.contains(e) => UseVar(map(e))) })

The sometd permits to walk the exp from the top and reach 'sqrt(x*x)' first. This way we actually never bother with x*x.

This worked until I stumbled on a case like that:

def f(x) { if (x > 0) sqrt(x)*sqrt(x) else 0 }
which got rewritten with:
def f(x) { v := sqrt(x) ; if (x > 0) v*v ; else 0 }

It this is wrong code since sqrt(x) would fail on negative values, it should not be computed upfront. This is my problem.

My impression is that "if then else" is a special case and the initial 'collect' was a little too liberal in collecting all including the exps inside a 'then' or an 'else'. Perhaps I should be a little more picky. I have already used more specific strategies to collect sub nodes in the past and I suspect it will be the way out. For example I have already typed code using sometd(rulefs[Exp] ... query[Exp]) to collect nodes in a mutable list using a given topdown/bottomup strategy so that it stops in right boundaries of the tree.

I was trying to come up with something like this for that case I described before. It would be a strategy which would start at the top, successfully insert expressions in general, but when encountering an exp which is the "then" or "else" of an "if", would stop the recursion. Something of that kind. Maybe it could apply a separate strategy when hitting an "if" in fact.

I read many times the various available strategies and I am afraid I am a bit stuck. Maybe there is something using those which take two strategies as parameters (loopnot, etc.) and I am going to give it a try but I think I would benefit a lot from some advices from you :)

Thanks for your understanding and precious help.

[Tony Sloane]

Hi Benjamin,

Thanks for your mail.

> On 26 Aug 2016, at 2:40 AM, Benjamin Gaidioz <bgai...@gmail.com> wrote:

<snip>

> I was trying to come up with something like this for that case I described before. It would be a strategy which would start at the top, successfully insert expressions in general, but when encountering an exp which is the "then" or "else" of an "if", would stop the recursion. Something of that kind. Maybe it could apply a separate strategy when hitting an "if" in fact.
>

> I read many times the various available strategies and I am afraid I am a bit stuck. Maybe there is something using those which take two strategies as parameters (loop not, etc.) and I am going to give it a try but I think I would benefit a lot from some advices from you :)

I confess that there are many library strategies and choosing which one to use in a given circumstance is not easy. We are developing more comprehensive KIama documentation which hopefully will help this situation eventually.

In your application of sometd, if I’ve understood it correctly, you can get more control over which subtrees are entered by sequentially composing your rule argument with another strategy that guards it. So instead of

rule[Exp] { case e if map.contains(e) => UseVar(map(e))) }

you could use

foo <* rule[Exp] { case e if map.contains(e) => UseVar(map(e))) }

where foo succeeds only on terms that you wish to apply the rule to. If foo fails, the rule will not be applied.

Or possibly it will be easier to state as

not(foo) <* rule[Exp] { case e if map.contains(e) => UseVar(map(e))) }

where foo succeeds only on terms you *don’t* wish to apply the rule to. E.g.,

val foo = rule[Exp] { case e @ … pattern matching if-then-else … => e }

I think this approach should mean that you will never try to do the replacement in those sub-trees that foo succeeds on.

(You can do similar things with the guarded choice combinator s1 < s2 + s3 if you want to try something else (s3) if the guard s1 fails.)

On a related point, you are using collect to find the sub-expressions and collect looks everywhere. At the moment Kiama lacks a fully-developed combinator language for this kind of “type-unifying” strategy (aka a fold). collect, query and some variants are all we have at the moment. In the future (hopefully later this year) you will be able to have more control over where the collection happens in a tree and therefore do things like not even collect sub-expressions from inside if-then-else constructs, for example.

I hope this helps.

regards,
Tony

[Benjamin Gaidioz]

Hello ! Many thanks for the quick help. Your suggestion makes sense, I let you know if I run in troubles :)

Bye.