4 ms·
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,
by openasocket 10y ago
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.
- amelius 10y agoHow about closures? Don't they allow cycles to be formed?
- agentgt 10y agoI 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?
- pklausler 10y agoIn Haskell, data are immutable and yet cyclic structures are possible. allOnes = 1 : allOnes
- openasocket 10y agoThis is possible in Haskell because it allows for lazy evaluation. In a strict language, immutability means you can't form cycles.
- pklausler 10y agoWhile 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;
- openasocket 10y agoHaha, 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.
- pklausler 10y agoThunks don't get repeatedly evaluated, sorry. Just once at most.
- dfox 10y agoFor 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.
- arethuza 10y agoCan't rplaca rplacd and setf destructively modify list structures? https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node150.html https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node150.html