Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Forth implemented in Rust trait system

github.com

Post reply on HN
Print view View original

61–70 of 91 posts

Re: Forth implemented in Rust trait system

#61

Post by oh_sigh »

saagarjha wrote: post #29
_bxg1 wrote: post #23

Earlier quoted context omitted.

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…

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

Re: Forth implemented in Rust trait system

#62

Post by a1369209993 »

samatman wrote: post #51
saagarjha wrote: post #34

Earlier quoted context omitted.

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…

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 '') * ... ).

Re: Forth implemented in Rust trait system

#63

Post by Animats »

vertex-four wrote: post #12
crazypython wrote: post #4

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,…

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…

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.

Re: Forth implemented in Rust trait system

#64

Post by mikepurvis »

ImprobableTruth wrote: post #49
qppo wrote: post #45

Earlier quoted context omitted.

The analog of a timeout in a compiler is recursion depth limits.

That alone definitely won't suffice. A naïve fibonacci implementation will give you a recursion depth of n, but even fib(64) take ages.

I don't think he's saying that a limit on recursion depth solves this problem. Rather, it's just a similar scenario where a real-world constraint (memory, time, whatever) comes to bear and may make a compilation fail on machine X where the identical code and environment would otherwise succeed on machine Y.

Re: Forth implemented in Rust trait system

#65

Post by mikepurvis »

dependenttypes wrote: post #38
codr7 wrote: post #36

Earlier quoted context omitted.

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://g…

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

True, but in the cross-compilation case, you then need to do fun stuff like compile anything invoked at compile time for the host arch as well as the target.

Re: Forth implemented in Rust trait system

#66

Post by ImprobableTruth »

mikepurvis wrote: post #64
ImprobableTruth wrote: post #49

Earlier quoted context omitted.

That alone definitely won't suffice. A naïve fibonacci implementation will give you a recursion depth of n, but even fib(64) take ages.

I don't think he's saying that a limit on recursion depth solves this problem. Rather, it's just a similar scenario where a real-world constraint (memory, time, whatever) comes to bear and may make a compilation fail on machine X where the identical code and environment would otherwise succeed on machine Y.

Alright, but that's not a feature, right? Stack limitations are just a natural limitation. Timeouts are something that you'd intentionally introduce, when you don't necessarily need it. And if possible, I'd like to minimize dependency on specifics of the machine as much as possible.

Re: Forth implemented in Rust trait system

#67

Post by Rantenki »

Animats wrote: post #63
vertex-four wrote: post #12

Earlier quoted context omitted.

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…

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.

It's possible to stop too soon though.

Re: Forth implemented in Rust trait system

#68

Post by mikepurvis »

ImprobableTruth wrote: post #66
mikepurvis wrote: post #64

Earlier quoted context omitted.

I don't think he's saying that a limit on recursion depth solves this problem. Rather, it's just a similar scenario where a real-world constraint (memory, time, whatever) comes to bear and may make a compilation fail on machine X where the identical code and environment would otherwise succeed on machine Y.

Alright, but that's not a feature, right? Stack limitations are just a natural limitation. Timeouts are something that you'd intentionally introduce, when you don't necessarily need it. And if possible, I'd like to minimize dependency on specifics of the machine as much as possible.

I dunno, I think they're pretty similar— both are an arbitrary cap that protects against exhausting a real world resource (time, memory).

In any case, the compile time evaluation would obviously still have a bunch of interesting constraints— like, probably reasonable to read in the contents of a file, but is it reasonable to make a network call? What about reading a file that's on a network share? Can you even tell the difference? That operation could also hang for reasons entirely outside of algorithmic complexity.

And of course, like a stack overflow, that's also true today; you can hang your compile by including a header from a network share that hangs.

So would it really be that bad to have the compilation hang, and just show a stack trace for the invoked-at-compile-time code when interrupted?

I don't think the halting problem is a deal breaker here.

Re: Forth implemented in Rust trait system

#69

Post by zamalek »

crazypython wrote: post #4

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,…

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.

Re: Forth implemented in Rust trait system

#70

Post by dependenttypes »

ImprobableTruth wrote: post #56
dependenttypes wrote: post #48

Earlier quoted context omitted.

> A timeout seems pretty off-putting. The idea that compilation could fail on a weaker machine just because it isn't fast enough just doesn't sit right with me. The timeout should be set based on what the user of the machine considers acceptable. Why should I have to tolerate a 2 hour wait time for a compile-time computation to finish in order for the auto-complete menu to appear on emacs just because I am using a la…

>Why should I have to tolerate a 2 hour wait time for a compile-time computation to finish in order for the auto-complete menu to appear on emacs just because I am using a laptop from 2010? I don't understand. If you aren't willing to wait that amount of time, you're simply not getting working auto-complete at all. Hell, if you can't even compile the project, I don't see how you can meaningfully work on it all. >Try…

I just realized that you said "are those that have some logic bug" rather than "are those that due to a logic bug loop forever" and also mentioned that this is true for the "vast majority of programs" in which case.. sure? If anything this is an argument that supports timeouts and can happen in both turing-complete and non-turing complete languages, plus I do not understand how popularity has anything to do with it.

> If you aren't willing to wait that amount of time, you're simply not getting working auto-complete at all

Or I am getting a working auto-complete for code that does not make the completion system to get killed by the timeout.

> Hell, if you can't even compile the project

I never mentioned not being able to compile the project.

Post reply on HN