/*
   Expression Trees, "New CSC123 Approach", Replacing the Visitor Pattern.

   Adding an element of Functional programming.

   Functional types A->B are expressed as Func<A,B>.  Types
   A*B->C are Func<A,B,C>, and Curried functions A->B->C are
   Func<A,Func<B,C>>.  Functions that do not return values (A->void)
   are of type Action<A>.
   
   Lambda terms are written x => y => x (lambda x.lambda y.x), which has
   type Func<A,Func<B,A>>. 
*/

using System;

public interface expr    // abstract interface for all expression trees
{
   void print();  // can combine with OOP approach
   // match is generic over the return type T
   T match<T>(Func<intnode,T> intf,
              Func<plusnode,T> plusf,
              Func<timesnode,T> timesf,
	      Func<divnode,T> divf,
              Func<negnode,T> negf
             );
}//expr

public class intnode : expr  // integer expreesion, or leave nodes
{
   public  int val;
   public intnode(int v) {val = v; }
   public void print() { Console.Write(val); }

   public T match<T>(Func<intnode,T> intf,
              Func<plusnode,T> plusf,
              Func<timesnode,T> timesf,
	      Func<divnode,T> divf,
              Func<negnode,T> negf
             ) { return intf(this); } // calls the correct function on this
} // intnode


public class operatornode  // interior node superclass for code sharing
{
   public expr left, right; // type of subtrees is "expr", not "node"!
   public operatornode(expr l, expr r) { left=l; right=r; }
   protected void print(String op) 
   {
	Console.Write("("+op+" ");  // prints in prefix notation "(+ 3 4)"
	left.print(); Console.Write(" ");
	right.print(); 
        Console.Write(")");
   }
} //operatornode superclass


public class plusnode : operatornode, expr     // + operator expression
{
   public plusnode(expr l, expr r) : base(l,r) {}
   public void print() { base.print("+"); }

   public T match<T>(Func<intnode,T> intf,
              Func<plusnode,T> plusf,
              Func<timesnode,T> timesf,
	      Func<divnode,T> divf,
              Func<negnode,T> negf
             ) => plusf(this);  // same as {return plusf(this);} 
} // plusnode

public class timesnode : operatornode, expr    // * operator expression
{
   public timesnode(expr l, expr r) : base(l,r)  {}
   public void print() { print("*"); }  //"base" is not needed (overloading)
   public T match<T>(Func<intnode,T> intf,
              Func<plusnode,T> plusf,
              Func<timesnode,T> timesf,
	      Func<divnode,T> divf,
              Func<negnode,T> negf
             ) => timesf(this);
} // timesnode

public class divnode : operatornode, expr    // * operator expression
{
   public divnode(expr l, expr r) : base(l,r)  {}
   public void print() { print("/"); }
   public T match<T>(Func<intnode,T> intf,
              Func<plusnode,T> plusf,
              Func<timesnode,T> timesf,
	      Func<divnode,T> divf,
              Func<negnode,T> negf
             ) => divf(this);  
} // timesnode

public class negnode : expr { // unary minus 
  public expr subexpr; // the expression being negated
  public negnode(expr s) { subexpr=s; }
  public void print() { 
    Console.Write("-("); subexpr.print(); Console.Write(")");
  }//print
   public T match<T>(Func<intnode,T> intf,
              Func<plusnode,T> plusf,
              Func<timesnode,T> timesf,
	      Func<divnode,T> divf,
              Func<negnode,T> negf
             ) => negf(this); 
}//negnode

/////////////////////////////////////////////////
public static class exprops { // operations on exprs
   public static int eval(expr e) {
      return e.match(
        intf: n => n.val,
        plusf: n => eval(n.left) + eval(n.right),
        timesf: n => eval(n.left) * eval(n.right),
        negf: n => -1 * eval(n.subexpr),
        divf: n => {
          int d = eval(n.right);
          if (d==0) throw new Exception("division by zero");
          else return eval(n.left) / d;
        }
      ); // e.match
   }//eval

   public static int size(expr e) { // number of nodes
      return e.match_op(
         Int: n => 1,
	 Binop: n => size(n.left) + size(n.right) + 1,
	 Uniop: n => size(n.subexpr) + 1
      );
   }//size

   public static string to_string(expr e) { //infix printing, functional style
     return e.match(
       intf: n=> ""+n.val,
       plusf: n => "(" + to_string(n.left) + "+" + to_string(n.right)+ ")",
       timesf: n => "(" + to_string(n.left) + "*" + to_string(n.right)+ ")",
       divf: n => "(" + to_string(n.left) + "/" + to_string(n.right)+ ")",
       negf: n =>  // avoid () around integers: -3 instead of -(3)
          n.subexpr.match(  // secondary match (not genuine pattern matching)
             intf: s => "-" + s.val,
             negf: s => to_string(s.subexpr),  // --3 cancels out to 3
             plusf: s => "-" + to_string(n.subexpr),
             timesf: s => "-" + to_string(n.subexpr),
             divf: s => "-" + to_string(n.subexpr)
          )//submatch
     );
   }//to_string


   // version of match that does not return a value

   public static void match_do(this expr e,   // "extension method"
			 Action<intnode> Int,
                         Action<plusnode> Plus,
                         Action<timesnode> Times,
                         Action<divnode> Div,
                         Action<negnode> Neg
		       ) {
      	e.match(n=> {Int(n); return 0;},
	        n=> {Plus(n); return 0; },
	        n=> {Times(n); return 0; },
	        n=> {Div(n); return 0; },
	        n=> {Neg(n); return 0; }
	       );
   }//match_do

   // version of match that unifies all binary operator nodes in
   // one clause:
   public static T match_op<T>(this expr e,
                   Func<intnode,T> Int,
		   Func<operatornode,T> Binop,
		   Func<negnode,T> Uniop) =>
      e.match(intf: Int,
              plusf: n => Binop(n),
	      timesf: n => Binop(n),
	      divf: n => Binop(n),
	      negf: Uniop);
		   
}// exprops


public class exptree3b
{
  public static void println<T>(T x) {Console.WriteLine(x);}

  public static void Main()
  {
    expr A = new plusnode(new timesnode(new intnode(2),new intnode(3)),
	                  new plusnode(new intnode(1),new intnode(4)));
    A.print();
    Console.WriteLine(" evaluates to " + exprops.eval(A));
    Console.WriteLine(" size " + exprops.size(A));
    Console.WriteLine(" prefix form: " + exprops.to_string(A));
    expr B = new plusnode(new intnode(4),new negnode(new negnode(new intnode(2))));
    string s = exprops.to_string(B);
    Console.WriteLine("B in infix form: " + s);
  } // main
}

/*
Notice that the functions inside exprops class, which was just created for
organization, are all static.  Dynamic dispatch occurs only once with
each call to .match, which invokes the correct function on the expression
type being called on.  This elminates the double-dispatch complexity of the
visitor pattern and it's convoluted syntax (v.accept(visitor)).

We can also provide variants on match, such as match_do, which 
perform an Action<T> on each node without returning a value.

The downside of this approach, however, is that we lose the ability to
easily add another type of node to design.  We would have to change
the match signature, along with how it's implemented in every single
expr subclass to accommodate the new node.  But we are able to add new
operations on exisiting nodes quite easily.  This is a general
trade-off between object oriented programming and functional
programmming.  With the latter, the type you want to define your
functions on have to be fixed.  If the type definition changes (by
adding a "modnode" for the % operator, for example), then all existing
functions become invalid.  We can't just implement a function
piecemeal.  In OOP, it's the *interface* of the objects that must be
fixed.  One can add new objects that implement the interface but it's
difficult to change the interface without changing each object.
Functional programming allows us to add new functions easily, while
OOP allows us to add new kinds of objects easily.
*/