Hacker News Reader

Hacker News

Comment by andylei | Hacker News Reader

Full thread

andylei

> Rust's trait system is Turing complete

has anyone tried implementing rust in rust's trait system

View on HN

How about making an LLVM backend which compiles to rust traits?

You're thinking too small. I want to see it run Doom ;)

Doom might actually be easier! Implementing borrowck is hard.

Turing complete≠uses the syntax of your favorite programming language.

Incorrect.

Turing completeness means using the syntax of your favorite programming language is "merely" a matter of writing the appropriate program.

What GP is proposing is completely impractical, of course. But not unreasonable, and certainly not impossible.

No, because the program may not be able to actually understand the syntax of your favorite programming language. As I mentioned in another comment, FRACTRAN is Turing-complete and you cannot just shove a string of Rust code at it because it has no idea what a string is; the best you can do is implement the "compiler" as working on some numerically-encoded version of Rust and producing some encoded version of a native binary on the other side. So you've lost the syntax because you've had to do that additional encoding.

You are misunderstanding the difference between “can in theory” and “presently able to do.”

I don't think so; would you mind explaining why you think that?

A Turing-complete language can, in theory and assuming no real-world limitations like RAM, do any computation. You can use Rust traits to compile Rust, or run a JVM instance, or whatever. Input and output are limited to what the compiler has access to, but you could perhaps have input as source files and output as text strings in a Rust binary.

That doesn't mean that the OP's hack can be used today, or even tomorrow for compiling-Rust-in-Rust. But you could, in theory, do so.

My point is that it's not actually going to be "you can type Rust code here and the trait system will magically compile it", it at best is going to be "you make some trait abomination that is somehow maps to the Rust program you wanted to compile and the machine will give you back some other abomination which you can through some encoding process get some sort of useful result out of".

I understand the distinction between a string and a numerically-encoded version of it, but my computer doesn't.

But your computer does understand the distinction between a string numerically encoded as consecutive bytes in memory, versus a string encoded as a arbitrary-precision integer equal to ( 2^(first ASCII value) * 3^(second ASCII value) * 5^(third '') * 7^(fourth '') * ... ).

Any Turing-complete system can do anything a general computer can do, which includes compiling your favorite programming language.

No, that's not what Turing complete means. Turing complete means it can do an arbitrary computation, but "implementing Rust" usually means it needs to be able to take in a string of code and produce a binary, which means your program needs to have some way of actually doing that. Sure, you can encode the compiler into the Turing machine, but an arbitrary Turing-complete tarpit may not actually have the syntax to know what a string is. Usually the best you can do is encode the programming language into some form the machine can understand. (For example, with Fractran you'd encode your input as some sort of Gödel numbering before giving it to the program.)

Compiling is an arbitrary computation.

Encoding the inputs/outputs for a given TC system may be a pain, but that is irrelevant to expressiveness power.

Right, I'm not saying you can't put the compiler for the encoded input/outputs into the machine or that it's not expressive enough. I'm just saying that you'll have to encode stuff, it's not like traits somehow can magically give you a "compileToRust()" function that you pass the unmodified code into.

Yeah, but when someone mentions some system is TC they are not claiming input/output is easy to encode.

In fact, in most cases, when you hear the TC claim it is about an exotic system :)

Fractran accepts any positive integer as an argument, and it is trivial to convert any, say, UTF8 encoded string to a positive integer.

Reply on news.ycombinator.com