V82(B): Generic Cyclic Behavior

Monkey Forums/Monkey Bug Reports/V82(B): Generic Cyclic Behavior

ImmutableOctet(SKNG)

(Posted 2015) [#1]

So, I was writing a generic class hierarchy before, and I found that the compiler is incorrectly giving me an error.

Here's some example code:

Strict

Public

' Functions:
Function Main:Int()
	Local X:= New Y(10)
	Local W:= New Y(100, X)
	
	Print(W.Parent.I)
	Print(X.I)
	
	' Return the default response.
	Return 0
End

' Classes:
Class Y Extends Z<Y>
	' Constructor(s):
	Method New(Value:Int=0, Parent:Y=Null)
		' Call the super-class's implementation.
		Super.New(Parent, Value)
	End
	
	' Fields:
	' Nothing so far.
End

Class Z<ParentType>
	' Constructor(s):
	Method New(Parent:ParentType, Value:Int=0)
		Self.Parent = Parent
		Self.I = Value
	End
	
	' Fields:
	Field Parent:ParentType
	Field I:Int
End

The above example doesn't compile; it will give me an error saying "Cyclic declaration of 'Y'", without being logically wrong. Just because the 'Y' class's super-class ('Z') knows what 'Y' is, that doesn't mean it should matter.

If I were to simply remove the parts that are generic, the result would be this:

Strict

Public

' Functions:
Function Main:Int()
	Local X:= New Y(10)
	Local W:= New Y(100, X)
	
	Print(W.Parent.I)
	Print(X.I)
	
	' Return the default response.
	Return 0
End

' Classes:
Class Y Extends Z
	' Constructor(s):
	Method New(Value:Int=0, Parent:Y=Null)
		' Call the super-class's implementation.
		Super.New(Parent, Value)
	End
	
	' Fields:
	' Nothing so far.
End

Class Z
	' Constructor(s):
	Method New(Parent:Y, Value:Int=0)
		Self.Parent = Parent
		Self.I = Value
	End
	
	' Fields:
	Field Parent:Y
	Field I:Int
End

The second snippet compiles without a problem. But, my code can't really be done like the second example without basically ruining it. To begin with, this isn't a logical problem with my code, the compiler's just reporting a bug that isn't there. I imagine this happens with the latest version as well (Which I should probably update to).

So, is this just an annoying limitation of Monkey, or is it an actual bug? I don't see why removing the generic element should make it work, unless it's a bug. If I can't do this by design, that means Monkey is literally telling me that I can't reuse code without suffering extra overhead and increased code complexity. I don't want interfaces doing the job of a generic class.

It's not like 'Y' is inheriting itself in some way, so why does the compiler throw an error?

EDIT: I have fixed my own code, but this is still more of a principle problem, than an actual issue with my code. Following the rules the compiler currently does may eventually cause this to happen on my other generic/template code.

Samah

(Posted 2015) [#2]

@ImmutableOctet(SKNG): So, is this just an annoying limitation of Monkey...

Yes. Monkey does not and has never supported self-referential generics in this way.

This is something that annoyed me when making the IComparable interface in Diddy. I couldn't do this:

Interface IComparable<T>
    Method Compare:Int(other:T)
End
Class Foo Implements IComparable<Foo>
    Method Compare:Int(other:Foo)
        ' code
    End
End

Instead it has to use Object and the developer must manually cast.

ImmutableOctet(SKNG)

(Posted 2015) [#3]

@Samah: In my particular case, I was able to get around it with another class for one of my classes, and an interface-based system for the other. Your situation is one of the possible downsides to not being able to do this. The fact is, a dynamic cast is horribly inefficient compared to a virtual call, or better yet, no extra overhead on runtime if generics/templates were used for actual types. Some of my own projects use generic class hierarchies, and I can see where this behavior could become an issue later down the road. I guess there's always interfaces, even if they are slightly slower. On the bright side, this means my code is even more reusable.

By the way, did we even get a proper ruling on generic interfaces? I think they're great, but doesn't the official documentation still consider them unsupported? Well, I don't see why Monkey shouldn't have them, but the documentation should probably say something about this. Here's the portion I'm talking about. They work just fine, though, so I don't see why they shouldn't be recommended.

Samah

(Posted 2015) [#4]

@ImmutableOctet: ...no extra overhead on runtime if generics/templates were used for actual types.

This would certainly help with Diddy's implementation of the Compare() method, then. At the moment it does some dirty dynamic casting magic on each call to check if the object implements IComparable. I suppose I could hack this to cache it as a boolean. I'd have to make a decent shuffle/sort test to check performance.

@ImmutableOctet: I guess there's always interfaces, even if they are slightly slower.

Hmm... I think if interfaces are making it slower, its probably down to usage rather than target implementation. Refactoring large loops to perform casts outside would alleviate this. Even if there's a slight performance hit, I reckon it's a fair trade-off given the quasi-multiple inheritance they provide.

@ImmutableOctet: By the way, did we even get a proper ruling on generic interfaces? I think they're great, but doesn't the official documentation still consider them unsupported?

If I recall, Monkey didn't support interfaces at all when it was first released. When they were added, they didn't support generics. It wasn't for quite a while that Mark added generic support for them. My guess is that the old documentation was never updated and has just been copy-pasted verbatim.

On a related note, I want generic wildcards and bounding. :(

ImmutableOctet(SKNG)

(Posted 2015) [#5]

Yeah, being able to limit what gets past to a generic class would be nice. That being said, virtual method calls via virtual multiple inheritance isn't usually much worse. Virtual calls aren't really costly these days, but when they aren't necessary, I like to reduce them. Luckily in other cases, most normal methods don't see any overhead from virtual calls. Monkey's actually pretty good about only compiling what's used. This means I don't have to worry about virtual overhead all the time, but I do in class hierarchies. Dynamic casts require compiler-specific checks against the RTTI for the object. This is a lot more overhead than what modern CPUs could do with a simple check against a table, and calling the right method. These days, branch prediction makes the overhead from virtual methods basically non-existent after a while. Of course, this is less useful when you have a lot of virtual methods in a hierarchy, because the branch predictor wouldn't be dealing with a single function pointer.

But back on topic, the compiler's tests for "cyclic" inheritance really should be more sophisticated.

Samah

(Posted 2015) [#6]

Classic example:

Class Vehicle
End

Class Car Extends Vehicle
End

Class Truck Extends Vehicle
End

Local cars:List<Car> = New List<Car>
Local trucks:List<Truck> = New List<Truck>

Current Monkey:

Function DoStuffWithVehicles(vehicles:List<Vehicle>)
End

' can't do this, because even though Car extends Vehicle, the generic List<Car> does NOT extend List<Vehicle>
DoStuffWithVehicles(cars)
DoStuffWithVehicles(trucks)

Using wildcard bounding:

Function DoStuffWithVehicles(vehicles:List<? Extends Vehicle>)
End

' these work, because Car and Truck fill in the wildcard
DoStuffWithVehicles(cars)
DoStuffWithVehicles(trucks)

I would assume this is very tricky stuff to implement, though.

ImmutableOctet(SKNG)

(Posted 2015) [#7]

Generic functions and/or methods would be a really good alternative to this. And maybe standard interfaces for the official enumerators...? Speaking of which, the 'Map' class's enumerators still produce more enumerator objects for no reason. They can simply return themselves, so you could just use the 'Eachin' syntax. I do this with my own code all the time, and it works perfectly.

therevills

(Posted 2015) [#8]

Samah writes: Classic example:

So to get around this limitation your initial lists have to be generic type of Vehicle?

Strict
Global cars:List<Vehicle> = New List<Vehicle>
Global trucks:List<Vehicle> = New List<Vehicle>

Function Main:Int()
	For Local i:Int = 0 To 9
		Local c:Car = New Car
		c.name = "Car " + i
		cars.AddLast(c)
	Next
	
	For Local i:Int = 0 To 9
		Local t:Truck = New Truck
		t.name = "Truck " + i
		trucks.AddLast(t)
	Next
	
	DoStuffWithVehicles(cars)
	DoStuffWithVehicles(trucks)

	Return True
End

Function DoStuffWithVehicles:Void(vehicles:List<Vehicle>)
	For Local v:Vehicle = Eachin vehicles
		Print (v.name)
	Next
End

Class Vehicle
	Field name:String
End

Class Car Extends Vehicle
End

Class Truck Extends Vehicle
End

ImmutableOctet(SKNG)

(Posted 2015) [#9]

The real problem with Samah's proposed design structure is that currently, 'Lists' are external from the context of the types themselves. In other words, 'List<Car>' does not extend 'List<Vehicle>'. In most cases, you can just get around this using the code you posted. But, what Samah was getting at was using the compiler to effectively make a method or function generic. His idea was to do this by stating that the type of 'List' must at least inherit the type specified. This means that you could pass any list that at least has the type set as the minimum. The only way around this right now is to use interfaces, which can cause unneeded overhead. The thing is, in Monkey you can't simply write generic methods and/or functions, they have to be inside a generic class. This also means 'trans' doesn't have much for this at the moment.

Interestingly enough, you can technically do this:

For Local V:Vehicle = Eachin Cars ' Where the 'Cars' list is made from 'List<Car>'.
	' ...
Next

But there isn't much of a point to that, unless you're dealing with generics. Even then, it's not all that useful. But anyway, the original point was regarding the lack of ability to write non-virtual code. Monkey still needs generic methods or functions, if you ask me. But the real problem was the fact that I had to use an interface. This is because the compiler blindly didn't care about the context where a class referred to itself. The example I gave works if you remove the generic elements, but of course, that can't be done under certain contexts. The big reasons to use generics are code generation and reuse. If I can't have a generic class hierarchy that unifies generic routines, then that's a limitation. Luckily, Monkey is really good about this normally, but I thought this particular problem was worth mentioning.

To put it simply, under circumstances like my initial example, I'd have to rely on virtual functionality for no reason. Now, virtual overhead is fine when the targeted CPU's branch prediction is solid, but I can't always expect that. Likewise, this kind of situation doesn't even need the extra overhead. Who knows, maybe I'm just over optimizing, but to me, maintaining an interface just doesn't seem worth it for this. There's just too much overhead that could be reduced on compile-time. I'm not expecting the complexity of C++'s templates, but Monkey's generic/template functionality is already really solid. I really just wanted to have a class to reference itself to the rest of the hierarchy. Monkey's compiler doesn't actually deduce this, it would seem. Instead, it just throws an error. This is why I think it's an unnecessary limitation, and it could be solved pretty easily.

EDIT: In case you're interested, I basically just went the interface route. The overhead was for loading managed resources to begin with, so it wasn't a runtime-level optimization. I ended up using this interface for another class of mine, so it ended up being beneficial. Here's the module I'm talking about. It still needs to be optimized, but it's not a bad draft for what I needed.

Samah

(Posted 2015) [#10]

@ImmutableOctet: And maybe standard interfaces for the official enumerators...?

If you take a look at the DiddyStack/DiddyList/DiddySet classes and the IContainer interface, you can see that this is what I've tried to do. I made it so that the Stack/List/Set classes conform to a common interface... kind of. Also the enumerators conform to a common interface... kind of. Check out IEnumerable and IEnumerator to see what I've done here.

marksibly

(Posted 2015) [#11]

> The above example doesn't compile; it will give me an error saying "Cyclic declaration of 'Y'", without being logically wrong.

This is a limitation of the way I've implemented generics, and wont be changing in the near future.