Are "Generic Functions" Using Protocols Possible?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
20 messages Options
Reply | Threaded
Open this post in threaded view
|

Are "Generic Functions" Using Protocols Possible?

Thomas Wetmore
More experimentation with Swift, and another demonstration of ignorance, I'm afraid. I write a lot of parsers and other code that uses nodes arranged in trees. I've written the following generic protocol for "nodeness" and have a couple concrete classes that implement it, and they work as expected.

protocol Node {
    typealias NodeAlias: Node
    var tag: String { get set }
    var value: String? { get set }
    var children: [NodeAlias]? { get set }
    var parent: NodeAlias? { get set }
}

Now, I would like to write some "generic" routines that process trees made of any kinds of nodes that implement this protocol. Here is an example of one such routine that would count all the nodes at and below any node. I guess I expected this function to "just work", but the compiler complains with the following:

"Protocol 'Node' can only be used as a generic constraint because it has Self or associated type requirements"

func count (node: Node) -> Int {   // <<---- compiler error (above) at first character of "Node".
    var count = 1
    if let children = node.children { for child in children { count += count(child) } }
    return count
}

When I did this in Objective-C, I wrote a "NodeProto" protocol and an "AbstractNode" class. I put these generic methods in the AbstractNode class and then had all the concrete node classes inherit both the prototype and the abstract class. I was really hoping to get rid of the abstract class (only meaning "abstract" in the sense that objects of the class are not instantiated by convention).

I "seems to me" that these generic functions should work, so I'm hoping I'm just missing something obvious. 

Can you tell I'm looking for some sage advice?

--
You received this message because you are subscribed to the Google Groups "Swift Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
To post to this group, send email to [hidden email].
To view this discussion on the web visit https://groups.google.com/d/msgid/swift-language/91abca90-842b-4c0f-9b71-e382a5e67065%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|

Re: Are "Generic Functions" Using Protocols Possible?

Kevin Greene
Does it work if you do this instead:

@class_protocol protocol Node { ... }

I'm not near my mac right now or I would verify that works, but I remember having to do that for a delegate protocol.


On Tue, Aug 5, 2014 at 2:38 PM, Thomas Wetmore <[hidden email]> wrote:
More experimentation with Swift, and another demonstration of ignorance, I'm afraid. I write a lot of parsers and other code that uses nodes arranged in trees. I've written the following generic protocol for "nodeness" and have a couple concrete classes that implement it, and they work as expected.

protocol Node {
    typealias NodeAlias: Node
    var tag: String { get set }
    var value: String? { get set }
    var children: [NodeAlias]? { get set }
    var parent: NodeAlias? { get set }
}

Now, I would like to write some "generic" routines that process trees made of any kinds of nodes that implement this protocol. Here is an example of one such routine that would count all the nodes at and below any node. I guess I expected this function to "just work", but the compiler complains with the following:

"Protocol 'Node' can only be used as a generic constraint because it has Self or associated type requirements"

func count (node: Node) -> Int {   // <<---- compiler error (above) at first character of "Node".
    var count = 1
    if let children = node.children { for child in children { count += count(child) } }
    return count
}

When I did this in Objective-C, I wrote a "NodeProto" protocol and an "AbstractNode" class. I put these generic methods in the AbstractNode class and then had all the concrete node classes inherit both the prototype and the abstract class. I was really hoping to get rid of the abstract class (only meaning "abstract" in the sense that objects of the class are not instantiated by convention).

I "seems to me" that these generic functions should work, so I'm hoping I'm just missing something obvious. 

Can you tell I'm looking for some sage advice?

--
You received this message because you are subscribed to the Google Groups "Swift Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
To post to this group, send email to [hidden email].
To view this discussion on the web visit https://groups.google.com/d/msgid/swift-language/91abca90-842b-4c0f-9b71-e382a5e67065%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "Swift Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
To post to this group, send email to [hidden email].
To view this discussion on the web visit https://groups.google.com/d/msgid/swift-language/CAEY8wq7VQvJonnXquC3rD1N75tC%2B8vw7VvS7QGWQQ-CGiTd%2B3g%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|

Re: Are "Generic Functions" Using Protocols Possible?

Garth Snyder
In reply to this post by Thomas Wetmore
Thomas, take a look here and see if that helps.

The problem is not the protocol per se; it’s the fact that the protocol includes a typealias. Therefore, just specifying the protocol is no longer sufficient to fully identify the object. (I wish I could be clearer about the exact reason for this, but I don’t understand it myself. It seems like you should be able to read the typealias right out of any conformant object, but perhaps that information is only available at compile time.)

You may be able to skirt the issue with a construction such as:

func count<T: Node>(node: T) -> Int { ...

Garth

 
On Aug 5, 2014, at 2:38 PM, Thomas Wetmore <[hidden email]> wrote:

I've written the following generic protocol for "nodeness" and have a couple concrete classes that implement it, and they work as expected. Now, I would like to write some "generic” routines...

--
You received this message because you are subscribed to the Google Groups "Swift Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
To post to this group, send email to [hidden email].
To view this discussion on the web visit https://groups.google.com/d/msgid/swift-language/282A3B05-675D-4E96-862B-7879CCD46343%40garthsnyder.com.
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|

Re: Are "Generic Functions" Using Protocols Possible?

Marco S Hyman
In reply to this post by Thomas Wetmore
Perhaps making count a generic func is what you want to do..

func count<T: Node>(node: T) -> Int {
    // ...
}

Lets see....  OK a simplified version that the playground likes

protocol Node {
    var tag: String { get set }
    var value: String? { get set }
    var children: [Node]? { get set }
    var parent: Node? { get set }
}

func count<T: Node>(node: T) -> Int {
    var c = 1
    if let children = node.children {
        for child in children {
            c += count(child)
        }
    }
    return c
}

* I removed the typealias just to simplify things.
* Count is generic over types that conform to Node
* You can NOT re-define count inside of the function count and expect
  to get the outer definition when invoking count(child).

I haven't actually tried to use this to see if it works other than
noting that this

struct SomeStruct: Node {
    var tag: String
    var value: String?
    var children: [Node]?
    var parent: Node?
}


Is also happy in the playground.

--
You received this message because you are subscribed to the Google Groups "Swift Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
To post to this group, send email to [hidden email].
To view this discussion on the web visit https://groups.google.com/d/msgid/swift-language/25FFCD9C-1939-4427-B842-6498DDD8CC31%40snafu.org.
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|

Re: Are "Generic Functions" Using Protocols Possible?

Thomas Wetmore
Garth, Marco,

Yes, thanks to you both; your approaches work. The below solves my problem. My original "non-solution" looks better to me, and in my opinion "should work", but this generic approach is clean enough for government work. We're not building a church.

protocol Node {
    typealias NodeAlias: Node
    var tag: String { get set }
    var value: String? { get set }
    var children: [NodeAlias]? { get set }
    var parent: NodeAlias? { get set }
}

func count<T: Node> (node: T) -> Int {
    var c = 1
    if let children = node.children { for child in children { c += count(child) } }
    return c
}


--
You received this message because you are subscribed to the Google Groups "Swift Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
To post to this group, send email to [hidden email].
To view this discussion on the web visit https://groups.google.com/d/msgid/swift-language/10df7574-d942-4391-9385-9d384d5ba3db%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|

Re: Are "Generic Functions" Using Protocols Possible?

Marco S Hyman
On Aug 5, 2014, at 4:44 PM, Thomas Wetmore <[hidden email]> wrote:

> protocol Node {
>     typealias NodeAlias: Node

What is the purpose of that line?  You have hard coded NodeAlias as
an alias for Node. Why not just use Node?

Or did you mean

     typealias NodeAlias

which is a placeholder for the actual type used when the protocol is
adopted. Look up Associated Types in the Swift Programming Language.

Marc

--
You received this message because you are subscribed to the Google Groups "Swift Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
To post to this group, send email to [hidden email].
To view this discussion on the web visit https://groups.google.com/d/msgid/swift-language/57826992-FDA9-4ECE-AF14-EE0E45102ED6%40snafu.org.
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|

Re: Are "Generic Functions" Using Protocols Possible?

Thomas Wetmore
There is a need for the typealias which I don't fully understand. If they are not used then the classes that derive from the protocol cannot be implemented using the derived type.

For example, when implementing, saw I have done the following:

class GedcomNode: Node {


On Tuesday, August 5, 2014 8:23:07 PM UTC-4, Marco Hyman wrote:
On Aug 5, 2014, at 4:44 PM, Thomas Wetmore <<a href="javascript:" target="_blank" gdf-obfuscated-mailto="pg4blRcVCFkJ" onmousedown="this.href='javascript:';return true;" onclick="this.href='javascript:';return true;">ttwet...@...> wrote:

> protocol Node {
>     typealias NodeAlias: Node

What is the purpose of that line?  You have hard coded NodeAlias as
an alias for Node. Why not just use Node?

Or did you mean

     typealias NodeAlias

which is a placeholder for the actual type used when the protocol is
adopted. Look up Associated Types in the Swift Programming Language.

Marc

--
You received this message because you are subscribed to the Google Groups "Swift Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
To post to this group, send email to [hidden email].
To view this discussion on the web visit https://groups.google.com/d/msgid/swift-language/4c73fcc0-aa68-41b9-aa5a-4f5483e76ed4%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|

Re: Are "Generic Functions" Using Protocols Possible?

Thomas Wetmore
In reply to this post by Marco S Hyman
The typealias seems to be needed. Say I implement the following:

class GedcomNode: Node {
    weak var Parent: GedcomNode? { ... }
    ....
}

without the typealias in the protocol the above would generate an error on the GedcomNode? type, requiring me to replace it with just Node?. With the typealias I can implement it as shown here using GedcomNode?, which is as it should be.

I don't truly understand this. And I don't like this. There was an earlier question of mine on this list that elicited this knowledge from someone on the list. The explanation somehow goes that by using the typealias, protocols can be made generic. Though I had thought that by their very nature protocols were already generic.

[In fact it's even worse. If I remove the typealias and change the NodeAlias's to Nodes, the compiler crashes.]

On Tuesday, August 5, 2014 8:23:07 PM UTC-4, Marco Hyman wrote:
On Aug 5, 2014, at 4:44 PM, Thomas Wetmore <<a href="javascript:" target="_blank" gdf-obfuscated-mailto="pg4blRcVCFkJ" onmousedown="this.href='javascript:';return true;" onclick="this.href='javascript:';return true;">ttwet...@...> wrote:

> protocol Node {
>     typealias NodeAlias: Node

What is the purpose of that line?  You have hard coded NodeAlias as
an alias for Node. Why not just use Node?

Or did you mean

     typealias NodeAlias

which is a placeholder for the actual type used when the protocol is
adopted. Look up Associated Types in the Swift Programming Language.

Marc

--
You received this message because you are subscribed to the Google Groups "Swift Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
To post to this group, send email to [hidden email].
To view this discussion on the web visit https://groups.google.com/d/msgid/swift-language/dcb7d4d4-9c31-47d0-b69d-193d809b1151%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|

Re: Are "Generic Functions" Using Protocols Possible?

Marco S Hyman
On Aug 5, 2014, at 5:47 PM, Thomas Wetmore <[hidden email]> wrote:

> The typealias seems to be needed. Say I implement the following:
>
> class GedcomNode: Node {
>     weak var Parent: GedcomNode? { ... }
>     ....
> }

Your typealias types NodeAlias as a Node, not a GedcomNode.  The doc
suggests typelias NodeAlias (not typealias NodeAlias: Node) is the
proper construct.  However when I try than with some test code I
trigger a different error in the playground.


protocol Node {
    typealias NodeAlias
    var tag: String { get set }
    var value: String? { get set }
    var children: [NodeAlias]? { get set }
    var parent: NodeAlias? { get set }
}

func count<T: Node>(node: T) -> Int {
    var c = 1
    if let children = node.children {
        for child in children {
            c += count(child)
        }
    }
    return c
}

struct SomeStruct: Node {
    var tag: String
    var value: String?
    var children: [SomeStruct]?
    var parent: SomeStruct?
}

The line "c += count(child) gives me the error
'Int' is not identical to 'UInt8'

I haven't a clue where that comes from

Marc

--
You received this message because you are subscribed to the Google Groups "Swift Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
To post to this group, send email to [hidden email].
To view this discussion on the web visit https://groups.google.com/d/msgid/swift-language/9802207B-915E-44D1-87CD-1654ACC8809C%40snafu.org.
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|

Re: Are "Generic Functions" Using Protocols Possible?

Thomas Wetmore
Marco,

I get the same compiler error when building my full executable command line program, when I get rid of the ": Node". In my naive way I chalk it up to "too many things with the same name, e.g., 'count'".

The version as I sent last time is the only one that I have found yet that compiles and runs correctly.

Tom

On Aug 5, 2014, at 9:13 PM, Marco S Hyman <[hidden email]> wrote:

> On Aug 5, 2014, at 5:47 PM, Thomas Wetmore <[hidden email]> wrote:
>
>> The typealias seems to be needed. Say I implement the following:
>>
>> class GedcomNode: Node {
>>    weak var Parent: GedcomNode? { ... }
>>    ....
>> }
>
> Your typealias types NodeAlias as a Node, not a GedcomNode.  The doc
> suggests typelias NodeAlias (not typealias NodeAlias: Node) is the
> proper construct.  However when I try than with some test code I
> trigger a different error in the playground.
>
>
> protocol Node {
>    typealias NodeAlias
>    var tag: String { get set }
>    var value: String? { get set }
>    var children: [NodeAlias]? { get set }
>    var parent: NodeAlias? { get set }
> }
>
> func count<T: Node>(node: T) -> Int {
>    var c = 1
>    if let children = node.children {
>        for child in children {
>            c += count(child)
>        }
>    }
>    return c
> }
>
> struct SomeStruct: Node {
>    var tag: String
>    var value: String?
>    var children: [SomeStruct]?
>    var parent: SomeStruct?
> }
>
> The line "c += count(child) gives me the error
> 'Int' is not identical to 'UInt8'
>
> I haven't a clue where that comes from
>
> Marc

--
You received this message because you are subscribed to the Google Groups "Swift Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
To post to this group, send email to [hidden email].
To view this discussion on the web visit https://groups.google.com/d/msgid/swift-language/A7E19B76-28B3-4154-852F-0DD48C5FCBBE%40gmail.com.
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|

Re: Are "Generic Functions" Using Protocols Possible?

Thomas Wetmore
Ah, but then I tried to write another generic node function to do a depth first traversal that runs a trivial visit function, which leads to yet another indecipherable (by me) compiler message:

// Perform a depth first recurse through a tree of nodes doing something.

func depthFirst<T: Node> (node: T, visit: (T) -> Int) {

    if let children = node.children {

        for child in children { depthFirst(child, visit) }  // 'T.NodeAlias' is not a subtype of 'T'

                                                  ^

    }

    visit(node)

}


So it's back to the drawing board.


Tom


On Tuesday, August 5, 2014 9:36:36 PM UTC-4, Thomas Wetmore wrote:
Marco,

I get the same compiler error when building my full executable command line program, when I get rid of the ": Node". In my naive way I chalk it up to "too many things with the same name, e.g., 'count'".

The version as I sent last time is the only one that I have found yet that compiles and runs correctly.

Tom

On Aug 5, 2014, at 9:13 PM, Marco S Hyman wrote:

> On Aug 5, 2014, at 5:47 PM, Thomas Wetmore wrote:
>
>> The typealias seems to be needed. Say I implement the following:
>>
>> class GedcomNode: Node {
>>    weak var Parent: GedcomNode? { ... }
>>    ....
>> }
>
> Your typealias types NodeAlias as a Node, not a GedcomNode.  The doc
> suggests typelias NodeAlias (not typealias NodeAlias: Node) is the
> proper construct.  However when I try than with some test code I
> trigger a different error in the playground.
>
>
> protocol Node {
>    typealias NodeAlias
>    var tag: String { get set }
>    var value: String? { get set }
>    var children: [NodeAlias]? { get set }
>    var parent: NodeAlias? { get set }
> }
>
> func count<T: Node>(node: T) -> Int {
>    var c = 1
>    if let children = node.children {
>        for child in children {
>            c += count(child)
>        }
>    }
>    return c
> }
>
> struct SomeStruct: Node {
>    var tag: String
>    var value: String?
>    var children: [SomeStruct]?
>    var parent: SomeStruct?
> }
>
> The line "c += count(child) gives me the error
> 'Int' is not identical to 'UInt8'
>
> I haven't a clue where that comes from
>
> Marc

--
You received this message because you are subscribed to the Google Groups "Swift Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
To post to this group, send email to [hidden email].
To view this discussion on the web visit https://groups.google.com/d/msgid/swift-language/12eea05a-20c8-4079-aef1-3cf327d1bd64%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|

Re: Are "Generic Functions" Using Protocols Possible?

Garth Snyder
In reply to this post by Thomas Wetmore
If this “Parent” is meant to be “parent”, the property defined in the protocol, then it’s not clear to me that what you’re trying to do makes sense. 

Here’s my thinking: the protocol promises a “parent” property of type Node that is both gettable and settable. In other words, you can look at parent and get a Node back, and you can also set parent to any Node. When you define your class’s parent as a GedcomNode, you’re violating the setter part of that contract since only GedcomNodes are acceptable as parents. So it seems reasonable that the compiler would balk.

You could get around this by making your implementations of the Node properties procedural and referencing other variables that are of type GedcomNode, but then you'd still end up with your API disgorging generic Nodes for parents and children, which is probably not what you want.

I suspect that a typealias is in fact the right solution here. But it’s not just a magic incantation to plop into the protocol; you have to define its value for each specific implementation. So here, in schematic form,

protocol Node {
    typealias NodeType
    var parent: NodeType? { get set }
}

class RealNode: Node {
    typealias NodeType = RealNode
    var parent: RealNode?

    init(_ p: RealNode? = nil) {
        parent = p
    }
}

Now RealNode is compliant with Node, but the compiler knows that it always requires or returns a RealNode as its parent.

Garth

On Aug 5, 2014, at 5:47 PM, Thomas Wetmore <[hidden email]> wrote:

The typealias seems to be needed. Say I implement the following:

class GedcomNode: Node {
    weak var Parent: GedcomNode? { ... }
    ....
}

without the typealias in the protocol the above would generate an error on the GedcomNode? type, requiring me to replace it with just Node?. With the typealias I can implement it as shown here using GedcomNode?, which is as it should be.

--
You received this message because you are subscribed to the Google Groups "Swift Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
To post to this group, send email to [hidden email].
To view this discussion on the web visit https://groups.google.com/d/msgid/swift-language/665A7DBB-5A84-4689-B58C-96B59A2B8241%40garthsnyder.com.
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|

Re: Are "Generic Functions" Using Protocols Possible?

Thomas Wetmore
Garth,

Thanks, yes, I meant parent, not Parent. Sorry for that confusion.

What I am doing seems clear to me. To meet the Node protocol an implementing type must provide a get/set parent property that must get/set an object meeting the Node protocol. If a RealNode type implements its parent property to get/set a RealNode, that meets the protocol requirement.

You imply that a concrete type that implements the Node protocol must be able to set an instance's parent property to any object that meets the Node protocol. Wouldn't that bring the protocol concept tumbling down?

The reason for this thread was because I was too obtuse to figure out how to write generic functions using any concrete instances that meet a given protocol. I believe it is only in those types of functions that we can require parameters that implement the protocols to be of any implementing real type.

Tom

On Aug 5, 2014, at 11:05 PM, Garth Snyder wrote:
If this “Parent” is meant to be “parent”, the property defined in the protocol, then it’s not clear to me that what you’re trying to do makes sense. 

Here’s my thinking: the protocol promises a “parent” property of type Node that is both gettable and settable. In other words, you can look at parent and get a Node back, and you can also set parent to any Node. When you define your class’s parent as a GedcomNode, you’re violating the setter part of that contract since only GedcomNodes are acceptable as parents. So it seems reasonable that the compiler would balk.

--
You received this message because you are subscribed to the Google Groups "Swift Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
To post to this group, send email to [hidden email].
To view this discussion on the web visit https://groups.google.com/d/msgid/swift-language/ba91ce92-02de-41e8-86ba-d5fdc6269d21%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|

Re: Are "Generic Functions" Using Protocols Possible?

Garth Snyder
Thomas Wetmore <[hidden email]> wrote: You imply that a concrete type that implements the Node protocol must be able to set an instance's parent property to any object that meets the Node protocol. Wouldn't that bring the protocol concept tumbling down?

Well, I don’t know about it ripping a hole in the fabric of the universe, but I agree: it’s not what you want for this application. These last few posts about the behavior of typealias-less protocols have been tangential to your real problem, though, so let me go back to something that may be helpful to you right now.

Your implementation of depthFirst, in combination with the Node protocol as you proposed it in the first message in this thread, is very close to being correct. To recap, here’s a simplified version:

protocol Node {
    typealias NodeType: Node
    var children: [NodeType] { get set }
}

func depthFirst<T: Node> (node: T, visit: (T) -> Int) {
    for child in node.children {
        depthFirst(child, visit)
    }
    visit(node)
}

In fact, the compiler complains about the recursive call to depthFirst() with the error “T.NodeType is not a subtype of T”. (As you note.)

The compiler is right: just because NodeType must be a type of Node doesn’t mean that it is the same type as the object whose children you are accessing. What you really want is a way to say that Node implementations of class X return lists of children whose types are also X. 

And in fact this exists, though it doesn’t seem to be covered in the Swift book:

protocol Node {
    var children: [Self] { get set }
}

Self behaves like a typealias in that it “poisons” the protocol for use as a parameter or return type, so you will still need to define depthFirst() as a generic function. (In fact, you can use exactly the same implementation shown above.)

This should work right now in beta 5.

OK, back to the tangential stuff, just for fun. Remember, here we’re back in the hypothetical world of Node protocols with no Self or typealias references, which I don’t think can be made to work in practice...

To meet the Node protocol an implementing type must provide a get/set parent property that must get/set an object meeting the Node protocol. If a RealNode type implements its parent property to get/set a RealNode, that meets the protocol requirement.

No, it doesn’t. Properties and self-referential protocols disguise the basic issue a bit, so consider this simpler analogy:

protocol Vehicle { … }

protocol Passenger {
    func boardVehicle(v: Vehicle)
}

class Train : Vehicle { … }

class Commuter : Passenger {
    func boardVehicle(t: Train) {
        …
    }
}

The compiler rejects this code because Commuter does not in fact conform to the Passenger protocol. Train is a more specific type than Vehicle, and a Passenger has to be able to board any kind of Vehicle, not just Trains.

Just as not all Vehicles are Trains, not all Nodes are RealNodes. Does this help?

Garth


On Aug 6, 2014, at 2:39 AM, Thomas Wetmore <[hidden email]> wrote:

What I am doing seems clear to me. To meet the Node protocol an implementing type must provide a get/set parent property that must get/set an object meeting the Node protocol. If a RealNode type implements its parent property to get/set a RealNode, that meets the protocol requirement.

You imply that a concrete type that implements the Node protocol must be able to set an instance's parent property to any object that meets the Node protocol. Wouldn't that bring the protocol concept tumbling down?

The reason for this thread was because I was too obtuse to figure out how to write generic functions using any concrete instances that meet a given protocol. I believe it is only in those types of functions that we can require parameters that implement the protocols to be of any implementing real type.

--
You received this message because you are subscribed to the Google Groups "Swift Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
To post to this group, send email to [hidden email].
To view this discussion on the web visit https://groups.google.com/d/msgid/swift-language/5B9C5B6A-05C0-4E5B-B4AC-7F88D40A7014%40garthsnyder.com.
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|

Re: Are "Generic Functions" Using Protocols Possible?

Thomas Wetmore
Garth,

Thanks so much. I will have to read and reread your message a few times before I can meaningfully reply.

But I can share a solution to the depthFirst algorithm that works:

// Perform a depth first recurse through a tree of nodes doing something.
func depthFirst<T: Node> (var node: T, visit: T -> ()) {
    if !node.mark {
        if let children = node.children {
            for child in children {
                depthFirst(child as T, visit)
            }
        }
        visit(node)
        node.mark = true
    }
}

A couple minor changes. 1) I added the notion of a marking nodes to prevent infinite loops on networks of nodes with cycles; 2) I changed the arity of the visit function/closure to have no return type; and 3) I got rid of the error that was blocking me by adding "as T" to the child argument to the recursive call.

I will admit that this was more of a trial and error fix than cerebral cogitation. However, with this implementation I now have a generic depth first traverser that all my concrete implementations of Node can use.

Here's a question, however. Because this algorithm now mutates Nodes by changing the state of the mark predicate values, does this imply that Nodes must be implemented as classes? Could a Node be implemented as a struct and this algorithm still work?

I have moved further and now am working with a Tree protocol, where a Tree is made up of networks of Nodes. This was necessitated by some of the issues of how one can dependably mark and unmark networks of Nodes when the Nodes were left in mixed marked states (some Nodes marked, some not), and you want to 1) guarantee that all Nodes are either marked or unmarked at the end of the marking and unmarking operations; 2) no infinite loops regardless of starting state; and 3) Nodes don't have to implement Hashable or Equatable. In doing so I have come across a new series of gotchas, some now fixed, but regrettably, some not.

Maybe more later when I better grasp what you have written. I am a seat of the pants programmer, and this stuff is giving me a headache.

Tom

--
You received this message because you are subscribed to the Google Groups "Swift Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
To post to this group, send email to [hidden email].
To view this discussion on the web visit https://groups.google.com/d/msgid/swift-language/bb507d0c-6676-4e2b-82db-e687edf6bee9%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|

Re: Are "Generic Functions" Using Protocols Possible?

Marco S Hyman
In reply to this post by Marco S Hyman
I wrote..

>
>> protocol Node {
>>    typealias NodeAlias: Node
>
> What is the purpose of that line?  You have hard coded NodeAlias as
> an alias for Node. Why not just use Node?

because I read "NodeAlias: Node" but thought "NodeAlias = Node"

Oops.  Just one of the (many) pitfalls of learning a new language.
Sorry for the noise.

--
You received this message because you are subscribed to the Google Groups "Swift Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
To post to this group, send email to [hidden email].
To view this discussion on the web visit https://groups.google.com/d/msgid/swift-language/0B39D91B-7F58-4724-853C-DE70D9814407%40snafu.org.
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|

Re: Are "Generic Functions" Using Protocols Possible?

Thomas Wetmore
In reply to this post by Garth Snyder
Garth,

Have read your email a couple times now. I'm not sure I agree with the following assumption:

On Aug 6, 2014, at 6:30 PM, Garth Snyder wrote:

> The compiler is right: just because NodeType must be a type of Node doesn't mean that it is the same type as the object whose children you are accessing. What you really want is a way to say that Node implementations of class X return lists of children whose types are also X.

I don't want to make that restriction. I don't see any reason why the depthFirst algorithm should care one way or the other whether all the nodes it visits in one particular execution be of the same concrete type. I can easily foresee a situation where one would want children Nodes of various concrete types. I am not doing that in my application, but I don't see any reason why it shouldn't be if the application calls for it; say a parse tree made up of nodes of many subtypes. The only requirement that depthFirst should "care about" is that every node meet the pure Node protocol. Would you disagree with that?

The solution I came up with that added the "as T" casting seems to have solved the problem fine. I will put together a test case where I build a tree of Nodes of more than one concrete type to see if things still work correctly

> And in fact this exists, though it doesn't seem to be covered in the Swift book:
>
> protocol Node {
>     var children: [Self] { get set }
> }

This is very interesting. Is it described anywhere what the real semantics of Self are in this case?

Tom

--
You received this message because you are subscribed to the Google Groups "Swift Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
To post to this group, send email to [hidden email].
To view this discussion on the web visit https://groups.google.com/d/msgid/swift-language/AD854280-3476-4FDB-BDD1-92566F6FD529%40gmail.com.
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|

Re: Are "Generic Functions" Using Protocols Possible?

Garth Snyder
I don't want to make that restriction [that node trees be homogeneous]. I don't see any reason why the depthFirst algorithm should care one way or the other whether all the nodes it visits in one particular execution be of the same concrete type. 

If the Node protocol contains a typealias or Self, I think you have to do it this way to make it possible to write depthFirst at all. When depthFirst calls itself, Swift has to be able to trace back the argument type to a specific NodeType, and the only place that can come from is T.

“But my current code works just fine, and it doesn’t have this restriction.”  In fact, it does. When you write this:

func depthFirst<T: Node>(node: T) {
    for child in node.children {
        depthFirst(child as T)
    }
}

the “child as T” evaluates to nil if child is not in fact a T. So child nodes are implicitly constrained to be of similar type to their parents.

If you want complete genericity everywhere, it’s easily achieved:

protocol Node {
    var children: [Node] { get set }
}

func depthFirst(node: Node) {
    for child in node.children {
        depthFirst(child)
    }
}

class NodeImplementation : Node {
    var children: [Node] = []
}

The disadvantage is that type information is lost even within the node implementations. You have to cast even your own children to do anything more than Node operations on them. Or you can have a parallel private (non-Node) API that’s type-specific — or any number of other work-arounds — but there will certainly be some minor friction there.

The bottom line is that you just have to make some explicit decisions about the level of type-specificity you want to enforce. If you mix degrees of type specificity, you’ll need glue.

Garth


On Aug 7, 2014, at 7:56 AM, Thomas Wetmore <[hidden email]> wrote:

Garth,

Have read your email a couple times now. I'm not sure I agree with the following assumption:

On Aug 6, 2014, at 6:30 PM, Garth Snyder wrote:

The compiler is right: just because NodeType must be a type of Node doesn’t mean that it is the same type as the object whose children you are accessing. What you really want is a way to say that Node implementations of class X return lists of children whose types are also X.

I don't want to make that restriction. I don't see any reason why the depthFirst algorithm should care one way or the other whether all the nodes it visits in one particular execution be of the same concrete type. I can easily foresee a situation where one would want children Nodes of various concrete types. I am not doing that in my application, but I don't see any reason why it shouldn't be if the application calls for it; say a parse tree made up of nodes of many subtypes. The only requirement that depthFirst should "care about" is that every node meet the pure Node protocol. Would you disagree with that?

The solution I came up with that added the "as T" casting seems to have solved the problem fine. I will put together a test case where I build a tree of Nodes of more than one concrete type to see if things still work correctly

And in fact this exists, though it doesn’t seem to be covered in the Swift book:

protocol Node {
   var children: [Self] { get set }
}

This is very interesting. Is it described anywhere what the real semantics of Self are in this case?

Tom


--
You received this message because you are subscribed to the Google Groups "Swift Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
To post to this group, send email to [hidden email].
To view this discussion on the web visit https://groups.google.com/d/msgid/swift-language/4814D915-855D-42AC-BA8C-1DD44700E6B2%40garthsnyder.com.
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|

Re: Are "Generic Functions" Using Protocols Possible?

Garth Snyder
In reply to this post by Thomas Wetmore
Unknown, captain.

I assume it's a placeholder that is replaced with a specific type at compile time when an implementation is encountered.

I'd love to read more if anyone knows where...

Garth

> On Aug 7, 2014, at 7:56 AM, Thomas Wetmore <[hidden email]> wrote:
>
> This is very interesting. Is it described anywhere what the real semantics of Self are in this case?

--
You received this message because you are subscribed to the Google Groups "Swift Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
To post to this group, send email to [hidden email].
To view this discussion on the web visit https://groups.google.com/d/msgid/swift-language/1047C6FE-6157-4038-A42B-D63F2DCD9A76%40garthsnyder.com.
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|

Re: Are "Generic Functions" Using Protocols Possible?

Thomas Wetmore
Thanks for all the responses. At this point all I can say is that I have learned a lot, but have a lot more to learn. I am a bit frustrated about how difficult it is proving to be to define a simple protocol for Trees and Nodes and to write generic functions that work for any concrete implementations of those protocols.

I wanted to sum up this thread by showing what I believe would be the ideal way to define protocols for Nodes and Trees of Nodes, and include a couple generic algorithms that would work for all concrete implementation of the two protocols. However, the following code generates a great number of compiler errors. In addition any concrete classes that try to implement these protocols also generates many compiler errors.

Experts reading this code may be amused by my naiveté. All I know is that this seems to me to be the right way to write this kind of code.

// Protocol for nodes.

protocol Node {

    var tag: String { get set }

    var value: String { get set }

    var mark: Bool { get set }

    var children: [Node] { get set }

    var parent: Node? { get set }

}


// Protocol for trees of nodes (actually graphs).

protocol Tree {

    var nodes: [Node] { get set }

    var root: Node { get set }

}


// Unmark all nodes in a tree/graph.

func unmark (var tree: Tree) {

    for node in tree.nodes {

        node.mark = false

    }

}


// Depth first traverse a tree/graph.

func depthFirst (var tree: Tree, visit: Node -> ()) {

    unmark(tree)

    depthFirst(tree.root, visit)

}


// Depth first traverse from a node.

func depthFirst (var node: Node, visit: Node -> ()) {

    if !node.mark {

        for child in children {

            depthFirst(child, visit)

        }

        visit(node)

        node.mark = true

    }

}


--
You received this message because you are subscribed to the Google Groups "Swift Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
To post to this group, send email to [hidden email].
To view this discussion on the web visit https://groups.google.com/d/msgid/swift-language/a1954e44-6fef-4e04-99ce-5a14be3c86db%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.