6 ms·

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

• jlarocco 8y ago
  Not built-in, but there are libraries.
  • drcode 8y ago
    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.
    • chrisseaton 8y ago
      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?
      • drcode 8y ago
        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.
      • kazinator 8y ago
        "Persistent" generally means something like "survives process restart and machine reboot".
        • taeric 8y ago
          Does it? I thought for data structures it was simply that it survived editing. That is, old versions are always accessible.
          • fiddlerwoaroof 8y ago
            It's an overloaded term: in some constexts it means "survives reboots" but in this context it means something else.
            • deleted 8y ago
              [deleted]
        • sriram_malhar 8y ago
          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.
          • deleted 8y ago
            [deleted]
          • deleted 8y ago
            [deleted]
          • kazinator 8y ago
            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.
      • wooby 8y ago
        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.
        • lispm 8y ago
          > 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/clojure/lang/PersistentList.java https://github.com/clojure/clojure/blob/master/src/jvm/cloju...
        • fiddlerwoaroof 8y ago
          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.
    • jlarocco 8y ago
      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.
    • gre 8y ago
      How do you implement a persistent hashtable when your only abstraction is a linked list?
      • int_19h 8y ago
        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.
      • Jtsummers 8y ago
        > only abstraction is a linked list What language are you referencing here?
        • ardy42 8y ago
          >> 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.
      • coldtea 8y ago
        Does it have to have the performance characteristics, or just the semantics of a hashtable?
• chrisseaton 8y ago
  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?
  • coldtea 8y ago
    Doesn't have to be built-in to exist in the Lisp ecosystem.
    • chrisseaton 8y ago
      Sorry I don't understand what that means? A Lisp list is a persistent data structure.
      • coldtea 8y ago
        A Clojure seq offers much more than that. But you can re-create it in CL, it's just not built-in.
        • chrisseaton 8y ago
          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.
      • cgrand-net 8y ago
        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.