Forth implemented in Rust trait system

https://github.com/Ashymad/fortraith

by Ashymad • 6 years ago

157 83 6 years ago

github.com

jerf• 6 years ago

Finally, Rust is production-ready.

It is neat to see something more practical than an Brainf* interpreter.

ptspts• 6 years ago

A list of even more practical pieces of production code in Rust: https://wiki.mozilla.org/Oxidation#Shipped

saagarjha7• 6 years ago

I suspect you missed the /s

andylei• 6 years ago

Rust's trait system is Turing complete

has anyone tried implementing rust in rust's trait system

saagarjha7• 6 years ago

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

samatman2• 6 years ago

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.

_bxg12• 6 years ago

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

_bxg12• 6 years ago

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

andrewflnr• 6 years ago

Doom might actually be easier! Implementing borrowck is hard.

Skunkleton• 6 years ago

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

crazypython• 6 years ago

I 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• 6 years ago

Zig takes this approach. I haven't done more than kick the tires curiously, but it seems very cool.

empath75• 6 years ago

Doesn’t the compiler already do optimizations like that?

ncmncm2• 6 years ago

The 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.

dependenttypes9• 6 years 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?

vertex-four• 6 years ago

Rust is getting that, gradually, with the work of replacing the ad-hoc "const evaluator" with miri (an interpreter for a Rust intermediate representation). Right now you have procedural macros, which are Rust code that operates on the syntax tree, including custom attributes.

Proper reflective metaprogramming would be a fairly big step though - right now, the macro systems happen well before the type system even gets a chance to look at the code, so the data to play with types in an interesting way isn't there at the right step.

Animats2• 6 years ago

Rust is getting that, gradually.

Uh oh. I'd hoped the language would settle down.

The Go crowd knows when to stop. Go is mediocre, but stable.

zokier• 6 years ago

Rust have procedural macros https://doc.rust-lang.org/reference/procedural-macros.html

zozbot234• 6 years ago

I 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.

Because "full use of the programming language" implies Turing completeness, which means compilation may require unbounded time and compute resources. You can allow use of a non-Turing complete subset, and this is something that dependently-typed languages can do quite elegantly.

pilif• 6 years ago

Many type systems are already Turing complete like C++ and indeed Rust as evidenced by the project linked here.

It’s a valid point. Of compilation already is Turing complete, why not just drop the pretense and allow arbitrary compile time expressions.

dependenttypes9• 6 years ago

A program that requires 2^256 time units and 2^256 memory units is not really any better compared to unbounded computations.

dimtion• 6 years ago

One issue not yet mentioned with Turing complete language at compile is that it makes tooling and IDE integration much more difficult.

When you need to run an unbounded program each time you want to provide real time feedback, like type inference or in Rust case lifetime inference, you make the language tooling much less simple and accessible.

dependenttypes9• 6 years ago

One issue not yet mentioned with Turing complete language at compile is that it makes tooling and IDE integration much more difficult

How so?

When you need to run an unbounded program

How is a program that provably terminates but takes 2 years to finish any better for compile-time computation? You want timeouts in either case.

dependenttypes9• 6 years ago

It should be noted that gcc and clang both execute certain functions at compile-time at their higher optimization levels.

In addition C++ has constexpr which marks an expression to be evaluated at compile-time.

codr7• 6 years ago

I suspect a big reason is that you need an interpreter in addition to the compiler. From what I understand, the D gods spent quite some time and effort developing theirs.

For interpreted languages, there are no excuses; hooking into the interpreter at compile time is trivial. Full macros [0] are nice, but depends a lot on the syntax. A way to evaluate expressions at compile time [1] would go a long way.

[0] https://github.com/codr7/gfoo#macros

[1] https://github.com/codr7/gfoo#bindings

dependenttypes9• 6 years ago

If you do not want to implement a separate interpreter you can do multiple compilation passes instead.

octo_t• 6 years ago

Another issue not mentioned is cross-compiling.

If the result of my `sort ` function is dependent on `sizeof(void )` being 8, when I compile from my x86 hardware for a 32-bit only architecture, assumptions go awry.

Note that this isn't likely with something like sort, but definitely is* likely with precomputing values/structs etc.

staticassertion• 6 years ago

They do. You can.

You have procedural macros, which are literally "Rust code is the input, which you write rust code to manipulate, and output more rust code".

You have const fns, which are interpreted at compile time, and are closer to what you're referring to.

a13692099933• 6 years ago

Because that's fundamentally incompatible with a competently-designed compiled language. Consider:

  fn immutable foo() long:
    asm(long x:"rax") "mov rax 7"
    return x

Now try cross-compiling that from a 32-bit ARM machine.

Aside: D is kind of weird in this regard because most of it is designed to work as a interpreted language as well as a compiled one. To the extent the D is good, it's not compiled[0]; to extent that it's compiled[0], it's not good.

0: in the language design sense, not the language implementation sense.

BeKindAndLearn2• 6 years ago

Pretty much all languages with turing-complete compile-time expressions only expose a subset. This comfortably lands in the "not in that subset" category.

zamalek• 6 years ago

This is just nerd flexing. Rust has a slightly more flexible compile time code generation story than D. There's even a package that connects to your SQL DB and type-checks your queries.

pull_my_finger• 6 years ago

Terra[1] does this using Lua as it's compile time language.

[1] http://terralang.org/

s17n• 6 years ago

Lisp failed as an industrial language precisely because it has powerful meta programming capabilities. In the real world, nobody wants to have to solve a puzzle every time they visit a new area of the codebase.

BiteCode_dev• 6 years ago

I hope not.

I really don't want Rust to be crippled with a 1000 of DSL just because devs could write them easily.

GolDDranks2• 6 years ago

The recent signs are that in near-future Rust releases you are able to have rudimentary logic in constant expressions: if, match, loop etc. (Around Rust 1.47 ish. That's three months away.)

When the capabilities of the constant evaluation system get improved and stabilized, we are going to see the exact feature you are describing. (With the caveat that non-deterministic functions are not allowed to ensure deterministic builds.)

ncmncm2• 6 years ago

This 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• 6 years ago

Sort 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.

Ashymad3• 6 years ago

Indeed, 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/

fmakunbound• 6 years ago

This is a pretty superficial treatment of Forth. It's more of a simple RPN calculator than a Forth.

frompdx• 6 years ago

Definitely 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.

Ashymad3• 6 years ago

The 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• 6 years ago

The 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.

Ashymad3• 6 years ago

You 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• 6 years ago

Sick! :-)

unixhero• 6 years ago

Wow that's what I call an emergent property!

Forth implemented in Rust trait system

Related Stories