5
$\begingroup$

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. 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.

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – Bbrk24
    Commented Oct 14 at 0:43
  • 1
    $\begingroup$ do you object to real-time tracing gc? this would likely provide better throughput without sacrificing 'predictability' $\endgroup$
    – Moonchild
    Commented Oct 14 at 3:10
  • 1
    $\begingroup$ Note that CPython primarily relies on reference counting with the cycle detecting GC being optional (though on by default). PyPy relies only on GC. There are quite a few programs for which the distinction matters in practice. $\endgroup$
    – MisterMiyagi
    Commented Oct 14 at 5:51
  • 1
    $\begingroup$ 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) $\endgroup$
    – apropos
    Commented Oct 14 at 21:07

1 Answer 1

Reset to default
2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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