Does a Rust implementation of the Monkey programming language require a garbage collector?

Question

Awhile back I wrote a Rust implementation of the Monkey programming language by Thorsten Ball (https://monkeylang.org/). When I got done with it I was a bit surprised that I never used an Arc/Rc anywhere and didn't have a Garbage Collector and couldn't quite determine under what circumstances I'd need to build one. Being a relative novice at both Rust and language design and functional languages though I dropped that question due to being a bit mentally exhausted.

So my question is under what condition do you have to worry about Garbage Collection in the Monkey language and what kinds of tests would you have to write to exercise memory leaks in the language? Or alternatively what kinds of extensions would you need to write to the Monkey language where you would start to need a Garbage Collector? Clearly you'd need it if you were able to build circular data structures, but I actually don't know how to build those in Monkey. And for those unfamiliar with it, the language is purely functional and immutable.

I'll post more specific information about how I wrote the internal data structures in my implementation if it becomes necessary, but it pretty closely follows the go implementation in the books.

This question is very similar to Creating a new language with Rust without Garbage Collection? but I thought it was worth it to ask a concrete question about the Monkey language itself. And I think this has more to do with functional programming and language design than rust itself. I guess this question is closer to When do functional programming languages need advanced garbage collection?.

Answer 1

This will depend on your implementation strategy, but anything that is heap-allocated needs to be freed somewhere if there is not to be a memory leak. Arrays, hash maps, and closures are prime candidates here: they can't be statically-allocated, because they can depend on run-time data, they can't be stack-allocated, because they can be returned from functions, and they can't all be cleaned up with their enclosing environment, because they can be created and passed anonymously as function arguments.

You don't absolutely need garbage collection when your language is restricted enough, but you do need to deal with the allocations somewhere, and perhaps trade off time and memory against it. Which costs you're willing to pay, and when, will determine how you go about this, and the straightforward implementations lean pretty hard in opposite directions: go quick and leak some memory, or go slower and use more unleaked memory.

Consider the simple program:

fn g(x) {
  1
}
fn f(a) {
  g([a, "end"])
}
f("start")

The array is created inside an invocation of f, immediately given to g, and then never touched again. You could similarly slot in a closure or hash map. Naively:

• It can't be freed inside g, because that doesn't know that nowhere else is using it.
• It can't be freed inside f, because g could have returned it and that would then be the return value of f.
• It can't be freed at the top level, because that doesn't even know about it.

It's going to leak unless something else deals with it, which will could be reference counting or some other garbage collection, or optimisation passes that preemptively eliminate the useless allocations. In other cases where the allocations are used, something will need to be done at run time.

However, for this language there are other ways to build the interpreter without GC. For example, if you deep-copy every non-literal argument, return, and assignment value, you can free the original on your own schedule because you know it is a unique reference. In broad strokes, return values will have the lifetime of their caller's scope, arguments will have the lifetime of the callee, and local variable values will have the lifetime of the scope they're in. For a pure functional language, that is semantically ok, although it does a lot more allocation and copying work than ideal. If you don't have to deal with aliasing, this approach is always possible if you can tolerate the increased time and memory complexity.

Cyclic structures or reference identity break this strategy, as does mutable state. Some sorts of program become very expensive under it: for example, consider a recursive function processing a lengthy array one element at a time, or a deep tree of closures that must be walked every time it is passed around. There are various midpoints as well, some of which are ultimately reference-counting from a different point of view. For languages where the programs are expected to be short-lived, a memory leak isn't really a problem — the operating system is your garbage collector — and so you don't need to care much regardless.

Answer 2

The obvious and trivial answer is: you don't need any sort of memory deallocation at all if the programs you execute don't allocate more memory than you have available.

If all your test programs are small, simple, and short-lived, you will never know the difference.

In this case, your interpreter and/or the compiled code will leak memory left and right, but the OS is going to clean that up when the process exits. And if you have enough memory available, that may even be a valid implementation strategy.

For example, if you generally only run small scripts, it might be acceptable to not deal with memory deallocation at all. Just let it leak and let the OS take care of it. Likewise, if you know all the possible programs you want to run, you can try and prove that they will only ever allocate a certain amount of memory. If that amount is smaller than the memory you have, there is again no need to perform any memory deallocation.