DiscriminatedUnion Protocol

I've had this idea for a while but have been distracted by a great many things.

My hand has been forced, a little, by Extract Payload for enum cases having associated value - #140 by gwendal.roue. I consider this a possible alternative. I admit that I've stopped following the thread consistently but I've checked in on the thread every now and then.

Motivation

There are times when you need to construct a decision tree about and enum well before you have an instance of that enum. Consider a state machine and describing valid transitions between states. As a developer, it would be useful to describe, without considering any associated value, which state transitions are valid.

Another benefit of using a protocol is that it provides a consistent way to add more pattern matching capabilities to non-enum types.

The heart of my pitch is:

protocol DiscriminatedUnion {
    associatedtype Discriminant : Equatable, CaseIterable // as an aside, it would really be nice if we could mark a protocol as being restricted to enums much like we can with classes. failing that, restricted to types with value semantics.

    var discriminant: Discriminant { get }
}

Synthesis for enums marked with DiscriminatedUnion would look like

enum TrainStatus: DiscriminatedUnion {
    case onTime
    case early(minutes: UInt)
    case delayed(minutes: UInt, reason: String)
    case cancelled(String)
}


// Synthesized
extension TrainStatus {
    enum Discriminant : Hashable {
        case onTime
        case early
        case delayed
        case cancelled
    }

    var discriminant: Discriminant { … }
}

The way in which this could be an alternative to the proposed payload solution is that one more level of types could be introduced nested inside Discriminant. One type for each case. I haven't settled on a convention for converting labels but a leading underscore should work for now

extension TrainStatus {
    extension Discriminant {
        enum OnTime {
        // might not actually need any cases. Empty enum can serve as a namespace

            static func payload(from instance: TrainStatus) -> Void? // this is optional to handle instances that do not match `onTime`
        }

        enum Early_minutes {
            static func payload(from instance: TrainStatus) -> Int? 
        }

        enum Delayed_minutes_reason {
            static func payload(from instance: TrainStatus) -> (minutes: UInt, reason: String)?
        }

        enum Cancelled_reason {
            static func payload(from instance: TrainStatus) -> String?
        }
    }
}

This would allow a state machine to be described (Thanks to @harlanhaskins for this example—which does, in fact, work right now! Try it out!)

protocol DiscriminatedUnion {
  associatedtype Discriminator: Equatable where Discriminator: CaseIterable
  var discriminant: Discriminator { get }
}

extension DiscriminatedUnion {
  func `is`(_ Discriminator: Discriminator) -> Bool {
    return discriminant == Discriminator
  }
}

struct StateMachine<State: DiscriminatedUnion> where State.Discriminator: Hashable {
  enum Error: Swift.Error {
    case invalidTransition(from: State, to: State)
  }
  let transitions: [State.Discriminator: Set<State.Discriminator>]
  private(set) var state: State

  init(
    _ initialState: State,
    validTransitions: [State.Discriminator: Set<State.Discriminator>]
  ) throws {
    self.state = initialState
    self.transitions = validTransitions
  }

  mutating func transition(to newState: State) throws {
    let states = transitions[state.discriminant]!
    guard states.contains(newState.discriminant) else {
      throw Error.invalidTransition(from: state, to: newState)
    }
    state = newState
  }
}

enum LoadingState<T>: DiscriminatedUnion {
  case notLoaded, loading(Double), loaded(T)

  enum Discriminator: Hashable, CaseIterable {
    case notLoaded, loading, loaded
  }

  var discriminant: Discriminator {
    switch self {
    case .notLoaded: return .notLoaded
    case .loading: return .loading
    case .loaded: return .loaded
    }
  }
}

var loadingMachine =
  try StateMachine<LoadingState<Int>>(
    .notLoaded,
    validTransitions: [
      .notLoaded: [.loading],
      .loading: [.loading, .loaded],
      .loaded: []
    ]
  )

try loadingMachine.transition(to: .loading(50))
try loadingMachine.transition(to: .notLoaded)

Future Direction

This could provide a path for improving pattern matching on structs. Either with something along the lines active patterns mentioned by @Joe_Groff or—in certain circumstances—providing a compile time exhaustivity check (when the struct is proven to be composed entirely of types that can be checked for exhaustivity).

6 Likes

I presume TrainStatus.onTime == TrainStatus.Discriminant.onTime? Also, could you elaborate more about what associatedValue is? Is it specific to this protocol or is it a new language feature?

That… was a typo. Thank you!. associatedtype

TrainStatus.onTime corresponds to TrainStatus.Discriminant.OnTime but they aren't equal in any reasonable way that I can think of. (I'm not criticizing the question, I just don't want to muddy the waters.)

1 Like

I had, originally, left out the original motivating property (trying to jump right to how it could encompass the payload issue) . That should actually make it clearer what the connection is.

How would you handle overloaded enums?

I'll be clearer:

enum TrainStatus: DiscriminatedUnion {
    case onTime
    case early(minutes: UInt)
    case early(hours: UInt)
    case delayed(minutes: UInt, reason: String)
    case delayed(hours: UInt, reason: String)
    case cancelled(String)
}

What would be the discriminant in this case?

That's what I was hinting at with the underscores. Currently, it is a brute force name transform where the leading parenthesis and : characters are replaced with an underscore. I am not committed to this as the convention… I just think that it can be as simple as this.

extension TrainStatus {
    extension Discriminant {
        enum OnTime {
        // might not actually need any cases. Empty enum can serve as a namespace

            static func payload(from instance: TrainStatus) -> Void? // this is optional to handle instances that do not match `onTime`
        }

        enum Early_minutes {
            static func payload(from instance: TrainStatus) -> Int? 
        }

        enum Early_hours {
            static func payload(from instance: TrainStatus) -> Int? 
        }

        enum Delayed_minutes_reason {
            static func payload(from instance: TrainStatus) -> (minutes: UInt, reason: String)?
        }

        enum Delayed_hours_reason {
            static func payload(from instance: TrainStatus) -> (hours: UInt, reason: String)?
        }

        enum Cancelled_reason {
            static func payload(from instance: TrainStatus) -> String?
        }
    }
}

The benefits of KeyPaths and my pitched solution is that the "discriminant" (in my pitch the pattern, and in Stephen pitch the KeyPath) hold all the informations needed to understand which the result type would be, coming from which case. Discriminant is a separate enum, and has no informations for root or return type. I think this proposal has potential, but it needs some more work.

The barrier that I see is a smooth way to provide the corresponding nested type from an instance of discriminant. I'd avoided it to keep the compiler magic aspect low but, yes, it would be nice.

My solution has compiler magic to zero and it works today (I've built a library that works already), but it objectively has limits. I use Mirror in my pitch, which really isn't the way when it comes to language level feature. Compiler is needed to have something like this, whichever solution we will decide to pursue. :slight_smile:

What would the result be for the following enum?

enum E {
    case foo(bar: Int)
    case foo_bar
}

How about something like F#'s active patterns, which are a way of defining custom mutually-exclusive conditions for pattern matching purposes? You could think of them as being "computed cases", a list of mutually exclusive cases whose value is determined by an associated block of code:

struct ErrorCode {
  // 0 if success, <0 if failure
  var value: Int

  // A computed case that lets you pattern match an ErrorCode
  case ok, error(code: Int) {
    assert(value <= 0)
    if value == 0 { return ok }
    return error(code: value)
  }
}

func handleError(code: ErrorCode) throws {
  switch code {
  case .ok: return
  case .error(let code): throw ErrorCodeError(code)
  }
}
17 Likes

+1. I have wanted something like this for a long time.

3 Likes

right now? my answer would probably be some sort of diagnostic and requiring that you write your own discriminant and lose synthesis. This isn't the interesting part of the proposal, in my opinion. Overloading on base names isn't completely supported, I think and–when/if it is—coming up with some transformation rules seems manageable.

I found an older thread that is relevant to the idea of active patterns: Generalized pattern matching. The example in that thread was based on functional-style list destructuring. I like your syntax better than what I had come up with in that thread. The example might look something like this:

extension Collection {
    case empty, element(Element, rest: SubSequence) {
        if self.isEmpty { 
           return empty
        } else {
           let secondIndex = self.indexAfter(self.startIndex)
           return element(self[self.startIndex], self[secondIndex..<endIndex])
        }
    }
}

I like the idea but I don't understand what it helps with in the proposal…

I might be unclear on what problem you're trying to solve with the proposal. The impression I got was that you wanted some means of introducing discriminators onto arbitrary types, or mapping new discriminators onto enums besides their "fundamental" discriminator.

ah, I have to reconstruct the original motivator that I had but the short explanation is that matching on the 'fundamental' discriminator sometime requires creating an instance of the enum when that isn't desirable.

You haven't showed what you want to do with the synthesized discriminator enum. I'm curious what the use case is.

I have synthesized discriminator enums like this for encoding / decoding purposes but don't recall seeing any other use cases. I think there are other language features that would address the encoding / decoding use case more directly so I don't see that as a strong motivator for this feature. And fwiw, in the encoding / decoding use case I have needed control of the discriminator enum's raw value (which I specify using a Sourcery annotation).

1 Like

It had to do with creating a token stream and then wanting to process that stream. I'll reconstruct the exact situation that I had in mind but before that I really want to push back on the idea that we have discriminant. The compiler might. The runtime might. We don't have access to just the discriminant.

Edit: It was in creating a lexer and parser using parser combinators. While building the actual parser that consumes tokens, you don't actually have instances of tokens. You need a way to utter the cases without having one because you're describing/building the machinery to actually process an instance.