Hacker News Reader

Comment by jupp0r | Hacker News Reader

> tsc depends on shared mutability and has a cyclical mutable reference. Rust is designed to prevent this behavior. Having two references to the same data (shared mutability) is undefined behavior in Rust.

This problem has numerous solutions in Rust - (A)Rc, RefCell etc. I don't understand how this caused the author of the article to stop considering Rust.

View on HN

Non-GC languages are bad in general at handling cyclical references (mutable or not), and Rust is especially ill suited for it because of the borrow checker. For example should an arbitrary reference in tsc become an rc::Rc or an rc::Weak? You have to tease out the implicit ownership model and one may not even exist.

tsc was designed expecting GC and it makes perfect sense to port it to another fast GC language.

I'm not a Rust fanboy (in fact, I rather despise the RESF, especially given Rust's mediocre tooling), but: I think that "You have to tease out the implicit ownership model and one may not even exist" suggests a problem with the program itself.

I can't think of any reason why a program must have an ill-formed ownership model (unlike, say, the fact that many interesting programs must have an embedded dynamic type system (tagged unions etc) to do their thing).

Now. The Rust language and existing tooling doesn't give you any help in figuring out the ownership model, but I can easily imagine a language and tools that would help with that.

This isn't meant to refute anything you've said (you said "[existing] non-GC languages are bad in general" not that non-GC languages cannot be good) - just add clarity.

A program doesn't have to have an ill-formed ownership model. But if it does and you're trying to translate from one language to another, you should probably pick the language that makes the job easier.

It reminds me of a programming assignment I had 20 years ago. We had to take our teacher's old FORTRAN program and "convert" it to Java or C++. I knew both equally well at the time - and I picked C++ because it had goto whereas Java didn't.

This meant that I didn't really have to unravel the meaning of the program. Whereas with Java, I would have to.

Speaking as someone who has written non-trivial compilers in both Rust and Go...

Compilers tend to use a bit thornier data structures and graphs than you might see in other realms. It is very convenient to just represent these graphs as objects connected by pointers, and know that you don't have to worry about objects that become unreachable.

For example, the values in an SSA-based IR are all full of pointers to other values. Each value represents the computation to produce that value, like "x12 / 4". A strength-reduction pass goes in and mutates this node, replacing it with "x12 >> 2" (if such a change is valid). It knows the change is valid because it follows pointers from the node to its inputs. The change is available to all upstream values immediately because it is mutated. These changes may make other values unreachable, at which point, you don't care about them. You only care about the values which are reachable from computations with side effects. These nodes definitely have cycles and IMO, the notion of weak references between them doesn't make sense.

I'm sure there's a way to do that in Rust. Please, nobody try to explain how. I could figure it out. The thing is... it's not obvious how to do it in Rust, and figuring out how to "explain ownership to the Rust compiler" without creating Rc<RefCell<T>> cycle leaks is a non-trivial task that sucks away time I could be spending writing the compiler.

This reminds me of a paper I saw go by years back about writing a compiler in Haskell. Pure Haskell code doesn't let you mutate objects and doesn't let you do pointer comparisons, so it creates problems if you're trying to implement an algorithm which is conceptually pure (at a high level, a function with inputs and outputs) but where you're taking the implementation from a paper which constructs the output iteratively, piece by piece. The problem is that your data structures have to be annotated to show which parts are mutable (IORef, STRef, or TVar), but "which parts are mutable" may have a different answer depending on whether you are inside some function transforming or constructing a data structure.

It was obvious to me, reading the paper, that while I love functional purity, and functional purity solves all sorts of problems and makes it easier to write code in general, it sometimes gets in the way of getting shit done. The same is true of Rust's notion of ownership... super useful when it lets me write fast, efficient code without having to think about ownership (when it just works and gets out of the way), and super annoying when you have to figure out how to explain your program to Rust.

Thank you for explaining - now that you've pointed it out, I can see that this is just another form of the "graphs are hard in Rust" problem that I've encountered before.

However, I still stand by my point - Rust might be bad at graphs, but I believe that a well-designed language with a borrow checker (maybe something closer to Lobster, which automatically inserts RC cells when you try to multiply mutable borrow[1] - something obviously more correct than what Rust does, I'm not sure how they messed that one up) wouldn't necessarily have to be.

[1] https://aardappel.github.io/lobster/memory_management.html

The problem is that Rc<> is not replacement for GC, in GC language you just don't care about having multiple mutable references at all because it's mem-safe (so you don't need to panic). The only thing you can get is concurrency issue but that's often fine for isolated algorithms (where you do mutex at the top and don't care from there or you just send the whole thing to the worker using channel). Rust is placing restrictions on your code not because it's bad code but because it cannot prove it's safe. Yeah so you can mark it as unsafe but you can also switch to a different language and have a happy rest of life.

Do you mean a Rust Rc<> or a generic "borrow-checked language" Rc<>? In the former case, yes, I absolutely agree that Rust is not ideal. However, my argument is about a theoretical language with a borrow-checker, in which case - why isn't something like Lobster sufficient, which automatically detects when you have multiple owners and inserts reference counting under the hood?

https://aardappel.github.io/lobster/memory_management.html

Among other things, the article you linked explicitly mentions that it does not solve one of the major problems with using Rc<T>, which is that it does not handle cycles.

It sounds like a more ergonomic system that has the same technical shortcomings.

yeah I mean rust Rc<>, I don't have experience with lobster, does it allow mutation from multiple places or does it panic just like rust?

The latter - although as a sibling commentator pointed out, it doesn't do cycles - so it's better, but not a panacea.

Ah, ok, having cycles is another problem, also hard, but my point was about multiple mutable references which is not a safety problem if you have GC. You only get race conditions.

And I think it could/should work also with Rc<> but for some reason, rust authors decided it's important to write everything as if it was multi-threaded even if it's single-threaded now (so it can be easily turned to multi-threaded later).

And that's cool but it adds a lot of burden to developers. I am probably missing something, there is likely a good reason for this, as always, but it doesn't change the point, rust is super-complicated for hobby stuff and you have to think about irrelevant things, hence for me, it is low-level language (with generics and macros and very cool builtin unit testing but it's still low-level)

And by irrelevant I don't mean mem-safety, that IS important for me, I rather mean worrying about race-conditions in a single-threaded code :)

If your program is an interpreter, then I think the ownership model is going to be dominated by the program being interpreted, not the intepreter itself... That is, has to be general enough to interpret any program, and many of those programs will have cyclic data structures.

TSC is not an interpreter, but its type system is Turing complete, so I wouldn't be surprised if it has some similar issues.

> I rather despise the RESF, especially given Rust's mediocre tooling

Which tooling are you talking about?

Copying from a previous comment[1]:

The Rust compiler is both dog-slow and massive (both from a source and binaries perspective), and doesn't have a working incremental compilation mode yet, or support in-process hot-patching. There's no Rust REPL (hacks like papyrus don't count). Poor structural editing support. Integration with various editors/IDEs is lacking (e.g. there's no support for reporting possible performance issues with code constructs in any editor that I'm aware of, nor is there in-editor per-function disassembly or LLVM IR inspection, or borrow-checker lifetime annotation, no extract-function refactoring).

[1] https://news.ycombinator.com/item?id=29925783

The compiler is relatively fast for recompilation but you are right, this is a problem that's actively being worked on.

> support in-process hot-patching

I assume that we are comparing this with say C++ compilers. I think that Visual Studio added this recently but idk if saying this is a valid criticism of the compiler.

> There's no Rust REPL

Are you comparing it with C++ compilers?

The Rust tooling is so much better than C++ tooling that it's not even funny. You are right, there are places where this could be improved but just cargo makes my life so so so much easier than any other package manager.

> The compiler is relatively fast for recompilation

Relative to Rust when doing a cold-compile, maybe, but certainly not relative to other languages like C, sane C++, Go, or Common Lisp.

I'm comparing Rust tooling with existing tooling in other languages in general, that is feasible to implement.

Common Lisp has multiple compilers (SBCL, Allegro, Clasp) that compile code nearly instantly (within a second for my modest 2kloc codebases, and individual functions in milliseconds), have REPLs (that also do native-code compilation under the hood using the compiler proper - no hacks), and support hotpatching.

Visual Studio implements in-process hot-patching, too, so between C++'s highly static nature, and the fact that SBCL is run by a tiny group of unpaid contributors, there's no reason for the Rust compiler to not have it.

Meanwhile, GHC (compiling Haskell, a statically-typed language) has a REPL, so it's clear that being dynamically-typed is not a requirement.

From a user's perspective, having either long compilation times or lacking a REPL is OK, but not having either is unacceptable.

Having a good package manager is necessary for having good tooling, but not sufficient.

Rust does have a third-party `Gc` type (which used to be in the stdlib).

Is that the one where you need to derive() for every struct you want to use and which is, in general, not compatible with the rest of rust ecosystem?

I honestly like the explicit weak ref model and it’s usually trivial (child objects are strong references, parents and siblings are weak), and rust has Gc as a last resort.

But if the author’s more familiar with Go, performance in Go is likely good enough

While I hate Go and love Rust, there is also the issue that RefCell/Gc/Rc are very different in terms of how expensive a memory allocation is compared to node. Historically there were very similar problems in trying to write C++ like one would write Java. Memory allocators today are much better and closer to GC languages, but I suspect it will still be more expensive for very allocation heavy code.

One way you could get this to work at the cost of some safety (depending on how you do it) would be to use arena style allocation. Obviously there are ways to do this safely in Rust, but it is probably easier to do it unsafely for a port.

However, if you just use a high performance language with a GC like Go/C#/Java, the port will be easier and you won't have to worry about doing too many allocations.

I think the point is valid. As a rust beginner I tried to make a graph data structure and it was difficult. Using RefCell is not very nice because it moves the problem from compile time to runtime and you still can’t mutate the same data structure more than once at the same time.

Rust encourages you to use an adjacent list/matrix for your graph representation, which is preferable almost all of the time for graph algorithms. It's a little unwieldy if the graph needs to be mutable during the core algorithms, but almost all algorithms in practice assume it will be stable.

This is interesting but I don't know Rust. Presumably your graph data structure grows dynamically, meaning you have to add nodes at runtime. When. you say you can't mutate the same data structure more than once at runtime, what does it mean? That you can't set both a parent and a child pointer in the same function, or what?

I’m very far from being a rust expert but it was difficult to build a bi-directional graph because it’s difficult to connect the nodes together. A simple recursive algorithm will not work. I ended up using a crate.

I found the following article interesting on the topic : https://aminb.gitbooks.io/rust-for-c/content/graphs/

It shouldn't be difficult:

1. You have a graph struct that has ownership of all nodes (in Rc containers).

2. Nodes have Weak references to connected nodes

In the case of RefCell, when you begin modifying its data, you’re not allowed to begin modifying its data a second time without declaring “I’m done” with the first modification. This makes doing several modifications in different places that are interspersed with each other tricky because it’s hard to reason about when each spot is actually done so that a modification can be performed elsewhere. (If your program is single threaded it’s possible you don’t even care about mutation happening in multiple places, but Rust cares because in general Rust programs need not be single threaded.)

Rust doesn't allow you to relax mutation constraints for a single-threaded program?

Reply on news.ycombinator.com