Blog Post

#1433 User Defined Generics

brian Thu 3 Mar 2011

Fantom has parameterized type support for List, Map, and Func (which interestingly means we have a great deal of compiler and runtime infrastructure for a generics type system). But we've never take the steps to turn this into a full blown generics system that any developer can use in their APIs. The omission of user defined generics is a re-occurring issue, most recently discussed ticket in #1393 and also some interesting discussion on Cedrics blog.

Generics seems to be an extremely polarizing issue, sort of like a political litmus test where a single issue might be said to unreasonably outweigh a balanced analysis of trade-offs.

This post is not a formal proposal for generics, rather I would like the share my thoughts and set the stage for the brainstorming on if and how generics should work in Fantom. I think they would be useful, and there are certainly cases where I wish for them. I view this is an engineering decision: examine the problem, brainstorm potential solutions, and then decide if the trade-offs in complexity versus functionality make sense.

Type System Background

First off I just want to restate what I consider a basic philosophy: the type system is one tool of many in the toolbox. Fantom should have a great type system that does as much as possible for us. But we must also accept that no type system is perfect and is going to cover all cases. So we must find the middle ground where the complexity of the type system justifies the value it brings. In 2008 I wrote a mini-blog post about this topic.

However, it is disingenuous to dismiss Fantom's lack of user defined generics as "stepping back in time to Java 1.4". Although Fantom doesn't support user defined generics, it does have features that Java and even Scala doesn't have: nullable types and const types. Yes you can use an Option type for nullable types, but that doesn't fully solve the problem. The key issue with both nullable types and const types is figuring out how they work with OO constructors. The challenge of fully constructing an immutable object with all its non-nullable fields assigned is by far the most complex aspect of Fantom, and as those of you who helped with the design know, it has taken years to get there (and we are still working on it!).

I like to think about these type system features as bringing the following three values:

  1. documention of programmer intent
  2. convenience to avoid having casts or as operators in your code when using type inference
  3. program quality to catch bugs at compile time

To me issue #1 is the most important issue. Fully documenting the interface of a type and its slots in code is mostly worth all the hassles a type system can impose on you. Saying that a reference is never null or guaranteed to be immutable has immense value. And likewise, I believe generics take this a step further to ensure more flexibility for documenting API interfaces.

My personal pet peeve is that when using non-generic class I often have to explicitly cast Obj to the type I want to use. It breaks the flow you often get with type inference. This is largely a convenience issue to avoid writing down the type and making your code ugly with a cast or as operator. It may seem like a little issue, but I believe that is what people really want when they ask for generics. Casting is ugly and mucks up pretty code.

Lastly we come to quality - do type system features really improve the quality of programs by catching bugs at compile time? Lets look at each feature:

  • Nullable Types: compiler and runtime ensures an object's non-nullable fields are assigned - this definitely improves quality and its nice to have "fail fast null" errors, but it is all really just nice enforcement of the real value in capturing programmer intent
  • Const Types: allowing compiler to fully ensure an immutable object is locked down when the constructor completes has huge value in catching bugs. And more importantly the ability for const types to interact with the concurrency model to ensure mutable state is not shared across threads is by far the #1 advantage Fantom has in quality over Java/C# like programming languages. Furthermore if you think actors is only a "library problem", then you don't appreciate how deeply Fantom's type system and concurrency model are intertwined
  • Generics: anyone from the Java community has likely had years of experience pre-1.5 and pre-generics. Do type bugs occur? Yes now and then, but can anyone really make the case that they happened often or were difficult to debug?

Or put another way: how many hours of your life have you spent debugging concurrency bugs? How many hours of your life have you spent debugging type bugs in your collections? Me personally: I've wasted enough hours in my life with concurrency bugs that I'd much rather have the type system address concurrency than collections. Fantom's type system directly addresses concurrency in a much deeper way than even Scala.

Why do I want to review this? I want to draw attention to the fact that nullable types and const types are very important features that address what I perceive as the real quality issues in programs. These features already impose complexity in their interaction with functions, it-blocks, constructors, static fields, etc. So while I would like to get generics into Fantom too, I would never trade const types for generic types. I also want to set the stage that I don't consider the design focus of generics to be about compile time quality control, but more focused on capturing developer intent and type inference convenience. As such I would be willing to make sacrifices in compile-time guarantees if it meant an overall simpler solution. But like everything - what you value in your type system and programming language is a very personal opinion.

Basic Definitions

There are different ways to look at parameterized types, but they way I like to look at them is as a "type factory". In Fantom we can define a type as a set of slots (fields and methods) with specific signatures. A parameterized type is where types used in the signature of its slots is left as a variable to be filled in later. The basic abstraction is not much different than a function where the arguments are left as variables to be filled in when you call the function. Where parameterized types tend to explode in complexity is how they interact with sub-typing in an object-oriented language. Taming this complexity is the prime mission of figuring out generics for Fantom.

Lets consider a simple example using Java syntax for further discussion:

class Foo<T>  {  Void bar(T t)  }

Any parameterized type solution would at a minimum need these basic features:

  • a syntax for declaring a generic type and use of the parameterized types in slot signatures
  • a syntax for instantiating a generic type at a usage site
  • well defined rules for subtyping

Advanced features to also consider:

  • constraints on the type parameters; in our example how can I specify that T must be a subclass of Baz?
  • variance rules for the type parameters; in our example above suppose we have created a Foo<Num>, should we allow bar() to be called with an Int or an Obj?
  • variance of the generic itself: should Foo<Int> be considered a subtype of Foo<Num> ? How about Foo<Obj> ?
  • both Java and C# allow a single method to declare generic parameters which is useful for utility methods

Use Cases

We have a couple of use cases already in the core library:

Plus I really still want to get some sort of Set class into the sys - its is the one core collection class which isn't well handled by List or Map (today I often use Map as a poor man's Set). We have also discussed something like ActorLocal which would be ideal for generics. Other use cases which scream for generics are other collection libraries, typed tuples, etc.

Random Thoughts

As I said at the start, I have no formal proposal. However, after noodling on this problem I have lots of random ideas that I want to jot down (some may seem from left field), but at this point you never know where a random source of inspiration might spring...

Sub-typing is where generics get sticky, especially with the model used with OO subtyping by inheritance. This is where covariance and contravariance issues rear their ugly head (as discussed at length about Fantom's List type). So I've been thinking a lot of how we could simplify or side-step this issue

Are generics useful if they can only be used on final classes?

How would generic sub-typing rules mess with Fantom implicit casting? Even with awesome generic type handling, implicit casting is still extremely useful for reflection code (but maybe we could change implicit casting back to only work with Obj, or have reflection use a new "wildcard" type)

I'm quite enamored with the idea of separating types from implementations - a great example I really like it Clojure protocols, and Go interfaces are sort of the same vein. Suppose a generic type like List automatically generated both an interface and default implementation. Maybe parameterized types could then be "attached" to objects which fit that interface. Maybe it can even happen at runtime as a sort of structural typing feature. Can this path lead to simplification of the sub-typing problem? I can't fully get my head around it, but I keep coming back again and again to this idea as a potential way to both simplify the type system but also make it more flexible.

Is subtype checks something that gets delegated at runtime, not compile time? Like some of the stuff Stephen has been discussing with "explicit conversions"

Maybe Fantom types are true code generation templates that just make an easy way to create a new types by actual syntax substitution - touched on in topic #1420. Obviously very different direction and helps nothing for the subtype issues, but interesting alternative

C# originally didn't have generics variance. Does anyone have experience with that regarding various tradeoffs?

Eiffel has interesting feature called "anchor" types where a method parameter type can refer to a another field/methods type that might be refined in a base class. I haven't thought about that much, but different way to look at the problem. Interestingly from what I can glean, Eiffel always treats Foo<B> as a subtype Foo<A>, if B is a subtype of A (seems to ignore potential contravariance issues).

So anyways, just some random thoughts. Short version: I think generics could be cool, but we have to come up with a design that doesn't impose too much complexity and can integrate with existing type system features, constructors, etc.

msl Fri 4 Mar 2011

Great to see this on the radar for "official" consideration!

Another use case that I keep bumping into is with sys::Type.

Often, it'd be great to be able to do something like:

Type<? extends Something> type

To avoid needing to do runtime checks across the specified type.

djspiewak Fri 4 Mar 2011

First off, interesting stuff. I don't know a whole lot about Fantom, but I think I can address some of the points from a type-theoretic perspective... :-)

In Fantom we can define a type as a set of slots (fields and methods) with specific signatures.

That's dicey. To be a little less vague, what you have just done is defined a type in Fantom as being equivalent to a record type. There's nothing wrong with this, except it flies in the face of nominal typing (which is what Fantom uses). Using record types for everything is actually the same as using structural types, and that's not a change you want to leap into. Scala has an interesting implementation of structural typing which basically maps them as anonymous interfaces which are implicitly inherited by all conforming types. This allows a limited form of structural typing to work in a predominantly nominal system, but it is still limited. An example of a very useful bit of Scala code which does not (and cannot) compile:

type Foo[A] = { def bar(a: A): String }

While it's impressive that Scala was able to have structural types at all, this really isn't sufficiently powerful as to call Scala's type system "structural" or even "hybrid structural". Even more importantly, it doesn't provide a strong enough mathematical framework to allow one to view Scala's types as records. You're going to run into the same problem in Fantom.

Now, I didn't see any place where you actually leveraged this record type framework except towards the end where you were talking about Go interfaces (which is a mostly structural type system). Eliminating nominal subtyping does indeed solve the majority of the problems with parametric polymorphism in an object-oriented context (see: OCaml). However, some complexities still remain (mostly stemming from Fantom's class-based nature rather than prototype-based). More importantly though, I don't think it's possible for Fantom to go to a purely structural type system at this point. Even ignoring backwards compatibility, there's the huge looming platform issue: structural typing is dog slow on both the CLR and the JVM.

Anyway, I don't have any more specific concerns about the structural typing stuff, just a general warning that it's not a sound way to think about the problem. It's an interesting perspective, but the model will break down in painful ways if you go too far in that direction.

C# originally didn't have generics variance. Does anyone have experience with that regarding various tradeoffs?

Ah, variance! This is one of the most-maligned features of Scala's type system, so be prepared for a world of criticism if you go this route. Given Fantom's pre-existing philosophy of "just make it work" (e.g. implicit casting), I would advise not implementing any form of variance (neither call-site or declaration-site). Instead, assume everything is co-variant (this is the common case anyway) and let the casts fail. Erik Meijer has a talk where he claims this is a much more rational and pragmatic way to handle the issue. I'm not sure that I agree with him, but I think it does fit better with the overall Fantom design.

If you do decide to implement variance, then you really need to implement both call- and declaration-site variance. To be clear, call-site variance is what Java has. Declaration-site variance is what C# has. Scala has both. If you only implement call-site, then you end up married to existential types and constantly writing code like List<? extends JComponent>. If you only implement declaration-site, then the situation is even more comical. Consider:

// Scala code, assuming no type quantification (decl-site variance)
class List[+A] {      // covariant in type A
  def insert(elem: A): List[A]       // will not compile!
}

Provably, the only way to implement the insert method here is to have a type parameter B >: A defined on insert. C# doesn't allow this, and as a result, its variance is nigh pointless.

So, variance is a rat's nest that I think you should probably avoid altogether. If you choose not to, then be sure to implement both sides of the equation (call- and decl-site), because one without the other is painful and restrictive.

tcolar Fri 4 Mar 2011

I think generics could be cool, but we have to come up with a design that doesn't impose too much complexity and can integrate with existing type system features, constructors, etc."

That's pretty much my take on it.

Generics are a good idea in general but current implementations I've seen just seem too complex to be worth it (lots of "unintuitive" things to think about), if you come up with something simple that can keep the other Fantom features as they are, sure , but I strongly doubt it.

I think Java couldn't make it simple enough, and Fantom with things like implicit casting, inference and more would probably be even much harder to understand correctly.

Also, since I work on one of the Fantom IDE I'm really not looking forward to generics either ... they are kinda painful to deal with when it comes to tooling in general IMO.

qualidafial Fri 4 Mar 2011

My vote is for a simple generics system with similar semantics to what we can do already with List:

fansh> Num[] nums := [1, 2.5, 3.0f]
[1, 2.5, 3.0]
fansh> nums.each { echo(it) }
1
2.5
3.0
fansh> Obj[] objs := nums
[1, 2.5, 3.0]
fansh> objs.each { echo(it) }
1
2.5
3.0
fansh> Int[] ints := nums
[1, 2.5, 3.0]
fansh> ints.each { echo(it) }
1
sys::CastErr: java.lang.ClassCastException: java.math.BigDecimal cannot be cast to java.lang.Long
  fan.sys.List.each (List.java:529)

Just let me cast to what I want, and let it blow up in my face if I make a mistake. Or, if the cast is invalid e.g. casting a Foo<Str> to Foo<Int>, then give me a compiler error. Anything more than this just turns the type system into an obstacle, and makes me want to tear out generics entirely. To wit:

interface Builder<This extends Builder<This>>
{
  This withFoo(String foo);

  Thing build();
}

interface FancyBuilder<This extends FancyBuilder<This>> extends Builder<This>
{
  This withBar(int bar);
}

Now try to go implement the concrete class for that. Warning: this exercise may make you try to hurt yourself; lock away any sharp objects beforehand.

I do think it would be valuable to enforce some minimum type for each type parameter:

WidgetBuilder<T : Widget>
{
  T build()
}

But that is as far as I'd go with bounded parameters.

casperbang Fri 4 Mar 2011

Would parametric polymorphism in Fantom be reified or by erasure?

One thing I often run into when switching from C# to Java, is how one becomes painfully aware of the duality of the Java type-system. Tooling and developers can grok with MultiComparable : Comparable[X], Comparable[Y] but the compiler itself can not.

So I guess I'd just like to warn against forcing the developer to know internal implementation details at various layers of the compiler frontend, and the whole "What you see is not necessarily what you get".

djspiewak Fri 4 Mar 2011

Beware! Reified generics don't play well with variance in any form. It's even worse once you throw in higher-kinded types, though I doubt that's a feature you would want in any case. Additionally, if you want Fantom generics to be at all interoperable with JVM generics, you're going to need to implement them using erasure.

Erasure isn't so bad in general. Java's implementation is particularly troublesome, made all the more so by existential types (which cannot be reified at all) and by the JVM's abysmal array semantics. Scala does a very nice job of smoothing over the inadequacies with a bit of compiler magic (the ClassManifest typeclass). This magic allows you to do almost all of the things you can do with fully reified generics (even creating arrays!). You still can't do things like inheriting from Comparable<X> and Comparable<Y>, but that's a very dangerous thing to be doing regardless, so I think it's actually a good thing that Scala doesn't allow it.

timclark Fri 4 Mar 2011

Scala does a very nice job of smoothing over the inadequacies with a bit of compiler magic (the ClassManifest typeclass).

In my experience with Scala generics they almost let me write type safe code like I can in Haskell or ML and then erasure ruins it for me! For example the last time I programmed in Scala I couldn't pattern match on a List[Toffee] without suppressing a warning. I'd gladly sacrifice being able to call my code from Java if when I need a Pizza[] (or List[Pizza] or List<Pizza>) my code won't accept Obj[] (or List[anyRef] or List).

djspiewak Fri 4 Mar 2011

If you have a ClassManifest in scope, then the pattern matching is actually able to handle matching on things like List[Toffee]. It's not behavior you should rely on though.

brian Fri 4 Mar 2011

Would parametric polymorphism in Fantom be reified or by erasure?

We would probably stick with existing design which is a hybrid. In Java bytecode they are erased and the bytecode generator inserts appropriate cases (just like Java). However we do keep track of the proper type for reflection:

fansh> [2, 3f].typeof
sys::Num[]

jodastephen Sun 6 Mar 2011

I believe user-defined generics in some form is now considered a language requirement to be succesful. But as you say, null-handling and const types are more critical (and I've said many times that the Java language gods should have tackled nulls, not added generics.

The key issue however is variance. The mass-market developer finds variance confusing and unimportant. Varianace doesn't help document intent, adds complexity and is beyond the point of sensible returns for the feature. Java generics are too complex as a syntax, especially with erasure. These days I find myself taking generics out of code as much as I put it in because generics in Java can't express what I actually need to express.

Firstly, syntax. Java and C# use <T> style constructs, and since they are the target users so should Fantom. Anyone reading these will know what they are without needing to be taught or think (unlike Scala's [T]). For a method defining its own type, having it after the method name makes more sense, although it makes the compiler harder:

static Set<T> createSet<T>(T singleton) { ... }

Quickly looking through the thoughts: Generics cannot just be on final classes, its just too much of a restriction. I don't see a way of separating interfaces and classes without having a radically different developer model and thus ceasing to be easy to pick up from Java. A code generation approach isn't necessary that bad. There has been some discussion of JVM reification by adding an additional "hint" to a type at runtime (cf John Rose). I'm not overly fussed by structural types, although being able to say "this method accepts any class with a name() method" would certainly be useful on occasions. I'm unconvinced at the moment of the need for bounding the types in Fantom generics.

The core of making Fantom generics possible is variance though. My view is that mass-market developers don't choose to care about variance issues (They are perfectly capable of understanding if it is explained to them, but since knowing about it doesn't help them achieve their principal goals of writing business logic, the explanation will typically be rapidly forgotten. This isn't a criticism, just an observation of human nature. We remember two things - what we need to and what we care about.)

Thus in my view, assigning generified types must "just work", and there should be neither call or declaration site variance in syntax.

Set<Num> a := ...
Set<Obj> b := a  // must work somehow
Set<Int> c := a  // must work somehow

Having an unsound type system is undesirable, so should be avoided where possible.

What we do know though is that the JVM is good at inlining code, thus there is a sensible avenue to explore. And that is where my "explicit conversion" concept comes in.

Set<Obj> b := ~a  // explicitly convert between the types
Set<Int> c := ~a  // explicitly convert between the types

(As I've argued before, this makes most sense as a general purpose conversion approach)

With generics, the ~ conversion would wrap the original object with a wrapper (compile or runtime created class) that provides an additional level of safety. For b it would check all additions to ensure that only Num could be added. For c it would check on get that the object really is an Int (this could be checked on conversion at extra cost). The hard part is working out exactly how the compiler can generate the wrapper classes without programmer intervention. I suspect its possible, but I'd love to hear a type-theoretician view.

Obviously, these conversions should operate at the method call point as well as assignment. The real point is that senior developers would understand what the conversion is there for and the overead of using it. Other developers would simply learn that sometimes a conversion is needed. Its this usability focussed approach that is key.

(The ~ operator used here is in a sense orthogomal. The wrapper approach could be used at the point of conversion without the ~ operator. Personally, I prefer to see that my object is being messed with - something Scala makes too invisible in implicits.)

One point to note is that Java already has this, its just not widely used. The only real question for me is if a "checked" class can be generated automatically by the compiler.

MoOm Sun 6 Mar 2011

If I understand correctly, the biggest problem there seems to be with generics is about generic-type variance: i.e. should we allow Int[] to be converted into an Obj[] (or the inverse)?

If I look at my existing code, this kind of implicit conversion seems to be quite rare. Actually, the only situation I can find where I need this feature is when, for example, I've got an Int[] variable and that I need to pass it to a method that takes a Num[].

For example, please consider the following snippet:

Str processNums(Num[] nums)
{
  //...
}

void foo()
{
  Int[] ints := [1, 2, 3]
  processNums(ints) // Here, ints is implicitely converted into a Num[]
}

So indeed, if we don't allow generic-type variance, this code will no longer compile. But then, if we add support for generic method-parameters, I could rewrite processNums to be generic:

Str processNums<T : Num>(T[] nums)
{
  //...
}

void foo()
{
  Int[] int := [1, 2, 3]
  processNums(int) // Now, ints no longer needs to be converted into a Num[].
}

There are other situations I can see where generic-type variance would be useful, but none of them justify the complexity of generic-type variance.

DanielFath Sun 6 Mar 2011

Set<Num> a := ...
Set<Obj> b := a  // must work somehow
Set<Int> c := a  // must work somehow

Ok the third example, lost me how does is a list/set of Num a list/set of Int? It's obvious a list of [1,2.0f,3.0] is both a list of Obj and list of Num, but how is it list of Int?

helium Sun 6 Mar 2011

Ok the third example, lost me how does is a list/set of Num a list/set of Int? It's obvious a list of [1,2.0f,3.0] is both a list of Obj and list of Num, but how is it list of Int?

Both make sense under different circumstances.

Treating a Set of Num as a Set of Obj makes sense if you only read values from the set but never put new stuff in (as you could put any objects into it otherwise). Treating a Set of Nums as a Set of Int makes sense if you only write to it (putting Ints into a set of Nums always works).

mike Sun 6 Mar 2011

One thing that Fantom could do with generics that would represent a great increase in code legibility over Java and C# is typedefing them somehow. For instance, lets say you have two maps, one simple, and the other nested:

Map<Int, String>
Map<Foo, Map<Bar, Set<Quux>>>

Passing around type identifier for the first map is merely annoying. Having to pass around the type identifier for the second map goes beyond annoying into the realm of illegibility. I don't consider the second example contrived either, in fact I've gone further than that before with nesting in my own code.

It would be really cool if there were some way to typedef generic signatures, e.g.

typedef MySimpleMap Map<Int, String>;
typedef MyNestedMap Map<Foo, Map<Bar, Set<Quux>>>;

Then you could pass around much smaller generic types, which would be tagged semantically with their purpose.

There are no doubt all sorts of major problems associated with getting this idea to actually work. However, given that Fantom is finally opening the door to generics, it would be really cool if they were done in a way that represented a major improvement in legibility over other languages.

timclark Sun 6 Mar 2011

I like the typedef idea, I use that all the time in Haskell so that I can make the type signatures shorter and more descriptive.

tcolar Sun 6 Mar 2011

I proposed the typedef concept before too

Obviously doesn't resolve the variance issues, but still worthwhile IMO

Code readability would be way better that the java eyesore.

DanielFath Mon 7 Mar 2011

Treating a Set of Num as a Set of Obj makes sense if you only read values from the set but never put new stuff in (as you could put any objects into it otherwise). Treating a Set of Nums as a Set of Int makes sense if you only write to it (putting Ints into a set of Nums always works).

Why wouldn't Set of Num accept Int? Int is a Num thus you should be able to insert it, no? I presume Set of Num has add(Num a). Parametric polymorphism should be able to handle inserting Int.

helium Mon 7 Mar 2011

Why wouldn't Set of Num accept Int?

Who said this? A set of Num can accept Ints and can deliver Objs. That's they point I made.

I write a function taking a Set<Obj> that only reads from the set so I expect that I can pass in a Set<Num>. If I write a function that takes a Set<Int> and adds a few further Ints in there I expect to be able to pass a Set<Num>.

// Only reads from foo, so sets of derived types are OK
Obj getAny(Set<Obj> foo) // really Set<Obj or subclasses>
{
   return foo.first
}

// Only writes to foo, so sets of base types are OK
Void put42(Set<Int> foo) // really Set<Int or baseclasses>
{
   foo.add(42)
}

Void main()
{
   set := Set<Num>(3.14159, 2, 17.5f)

   echo(getAny(set))

   put42(set)
}

Things are covariant if you can only read from them, contravariant if you can only write to them.

Fantom will probably just always allow both co- and contra-variance and throw a runtime exception if something goes wrong, similar to what it does with its list type.

helium Mon 7 Mar 2011

@djspiewak:

Provably, the only way to implement the insert method here is to have a type parameter B >: A defined on insert. C# doesn't allow this, and as a result, its variance is nigh pointless.

How often do you really need this? In the code I've seen so far everybody is happy with a non-variant list and a covariant read only interface implemented by that list type.

brian Mon 7 Mar 2011

Just to keep things on track - detailed analysis of co-variance and contra-variance is not really applicable to Fantom. For some reason all discussions of type systems seem to lead to ensuring your type system can cover every case at compile time. As Fantom practice has shown (for those of you using Fantom on a day to day basis), the existing type system with implicit casting works well. It catches almost all the stupid stuff you might do, but doesn't suffocate you. In fact I can't remember the last time I had a class cast exception in my code.

So as a general principle co-variance and contra-variance rules can be ignored because the compiler is going to ignore them anyways. In fact the only place this comes into play today is Type.fits (and that could use some simplification anyways). So the basic principle is this: if the code could work, then it will compile. If it could never work, then it will not compile. This is why:

  • Num[] can be where a Int[] or Obj[] is expected
  • Str[] can not be used where Int[] is expected

On typedefs, if it looks like we end up with generics in the Java sense of Foo<Bar>, then a simple type alias mechanism would be useful too.

cbeust Mon 7 Mar 2011

Regarding typedefs: you can do without today simply by creating a class that extends your complicated generic class. They also come with their own set of problems (e.g. error messages), and since they are orthogonal to the current discussion, I don't think they should be high on the priority list.

ahhatem Tue 8 Mar 2011

Type aliases are nice... but they are specifically important when there is no static type inference... This was really obvious in LINQ in .net it used generics and involved complex generics that no one had to remember since you just use: var x = ... So, Type aliases are nice but not mandatory.

MoOm Mon 18 Apr 2011

Duplicate post

MoOm Mon 18 Apr 2011

Here is my proposal for generics in Fantom.

Generic class

Proposed syntax:

class Node<T>
{
  T get()
  Void set(T v)

  private T val
  private Node<T> next
}

would compile the same way as the following code:

class Node
{
  Obj get()
  Void set(Obj v)

  private Obj val
  private Node next
}

When using an instance of Node, (for example Node<Str>), the compiler will check that type constraints are satisfied (i.e. the parameter passed to set() is a Str...).

Multiple generic params:

Multiple generic params could be specified by separating them by commas. For example:

class Pair<S, T>
{
  S first
  T second
}

Generic methods:

Methods can be parameterized the same way classes can:

class NodeUtil
{
  Void dumpNodes<T>(Node<T> first)
}

Constraint on the superclass of a parameterized type:

The following syntax could be used to guarantee that Node only contains Vehicle instances:

class Node<T : Vehicle>
{
  T get()
  Void set(T v)

  private T val
  private Node<T> next
}

would compile as the following code:

class Node
{
  Vehicle get()
  Void set(Vehicle v)

  private Vehicle val
  private Node next
}

The compiler would ensure that the code never instantiates a Node with a type that does not inherit from Vehicle

I don't think its worth it to support an equivalent of the <T super Vehicle> java-syntax.

Variance of the generic class:

Should an AtomicRef<Str> also be an AtomicRef<Obj>? Personnaly, I don't think this feature is worth the effort it would require to make this works. And it might lead to errors that might not be easy to debug. For example:

AtomicRef<Obj> getValue()
{
  return Unsafe<Str>("foo")
}

// Later
val := getValue()
val.set(`/home/toto/file`)  // From this location in code, it's not obvious that this call is dangerous

The only class I would like to have variance-support is List as we make heavy use of it and some variance can be sometimes handy. But even this, I can live without it. Last point about List variance: I would not support variance of List of value-types: i.e., I would forbid List<Int> to be referenced by a List<Obj> variable. Allowing that makes it really hard to offer a fast implementation of List for value-types: it would be really nice if List<Int> could be natively implemented by a Java long[] array (instead of Object[]), but variance of value-type Lists makes this really hard to happen.

Variadic generics:

At some point, I'd really like to have variadic generics. Something like this:

class Func<V...>
{
  Obj? call(V... params)
}

It would be great in order to implement an event-based system for example. But I guess we probably should not focus on this as it is definitely not the priority.

In a first time, it would be great if we could have several generic classes with the same name but with different numbers of paramaterized types. For example:

class Func<>
{
  Obj? call()
}
class Func<A>
{
  Obj? call(A a)
}
class Func<A, B>
{
  Obj? call(A a, B b)
}
...

What are your thoughts about all of this?

brian Tue 19 Apr 2011

@MoOm,

I think that is a pretty solid proposal. I definitely think we will use the syntax you described for types (and probably methods).

Constraints we might do, although worse comes worse you can handle that in code with casts.

Regarding variance, I think I am going to totally ignore it. The basic Fantom static type system philosophy is this: if we know it can't ever work at runtime then make it a compile time error. If it might work at runtime, then let it compile and have the runtime throw an exception when it doesn't work. This is already the philosophy with List variance (just ignoring/allowing co- and contra-variance), and is pretty much what I am thinking for user defined generics.

MoOm Tue 19 Apr 2011

Thanks for the feedback Brian!

About variadic generics, another way (that I personnaly prefer) of doing it would be by using default values for type-parameters. Consider the following example:

class Func<Ret = Void, A = Void, B = Void, C = Void, D = Void, E = Void>
{
  Ret call(A a, B b, C c, D d, E e)
}

Func<> func1            // equivalent to |->| func1
Func<Int, Str> func2    // equivalent to |Str->Int| func2
res := func2("foo")     // will compile fine
res := func2("foo", 23) // won't compile as 2nd parameter should be Void (i.e. not specified)

Variadic generics could also be used to build simple tuples:

class Tuple<A = Void, B = Void, C = Void, D = Void, E = Void>
{
  A first
  B second
  C third
  D fourth
  E fifth
}

Tuple<Int, Float, Str> tuple
tuple.first = 20     // ok
tuple.fourth = "foo" // won't compile, "fourth" is Void and cannot be assigned

Another feature I'd like to have, if we do variance by adding runtime checks as you suggested, would be to have a "non-generic" version of each generic type, which would just be a shortcut for the generic version with Obj? type-parameters. This way:

Unsafe would be a shortcut for Unsafe<Obj?>
Func would be a shortcut for Func<Obj?, Obj?, Obj?, Obj?, Obj?, Obj?, Obj?>

This way, the generics would be backward compatible with existing code, and the non-generic version could be used, thanks to variance, to reference any parameterized instance of the type.

brian Wed 20 Apr 2011

Using Void as a poor man's variadic is a pretty good idea. At the very least we'll want to do something for Func, although maybe we can get by and say with the special syntax, that you to have to fully parameterized all 9 type variables.

rfeldman Wed 20 Apr 2011

Might using Fantom's nullable syntax be a more concise/intuitive way to specify variadics than Void?

class Tuple<A?, B?, C?, D?, E?>

mike Wed 20 Apr 2011

+1 to Tuples. Combining them with a simple typedefing scheme and multiple assignment would be most excellent.

typedef Foo Tuple<Int, Float, Str>

Foo a()
{
   // .....
}

Void b()
{
   (x, y, z) = a()
}

Akcelisto Tue 26 Apr 2011

Generics is good. But today thinking about its is very early.

Fantom has many other more important issues which more annoyed.

  1. lack of arm in fantom lib
  2. problems with serilization (take off short ctor, no clearly pre- post- hooks)
  3. lack of extension methods
  4. hard syntax for mutable fields in actors
  5. lack of repository like "maven central"

Lack of user-defined generics is insignificant in comparison with this issues.


Suggestions:

  1. Extend list of fantom-defined generics for Unsafe
  2. Remove const for Actor. Consider all non-const fields as thread/actor local fields and throw Err if there is calling from another thread/actor.

Is there something else?

Tuples and sets? Just add them in sys with fantom-defining generics.

And forgive about generics before Fantom 3.0 or 4.0.

brian Wed 27 Apr 2011

All good comments, I think we could easily make the case that other features should trump generics in terms of "pain". Although generics deserve a look for 1.0 b/c they have the potential to make you rethink things with breaking changes.

Right now the central repository is next up to be done very soon. I will be posting a proposed design this week.

tcolar Wed 27 Apr 2011

Cool ... central repo is one that i keep wishing for often ....

tompalmer Tue 17 May 2011

Been gone for a long while. Happened to check in today. I like the thinking that MoOm discussed and the further discussion by Brian. I agree that if it's to be done, then done sooner than later is important, relative to how APIs are designed. I also agree that it's best to use generics as a very basic safety net and just to let the rest be handled by runtime checks.

MoOm Wed 30 Nov 2011

There is a subject somehow related to generics that has not been talked about yet: it's generics and constness. If we add generics in Fantom and I want to implement a generic class Set with them, I'd probably want this class to be able to contain mutable and immutable objects. And I'd like to able to call toImmutable and isImmutable on a Set, the same way I do on a List or a Map.

The problem is that toImmutable and isImmutable are non-virtual methods, and are actually overridden by the compiler on each const-class.

I see two ways to solve this problem:

  • make toImmutable and isImmutable virtual methods. This way, I could override them in the Set class. I can see two downsides of this approach: first, this will allow the user to do dangerous things if he doesn't implement them correctly (he could then share mutable objects between threads - but he actually already can do this with Unsafe). And I won't know at compile-time that I'm calling a mutable method on an immutable instance as the mutable and immutable Set share the same interface (there is the same problem with List and Map, but I don't think it's that much of a problem)
  • second approach: I could implement a MutableSet and a ImmutableSet. I could use constructors to do the immutable/mutable conversion. The problem is that I will have two classes and it won't work with actors.

brian Wed 30 Nov 2011

Good thoughts, although I actually think we can handle toImmutable as an orthogonal problem because that conversion is really a part of the runtime API, not the type system.

Set will be built in as a core collection, so its really custom collections. I personally dislike the whole Mutable vs Immutable different types and would like to keep them as implementation details. But think there is some design work to do - I think we can do something where you can customize toImmutable, but it is still checked by the run-time.

detroitmatt Wed 7 Mar 2012

Stephen's suggestion is an interesting one, but it doesn't really function as a generic did in Java or C#. Since we're borrowing from that syntax, we should avoid replacing that old behavior. Rather, I think a "where" clause would be more useful

static Int byteArrayToInt(Byte[] b)
   where b.length <= 4	//4 bytes in an int
{ 
   // elided
}

Violating the terms of the "where" clause throws an ArgErr. If we want to avoid creating new keywords, "where" could be "if", or something else that makes sense. This allows us to specify preconditions programatically in the header, which is preferable for contract design.

This is becoming irrelevant to the discussion of generics in Fantom, though, so I'll offer my thoughts there:

I'm all for them, as long as they don't use Type Erasure (C# had much better generics than Java). They can make code more readable (Or admittedly, unreadable if abused), and they allow for classes that manipulate classes, (as opposed to objects representing classes reflectively). In fact, i think they're very well suited to Fantom implementation, because if you don't like them, it's easy enough to work around using the dynamic typing features. Meanwhile, they help us avoid downcasting (Which I can't be more averse to). I think as Fantom grows, more and more we're going to want generics. Generics are very helpful for developing libraries (Especially if you're coming from a static-type background), so supporting them will naturally facilitate library development in the language, which is good for its maturity and growth. Java and .NET made the mistake of not planning for generics, and it really intruded in their languages when they finally did add them (Java had to adopt that awful erasure system). Generics are a big feature, if we try to add them too late, they'll be intrusive. It'll be earlier and easier to add them now than later.

Edit: Oh crap, I just realized this thread is months dead... Sorry D:

Xan Fri 9 Mar 2012

I like generics, very much, overall for definining generic sum of objects

sum[T](T a, T b) {a + b}

but we should assure that T has operator + defined. I don't know how to do it technically but surely other people know it. Just say it for take into account.

For the other hand, if brian and others implement generics, for what version we could spect it? Fantom 2.0?

Xan Sat 10 Mar 2012

With asserts we could define more problematic things. I explain: what do you define this (in Scala):

sum[T](T a, T b) {a + b}

in Fantom?

First of all, a and b have to be the same type And a and b have to have + operator

Witg asserts we have to do it:

sum(Obj a, Obj b){
    assert(a.typeof = b.typeof)
    assert(a.typeof has OperatorSum)
   sum (a, b) {a + b}
}

we could pass asserts to constructors than assure we can construct classes

(the above was pseudocode, but you could image the code in Fantom)

DanielFath Sat 10 Mar 2012

It's an interesting idea. But thing that so far struck brian's fancy was a Go-like interface system.

What that means is this:

interface Summable
{
  Summable plus(Summable a) { return this+a }
}

Now any class that has plus method is now summable so for instance:

Num is Summable true 
Int is Summable true
List is Summable false

If you had Go-like interfaces you'd probably not have any need for generics(other than the genericness of interfaces). However issue with this is that since there is no method overloading it kinda gets tedious writting all the possible ways a thing can be plussed. E.g.

interface SummableByFloat
{
  Float plusFloat(Summable a)
}

interface SummableByInt
{
  Float plusInt(Summable a)
}

dobesv Sun 11 Mar 2012

I think the main thing I have used generics (i.e. parameterized types) is to avoid casts and improve compile-time checking on data structures. So for example if I have the ability to delcare Actor[MyMessage,MyResponse] then the receive() method takes MyMessage and returns MyResponse and the send() method only takes a MyMessage and the resulting Future only returns a MyResponse.

There are a number of re-usable classes that can accept a variety of types where they don't do much with it but pass it along, but they would be better type-checked (and documented) using parameterized typing.

Just recently I had the problem where I changed the type of message received by an Actor but didn't update all the places that sent it a message. If the compiler had helped me I would have appreciated that.

Daniel you are talking about what you might call "protocols" / "duck typing", where you want to say "this method accepts anything that has a plus method". Basically like interfaces but your classes "auto-implement" interfaces they conform to even if they don't declare it explicitly. In a language that has explicit traits and interfaces it's there to fill in the cases where you can't (or don't want to) change the type signature of the object you're passing in. I haven't run into this very much in Java. I don't think people "accidentally" implement interfaces very often - you almost always always need some kind of API mapping.

Xan Fri 23 Mar 2012

I don't like Go-like interface structures. These imply that you have to define more code than you could define with class-based structures.

Something like

sum[T](T a, T b) {a + b}

is shorter and understandable than defining an interface...

I think we think in different things: one is what programmer code and another is what compiler do.

If programmer code:

sum[T](T a, T b) {a + b}

the compiler really do this:

sum(Obj a, Obj b){
    with(a.typeof = b.typeof)
    with(a.typeof has OperatorSum)
    return sum (a, b) {a + b}
}

you could implement interfaces in the compiler but let programmer free to do that. It's a tedious think.

For the other hand, Go-interfaces forgets pure Object Oriented aspect of Fantom. Please think about....

With respect, Xan.

Login or Signup to reply.