[RFC] New Generics

[peq]

Currently, generics are translated using erasure. This means, that generics can only be instantiated with types compatible with int. The idea of this proposal is to change the translation and instead of using erasure translation would generate one copy per instantiated type. This would allow to extend generics with some interesting new features, but would also be incompatible in some cases.

Language changes:

1. Allow all types for generics

Every type can be inserted for a generic type parameter without any restrictions.

For example, we can then use LinkedList<vec3>.

This also allows us to get rid of the implicit calls to fromIndex and toIndex that we currently have as a woraround.

2. Allow to restrict type parameters / type classes

Sometimes we want to restrict type parameters.
For example LinkedList<T>.toString() returns string only can be implemented, if we have a method toString(T) returns string.

We could of course provide this method using an additional argument:

LinkedList<T>.toString(Show<T> elementShower) returns string
      ... elementShower.toString(x) ...

interface Show<T>
    function toString(T elem) returns string

However, it is not very convenient to always pass this Showvalue explicitly.

Instead we allow to use generic interfaces as type constraints:

function LinkedList<T>.toString<T : Show>() returns string
      ... T.toString(x) ...

interface Serializable<T>
    function encode(T t) returns string
    function decode(string s) returns T

function LinkedList<T>.encode<T : Serializable>() returns string
    ...
function LinkedList<T>.decode<T : Serializable>(string s) returns T
    ...

The compiler automatically finds instances that are defined with the new instance definitions:

instance Show<vec2>
    function toString(vec2 v) returns string
        return "(" + v.x.toString() + ", " + v.y.toString() + ")"

// make all lists with serializable elements serializable:
instance <T : Serializable> implements Serializable<LinkedList<T>>
    // implement methods here

If multiple instance are in scope there is a compilation error.

The instantiation is part of the type, so the following example is not allowed:

package A

public interface Ord<T>
    function lessEq(T a, T b) returns boolean

instance Ord<string>
    function lessEq(string a, string b) returns boolean
        return a.length() <= b.length()

public class TreeSet<T : Ord>
    ...

public TreeSet<string> mySet = TreeSet.create("a","aa","aaa")

package B
import A

instance Ord<string>
    function lessEq(string a, string b) returns boolean
        return a.length() >= b.length()

init
    TreeSet<string> s = mySet // error, because Ord intances are not compatible

To resolve instances, we first match the parameters and then match the type constraints from left to right.

Type class translation: The translation uses monomorphization (like traits in Rust) when translating to Jass and dictionary passing when translating to Lua.

3. Disallow casting to int

Since we now allow all types to be used for type parameters, we can no longer cast type parameters to int. However, we can use the new feature of restricted type parameters to implement the same feature:

Old HashMap:

public class HashMap<K,V> extends Table

	/** Whether a value exists under the given key or not */
	function has(K key) returns boolean
		return hasInt(key castTo int)

	/** Saves the given value under the given key */
	function put(K key, V value)
		saveInt(key castTo int, value castTo int)

	/** Retrieves the value saved under the given key */
	function get(K key) returns V
		return loadInt(key castTo int) castTo V

	/** Removes the value saved under the given key */
	function remove(K key)
		removeInt(key castTo int)

New HashMap

typeclass Indexable<T>
    function toIndex(T elem) returns int
    function fromIndex(int index) returns T

public class HashMap<K : Indexable, V : Indexable> extends Table

	/** Whether a value exists under the given key or not */
	function has(K key) returns boolean
		return hasInt(K.toIndex(key))

	/** Saves the given value under the given key */
	function put(K key, V value)
		saveInt(K.toIndex(key), V.toIndex(value))

	/** Retrieves the value saved under the given key */
	function get(K key) returns V
		return V.fromIndex(loadInt(K.toIndex(key)))

	/** Removes the value saved under the given key */
	function remove(K key)
		removeInt(K.toIndex(key))

To simplify the transition, we could automatically interpret the old code as the new one.

Also we can automatically create some useful instances for all classes, for example the Indexable above.

A challenge here is that for Jass and Lua different type classes would make sense:
Casting classes to int in Lua is an ugly and leaky workaround and not really needed as we have tables to store stuff without indexes.

4. Disallowing casting between different instantiations

Currently the following code is valid:

class A
class B extends A

function foo(LinkedList<A> l)

@Test function testCast()
	LinkedList<B> list = asList(new B, new B, new B)
	foo(list castTo int castTo LinkedList<A>)

With the proposed changes this would still compile, but might no longer work, since translation might create complete different code for List<A> and List<B>.
Maybe it makes sense to guarantee that all instantiations with class types share the same code (same as it is now), but this is difficult to implement in combination with typeclasses.

[Cokemonkey11]

The idea of this proposal is to change the translation and instead of using erasure translation would generate one copy per instantiated type.

Can you explain what this means/how this works? I'm interested to know if the compiled jass looks any different.

It seems that this is a pretty breaking change, and one that less experienced programmers are more likely to be confused by. vJass, older C++, and older Java (including what you might see as a student/junior engineer) prefer inheritance over type interfacing.

Is it possible to ease the burden on wurst users, for example by gating this behind a feature flag?

# wurst.build
wurst_generics = "2019"

[Frotty]

Can you explain what this means/how this works? I'm interested to know if the compiled jass looks any different.

Right now generic classes are simply classes, and the generic type is cast to int via the typecasting bug. Thus it is erased during compilation, similar to Java.

The plan is to actually keep the type (allowing us to use the actual respective hashtable functions, e.g.) and not casting it to int anymore.
This will of course mean that if you have a LinkedList<Indexable> and LinkedList<MyInterface>, it will result in 2 classes in the compiled jass.

It seems that this is a pretty breaking change, [...]

Not necessarily. Peq already mentioned that the old code could still be interpreted the old way, and basic usage of generics will stay compatible. Only unsafe casting like LinkedList<X> castTo LinkedList<Y> would break.

Is it possible to ease the burden on wurst users, for example by gating this behind a feature flag?

Sure, but I don't think it is ever useful to make language features dependent on passed arguments. It will just always be a problem/confusion in the future, I believe.

[Cokemonkey11]

Not necessarily. Peq already mentioned that the old code could still be interpreted the old way, and basic usage of generics will stay compatible. Only unsafe casting like LinkedList castTo LinkedList would break.

Is that also true for casting up/down an inheritance hierarchy?

That's the use-case I envisage newer users to be abusing

[peq]

Is that also true for casting up/down an inheritance hierarchy?

No, you would still be able to cast A to B if A and B have a common super-type. Only if A and B are unrelated types (like LinkedList<Unit> and LinkedList<Entity>) there would be incompatibilities. And these cases already give you a compilation error, so the only way you can notice the incompatibility is if you cast to int first.

So I think this would be a minor incompatibility.

[peq]

Updated section 2 on "restrict type parameters"

[peq]

Updated section 2 again. With these changes interfaces stay like they are, which should avoid some confusion for users and compiler implementers.

I'll try to release a first version on the weekend (See PR #931).
Then we'll try to update the standard library and probably will find more problems.

[AndyClausen]

inb4 WurstScript becomes Typescript

Thank you all for still working on this. It's making me want to give map-making a shot. I was almost scared away when I today looked up JASS, but seeing this makes me hard excited. Although, I might wait until this is ready for user testing.

Keep up the good work! And don't let Reforged kill your spirits ❤️

[Frotty]

Thanks. If by Although, I might wait until this is ready for user testing you mean waiting for this feature to be implemented before trying out Wurstscript, I don't think that's a good idea 😅 .
Reforged itself isn't so bad I guess, but killing classic and blizzard's general handling of wc3/the situation discouraged me somewhat and I have been inactive for some time.

[Cokemonkey11]

@peq revive new generics? :)

[peq]

Just started a real job this year. Probably gonna be some time before I'll be hacking Wurst again.