recursive type definitions

Jason Freeman (@JsonFreeman)

I have a recursive type definition for JSON Serializable entities (Exhibit A, edited after discussion with Jason Freeman (@JsonFreeman) ):

export type IJSONSerializable = IJSONSerializableObject | number | string | IMaybeRecursiveArray<IJSONSerializableObject | number | string>;

interface IMaybeRecursiveArray<T> {
   [i: number]: T | IMaybeRecursiveArray<T>;
}

interface IJSONSerializableObject {
    [paramKey: string]: IJSONSerializable
}

I would like to be able to write the following, but get a circular reference error (Exhibit B):

export type IJSONSerializable = {[paramKey: string]: IJSONSerializable} | number | string | Array<IJSONSerializable>;

How difficult would it be to address this limitation of the type system?

That isn't just recursion, it is infinite recursion. How do you suggest the compiler could resolve that, since it needs to understand IJSONSerializable to be able to type guard IJSONSerializable?

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

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 to IJSONSerializable? 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 of foo is assignable to IJSONSerializable and 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 to any after 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)

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 any under the hood? If not, it seems the compiler is already able to understand this notion to some degree.

opensrcken

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 for Array<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 what IJSONSerializable is, 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.

opensrcken

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));
}

opensrcken

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 flatten function is in nearly every utility library out there.

opensrcken

Actually 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 that string is not assignable to Nested<number>. I'll go in steps:

Is string assignable to number[]? No. Let's try Nested<number[]>
Is string assignable to number[][]? No. Let's try Nested<number[][]>
Is string assignable to number[][][]? No. Let's try Nested<number[][][]>
Is string assignable to number[][][][]? No. Let's try Nested<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, string is assignable to Nested<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>;

Jason Freeman (@JsonFreeman)

Jason Freeman (@JsonFreeman)

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.call and Function.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.

IMPinball

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.

@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 } }

data constructors actually introduce indirection which saves Haskell. The direct Haskell translation of the OP's snippet would require using either type or newtype, 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.

but type system of TS is unsound anyway
@polkovnikov-ph is this a personal opinion? Can yo explain a bit?

Lasana Murray (@metasansana)

Lasana Murray (@metasansana) #9825 - It's a theoretical thing.

Lasana Murray (@metasansana)

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.

did you try compiling your code with --strictFunctions flag? i asm not at the computer, but it should break it (as you expect)

Aleksey-Bykov

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.

the 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

Aleksey-Bykov

Aleksey-Bykov You meant the --strictFunctionTypes flag right?

Fixed in #33050.

Navigation Menu

Repository navigation

recursive type definitions #3496

13 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

recursive type definitions #3496

Description

Activity

kitsonk commented on Jun 13, 2015

opensrcken commented on Jun 14, 2015

opensrcken commented on Jun 15, 2015

danquirk commented on Jun 15, 2015

opensrcken commented on Jun 15, 2015

JsonFreeman commented on Jun 17, 2015

JsonFreeman commented on Jun 17, 2015

JsonFreeman commented on Jun 17, 2015

opensrcken commented on Jun 17, 2015

dead-claudia commented on Jul 14, 2015

JsonFreeman commented on Jul 14, 2015

dead-claudia commented on Jul 15, 2015

JsonFreeman commented on Jul 15, 2015

13 remaining items

gcnew commented on Feb 13, 2017

reverofevil commented on Nov 30, 2017

metasansana commented on Dec 5, 2017

dead-claudia commented on Dec 5, 2017

reverofevil commented on Dec 11, 2017

zpdDG4gta8XKpMCd commented on Dec 11, 2017

reverofevil commented on Dec 12, 2017

zpdDG4gta8XKpMCd commented on Dec 12, 2017

metasansana commented on Dec 14, 2017

ahejlsberg commented on Aug 30, 2019

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions