(* Datatype implementation of EXPR signature
   CS 131
   Based on code by Kurt M. Dresner and Chris Stone
*)

structure Expr :> EXPR =  struct

   (* In this implementation, values of type expr will be
      symbolic expressions represented as trees.
   *)
   datatype expr = X
                 | Y
                 | SinPi of expr
                 | CosPi of expr
                 | Avg   of expr * expr
                 | Times of expr * expr
                               
   (* The build functions are then just trees (in the base cases), or
      simple functions to join subtrees together into a bigger tree. *)
                
   val build_x : expr = X
   val build_y : expr = Y

   fun build_sinpi(e : expr)             = SinPi(e)
   fun build_cospi(e : expr)             = CosPi(e)    
   fun build_avg  (e1 : expr, e2 : expr) = Avg(e1,e2)
   fun build_times(e1 : expr, e2 : expr) = Times(e1,e2)
                                           
   (* A sample expression 
    *)
   val sampleExpr =   
          build_cospi(build_sinpi(build_times(build_cospi(build_avg(build_cospi
          build_x,build_times(build_cospi (build_cospi (build_avg (build_times
          (build_y,build_y),build_cospi build_x))), build_cospi (build_times 
          (build_sinpi (build_cospi build_y),build_avg (build_sinpi build_x,
          build_times (build_x,build_x))))))),build_y)))

   (* eval : expr -> real*real -> real
         Evaluator for expressions in x and y.

         This code doesn't do a very good job...please replace it!
    *)
   fun eval _ (_,_) = 0.0


   (* Finally, some code to print out expressions in a moderately
      readable format (unambiguously showing the tree, but without lots
      of unnecessary parentheses around sub-expressions 
    *)       
   local
       (* ppexpr' : expr -> unit
           Prints the given expr
        *)
       fun ppexpr' X = print "x"
         | ppexpr' Y = print "y"
         | ppexpr' (SinPi e) = (print "sin(pi*"; ppexpr' e; print ")")
         | ppexpr' (CosPi e) = (print "cos(pi*"; ppexpr' e; print ")")
         | ppexpr' (Avg(e1,e2)) = (print "avg("; ppexpr' e1; print ", ";
                                   ppexpr' e2; print ")")
         | ppexpr' (Times(e1,e2)) = (ppexpr'' e1; print " * "; ppexpr'' e2)
                                    
       (* ppexpr'': expr -> unit
            Prints the given expr, with extra parentheses (if needed) to
            make it absolutely clear where the expression begins and ends
            (if it's inside some more complex expression).
            
            For now, we only need parentheses when printing multiplications,
            to make sure we can distinguish the tree (e1 * e2) * e3 from
            the tree e1 * (e2 * e3).
        *)                                        
       and ppexpr'' (e as Times(_,_)) = (print "("; ppexpr' e; print ")")
         | ppexpr'' e = ppexpr' e
   in
      (* ppexpr : expr -> unit
           Prints the given expr, followed by a newline.
       *)
      fun ppexpr e = (ppexpr' e; print "\n")
   end (* local *)

end (* struct *)