Comparing Object Encodings

notes.scala

/**
 * This file contains some notes taken while reading:
 *
 *     Comparing Object Encodings
 *     Kim B. Bruce, Luca Cardelli and Benjamin C. Pierce
 */
package object encodings {

  // Library Stuff
  trait Fix[F[_]] {
    type Fun[X] = F[X]
    def unroll: F[Fix[F]]
  }
  object Fix {
    def apply[F[_]](x: F[Fix[F]]) = new Fix[F] { def unroll = x }
    def unapply[F[_]](fx: Fix[F]): Option[F[Fix[F]]] = Some(fx.unroll)
  }
  implicit def unroll[F[_]](x: Fix[F]): F[Fix[F]] = x.unroll

  def fix[A](f: (=> A) => A): A = {
    lazy val a: A = f(a)
    a
  }


  type OR[I[_]] = Fix[I]

  type OE[I[_]] = {
    type Y
    def state: Y
    def impl: Y => I[Y]
  }

  // We need to use a named trait here, otherwise Scala does
  // not trust us when defining `pack` below.
  trait Exist[B, X] {
    type Y <: B
    def state: Y
    def impl: Y => X
  }

  type ORE[I[_]] = Fix[({ type λ[X] = Exist[Any, I[X]] })#λ]

  type ORBE[I[_]] = Fix[({ type λ[X] = Exist[X, I[X]] })#λ]
}

package object examples {

  import encodings._

  trait CellI[X] {
    def get: Int
    def set: Int => X
    def bump: X
  }

  // OR: Recursive Records

  def ORTests(mk: { val x: Int } => OR[CellI]): Unit = {
    val mycell = mk(new { val x = 0 })
    assert(mycell.bump.get == 1)
  }

  object OR {

    // mkobj is a generator function that produces codata.
    def mkobj(s: { val x: Int }): OR[CellI] = Fix(new CellI[Fix[CellI]] {
      def get = s.x
      def set = n => mkobj(new { val x = n })
      def bump = mkobj(new { val x = s.x + 1 })
    })

    ORTests(mkobj)
  }

  object ORSelf {
    def mkobj(s: { val x: Int }): OR[CellI] = {

      lazy val self = mkobj(s) // laziness here is important!

      Fix(new CellI[Fix[CellI]] {
        def get = s.x
        def set = n => mkobj(new { val x = n })
        def bump = self.set(self.get + 1)
      })
    }

    ORTests(mkobj)
  }

  // This is slightly more standard. Explicitly calling the fixed
  // point construction.
  object ORSelfFix {
    def mkobj(s: { val x: Int }): (=> OR[CellI]) => OR[CellI] =
      self => {
        Fix(new CellI[Fix[CellI]] {
          def get = s.x
          def set = n => fix(mkobj(new { val x = n }))
          def bump = self.set(self.get + 1)
        })
      }

    ORTests((mkobj _) andThen fix)
  }

  // Just for convenience
  type State = { val x: Int }

  // with some implicits for repackaging:
  implicit class OEOps(cell: OE[CellI]) {
    def bump: OE[CellI] = new {
      type Y = cell.Y
      def state = cell.impl(cell.state).bump
      def impl = cell.impl
    }
    def get: Int = cell.impl(cell.state).get
    def set: Int => OE[CellI] = n => new {
      type Y = cell.Y
      def state = cell.impl(cell.state).set(n)
      def impl = cell.impl
    }
  }

  def OETests(mk: State => OE[CellI]): Unit = {
    val mycell = mk(new { val x = 0 })

    // in the paper the object is packaged everytime, but we
    // also can just use the implementation like this:
    val impl = mycell.impl
    assert(impl(impl(mycell.state).bump).get == 1)

    assert(mycell.bump.get == 1)
  }

  // OE: Existentials
  object OE {

    // this is basically a coalgebra
    def coalg = (s : State) => new CellI[State] {
      def get = s.x
      def set = n => new { val x = n }
      def bump = new { val x = s.x + 1 }
    }

    def mkobj(s: State): OE[CellI] = new {
      type Y = State
      def state = s
      def impl = coalg
    }

    OETests(mkobj)
  }

  type Coalg[S, F[_]] = S => F[S]

  object OESelf {

    def coalg(self: => Coalg[State, CellI]) = (s : State) => new CellI[State] {
      def get = s.x
      def set = n => new { val x = n }
      def bump = self(s).set(self(s).get + 1)
    }

    def mkobj(s: State): OE[CellI] = new {
      type Y = State
      def state = s
      def impl = fix(coalg) // close the self-reference
    }

    OETests(mkobj)
  }

  // We could also expose some of the internal state
  type OBE[I[_], R] = {
    type Y <: R
    def state: Y
    def impl: Y => I[Y]
  }


  // We need to unroll the fixed point first. On the other
  // hand object usage is more uniform now:
  implicit def OREOps(cell: ORE[CellI]): CellI[ORE[CellI]] = {
    val un = cell.unroll;
    un.impl(un.state)
  }

  def ORETests(mk: State => ORE[CellI]): Unit = {

    def unroll(obj: ORE[CellI]): Exist[Any, CellI[ORE[CellI]]] =
      obj.unroll

    val mycell = mk(new { val x = 0 })

    assert(mycell.bump.get == 1)
  }

  object ORE {
    // lazy parameter for definition of ORBE below
    def pack[S, I[_]](s: => S, f: S => I[ORE[I]]): ORE[I] =
      Fix[ORE[I]#Fun](new Exist[Any, I[ORE[I]]] {
        type Y = S
        def state: Y = s
        def impl = f
      })

    // letrec
    def meth: State => CellI[ORE[CellI]] = (s: State) => new CellI[ORE[CellI]] {
      def get = s.x
      def set = n => pack(new { val x = n }, meth)
      def bump = pack(new { val x = s.x + 1 }, meth)
    }

    def mkobj(s: State): ORE[CellI] = pack(s, meth)

    ORETests(mkobj)
  }

  object ORESelf {
    import ORE.pack

    // not recursive
    def meth: (State => ORE[CellI]) => State => CellI[ORE[CellI]] =
      mk => s => new CellI[ORE[CellI]] {
        lazy val self = mk(s)
        def get = s.x
        def set = n => mk(new { val x = n })
        def bump = self.set(self.get + 1)
      }

    // now this is recursive
    def mkobj(s: State): ORE[CellI] = pack(s, meth(mkobj))

    ORETests(mkobj)
  }

  implicit def ORBEOps(obj: ORBE[CellI]): CellI[ORBE[CellI]] = {
    val un = obj.unroll
    un.impl(un.state)
  }

  // seems like the ORBE encoding is not much different from the
  // ORE encoding.
  object ORBE {
    import ORE.pack

    def meth: (State => ORE[CellI]) => State => ORE[CellI] => CellI[ORE[CellI]] =
      mk => state => self =>
       new CellI[ORE[CellI]] {
        def get = state.x
        def set = n => mk(new { val x = n })
        def bump = self.set(self.get + 1)
      }

    def mkobj(s: State): ORE[CellI] = pack(mkobj(s), meth(mkobj)(s))

    assert(mkobj(new { val x = 0 }).bump.bump.get == 2)
    ORETests(mkobj)
  }
}