module Exprs { 
 
  // Overview: Expression Problem 
 
  // The following example illustrates the expression problem 
  // In a nutshell, how is it to add new types, and new behavior? 
 
  // Define `Expr` type and some instances 
 
  // Expr type 
  union Expr { 
    ...             // ... indicates the types in this union will be defined elsewhere 
  } 
 
  // The Add Expr, used for + 
  ref struct Add { 
    left : Expr; 
    right : Expr; 
  } 
 
  // The Lit Expr, used for numbers 
  ref struct Lit { 
    value : int; 
  } 
 
  // Extend Expr union with Add and Lit 
  union ...Expr { 
    Add | Lit 
  } 
 
  // Define `Eval` interface, and implement 
 
  // Eval interface 
  interface Eval { 
    eval() : int; 
  } 
 
  // Implement Eval interface for Lit and Add types 
  impl Eval { 
 
    // implement eval of Eval interface for Lit 
    eval(this : Lit) : int => { 
      return this.value; 
    } 
 
    // implement eval of Eval interface for Add 
    eval(this : Add) : int => { 
      let eval_left = this.left::Eval; 
      let eval_right = this.right::Eval; 
      return eval_left.eval() + eval_right.eval(); 
    } 
  } 
 
  fn test1() { 
    // Create an expression: (1 + 2) + 3 
    let expr =  
      Add( 
        Add(Lit(1), Lit(2)), 
        Lit(3) 
      ); 
 
    // cast expression to Eval interface and evaluate using eval method 
    let result = expr::Eval.eval(); 
    print(result);  // prints 6 
  } 
 
  // Add another instance of `Expr` 
 
  // The Mul Expr, used for * 
  struct Mul { 
    left : Expr; 
    right : Expr; 
  } 
 
  // Extend Expr union with Mul type 
  union ...Expr { 
    Mul 
  } 
 
  impl Eval { 
 
    // Implement eval of Eval interface for Mul 
    eval(this : Mul) : int => { 
      let eval_left = this.left::Eval; 
      let eval_right = this.right::Eval; 
      return eval_left.eval() * eval_right.eval(); 
    } 
  } 
 
  fn test2() { 
    // Create an expression: (1 + 2) * 3 
    let expr =  
      Mul( 
        Add(Lit(1), Lit(2)), 
        Lit(2) 
      ); 
 
    // cast expression to Eval interface and evaluate using eval method 
    let result = expr::Eval.eval(); 
    print(result);  // prints 9 
  } 
   
  // add new behavior and implement for all `Expr` types 
 
  // define Print interface used to print an Expr 
  interface Print { 
    print(); 
  } 
 
  // implement Print for each type 
  impl Print { 
 
    // implement Print for Lit type 
    print(this : Lit) { 
      print(this.value); 
    } 
 
    // implement Print for Mul type 
    print(this : Mul) { 
      print("("); 
      this.left::Print.print(); 
      print(" * "); 
      this.right::Print.print(); 
      print(")"); 
    } 
 
    // implement Print for Add type 
    print(this : Add) { 
      print("("); 
      this.left::Print.print(); 
      print(" + "); 
      this.right::Print.print(); 
      print(")"); 
    } 
  } 
 
  fn test3() { 
    // Create expression: (1 + 2) * 3 
    let expr =  
      Mul( 
        Add(Lit(1), Lit(2)), 
        Lit(2) 
      ); 
 
    // cast expression to Print interface and call print 
    expr::Print.print();  // prints ((1 + 2) * 3) 
  } 
   
  // Adding helper implementations 
 
  // The following demonstrates creating a helper implementation 
  // of the Eval interface that can be used for types which 
  // are Binary, e.g. they operate on a left and right expression 
   
  // define BinaryEval interface implemented by binary expression 
  interface BinaryEval { 
    left.get() : Expr;                      // property getter for left expression 
    right.get() : Expr;                     // property getter for right expression 
    eval(left : int, right : int) : int;    // binary eval given integers 
  } 
 
  // define binary helper type 
  struct BinaryImpl { 
    binary : BinaryEval;    // helper is based on BinaryEval interface 
  } 
 
  impl Eval { 
 
    // implement eval for binary helper 
    eval(this : BinaryImpl) : int => { 
      // get left and right expressions using BinaryEval interface and eval them 
      const left = this.binary.left::Eval.eval(); 
      const right = this.binary.right::Eval.eval(); 
 
      // combine left and right using BinaryEval interface 
      return this.binary.eval(left, right); 
    } 
     
  } 
 
  // Add new type and use helper implementation 
 
  // Mod Expr type, used for % 
  struct Mod { 
    // add left and right fields based on getters in BinaryEval interface 
    ...BinaryEval; 
  } 
 
  impl BinaryEval { 
 
    // implement BinaryExpr getters for left and right 
    ...Mod; 
 
    // implement BinaryEval for Mod 
    eval(this : Mod, left : int, right : int) : int => { 
      return left % right; 
    } 
  } 
 
  impl Eval { 
 
    // use BinaryImpl helper to implement eval for Mod 
    constructor(this : Mod) : BinaryImpl => { 
      return BinaryImpl(this::BinaryEval); 
    } 
  } 
 
  fn test4() { 
    // Create expression: ((1 + 2) * 3) % 2 
    let expr =  
      Mod( 
        Mul( 
          Add(Lit(1), Lit(2)), 
          Lit(2) 
        ), 
        Lit(2) 
      ); 
 
    // cast expr to Eval interface and call eval 
    let result = expr::Eval.eval(); 
    print(result);                  // prints 1 
  } 
 
 
}