5 ms·

>Turing completeness could be disabled, if it is checked that a type cannot use itself in its definition (or in a definition of an referenced type) in any way,

>Turing completeness could be disabled, if it is checked that a type cannot use itself in its definition (or in a definition of an referenced type) in any way, not just directly as it is tested currently. This would make recursion impossible. That sounds like a reasonable resolution. https://github.com/microsoft/TypeScript/issues/14833 https://github.com/microsoft/TypeScript/issues/14833

n2d4 3y ago
You can't do that because recursion is a feature, not a bug. It lets you do really cool things, such as: type MultiDimArray<T> = T[] | MultiDimArray<T>[]; type LinkedList<T> = { value: T, next: LinkedList<T> | null, }; type Json = string | number | null | Json[] | { [k: string]: Json };
krapp 3y ago
Possibly a dumb question but why would Turing incompleteness be desirable in a language whose entire purpose is generating code in a Turing complete language?
- koito17 3y ago
  I'm not an expert on type theory, but I would guess "Turing complete types" make type checking an undecidable problem, similar to how dependent types make type inference undecidable, since dependent types let you more or less encode arbitrary things into a type (e.g. p is a value of type Prime). That at the very least gives you an infinite search space, and the possibility to encode e.g. a halting property into types.
- MobiusHorizons 3y ago
  The problem being discussed is not that typescript the language that compiles to JavaScript is Turing complete, but rather that typescript types the compile time code necessary to validate that typescript are Turing complete. The consequence is compilation speed foot guns, readability and complexity. Not the end of the world, but the sort of thing some people reasonably consider a downside
mostlylurks 3y ago
Not allowing types to be nested within themselves would be a massive downside. You'd lose the ability to model anything tree-like in a reasonable manner. There are some obvious workarounds, but they're so inconvenient that nobody using a scripting language would ever want to be limited to using them.

n2d4 3y ago

You can't do that because recursion is a feature, not a bug. It lets you do really cool things, such as: type MultiDimArray<T> = T[] | MultiDimArray<T>[]; type LinkedList<T> = { value: T, next: LinkedList<T> | null, }; type Json = string | number | null | Json[] | { [k: string]: Json };

krapp 3y ago

Possibly a dumb question but why would Turing incompleteness be desirable in a language whose entire purpose is generating code in a Turing complete language?

koito17 3y ago
I'm not an expert on type theory, but I would guess "Turing complete types" make type checking an undecidable problem, similar to how dependent types make type inference undecidable, since dependent types let you more or less encode arbitrary things into a type (e.g. p is a value of type Prime). That at the very least gives you an infinite search space, and the possibility to encode e.g. a halting property into types.
MobiusHorizons 3y ago
The problem being discussed is not that typescript the language that compiles to JavaScript is Turing complete, but rather that typescript types the compile time code necessary to validate that typescript are Turing complete. The consequence is compilation speed foot guns, readability and complexity. Not the end of the world, but the sort of thing some people reasonably consider a downside

mostlylurks 3y ago

Not allowing types to be nested within themselves would be a massive downside. You'd lose the ability to model anything tree-like in a reasonable manner. There are some obvious workarounds, but they're so inconvenient that nobody using a scripting language would ever want to be limited to using them.