How to make any immutable data structure distributed • Hacker News Board

Re: How to make any immutable data structure distributed

#31

Post by dwohnitmok » Mon, Dec 06, 2021, 7:47 AM UTC

Guvante wrote: post #28

nyanpasu64 wrote: post #18

Earlier quoted context omitted.

Sharing mutable data without a mutex (which suffers from unbounded contention) is hard. Approaches that work include updating persistent data structures and sharing the new copy, or sharing diff objects over a lock-free queue.

Sharing a new copy isn't always easy though. That is why lens are a thing. Unfortunately lens are (last I checked) still not quite easy to grow. The point is neither copying the whole structure nor diffs are as easy as mutex + inner mutation.

Sharing the copy is not what's solved by lenses. In a certain sense lenses are just a way to try to do away with the boilerplate of updating nested immutable data structures. It is very easy to write this boilerplate (in the sense that it is straightforward and hard to mess up). It's just mind-numbingly tedious.

Although I don't know what you mean by growing lenses.

Mutex + inner mutation is no easier than CAS (which is the usual solution with concurrent writing of immutable data structures) a la Java AtomicReference or STM (another popular one) and in my opinion significantly harder as soon as you have multiple mutexes.

Re: How to make any immutable data structure distributed

#32

Post by simongray » Mon, Dec 06, 2021, 8:08 AM UTC

runT1ME wrote: post #23

Scarbutt wrote: post #11

Earlier quoted context omitted.

Besides performance, what other cons exists for immutable data structures in a single standalone system?

It's awkward to work with fully nested structures. Think about having a map of customer objects which have a list of addresses and you need to update everyone's first address to be capitalized for some raeson. You'd really want a fully fleshed out lens library and maybe even macros for auto generating them on your concrete data structures to make it easy to 'update' (via a persistent structure) without having to deal…

I agree that you want specialised mini-DSLs for querying and updating highly nested structures (... which you should probably avoid creating anyway), but for such a simple task you could just do this (Clojure example):

    (update-vals customers #(update-in % [:address 0] str/capitalize))

Re: How to make any immutable data structure distributed

#33

Post by mlajtos » Mon, Dec 06, 2021, 8:40 AM UTC

simongray wrote: post #32

runT1ME wrote: post #23

Earlier quoted context omitted.

It's awkward to work with fully nested structures. Think about having a map of customer objects which have a list of addresses and you need to update everyone's first address to be capitalized for some raeson. You'd really want a fully fleshed out lens library and maybe even macros for auto generating them on your concrete data structures to make it easy to 'update' (via a persistent structure) without having to deal…

I agree that you want specialised mini-DSLs for querying and updating highly nested structures (... which you should probably avoid creating anyway), but for such a simple task you could just do this (Clojure example): (update-vals customers #(update-in % [:address 0] str/capitalize))

In JavaScript world, there is ImmutableJS, which uses this style of updates. However, there is better approach which is what ImmerJS uses – you write a function where you can do mutation to the target data structure, wrap it in a "produce" function, and library will pick on those mutations and create a new copy of the data that is structurally shared with the original.

https://immerjs.github.io/immer/

Re: How to make any immutable data structure distributed

#34

Post by luckysid » Mon, Dec 06, 2021, 9:25 AM UTC

zomglings wrote: post #24

lidatong wrote: post #12

I think there were a lot of great ideas presented in these small examples. 1. Explicitly marking non-local _data_ vs. in-memory. A very cool idea -- languages and libraries I've used all seem to try to make this transparent (unsuccessfully, as indicated by the random serialization errors you get) 2. Making the noise around serialization and RPC transparent to the user 3. Bring the code to the data, not the data to th…

Your use of the word transparent confused me a little. It seems you are using it in the sense that details that are being made transparent are being hidden from the user. But if you make something transparent to the user, it could also mean that you are directly exposing that thing to the user. (Right? I could be wrong about this.) Just confused me and thought it might be useful to you to know that. Not trying to be…

I think in a technical context, it always has the meaning OP is talking about. Check out https://en.wikipedia.org/wiki/Transparency_(human%E2%80%93co.... I've mostly seen research papers use transparency with this meaning.

Re: How to make any immutable data structure distributed

#35

Post by simongray » Mon, Dec 06, 2021, 10:02 AM UTC

mlajtos wrote: post #33

simongray wrote: post #32

Earlier quoted context omitted.

I agree that you want specialised mini-DSLs for querying and updating highly nested structures (... which you should probably avoid creating anyway), but for such a simple task you could just do this (Clojure example): (update-vals customers #(update-in % [:address 0] str/capitalize))

In JavaScript world, there is ImmutableJS, which uses this style of updates. However, there is better approach which is what ImmerJS uses – you write a function where you can do mutation to the target data structure, wrap it in a "produce" function, and library will pick on those mutations and create a new copy of the data that is structurally shared with the original. https://immerjs.github.io/immer/

Yeah, that is basically what that Clojure code does. All of the data structures in Clojure are persistent and use structural sharing.

Re: How to make any immutable data structure distributed

#36

Post by gpderetta » Mon, Dec 06, 2021, 10:29 AM UTC

skyde wrote: post #20

jltsiren wrote: post #15

I dislike the term "immutable data structure", because it has two widely used conflicting meanings: 1. Read-only data structures, which are used by everyone in every language all the time. 2. Persistent data structures, which make the underlying immutable structures kind of mutable by creating new versions and reusing parts from the old versions of the structure.

lol the word "persistent" is itself ambiguous an have conflicting meaning: 1- https://en.wikipedia.org/wiki/Persistence_(computer_science) In computer science, persistence refers to the characteristic of state of a system that outlives (persists more than) the process that created it. 2- https://en.wikipedia.org/wiki/Persistent_data_structure In computing, a persistent data structure or not ephemeral data structure i…

Yes, first time I read about persistent data structures, I thought it had something to do with mmap :).

Re: How to make any immutable data structure distributed

#37

Post by pmapcat » Mon, Dec 06, 2021, 11:21 AM UTC

runT1ME wrote: post #23

Scarbutt wrote: post #11

Earlier quoted context omitted.

Besides performance, what other cons exists for immutable data structures in a single standalone system?

It's awkward to work with fully nested structures. Think about having a map of customer objects which have a list of addresses and you need to update everyone's first address to be capitalized for some raeson. You'd really want a fully fleshed out lens library and maybe even macros for auto generating them on your concrete data structures to make it easy to 'update' (via a persistent structure) without having to deal…

That is the use case that we have to work with quite often. In the end, we use something along the lines of

  (update-fn (fn [{:keys [address]}
                   :as customer]
               (if address (update customer :address clojure.string/capitalize) customer))
    customers)

which pattern matches on some `object` (map) and does processing. We find it less fragile than specifying explicit path to an element. It can also work in a polymorphic fashion. On the other hand, there is a risk of a false positive (when you modify address that you shouldn't). But you can mitigate that risk by using additional checks (in case of a customer, you can check for additional set of fields that are specific for that object(map) edit:formatting

Re: How to make any immutable data structure distributed

#38

Post by dwohnitmok » Mon, Dec 06, 2021, 11:24 AM UTC

simongray wrote: post #35

mlajtos wrote: post #33

Earlier quoted context omitted.

In JavaScript world, there is ImmutableJS, which uses this style of updates. However, there is better approach which is what ImmerJS uses – you write a function where you can do mutation to the target data structure, wrap it in a "produce" function, and library will pick on those mutations and create a new copy of the data that is structurally shared with the original. https://immerjs.github.io/immer/

Yeah, that is basically what that Clojure code does. All of the data structures in Clojure are persistent and use structural sharing.

That Clojure code isn't quite grasping the essence of ImmerJS. The whole point of ImmerJS is that JS has nice, built-in syntax for in-place mutation and we can reuse that syntax to generate updates to an immutable data structure so long as we scope the mutation syntax so that outside of an individual block of mutation syntax everything stays immutable. That it is implemented with JS proxies is something of an implementation detail (it could e.g. be implemented with linear or affine types or something like Haskell's ST type).

In this sense it's closer to Clojure's transients, if Clojure came prepackaged with special mutation syntax (notably assignment via =) and if transient-ness could be propagated transitively to all nested structures in a data structure.

Re: How to make any immutable data structure distributed

#39

Post by chrisjc » Mon, Dec 06, 2021, 11:44 AM UTC

runT1ME wrote: post #6

I really think this is where pure FP shines. If you look at the architecture of something like Apache Beam, while you describe your computations in a language like Java or Python, you're really using a DSL for creating an immutable DAG that processes chunks of immutable data, persisiting each chunk (being loose with terms here) for durability, 'modifying' it in the immutable sense and then passing it on to the next e…

Intriguing, but I think I lost you a little in the details and really dying to understand your perspective.

    1) creating an immutable DAG that processes chunks of immutable data, 
    2) persisting each chunk (being loose with terms here) for durability, 
    3) 'modifying' it in the immutable sense 
    4) and then passing it on to the next edge and so on

Isn't #4 the persisting part, not #2? Maybe I'm confused by what you mean by "persist"? Render the instructions (mutate the data)?

And when you say "'modifying' it in the immutable sense", does this mean that the original data stays untouched, but "instructions" on how to modify the data get "pinned" to the data?

Then every other subsequent step in the DAG is just modifying the "instructions"?

If I understand you correctly, your point about how this is where FP shines is really illustrated in #4. You end up passing instructions around instead of the data. But how FP instructions can be modified and modified again really baffles me. The closest I can get to understanding it in practical terms is by using something like Clojure and thinking about how Clojure is just data, and you can modify, or build upon Clojure by modifying like you modify data. I struggle extending this to another language like Scala or JavaScript.

Re: How to make any immutable data structure distributed

#40

Post by nyanpasu64 » Mon, Dec 06, 2021, 3:22 PM UTC

dwohnitmok wrote: post #31

Guvante wrote: post #28

Earlier quoted context omitted.

Sharing a new copy isn't always easy though. That is why lens are a thing. Unfortunately lens are (last I checked) still not quite easy to grow. The point is neither copying the whole structure nor diffs are as easy as mutex + inner mutation.

Sharing the copy is not what's solved by lenses. In a certain sense lenses are just a way to try to do away with the boilerplate of updating nested immutable data structures. It is very easy to write this boilerplate (in the sense that it is straightforward and hard to mess up). It's just mind-numbingly tedious. Although I don't know what you mean by growing lenses. Mutex + inner mutation is no easier than CAS (which…

IMO the hard part of immutable structures is mutation (solved by https://lib.rs/crates/im), the hard part of diffing is writing one "command" subclass per type of operation (which can be more or less manageable), and the hard part of mutexes is remembering to lock the mutex or rwlock in every single access (Rust fixes this), avoiding priority inversions (Rust doesn't help), and avoiding deadlocks (Rust doesn't help).