3 ms·

Rust type system is also Turing complete: https://sdleffler.github.io/RustTypeSystemTuringComplete/ https://sdleffler.github.io/RustTypeSystemTuringComplete/ I

Rust type system is also Turing complete: https://sdleffler.github.io/RustTypeSystemTuringComplete/ https://sdleffler.github.io/RustTypeSystemTuringComplete/ It has allowed us to emulate (numeric) const generics in crates like typenum (https://docs.rs/typenum https://docs.rs/typenum) long before they were implemented as a proper language feature. Even today, typenum is more powerful in some regards than the stable version of const generics.

saghm 5y ago
Another fun Rust one I found was trying to make a macro to do arbitrary levels of `Option` flattening. There's an existing method `Option::flatten`, but it only flattens a single level (i.e. `Option<Option<T>>` to `Option<T>`, which makes sense given you can't really specify return type any differently. I had a hunch that it might be possible to do this by making a trait with a generic type parameter specifying that a given "flattening" is possible, e.g. `Option<Option<Option<T>>` would implement `Flatten<Option<Option<T>>` and `Flatten<Option<T>>`. This did turn out to be possible to specify with a couple of impl blocks; however, the compiler tried to exhaustively enumerate all of the possible implementations of this trait on all levels of `Option` nesting, whereas I had implicitly assumed it would just verify the correctness of the trait bounds that I used in my code. The compiler generated all the implementations of flatten for `Option<T>`, `Option<Option<T>>`, `Option<Option<Option<T>>>`...until it understandably hit a max recursion limit. Since the compiler obviously could not tell that there was no actual end to the implementations, it suggested that I try increasing the recursion limit with a crate-level attribute, and just for fun I followed its suggestions to keep increasing the limit to no avail, after which I took pity on the compiler and stopped forcing it to continue toiling in its Sisyphean endeavor.
- exdsq 5y ago
  Sort of reminds me of implementing multiplication in the type system of TypeScript with Peano arithmetic - endless recursion limit errors of Succ<Succ<Succ<Succ<Zero>>>>... Never did get it to work properly :(
- tialaramex 5y ago
  As you discovered, Rust's Generics aren't like a C++ template. The C++ template really is just fill-in-the-blanks, (but with a special behaviour named SFINAE, Substitution Failure Is Not An Error) so I believe this trick would have worked if you'd been doing C++, producing all the necessary layers of flattening for whatever input you had. To me, if I find that manually writing two more layers of flatten isn't enough, I would start to think this is the wrong problem to be solving.
  - saghm 5y ago
    Yep! I had heard this before, but like with a lot of things, I had to really dig into it and test the boundaries to fully understand at a fundamental level. > To me, if I find that manually writing two more layers of flatten isn't enough, I would start to think this is the wrong problem to be solving. Definitely! This was more of a fun intellectual exercise than anything else. I absolutely love seeing what can be done at compile time, and a lot of stuff that isn't useful in practice can still be pretty entertaining.
    - tialaramex 5y ago
      > test the boundaries to fully understand at a fundamental level. This sort of thing is why I wrote https://crates.io/crates/misfortunate https://crates.io/crates/misfortunate Rust lets me write safe implementations of well-known Traits like Ord (the trait which compares things because they are ordered) but promises the outcome when these traits are relied upon elsewhere is always safe even if my implementations are very silly. So I can sort() things for which I've implemented nonsensical ordering (e.g. they all claim they're before each other) and Rust promises that's still safe. This futile task might well not finish and if it does finish they won't seem any more or less "sorted" than they were before I tried, but it won't crash or do anything unfathomable. And indeed that's exactly what happens, cementing my faith in the idea of Rust. [Not all Rust's traits are safe. If you have to say "unsafe" to write the implementation then it wasn't safe, and if you do something nonsensical in an unsafe trait then you get to keep both halves when it breaks, misfortunate is only interested in safe traits]

saghm 5y ago

Another fun Rust one I found was trying to make a macro to do arbitrary levels of `Option` flattening. There's an existing method `Option::flatten`, but it only flattens a single level (i.e. `Option<Option<T>>` to `Option<T>`, which makes sense given you can't really specify return type any differently. I had a hunch that it might be possible to do this by making a trait with a generic type parameter specifying that a given "flattening" is possible, e.g. `Option<Option<Option<T>>` would implement `Flatten<Option<Option<T>>` and `Flatten<Option<T>>`. This did turn out to be possible to specify with a couple of impl blocks; however, the compiler tried to exhaustively enumerate all of the possible implementations of this trait on all levels of `Option` nesting, whereas I had implicitly assumed it would just verify the correctness of the trait bounds that I used in my code. The compiler generated all the implementations of flatten for `Option<T>`, `Option<Option<T>>`, `Option<Option<Option<T>>>`...until it understandably hit a max recursion limit. Since the compiler obviously could not tell that there was no actual end to the implementations, it suggested that I try increasing the recursion limit with a crate-level attribute, and just for fun I followed its suggestions to keep increasing the limit to no avail, after which I took pity on the compiler and stopped forcing it to continue toiling in its Sisyphean endeavor.

exdsq 5y ago
Sort of reminds me of implementing multiplication in the type system of TypeScript with Peano arithmetic - endless recursion limit errors of Succ<Succ<Succ<Succ<Zero>>>>... Never did get it to work properly :(
tialaramex 5y ago
As you discovered, Rust's Generics aren't like a C++ template. The C++ template really is just fill-in-the-blanks, (but with a special behaviour named SFINAE, Substitution Failure Is Not An Error) so I believe this trick would have worked if you'd been doing C++, producing all the necessary layers of flattening for whatever input you had. To me, if I find that manually writing two more layers of flatten isn't enough, I would start to think this is the wrong problem to be solving.
- saghm 5y ago
  Yep! I had heard this before, but like with a lot of things, I had to really dig into it and test the boundaries to fully understand at a fundamental level. > To me, if I find that manually writing two more layers of flatten isn't enough, I would start to think this is the wrong problem to be solving. Definitely! This was more of a fun intellectual exercise than anything else. I absolutely love seeing what can be done at compile time, and a lot of stuff that isn't useful in practice can still be pretty entertaining.
  - tialaramex 5y ago
    > test the boundaries to fully understand at a fundamental level. This sort of thing is why I wrote https://crates.io/crates/misfortunate https://crates.io/crates/misfortunate Rust lets me write safe implementations of well-known Traits like Ord (the trait which compares things because they are ordered) but promises the outcome when these traits are relied upon elsewhere is always safe even if my implementations are very silly. So I can sort() things for which I've implemented nonsensical ordering (e.g. they all claim they're before each other) and Rust promises that's still safe. This futile task might well not finish and if it does finish they won't seem any more or less "sorted" than they were before I tried, but it won't crash or do anything unfathomable. And indeed that's exactly what happens, cementing my faith in the idea of Rust. [Not all Rust's traits are safe. If you have to say "unsafe" to write the implementation then it wasn't safe, and if you do something nonsensical in an unsafe trait then you get to keep both halves when it breaks, misfortunate is only interested in safe traits]