////// Expression Trees in Kotlin, corresponding to C# programs

interface Expr
{
   fun depth():Int // depth or height of tree (length of max branch)
   // other functions could be added in a different way?
}

class Intexp(v:Int) : Expr
{
  var intval = v;  // type inferred as Int
  override fun depth():Int { return 1 }
}

// superclass of all binary operators Plus, Times, etc
open class Binop(var left:Expr, var right:Expr)
{
   fun depth(): Int
   {
      val ld = left.depth()
      val rd = right.depth()
      if (ld>rd) return ld+1; else return rd+1;
   }
}// Binop superclass


// by declaring class parameters as var/val, they become
// automatically public attributes 
class Plusexp(left:Expr, right:Expr) : Expr, Binop(left,right)
{
   // depth is inherited, "override" keyword is needed?
}

class Multexp(left:Expr, right:Expr) : Expr, Binop(left,right)
{}

// unary minus, as in 4 + -3
class Negexp(var sub:Expr) : Expr  // sub is single subexpression
{
  override fun depth():Int { return 1+sub.depth(); }
}

//// now for more functions that operates on expr, the when statement
//// syntactically improves upon the switch statement significantly:

fun eval(e:Expr):Int
{
   when (e)
   {
    is Intexp -> return e.intval; // no need to typecast again!
    is Plusexp  -> return eval(e.left) + eval(e.right);
    is Multexp  -> return eval(e.left) * eval(e.right);     
    is Negexp   -> return -1 * eval(e.sub);
    else -> throw RuntimeException("illegal expression");
   }//when(e)
     // Not bad, but it's still limited...
}//eval function

fun printexp(e:Expr)
{
   when (e)
   {
    is Intexp -> print(e.intval)
    is Plusexp  ->
       { print("(+ "); printexp(e.left);
         print(" "); printexp(e.right); print(")"); }
    is Multexp  ->
       { print("(* "); printexp(e.left);
         print(" "); printexp(e.right); print(")"); }    
    is Negexp   ->
       { print("-"); printexp(e.sub); }
    else -> println()
   }//when(e)
}//printexp


fun main(argv:Array<String>)
{
    var A:Expr =
    	Plusexp(Multexp(Intexp(2),Intexp(3)),Plusexp(Intexp(1),Intexp(4)));

    println(A.depth());
    println( eval(A) );
    printexp(A);  println();

    // testing new feature defined below:
    var B:Expr = Plusexp(Intexp(2),Divexp(Intexp(6),Intexp(2)));
    print ( eval2(B) ); // doesn't work!  throws runtime exception
}//main

/*
The when construct looks better than if-else or switch.  In particular,
in Java/C# even after I check the type of an expression using "is" or
"instanceof" I still would need to typecast:

   if (e is Intexp) return ((Intexp)e).intval;

It might seem that the when construct is a much easier way to add new
operations on expression trees compared to the visitor pattern, but we still
need to consider the following issues:

   1.  If one of the when conditions (say for Multexp) was missing, it would
   NOT be a compiler error, and in fact might not even be a runtime error
   (depending on how the else -> clause of the when was written).
   In constrast, with the Visitor Pattern if you forgot to implement one
   of the visit functions inside a visitor class, you would get a
   COMPILER ERROR.  This is a rather signficant difference!

   2. What if we want to add a new kind of expression, say Divexp to
   this framework?  How do we extend the existing code modularly?
*/

class Divexp(left:Expr, right:Expr) : Expr, Binop(left,right)
{}

// How to define new versions of print, eval that reuses the existing code?
// We might try this (which won't work):

fun eval2(e:Expr):Int
{
   when (e)
   {
     is Divexp -> return eval2(e.left) / eval2(e.right);
     else -> return eval(e); // call original eval
   }
}

// Why doesn't this work? Because the recursive calls made by eval will
// call eval, not eval2, so if you have a Div subexpression of Plusexp
// it will not know how to evaluate it: 
//  var B:Expr = Plusexp(Intexp(2),Divexp(Intexp(6),Intexp(2))); // 2+(6/2)
//  print ( eval2(B) ); // throws exception.

// Any existing function that calls eval will have to be changed to call
// eval2 in order for the "extension" to take effect.
// The eval method itself has to change.  Compare this to how we
// can add a new kind of expression to the visitor pattern: although
// we had to write some odd looking code that involves the use of
// "if .. is .."  it is still much easier to extend an existing
// visitor with a new ability (to visit Divexp).

// It is possible to change eval (without defining a new eval2)
// by using pointers to functions and simulating the dynamic scoping
// of functions - but that's a SUBVERSIVE IDEA!

// Finally, the when construct does not go far enough in terms of pattern
// matching.  That is, it is still looking at one object at a time,
// not multiple objects, not objects within objects...
// We'd really like to write (in eval):

//  is Plusexp(x,Negexp(y)) -> return eval(x) - eval(y);  //NO WAY!
//  is Negexp(Intexp) -> return -1 * e.sub.intval;  //NO CHANCE

// Without these extended abilities, the when construct is still
// just a glorified if-else.