Compute: A very simple language for addition/substraction.

Compute.scala

import scala.util.parsing.combinator._
import scala.util.matching._

object Compute {
  sealed trait Expression

  object Expression {
    case class Literal(value: Int) extends Expression
    case class Apply(operator: Operator, lhs: Expression, rhs: Expression) extends Expression

    sealed trait Operator
    object Operator {
      case object Minus extends Operator
      case object Plus extends Operator
    }
  }

  import Expression._
  import Operator._

  object Parser extends RegexParsers {
    def parse(input: String): Either[String, Expression] = parseAll(apply, input) match {
      case Success(expression, _) => Right(expression)
      case NoSuccess(msg, input) => Left(s"${input.pos}: $msg")
    }

    private val operators = Map(Minus -> "-", Plus -> "+")

    private def apply: Parser[Expression] = (literal ~ (operator ~ literal).*).map {
      case x    ~ Nil                 => x
      case lhs  ~ ((op ~ rhs) :: xs)  => xs.foldLeft(Apply(op, lhs, rhs)) { case (e, (op ~ rhs)) => Apply(op, e, rhs) }
    }

    private def literal: Parser[Literal] = ("\\d+"r).map(_.toInt).map(Literal(_))
    private def operator: Parser[Operator] = operators.map { case (op, sym) => literal(sym).map { _ => op } }.reduce(_ | _)
  }

  object Interpreter {
    def eval: Expression => Int = _ match {
      case Apply(op, lhs, rhs) => operators(op)(eval(lhs), eval(rhs))
      case Literal(value)      => value
    }

    private val operators = Map[Operator, (Int, Int) => Int](Minus -> (_ - _), Plus -> (_ + _))
  }

  def apply(expression: String): Either[String, Int] = Parser.parse(expression).right.map(Interpreter.eval)
}