Hacker News Reader

Comment by xiaq | Hacker News Reader

Scheme and CL have immutable data structures, but not persistent data structures.

But the paper that introduced the term 'persistent data structure' said they already existed in Lisp and gave the example of a persistent queue built by sharing the tail of an existing one with a new head?

Doesn't have to be built-in to exist in the Lisp ecosystem.

Sorry I don't understand what that means?

A Lisp list is a persistent data structure.

A Clojure seq offers much more than that. But you can re-create it in CL, it's just not built-in.

I was replying to

> Scheme and CL have immutable data structures, but not persistent data structures.

And I said they do. You've said Clojure persistent data structure offer more. Ok, but I just said they existed in Lisp and they do.

Sort of.

First, conses are mutable so lists are persistent as long as they are used in a persistent way -- it has to be enforced through the codebase (and deps).

Second, lists big-O access/update costs are not as interesting as persistent maps and vectors.

Not built-in, but there are libraries.

But afaik most immutable, persistent data structure libraries in other lisps either (1) had poor performance or (2) were developed after clojure and borrowed from clojure.

Isn't changing the head of a Lisp lisp by referring to the same tail from a new head an example of a persistent data structure?

I think you're referring to "association lists" which definitely predate clojure and are definitely a persistent data structure and very cool in their own right. However, their performance profile is pretty poor (i.e. O(n) lookups) and are therefore rarely used in modern lisp programming anymore, to the best of my knowledge.

"Persistent" generally means something like "survives process restart and machine reboot".

Does it? I thought for data structures it was simply that it survived editing. That is, old versions are always accessible.

It's an overloaded term: in some constexts it means "survives reboots" but in this context it means something else.

Not in this context. Persistent here means "stable". It is like having a versioned database; any reads of that version are stable. Once a version is created, it cannot be written to. All further additions create newer versions, but those changes are not visible via a handle to an earlier version.

I see now that this term was introduced in a 1986 paper about versioned, immutable data structures (Making Data Structures Persistent, Driscoll, Tarjan et al).

I'm well aware of the techniques, just not the word.

Interestingly, they were aware of the connection between their work and Lisp:

"The node-copying method of Section 2 can be modified so that it is write-once except for access pointers. The main modification is to handle inverse pointers as discussed in Section 3. The write-once property is important for certain kinds of memory technology. Also, it implies that any data structure of constant bounded in-degree that can be built using the augmented LISP primitives cons, cdr, replaca, and replacd can be simulated in linear time using only the pure LISP primitives cons, car, and cdr. Thus the result sheds light on the power of purely applicative programming languages."

Or, rather, it seems they were made aware by a reviewer:

"We thank Nick Pippenger for noting the connection between write-once data structures and the power of pure LISP."

(Good old Nick didn't go as far as to point out that rplaca and rplacd can introduce cycles, which cannot be constructed with cons over existing structure.)

Sadly, no reviewer similarly piped up about "persistent" being taken already for durable storage.

Strictly speaking: yes. But whether conses (aka pairs), lists, or other derivative structures support pervasive FP in a language is probably most influenced by whether conses are mutable or not.

In Common Lisp, they are. In Scheme, they are not.

Mutable conses are useful because at least because values can be accumulated in a list from the end by retaining and mutating the tail.

However, the presence of mutable conses detracts from a language's ability to support FP, since it must be done by convention and with much copying.

I see Clojure's innovation in this area not in the fact that its lists are immutable (Scheme did this already) but in the fact that its lists are immutable and there's never a need to mutate the tail, because lazy sequences are supported throughout the language. The icing on the top of the story is that concrete lists and lazy sequences both inhabit the "Seq abstraction", and so don't require different APIs most of the time.

Of course, I'm pretty sure lazy sequences existed before CL was standardized (they're in SICP), but I can imagine how the designers would have preferred a simple, well-known tool (mutable conses) over admitting a whole other sequence abstraction. Plus, immutable conses would have been a breaking change.

So, it's not that anything that Clojure does with regard to lists couldn't have been done before, just that it wasn't -- while also being packaged in a vehicle that was wildly compelling for many other unrelated reasons.

Scheme's conses are mutable: r7rs (and the previous standards) define set-car! and set-cdr! to mutate the parts of the conses. One of the reasons why Racket is not a Scheme is that Racket's conses are immutable.

Thanks for clarifying. I remembered it as a point of contention in the Scheme community.

> because lazy sequences are supported throughout the language.

Most of the time Lisp implements these data structures themselves - many/most Lisps are largely implemented in itself. As such Lisp exposes and provides very low-level data structures like conses, which are simply two element cells. Basically Lisp here is on the level of assembler - which is reflected that the historical name CAR means something like 'contents of the address register'.

Clojure's persistent immutable sequences are a very different data structure. Clojure does not expose its implementation and the implementation does not easily map to hardware, especially since quite a bit of the language is implemented in terms of the JVM and the Java language.

Example:

https://github.com/clojure/clojure/blob/master/src/jvm/cloju...

"lazy" and "immutable" are orthogonal. "lazy" happily co-exists with "mutable". TXR Lisp has mutable lazy conses:

  1> (take 12 (range 1))
  (1 2 3 4 5 6 7 8 9 10 11 12)
  2> (let ((r (range 1)))
       (inc [r 4] 15)
       (take 12 r))
  (1 2 3 4 20 6 7 8 9 10 11 12)

There is no reason to prevent mutation; all we have to do is assume that programmers are grownups and treat them as such.

Remember, mutate responsibly; if you mutate, don't derive.

Even if someone has been mutating "harmless" local variables, do not jump into the same lexical scope with them.

I don't know. Outside of a few narrow use cases I personally don't think there's much advantage to using explicitly persistent data structures, so I haven't tried them, I just know the libraries exist.

How do you implement a persistent hashtable when your only abstraction is a linked list?

You'd do that in roughly the same way as in any other language that allows you to heap-allocate stuff and pass references to it.

> only abstraction is a linked list

What language are you referencing here?

>> But afaik most immutable, persistent data structure libraries in other lisps either (1) had poor performance or (2) were developed after clojure and borrowed from clojure.

>> only abstraction is a linked list

> What language are you referencing here?

They are referring to Lisp.

Does it have to have the performance characteristics, or just the semantics of a hashtable?

Reply on news.ycombinator.com