Protocol function with generic type

Question

I would like to create a protocol like the following:

protocol Parser {
    func parse() -> ParserOutcome<?>
}

enum ParserOutcome<Result> {
    case result(Result)
    case parser(Parser)
}

I want to have parsers that return either a result of a specific type, or another parser.

If I use an associated type on Parser, then I can't use Parser in the enum. If I specify a generic type on the parse() function, then I can't define it in the implementation without a generic type.

How can I achieve this?

Using generics, I could write something like this:

class Parser<Result> {
    func parse() -> ParserOutcome<Result> { ... }
}

enum ParserOutcome<Result> {
    case result(Result)
    case parser(Parser<Result>)
}

This way, a Parser would be parameterized by the result type. parse() can return a result of the Result type, or any kind of parser that would output either a result of the Result type, or another parser parameterized by the same Result type.

With associated types however, as far as I can tell, I'll always have a Self constraint:

protocol Parser {
    associatedtype Result

    func parse() -> ParserOutcome<Result, Self>
}

enum ParserOutcome<Result, P: Parser where P.Result == Result> {
    case result(Result)
    case parser(P)
}

In this case, I can't have any type of parser that would return the same Result type anymore, it has to be the same type of parser.

I would like to obtain the same behavior with the Parser protocol as I would with a generic definition, and I would like to be able to do that within the bounds of the type system, without introducing new boxed types, just like I can with a normal generic definition.

It seems to me that defining associatedtype OutcomeParser: Parser inside the Parser protocol, then returning an enum parameterized by that type would solve the problem, but if I try to define OutcomeParser that way, I get the error:

Type may not reference itself as a requirement

I can't really write up an answer for this myself, but it looks to me like you might be looking for type erasure. I know that @RobNapier has shown elegant use of it in some of this answers, maybe you can find something to investigate there. — dfrib
I'm looking for language support. If it requires a hack, then I'd rather not implement it. — rid
I don't believe that type erasure is to be considered a hack, but rather a technique (which I haven't mastered myself :). I think I read somewhere that the Swift stdlib itself makes use of type erasure at some places. (Also, since I haven't really grasped type erasure myself, it might be totally off to use it in this context). — dfrib
Hmm, indeed, AnySequence is using type erasure, it's in the standard library, and it's explicitly documented as "type erased" by Apple. So far, it still feels like a hack, but I'm looking more into it. — rid
Type erasures are not a hack. They are used across the Swift Standard Library. You can read more about them here - natashatherobot.com/swift-type-erasure. — itskoBits

Hamish Hamish · Accepted Answer · 2016-07-07T13:10:42

I wouldn't be so quick to dismiss type erasures as "hacky" or "working around [...] the type system" – in fact I'd argue that they work with the type system in order to provide a useful layer of abstraction when working with protocols (and as already mentioned, used in the standard library itself e.g AnySequence, AnyIndex & AnyCollection).

As you said yourself, all you want to do here is have the possibility of either returning a given result from a parser, or another parser that works with the same result type. We don't care about the specific implementation of that parser, we just want to know that it has a parse() method that returns a result of the same type, or another parser with that same requirement.

A type erasure is perfect for this kind of situation, as all you need to do is take a reference to a given parser's parse() method, allowing you to abstract away the rest of the implementation details of that parser. It's important to note that you aren't losing any type safety here, you're being exactly as precise about the type of the parser as you requirement specifies.

If we look at a potential implementation of a type-erased parser, AnyParser, hopefully you'll see what I mean:

struct AnyParser<Result> : Parser {

    // A reference to the underlying parser's parse() method
    private let _parse : () -> ParserOutcome<Result>

    // Accept any base that conforms to Parser, and has the same Result type
    // as the type erasure's generic parameter
    init<T:Parser where T.Result == Result>(_ base:T) {
        _parse = base.parse
    }

    // Forward calls to parse() to the underlying parser's method
    func parse() -> ParserOutcome<Result> {
        return _parse()
    }
}

Now in your ParserOutcome, you can simply specify that the parser case has an associated value of type AnyParser<Result> – i.e any kind of parsing implementation that can work with the given Result generic parameter.

protocol Parser {
    associatedtype Result
    func parse() -> ParserOutcome<Result>
}

enum ParserOutcome<Result> {
    case result(Result)
    case parser(AnyParser<Result>)
}

...

struct BarParser : Parser {
    func parse() -> ParserOutcome<String> {
        return .result("bar")
    }
}

struct FooParser : Parser {
    func parse() -> ParserOutcome<Int> {
        let nextParser = BarParser()

        // error: Cannot convert value of type 'AnyParser<Result>'
        // (aka 'AnyParser<String>') to expected argument type 'AnyParser<_>'
        return .parser(AnyParser(nextParser))
    }
}

let f = FooParser()
let outcome = f.parse()

switch outcome {
case .result(let result):
    print(result)
case .parser(let parser):
    let nextOutcome = parser.parse()
}

You can see from this example that Swift is still enforcing type-safety. We're trying to wrap a BarParser instance (that works with Strings) in an AnyParser type erased wrapper that expects an Int generic parameter, resulting in a compiler error. Once FooParser is parameterised to work with Strings instead of Int, the compiler error will be resolved.

In fact, as AnyParser in this case only acts as a wrapper for a single method, another potential solution (if you really detest type erasures) is to simply use this directly as your ParserOutcome's associated value.

protocol Parser {
    associatedtype Result
    func parse() -> ParserOutcome<Result>
}

enum ParserOutcome<Result> {
    case result(Result)
    case anotherParse(() -> ParserOutcome<Result>)
}


struct BarParser : Parser {
    func parse() -> ParserOutcome<String> {
        return .result("bar")
    }
}

struct FooParser : Parser {
    func parse() -> ParserOutcome<String> {
        let nextParser = BarParser()
        return .anotherParse(nextParser.parse)
    }
}

...

let f = FooParser()
let outcome = f.parse()

switch outcome {
case .result(let result):
    print(result)
case .anotherParse(let nextParse):
    let nextOutcome = nextParse()
}

Protocol function with generic type

3 Answers