Top-down pre and postorder traversal

[abortji]

I am currently working on a DSL for banking (based on http://homepages.cwi.nl/~jurgenv/papers/ITSLE-2016.pdf in case you are interested). Kiama seems to be a very good fit for what we are doing, but we currently fail to find a strategy that fits what we are looking for. I have reduced this to a small case (see code below). Which strategy do we use for this? The downup strategy description seems to fit best, but does not help to get the targeted output. Thank you in advance.

import org.bitbucket.inkytonik.kiama.rewriting.CallbackRewriter
import org.bitbucket.inkytonik.kiama.rewriting.Rewriter._

sealed trait KiamaNode extends Product
case class KiamaTreeNode(lhs: KiamaNode, rhs: KiamaNode) extends KiamaNode
case class KiamaLeaf(x: Int) extends KiamaNode

object KiamaCallbackRewriter extends CallbackRewriter {
  def rewriting[T](oldTerm: T, newTerm: T): T = {
    println(s"\t$oldTerm => $newTerm")
    newTerm
  }
}

object KiamaQuestion extends App {
  val tree = KiamaTreeNode(KiamaTreeNode(KiamaLeaf(1), KiamaLeaf(2)), KiamaLeaf(3))

  val r1 = KiamaCallbackRewriter.rule[KiamaNode] {
    case KiamaTreeNode(lhs, rhs) => println(s"R1: KiamaTreeNode($lhs, $rhs)"); KiamaTreeNode(lhs, rhs)
    case KiamaLeaf(x) => println(s"R1: KiamaLeaf($x)"); KiamaLeaf(x + 10)
  }
  val updated = KiamaCallbackRewriter.rewrite(KiamaCallbackRewriter.everywheretd(r1))(tree)
  println(s"\n$updated")

  /**
    * Actual output:
    * R1: KiamaTreeNode(KiamaTreeNode(KiamaLeaf(1),KiamaLeaf(2)), KiamaLeaf(3))
    *     KiamaTreeNode(KiamaTreeNode(KiamaLeaf(1),KiamaLeaf(2)),KiamaLeaf(3)) => KiamaTreeNode(KiamaTreeNode(KiamaLeaf(1),KiamaLeaf(2)),KiamaLeaf(3))
    * R1: KiamaTreeNode(KiamaLeaf(1), KiamaLeaf(2))
    *     KiamaTreeNode(KiamaLeaf(1),KiamaLeaf(2)) => KiamaTreeNode(KiamaLeaf(1),KiamaLeaf(2))
    * R1: KiamaLeaf(1)
    *     KiamaLeaf(1) => KiamaLeaf(11)
    * R1: KiamaLeaf(2)
    *     KiamaLeaf(2) => KiamaLeaf(12)
    * R1: KiamaLeaf(3)
    *     KiamaLeaf(3) => KiamaLeaf(13)
    *
    * Targeted output:
    * R1: KiamaTreeNode(KiamaTreeNode(KiamaLeaf(1),KiamaLeaf(2)), KiamaLeaf(3))
    * R1: KiamaTreeNode(KiamaLeaf(1), KiamaLeaf(2))
    * R1: KiamaLeaf(1)
    *     KiamaLeaf(1) => KiamaLeaf(11)
    * R1: KiamaLeaf(2)
    *     KiamaLeaf(2) => KiamaLeaf(12)
    *     KiamaTreeNode(KiamaLeaf(1),KiamaLeaf(2)) => KiamaTreeNode(KiamaLeaf(11),KiamaLeaf(12))
    * R1: KiamaLeaf(3)
    *     KiamaLeaf(3) => KiamaLeaf(13)
    *     KiamaTreeNode(KiamaTreeNode(KiamaLeaf(1),KiamaLeaf(2)),KiamaLeaf(3)) => KiamaTreeNode(KiamaTreeNode(KiamaLeaf(11),KiamaLeaf(12)),KiamaLeaf(13))
    */
}

[Tony Sloane]

Hi,

Thanks for your interest in Kiama. We hope it will be useful for your work :-)

I am a bit confused by your question, however, since the output you are getting seems to be consistent with the everywheretd strategy that you are using. In a nutshell, everywheretd(r) will first apply r to the current node, then to all of that node's children. Thus you see the “oldTerm => newTerm” output for a node, before you see it for its children.

Perhaps you want a bottom-up version instead such as everywherebu?

However, it’s not clear you can get exactly the output that you target since the example you give seems to separate the output from the r1 rule, such as

   * R1: KiamaTreeNode(KiamaTreeNode(KiamaLeaf(1),KiamaLeaf(2)), KiamaLeaf(3))

from the log printed by the “rewriting” method:

KiamaTreeNode(KiamaTreeNode(KiamaLeaf(1),KiamaLeaf(2)),KiamaLeaf(3)) => KiamaTreeNode(KiamaTreeNode(KiamaLeaf(11),KiamaLeaf(12)),KiamaLeaf(13))

but that won’t be possible using CallbackRewriter since it calls the rewriting method immediately after the rewrite rule has been applied.

Can you describe in more detail the effect you are trying to achieve in terms of tree rewrites? I presume the use of CallbackRewriter is just to get debugging output and isn’t crucial to the application.

regards,

Tony Sloane

--
You received this message because you are subscribed to the Google Groups "kiama" group.
To unsubscribe from this group and stop receiving emails from it, send an email to kiama+un...@googlegroups.com.
To post to this group, send email to ki...@googlegroups.com.
Visit this group at https://groups.google.com/group/kiama.
For more options, visit https://groups.google.com/d/optout.