Skip to content

Instantly share code, notes, and snippets.

View Dev380's full-sized avatar
💫
I love the stars

Dev380

💫
I love the stars
View GitHub Profile
#!/bin/rust-script
/// This program uses the Rust type system to solve CCC '20 J1. Rust's type system is Turing complete
/// (see prior art using the SKI calculus [here](https://github.com/Dev380/rust-types-turing-complete)) because
/// solving generic type constraints is isomorphic to reductions in prolog, which is turing complete (in fact
/// the rust type team is rewriting prolog in Rust right now to make the type solver faster). The basic idea
/// is to have a generic type be the input to a function and an associated type be an output. In practice, this
/// means creating a trait for type functions of a particular arity and implementing it for each function type,
/// then casting like so: `<SpecificFunction as FunctionType<ArgumentType>>::Output` to get the output type.
/// Surprisingly, this is only mildly annoying to program it (barring syntax and boilerplate pains), feeling like