24 ms·
Forth implemented in Rust trait system
- jerf 6y agoFinally, Rust is production-ready. It is neat to see something more practical than an Brainf* interpreter.
- andylei 6y ago> Rust's trait system is Turing complete has anyone tried implementing rust in rust's trait system
- saagarjha 6y agoTuring complete≠uses the syntax of your favorite programming language.
- samatman 6y agoIncorrect. 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.
- saagarjha 6y agoNo, 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.
- garmaine 6y agoYou are misunderstanding the difference between “can in theory” and “presently able to do.”
- saagarjha 6y agoI don't think so; would you mind explaining why you think that?
- garmaine 6y agoA 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.
- saagarjha 6y agoMy 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".
- _bxg1 6y agoAny Turing-complete system can do anything a general computer can do, which includes compiling your favorite programming language.
- saagarjha 6y agoNo, 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.)
- jfkebwjsbx 6y agoCompiling is an arbitrary computation. Encoding the inputs/outputs for a given TC system may be a pain, but that is irrelevant to expressiveness power.
- saagarjha 6y agoRight, 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.
- jfkebwjsbx 6y agoYeah, 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 :)
- oh_sigh 6y ago
- _bxg1 6y agoYou're thinking too small. I want to see it run Doom ;)
- andrewflnr 6y agoDoom might actually be easier! Implementing borrowck is hard.
- Skunkleton 6y agoHow about making an LLVM backend which compiles to rust traits?
- crazypython 6y agoI don't see why people won't just take the step D and Lisp do-- allowing full use of the programming language at compile time. You can execute an ordinary functions at compile-time to read a DSL from a string or read attributes (reflective metaprogramming) on your program's classes. Take the string it outputs, use mixin(), and you have code. For example: // Sort a constant declaration at Compile-Time enum a = [ 3, 1, 2, 4, 0 ]; static immutable b = sort(a); "a" only appears in the compiler's memory. "sort" is a normal function that runs at compile-time. "allowing accessto the full language at compile-time" is similar to what dynamic languages such as Python and JavaScript give you, except D is a static language with GCC and LLVM backends.
- dilap 6y agoZig takes this approach. I haven't done more than kick the tires curiously, but it seems very cool.
- empath75 6y agoDoesn’t the compiler already do optimizations like that?
- ncmncm 6y agoThe most useful values at compile time are types, so straight-up interpreting the core language at compile time is not enough. You need meta-typed named values to transport types in, and meta-functions to pass them to. Fortraith cleverly re-purposes existing features, doing some violence to language usage conventions to achieve it.
- deleted 6y ago[deleted]
- dependenttypes 6y ago> so straight-up interpreting the core language at compile time is not enough. You need meta-typed named values to transport types in, and meta-functions to pass them to. Can you please explain what you mean by this?
- ncmncm 6y agoThis is brilliant! Equivalent, in its way, to C++ template metaprogramming. It was cheeky to do a Forth instead of an ML. The traditional way to demonstrate TC is by sieving primes at compile time. C++ is actively replacing its compile-time ML with core language features, but isn't there yet. Still, it has been many years since I needed to code any of my own TMP.
- bonzini 6y agoSort of, arithmetic is implemented (through the trait-eval crate) from the Peano axioms. Probably it is not very fast, even in comparison to C++ standards.
- Ashymad 6y agoIndeed, could possibly be sped up by using typenum[1] instead of trait-eval, as it is not Peano axioms based. [1] https://docs.rs/typenum/ https://docs.rs/typenum/
- fmakunbound 6y agoThis is a pretty superficial treatment of Forth. It's more of a simple RPN calculator than a Forth.
- frompdx 6y agoDefinitely interesting, but I don't see any mention of being able to use this interactively or incremental compilation, which is what makes Forth, Forth. Forth isn't just syntax. It's an operating system and a programable programming language.
- Ashymad 6y agoThe trait system and macros run at compile time and sadly there is no way to interact with the Rust compiler. However the macro is fully incremental (creating new words too). Which means in theory if it were possible to ask for input and pass it to the macro it would behave more like a VM: // create a word forth!(: inc 1 + ;); // ask user for $input type Stack = forth!($input inc return); // if you keep the stack around it can be used again forth!({ Stack } inc .); // should print $input + 2
- megameter 6y agoThe term "concatenative language" fits better for adaptations of Forth that also discard major semantics of Forth. There is a holistic quality to Forth that results in a lot of idioms that are not obvious, and concatenative systems that deviate from the whole tend to fall into an unexplored territory. For example, in CASE ... OF ... ENDOF ... ENDCASE, the input value is consumed when OF is entered. But this means that the default result, positioned before ENDCASE, has to move the input value to the top of stack so that it can be consumed before the result. The examples in the ANS standard prefer using >R ... R> as a scratchpad for this purpose, so that any number of results may be pushed into the data stack, while the input is moved onto the result stack and then pushed back to the data stack. But the whole existence of the return stack and words that use it is a curious detail that doesn't come up if you start from an RPN calculator instead of a complete Forth system. Someone writing a RPN system in an applicative language, upon seeing this semantic, might be tempted to beef up the syntax rather than add this idiom. And in Forth this idea likely was only arrived at through the numerous iterations Moore made to achieve better expression in fewer words, since the return stack is useful everywhere.
- Ashymad 6y agoYou got me. I was too lazy to implement the return stack. But it should be fully possible. The hardest part was not implementing things in the trait system, but parsing any non-trivial syntax using the clunky macro_rules!. For this reason if/else/then are not a special syntax but words that block and unblock subsequent word execution.
- mrlonglong 6y agoSick! :-)
- unixhero 6y agoWow that's what I call an emergent property!