<p><strong>What are some alternatives to tracing GC for dynamically-typed languages?</strong></p>
<p>I've been interested in dynamically typed languages with predictable behavior since learning about <a href="https://man.netbsd.org/lua.4" rel="noreferrer">lua in the NetBSD kernel</a>. AFAICT, NetBSD's lua interpreter was intended just to prototype drivers. But it does make me wonder how much of an operating system could reasonably be implemented in a dynamically typed language (without using special hardware like a lisp machine).</p>
<p>I'm aware of essentially three or four mainstream memory management strategies for dynamically typed languages:</p>
<ol>
<li>no memory management (e.g. Forth)</li>
<li>a closed type system with strings and aggregates of strings (e.g. Awk, Bash, Perl 4)</li>
<li>reference counts and no cycle detection (e.g. Perl 5)</li>
<li>tracing GC (e.g. Lisp, Python, Javascript)</li>
</ol>
<p>Although I guess that technically (2) could be implemented by copying strings, with reference counts, or with some combination of the two. In either case, the difference between 2 and 3 is that 2 makes circular references impossible to express.</p>
<p>I'm wondering what alternatives there are to these strategies, especially ones that would have deterministic lifetimes and no pauses.</p>
<p>One could imagine a Lisp-Rust Frankenstein that has lifetimes as the sole component of its type system, although I'm not sure what the details would look like (and whether this would violate the spirit of a dynamically typed language).</p>
<p>One could also imagine a language <a href="https://www.newlisp.org/MemoryManagement.html" rel="noreferrer">that copies all the time</a>.</p>

<memory-management><dynamic-typing>
Alternatives to tracing GC for dynamically-typed languages
CC BY-SA 4.0
2024-10-14T00:43:35.127Z
It is possible to add cycle detection on top of RC without having to do a full "stop the world" trace. I believe PHP does this; see Bacon and Rajan's 2001 paper for an example, though I'm sure there have been other versions of this.
Bbrk24
CC BY-SA 4.0
2024-10-14T03:10:46.743Z
do you object to real-time tracing gc?  this would likely provide better throughput without sacrificing 'predictability'
Moonchild
CC BY-SA 4.0
2024-10-14T05:51:16.173Z
Note that CPython primarily relies on reference counting with the cycle detecting GC being optional (though on by default). [PyPy relies only on GC](https://doc.pypy.org/en/latest/cpython_differences.html#differences-related-to-garbage-collection-strategies). There are quite a few programs for which the distinction matters in practice.
MisterMiyagi
CC BY-SA 4.0
2024-10-14T21:07:20.213Z
I am very curious: could you talk a little bit more about why you're interested in dynamically typed languages in particular? I haven't heard of memory management approaches differing fundamentally by dynamic vs. static typing before... (probably b/c I am only familiar with the details of statically typed languages)
apropos
<p>I won't comment on what a bad idea it would be to write an OS in a dynamically typed language, but...</p>
<p>In the past I have used reference counting with immutable references, which implies that an object can only refer to objects that were constructed earlier.  The reference graph is therefore acyclic, and no cycle finding is necessary.</p>
<p>You can still make recursive data structures, using getters and Y-combinator-like techniques.</p>

CC BY-SA 4.0
2024-10-15T21:45:42.963Z
2024-10-15T21:45:42.963Z
Matt Timmermans
# Alternatives to tracing GC for dynamically-typed languages
Posted by: username_0 on 2024-10-14
**What are some alternatives to tracing GC for dynamically-typed languages?**

I've been interested in dynamically typed languages with predictable behavior since learning about [lua in the NetBSD kernel](https://man.netbsd.org/lua.4). AFAICT, NetBSD's lua interpreter was intended just to prototype drivers. But it does make me wonder how much of an operating system could reasonably be implemented in a dynamically typed language (without using special hardware like a lisp machine).

I'm aware of essentially three or four mainstream memory management strategies for dynamically typed languages:

1. no memory management (e.g. Forth)
2. a closed type system with strings and aggregates of strings (e.g. Awk, Bash, Perl 4)
3. reference counts and no cycle detection (e.g. Perl 5)
4. tracing GC (e.g. Lisp, Python, Javascript)

Although I guess that technically (2) could be implemented by copying strings, with reference counts, or with some combination of the two. In either case, the difference between 2 and 3 is that 2 makes circular references impossible to express.

I'm wondering what alternatives there are to these strategies, especially ones that would have deterministic lifetimes and no pauses.

One could imagine a Lisp-Rust Frankenstein that has lifetimes as the sole component of its type system, although I'm not sure what the details would look like (and whether this would violate the spirit of a dynamically typed language).

One could also imagine a language [that copies all the time](https://www.newlisp.org/MemoryManagement.html).
**Tags:** memory-management dynamic-typing
> **Comments:**
> **username_1**: It is possible to add cycle detection on top of RC without having to do a full "stop the world" trace. I believe PHP does this; see Bacon and Rajan's 2001 paper for an example, though I'm sure there have been other versions of this.  
> **username_2**: do you object to real-time tracing gc?  this would likely provide better throughput without sacrificing 'predictability'  
> **username_3**: Note that CPython primarily relies on reference counting with the cycle detecting GC being optional (though on by default). [PyPy relies only on GC](https://doc.pypy.org/en/latest/cpython_differences.html#differences-related-to-garbage-collection-strategies). There are quite a few programs for which the distinction matters in practice.  
> **username_4**: I am very curious: could you talk a little bit more about why you're interested in dynamically typed languages in particular? I haven't heard of memory management approaches differing fundamentally by dynamic vs. static typing before... (probably b/c I am only familiar with the details of statically typed languages)  
---
## 1 answers
### Answer by username_5 on 2024-10-15. Score: 2
I won't comment on what a bad idea it would be to write an OS in a dynamically typed language, but...

In the past I have used reference counting with immutable references, which implies that an object can only refer to objects that were constructed earlier. The reference graph is therefore acyclic, and no cycle finding is necessary.

You can still make recursive data structures, using getters and Y-combinator-like techniques.
---
