Conditionally rewriting terms in Kiama/Scala

Question

I'm trying to implement a "Committed choice" operation in Kiama (along with some other functions that work in a similar way).

I want to re-write a term iff one of its subterms can be successfully re-written (the idea being that once you start down either branch, you're committed).

Currently, I can do it like this:

import org.kiama.rewriting.Rewriter
import org.junit.Test

case class B(l:L,r:L)
case class L(s:String)
class RewriteExperiment extends Rewriter {
  def r1 = rule {
    case L(l) if l.s == "X" => L("Did stuff")
  }

  def r2 = strategy {
    case B(l,r) => r1(l) match {
      case Some(x:L) => Some(B(x,"Avoided"))
      case _ => None
    }
  }

  implicit def s2l(s:String) : L = L(s)
}

class RewriteTest extends RewriteExperiment {
  @Test
  def testPruning : Unit = {
    println( rewrite(r2)(B("P","b")) )
    println( rewrite(r2)(B("X","b")) )
  }
}

So r2 only fires when it can apply r1 to the first subterm successfully.

This doesn't feel very Kiama-ish. I have a feeling that I should be using congruences, but I can't figure out how they work from the docs.

Can anyone suggest a more elegant and Kiamaish way to do this?

Answer 1

Congruences would be one way, but unfortunately in Kiama they require some boilerplate. If you want to go in that direction, see Kiama's lambda2 example. AST.scala defines congruences for the tree node types and files such as ParLazySubst.scala use them to define strategies. E.g., in App (s, id), the App is a congruence and the App (s, id) strategy succeeds on App nodes if s succeeds on the first child of the node (id is the identity strategy).

An alternative is to use child which is sort of a generic congruence for a single child, where you say which child you want to operate on by giving its number. (Alternatively, if you don't know which child it is or you want to operate on more than one child, you can use all, one, or some.)

E.g., I think the following is a clearer way to do what you are doing above:

  def r1 =
    rule {
      case L (l) if l.s == "X" => L ("Did stuff")
    }

  def r2 =
    rule {
      case B (l, r) => B (l, "Avoided")
    }

  val r3 = (child (1, r1)) <* r2

and then use r3.

Notice that the child (...) strategy operates on the original input term, so we can use normal sequencing (<*) to decide whether or not to apply r2 to that term as well. This solution is more composable since r2 doesn't have to know anything about r1.