6
$\begingroup$

I am new to language development. I am aware of Rust's ownership model that builds programs in a way that does not need garbage collection.

So if I am to build a new programming language using safe Rust exclusively, will it be that the programming language will not need for me to implement garbage collection?

Here is the context;

I want to create an interpreted language. I have decided to either use Nim or Rust.

I love Nim's syntax and find it fun to work with. I also hear interesting things concerning Rust, especially regarding its safety features.

So my questions are;

  1. Does using Rust eliminate the need to implement garbage collection in a language? If not, what other benefits do you think one can get by using Rust for working on an interpreted language?

  2. If I am to use Nim, what exactly will I be losing (or gaining) over rust?

$\endgroup$
6
  • 19
    $\begingroup$ If you use Rust to implement a different language, then the fact that Rust - the host language - does not use a GC, does not imply anything about whether the language you are implementing will have a GC or not. That's a language design decision for you, the language designer, to make. $\endgroup$
    – kaya3
    Sep 27, 2023 at 18:00
  • 4
    $\begingroup$ The top question here about GC is answerable, but the two labelled “my questions” are different and very broad currently. Which part of this are you looking for an answer to here? You can ask separate questions for different topics, although the broad ones would need to be dialed in a bit more for people to be able to give you good answers. $\endgroup$
    – Michael Homer
    Sep 27, 2023 at 18:08
  • 1
    $\begingroup$ Welcome to PLDI! One thing worth noting is that the things you hear about Rust regarding safety are typically relative to lower level languages like C/C++. Nim is likely to be similar in how safe it is (I don't know much about it tho). $\endgroup$ Sep 27, 2023 at 18:09
  • 2
    $\begingroup$ Nim has a GC (you can choose from multiple GCs, actually, or no GC if you want), so if you make an interpreter in Nim and don't do any unsafe stuff, you shouldn't need to implement garbage collection yourself. I'm not sure why you mentioned Nim and Rust specifically, because any language that has either a GC or borrow checking like Rust can be used to implement an interpreter without requiring another GC, as long as you don't do something unsafe that the GC or borrow checker don't know about/can't handle. $\endgroup$
    – user
    Sep 27, 2023 at 18:17
  • 3
    $\begingroup$ You should think about whether your language implementation is as an interpreter or with a compiler — you didn't say, and it can make a difference. $\endgroup$
    – Erik Eidt
    Sep 27, 2023 at 19:01

4 Answers 4

26
$\begingroup$

Does using Rust eliminate the need to implement garbage collection in a language?

No. Rust’s memory management relies on semantic properties of the language that are carefully guaranteed. Unless your language is implemented as an embedded domain-specific language within Rust (that is, it is “just” a Rust library, perhaps with some fancy macros to provide sugar), you cannot easily inherit these guarantees from the host language, so you will still have to worry about your language’s memory management in the usual way.

If your language is interpreted, and you wish to remain within the safe subset of Rust, you will somehow have to prove to the borrow checker that values of your language have well-defined lifetimes. Depending on the semantics of your language, this may be tricky to do. On the other hand, if your language is compiled, Rust’s memory management has little impact on the memory and lifetime semantics of your language, as you are free to produce whatever code you’d like.

If your language is intended to support fully automatic memory management without explicit lifetimes, then an interpreter is likely to be easier to implement in a garbage collected language, as it is possible to reuse the garbage collector of the host language in that case. However, again, if your language is compiled, the memory management of the host language is essentially irrelevant.

If not what other benefits do u think one can get by using Rust for working on an interpreted language. […] If I am to use Nim what exactly will I be missing out (or benefiting) on if I choose to use Nim or Rust to implement a language.

These questions are not on-topic on this site, as they are extremely broad and in some cases essentially come down to opinion. Also, more broadly, it’s best to only ask one question per question on Stack Exchange sites. See our Help Center for what types of questions you can ask here.

$\endgroup$
5
  • $\begingroup$ Thank you very much. This was helpful. $\endgroup$
    – M4X_
    Sep 27, 2023 at 18:19
  • $\begingroup$ In short (and assuming that my own understanding is correct), simple data types like integers will be deallocated once the the semantics determine they will no longer be used, while more complex types like strings are garbage collected. It is this semantic analysis, as distinct from a simple consideration of scope etc., which distinguishes Rust from its ALGOL-based predecessors. $\endgroup$ Sep 28, 2023 at 7:06
  • $\begingroup$ @MarkMorganLloyd describing rust as Garbage Collected is a bit iffy. Most common understandings of garbage collection are about scanning collectors, which rust does not have. Rusts analysis falls under the same bucket as Objective C++ ARC, and RAII. Semantic lifetime analysis which is different enough to be regarded as seperate. $\endgroup$ Sep 28, 2023 at 8:48
  • $\begingroup$ @user1937198 I agree, but I was trying to to stray too far from OP's phrasing. Also I think it's fair- in the general case- to assume that implementations can use different classes of storage one of which might be heap for strings etc. $\endgroup$ Sep 28, 2023 at 8:51
  • $\begingroup$ @MarkMorganLloyd An interpreter might. Rust as it currently stands? Only one heap in the standard library. Any alternative allocation store would be a custom library. Whether the rust language recognizes the existence of heap at all is a bit iffy, boxes etc are part of alloc, not core, and running Rust with just core is a standard supported configuration, unlike say C where the standard specifies malloc will exist because the standard only specifies the full stdlib. $\endgroup$ Sep 28, 2023 at 8:56
5
$\begingroup$

No, while rust's safety model will prevent many types of memory errors like use-after-free, it does not prevent memory leaks. From the Rust book:

Rust’s memory safety guarantees make it difficult, but not impossible, to accidentally create memory that is never cleaned up (known as a memory leak). Preventing memory leaks entirely is not one of Rust’s guarantees in the same way that disallowing data races at compile time is, meaning memory leaks are memory safe in Rust. We can see that Rust allows memory leaks by using Rc and RefCell: it’s possible to create references where items refer to each other in a cycle. This creates memory leaks because the reference count of each item in the cycle will never reach 0, and the values will never be dropped.

You can trivially create a memory leak by creating a cycle with an Arc<T>/Rc<T>. Also functions like std::mem::forget are considered safe even though they may leak memory.

A language implemented only in safe rust will inherit rust's safety guarantees, but will still leak memory as that isn't one of the guarentees. If you want memory usage to stay within limits you need some system to detect leaked objects and free them (eg. a Mark and Sweep Garbage Collector)

You don't need a garbage collector though, if you are willing to accept leaks can happen and are not much of a problem. PHP for example uses only reference counting to free objects which means it will leak memory in much the same situations as rust would. If you are a language intended to be used for short scripts it may not be a huge problem.

Further reading:

$\endgroup$
2
  • $\begingroup$ PHP does not leak memory with circular references; it keeps a list of freed references, and periodically runs a specific garbage collection algorithm to detect if any lead to closed cycles. This has been enabled by default since PHP 5.3, released in 2009. See php.net/manual/en/features.gc.collecting-cycles.php $\endgroup$
    – IMSoP
    Oct 28, 2023 at 13:38
  • $\begingroup$ I would replace the "will still leak" with "may still leak": whether it leaks, or not, depends on the language implementation. A language with only strict evaluation and immutable values, for example, could use Rc/Arc with a guaranteed absence of cycles, hence not leaking. $\endgroup$ Apr 1 at 10:59
1
$\begingroup$

Does using Rust eliminate the need to implement garbage collection in a language?

No. The language in which a language is implemented has almost nothing to do with the properties of the implemented language. Rust was originally written in OCaml, for example, but OCaml is garbage collected and Rust is not.

If I am to use Nim, what exactly will I be losing (or gaining) over Rust?

As you noted, Nim is garbage collected (reference counted) and does not use an ownership system for anything other than eliding reference counts. There are some data structures that are difficult to represent in an ownership system like Rust, notably trees. If you use a tree to represent any part of your language - and you likely will - it's probable that you will run into difficulties with the borrow checker, especially starting off, or have to fall back on using Rc and Arc to form a reference-counted structure. (a possible alternative is to instead represent trees as Vecs)

Rust is descended from the ML family of languages, however, and inherited many of their features that make them nice for building languages (ML: literally "Meta Language"). The combination of Rust's struct and enum types allow for the modelling of many data structures useful for implementing a language, while its match statement allows for structurally decomposing them. These are heavily inspired by ML's data/type/datatype and match/case/of constructs.

Rust's struct is directly equivalent to Nim's object. Rust's enum has no direct equivalent. Instead, Nim has "object variants": structs that have a tag that can be matched upon to access different fields. This means that fields can be shared across variants, unlike Rust's enum, but the tag must be explicitly defined separately. This is generally a little harder to work with. Nim also does not have structural pattern matching: its case/of statement can only match upon ordinal types and strings (though, there are libraries that extend it to work structurally).

There's not a right or wrong choice, of course, and there are many examples of languages implemented in both, but hopefully that provided some exposition as to what language features make a language suitable for implementing other languages in.

$\endgroup$
4
  • $\begingroup$ "there are many examples of languages implemented in both" have people have written a lot of compilers in Nim? Actually while I'm less surprised about Rust for all the reasons you name I'd love for you to link some of the Rust examples as well. $\endgroup$ Oct 27, 2023 at 12:45
  • 2
    $\begingroup$ Yes! Here are a couple: github.com/arturo-lang/arturo, github.com/h3rald/min, github.com/calebwin/pipelines. Plus the Nim compiler itself and community libraries of a certain complexity, ex. the LLVM backend. As for Rust, there's a neatly collected (and long) list at github.com/alilleybrinker/langs-in-rust. $\endgroup$
    – apropos
    Oct 28, 2023 at 11:02
  • $\begingroup$ Thanks! This is why I love the internet :) $\endgroup$ Oct 28, 2023 at 12:22
  • $\begingroup$ Trees actually follow Rust's ownership model very nicely, because each node has exactly one owner. I think you're thinking of graphs. If you had any particular examples in mind I would be very interested to hear them. $\endgroup$ Mar 10 at 10:50
1
$\begingroup$

Rust does not provide garbage collection out of the box. But when you write a new language in Rust, the new language may require garbage collection. You can not write a Scheme interpreter without implementing a garbage collector. Whether you need a garbage collector depends on the language you want to implement. Rust does not require one, but other languages require one. And if the new language requires garbage collection, Rust's borrow semantics will not help. You have to write a garbage collector in Rust in the same way people wrote garbage collectors in C.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .