GitHub - Dragon-Hatcher/type-system-chess: Chess implemented entirely in the Rust and TS type systems. · GitHub
/" data-turbo-transient="true" />
Skip to content
Search/
Sign in<br>Sign upAppearance settings
You signed in with another tab or window. Reload to refresh your session.<br>You signed out in another tab or window. Reload to refresh your session.<br>You switched accounts on another tab or window. Reload to refresh your session.
Dismiss alert
{{ message }}
Dragon-Hatcher
type-system-chess
Public
Notifications<br>You must be signed in to change notification settings
Fork
Star<br>312
main
BranchesTags
Go to file
CodeOpen more actions menu
Latest commit
History<br>30 Commits<br>30 Commits
Folders and files<br>NameNameLast commit message<br>Last commit date<br>rust
rust
ts
ts
LICENSE
LICENSE
README.md
README.md
showcase.png
showcase.png
View all files
Repository files navigation
Type System Chess
This repo contains chess implemented entirely in the (stable) Rust and Typescript type systems. Both languages feature turing complete type systems making this possible.
What I mean by a chess implementation is the ability to generate the list of legal moves and then select and play one by specifying the start and end square. See Features for more.
I believe that this is the most complicated program implemented in the Rust type system. If you know of any similarly complex Rust projects please let me know.
Other very complex type systems programs have been written in Typescript. For example, HypeScript.
Features
The programs implement all chess rules except for draws by repetition and the 50 move rule. That means they cover:
Castling
Promotion
En Passant
Both versions allow you to play moves using long algebraic notation (specifying the start and end square). Because TS allows parsing strings in the type system I also implemented a FEN parser for the TS version.
Check main.rs and index.ts for more on how to use.
Bugs
I have implemented a few tests for each program but it is likely that bugs still exist. If you find a bug or add more tests feel free to open an issue/PR.
Performance
Both programs are rather slow. Running the TS test suite takes about 30 seconds on my computer and running the Rust test suite takes about 10 minutes 50 seconds.
Update: An update was made to the Rust compiler specifically because of this project which speeds up compilation by an order of magnitude. See this article by @nnethercote about how he made this and other performance improvements to the Rust compiler.
Rust performance was a fair bit better up until the end when I added the various complex pawn moves. I suspect that the compiler might have some extra difficulties with how these are implemented.
I was almost able to get away without increasing the recursion limit for the Rust program. It was fine after adding castling kingside but broke when I added queenside castling (i.e. it is very close to not needing the extra recursion).
Inspiration
Typescript
I read a number of different articles about programming in TS types but this one specifically is where I drew most of my inspiration.
Type System Game Engines
A few of the utility types I used are from this article.
Rust
There aren't nearly as many resources about programming in the Rust typesystem (probably because, as I will explain shortly, it is significantly harder than typescript). The only one I found is this article which I believe is the original proof of the Turing Completeness of the Rust type system. I use the methodology described in this article.
Rust's Type System is Turing-Complete
Thoughts
Typescript
As esoteric program languages go TS types aren't really that bad. I would honestly hesitate to even call it a Turing-Tarpit; It's just a slightly strange functional program language. With let bindings, math, and a big speed increase it could be almost pleasant to use.
Rust
Rust types are a real pain to work with. To give a little taste: the Typescript program is about 900 lines of code (including the FEN parser) to the Rust version's 5000.
A few issues1 I encountered:
Every Computation has to be performed twice.
Each time you use a trait you have to rewrite the same thing twice, once in the where clause and once in the output type. In fact, if you nest layers you have to specify each layer again. So Foo> requires, roughly, this.
Bar: RunFoo,<br>type Output = Foo>">where Baz: RunBarQaz>,<br>BarBaz, Qaz>: RunFoo,<br>type Output = FooBarBaz, Qaz>>
For some truly horifying examples of this look in move_gen::castle.
There is no form of negative reasoning. This results in the type RankEq (which checks if two ranks are equal) being implemented as a lookup table for all 64 combinations of two ranks.
Ironically there is no way to get the Rust compiler to understand that an enum is closed. So just becuase you implement something for colors White and Black doesn't mean the Rust compiler knows that you have implemented it for all implementers of the...