Hacker News Reader

Comment by amelius | Hacker News Reader

It would be cool if the garbage collector could be written in the language itself.

In this case a garbage collector is unnecessary. In this Lisp, list structures are immutable, which means it is impossible to create a list with a cycle. Thus, the interpreter can use basic reference counting without fear that anything will leak.

In Haskell, data are immutable and yet cyclic structures are possible.

  allOnes = 1 : allOnes

This is possible in Haskell because it allows for lazy evaluation. In a strict language, immutability means you can't form cycles.

While non-strict evaluation helps with forming cyclic structures in general, in this specific example it is not required. You just need a language that allows names to appear in their bindings, such as in C:

  struct node { int x; struct node *next; } allOnesList = { 1, &allOnesList }, *allOnes = &allOnesList;

For normal lisp implementations, allowing names to appear in their own definitions requires lexical environment frame to be mutable, which breaks the assumption that all notionally on-heap objects are immutable.

This observation is somewhat relevant to the weird semantics of "lexical" scoping in Python, because the obvious semantics would cause cycle between frame object and function defined in it's scope.

Haha, I hadn't thought of that! That ability to create self-referential data is the main factor. That isn't really possible in lisp without some sort of letrec function, which this lisp shouldn't support. You would also have to watch out for recursive function definitions. Usually, the function body will just contain the symbol that refers to the function, which conceptually is similar to a straight pointer to the function, and someone might try to optimize it that way.

In fact, with more thought, I realized the lazy evaluation is actually orthogonal to forming cyclic data. The "allOnes = 1 : allOnes" line doesn't necessarily form a cycle (depending on the interpreter/compiler, I imagine ghc and any other sensible implementation will form a cycle). Naively, this will just create a thunk which will get repeatedly evaluated, generating a long list of ones.

EDIT: Nevermind, you're right.

Thunks don't get repeatedly evaluated, sorry. Just once at most.

Can't rplaca rplacd and setf destructively modify list structures?

https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node150.html

How about closures? Don't they allow cycles to be formed?

I think because everything is immutable and because lexical scoping I can't figure how this would happen other than a direct cycle which I think the reference counting might be able to figure out.

I am curious as well though. Maybe you could show an example?

It's been done as other comments pointed out. But the fact that you can do it is mildly interesting, isn't it? It's a sort of bootstrapping problem.

Obviously you can't trigger full GC in your GC code. So you have to write GC code in such a way that it won't trigger GC or, in some cases, very limited mode of GC that you know is safe to perform at that point. It is trickier in languages that implicitly allocates. Traditionally, Lisp programmers are pretty aware of what operation would allocate and good at avoiding them. Plus, an implementation often provide a primitive to turn off GC in certain regions. Another approach is to design a subset of language with guaranteed safety properties and implement the core part of GC with it.

I've seen this in various Lisp implementations. And the Boehm collector is written in C for C.

Reply on news.ycombinator.com