Abstract domains using Scala-style typeclasses

[octalsrc]

I have redefined the abstractions for abstract domains using the pattern of Scala-style typeclasses and implemented two abstract domains as examples, Interval and Vote.

To use these abstractions for your new abstract domain datatype Foo (which abstracts concrete datatype Int), you implement instances of Abstraction[Int,Foo] and Semilattice[Foo] (or, optionally, Lattice[Foo]) as implicit values in the object Foo.implicits.

object Foo {
  object implicits {
    implicit val semilatticeFoo: Semilattice[Foo] = new Semilattice[Foo] {
      @override val bot: Foo = ...
      @override implies(e1: Foo, e2: Foo): Boolean = ...
      @override join(e1: Foo, e2: Foo): Foo = ...
    }

    implicit val abstractionFoo: Abstraction[Int,Foo] = new Abstraction[Int,Foo] {
      @override def represent(c: Int): Foo = ...
    }
  }
}

Having provided these implementations, you can use the semilattice and abstraction operations wherever you like. (beta, as used in this example, is an alias for represent)

import Abstraction._
import Semilattice._
import Foo.implicits._

val foo1 = join(beta(4),beta(8))
val hmm = implies(foo1,beta(3000))

You can also define generic operations over abstract domain values

import Abstraction._
import Semilattice._

def bar[A : Semilattice](e1: A, e2: A, e3: A): A = (implies(join(e1,e2),e3)) match {
  case true => e3
  case false => e1
}

// Since Abstraction has two parameters, we have to write its constraint in this 
// longer form rather than using the syntactic sugar as we do for Semilattice
//
def baz[A : Semilattice](c1: C, c2: C, c3: C)(implicit inst: Abstraction[C,A]): A = 
  bar(beta(c1),beta(c2),beta(c3))

and use them for Foo.

import Foo.implicits._

val asdf: Foo = baz(1,2,3)

[octalsrc]

As mentioned before, we can further use simulacrum, in the style of the cats library, to eliminate some of the boilerplate required for defining these abstractions. Specifically, the companion objects for Lattice, Semilattice, and Abstraction which enable the typeclass-like usage of the traits can be macro-generated with the @typeclass annotation.

[ftc]

Just a note: I changed some of the scaladoc since Intellij was complaining about broken references.

When using the [[Foo]] Syntax it tries to find a class. I changed the method references in there to [[Foo.method]] which removed the error. I am not sure how to specifically make it link to the methods though since when I build the scala-doc the links seem broken. If anyone has an idea on this it would be good to hear.

To view scaladoc in intellij: ctrl j (on Mac)

[ftc]

@octalsrc I believe we should have a discussion on the following points. I had some trouble implementing extra unit tests but I think it may be my understanding of implicits. I will try to spend some time tonight going through the documentation and understand them better. Perhaps we can spend some time looking at this together next time we meet?

Notes on interface: -The methods in the tests which "adapt" implicits to be used locally seem redundant and it would be nice if we didn't need such things. Is there a better way to do this? Also I had trouble replicating this when I attempted to add a test for "isBottom" but I think that is my own lack of experience with implicits in scala.

  def checkmeet[C,A : Lattice](
    c1: C, c2: C
  )(
    implicit inst: Abstraction[C,A]
  ): A = {
    meet(beta(c1),beta(c2))
  }

• What do the apply methods do? they are not used in the unit tests and I am unsure how I would add tests to exercise them.
• I think we should have a "widen" operator
• For the vote domain, what is the difference between the "represent" method and "beta"? Is there a reason to separate these two methods like this rather than implementing it more directly? Do we need to do this with all of the methods we want in this interface?

[octalsrc]

@ftc Sorry, those methods you cited (checkmeet, checkjoin) are actually not needed; they were sort of testing that writing polymorphic methods for typeclasses works (since all the typeclass uses otherwise in the suites were concrete).

The apply methods are used to take a step out of using the instances. It's described in this document: http://typelevel.org/cats/typeclasses.html

Providing this apply for a typeclass Monoid, for example,

object Monoid {
  def apply[A : Monoid]: Monoid[A] = implicitly[Monoid[A]]
}

lets you use this:

def combineAll[A : Monoid](list: List[A]): A =
  list.foldRight(Monoid[A].empty)(Monoid[A].combine)

instead of this:

def combineAll[A : Monoid](list: List[A]): A =
  list.foldRight(implicitly[Monoid[A]].empty)(implicitly[Monoid[A]].combine)

As for method names, represent and beta are the same; I've changed it to just beta now. It's up to bikeshedding which one we end up with.

[bechang]

The reason there are both represent and beta is that either of them could be clearer depending on the context and what your background is.

[ftc]

Nick and I discussed this and believe that the next reasonable step is to implement an abstract interpreter on top of this. I am going to start by extending the interval domain with a few things and making a domain for static variables.

[bechang]

@ftc But this is a new task. Could you finish the review? For the review, critique what you think is relevant to this feature. Is the code being committed connected with tests? Can you add an additional (likely somewhat redundant) test case?

[ftc]

I added unit tests for the "isBottom" method and it appears to be something I can work with (Although I am still learning how it is organized). I think I would be satisfied to merge this and start working on extensions after we figure out how to write unit tests that exercise a few things:

• [x] Lattice apply method
• [x] Semilattice apply method
• [x] Lattice isTop (I tried to just write this unit test, however I think there is some code missing elsewhere to make this work)
• [x] no case with an underscore in the interval domain has a unit test. Do we need these? If so how do we test them?

For a general todo: I can't figure out how to make code coverage work on the domains package, it seems to not list them in a meaningful way. Manual inspection makes me think they are reasonably covered beyond the bullets above though.