Sealing up primitives

[umazalakain]

This is an early draft for a proposal that aims to clarify and consolidate the existing type hierarchy. Big disclaimer: I have little to no experience with Scala's type system. Comments and input are really appreciated ^_^

The existing structure mixes OOP and FP styles in that it

• allows for open subclassing, e.g. exp primitives in DPIA, which are not sealed and delegate translation to imperative;
• certain translation steps pattern match against a(n incomplete) set of known primitives.

Mixing both styles can certainly be a good idea sometimes, but in this case adding a new primitive still requires adding the relevant pattern match cases in the relevant translation points, and at the same time we do not get exhaustiveness checks out of Scala. There are places where not adding a primitive to a pattern match clause causes the translation to crash, and while this is not bad by itself we do not get any warnings at compile time.

One could take the OOP approach and delegate all translation steps to the primitives. While certainly possible this might become a bit of a mess: translation steps deal with callbacks and need to keep track of environments and would need to pass them down to the primitive classes.

The other option is to go the FP way, seal the set of primitives, and do each of the translation steps in one single place. What we get out of it is exhaustiveness checking. If we want to add a primitive, we can do so, and the compiler will tell us about where we need to add pattern matching clauses. Furthermore, we can use traits to restrict the set of primitives that will be available in each of the translation steps.

Two naive examples, one without steps and one with steps:

// A language
sealed trait Language[E,A,C]
case class Exp[E,A,C](e : E) extends Language[E,A,C]
case class Acc[E,A,C](a : A) extends Language[E,A,C]
case class Com[E,A,C](c : C) extends Language[E,A,C]

// The C language
sealed trait CExp
case class Var() extends CExp
case class Lambda() extends CExp
case class App() extends CExp

sealed trait CAcc
case class MapAcc() extends CAcc

sealed trait CCom
case class For() extends CCom

// The OpenCL language
sealed trait OpenCLExp
case class CPrim(e : CExp) extends OpenCLExp
case class Additional() extends OpenCLExp

object Test {
  type CLanguage = Language[CExp, CAcc, CCom]
  type OpenCLLanguage = Language[OpenCLExp, CAcc, CCom]

  // What we get
  def testCExp : CExp => Unit = {
      case Var() => ()
      case Lambda() => ()
      case App() => ()
    }
  def textC : CLanguage => Unit = {
      case Exp(e) => testCExp(e)
      case Acc(a) => ()
      case Com(c) => ()
    }
  def testCL : OpenCLLanguage => Unit = {
    case Exp(CPrim(cexp)) => testCExp(cexp)
    case Exp(Additional()) => ()
    case Acc(a) => ()
    case Com(c) => ()
  }
}

// A language
sealed trait Language[E,A,C,S]
case class Exp[E,A,C,S](e : E with S) extends Language[E,A,C,S]
case class Acc[E,A,C,S](a : A with S) extends Language[E,A,C,S]
case class Com[E,A,C,S](c : C with S) extends Language[E,A,C,S]

// Translation steps: we go from functional+imperative to imperative
sealed trait Imperative
sealed trait Functional extends Imperative

// The C language
sealed trait CExp
case class Var() extends CExp with Imperative with Functional
case class App() extends CExp with Imperative with Functional
case class Lambda() extends CExp with Imperative with Functional
case class Drop() extends CExp with Functional

sealed trait CAcc
case class MapAcc() extends CAcc with Functional

sealed trait CCom
case class For() extends CCom with Functional

// The OpenCL exp language
sealed trait OpenCLExp
case class CExpFun(e : CExp with Functional) extends OpenCLExp with Functional
case class CExpImp(e : CExp with Imperative) extends OpenCLExp with Imperative
case class Foo() extends OpenCLExp with Imperative
case class Bar() extends OpenCLExp with Functional

object Test {
  type FunExp = CExp with Functional
  type ImpExp = CExp with Imperative
  type FunDPIA = Language[CExp, CAcc, CCom, Functional]
  type ImpDPIA = Language[CExp, CAcc, CCom, Imperative]
  type FunOpenCL = Language[OpenCLExp, CAcc, CCom, Functional]
  type ImpOpenCL = Language[OpenCLExp, CAcc, CCom, Imperative]

  def funExpToImpExp : FunExp => ImpExp = {
    case Var() => Var()
    case Lambda() => Lambda()
    case App() => App()
    case Drop() => Var() // whatever, translation happens here
  }
  def funToImpC : FunDPIA => ImpDPIA = {
    case Exp(e) => Exp(funExpToImpExp(e))
    case Acc(a) => Acc(a)
    case Com(c) => Com(c)
  }
  def funToImpOpenCL : FunOpenCL => ImpOpenCL = {
    case Exp(CExpFun(e)) => Exp(CExpImp(funExpToImpExp(e)))
    case Exp(Bar()) => Exp(Foo())
    case Acc(a) => Acc(a)
    case Com(c) => Com(c)
  }
}

[michel-steuwer]

On aspect that I dislike about these implementations is that we have to wrap the CExp explicitly into a CPrim when defining the OpenCLExpr ADT.

The new Scala 3 Union Types allow to avoid this:

// Rest as above

// The OpenCL language
sealed trait OpenCLExp
case class Additional() extends OpenCLExp

type OpenCLLanguage = Language[OpenCLExp | CExp, CAcc, CCom]
//                                       ^
//                                       Union Type

def testCL : OpenCLLanguage => Unit = {
  case Exp(Var()) => ()
  case Exp(Lambda()) => ()
  case Exp(App()) => ()
  case Exp(Additional()) => ()
  case Acc(a) => ()
  case Com(c) => ()
}

Do you see a way to achieve the same in Scala 2 without the union typ?

[umazalakain]

I think the opposite, that it is good to be explicit about whether "these primitives serve for all" or "these are special cases for the OpenCL backend". After all when you extend a translation step in OpenCL you will probably delegate to the corresponding C step every C primitive you encounter.

But apparently yes, it is possible to do something like this, though it is quite clunky:

sealed trait OpenCLExp
case class Additional() extends OpenCLExp

class COrOpenCL[T]
object Or{
  implicit object Left extends COrOpenCL[CExp]
  implicit object Right extends COrOpenCL[OpenCLExp]
}

object Bar {
  def foo[T: COrOpenCL](x: T) = x match {
    case _: String => println("str")
    case _: Int => println("int")
  }
}

object Test {
  def testCL[T : COrOpenCL] : T => Unit = {
    case Var() => ()
    case Lambda() => ()
    case App() => ()
    case Additional() => ()
  }
}

We can use a parametrised macro to generalise COrOpenCL and create "unions" on the fly.