GADT in Swift

GADT.swift

/// A type equality guarantee is capable of safely casting one value to a
/// different type. It can only be created when `S` and `T` are statically known
/// to be equal.
struct TypeEqualityGuarantee<S, T> {
  private init() {}

  /// Safely cast a value to the other type.
  func cast(_ value: T) -> S {
    return value as! S
  }

  /// Safely cast a value to the other type.
  func cast(_ value: S) -> T {
    return value as! T
  }
}

// The same-type constraint guarantees that `TypeEqualityGuarantee` is only
// constructed when `S` is statically known to be equal to `T`.
extension TypeEqualityGuarantee where S == T {
  // Creates a type equality guarantee.
  init() {}
}

/// Lifted arithmetic operators
enum Arithmetic<T : BinaryInteger> {
  case add, subtract, multiply, divide

  subscript(x: T, y: T) -> T {
    switch self {
    case .add: return x + y
    case .subtract: return x - y
    case .multiply: return x * y
    case .divide: return x / y
    }
  }
}

/// Lifted comparison operators
enum Comparator<T : Comparable> {
  case greaterThan, lessThan, equal

  subscript(x: T, y: T) -> Bool {
    switch self {
    case .greaterThan: return x > y
    case .lessThan: return x < y
    case .equal: return x == y
    }
  }
}

/// Expression
indirect enum Expression<T> {
  case number(TypeEqualityGuarantee<T, Int>, Int)
  case bool(TypeEqualityGuarantee<T, Bool>, Bool)
  case arithmetic(TypeEqualityGuarantee<T, Int>, Arithmetic<Int>, Expression<Int>, Expression<Int>)
  case compare(TypeEqualityGuarantee<T, Bool>, Comparator<Int>, Expression<Int>, Expression<Int>)
  case negate(TypeEqualityGuarantee<T, Bool>, Expression<Bool>)
}

extension Expression {
  static func number(_ x: Int) -> Expression<Int> {
    return .number(TypeEqualityGuarantee(), x)
  }
  static func bool(_ b: Bool) -> Expression<Bool> {
    return .bool(TypeEqualityGuarantee(), b)
  }
  static func arithmetic(_ operator: Arithmetic<Int>,
                         _ lhs: Expression<Int>,
                         _ rhs: Expression<Int>) -> Expression<Int> {
    return .arithmetic(TypeEqualityGuarantee(), `operator`, lhs, rhs)
  }
  static func compare(_ comparator: Comparator<Int>,
                      _ lhs: Expression<Int>,
                      _ rhs: Expression<Int>) -> Expression<Bool> {
    return .compare(TypeEqualityGuarantee(), comparator, lhs, rhs)
  }
  static func negate(_ x: Expression<Bool>) -> Expression<Bool> {
    return .negate(TypeEqualityGuarantee(), x)
  }
}

extension Expression {
  func evaluated() -> T {
    switch self {
    case let .number(proof, n):
      return proof.cast(n)
    case let .bool(proof, b):
      return proof.cast(b)
    case let .arithmetic(proof, arith, n1, n2):
      return proof.cast(arith[n1.evaluated(), n2.evaluated()])
    case let .compare(proof, comp, n1, n2):
      return proof.cast(comp[n1.evaluated(), n2.evaluated()])
    case let .negate(proof, n1):
      return proof.cast(!n1.evaluated())
    }
  }
}

/// Simple expression
let expr1 = Expression<Bool>.compare(.equal, .number(10), .number(30))
print(expr1.evaluated()) /// => false
let expr2 = Expression<Int>.arithmetic(.add, .number(10), .number(20))
print(expr2.evaluated()) /// => 30

Static type check:

let expr3 = Expression.compare(.equal, .number(10), .bool(false))

error: member 'bool' in 'Expression<Int>' produces result of type 'Expression<Bool>', but context expects 'Expression<Int>'
let expr3 = Expression.compare(.equal, .number(10), .bool(false))
                                                     ^