News for hackers. Stuff that matters.
Re:Bone Lisp – Lisp Without Garbage Collection by amelius on Tuesday June 07, 2016 @08:51AM (#11854092)
It would be cool if the garbage collector could be written in the language itself.
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.
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?

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

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?

Re:Bone Lisp – Lisp Without Garbage Collection by shiro on Tuesday June 07, 2016 @02:21PM (#11856509)
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.

Re:Bone Lisp – Lisp Without Garbage Collection by treerex on Tuesday June 07, 2016 @11:46AM (#11855265)
I've seen this in various Lisp implementations. And the Boehm collector is written in C for C.