Generic types

[maiermic]

How do I type a function with a type variable in rtype?

Example: map function

In functional languages you write something like this:

map :: Functor f => (a -> b) -> f a -> f b
map f a = ...

In TypeScript you use generics (ramda.map):

map<T, U>(fn: (x: T) => U, list: T[]): U[];
map<T, U>(fn: (x: T) => U, obj: any): any; // used in functors
map<T, U>(fn: (x: T) => U): (list: T[]) => U[];

[Mouvedia]

So you want the signature of Array.prototype.map?

[maiermic]

Yes, whereby the map function that I described takes the array as second parameter.

[ericelliott]

IMO, if you put too much inline, it becomes hard to read. I suggest splitting it:

Transform(a: Any) => b: Any
Map(fn: Transform, arr: []) => newArray: []

[maiermic]

Since Transform takes and returns Any I loose type information, right? Thus, this error is not recognized:

map( (text: String) => text.length, [1, 2, 3] )

[ericelliott]

Yep, but my map() signature example is intentionally generic to allow for any kind of transform. Bring your own Transform is implied. Do you have an alternative suggestion that works for every possible Transform without losing type information?

[maiermic]

intentionally generic means intentionally error-prone. It's like a leak in the type system. Everything that depends on the undefined type variable is untyped and can not be analyzed.

I already mentioned two examples of other type systems. TypeScript uses generics, but I'm not sure if it is the way we should go. I really like the way of functional type systems (simple, clear and expressive), but I'm not sure how compatible it is with the existing rtype system. I mentioned those examples, since TypeScript and Haskell are mentioned in About Rtype:

Standing on the shoulders of giants: ES6, TypeScript, Haskell, Flow, & React

[BerkeleyTrue]

@maiermic I think you missunderstood @ericelliott's comment.

MY map() signature example is intentionally generic to allow for any kind of transform. Bring YOUR OWN Transform is implied.

Meaning he supplied a generic function, You can supply a typed function.

Transform(a: String) => b: String
Map(fn: Transform, arr: [String]) => newArray: [String]

[ericelliott]

I think you missunderstood @ericelliott's comment.

👍

Bring your own Transform is implied.

[ericelliott]

@maiermic It's also worth noting that Haskell is polymorphic and generic programming is common in Haskell. https://wiki.haskell.org/Generics

[ericelliott]

More to your original point: currently, we don't support type variables like TypeScript's generics in function signatures, and the TypeScript syntax feels like an assault on my senses.

I'm open to the idea of adding this feature, if we can come up with syntax that doesn't make me want to claw out my eyes. I'll repeat my invitation for you to help:

Do you have an alternative suggestion that works for every possible Transform without losing type information?

[ericelliott]

It's also worth noting that just because a type isn't in a signature does not mean that the variable is untyped, and the Haskell docs actually show a map example to demonstrate:

map :: (a -> b) -> [a] -> [b]
Char.ord :: (Char -> Int)

For the expression map ord the type checker finds out that the type variable a must be bound to the type Char and b must be bound to Int and thus it concludes:

map ord :: [Char] -> [Int]

IMO, type inference should be favored as much as possible. Trying annotate every little thing can add a lot of noise.

[maiermic]

type inference 👍

Meaning he supplied a generic function, You can supply a typed function.

Maybe I still mispreceive it. Let's try to clear up misunderstandings:
Someone wrote a library with a intentionally generic function map, i.e. he types map like that:

Transform(a: Any) => b: Any
Map(fn: Transform, arr: [Any]) => newArray: [Any]

Now someone else likes to use this function like that:

var a = map( (text: String) => text.length, ['example', 'input'] );
var b = map( (x: Number) => x > 6, a );
var c = map( (text: String) => text.split('p'), b );

In case a map is used with types

Transform(a: String) => b: Number
Map(fn: Transform, arr: [String]) => newArray: [Number]

In case b map is used with types

Transform(a: Number) => b: Boolean
Map(fn: Transform, arr: [Number]) => newArray: [Boolean]

In case c map is used with types

Transform(a: String) => b: String
Map(fn: Transform, arr: [Boolean]) => newArray: [Number]

Since Any is compatible with any type (including Boolean, Number and String) those type definitions are all compatible with the original type

Transform(a: Any) => b: Any
Map(fn: Transform, arr: [Any]) => newArray: [Any]

Thus, the type conflict in case c is not recognized. Who should supply a typed function? Author or user? Where and how should it be supplied? It would be an imposition and error-prone for the user to add a concrete type signature before each usage of map. Therefore, we need type variables the author can use.

Do you have an alternative suggestion that works for every possible Transform without losing type information?

TypeScript uses generics to define type variables

map<T, U>(fn: (x: T) => U, list: T[]): U[];

You can pass type variables to other gerneric type definitions:

Transform<T, U>(x: T) => U
map<T, U>(fn: Transform<T, U>, list: T[]): U[];

You don't need to specify generic types on each call just in the definition.

Generics are widespread and established, but they are considered to be quite complex.

TypeScript syntax feels like an assault on my senses

What do you not like? Maybe we can find a better solution, if you describe your feelings in more detail.

By the way, we already use generics under the hood to describe arrays, don't we? String[] is the same as Array<String>.

[ericelliott]

By the way, we already use generics under the hood to describe arrays, don't we? String[] is the same as Array<String>.

Yes, and I even considered TypeScript's generic syntax for that purpose, but I think there's something about the angle brackets that drives me crazy. Reminds me of C++ templates or something (which I have bad memories of).

Are there any other generic syntaxes we could use as inspiration?

[BerkeleyTrue]

👎 For angle brackets

[maiermic]

Scala uses square brackets:

def map[T,U](fn: T => U, list: List[T]): List[U] = ...

We could write Array[T] instead of T[] in rtype. We might use [T] as short version of Array[T]. One benefit of writing the generic type in brackets is better readablity of type expressions:
(Number | String)[] vs. [Number | String] or Array[Number | String]

[Mouvedia]

👎 for the long version
We shouldn't use the constructor for that: it's too confusing.

[maiermic]

We shouldn't use the constructor for that: it's too confusing.

Array is not the constructor. It is the type interface Array. The constructor Array is a function with type

function Array[T](...elements: Array[T]): Array[T] { ... }

But I would say that is even more confusing 😉

We could use another name ArrayInstance or IArray for the type interface of an array to avoid misunderstandings (see example of the documentation):

function Array[T](...elements: ArrayInstance[T]): ArrayInstance[T] { ... }

or

function Array[T](...elements: IArray[T]): IArray[T] { ... }

Whereby the short syntax is more readable, but less explicit (special case)

function Array[T](...elements: [T]): [T] { ... }

We characterize the naming conventions. That's why should think carefully about naming predefined types. ArrayInterface may be considered, too.

Some more examples of generic types (not considering one of these naming conventions):

Stream[T]
Map[K, V]
Object[K, V] // Object that is used like a map (might be controversal, but is common in JS world)
Pair[A, B]

[ericelliott]

I like the square bracket syntax MUCH BETTER. I'm OK with this:

Stream[T]
Map[K, V]
Object[K, V] // Object that is used like a map (might be controversal, but is common in JS world)
Pair[A, B]

[Mouvedia]

I don't think we should reuse square brackets since in JS it's for arrays.
We need a new syntax that doesn't use (), {} or [] but still conveys inclusion.
I don't like <> either but it has the advantage of not being confusing.

Promise::String::
Would that work?

[tomek-he-him]

Wouldn’t square brackets mentally collide with our syntax for typed arrays? Object[] vs Object[String, Number] vs Object[String, Number][].

Elm just uses spaces for that. Similarly to Haskell, it has lowercase for generics and uppercase for concrete types:

Stream t
Map k v
Object k v
Pair a b

Transform t u: (x: t) => u
Map t u: (fn: Transform t u, list: t[]) => u[]

[ericelliott]

This is my favorite suggestion so far. 👍 @tomekwi

Advantages:

• No ambiguity with arrays
• No jarring angle brackets
• Clean, readable syntax
• Follows existing conventions (Elm, Haskell)

[tomek-he-him]

Woohoo 🎉! Let’s wait what the others say.

[stoeffel]

@tomekwi love your suggestion. I'm a fan of the Hindley-Milner type system. (https://en.m.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_system)

[tomek-he-him]

Whooah, looks hardcore! 😉

[Mouvedia]

So simple yet so clear.

👍 on space

[koresar]

The following looks very bright and logical. Although, rather unreadable. Let me explain.

Stream t
Map k v
Object k v
Pair a b
Transform t u: (x: t) => u
Map t u: (fn: Transform t u, list: t[]) => u[]

Thousands of C++/Java/C# developers are currently being converted to JS developers, you all know that. Students in (high)schools study the C++/Java/C#. I would recommend to make sure these people can read rtype easily without browsing the documentation (JSDoc is quite readable, btw, thus popular).

Haskell is known but an exotic language yet. For C++/Java/C# developers it is counter intuitive that the space symbol have a special syntactic meaning. Frankly speaking, I still do not understand what's that: Transform t u: (x: t) => u.

I would recommend to level the readability up to the highest level possible, gentlemen.

Haskell is still not readable unfortunately. TypeScript syntax is readable to most developers. They would easily understand that:

Transform(a: T) => U
Map<T, U>(fn: Transform<T, U>, list: T[]) => U[]

But not many would understand this (hopefully I understood it correctly):

Transform t u: (x: t) => u
Map t u: (fn: Transform t u, list: t[]) => u[]

C++/Java/C#/TypeScript languages have so called "generics". I'd recommend utilizing it's syntax - i.e. chevrons < and >.

[koresar]

Let me list "arguments" against the angle brackets you have expressed:

... something about the angle brackets that drives me crazy. Reminds me of C++ templates or something (which I have bad memories of).

---

👎 For angle brackets

---

I don't like <> either

---

No jarring angle brackets

Do you feel like those are far from being an argument? :)

[Mouvedia]

Converted by force?
I think we should concentrate on our community needs.
The newcomers already added class to ES, that's plenty enough in my opinion.

[koresar]

Those "converted" people are also our community.

[maiermic]

In case of a single-parameter-function as concrete type argument readability is decreased with angle brackets notation due to the fact that a closing angle bracket is used as arrow head:

MyInterface<String => String>   // angle bracket syntax

MyInterface<(String => String)> // angle bracket syntax, IMO parentheses don't increase readability in this case

MyInterface (String => String)  // whitespace syntax (type argument has to be enclosed in parentheses, otherwise it would be equal to `(MyInterface String) => String`

MyInterface(String => String)   // parentheses/function syntax; Note: Could also be written like whitespace syntax in this case: `MyInterface (String => String)`

This case is a common one. It could be bypassed with a function alias

interface StringStringFunction:
    String => String

but you don't always like to do that.

To be fair, there may be awkward examples in other syntaxes, too. Please comment if anything comes into your mind.

[tomek-he-him]

@maiermic

Since Any accepts values of any type, it should be used carefully and should be avoided in most cases. You should only use Any if you do not need or know type information. Otherwise a more specific type is prefered. console.log is a prominent example of a function that does not need specific typed paramerters:

(message?: Any, ...optionalParams: Any[]) => void

That makes sense. I meant that could be expressed by generics like this:

(message?: a, ...optionalParams: b[]) => Void

– but on second thoughts, it only makes the thing more obscure. Generics only really make sense in interface definitions. Type annotations should only allow concrete types like those in your example.

[maiermic]

(message?: Any, ...optionalParams: Any[]) => void

and

(message?: a, ...optionalParams: b[]) => Void

are not the same. The function (console.log) takes values of arbitrary types as optionalParams that have no common super type b except Any.

What should be the type of b in this example?

console.log("arbitrary values", true, 42, "string", [1, 2, 3], { property: "value" });

I did not pass a value of every existing type, but it would be possible. Hence, b is Any.

[tomek-he-him]

Definitely 👍

[ericelliott]

@maiermic

Ah, I think I see your point:

MyInterface (String => String)

May be interpreted as:

MyInterface(String) => String

Of course, if MyInterface was already declared, we could detect it and figure out that it's intended as a function call syntax to form a concrete type:

MyInterface(String => String)

Looks like there are ambiguity and readability problems with all of the syntax proposals so far.

Which one has the best readability + disambiguation solution?

[maiermic]

MyInterface (String => String)

May be interpreted as:

MyInterface(String) => String

No, it isn't, but

MyInterface String => String

may is interpreted as

(MyInterface String) => String

because of the higher binding of an interface declaration (I should have mentioned that earlier 😞 ), which results in

MyInterface(String) => String

There is no such ambiguity.

MyInterface (String => String)

is a different type. It is a concrete type. It is not an interface declaration, because it would be missing an interface body.

[ericelliott]

Ah, yes, thanks for the reminder.

In that case, I think I'm happy with the function call syntax. Are you?

[koresar]

May be interpreted as:

Even Eric is confused.

Think of that. Every one here got confused on how the new "function call" syntax actually works. Add several other confusions we had above. And imagine thousands of other people being confused.

Surprisingly, none in this thread got confused with the "angel brackets" syntax.

[ericelliott]

@koresar Maybe. Keep in mind that none of us are familiar with the existing syntax, and we are familiar with other type system syntax, so it's easy for our brains to jump to more familiar constructs to try to parse proposal examples.

I think being confused about these examples says something, but I think that a little familiarity will go a long way toward reducing confusion in the future, whereas being familiar with angle bracket syntax with inline signature annotations more than a decade has never made them much easier for me to parse when they're intermingled, as in C++ templates... So I'd really like to avoid that.

To reiterate, what really confuses my brain about angle bracket syntax is when it's mixed with function signatures, as in the type constructor declarations. For the purposes of the signature demonstration, I'll return to the map function example rather than the map data type example:

map<t, u>(fn: (x: t) => u, list: t[]) => u[];

IMO, this is even worse than the C++ & Java versions because of the arrow functions. Note how the closing angle bracket for the type parameter declaration looks visually very similar to the arrows in the arrow functions. My brain tries to match them up.

My brain also struggles with the groupings of type parameters and function parameters, mostly lost in the syntax noise.

I strongly prefer this version for declaration. Because the syntax noise from the angle brackets is gone, it lets the type parameters take a supporting role, rather than making them the noisiest part of the signature:

map t u (fn: (x: t) => u, list: t[]) => u[]

That allows my brain to much more easily focus on the important parts of the signature: the positions of the types within the signature body itself.

This is more important than it might seem at first, I think. Imagine you're driving a car, and there's some really important information in the dashboard about your engine overheating, warning you that the car's RPMs are 3x higher than the safe level. The trouble is, it's not flashing. It's not red. There's no motion drawing your eye to it.

You're driving a fancy new car with a GIGANTIC display off to the right. Normally that big display is showing you something innocuous like the name of the current track playing on your car stereo but right now it's flashing a bright red cryptic message at you -- you may be distracted and not notice the critical information tucked away in the dashboard dials.

In my brain, angle brackets mixed into function signatures has that effect. It draws my eyes and my brain's attention away from the signature itself, and to the angle brackets -- not even the contents of the angle brackets, but the brackets themselves. The thing is, in the context of the function signature, I don't believe that the brackets need to be there in the first place. In fact, I really like this form we discussed earlier:

map t u (fn: (x: t) => u, list: t[]) => u[]

So now that we've established that the space separated style might not work as well for invocation, I still want to have my cake and eat it, too.

Does it make sense to mix and match spaces for declarations and angle brackets for invocation?

map t u (fn: t => u, list: t[]) => u[]

interface mapStringsToStrings:
  map<String, String> 

As @maiermic pointed out, part of the visual confusion still exists because you can pass an arrow function signature as a concrete type:

interface StringStringThing:
  MyInterface<String => String>

Which visually looks a bit like this:

interface StringStringThing:
  MyInterface<String => // wtf is the rest of that nonsense?

And then your brain registers that there's an = sign in there and you can get back on track...

Which is why I like this version:

interface StringStringThing:
  MyInterface(String => String)

I was only worried for a moment because I thought it may be confused with this signature declaration:

MyInterface(String) => String

But in order to interpret MyInterface(String => String) as a constructor call, it's missing a bunch of stuff, like the interface keyword (only signatures are allowed to leave it off), the new interface name, and even the : could provide a clue if we disallow them in signatures. (see the previous example). In other words:

// Error: Unexpected token, `:`
MyInterface:(String => String)
           ^

Conclusion & Proposal

1. Parameter groupings are NOT required for type variable declarations (no need to mix <> & () in function signatures). Hence, we should not use or allow them.
2. Parenthesis do NOT produce ambiguity in type constructor invocations. Hence, we should use () for invocations. They should be required, even if there is only one parameter, and no need for grouping.
3. I don't see the need for <>, and only @koresar seems to be championing them.

Questions:

• Would anybody other than @koresar like to weigh in in favor of <> with any justifications we haven't already considered?
• Am I missing any other ambiguities or issues with this proposal?

[ericelliott]

P.S. "Even Eric is confused."

This happens a lot, and should not be taken as evidence of anything particularly interesting. ;)

[koresar]

Looks like our brains work in a different ways.

To make the best decision we need to survey other people in order to understand how the majority of the developers' brains work.

Could you create a poll with a single question "What's more readable to you?" and three examples of the proposed syntax (space delimited, function-like, and angle brackets)?

[maiermic]

I already started working on a survey of generic syntaxes. I'd like to give an overview of each syntax with description and examples. Further, I try to point out advantages and disadvantages as objective as possible.

Sadly, I'm really busy in the next weeks. Thus, it may take some time. Please be patient.

The examples are intended to cover all basic use cases of generics: functions, objects, methods (with additional generic types that depend on the parameters and are not defined on the object interface itself), considering type restrictions/bounds and declaration-site variance annotations. Am I missing something? They should be preferably familiar and not unnecessary complex. I'm open for suggestions. I miss good examples for type restrictions/bounds and declaration-site variance annotations yet. Any ideas?

[Mouvedia]

If you do that just select an use case that is common for the examples.

[maiermic]

Status RFC:
In the future, the rtype library will parse rtype strings and return a predicate function for type checking.

Given a generic interface (here written in function/parentheses syntax):

interface Collection(T) {
  // ...
}

How can we check the generic type at runtime?

import rtype from 'rtype';
// I don't know how type checking will look like. Thus, I define it like this:
/**
 *  Returns `true` if `a` is of type `t`, else `false`.
 *  (t: Rtype, a: Any) => Boolean
 */
const isOfType = rtype.isOfType;

// Collection(Any) => Void
function (c) {
  if (isOfType(Collection(Number), c)) {
    // ...
  } else {
    // ...
  }
}

In other words: How can we implement reified generics?

Note: Syntax does not really matter in this case.

[ericelliott]

@maiermic, my first-pass naive plan is essentially this:

Generics are parameterized functions which get compiled to concrete types based on the type parameters passed to them. Here's a naive first pass at the runtime compiler output for each type:

interface TypeChecker {
  interfaceName: String
  interfaceString: InterfaceString,  // original, unmodified interface string here
  isType?: Predicate, // For non-function types, a synchronous predicate returns true if input matches interface shape, false otherwise
  wrapper: WrapperFunction   // for functions, the wrapper optionally monitors arguments, return values, throws, and warns if they deviate from the described interface
};

For generics, the type parameter information could be included in the TypeChecker interface, but I thought it would be enough to fix them inside isType and/or wrapper.

If you see problems with that approach, I'd love to hear them.

See also #62

[maiermic]

How does the corresponding JavaScript function isType of String[] and Number[] look like?

[ericelliott]

@maiermic

A runtime check would iterate through the Array and check that every element satisfies the .isType() check for String, or Number, respectively. Of course, that would be slow, which is why it's a good idea to turn off runtime checking in production.

Is it possible to combine compile time static analysis & runtime analysis to compile optimized runtime checking strategies?

[maiermic]

How about empty arrays?

Pseudocode:

var a: String[] = [];

if (a is Number[]) {
  a.push(666); // `Number` is inserted into `String[]`
}

[ericelliott]

If there are no elements, then "every element" satisfies the .isType() check -- meaning there are no failing elements in the array... correct? =)

P.S. I don't think I understood what the pseudocode was meant to demonstrate, which means I may have completely misunderstood your last comment.

[maiermic]

Sorry, I am short of time, but I try to explain the issue more clearly:
If array [] satisfies the runtime type check of Number[] and String[], we might push a Number into the array, because we think it is of type Number[], but a variable somewhere else, that stores that array, has been specified as String[]. Thus, we can unnoticeably store impermissibly a Number in String[].

[ericelliott]

Ah, I see what you mean. Yes, [] will satisfy the runtime check of Number[] and String[], but if there is an error, it would be caught the first time you type check the array with any value in it. Aside from that, though, a static analysis may be able to catch the error at compile time before it ever gets to runtime checks. =)

[maiermic]

Static analysis is not able to catch the error 😟 Runtime checks are only used if static analysis does not provide (enough) detailed type information (for example type is Any). Otherwise, a runtime check wouldn't be necessary.

[ericelliott]

Further discussion can be found in the RE: generic types syntax can be found in #80.