Rewriting Sets

[Tomofumi Yuki]

Hi,

I am currently trying to see if I can use Kiama for quick prototyping of interpreter/semantics for small DSLs. I am having difficulty expressing rewriting rules involving sets; I saw the wiki entry on Collections and went through the examples in the repository but did not find much about how to specify rewriting rules for sets.

A simple example to illustrate the kind of rewriting rules that I want to specify is given in the following. 

I have a simple structure that is a set of tasks, identified by integers.

object TS {

  abstract class Node

  case class TaskSet(tasks: Set[Task]) extends Node

  case class Task(id: Int) extends Node

}

I want to specify the execution of this TaskSet as rewriting rules with non-determinism. A Task is selected randomly from the TaskSet and executed (= removed from the set). Alternatively, it can be described with set notation as:

  TaskSet(s \in S) -> TaskSet(S\s)

or

 TaskSet({s} union r) -> TaskSet(r)

I am unable to specify rules like the above as rules for Kiama. The error messages I get indicates that it is because Set is not a case class. The Kiama wiki suggest that there are some support for Collections including Sets, but what I am trying to do may be out of its scope. I would appreciate your help in understanding how to specify rewriting for sets and its limits.

Thanks,

Tomofumi Yuki

[Tony Sloane]

Hi Tomofumi,

Kiama can certainly rewrite within sets. E.g., see the following transcript:

scala> import org.bitbucket.inkytonik.kiama._

import rewriting.Rewriter._

scala> val r = Set(1,5,8,9)

r: scala.collection.immutable.Set[Int] = Set(1, 5, 8, 9)

scala> val s = rule[Int] { case i => i * 2 }

s: org.bitbucket.inkytonik.kiama.rewriting.Strategy = s

scala> rewrite(alltd(s))(r)

res1: scala.collection.immutable.Set[Int] = Set(2, 10, 16, 18)

So, I expect there is something particular about what you are doing that is going wrong. Would you be able to reply with a (small as possible) example of what code you try to run and what happens?

thanks,

Tony 

--
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.

[Tomofumi Yuki]

hi Tony,

Your example is applying the rule to each elements of a set. I want to match some patter on the set itself. Here is an extension of the above example that I tried:

object TS {

  abstract class Node

  case class TaskSet(tasks: Set[Task]) extends Node

  case class Task(id: Int) extends Node

}

object TSRule {

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

  import TS._

    

  //remove one task from the set randomly

  val r1 = rule[Node] {

        //case 1 trying to specify:

        //  {s} union r -> r

        //compile-time error: value Set is not a case class, nor does it have an unapply/unapplySeq member

       case TaskSet(Set(s) | r) => TaskSet(r)

       

       //case 2 trying to specify:

       //  t \in s -> s\{t}

       //compile-time error: symbol t is undefined

       case TaskSet(s) if (s.contains(t)) => TaskSet(s.-(t))

  }

}

but it does not compile for the reasons noted as comments.

Thanks,

Tomofumi Yuki

[Tony Sloane]

Hi Tomofumi,

Ah, yes. I see what you mean.

The main issue is that Kiama just uses normal Scala pattern-matching which only works on case class instances or objects that have been given an unapply or unapplySeq method (case classes get them via the compiler) as the message for your “case 1” says. Unfortunately the Set library type doesn’t fulfil this condition so you can’t use it directly in a pattern.

“case 2” has a problem because you are using the variable “t” but it hasn’t been bound by the pattern (or elsewhere in scope). 

I think you can achieve what you want with something like this if you are happy with Set.drop selecting the element to remove:

        case TaskSet(s) if s.nonEmpty =>

            TaskSet(s.drop(1))

and you get:

     val s = TaskSet(Set(Task(1), Task(2), Task(3)))

        println(rewrite(r1)(s))  // TaskSet(Set(Task(2), Task(3)))

        println(rewrite(repeat(r1))(s))  // TaskSet(Set())

cheers,

Tony

--

[Tony Sloane]

Hi Tomofumi,

Yeah, Scala pattern-matching can only go so far...

It sounds like you need a more complex approach than a simple tree rewriting if you need to take task dependences into account.

We have had Kiama users specify dependence graphs and use rewriting to optimise them (see e.g., the memo rewriting support in Kiama which preserves results if the “tree” structure is actually a DAG). Maybe you could use a similar approach.

Another possibility is to write Kiama attributes that represent the dependence information and write a custom method to select a “ready to go” task from the set, then remove that one. Then the logic for calculating dependences isi n the attribute world not the rewriting world. However, you will need a more complex structure for that since as presented your tasks are just Ints.

regards,

Tony

On 3 Apr 2018, 11:16 AM +1000, Tomofumi Yuki <tomofu...@gmail.com>, wrote:

Hi Tony,

OK. I had a feeling that such patterns were not supported, but I wanted make sure that I was not missing something. Thank you for your quick responses!

Your suggestion does work for my example. Unfortunately, my original problem before simplification is a bit more involved. Only a subset of the taskset can be selected for removal depending on other state information. You can think of it as a task graph where a task may only fire when its dependences are satisfied. Checking for these dependences requires more complex pattern matching that would ultimately require one of the two forms of pattern in the example.

Thanks,

Tomofumi Yuki

2018年4月3日火曜日 0時12分06秒 UTC+2 Tony Sloane: