Repository navigation
recursive type definitions #3496
Description
Activity
That isn't just recursion, it is infinite recursion. How do you suggest the compiler could resolve that, since it needs to understand
IJSONSerializableto be able to type guardIJSONSerializable?I haven't looked into the typescript compiler code. Lazily evaluate the type definition? Translate something like Exhibit B back into Exhibit A? If you point me to the relevant area in the code base, I can attempt to address it.
Edited previous comments for clarity.
opensrcken Compiler code is not necessary here to define a general algorithm that will solve the problem.
export type IJSONSerializable = {[paramKey: string]: IJSONSerializable} | number | string | Array<IJSONSerializable>; var aThing: IJSONSerializable = { foo: 'a' };
Lazily evaluating the original type definition isn't the issue. The problem comes as soon as you try to use it, like here, where we need to check whether something is assignable to that type. So the compiler asks is
{ foo: string }assignable toIJSONSerializable? Well to answer that question it needs to know whether{ foo: string }is assignable to{ [paramKey:string]: IJSONSerializable }. So then it has to check whether the type offoois assignable toIJSONSerializableand then we're back to trying to answer the first check again and infinitely recursing. One way we break out of this situation today is by falling back toanyafter a certain number of loops, but that's not what you want here since that would make this type definition essentially useless (everything would be assignable to it).Dan Quirk (@danquirk), I think the compiler implementation is relevant.
Let's simplify this a bit -- we are trying to define the type of a data structure that is legitimately recursive, theoretically infinitely so. For simplicity's sake, let's think about a vanilla Binary Tree, instead of JSON.
It would seem to me that the compiler should understand the possibility of an infinitely recursive type, and only match a data structure that claims to match that type if it also detects that the data structure itself is theoretically recursive in the same way. The missing piece in your example is the ability to detect infinite recursion in a type definition, without actually having to recurse infinitely, and treat that as a type in and of itself, distinct from
any.Remember, the very first example in the OP is infinitely recursive, it's just not directly self-referential:
export type IJSONSerializable = IJSONSerializableObject | number | string | Array<IJSONSerializableObject | number | string>; interface IJSONSerializableObject { [paramKey: string]: IJSONSerializable }
So are you saying that the compiler is actually treating this as
anyunder the hood? If not, it seems the compiler is already able to understand this notion to some degree.opensrcken The types you've defined in exhibit A and exhibit B are not even the same. In exhibit B, your type would allow
Array<Array<number>>, whereas the type in exhibit A would not. Am I correct?The reason this is an error is the
Array<IJSONSerializable>reference. In order to know what that type represents, we cannot create a type forArray<IJSONSerializable>because we don't even know if it's an object type. Furthermore, if it is, we don't know if it's a type we created already, or a new type. Our only way of looking up this information is by knowing exactly whatIJSONSerializableis, and we don't.In order to support this, we'd need to change the architecture of type aliases so that all operations in the type checker know how to process the types created by them. It would involve actually creating a container every time we encounter a type alias. This would possibly create memory overhead, and would add another case to handle in every type operation in the checker. It is nontrivial, but not fundamentally undoable.
Forgot to clarify, it is not a result of failure to detect relations between types that are infinitely recursive.
Also, it's simple recursion in this case (classic mu type), not infinite/generative recursion.
Yes, you are correct about the difference between exhibit A and B. That is an oversight on my part. I have edited exhibit A to correctly reflect the potential recursive nature of JSON arrays.
I think the important thing here is that JSON is not some sort of edge case. Recursive types are fairly commonplace in programming, and it seems worth supporting.
Another example: Promises/A+ promises.
type ThenableLike<T> = T | ThenableLike<Thenable<T>>; interface Thenable<T> { then(callback: (value: T) => ThenableLike<T>): Thenable<T>; } class Promise<T> implements Thenable<T> { static all<T>(thenables: ThenableLike<T>[]): Promise<T>; static race<T>(thenables: ThenableLike<T>[]): Promise<T>; static resolve<T>(thenable: ThenableLike<T>): Promise<T>; static reject<T>(thenable: ThenableLike<T> | Error): Promise<T>; then<U>( callback: (value: T) => ThenableLike<U>, error?: (err: Error) => ThenableLike<U> ): Promise<U>; catch<U>(error: (err: Error) => ThenableLike<U>): Promise<U>; }
Or, the classic array flatten function:
type Nested<T> = T[] | Nested<T[]>; function flatten<T>(list: Nested<T>): T[] { return (<T> []).concat(...list.map<T | T[]>((i: T | Nested<T>) => Array.isArray(i) ? flatten(i) : i)); }
I think the important thing here is that JSON is not some sort of edge case. Recursive types are fairly commonplace in programming, and it seems worth supporting.
👍 Definitely not an edge case. That
flattenfunction is in nearly every utility library out there.Reacted by Strider, Jaden Geller, Yuba, Leonard Breitkopf, Miloslav Nenadál, Mathias Lykkegaard Lorenzen and Aneil MallavarapuActually opensrcken I don't think ThenableLike or Nested make sense the way they are defined. Those are infinitely expanding type aliases with no structure other than a union type, and those would degenerate. This problem does not occur with your ideal definition of IJSONSerializable above. To see what I mean, let's take
Nested<number>as an example. Let's now try to show thatstringis not assignable toNested<number>. I'll go in steps:- Is
stringassignable tonumber[]? No. Let's tryNested<number[]> - Is
stringassignable tonumber[][]? No. Let's tryNested<number[][]> - Is
stringassignable tonumber[][][]? No. Let's tryNested<number[][][]> - Is
stringassignable tonumber[][][][]? No. Let's tryNested<number[][][][]> - ...
Eventually, the type system decides that it's never going to get an answer. So it has no basis to give an error, and as a result,
stringis assignable toNested<number>. In fact, everything is, and it's a useless type.Now I'm not saying that recursive types are bad. Just this kind of recursive type is bad. It is much better if Nested is written like this:
type Nested<T> = T[] | Nested<T>[];
Now the type has structure because all constituents are arrays.
The same thing goes for ThenableLike. You'd need to define it like this to make it not degenerate:
type ThenableLike<T> = T | Thenable<ThenableLike<T>>;
Although in this case, perhaps what you want is not recursive at all. Thenable itself already seems to encapsulate the recursion. Why is it not
type ThenableLike<T> = T | Thenable<T>;
- Is
- You mean me, IMPinball? ;)
- I came up with those from more of a pure functional mindset (Haskell/OCaml/etc.), which has a type system in which types sometimes can become data. My mistake on that part.
- The above definition for Thenable itself doesn't fully encapsulate the possibilities for things such as this, an arbitrary amount of nesting:
Thenable<Thenable<Thenable<...<Thenable<T>>...>>>
Although, I just realized that this could potentially also be used to properly, and completely type
Function.prototype.callandFunction.prototype.bind. It may take a little bit of ugly hacking to pull it off, but it may be possible. I wouldn't hold my breath for it, though.Yes, sorry IMPinball. I got confused when you addressed opensrcken.
I realize different type systems have different ways of understanding types and data, so they don't always translate perfectly. Specifically in TypeScript, there is a very clean separation of values and types. So an infinitely recursive type without structure just wouldn't work, even if we were to maximally support recursive types.
For the arbitrary recursion on Thenable, ideally you should be able to do that with type
ThenableLike<T> = T | Thenable<ThenableLike<T>>;if we supported it. The type system could handle it just fine, it's just that we have to adjust the compiler architecture.13 remaining items
@isiahmeadows The TypeScript translation of the Haskell json data type that you've posted works just fine:
type JSValue = { kind: 'JSNull' } | { kind: 'JSBool', value: boolean } | { kind: 'JSString', value: string } | { kind: 'JSRational', asFloat: boolean, value: number } | { kind: 'JSArray', value: JSValue[] } | { kind: 'JSObject', value: { [key: string]: JSValue } }
dataconstructors actually introduce indirection which saves Haskell. The direct Haskell translation of the OP's snippet would require using eithertypeornewtype, but that's not possible.@isiahmeadows That's called "equirecursive" and "isorecursive" approaches to infinite types. In first case we get "real" infinite types, and it's barely possible to do type inference there, even without any other type system extensions. In a big type system like TS there might not be even a way to typecheck it.
Most programming languages (including Haskell and O'Caml) prefer to use isorecursive approach. Operations on named types (constructing its instance or pattern-matching it) include operations of explicit type folding and unfolding, while types are represented in finite notation and don't equal each other even if they're isomorphic to each other.
Recursion on type aliases is essentially equirecursive feature, and it's most likely impossible to implement in TS at all. Someone could make a proof of this claim, but type system of TS is unsound anyway, so there's not much sense in making it.
Reacted by Claudia Meadows and Ryan Cavanaughbut type system of TS is unsound anyway
@polkovnikov-ph is this a personal opinion? Can yo explain a bit?Lasana Murray (@metasansana) #9825 - It's a theoretical thing.
Lasana Murray (@metasansana) There is even a gist for it: https://gist.github.com/t0yv0/4449351
The following code shouldn't compile, but it does
class A {} class B extends A { foo(x: string) : string { return x + "!"; }; } function f1(k: (a: A) => void) : void { k(new A()); } function f2(k: (a: B) => void) : void { f1(k); } f2(function (x: B) { console.log(x.foo("ABC")); });
This is one of the many bugs in type system of TS, and, unfortunately
100% soundness is not a design goal.
Reacted by Lasana Murraydid you try compiling your code with
--strictFunctionsflag? i asm not at the computer, but it should break it (as you expect)Aleksey-Bykov I tried it in TS playground. It doesn't have such a flag. In no way this should be a "feature" disabled by default, let alone the fact it shouldn't even exist. "False positives" are intolerable in type systems.
Reacted by Ariel Shaqed (Scolnicov)Reacted by Ryan Cavanaughthe problem you are talking about doesnt exist anymore, typescript takes it slow progressing from loose to strict giving us a chance to tighten our code (originally written in js) one step at a time at a comfortable pace, this is the reason for the flag
playground might be lagging behind the latest version in master, but it doesnt stop anyone from using it in production
what else is wrong?
honestly there are very few impurities left in TS that make your code unsound, and TS design team doesnt hesitate rolling out breaking changes for the sake of brighter future, i am personally very happy with that, wish you the same
Reacted by Marin MarinovReacted by Daniel RosenwasserAleksey-Bykov You meant the
--strictFunctionTypesflag right?- locked and limited conversation to collaborators
on Jun 19, 2018 Fixed in #33050.
I have a recursive type definition for JSON Serializable entities (Exhibit A, edited after discussion with Jason Freeman (@JsonFreeman) ):
I would like to be able to write the following, but get a circular reference error (Exhibit B):
How difficult would it be to address this limitation of the type system?