5 ms·
For TypeScript I'm not really sure what you would expect them to change just to avoid being Turing complete. Its Turing completeness is a straightforward conseq
by tshaddox 3y ago
For TypeScript I'm not really sure what you would expect them to change just to avoid being Turing complete. Its Turing completeness is a straightforward consequence of its basic building blocks: iteration, conditional types, and recursive type definitions. Of course TypeScript could go out of its way to avoid Turing completeness by just specifying a maximum recursion depth or something similar, but why?
- RussianCow 3y ago> specifying a maximum recursion depth or something similar Doesn't TS do exactly this? It doesn't seem like setting a cap on recursion depth would disqualify something from being Turing complete. Or am I misunderstanding your comment?
- explaininjs 3y agoWhen recursion is the only method of iteration, of course it would.
- smacke 3y agoIs the recursion limit an implementation detail of the compiler though, or something statically built into the language? If the former there's nothing to prevent the language itself from being Turing complete. (Similar to how every Turing complete programming language today runs on something technically weaker than a Turing machine due to finite memory.)
- explaininjs 3y agoThere’s no spec so the compiler is the language.
- olalonde 3y agoWhat is the other method of iteration? Also, TypeScript does have a recursion limit[0]. [0] https://herringtondarkholme.github.io/2023/04/30/typescript-magic/ https://herringtondarkholme.github.io/2023/04/30/typescript-...
- CSMastermind 3y agoDo you mean within a state machine or in practice? Iteration (loops) are typically represented as jump or branch instructions while recursion requires the creation of a new stack frame on the call stack.
- olalonde 3y agoNo, in TypeScript's type system. As far as I know, recursion is the only method of iteration but the comment I was replying to seemed to imply otherwise.
- explaininjs 3y agoThe comment does not imply otherwise
- olalonde 3y agoI thought you did because of the "would". So you're saying that TypeScript is not Turing complete?
- deleted 3y ago[deleted]
- explaininjs 3y agoNothing is Turing complete. But it is the stronger form of incomplete where even on a machine with truly unlimited memory it’d still be unable to model some (almost all, formally) executions.
- Zamicol 3y ago>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 agoYou 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 agoPossibly 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 agoI'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 agoThe 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
- 3y ago
- jongjong 3y agoIMO, TypeScript fails as a developer tool. Developer tools should guide the developer towards making good decisions. TS guides developers towards making poor decisions by facilitating code with complex interfaces. JavaScript taxes interface complexity through increased cognitive load. Typescript frees developers from that tax and harms architecture in the process. Funny how business gurus keep saying over and over that incentives are everything and yet when it comes to choosing developer tools for their businesses, they choose tools which promote terrible incentives, instead they choose "that which sounds good"... It's like communism. It sounds good in theory but it fails spectacularly at the incentive layer... It fails at the most important layer.
- motoxpro 3y agoJust write your JS first and then type it afterward. Best of both.
- wk_end 3y agoIt's the exact opposite; TypeScript discourages complex interfaces by making them explicit. It's far too easy in a dynamic language for devs to introduce absurdly complex interfaces without understanding the cognitive load it's imposing on other users. In TypeScript, they're forced to type it...which immediately reveals that complexity - if they're able to do it all! This isn't theoretical; the only reason TypeScript allows for such complex interfaces is precisely because JavaScript devs have created those interfaces, and TypeScript makes a best-effort to make as much JS code type-able as possible.