Re:Bone Lisp – Lisp Without Garbage Collection
by openasocket on Tuesday June 07, 2016 @08:56AM
(#11854115)
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.
[ Parent
| on HN ]
Re:Bone Lisp – Lisp Without Garbage Collection
by pklausler on Tuesday June 07, 2016 @11:41AM
(#11855227)
In Haskell, data are immutable and yet cyclic structures are possible.
allOnes = 1 : allOnes
Re:Bone Lisp – Lisp Without Garbage Collection
by openasocket on Tuesday June 07, 2016 @12:36PM
(#11855629)
This is possible in Haskell because it allows for lazy evaluation. In a strict language, immutability means you can't form cycles.
Re:Bone Lisp – Lisp Without Garbage Collection
by pklausler on Tuesday June 07, 2016 @12:43PM
(#11855679)
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;
Re:Bone Lisp – Lisp Without Garbage Collection
by dfox on Tuesday June 07, 2016 @01:22PM
(#11855972)
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.
Re:Bone Lisp – Lisp Without Garbage Collection
by openasocket on Tuesday June 07, 2016 @12:59PM
(#11855821)
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.
Re:Bone Lisp – Lisp Without Garbage Collection
by pklausler on Tuesday June 07, 2016 @01:06PM
(#11855868)
Thunks don't get repeatedly evaluated, sorry. Just once at most.
Re:Bone Lisp – Lisp Without Garbage Collection
by arethuza on Tuesday June 07, 2016 @12:22PM
(#11855510)
Can't rplaca rplacd and setf destructively modify list structures?
Re:Bone Lisp – Lisp Without Garbage Collection
by amelius on Tuesday June 07, 2016 @09:19AM
(#11854257)
How about closures? Don't they allow cycles to be formed?
Re:Bone Lisp – Lisp Without Garbage Collection
by agentgt on Tuesday June 07, 2016 @09:34AM
(#11854375)
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?