Generic implementation doesn't work with concrete types

[llacroix (Loïc Faure-Lacroix)]

I've been trying to implement some ways to have some kind of generic way to handle actions that would update a store.

Here's a short reproducible example. I couldn't get my head around making this with protocols ( if it's even possible) so I thought about doing this using Generic structs instead.

Here you have an Updater that can take any kind of Subject and Modifier that would modify the subject and two implementations of the apply method for concrete pair of types.

struct Updater<Subject, Modifier> {
    let subject: Subject
    let modifier: Modifier

    init(_ subject: Subject, _ modifier: Modifier) {
        self.subject = subject
        self.modifier = modifier
    }
}

extension Updater where Subject == State, Modifier == Add {
    func apply() -> Subject {
        State(value: subject.value + modifier.value)
    }
}

extension Updater where Subject == State, Modifier == Remove {
    func apply() -> Subject {
        State(value: subject.value - modifier.value)
    }
}

struct State {
    let value: Int
}

struct Add {
    let value: Int
}

struct Remove {
    let value: Int
}


var state = State(value: 0)
print(state)
state = Updater(state, Add(value: 1)).apply()
print(state)
state = Updater(state, Remove(value: 1)).apply()
print(state)

So this works but it's not really convenient to use.

But the following doesn't work.

func apply_action<S, M>(_ state: S, _ modifier: M) -> S {
    Updater(state, modifier).apply()
}
app = apply_action(app, Add(value: 1))

What's really strange is that while the snippet above isn't able to find the proper
apply method being confused between the 2 declared methods...

The following snippet clearly show that the type of Updater is properly inferred to Updater<State, Add>. So I'm a bit confused as to why it's confused picking the function apply from the other concrete implementation. It clearly shouldn't be confused.

What's interesting is that I can implement the methods as such in the State without using generics but just reusing the code like this:

extension State {
   func apply(_ modifier: Remove) -> State {
       Updater(state, modifier).apply()
   }

   func apply(_ modifier: Add) -> State {
       Updater(state, modifier).apply()
   }
}

And this would allow writing code like this:

state = state.apply(Remove(value: 1))

But making that method generic doesn't seem possible for some reasons.

[wadetregaskis]

@llacroix

func apply_action<S, M>(_ state: S, _ modifier: M) -> S {
    Updater(state, modifier).apply()
}

Maybe I'm missing something, but I wouldn't expect this to work because Updater doesn't have a generic apply method. You have specific apply methods for two specific specialisations, but that's not helpful for a generic method like apply_action.

I'd only expect it to pass type checking if you limit S to State and M to Add and/or Remove.

[Nobody1707]

I think this is a case of expecting generics to work like templates.

[llacroix (Loïc Faure-Lacroix)]

@wadetregaskis

I'd only expect it to pass type checking if you limit S to State and M to Add and/or Remove.

It's possible but calling but look at this:

func apply_action<S, M>(_ state: S, _ modifier: M) -> S {
    print(Updater(state, modifier))
    return state
}
state = apply_action(state, Remove(value: 1))
state = apply_action(state, Add(value: 1)) 

This will compile properly and output this:

Updater<State, Remove>(subject: repro.State(value: 0), modifier: repro.Remove(value: 1))
Updater<State, Add>(subject: repro.State(value: 0), modifier: repro.Add(value: 1))

So here it's clear that the type passed to the generic function can properly create the specialized type. In the non generic context we can call the specialized function but in the generic context it still attempting to decide between the specialized function and those that don't match the current specialized type. I understand what you mean here but saying that the apply isn't generic sounds wrong considering that the apply function are bound to a generic specialization.

For example you could have a default function that simply returns the subject.

extension Updater {
    func apply() -> Subject {
        subject
    }
}

But a specialized function should be picked if available.

@Nobody1707

I think this is a case of expecting generics to work like templates.

What's the purpose of creating specialized function with specialized extension if they can't be used in a generic context?

[llacroix (Loïc Faure-Lacroix)]

Sounds like a bug to me, when creating a non constrained version of apply that only return its subject. It will compile but will completely ignore the specialized functions that are still there.

extension Updater {
    func apply() -> Subject {                                                                                                                                                                                                                 
        subject
    }
}

extension Updater where Subject == State, Modifier == Add {
    func apply() -> Subject {
        State(value: subject.value + modifier.value)
    }
}

extension Updater where Subject == State, Modifier == Remove {
    func apply() -> Subject {
        State(value: subject.value - modifier.value)
    }
}

From the generic context, it will never call any specialized function even if you modify the signature of the function to return a tuple (S, M) to attempt constraining the return type.

Here's an example:

Swift Online Playground

[Slava_Pestov]

Here is how method calls work in swift:

1. We find all applicable overloads at compile time and pick the most specific one, using static type information.

2. If the chosen overload is a protocol requirement, we generate code to look up and call the witness.

3. Otherwise we generate a direct call to the implementation of the chosen overload.

4. When checking a conformance of a type to a protocol we find the best witness for each protocol requirement, once again using static type information, as in (1). This is what gets called in 2.

I think some people imagine it as being more like:

1. For every method call, the compiler generates code to collect the dynamic types of all arguments, and does a lookup in some table.

2. All method declarations are added to this table at runtime.

That’s not how it works though, so if you start with that mental model it won’t match reality.

[Jumhyn (Frederick Kellison-Linn)]

@Slava_Pestov

1. We find all applicable overloads at compile time and pick the most specific one, using static type information.

Important to emphasize that this is 'static type information directly at the specific overload call site'. So when a call occurs in a generic context, you can only deduce overloads using the local generic information. That callers into that generic context might provide additional type context will never cause overload resolution to change.

And as @Nobody1707 notes above, this may be unexpected for folks coming to Swift from C++.

[llacroix (Loïc Faure-Lacroix)]

@Slava_Pestov

I think some people imagine it as being more like:

1. For every method call, the compiler generates code to collect the dynamic types of all arguments, and does a lookup in some table.
2. All method declarations are added to this table at runtime.

That’s not how it works though, so if you start with that mental model it won’t match reality.

Care to point out where I'm using any dynamic typing? To me it seems everything is statically typed.

@Jumhyn

Important to emphasize that this is 'static type information directly at the specific overload call site'. So when a call occurs in a generic context, you can only deduce overloads using the local generic information. That callers into that generic context might provide additional type context will never cause overload resolution to change.

And as @Nobody1707 notes above, this may be unexpected for folks coming to Swift from C++.

Would you be able to explain how the type of Updater is properly resolved to Updater<State, Add> or Updater<State, Remove> but cannot find the proper apply method specialized for the type considering it has all the static data to resolve it.

[Slava_Pestov]

@llacroix

Care to point out where I'm using any dynamic typing? To me it seems everything is statically typed.

You’re making the implicit assumption that the call to apply() will pick one of several implementations based on dynamic type information. In reality, overload resolution picks the most specific overload at compile time, and that’s the one that gets called.

[Jumhyn (Frederick Kellison-Linn)]

@llacroix

Would you be able to explain how the type of Updater is properly resolved to Updater<State, Add> or Updater<State, Remove> but cannot find the proper apply method specialized for the type considering it has all the static data to resolve it.

At the call site of apply():

func apply_action<S, M>(_ state: S, _ modifier: M) -> S {
    let updater = Updater(state, modifier)
    print(updater)
    return updater.apply()
}

S and M are unconstrained generic parameters. From the internal view, the compiler doesn't know anything about them. But the specific overload of apply() must be chosen, once, at the time we compile apply_action, and that choice cannot change later based on information that is only available when apply_action is called with concrete arguments.

Since nothing is known about S and M, the only available overload to call is the unconstrained overload of apply() which imposes no requirements on S and M.

[Slava_Pestov]

@Jumhyn

Since nothing is known about S and M, the only available overload to call is the unconstrained overload of apply() which imposes no requirements on S and M.

Here is another simple example:

func f<T>(t: T) { g(t: t) }
func f<T: Equatable>(t: T) { g(t: t) }

func g<T>(t: T) {}
func g<T: Equatable>(t: T) {}

The first f calls the first g, and the second f calls the second g.

[Jumhyn (Frederick Kellison-Linn)]

@Slava_Pestov

The first f calls the first g, and the second f calls the second g.

And just to drive the point home: Swift's model allows us to unequivocally make this statement just by looking the body of f without ever seeing anything call f.

[llacroix (Loïc Faure-Lacroix)]

@Jumhyn

Since nothing is known about S and M, the only available overload to call is the unconstrained overload of apply() which imposes no requirements on S and M.

Oh ok, so it won't create a specialized function of apply_action for every pair of S, M. As a result, when building the apply_action function it will only be able to know about the overly generic one or the only specialized function one.

So it never really statically check S -> Subject and M -> Modifier when compiling it just later does some "sanity" check to verify that the code is sound.

[Jumhyn (Frederick Kellison-Linn)]

@llacroix

So it never really statically check S -> Subject and M -> Modifier when compiling it just later does some "sanity" check to verify that the code is sound.

I'm not sure exactly what you mean here. Subject and Modifier (the generic parameters to Updater) are also unconstrained, so there's nothing for the compiler to 'check'. Any two types could be passed for those parameters, and so the compiler knows it can construct an Updater<S, M> without issue. If Subject or Modifier had a constraint which S or M respectively wouldn't satisfy, then you'd get an error when trying to construct Updater<S, M>.

[Slava_Pestov]

@llacroix

Oh ok, so it won't create a specialized function of apply_action for every pair of S, M.

Right. In C++, template expansion happens before overload resolution. In Swift, generic declarations are first-class and compiled separately.

[tera]

So this works but it's not really convenient to use.

Why is that inconvenient?

@llacroix

I've been trying to implement some ways to have some kind of generic way to handle actions that would update a store.

Here's my attempt without using generics:

protocol Subject {
    init(value: Int)
    var value: Int { get }
    func apply(_ modifier: Modifier) -> Self
}
protocol Modifier {
    func apply(_ subject: Subject) -> Int
}
struct State: Subject {
    var value: Int
    func apply(_ modifier: Modifier) -> Self {
        Self.init(value: modifier.apply(self))
    }
}
struct Add: Modifier {
    let value: Int
    func apply(_ subject: Subject) -> Int {
        subject.value + value
    }
}
struct Remove: Modifier {
    let value: Int
    func apply(_ subject: Subject) -> Int {
        subject.value - value
    }
}
var state = State(value: 3)
print(state)
state = state.apply(Add(value: 2))
print(state)
state = state.apply(Remove(value: 1))
print(state)

Here modifiers don't know how to create new subjects but they know how to perform the operation and create a new value, and Subject create a new version of self with a new value.

[Slava_Pestov]

@Jumhyn

Important to emphasize that this is 'static type information directly at the specific overload call site'. So when a call occurs in a generic context, you can only deduce overloads using the local generic information. That callers into that generic context might provide additional type context will never cause overload resolution to change.

Here is the same principle but illustrated using subclassing instead of generics:

class Base {
  func f(_ other: Base) { g(other) }
  func g(_ other: Base) {}
}

class Derived: Base {
  override func g(_ other: Base) {}
  /* not an override */ func g(_ other: Derived) { /* never called! */ }
}

Derived().f(Derived())

While this example is not so surprising for people coming from C++ and Objective-C, the behavior is not a given -- CLOS can express this kind of customization through multiple dispatch for example.

[llacroix (Loïc Faure-Lacroix)]

I provided a very simple example. As far as I know, what I'm trying to achieve is not currently possible to achieve with protocols if it ever will.

Let imagine that the state you want to modify is like this:

struct SuperState: Subject {
   let state1: State
   let state2: OtherState

   func apply(_ modifier: Modifier) -> Self {
      Self.init(
        state1: state1.apply(modifier),
        state2: state2.apply(modifier)
      )
   }
}

So now the protocol for Add, Remove should be implemented to also take a State as an argument for apply and the Subject would also need to know how to construct something with init(state1: State, state2: OtherState) but you wouldn't want a State: Subject to be forced to implement this constructor as it makes no sense...

[llacroix (Loïc Faure-Lacroix)]

That explains why it's not working. I'll have to find a different approach to do what I'm trying to do I guess.

[Slava_Pestov]

@llacroix

That explains why it's not working. I'll have to find a different approach to do what I'm trying to do I guess.

I think there are two approaches you can try:

• A case analysis on the type of the modifier inside the “leaf” apply() implementation. This is the static equivalent of:
• Have the “leaf” turn around and call modifier.applyTo(state). Now each modifier has to know how to apply itself to a “leaf” state, that is, one that isn’t a SuperState.

This is a design pattern in OO languages called double dispatch. It translates to protocols directly.