App.scala

import Expr._
import Pattern._
import Value._

trait Expr

object Expr {
  case class Var(name: String) extends Expr
  case class Val(value: Any, args: List[Expr]) extends Expr
  case class Function(arg: Var, body: Expr) extends Expr
  case class Letrec(bindings: List[(Var, Function)], body: Expr) extends Expr
  case class Apply(body: Expr, arg: Expr) extends Expr
  case class Case(pattern: Pattern, body: Expr) extends Expr
  case class Match(arg: Expr, cases: List[Case]) extends Expr
}


sealed trait Pattern

object Pattern {
  case class ValP(value: Any, args: List[Pattern]) extends Pattern
  case class VarP(name: String) extends Pattern
}


sealed trait Value

object Value {
  case class ValV(x: Any, xs: List[Value]) extends Value
  case class ThunkV(expr: Expr, var env: Environment) extends Value
}


case class Environment(maps: Map[String, Value]) {
  def set(t: (String, Value)): Environment = Environment(maps + t)

  def get(name: String): Value = maps(name)
}

object Interpreter {

  def interp(e: Expr, env: Environment = Environment(Map())): Value = e match {
    case Var(name) => env.get(name)
    case Val(value, args) => ValV(value, args.map(x => force(interp(x, env))))

    case Letrec(bindings, body) =>
      val env1 =
        bindings.foldLeft(env)((e, a) => e.set(a._1.name -> ThunkV(a._2, null)))
      bindings.foreach(b => env1.get(b._1.name).asInstanceOf[ThunkV].env = env1)
      interp(body, env1)

    case Function(arg, body) => ThunkV(Function(arg, body), env)

    case Match(arg, cases) =>
      val value = force(interp(arg, env))
      val result =
        cases
          .toStream
          .map(c => (c.body, doMatch(value, c.pattern, env)))
          .find(c => c._2 != null)
          .getOrElse(throw new Exception(s"Match exception, could not match $value with any of the case clauses"))

      interp(result._1, result._2)

    case Apply(b, arg) => interp(b, env) match {
      case ThunkV(Function(param, body), closureEnv) =>
        val env1 = closureEnv.set(
          param.asInstanceOf[Var].name -> interp(arg, env)
        )
        interp(body, env1)
    }
  }


  def force(value: Value): Value = value match {
    case ThunkV(expr, env) => force(interp(expr, env))
    case v => v
  }

  def doMatch(left: Value, right: Pattern, env: Environment): Environment = {
    if (env == null)
      return null

    (left, right) match {
      case (ValV(l, ls), ValP(r, rs)) if l.equals(r) => ls.zip(rs).foldLeft(env)((e, t) => doMatch(t._1, t._2, e))
      case (v @ ValV(_, _), VarP(name)) => env.set(name -> v)
      case _ => null
    }
  }
}


object App {
  def main(args: Array[String]): Unit = {

    // Lists
    val list1 =
      Val("Cons", List(Val("Num", List(Val(1, List()))),
        Val("Cons", List(Val("Num", List(Val(2, List()))),
          Val("Empty", List())))))
    val list2 =
      Val("Cons", List(Val("Num", List(Val(3, List()))),
        Val("Cons", List(Val("Num", List(Val(4, List()))),
          Val("Cons", List(Val("Num", List(Val(5, List()))),
            Val("Empty", List())))))))

    val code = Letrec(
      List(
        (Var("append"), Function(Var("x"), Function(Var("ys"), Match(Var("x"), List(
          Case(ValP("Empty", Nil), Var("ys")),
          Case(ValP("Cons", List(VarP("a"), VarP("as"))), Val("Cons", List(Var("a"), Apply(Apply(Var("append"), Var("as")), Var("ys")))))
        )))))
      ),
      Apply(Apply(Var("append"), list1), list2)
    )

    println(formalized(Interpreter.interp(code)))
  }

  def formalized(value: Value): String = value match {
    case ValV(x, Nil) => x.toString
    case ValV(x, xs) => s"$x(${xs.map(formalized).mkString(", ")})"
    case x => x.toString
  }
}