trait Lambda {
  trait Exp[T]
  case class Const[T](t: T) extends Exp[T]
  case class App[S, T](fun: Exp[S => T], arg: Exp[S]) extends
    Exp[T]
  case class Fun[S, T](body: Exp[S] => Exp[T]) extends Exp[S => T]
}

trait LamExamples extends Lambda {
  val term1 = App(Fun((x: Exp[Int]) => x), Const(1))
  //val termWrong = Fun((x: Exp[Int]) => App(x, Const(1))) //@ \label{ln:termwrong}
  //termWrong gives a type error
}

trait Interp extends Lambda {
  def eval[T](term: Exp[T]): T =
    term match {
      case Const(t) => t //@ \label{ln:matchconst}
      case App(fun, arg) => //@ \label{ln:matchapp}
        eval(fun) apply eval(arg)
      case f: Fun[s, t] => //@ \label{ln:matchfun}
        (x: s) => eval(f.body(Const(x))) //@ \label{ln:handlefun}
    }
}

trait Nums extends Lambda with Interp {
  case class Plus(a: Exp[Int], b: Exp[Int]) extends Exp[Int]

  override def eval[T](term: Exp[T]): T =
    term match {
      case p @ Plus(a, b) =>
        eval(a) + eval(b)
      case _ => //@ \label{ln:default}
        super.eval(term)
    }
}

trait BetaReduce extends Lambda {
  def betaReduce[T](term: Exp[T]): Exp[T] =
    term match {
      case App(Fun(f), arg) => f(arg)
      case e => e
    }
}

trait Consts {
  trait Exp[+T]
  case class Const[T](t: T) extends Exp[T]
  def eval[T](term: Exp[T]): T =
    term match {
      case Const(t) => t  //@ \label{ln:fail1}
    }
}

object Unsound extends Consts {
  class UnsoundConst(t: String) extends Const[Any](t) with
    Exp[Boolean]
  val unsoundTerm1 = new UnsoundConst("")
  val unsound1 = eval(unsoundTerm1) //@ \label{ln:fail2}
}

object Rebuild extends Consts {

def rebuild[T](term: Exp[T]): Exp[T] =
  term match {
    case Const(t) => Const(t)
  }

}

trait LambdaUpcast extends Lambda {
  case class Upcast[U, T <: U](e: Exp[T]) extends Exp[U] //@ \label{ln:UpClass}
  implicit def upcast[U, T <: U](e: Exp[T]): Exp[U] = Upcast(e)//@ \label{ln:UpConv}
}

trait BetaReduceSub extends LambdaUpcast {
  def betaReduce[T](term: Exp[T]): Exp[T] =
    term match {
      case App(Fun(f), arg) => f(arg)
      case App(Upcast(Fun(f)), arg) => f(arg)
      case e => e
    }
}

trait LambdaInterpFinal {
  trait Exp[+T]

  final case class Const[T](t: T) extends Exp[T]
  final case class App[S, T](fun: Exp[S => T], arg: Exp[S])
    extends Exp[T]
  final case class Fun[S, T](body: Exp[S] => Exp[T])
    extends Exp[S => T]

  def eval[T](term: Exp[T]): T =
    term match {
      case Const(t) => t
      case App(fun, arg) =>
        eval(fun) apply eval(arg)
      case f: Fun[s, t] =>
        (x: s) => eval(f.body(Const(x)))
    }
}

trait Compared extends Consts {
  class UnsoundConst(t: String) extends Const[Any](t) with
    Exp[Boolean]
  class SoundConst(t: String) extends Const[Any](t)
}