object exp {

  sealed trait ExprTpe[T]
sealed trait ExprPrimitiveTpe[T] extends ExprTpe[T]
sealed trait ExprContainerTpe[T] extends ExprTpe[T] {
  def mapping: List[(String, ExprTpe[_])]
}

case class ContainerTpe2[A, B](_1: ExprTpe[A], nme1: String,  _2: ExprTpe[B], nme2: String) extends ExprContainerTpe[(A, B)] {
  override def toString = s"""Type container of ${_1} and ${_2}"""

  override val mapping = List(nme1 -> _1, nme2 -> _2)
}

case class TransformingTpe[A, B](_1: ExprTpe[A], _2: ExprTpe[B]) extends ExprTpe[Fn[A, B]] {
  override def toString = s"""Type container of ${_1} and ${_2}"""
}

case object PInt extends ExprPrimitiveTpe[Int]
case object PDouble extends ExprPrimitiveTpe[Double]
case object PFloat extends ExprPrimitiveTpe[Float]
case object PBoolean extends ExprPrimitiveTpe[Boolean]

object ExprTpe {
  implicit def pIntProvider: ExprTpe[Int] = PInt
  implicit def pDoubleProvider: ExprTpe[Double] = PDouble
  implicit def pFloatProvider: ExprTpe[Float] = PFloat
  implicit def pBooleanProvider: ExprTpe[Boolean] = PBoolean
  implicit def container2[T: ExprTpe, U: ExprTpe]: ExprContainerTpe[(T, U)] =
    ContainerTpe2(implicitly[ExprTpe[T]], "_1", implicitly[ExprTpe[U]], "_2")
  implicit def exprTpeProvider[A:ExprTpe, B: ExprTpe]: ExprTpe[Fn[A, B]] = TransformingTpe(implicitly, implicitly)
}

case class Scope(m: Map[Var[_], Exp[_]]) {
  def put[T](pair: (Var[T], Exp[T])): Scope = new Scope(m + pair)
  def apply[T](v: Var[T]): Either[String, Exp[T]] = m.get(v) match {
    case Some(exp) => Right(exp.asInstanceOf[Exp[T]])
    case None => Left(s"$v not found. Scope: $m")
  }
}
object Scope {
  def empty: Scope = Scope(Map.empty)
}

sealed trait Exp[A] {
  def tpeInfo: ExprTpe[A]
  /**
   * Either evaluate the Expression, or return an error string
   * (about missing Vars is the only thing that can go wrong)
   */
  private[exp] def run(scope: Scope): Either[String, A]
}

case class Const[A: ExprTpe](get: A) extends Exp[A] {
    override val tpeInfo = implicitly[ExprTpe[A]]

  private[exp] def run(scope: Scope) = Right(get)
}
case class Pair[A: ExprTpe, B: ExprTpe](first: Exp[A], second: Exp[B]) extends Exp[(A, B)] {
  override val tpeInfo = implicitly[ExprTpe[(A, B)]]
  private[exp] def run(scope: Scope) = for {
    a <- first.run(scope).right
    b <- second.run(scope).right
  } yield (a, b)
}

case class Apply[B: ExprTpe, A: ExprTpe](in: Exp[B], fn: Exp[Fn[B, A]]) extends Exp[A] {
  override val tpeInfo = implicitly[ExprTpe[A]]
  private[exp] def run(scope: Scope) = for {
    b <- in.run(scope).right
    f <- fn.run(scope).right
  } yield f.run(b)
}

case class Var[A: ExprTpe](name: String) extends Exp[A] {
  override val tpeInfo = implicitly[ExprTpe[A]]
  private[exp] def run(scope: Scope) = for {
    a <- scope(this).right
    result <- a.run(scope).right
  } yield result
}
case class Lambda[A: ExprTpe, B: ExprTpe](x: Var[A], result: Exp[B]) extends Exp[Fn[A, B]] {
  override val tpeInfo = implicitly[ExprTpe[Fn[A, B]]]
  private[exp] def run(scope: Scope) = Right(Fn.LambdaFn(this, scope))
}
// Private Fn class, so we can't write general scala functions
sealed trait Fn[A, B] {
  private[exp] def run(a: A): B
}



object Exp {
  // would not be here in real life, as it is an escape hatch
  // instead, we would convert the Exp to code/source that can
  // be run elsewhere
  def run[A](e: Exp[A]): Either[String, A] = e.run(Scope.empty)

  implicit class FnExp[A: ExprTpe, B: ExprTpe](val e: Exp[Fn[A, B]]) {
    def apply(a: Exp[A]): Exp[B] = Apply[A, B](a, e)
    def andThen[C: ExprTpe](that: Exp[Fn[B, C]]): Exp[Fn[A, C]] = {
      val va = Var[A]("a")
      val eb = Apply(va, e)
      val ec = Apply(eb, that)
      Lambda(va, ec)
    }
    def zip[C: ExprTpe](that: Exp[Fn[A, C]]): Exp[Fn[A, (B, C)]] = {
      val va = Var[A]("a")
      val b = Apply(va, e)
      val c = Apply(va, that)
      Lambda(va, Pair(b, c))
    }
  }
}

object Fn {

  import ExprTpe._
  def fst[A: ExprTpe, B: ExprTpe](p: Exp[(A, B)]): Exp[A] = Apply(p, lift(Fst[A, B]()))
  def snd[A: ExprTpe, B: ExprTpe](p: Exp[(A, B)]): Exp[B] = Apply(p, lift(Snd[A, B]()))

  def addInt(a: Exp[Int], b: Exp[Int]): Exp[Int] =
    Apply(Pair(a, b), lift(AddInt))

  def ifThenElse[A: ExprTpe](b: Exp[Boolean], iftrue: Exp[A], iffalse: Exp[A]): Exp[A] =
    Apply(Pair(b, Pair(iftrue, iffalse)), lift(IfThenElse[A]()))

  def select[A, B](a: Exp[A], fieldName: String): Exp[B] = {
    a.tpeInfo match {
      case container: ExprContainerTpe[_] =>
        val indx = container
          .mapping
          .indexWhere(e => e._1 == fieldName)
          require(indx >= 0)
        implicit val tpeInfoA: ExprTpe[A] = a.tpeInfo.asInstanceOf[ExprTpe[A]]

        implicit val tpeInfoB: ExprTpe[B] = container.mapping(indx)._2.asInstanceOf[ExprTpe[B]]
        Apply(a, lift(Select[A, B](indx)))
      case _ => sys.error("Should not occur, A is a container Tpe")
    }
  }
  // non fundamental ops

  def lift[A: ExprTpe, B: ExprTpe](f: Fn[A, B]): Exp[Fn[A, B]] = Const(f)
  def swap[A: ExprTpe, B: ExprTpe](p: Exp[(A, B)]): Exp[(B, A)] =
    Pair(snd(p), fst(p))

  def curry[A: ExprTpe, B: ExprTpe, C: ExprTpe](fn: Exp[Fn[(A, B), C]]): Exp[Fn[A, Fn[B, C]]] = {
    val a = Var[A]("A")
    val b = Var[B]("B")
    val pair = Pair(a, b)
    val c = Apply(pair, fn)
    val fnbc = Lambda(b, c)
    Lambda(a, fnbc)
  }
  def uncurry[A: ExprTpe, B: ExprTpe, C: ExprTpe](fn: Exp[Fn[A, Fn[B, C]]]): Exp[Fn[(A, B), C]] = {
    val pair = Var[(A, B)]("pair")
    val a = fst(pair)
    val fnbc = Apply(a, fn)
    val b = snd(pair)
    val c = Apply(b, fnbc)
    Lambda(pair, c)
  }

  // implementations
  private[exp] case class LambdaFn[A: ExprTpe, B: ExprTpe](l: Lambda[A, B], scope: Scope) extends Fn[A, B] {
    def run(a: A) = {
      val newScope = scope.put(l.x -> Const(a))
      val b = l.result.run(newScope)
      b.right.get
    }
  }
  private case class Fst[A: ExprTpe, B: ExprTpe]() extends Fn[(A, B), A] {
    def run(b: (A, B)) = b._1
  }
  private case class Snd[A: ExprTpe, B: ExprTpe]() extends Fn[(A, B), B] {
    def run(b: (A, B)) = b._2
  }
  private case object AddInt extends Fn[(Int, Int), Int] {
    def run(p: (Int, Int)) = p._1 + p._2
  }
  private case class IfThenElse[A]() extends Fn[(Boolean, (A, A)), A] {
    def run(in: (Boolean, (A, A))) = if(in._1) in._2._1 else in._2._2
  }
  private case class Select[A, B](idx: Int) extends Fn[A, B] {
    def run(in: A) = {
      val iter = in.asInstanceOf[Product].productIterator
      if (idx > 0) iter.drop(idx)
      iter.next.asInstanceOf[B]
    }
  }
}

}

/*
scala> import exp._
import exp._

scala> val c = Const(123, (245.0, 121))
c: exp.Const[(Int, (Double, Int))] = Const((123,(245.0,121)))

scala> val sel = Fn.select(Fn.select(c, "_2"), "_1")
sel: exp.Exp[Nothing] = Apply(Apply(Const((123,(245.0,121))),Const(Select(1))),Const(Select(0)))

scala> sel.tpeInfo
res37: exp.ExprTpe[Nothing] = PDouble

scala>

scala> Exp.run(Fn.select(Fn.select(c, "_2"), "_1"))
res38: Either[String,Nothing] = Right(245.0)
*/