12 ms·

Functions and algorithms implemented purely with TypeScript's type system

166 points by behnamoh 3y ago

spencerchubb 3y ago
Looks like the arithmetic only supports integers 0 through 10 https://github.com/ronami/meta-typing/blob/master/src/utils/math.d.ts https://github.com/ronami/meta-typing/blob/master/src/utils/...
- mozey 3y ago
  "This project attempts to push TypeScript's type system to its limits by actually implementing various functions and algorithms, purely on top of the type system... Please note that this project is meant to be used for fun and learning purposes and not for practical use"
  - spencerchubb 3y ago
    It is indeed interesting! I was just trying to analyze it a bit deeper
- n_e 3y ago
  You can count to an arbitrary number (until the recursion limit) by using tuples of length N (and go back and forth to number literals by using the type of tuple['length']) e.g. : type zero = [] type Inc<N extends string[]> = [...N,''] type Dec<N extends string[]> = N extends [...infer T,''] ? T : never type one = Inc<zero> type two = Inc<one> type oneb = Dec<two>
  - dqbd 3y ago
    A tuple does have a upper limit of 10 000 elements, which means that with this approach we can count to 10 000 at most. Another approach which I tried is to do arithmetics on digits directly, storing digits in a tuple instead, but the code is not as elegant as the tuple one https://github.com/dqbd/ts-math-evaluate/blob/main/src/math/add.ts https://github.com/dqbd/ts-math-evaluate/blob/main/src/math/...
- vesinisa 3y ago
  Noticed the same. Not a very practical computer, although you could say the host CPU does the same except for int's in 0 through 2^64-1.
behnamoh 3y ago
Related: https://news.ycombinator.com/item?id=36568183 https://news.ycombinator.com/item?id=36568183
- Kerrick 3y ago
  Also related: https://news.ycombinator.com/item?id=35120084 https://news.ycombinator.com/item?id=35120084
TuringTest 3y ago
Proof that type systems are nothing else that domain-specific languages that run at compile time. When seen like that, it should be no surprise that they can be coerced to do general computation.
- vore 3y ago
  That’s not universally true, and indeed some languages (e.g. Haskell without extensions) have explicitly designed decidable type systems.
  - slaymaker1907 3y ago
    That just means that it isn’t Turing complete which is true of many DSLs.
    - formulathree 3y ago
      Which means you can't to general computation with it. You're just reiterating his point.
      - slaymaker1907 3y ago
        Regex (at least most implementations) isn't Turing complete, but you can still do a lot of stuff with it and I think most type systems go far beyond regex in expressive power. Unless you're trying to write quines, you probably don't need Turing completeness.
- marton78 3y ago
  Yes. We have known this since C++ template metaprogramming.
- paganel 3y ago
  > else that domain-specific languages that run at compile time. Probably stupid question, but that probably means that one could, theoretically, implement a type system for any one of those DSL(-like) type systems, isn't that correct? And so on and so forth, we could have, theoretically, DSL-like type systems all the way down.
mpoteat 3y ago
At the risk of too much self promotion, I have a much deeper and more feature complete treatment of many of these type-level computations, represented with higher kinded types (which are thus composable) here: http://hkt.code.lol/ http://hkt.code.lol/ This is my "lodash for types" project. It supports integer division for up to 2^64, for example. It has over 200 composable utility types.
- primitivesuave 3y ago
  I love this. I'm frequently experimenting with the "syntactic sugar" possibilities of the TypeScript type inference system, and am truly in awe of your implementation (as well as the excellent and thorough commenting).
- tchaffee 3y ago
  I know I'll likely get a biased answer here but what do you think the cons are of using types in this way? My current thinking is that types should should optimize for an easy learning curve so folks can just get on with writing code. This seems like it would require a deep knowledge of TS. lodash does come to mind in fact. The last few shops where I've worked use a very small subset of lodash utilities and ignore most of the library. Their documentation is terse so it's often easier to just write your own code that is longer but more readable to the average engineer.
  - mpoteat 3y ago
    Well, slower compile times, and additional complexity are the biggest cons. There is a project I'm working on to eliminate the latter bit - ideally, a way to represent these complex types with "zero type-level code"
    - Byamarro 3y ago
      Could you elaborate on the project? I'm curious
  - imiric 3y ago
    Conversely, and I don't mean to sound flippant, but are there any pros of (ab)using types in this way? These projects are interesting in an amusing "oh look, another Turing complete type system" way, for the author to gain expertise, and as something to highlight in CVs and to chat about during interviews. But other than that, I would never actually choose to use any of this in a real-world project. Depending on the stability of this API (TPI?), and subjecting colleagues to esoteric libraries would be a nightmare to maintain and support.
jumploops 3y ago
I recently learned about Typescript transformers[0] and wish they were better supported in a first-class manner. Working with ttypescript or ts-patch[1] is easy enough, but it still feels like you're doing something you shouldn't be doing. My goal was to pass the Typescript types to the JS runtime, maybe there's a better way and GPT-4 just led me astray... [0] https://github.com/itsdouges/typescript-transformer-handbook https://github.com/itsdouges/typescript-transformer-handbook [1] https://github.com/nonara/ts-patch https://github.com/nonara/ts-patch
asicsp 3y ago
See also: https://github.com/tayllan/awesome-algorithms https://github.com/tayllan/awesome-algorithms
Hirrolot 3y ago
For those who are wondering whether types can be computed in the same way as values -- yes, they can, with a proper type system. Idris [1] is a prominent example of a programming language with first-class types, meaning that if you can perform (finite) computation on values, you can do so on types. The difference between Idris and TypeScript (Rust, C++, etc.) is that the former treats types as values, and therefore has no traditional separation of values and types; everything is done with the same syntax. Zig strives to use the same syntax for metacomputation, although its approach is not tightly integrated into the type system, which is why you'd see compilation errors at expansion, not function definition. [1] https://www.idris-lang.org/ https://www.idris-lang.org/
marcle 3y ago
The following homage to Aphyr’s "Typing the technical interview" solves the N-queens problem using types in Typescript. This is both funny and insightful. https://www.richard-towers.com/2023/03/11/typescripting-the-technical-interview.html https://www.richard-towers.com/2023/03/11/typescripting-the-... (Edit: this is mentioned elsewhere in this thread by Kerrick)
- draw_down 3y ago
  [dead]
jongjong 3y ago
I don't know whose brilliant idea it was to turn TypeScript's type system into a Turing-complete language but now many developers are actually using it as such on real projects and it's a massive productivity drain and it makes some code impossible to read... Often, the IDE can't even display the type when you hover over the variable because it's too darn complicated. Did anyone ever think "Hang on, maybe the problem, the reason why coding is so difficult is that interfaces are often too darn complicated to keep track of? Oh, wait a minute, if the interfaces were really simple, would we even need TypeScript at all? Why don't we just design our software in such a way that the interfaces between components are simple so that we can easily remember which functions accept what kinds of input without losing our train of thought? Wait a minute, this idea already exists? It's called loose coupling and high cohesion. How in Alan Kay's name did I not think of it before???"
- sk0g 3y ago
  If the Typescript team got carte blanche to create their own language, it would likely be... C#. TS is complicated and chaotic because the language it compiles down to is. TS' aim is to model the behaviour seen in JS in a flexible, user-friendly type system. Good luck! What doesn't make sense to me is when teams (like mine) have a blank slate and the choice of any mainstream backend language, and then opt in to that ecosystem anyway. TS is good when you're coming from JS sure, but some of us have used more "sane" languages like C# and Go :(
  - deleted 3y ago
    [deleted]
  - seedboot 3y ago
    > If the Typescript team got carte blanche to create their own language, it would likely be... C#. This is sarcasm, right? The creator of TS is the lead architect of C#
    - dnadler 3y ago
      I feel like that’s supporting the parent, right?
germandiago 3y ago
oh, C++ metaprogramming!?
- lionkor 3y ago
  is<std::this_cpp<meta::pro>, std::enable_if_v<gramming>>>>>>>>>>>>>>?
agumonkey 3y ago
Is TS becoming the leader in faux dependent typing ? it seems that the metalevel boundary has almost evaporated in it.
Already__Taken 3y ago
so a typescript pattern I keep tripping into, which is probably bad practice on my part, is parallel data structures. say any large state object. I have an object the same shape but holding errors of subkeys. the state setter clears the errors object keys per access modification. TS does not like that error object. it can never have an error there isn't a setter for, but it complains it might not.
nsenifty 3y ago
SQL implemented in typescript types - https://github.com/codemix/ts-sql https://github.com/codemix/ts-sql
johnea 3y ago
Yes, of course. Once we annihilate all human life on earth, the stock market will be at $0.

166 points by behnamoh 3y ago

Looks like the arithmetic only supports integers 0 through 10 https://github.com/ronami/meta-typing/blob/master/src/utils/math.d.ts https://github.com/ronami/meta-typing/blob/master/src/utils/...

mozey 3y ago
"This project attempts to push TypeScript's type system to its limits by actually implementing various functions and algorithms, purely on top of the type system... Please note that this project is meant to be used for fun and learning purposes and not for practical use"
- spencerchubb 3y ago
  It is indeed interesting! I was just trying to analyze it a bit deeper
n_e 3y ago
You can count to an arbitrary number (until the recursion limit) by using tuples of length N (and go back and forth to number literals by using the type of tuple['length']) e.g. : type zero = [] type Inc<N extends string[]> = [...N,''] type Dec<N extends string[]> = N extends [...infer T,''] ? T : never type one = Inc<zero> type two = Inc<one> type oneb = Dec<two>
- dqbd 3y ago
  A tuple does have a upper limit of 10 000 elements, which means that with this approach we can count to 10 000 at most. Another approach which I tried is to do arithmetics on digits directly, storing digits in a tuple instead, but the code is not as elegant as the tuple one https://github.com/dqbd/ts-math-evaluate/blob/main/src/math/add.ts https://github.com/dqbd/ts-math-evaluate/blob/main/src/math/...
vesinisa 3y ago
Noticed the same. Not a very practical computer, although you could say the host CPU does the same except for int's in 0 through 2^64-1.

behnamoh 3y ago

Related: https://news.ycombinator.com/item?id=36568183 https://news.ycombinator.com/item?id=36568183

Kerrick 3y ago
Also related: https://news.ycombinator.com/item?id=35120084 https://news.ycombinator.com/item?id=35120084

TuringTest 3y ago

Proof that type systems are nothing else that domain-specific languages that run at compile time. When seen like that, it should be no surprise that they can be coerced to do general computation.

vore 3y ago
That’s not universally true, and indeed some languages (e.g. Haskell without extensions) have explicitly designed decidable type systems.
- slaymaker1907 3y ago
  That just means that it isn’t Turing complete which is true of many DSLs.
  - formulathree 3y ago
    Which means you can't to general computation with it. You're just reiterating his point.
    - slaymaker1907 3y ago
      Regex (at least most implementations) isn't Turing complete, but you can still do a lot of stuff with it and I think most type systems go far beyond regex in expressive power. Unless you're trying to write quines, you probably don't need Turing completeness.
marton78 3y ago
Yes. We have known this since C++ template metaprogramming.
paganel 3y ago
> else that domain-specific languages that run at compile time. Probably stupid question, but that probably means that one could, theoretically, implement a type system for any one of those DSL(-like) type systems, isn't that correct? And so on and so forth, we could have, theoretically, DSL-like type systems all the way down.

mpoteat 3y ago

At the risk of too much self promotion, I have a much deeper and more feature complete treatment of many of these type-level computations, represented with higher kinded types (which are thus composable) here: http://hkt.code.lol/ http://hkt.code.lol/ This is my "lodash for types" project. It supports integer division for up to 2^64, for example. It has over 200 composable utility types.

primitivesuave 3y ago
I love this. I'm frequently experimenting with the "syntactic sugar" possibilities of the TypeScript type inference system, and am truly in awe of your implementation (as well as the excellent and thorough commenting).
tchaffee 3y ago
I know I'll likely get a biased answer here but what do you think the cons are of using types in this way? My current thinking is that types should should optimize for an easy learning curve so folks can just get on with writing code. This seems like it would require a deep knowledge of TS. lodash does come to mind in fact. The last few shops where I've worked use a very small subset of lodash utilities and ignore most of the library. Their documentation is terse so it's often easier to just write your own code that is longer but more readable to the average engineer.
- mpoteat 3y ago
  Well, slower compile times, and additional complexity are the biggest cons. There is a project I'm working on to eliminate the latter bit - ideally, a way to represent these complex types with "zero type-level code"
  - Byamarro 3y ago
    Could you elaborate on the project? I'm curious
- imiric 3y ago
  Conversely, and I don't mean to sound flippant, but are there any pros of (ab)using types in this way? These projects are interesting in an amusing "oh look, another Turing complete type system" way, for the author to gain expertise, and as something to highlight in CVs and to chat about during interviews. But other than that, I would never actually choose to use any of this in a real-world project. Depending on the stability of this API (TPI?), and subjecting colleagues to esoteric libraries would be a nightmare to maintain and support.

jumploops 3y ago

I recently learned about Typescript transformers[0] and wish they were better supported in a first-class manner. Working with ttypescript or ts-patch[1] is easy enough, but it still feels like you're doing something you shouldn't be doing. My goal was to pass the Typescript types to the JS runtime, maybe there's a better way and GPT-4 just led me astray... [0] https://github.com/itsdouges/typescript-transformer-handbook https://github.com/itsdouges/typescript-transformer-handbook [1] https://github.com/nonara/ts-patch https://github.com/nonara/ts-patch

asicsp 3y ago

See also: https://github.com/tayllan/awesome-algorithms https://github.com/tayllan/awesome-algorithms

Hirrolot 3y ago

For those who are wondering whether types can be computed in the same way as values -- yes, they can, with a proper type system. Idris [1] is a prominent example of a programming language with first-class types, meaning that if you can perform (finite) computation on values, you can do so on types. The difference between Idris and TypeScript (Rust, C++, etc.) is that the former treats types as values, and therefore has no traditional separation of values and types; everything is done with the same syntax. Zig strives to use the same syntax for metacomputation, although its approach is not tightly integrated into the type system, which is why you'd see compilation errors at expansion, not function definition. [1] https://www.idris-lang.org/ https://www.idris-lang.org/

marcle 3y ago

The following homage to Aphyr’s "Typing the technical interview" solves the N-queens problem using types in Typescript. This is both funny and insightful. https://www.richard-towers.com/2023/03/11/typescripting-the-technical-interview.html https://www.richard-towers.com/2023/03/11/typescripting-the-... (Edit: this is mentioned elsewhere in this thread by Kerrick)

draw_down 3y ago
[dead]

jongjong 3y ago

I don't know whose brilliant idea it was to turn TypeScript's type system into a Turing-complete language but now many developers are actually using it as such on real projects and it's a massive productivity drain and it makes some code impossible to read... Often, the IDE can't even display the type when you hover over the variable because it's too darn complicated. Did anyone ever think "Hang on, maybe the problem, the reason why coding is so difficult is that interfaces are often too darn complicated to keep track of? Oh, wait a minute, if the interfaces were really simple, would we even need TypeScript at all? Why don't we just design our software in such a way that the interfaces between components are simple so that we can easily remember which functions accept what kinds of input without losing our train of thought? Wait a minute, this idea already exists? It's called loose coupling and high cohesion. How in Alan Kay's name did I not think of it before???"

sk0g 3y ago
If the Typescript team got carte blanche to create their own language, it would likely be... C#. TS is complicated and chaotic because the language it compiles down to is. TS' aim is to model the behaviour seen in JS in a flexible, user-friendly type system. Good luck! What doesn't make sense to me is when teams (like mine) have a blank slate and the choice of any mainstream backend language, and then opt in to that ecosystem anyway. TS is good when you're coming from JS sure, but some of us have used more "sane" languages like C# and Go :(
- deleted 3y ago
  [deleted]
- seedboot 3y ago
  > If the Typescript team got carte blanche to create their own language, it would likely be... C#. This is sarcasm, right? The creator of TS is the lead architect of C#
  - dnadler 3y ago
    I feel like that’s supporting the parent, right?

germandiago 3y ago

oh, C++ metaprogramming!?

lionkor 3y ago
is<std::this_cpp<meta::pro>, std::enable_if_v<gramming>>>>>>>>>>>>>>?

agumonkey 3y ago

Is TS becoming the leader in faux dependent typing ? it seems that the metalevel boundary has almost evaporated in it.

Already__Taken 3y ago

so a typescript pattern I keep tripping into, which is probably bad practice on my part, is parallel data structures. say any large state object. I have an object the same shape but holding errors of subkeys. the state setter clears the errors object keys per access modification. TS does not like that error object. it can never have an error there isn't a setter for, but it complains it might not.

nsenifty 3y ago

SQL implemented in typescript types - https://github.com/codemix/ts-sql https://github.com/codemix/ts-sql

johnea 3y ago

Yes, of course. Once we annihilate all human life on earth, the stock market will be at $0.