#1393 Generics support

ahhatem Mon 17 Jan 2011

Are there any plans to support generics (a la C# not Java)? I believe they are very nice in maintaining static typing... which is especially useful when writing a library that will be heavily used by others... I Think that Fantom is great because it feels like ruby but with static typing which gives me java or scala performance...

So, are there any plans to support them?

DanielFath Mon 17 Jan 2011

There have been at length discussions about generics, andy and brian dislike them and to my knowledge their opinions on them haven't changed. See http://fantom.org/doc/docIntro/WhyFantom.html#generic for why they dislike it.

Generic support is a rather interesting issue that has unfortunately been discussed ad nauseam.

brian Wed 19 Jan 2011

I think a simple non-variance based user type parameterization will eventually make it ways into Fantom. But not anytime in short term.

DanielFath Wed 19 Jan 2011

Really? Any example what non-variance based type parametrization means (other than C++ templates).

helium Wed 19 Jan 2011

C# 2 or 3.

ahhatem Wed 19 Jan 2011

Just a little thing to consider: Generics help build the apis differently (like the change in many apis in the .net framework after c# 2), so, IMHO that should be better done the sooner the better, since in my personal belief, Fantom will gain a lot of adoption in the next 2 years, which will probably be associated with the writing of lots of libraries, so, I personally believe that this is better done with the generics part of the lang to obtain the best from the start....

helium Wed 19 Jan 2011

Yes, in .Net there is a lot of code duplication because of the late introduction of generics.

andy Wed 19 Jan 2011

Most of the core APIs already use parameterized Lists and Maps - so I don't consider this a big an issue as it is/was in C# or other languages. Might be worth a look at what might change tho.

vkuzkokov Wed 19 Jan 2011

That's not core APIs we're talking about. There can be custom containers, channels, generic algorithms or anything else that won't be properly typed until the introduction of generics.

tactics Thu 20 Jan 2011

Generics are a popular topic of controversy with Fantom.

The reason is that the target userbase (existing Java and C# developers) have become so reliant on generics. They look at Fantom's type system and see it as a weak version of C#'s.

But there's another way to look at the issue. Instead of thinking of Fantom as a "weak C#", think of it like a "strong Ruby". The type system is there only to keep you sane. Automatic upcasting, dynamic invoke, local type inference, sys::Env.compileScript, and the streamlined reflection API make it feel like a dynamic language.

And in a dynamic language, the notion of generics is completely unnecessary.

Since a type has to be ascribed to each object in Fan, we get a paradigm shift where using Obj becomes best practice. Auto-upcasting makes much of the code look exactly the same as if we had used generics. It also simplifies the language significantly.

The only drawbacks are that some type-checking must be performed at runtime, and the type signature do not capture as much information as they might in C#.

But the cost of a fully-featured generics system in your type system is enormous, both in terms of the programming language itself and the barrier to grok what another coder wrote. Sometimes, it's better to ignore the fact the parameter is a List<Map<Int, List<Int>>>, and instead, call it a List and rely on programmer intuition to reason about how it can be used.

Fantom's built-in generics provides a fair compromise between type-safety and type-freedom. Type-checking is merely sanity-checking. You must still prove the program's correctness through testing, and that is true entirely regardless of what language you're using.

rfeldman Thu 20 Jan 2011

Well said.

Personally, I think the only real argument for generics being supported in Fantom at some point stems from this part in the docs, which I agree with wholeheartedly:

Programming is about constructing well defined contracts between software components - type systems aren't perfect, but they do a pretty good job for documenting and defining these contracts. If I want to write a method which expects a Str and returns an Int, then that should be captured right in the code.

I remember creating a Java class called something like RecordPage<?> which represented a single page in a paginated view (e.g. "Page 2 of 4, showing records 11-20"). It held a count of total records, what page was being displayed, how many records to show per page, and a list of the individual records.

From a contractual standpoint, it made the code cleaner that I could do RecordPage<User> and RecordPage<Comment> - it was easier to understand what methods were expecting and returning than if I'd been stuck with the ambiguous RecordPage everywhere.

So while I agree that "in a dynamic language, the notion of generics is completely unnecessary," Fantom is a language that aspires to bridge the gap between static and dynamic languages, and conceptually generics (or something like them) do seem to fit somewhere into its stated goals of clear contracts in software.

Exactly where and how, granted, remains unclear.

vkuzkokov Thu 20 Jan 2011

Sometimes, it's better to ignore the fact the parameter is a List<Map<Int, List<Int>>>, and instead, call it a List and rely on programmer intuition to reason about how it can be used.

Also known as "programming by coincidence".

If it's open API you must not rely on anything and give as much information as possible.

If it's local variable its type should be inferred. Combined with very limited presence of overloading in Fantom your code will be at least as clear as without generics.

DanielFath Thu 20 Jan 2011

So most people agree what there is some need for generics. Does anyone have any idea what ideal generics in Fantom would look like (not looking like java isn't much of a description)?

tcolar Thu 20 Jan 2011

Personally I don't care for generics (at least the way they are implemented in Java for sure).

The limited support for collections in Fantom is enough for me.

Generics mostly add a lot of complexity(learning/tooling) that is not really needed with a language like Fantom (nice syntax).

If anything is done, I would want a "bare minimum" approach to it (no ugly list<Map<Int, List<Int>>>'' or <? extends ....>'' please !

tactics Thu 20 Jan 2011

@vkuzkokov

If it's open API you must not rely on anything and give as much information as possible.

"Give as much information as possible" isn't right. It should be "give as much information as practical".

There are tons of invariants that are impractical to specify in a useful type system:

  • In creating a new array, the length must be non-negative. (This is possible in C, but not Java).
  • In querying a database, you must provide a well-formatted and sanatized query string.
  • In concurrent programming, functions run in parallel must be proven dead-lock free. (This can actually be encoded into a type system, such as in Software Transactional Memory).
  • In RPC code, you have to prove the program to be non-malicious, either by sanitizing inputs or by restricting how the program may interact with the outside world.

I hope you agree that there is a lot of contractual information that cannot be captured by a Java or C# type. Some of these guarantees can of course be checked at runtime, but the point is that they can't be checked statically.

Fantom is just like them, except it adds a few others, such as this:

  • In collections, you must always pass the same kind of object if you expect the collection to return the same kind of object.

jodastephen Thu 20 Jan 2011

I've come to believe that a better solution to generics than Java and Scala is possible.

Java's solution has variance in your face (? extends and ? super). The original authors thought that extends and super would be for experts only, but it didn't work out that way. Every time I try to write APIs that aren't collections, the whole system fails.

Scala's solution has simpler variance (defined by the API author), but of extraordinary complexity. The generics system of Scala is turing complete. Very clever, but completely inappropriate. The "Javadoc" has to be specially simplified to actually make it usable.

I have two approaches. Firstly use the ~ operator to convert when appropriate. Converting a List<String> to a List<Object> is unsafe, so the ~ operator marks it as such (and probably wraps the original list in a type checker):

List<String> a := ...
List<Object> b := ~a

As I've previously pointed out, conversion ~ is just a general purpose operator.

The second part is to think of this as "constraints", not generics. I frequently want to express a constraint on a number for example, or the allowed values of a string:

Void processDay(Int<1..31> dayOfMonth)
Void processAirport(Str<[A-Z]{3}> airportCode)

Each constraintable class would essentially have a constraint processing engine that is called at compile time to handle the constraint and add suitable checks.

Of course this is a radical set of changes. And one I suspect won't be adopted. But it is the route of a really powerful yet usable language.

tcolar Thu 20 Jan 2011

@jodastephen That kinda look more useful in general than java generics(like the constraint example) and a lot less noisy.

In general, I'd be curious to see if some other languages might have implemented generics in a simpler/cleaner way (Java is probably the worst) or maybe some sort of alternative to generics that allow similar results.

helium Thu 20 Jan 2011

If anything is done, I would want a "bare minimum" approach to it (no ugly list<Map<Int, List<Int>>>'' or <? extends ....>'' please !

So what is the bare minimum?

And I'm not sure I understand the purpose of your example. Are you saying that [Int:Int[]][] is a lot easier to understand than List<Map<Int, List<Int>>> or is it your aversion against < > to pass parameters or what is it?

DanielFath Thu 20 Jan 2011

I'd personally like to see something amongst the lines of Go interfaces which are implemented without explicitly specifying which interface it implements. In other words you implement an interface by satisfying all method signatures in that interface. Go isn't OO but some kind of rough translation would look like this.

interface Comparable
{
    Int compareTo(This that)
}

class Float //it implements the interface Comparable.
{
   Int compare(Float that)
}

Usually when I use <? extends Foo> I just want to say "my generics needs to be able to use Foo slots".

interface Foo
{
  void doSomething()
}

class Bla 
{
    Foo
}

Final step would be going beyond This keyword and adding full generics to such interfaces.

interface Greater<T,V> 
{
  Int compare(T,V)
}

However I can see how certain properties of such interface might overlap with OO principles and Object hierarchy. Anyway those were my 2 cents.

helium Thu 20 Jan 2011

However I can see how certain properties of such interface might overlap with OO principles and Object hierarchy.

What do you mean by overlapping "with OO principles and Object hierarchy"?

tcolar Thu 20 Jan 2011

I don't know I guess I never write long winded generics like that List<Map<Int, List<Int>>> anyway

I sure really don't like the way it looks when they are nested.

Would it be OK to NOT allow nested ... I see it could be more work for those rare nested case but it would be cleaner, so say you really want your <Map<Int, List<Int>>> type, you would have to do something like that:

Type ListInt := Int[] // so it would only allow Integers or subclasses of integer
Type FunnyMap := Map[Int:ListOfInt]

Then you could have code like this:

FunnyMap internalMap
Void addList(Int index, ListInt list) {lists.put(index, list)}
ListInt getList(Int index) {lists[index]}
FunnyMap getAll() {return lists}

I guess it adds work declaring the types, but it makes some for much clearer code.

dunno

DanielFath Thu 20 Jan 2011

What do you mean by overlapping "with OO principles and Object hierarchy"?

I'm not sure if such concept competes with existing object hierarchy and when you should use one or the other.

I think the areas where such interfaces would be most useful is implementing operators such as plus, minus, get, set etc. Concertizing conventions such as shortcut operators into code.

@tcolar: I'd personally call them alias unless such types could define extra behavior. And uggh no definetely wouldn't like to have to flatten each Map/List into a single type.

tactics Thu 20 Jan 2011

One more point I want to add.

My theory is that Java and C# programmers don't really like generics. But a language without generics forces programmers to use Obj a lot.

And Java and C# hate Obj.

They hate Obj because it provides the weakest possible contract. When you have an Obj object, you know absolutely nothing about it. You have to look at the surrounding context.

But this is not unique to Obj nor to Fantom. There is a much bigger offender that has become an absolute standard in every programming language in use.

It is the String type.

String is what you use when you want to avoid the type system. You can store anything you want in a String.

Here are a handful of common String objects you'll use:

  • A valid SQL query
  • A well-formatted application serial key
  • A well-formatted XML/JSON document
  • A well-formatted datetime string
  • A well-formatted regular expression
  • A "good-enough" formatted HTML string
  • A wiki-formatted document
  • The name of an application-specific configuration option or command-line switch
  • The name of a valid RPC server
  • The name of a DNS server or well-formatted IPv4/v6 string
  • One of several string constants used as an informal enumeration type
  • The valid name/username/ID for a database/business entity
  • A single-line text string (textbox.value = foo bar baz, control characters forbidden)
  • A possibly multi-line string (textarea.value = foo\nbar\nbaz, control characters forbidden)
  • A textual representation of a numeric value (parseInt, hashPassword)
  • An application-specific error code
  • A serialized data object

Just like how you can't verify an Obj is actually an Int at compile time, neither you can't tell if a String is an XML document.

Let's consider a generic Queue of SQL queries:

var queue = Queue<String>();
for a while 
{
  var query = getQuery();
  queue.push(query);
}
return queue;

Nowhere in the types of anything is it specified that getQuery() must return a query or that queue.push() be passed a query.

This is not different from a Fantom-looking variation:

queue := Queue()
for a while
{
  query := getQuery
  queue.push(query)
}

return queue

The only difference is that the "lame" type is Obj instead of Str. Both types under-specify what it is the collection contains.

It's not hard to see that there are many real-world use cases where generics don't gain us much of anything. Surely, there are other cases where they do, as well. But it is important to see that generics are not the End-All of type systems. There are tradeoffs involved.

And the Ruby programmers just laugh, because they never saw it as a problem. In a dynamic language, ALL objects are Objs. As long as they are meticulous in their documentation and unit tests, there are, on average, no increased rates of failure. (And Fantom has absolutely astounding support for annotated documentation and unit tests).

DanielFath Thu 20 Jan 2011

@tactics: I don't hate Obj as such. I just hate typecasting from Obj-> SomeType without the knowledge that it will always be SomeType. In static typing not knowing what your type is, is just god-awful. You need to make sure some kind of exception will happen once incorrect type is added.

OTOH I imagine those doing unit tests in dynamic languages need more tests to cover those cases compilers takes care for me.

tcolar Fri 21 Jan 2011

After all generics (at least when running in the JVM - erasure) is just a way to give type information to the compiler, so it can do type checking. (and IDE warn you / do completion)

Considering Fantom auto casting and Inference ... I think Java style generics would be pretty hard to get working right ....

I wonder if some optional facet(s) would not be enough for those who do want/need that extra safety net.... (I guess it gets sorta similar to Stephen "constraint idea" but less powerful)

@typeInfo {K=Int, V=Str}
Map m := [,]
//compiler would complain
m.put(5,5)

Yeah it's not nearly as useful as full generics support .... but in the end it still gives you most of the type info you wanted, so the compiler/IDE can use it, but it doesn't pollute the language.

vkuzkokov Fri 21 Jan 2011

@jodastephen I think Ada language has something close to constraints (like range type or String with limitation of size). Or almost every database engine.

On the sidenote to general discussion: I've never seen unit tests as a way to make you program correct (at least to the point of "nearly bug-free"). Mostly, because I've never seen a project which experience would show otherwise.

helium Fri 21 Jan 2011

@tcolar: Regarding not to allow nesting: Shouldn't we than prohibit nesting of function calls as well?

x := foo(bar(123, foo(456)))

would have to be written as

tmp1 := foo(456)
tmp2 := bar(123, tmp1)
x := foo(tmp2)

Programmers are able to decide on their own whether they want to create a temporary variable to make such statements clearer by giving names to intermediate results. I suppose they are able to do the same at the type level (if the language has something like your Type construct).

helium Fri 21 Jan 2011

@tactics:

class XmlStr {
   Str string { private set }
   new make(Str xmlString)
   {
      string = validate(xmlString)
   }
}

Now make all your XML-API only accepts XmlStr instead of Str and you basically got what you want.

tcolar Fri 21 Jan 2011

@hellium .... not sure a type definition and a call needs to be treated the same.

If Java had such a simple "type/alias" definition (even optional) as in my example I would definitely use it rather than typing <Map<Int, List<Int>>> 20 times.

helium Fri 21 Jan 2011

Of course applying a type constructor does not need to be teated the same as applying a function. But why should they follow different rules? Why are people sometimes to dumb to structure their code sanely (in the case of type level stuff) and sometimes aren't (in the case of value level stuff).

If nested function calls get unreadable you'll give names to the intermediate results to make the code clear, right. So just use the same logic when you apply type constructors.

tactics Fri 21 Jan 2011

@DanielFath

Yes, that is exactly why people hate it. Downcasting is inherently unsafe. It's that "not knowing what your type is at compile time" dilemma people don't like.

@helium

Even with wrapper code, you still don't validate the string's format until runtime. "Runtime validation" is just an another way of saying "downcast".

In regards to the nesting issue, it's a trade-off. Most typing information doesn't add anything to what the code actually does after type checking. It is prone to becoming line noise, since very often, the type is obvious from the context anyway.

rfeldman Fri 21 Jan 2011

To be fair, since method bodies are dynamically typed in Fantom, such line noise there is optional.

If you find a given declaration syntax overly convoluted, you can easily omit it when writing your actual method logic, instead using it only for contracts.

ahhatem Fri 21 Jan 2011

My main thoughts:

1- static vs dynamic typing:

static typing: type safety, more clear contracts, better performance....

dynamic typing: too complicated, handle in runtime

I think we need both... static annoying and detailed typing when writing a lib or something that needs type safety and performance.... dynamic inside my app, I probably know what I am writing.

I don't think a lot of people use generics a lot inside their code, generics are great in libs and shared code where it will be used a lot by many people and thus type safety and a lot of compile time info is useful and handy.

2- the syntax is annoying: we could change it .... that is the beauty of making a new lang :)

3- its exact behavior:

I don't think we need a lot of magic, c#2 generics will be great... even a simple version of c++ templates, with compile time generation and substitution of the types and that is it (without the c++ templates magic)... would be nice and useful.... though actually the syntax of <x extends y> is useful in giving info about the type passed

DanielFath Fri 21 Jan 2011

A question for brain will users be able to define their own List and Map implementations or add their own generic collections using Fantom's theoretical generics? If not is there a plan for some kind of a DSL that would enable us to do so?

katox Fri 21 Jan 2011

I'm not dissatisfied with the limited type flexibility support provided by This.

  • It is true current limitations skew the system towards using default Map and List types but so are Map and List literals. This won't change even with full generics.
  • Type checking is very useful for documentation purposes. It is probably the best feature of any type system. Fantom already provides this.
  • Sometimes it is hard work to convince type checker to accept a completely valid program just because it is not written in a certain way. Sometimes I don't want to pay this (huge) price. I might be - when writing a library, for instance. But if I am prototyping?
  • If types are weak, as in Java, using them sadly guarantees almost nothing. I don't see any major difference in C, Java, Ruby or even Awk programs blowing into my face due to an unexpected object inconsistency. Note that I use full generics in Java because I don't want downcast explicitly everywhere. Fantom does only some checking (and some runtime checks) but manages to avoid the verbosity.
  • If types are strong, programer's thinking wraps around satisfying the typechecker. Think of your early Haskell or ML attempts. Strong type system has more benefits than a weak one but it is usually much more complex to both learn and implement. And it is very unlikely that someone will do much better than ML or Haskell. If you try to replace the weak system from Java you will end up with Scala (which is not really that bad but still not to my liking). In that regard, I also doubt anyone will produce something significantly better anytime soon.

There is an old but interesting paper on non-mandatory typing. You probably know that but I'm linking it anyway ;)

TL;DR: -1 Useful, but not enough bang for the buck.

ahhatem Sat 22 Jan 2011

Well, if you are prototyping, don't use it.... A lot of people will be writing large apps and libs and will benefit from the generics and type safety.

the discussion is about supporting generics, not forcing generics and type safety... it is your choice

jodastephen Sat 22 Jan 2011

The main concern here is the level of additional complexity. No one as yet created a set of language features that allows the generics/constraints to be added, yet keeps usage simple. It is language usability that is the great frontier in language design, not the strength of the type system or power that Scala promotes.

One point mentioned was the aliasing question. I would add the ability to have simple type defs of "wrapped strings" or "wrapped ints". Artifical syntax examples:

class AirportCode :::: Str<[A-Z]{3}>

class DayOfMonth :::: Int<1...31>

class ListOfInt :::: Int[]

This approach allows quick definitions of types. But the problem you then face is the explosion of types - every type means writing a conversion method, and lots of manual calls to do the conversions (an AirportCode has to be converted to a Str).

So a key element to allowing these extra types (which are useful to document the system), is providing a mechanism to get back out of the types. Thats what the conversion operator does.

Void process(AirportCode code) { ... }  // method takes an airport code

str := "LGW"  // regular string

process(~str)  // ~ conversion between the types, checked at compile or run time as appropriate

Therefore, these features work together as a set - defining (aliasing) types, constraints (generics) and conversion (~) as the glue. The additional type info is incredibly useful (yet still optional), but the conversion operator is essential to make it usable.

But its quite a way from Fantom today.

helium Sat 22 Jan 2011

@tactics

Even with wrapper code, you still don't validate the string's format until runtime. "Runtime validation" is just an another way of saying "downcast".

You use the type system to prove that the XML API only ever gets passed valid XML. You can do the same for SQL to prove that only sanitized queries get executed which makes SQL injection impossible. ...

tactics Mon 24 Jan 2011

@helium

Oops, I missed that you use validate in the constructor.

brian Tue 25 Jan 2011

Here are a couple thoughts:

If you are coming from Ruby/Python world then you don't really miss generics - Fantom is like a more typed, faster language dynamic language. If you are coming from the Java/C# world then you probably miss them. My general observations that most new-comers to Fantom are from latter group and are turned off by lack of generics.

My personal experience is that generics aren't a quality/type safety issue, but rather a convenience issue. I could probably dedicate a whole blog post to this, but the summary is that I find that public inter-module APIs rarely need generics to publish clean interfaces. Yes generic collections APIs scream for generics, but I have purposely tried to ensure that public inter-module APIs stick to List/Map. I believe more advanced collections belong as module internals rather than public APIs.

So where I would tend to use generics is for my own internal code. And I would find generics would be a convenient mechanism to avoid casting or as operators.

In the end there is a balance between type safety/convenience and language complexity. Adding any form of parameterized types can easily burn your entire complexity budget. My strategy so far has to be target the type system for the "biggies":

  • nullable types
  • mutability
  • core collection classes

I also personally believe targeted solutions work better. For example I believe Fantom's treatment of nullable types as a built-in language feature is much more pleasant to work with then using something like Option<T> everywhere.

But just to re-iterate: I am not opposed to generics if we can find a simple solution that doesn't add a huge amount of complexity. One thing that really bothers me is the slippery slope of variance. But new ideas like Stephen has been proposing is what it takes to get the brainstorming machine rolling. Also have watching Go to see what they might come up.

DanielFath Tue 25 Jan 2011

What are do you mean by:

I believe more advanced collections belong as module internals rather than public APIs.

Does this mean we implement our own solution as a language patch or mess around pod with native keyword (or neither)?

helium Wed 26 Jan 2011

constraints (generics)

I don't normally view generics as constraints. They are type factories. For example you might have a type factory Heap that you pass a type as parameter - e.g. Int - and you get a new type that represents a heap of integers. For the same argument this factory always returns the same concrete type, so Heap<Int> refers always to the same type. You can imagine it like the factory having a cache.

In some languages you have some influence on what the factory returns for which parameter e.g. in C++ using template specialization or type families in Haskell. You might implement some general set class but you have an idea how to make it a lot faster in the case of integers so you could use a special implementation for Set<Int> and the default implementation for all other sets. .Net generates one class per value type under the covers but you don't notices this at all.

Just to get a little crazy:

tcolar already suggested a type keyword to define type level constants. So like you can say

const Int x = 42

to define a value level constant you then can say

type X = Int

This idea of type level constants could be extended to type level functions:

// a generic class
class Pair<T1, T2> {
   T1 first
   T2 second
}

// a type level function
type SameTypePair<T> {
   return Pair<T, T>
}

// using the type level function to give a type to the parameter
Void foo(SameTypePair<Int> x) {  // same as Void foo(Pair<Int, Int> x)
   ...
}

But Fantom probably isn't the right language for things like this.

Login or Signup to reply.