views:

245

answers:

1

Hi stackoverflow.

Having a background in Haskell I am currently trying to get familiar with Scala.

I encountered some problems trying to translate a small, extensible expression language from Haskell into Scala. The underlying issue of writing a data type that is extensible with both new data-variants and operations is commonly known as the expression problem.

My original solution in Haskell uses type classes and instance declarations with constraints. The base of my expression is defined as follows:

module Expr where

class Expr e where
 eval :: e -> Integer

data Lit = Lit Integer
instance Expr Lit where
  eval (Lit l) = l

data Plus a b = (Expr a, Expr b) => Plus a b
instance (Expr a, Expr b) => Expr (Plus a b) where
  eval (Plus x y) = (eval x) + (eval y)

Then, I have one data-extension that adds multiplication:

module ExprWithMul where
import Expr

data Mul a b = (Expr a, Expr b) =>  Mul a b
instance (Expr a, Expr b) => Expr (Mul a b) where
  eval (Mul x y) = (eval x) * (eval y)

Let's take a pretty-printer as an operational extension:

module FormatExpr where
import Expr

class (Expr t) => FormatExpr t where
  format :: t -> String

instance FormatExpr Lit where
  format (Lit l) = show l

instance (FormatExpr a, FormatExpr b) => FormatExpr (Plus a b) where
  format (Plus x y) = "(" ++ (format x) ++ "+" ++ (format y) ++ ")"

And, finally, in the fourth module the two independent extensions can be combined:

module FormatExprWithMult where
import FormatExpr
import ExprWithMul

instance (FormatExpr a, FormatExpr b) => FormatExpr (Mul a b) where
  format (Mul x y) = "(" ++ (format x) ++ "*" ++ (format y) ++ ")"

Now for my problem: Usually type classes from haskell are translated to the concept-pattern with implicits in Scala. This is how far I got:

abstract class Expr[A] { // this corresponds to a type class
  def eval(e:A): Int;
}

case class Lit(v: Int)
implicit object ExprLit extends Expr[Lit] {
 def eval(e: Lit) = x.v;
}
case class Plus[A,B] (e1: A, e2: B) (implicit c1: Expr[A], c2: Expr[B])

Here I am stuck with implementing the implicit object for Plus. How do I declare an implicit object with type parameters and constraints?

I know that there are other solution for the expression problem in Scala, I am however interested in this version in particular.

Thank you all for reading my somewhat lengthy question.

+10  A: 

First attempt (flawed):

case class Plus[A,B] (e1: A, e2: B) (implicit c1: Expr[A], c2: Expr[B]) {
    implicit object ExprPlus extends Expr[Plus[A, B]] { 
        def eval(p:Plus[A, B]) = c1.eval(p.e1) + c2.eval(p.e2)
    }
}

Edit 1:

The above isn't sufficiently powerful (you can't add two Plus expressions), and the implicit witness need not be defined inside of the Plus case class... try this instead:

case class Plus[A,B] (e1: A, e2: B) (implicit val c1: Expr[A], c2: Expr[B])
implicit def ExprPlus[A, B](implicit c1: Expr[A], c2: Expr[B]) = 
    new Expr[Plus[A, B]] { 
        def eval(p:Plus[A, B]) = c1.eval(p.e1) + c2.eval(p.e2)
    }

Edit 2:

Here's a (perhaps) slightly more idiomatic version:

case class Plus[A: Expr, B: Expr] (e1: A, e2: B)
implicit def ExprPlus[A: Expr, B: Expr] = new Expr[Plus[A, B]] {
    def eval(p:Plus[A, B]) = implicitly[Expr[A]].eval(p.e1) + 
                             implicitly[Expr[B]].eval(p.e2)
}
pelotom
Oh, this *seems* kind of obvious. Thank you for the answer, but his only partially solves my problem. When you can't define the implicit conversion outside of the definition of "class Plus", how can you do further operational extensions? Am I missing something here?
FloDo
Implicit conversions and values may be defined in objects and in package objects and these have a global / static characteristic that allows them to be imported into any scope. I do not know what you mean by "further operational extensions," however.
Randall Schulz
By operational extensions I refer to adding, for example, pretty-printing functionality to expressions, without modifying existing code. Like in the Haskell code I posted. Wouldn't this require a way to add implicit objects *outside* of the class definition?
FloDo
@FloDo, see my edit, I think it addresses your point.
pelotom
Now this is what I was looking for. Thank you, I was not considering using a implicit function definition. Though it solves the same problem, the solution in Haskell looks somewhat cleaner, but I guess I have to live with that.
FloDo
@FloDo: It sounds like you're looking for solutions to the Expression Problem in Scala. There has been some work done on this front. I suggest searching with appropriate terms on Google Scholar.
Randall Schulz
@FloDo: See my second edit for a marginally cleaner-looking solution... I think there is work underway to add more syntax sugar for type classes to Scala, but it will never be as pretty as Haskell ;)
pelotom
@Randall Schulz: he mentioned the expression problem in his question :)
pelotom
It would be really nice if `implicitly` was applied, well... implicitly
pelotom
It should be said that the initial solution, while admirably compact, is not particularly idiomatic Scala. Implicit conversions are almost always defined outside of the object being converted. It's also weaker than the second form, as it makes it more difficult to provide alternate conversions (e.g. the addition and multiplication Monoids over Ints, or simply alternate definitions of a PrettyPrinting instance)
Dave Griffith
@Dave Griffith: I agree, I only left it there to avoid "breaking" comments that referred to it
pelotom
Do note that this is fully strict. Case classes do not support lazy (by-name) arguments.
Apocalisp
I think the best place to put this is inside `Plus` object companion, though, of course, that doesn't need to be the case.
Daniel