CODEWITHSUNDEEP
scala
Jofbr
Jofbr

Reputation: 473

Expression prblem solution in scala

I am new to Scala. Consider this article (http://scala-lang.org/docu/files/IC_TECH_REPORT_200433.pdf). The article presents two solutions to the expression problem (https://en.wikipedia.org/wiki/Expression_problem) in Scala. In section 3, it presents an object-oriented solution and in section 4, it presents a functional approach.

I am trying to construct a full program from the solution in section 3. Therefore, I have the following code below as my scala program (filename: 'ep.scala').

trait Base {
  type exp <: Exp;
  trait Exp {
    def eval: Int
  }
  class Num(v: Int) extends Exp {
    val value = v;
    def eval = value
  }
}

trait BasePlus extends Base {
  class Plus(l: exp, r: exp) extends Exp {
    val left = l; val right = r;
    def eval = left.eval + right.eval
  }
}

trait BaseNeg extends Base {
  class Neg(t: exp) extends Exp {
    val term = t;
    def eval = - term.eval;
  }
}

trait BasePlusNeg extends BasePlus with BaseNeg;

trait Show extends Base {
  type exp <: Exp;
  trait Exp extends super.Exp {
    def show: String;
  }
  class Num(v: Int) extends super.Num(v) with Exp {
    def show = value.toString();
  }
}

trait ShowPlusNeg extends BasePlusNeg with Show {
  class Plus(l: exp, r: exp) extends super.Plus(l, r) with Exp {
    def show = left.show + "+" + right.show;
  }
  class Neg(t: exp) extends super.Neg(t) with Exp {
    def show = "-(" + term.show + ")";
  }
}

trait DblePlusNeg extends BasePlusNeg {
  type exp <: Exp;
  trait Exp extends super.Exp {
    def dble: exp;
  }
  def Num(v: Int): exp;
  def Plus(l: exp, r: exp): exp;
  def Neg(t: exp): exp;
  class Num(v: Int) extends super.Num(v) with Exp {
    def dble = Num(v * 2);
  }
  class Plus(l: exp, r: exp) extends super.Plus(l, r) with Exp {
    def dble = Plus(left.dble, right.dble);
  }
  class Neg(t: exp) extends super.Neg(t) with Exp {
    def dble = Neg(t.dble);
  }
}

trait ShowDblePlusNeg extends ShowPlusNeg with DblePlusNeg {
  type exp <: Exp;
  trait Exp extends super[ShowPlusNeg].Exp 
           with super[DblePlusNeg].Exp;
  class Num(v: Int) 
    extends super[ShowPlusNeg].Num(v)
       with super[DblePlusNeg].Num(v)
       with Exp;
  class Plus(l: exp, r: exp)
    extends super[ShowPlusNeg].Plus(l, r)
       with super[DblePlusNeg].Plus(l, r)
       with Exp;
  class Neg(t: exp)
    extends super[ShowPlusNeg].Neg(t)
       with super[DblePlusNeg].Neg(t)
       with Exp;
}

trait Equals extends Base {
  type exp <: Exp;
  trait Exp extends super.Exp {
    def eql(other: exp): Boolean;
    def isNum(v: Int) = false;
  }
  class Num(v: Int) extends super.Num(v) with Exp {
    def eql(other: exp): Boolean = other.isNum(v);
    override def isNum(v: Int) = v == value;
  }
}

trait EqualsPlusNeg extends BasePlusNeg with Equals {
  type exp <: Exp;
  trait Exp extends super[BasePlusNeg].Exp
           with super[Equals].Exp {
    def isPlus(l: exp, r: exp): Boolean = false;
    def isNeg(t: exp): Boolean = false;
  }
  class Num(v: Int) extends super[Equals].Num(v)
                   with Exp;
  class Plus(l: exp, r: exp) extends Exp
                            with super.Plus(l, r) {
    def eql(other: exp): Boolean = other.isPlus(l, r);
    override def isPlus(l: exp, r: exp) = (left eql l) && (right eql r)
  }
  class Neg(t: exp) extends Exp
                   with super.Neg(t) {
    def eql(other: exp): Boolean = other.isNeg(t);
    override def isNeg(t: exp) = term eql t
  }
}

trait EqualsShowPlusNeg extends EqualsPlusNeg
                       with ShowPlusNeg {
  type exp <: Exp;
  trait Exp extends super[EqualsPlusNeg].Exp
           with super[ShowPlusNeg].Exp;
  class Num(v: Int)
    extends super[EqualsPlusNeg].Num(v)
       with super[ShowPlusNeg].Num(v)
       with Exp;
  class Plus(l: exp, r: exp)
    extends super[EqualsPlusNeg].Plus(l, r)
       with super[ShowPlusNeg].Plus(l, r)
       with Exp;
  class Neg(term: exp)
    extends super[EqualsPlusNeg].Neg(term)
       with super[ShowPlusNeg].Neg(term)
       with Exp;
}

But when I try to compile this using scalac ep.scala, I get the following errors:

ep.scala:72: error: class Num needs to be a trait to be mixed in
       with super[DblePlusNeg].Num(v)
                           ^
ep.scala:76: error: class Plus needs to be a trait to be mixed in
       with super[DblePlusNeg].Plus(l, r)
                           ^
ep.scala:80: error: class Neg needs to be a trait to be mixed in
       with super[DblePlusNeg].Neg(t)
                           ^
ep.scala:106: error: class Plus needs to be a trait to be mixed in
                            with super.Plus(l, r) {
                                       ^
ep.scala:111: error: class Neg needs to be a trait to be mixed in
                   with super.Neg(t) {
                              ^
ep.scala:124: error: class Num needs to be a trait to be mixed in
       with super[ShowPlusNeg].Num(v)
                           ^
ep.scala:128: error: class Plus needs to be a trait to be mixed in
       with super[ShowPlusNeg].Plus(l, r)
                           ^
ep.scala:132: error: class Neg needs to be a trait to be mixed in
       with super[ShowPlusNeg].Neg(term)
                           ^
8 errors found

Please explain how to fix these errors.

I am using scala version 2.11.8. From my understanding, there was some break in retrocompatibilty in scala, from the current version w.r.t. the version of the article. I have tweaked the code to fix minor issues arising from those language differences, but those 8 errors (all of the same kind) still stay. Trying to declare the classes indicated by the errors as traits does not help, since traits can not have parameters "as" fields.

Note: I do not want to deviate from the approach presented in the paper. Please only provide solutions on how can I fix my code (above) without drastically deviating from this solution.

Upvotes: 2

Views: 117

Answers (1)

SergGr
SergGr

Reputation: 23788

This report is probably 10+ years old when Scala was much more experimental than it is now and Scala has changed in quite a few places since then. But you still can make this work with a few modifications. The most important thing to fix is multiple inheritance from classes. I'm not sure how exactly it worked then in Scala in the diamond case (which is exactly what happens here). Assuming this code ever worked it looks like the inheritance must have been "virtual" i.e. only one set of fields was inherited from the common base class. You still can simulate this in Scala using multiple inheritance of traits aka mixins and self types. You may try to do something like this:

trait Base {
  type exp <: Exp

  trait Exp {
    def eval: Int
  }


  class Num(val value: Int) extends Exp {
    def eval: Int = value
  }

  type BaseNum = Num
}

trait BasePlus extends Base {

  class Plus(val left: exp, val right: exp) extends Exp {
    def eval: Int = left.eval + right.eval
  }

  type BasePlus = Plus
}

trait BaseNeg extends Base {

  class Neg(val term: exp) extends Exp {
    def eval = -term.eval
  }

  type BaseNeg = Neg
}

trait BasePlusNeg extends BasePlus with BaseNeg

trait Show extends Base {
  type exp <: Exp

  trait Exp extends super.Exp {
    def show: String
  }

  trait NumBehavior extends Exp {
    self: BaseNum =>
    override def show: String = value.toString
  }

  final class Num(v: Int) extends BaseNum(v) with NumBehavior with Exp

}

trait ShowPlusNeg extends BasePlusNeg with Show {

  trait PlusBehavior {
    self: BasePlus =>
    def show = left.show + "+" + right.show;
  }

  final class Plus(l: exp, r: exp) extends BasePlus(l, r) with PlusBehavior with Exp

  trait NegBehavior {
    self: BaseNeg =>
    def show = "-(" + term.show + ")";
  }

  class Neg(t: exp) extends BaseNeg(t) with NegBehavior with Exp

}

trait DblePlusNeg extends BasePlusNeg {
  type exp <: Exp

  trait Exp extends super.Exp {
    def dble: exp
  }

  def Num(v: Int): exp

  def Plus(l: exp, r: exp): exp

  def Neg(t: exp): exp


  trait NumBehavior {
    self: BaseNum =>
    def dble = Num(value * 2)
  }

  final class Num(v: Int) extends BaseNum(v) with NumBehavior with Exp


  trait PlusBehavior {
    self: BasePlus =>
    def dble = Plus(left.dble, right.dble)
  }

  class Plus(l: exp, r: exp) extends BasePlus(l, r) with PlusBehavior with Exp


  trait NegBehavior {
    self: BaseNeg =>
    def dble = Neg(term.dble)
  }

  class Neg(t: exp) extends super.Neg(t) with NegBehavior with Exp

}

trait ShowDblePlusNeg extends ShowPlusNeg with DblePlusNeg {
  type exp <: Exp

  trait Exp extends super[ShowPlusNeg].Exp with super[DblePlusNeg].Exp;

  trait NumBehavior extends super[ShowPlusNeg].NumBehavior with super[DblePlusNeg].NumBehavior {
    self: BaseNum =>
  }

  final class Num(v: Int) extends BaseNum(v)
    with NumBehavior
    with Exp


  trait PlusBehavior extends super[ShowPlusNeg].PlusBehavior with super[DblePlusNeg].PlusBehavior {
    self: BasePlus =>
  }

  final class Plus(l: exp, r: exp) extends BasePlus(l, r)
    with PlusBehavior
    with Exp

  trait NegBehavior extends super[ShowPlusNeg].NegBehavior with super[DblePlusNeg].NegBehavior {
    self: BaseNeg =>
  }

  final class Neg(t: exp) extends BaseNeg(t)
    with NegBehavior
    with Exp

}

trait Equals extends Base {
  type exp <: Exp;

  trait Exp extends super.Exp {
    def eql(other: exp): Boolean;

    def isNum(v: Int): Boolean = false;
  }

  trait NumBehavior extends Exp {
    self: BaseNum =>
    def eql(other: exp): Boolean = other.isNum(value);

    override def isNum(v: Int) = v == value;
  }


  final class Num(v: Int) extends BaseNum(v) with NumBehavior with Exp

}

trait EqualsPlusNeg extends BasePlusNeg with Equals {
  type exp <: Exp;

  trait Exp extends super[BasePlusNeg].Exp
    with super[Equals].Exp {
    def isPlus(l: exp, r: exp): Boolean = false;

    def isNeg(t: exp): Boolean = false;
  }


  final class Num(v: Int) extends BaseNum(v)
    with NumBehavior // effectively super[Equals].NumBehavior
    with Exp


  trait PlusBehavior extends Exp {
    self: BasePlus =>
    def eql(other: exp): Boolean = other.isPlus(left, right);

    override def isPlus(l: exp, r: exp) = (left eql l) && (right eql r)
  }

  final class Plus(l: exp, r: exp) extends BasePlus(l, r) with PlusBehavior with Exp


  trait NegBehavior extends Exp {
    self: BaseNeg =>
    def eql(other: exp): Boolean = other.isNeg(term);

    override def isNeg(t: exp) = term eql t
  }

  final class Neg(t: exp) extends BaseNeg(t) with NegBehavior with Exp

}

trait EqualsShowPlusNeg extends EqualsPlusNeg with ShowPlusNeg {
  type exp <: Exp

  trait Exp extends super[EqualsPlusNeg].Exp
    with super[ShowPlusNeg].Exp


  trait NumBehavior extends super[EqualsPlusNeg].NumBehavior with super[ShowPlusNeg].NumBehavior {
    self: BaseNum =>
  }

  class Num(v: Int) extends BaseNum(v) with NumBehavior with Exp

  trait PlusBehavior extends super[EqualsPlusNeg].PlusBehavior with super[ShowPlusNeg].PlusBehavior {
    self: BasePlus =>
  }

  class Plus(l: exp, r: exp) extends BasePlus(l, r) with PlusBehavior with Exp

  trait NegBehavior extends super[EqualsPlusNeg].NegBehavior with super[ShowPlusNeg].NegBehavior {
    self: BaseNeg =>
  }

  class Neg(term: exp) extends BaseNeg(term) with NegBehavior with Exp

}

Finally you may create instances of some of those composed traits such as

object EqualsShowPlusNegInstance extends EqualsShowPlusNeg {
  override type exp = Exp
}

object ShowDblePlusNegInstance extends ShowDblePlusNeg {
  override type exp = Exp

  override def Num(v: Int) = new Num(v)

  override def Plus(l: Exp, r: Exp) = new Plus(l, r)

  override def Neg(t: Exp) = new Neg(t)
}

and then you can do something like this:

def test1() = {
  import EqualsShowPlusNegInstance._
  println("EqualsShowPlusNegInstance:")
  println(new Num(3).show)
  // println(new Num(3).dble.show) // compilation error for dble
  println(new Plus(new Num(3), new Num(4)).show)
  // println(new Plus(new Num(3), new Num(4)).dble.show) // compilation error for dble
  println(new Num(3).eql(new Num(4)))

}

def test2() = {
  import ShowDblePlusNegInstance._
  println("ShowDblePlusNegInstance:")
  println(new Num(3).show)
  println(new Num(3).dble.show)
  println(new Plus(new Num(3), new Num(4)).show)
  println(new Plus(new Num(3), new Num(4)).dble.show)
  // println(new Num(3).eql(new Num(4)))  // compilation error for eql
}

The most important trick here is that classes with multiple inheritance on different levels such as Num are split into:

  1. Single base class (such as Base.Num). Such classes are usually type aliased into something like BaseNum
  2. Behavior traits (such as Show.NumBehavior) on every level that contain all the logic and can be inherited further (aka mixins)
  3. Concrete final classes on every level (such as Show.Num).

This split allows creating concrete classes by inheriting just one base class and "enhancing" it with a Behavior trait that is a join of all Behavior traits of parents.

Upvotes: 1

Related Questions