Generics (F-bound type) approach

f-bound-type-encoding.cs

namespace ExpressionProblem {
  using System;

  interface Exp<E> where E: Exp<E> { }

  class Int<E>: Exp<E> where E: Exp<E> {
    public int Value { get; set; }
  }
  class Add<E>: Exp<E> where E: Exp<E> {
    public E Operand0 { get; set; }
    public E Operand1 { get; set; }
  }

  interface EvalExp<E> : Exp<E> where E: EvalExp<E> {
    int Eval();
  }

  class EvalInt<E>: Int<E>, EvalExp<E> where E: EvalExp<E> {
    int EvalExp<E>.Eval() {
      return this.Value;
    }
  }

  class EvalAdd<E>: Add<E>, EvalExp<E> where E: EvalExp<E> {
    int EvalExp<E>.Eval() {
      return this.Operand0.Eval() + this.Operand1.Eval();
    }
  }

  interface EvalExpFix : EvalExp<EvalExpFix> { }
  class EvalIntFix : EvalInt<EvalExpFix>, EvalExpFix { }
  class EvalAddFix : EvalAdd<EvalExpFix>, EvalExpFix { }

  class Program {
    static void Main(String[] argv) {
      Console.WriteLine(((EvalExpFix)(new EvalAddFix() {
        Operand0 = new EvalIntFix() { Value = 100 },
        Operand1 = new EvalIntFix() { Value = 200 }
      })).Eval());
    }
  }
}