package interpreter;

///////////////////////////////////////////////////////////////////////////////
//
//                          Symbolic expressions
//
///////////////////////////////////////////////////////////////////////////////

public abstract class Expr<T> {
  // Do one step of evaluation
  public step(env: Env<T>): Expr<T>;

  // Perform a full step-by-step evaluation
  public eval(env: Env<T>): ();

  // Variable constructor (generic)
  public static variable<U>(name: String): VarExpr<U>;
  
  // Constant constructor (generic)
  public static constant<U>(value: U): CstExpr<U>;
  
  // Sum constructor (floats)
  public static plus<U: float>(e1: Expr<U>, e2: Expr<U>): Expr<U>;
  
  // Multiplication constructor (floats)
  public static mult<U: float>(e1: Expr<U>, e2: Expr<U>): Expr<U>;
  
  // Concatenatio constructor (strings)
  public static concat(e1: Expr<String>, e2: Expr<String>): Expr<String>;

  // Return true if the expression is evaluated (i.e., is a constant)
  evaluated(): boolean;
}

///////////////////////////////////////////////////////////////////////////////
//
//                           Implementation
//
///////////////////////////////////////////////////////////////////////////////

// Constant expressions (visible only at the package level)
class CstExpr<T> extends Expr<T> {
  value: T;
}

// Function applications (visible only at the package level)
class AppExpr<T> extends Expr<T> {
  f: Functor<T>;
  args: Expr<T>[f.arity];
}

// Variables (visible only at the package level)
class VarExpr<T> extends Expr<T> {
  name: String;
}

// Functors (visible only at the package level)
class Functor<T> {
  name: String;
  arity: int;
  eval: fun(CstExpr<T>[]): CstExpr<T>;
}

// Generic display of expressions
toString@VarExpr() = name;
toString@Functor() = name;
toString@CstExpr() = (value instanceof String ?
                      format("\"%a\"", value) :
                      format("%a", value));
toString@AppExpr() = format("%a(%s)", f, str[f.arity])
{
  str = ["", args[0].toString(), i -> format("%s, %a", str[i-1], args[i-1])];
}

// Evaluated expressions
evaluated@Expr() = (this instanceof CstExpr);
  
// Perform one step of evaluation
step@CstExpr<T>(env) = this;
step@VarExpr<T>(env) = env.lookup(name);
step@AppExpr<T>(env) = result
{
  // Number of arguments
  n = f.arity;
  
  // Checks that the arguments args[0],..., args[i-1] are evaluated
  evaluated = [true, i -> evaluated[i-1] && args[i-1].evaluated()];

  if (evaluated[n]) {
    // Apply the functor operation on the evaluated arguments
    var args' = [i -> (CstExpr) args[i]];
    result = f.eval(args': CstExpr<T>[n]);
  } else {
    // Evaluate the first non-evaluated argument
    var args' = [i -> (evaluated[i] && !args[i].evaluated() ?
                       args[i].step(env) : args[i])];
    result = clone(args = args': Expr<T>[n]);
  }
}

// Full step-by-step evaluation
eval@Expr<T>(env) = ()
{
  @ print("{%a}\n -> %a\n%s\n", env, this, eval(this));
  
  fun eval(x: Expr<T>) = (x'.evaluated() ?
                          format(" -> %a", x') :
                          format(" -> %a\n%s", x', eval(x')))
  {
    x' = x.step(env);
  }
}

// Variable constructor (generic)
Expr.variable(name) = new VarExpr(name = name);

// Constant constructor (generic)
Expr.constant(value) = new CstExpr(value = value);

// Expression constructors (floats)
Expr.plus(e1, e2) = new AppExpr(f = f, args = [e1, e2])
{
  f = new Functor(name = "plus", arity = 2, eval = eval);
  fun eval(args) = Expr.constant(args[0].value + args[1].value);
}

Expr.mult(e1, e2) = new AppExpr(f = f, args = [e1, e2])
{
  f = new Functor(name = "mult", arity = 2, eval = eval);
  fun eval(args) = Expr.constant(args[0].value * args[1].value);
}

// Expression constructors (strings)
Expr.concat(e1, e2) = new AppExpr(f = f, args = [e1, e2])
{
  f = new Functor(name = "concat", arity = 2, eval = eval);
  fun eval(args) = Expr.constant(format("%s%s", args[0].value, args[1].value));
}