News for hackers. Stuff that matters.
Re:Bone Lisp – Lisp Without Garbage Collection by johnhattan on Tuesday June 07, 2016 @02:19PM (#11856492)
As someone who hasn't dealt with Lisp since the 1980's, help me out here. Immutable structures and Lisp seems to be incompatible, as Lisp's lists are about the most mutable things you'll ever see.

If, for example, I want to put a value into the middle of a list, would I be doing something akin to. . .

MyList = MyList.firstHalf + NewValue + MyList.secondHalf?

And how doesn't this become a horrible bottleneck?

Re:Bone Lisp – Lisp Without Garbage Collection by openasocket on Tuesday June 07, 2016 @02:58PM (#11856834)
You can represent the list as a zipper data structure[1]. The idea is to represent a "cursor" pointing to some point in the list as a triple: (list of points before, point at current position, list of points after). So a zipper for an arbitrary list "xs" pointing to the beginning would be (() (car xs) (cdr xs)). There are some things you can do to handle the case with empty lists, which I'll leave to the reader :).

Given a zipper (as x bs) you can move the cursor right (rather, compute the zipper with the cursor one step further to the right, since we're purely functional) as ((cons x as) (car bs) (cdr bs)). You can insert a new element "y" into you current position by computing (as y (cons x bs)). If you discard the old version of the zipper every time you move or insert, this will use the same amount of memory as just storing the list, and you get insertions in O(N) time and O(1) memory. There's a whole field devoted to making data structures like this for purely functional languages, and this zipper concept extends itself rather naturally to trees.

[1]https://en.wikipedia.org/wiki/Zipper_%28data_structure%29

Re:Bone Lisp – Lisp Without Garbage Collection by outworlder on Tuesday June 07, 2016 @02:48PM (#11856755)
They are not necessarily incompatible. Historically, Lisp pairs are mutable, but that doesn't have to be the case. See Clojure, it is Lisp-like, with most data structures immutable.

Your example is not possible in an immutable list. Also note that this reassigning of variables is a red flag even in standard Lisps. In fact, variables are not that common. The most common way of referencing something for later usage is the let form, which already creates new "variables" anyway. Just eliminate ways to reassign them (setf?).

What you would do is to create a new list containing the elements you want. You may or may not want to give it a new name afterwards. Most likely, you'll use as it is and pass on to some other function.

I can't comment on this particular implementation. But it does not necessarily have to be a bottleneck. In fact, by having immutable data structures, that means that you can share data like crazy, without fear of anything being replaced where it should not. All sorts of optimizations are enabled that wouldn't be possible otherwise. If this implementation uses them, it's another matter entirely. No idea.

Re:Bone Lisp – Lisp Without Garbage Collection by rrradical on Tuesday June 07, 2016 @02:46PM (#11856736)
Generally you build the new list using the tail of the old list (which is unchanged), your inserted value, and each of the values in front inserted onto that. So, immutability is preserved. Any existing references will not see their values changed. And the new references will share some memory with the old ones (how much depends on where in the list the value was inserted).

You can learn more in Okasaki's great book: http://www.amazon.com/Purely-Functional-Structures-Chris-Oka...

Re:Bone Lisp – Lisp Without Garbage Collection by _ph_ on Tuesday June 07, 2016 @04:55PM (#11857736)
Actually Common Lisp and Scheme have a clear distinction between mutating and non-mutating list functions. They even have a naming schema to distinguish between, and most books focus on the non-mutating, in Common Lisp speak "nondestructive" list functions. Functions like append, remove do not mutate the input list, but (partially) new lists, which can share sublists with the input lists. For example (append a b) returns a list which contains a copy of a and the original b.
Re:Bone Lisp – Lisp Without Garbage Collection by bch on Tuesday June 07, 2016 @02:37PM (#11856664)
I wonder if you could use ropes[0].

[0] https://en.wikipedia.org/wiki/Rope_%28data_structure%29

Re:Bone Lisp – Lisp Without Garbage Collection by mwfunk on Tuesday June 07, 2016 @02:47PM (#11856739)
I may be misreading this, but isn't that an example of lists being immutable rather than pervasive mutability?
Re:Bone Lisp – Lisp Without Garbage Collection by sklogic on Tuesday June 07, 2016 @02:44PM (#11856719)
Do not put a value into a middle of a list.

Read Chris Okasaki, "Purely functional data structures" for better options.

Re:Bone Lisp – Lisp Without Garbage Collection by gosub on Tuesday June 07, 2016 @02:50PM (#11856772)
structural sharing is what clojure does. But you can have immutable data structures in old lisps if you only use cons, car and cdr, avoiding set-car and set-cdr.