<p>Awhile back I wrote a Rust implementation of the Monkey programming language by Thorsten Ball (<a href="https://monkeylang.org/" rel="nofollow noreferrer">https://monkeylang.org/</a>).  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.</p>
<p>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.</p>
<p>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.</p>
<p>This question is very similar to <a href="https://langdev.stackexchange.com/questions/2970/creating-a-new-language-with-rust-without-garbage-collection">Creating a new language with Rust without Garbage Collection?</a> 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 <a href="https://langdev.stackexchange.com/questions/3588/when-do-functional-programming-languages-need-advanced-garbage-collection">When do functional programming languages need advanced garbage collection?</a>.</p>

<functional-programming><rust><garbage-collection><lambda-calculus>
Does a Rust implementation of the Monkey programming language require a garbage collector?
CC BY-SA 4.0
2024-03-29T19:59:38.540Z
Given `fn f(x) { fn(y) { y } } ; f(fn(z) { a + b })` there seems no obvious way to free the argument closure without some sort of collection strategy. Is that what you’re looking for (i.e. a code example), or is it more about Rust implementation strategies? Writing in Rust or not doesn’t make a huge difference to what the language requires in order not to leak memory, but the lifetimes you give may highlight where it can be happening.
Michael Homer
CC BY-SA 4.0
2024-03-30T01:52:04.750Z
The properties of the language of implementation (Rust) don't really matter here at all (per the discussion you linked). And I think the rest of your question is answered by the second discussion you linked - you need a garbage collector if you allocate anything on the heap (via cyclic references, indirection, etc). If Monkey does that, then Monkey needs a garbage collector.
apropos
CC BY-SA 4.0
2024-03-30T09:45:00.097Z
Does this answer your question? [Does using Rust eliminate the need to implement garbage collection in a language?](https://langdev.stackexchange.com/questions/2970/does-using-rust-eliminate-the-need-to-implement-garbage-collection-in-a-language)
чистов_n
CC BY-SA 4.0
2024-03-30T12:13:17.380Z
I suspect you were deep-copying all values where necessary to maintain uniqueness.  This would not be possible when implementing in a language with mutation.  Rust makes it easy to deep-copy structures where the equivalent code in a sensible language would share them.
Moonchild
CC BY-SA 4.0
2024-04-11T19:40:42.340Z
Yeah, so the thing to look for is probably when the language is extended to support mutation and pass by reference for Array and Map types rather than just deep copying (and indeed I internalized that deep copying is "easy" and "often cheaper than you think" when writing rust).
lamont
<p>This will depend on your implementation strategy, but anything that is heap-allocated needs to be freed <em>somewhere</em> 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.</p>
<p>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.</p>
<p>Consider the simple program:</p>
<pre class="lang-none prettyprint-override"><code>fn g(x) {
  1
}
fn f(a) {
  g([a, &quot;end&quot;])
}
f(&quot;start&quot;)
</code></pre>
<p>The array is created inside an invocation of <code>f</code>, immediately given to <code>g</code>, and then never touched again. You could similarly slot in a closure or hash map. Naively:</p>
<ul>
<li>It can't be freed inside <code>g</code>, because that doesn't know that nowhere else is using it.</li>
<li>It can't be freed inside <code>f</code>, because <code>g</code> could have returned it and that would then be the return value of <code>f</code>.</li>
<li>It can't be freed at the top level, because that doesn't even know about it.</li>
</ul>
<p>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.</p>
<p>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.</p>
<p>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.</p>

CC BY-SA 4.0
2024-03-29T22:35:02.993Z
2024-03-29T22:35:02.993Z
Michael Homer
<p>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.</p>
<p>If all your test programs are small, simple, and short-lived, you will never know the difference.</p>
<p>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.</p>
<p>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.</p>

CC BY-SA 4.0
2024-03-31T16:17:37.607Z
2024-03-31T16:17:37.607Z
Jörg W Mittag
CC BY-SA 4.0
2024-03-31T19:07:27.663Z
This is true but not very useful for programming language implementation; typically, the implementer of a language does not know in advance the complete set of programs that will be written in that language. If the language is designed for short-lived scripts which don't allocate much memory then this could be a consideration, but Monkey doesn't seem to be that. It seems to be meant as a toy or for educational use, in which case perhaps one should decide whether to implement garbage collection if it would be fun or informative to do so, rather than based on the intended use of it.
kaya3
# Does a Rust implementation of the Monkey programming language require a garbage collector?
Posted by: username_0 on 2024-03-29
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?](https://langdev.stackexchange.com/questions/2970/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?](https://langdev.stackexchange.com/questions/3588/when-do-functional-programming-languages-need-advanced-garbage-collection).
**Tags:** functional-programming rust garbage-collection lambda-calculus
> **Comments:**
> **username_1**: Given `fn f(x) { fn(y) { y } } ; f(fn(z) { a + b })` there seems no obvious way to free the argument closure without some sort of collection strategy. Is that what you’re looking for (i.e. a code example), or is it more about Rust implementation strategies? Writing in Rust or not doesn’t make a huge difference to what the language requires in order not to leak memory, but the lifetimes you give may highlight where it can be happening.  
> **username_2**: The properties of the language of implementation (Rust) don't really matter here at all (per the discussion you linked). And I think the rest of your question is answered by the second discussion you linked - you need a garbage collector if you allocate anything on the heap (via cyclic references, indirection, etc). If Monkey does that, then Monkey needs a garbage collector.  
> **username_3**: Does this answer your question? [Does using Rust eliminate the need to implement garbage collection in a language?](https://langdev.stackexchange.com/questions/2970/does-using-rust-eliminate-the-need-to-implement-garbage-collection-in-a-language)  
> **username_4**: I suspect you were deep-copying all values where necessary to maintain uniqueness.  This would not be possible when implementing in a language with mutation.  Rust makes it easy to deep-copy structures where the equivalent code in a sensible language would share them.  
> **username_0**: Yeah, so the thing to look for is probably when the language is extended to support mutation and pass by reference for Array and Map types rather than just deep copying (and indeed I internalized that deep copying is "easy" and "often cheaper than you think" when writing rust).  
---
## 2 answers
### Answer by username_1 on 2024-03-29. Score: 7
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 by username_5 on 2024-03-31. Score: 3
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.
> **Comments:**
> **username_6** (2024-03-31): This is true but not very useful for programming language implementation; typically, the implementer of a language does not know in advance the complete set of programs that will be written in that language. If the language is designed for short-lived scripts which don't allocate much memory then this could be a consideration, but Monkey doesn't seem to be that. It seems to be meant as a toy or for educational use, in which case perhaps one should decide whether to implement garbage collection if it would be fun or informative to do so, rather than based on the intended use of it.  
---
