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

51–60 of 91 posts

Re: Forth implemented in Rust trait system

#51

Post by samatman »

saagarjha wrote: post #34
samatman wrote: post #22

Earlier quoted context omitted.

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…

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

Re: Forth implemented in Rust trait system

#52

Post by jfkebwjsbx »

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…

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.

Re: Forth implemented in Rust trait system

#54

Post by saagarjha »

jfkebwjsbx wrote: post #52
saagarjha wrote: post #29

Earlier quoted context omitted.

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…

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.

Re: Forth implemented in Rust trait system

#55

Post by saagarjha »

garmaine wrote: post #47
saagarjha wrote: post #46

Earlier quoted context omitted.

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…

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

Re: Forth implemented in Rust trait system

#56

Post by ImprobableTruth »

dependenttypes wrote: post #48
ImprobableTruth wrote: post #43

Earlier quoted context omitted.

>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. I'm not sure how realistic that actually is. Besides certain party tricks like encoding the ackermann functino using primitive recursion, I haven't actually seen anything like that. From my experience the vast majority of programs that don't finish in a reasonable amount of…

> 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 prolog then (or something similar) and write something of the form sha512(X) = 0 this will initiate a brute-force search that will last essentially forever.

This is literally just another nonsensical party trick. I'm talking about something that someone might actually want to use, not contrived examples that really don't matter at all. I don't care to consider imaginary people that intentionally brick their programs.

Re: Forth implemented in Rust trait system

#57

Post by jfkebwjsbx »

saagarjha wrote: post #54
jfkebwjsbx wrote: post #52

Earlier quoted context omitted.

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 :)

Re: Forth implemented in Rust trait system

#58

Post by [deleted] »

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

[deleted]

Re: Forth implemented in Rust trait system

#59

Post by dllthomas »

qppo wrote: post #45
ImprobableTruth wrote: post #43

Earlier quoted context omitted.

>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. I'm not sure how realistic that actually is. Besides certain party tricks like encoding the ackermann functino using primitive recursion, I haven't actually seen anything like that. From my experience the vast majority of programs that don't finish in a reasonable amount of…

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

Or just instruction count. Although in either case, while we are now machine agnostic (with some reasonable assumptions about the design) changing optimization flags that a build is running under might make it fail.

Re: Forth implemented in Rust trait system

#60

Post by a1369209993 »

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

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.

Post reply on HN