A working implementation of Wadler's solution to the Expression Problem (http://homepages.inf.ed.ac.uk/wadler/papers/expression/expression.txt).

ExpressionProblem.scala

import scala.language.higherKinds

trait Exp[Visitor[_]] {
  def visit[R](visitor: Visitor[R]): R
}

trait VisitorF[R] {
  def forNum(n: Int): R
}

trait LangF[Visitor[R] <: VisitorF[R]] {
  class Num(n: Int) extends Exp[Visitor] {
    override def visit[R](visitor: Visitor[R]): R =
      visitor.forNum(n)
  }

  class Eval extends VisitorF[Int] {
    override def forNum(n: Int): Int = n
  }
}

class Lang extends LangF[VisitorF]

trait Visitor2F[R] extends VisitorF[R] {
  def forPlus(e1: Exp[Visitor2F], e2: Exp[Visitor2F]): R
}

trait Lang2F[Visitor[R] <: Visitor2F[R]] extends LangF[Visitor] {
  class Plus(e1: Exp[Visitor2F], e2: Exp[Visitor2F]) extends Exp[Visitor2F] {
    override def visit[R](visitor: Visitor2F[R]): R =
      visitor.forPlus(e1, e2)
  }

  class Eval extends super.Eval with Visitor2F[Int] {
    override def forPlus(e1: Exp[Visitor2F], e2: Exp[Visitor2F]): Int =
      e1.visit[Int](this) + e2.visit[Int](this)
  }

  class Show extends Visitor2F[String] {
    override def forNum(n: Int): String = n.toString

    override def forPlus(e1: Exp[Visitor2F], e2: Exp[Visitor2F]) =
      s"(${e1.visit(this)} + ${e2.visit(this)})"
  }
}

class Lang2 extends Lang2F[Visitor2F]

object Main extends App {
  val lang = new Lang
  val exp = new lang.Num(42)
  println("eval: " + exp.visit(new lang.Eval()))

  val lang2 = new Lang2
  val exp2 = new lang2.Plus(
    new lang2.Num(5), new lang2.Num(37))
  println("eval: " + exp2.visit(new lang2.Eval()))
  println("show: " + exp2.visit(new lang2.Show()))

  def apply(): Unit = main(Array.empty)
}