7 ms·

How to make any immutable data structure distributed

174 points by pierremenard 5y ago

jltsiren 5y ago
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.
- mopierotti 5y ago
  Aren't those the same things? i.e. 2. are just read-only data structures with functions to create new read-only data structures based on them. (e.g. immutable linked lists that you can filter, concat, etc. with) Or are you talking about something more specific, like mutable data structures that provide immutable snapshots of the backing data?
- skyde 5y ago
  lol the word "persistent" is itself ambiguous an have conflicting meaning: 1-https://en.wikipedia.org/wiki/Persistence_(computer_science) 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 https://en.wikipedia.org/wiki/Persistent_data_structure In computing, a persistent data structure or not ephemeral data structure is a data structure that always preserves the previous version of itself when it is modified.
  - armchairhacker 5y ago
    I usually distinguish "readonly" values (references which block mutation, but you can mutate via another reference) and "immutable" values (what OP calls persistent, where modification may copy-on-write but you're certain the original reference won't mutate).
  - gpderetta 5y ago
    Yes, first time I read about persistent data structures, I thought it had something to do with mmap :).
jmfldn 5y ago
I really hope Unison succeeds. It looks like a really interesting take on FP / distributed systems. The fact that Paul Chiusano and Runar Bjarnason are at the helm is exciting, especially to Scala / FP devs like me who know them as the writers of the legendary "red book". Just based on the rare quality of that book, I'm super interested in other FP projects that they're involved in.
- LandR 5y ago
  > writers of the legendary "red book". If you mean the manning book "Functional Programming in Scala", I don't even use Scala, yet I feel I got so much out of that book. It's the best functional programming book I've read. It would recommend the book to anyone that wants to learn FP, regardless if you will be using Scala.
  - jmfldn 5y ago
    That's the one. It's great for any FP learner for sure. A great example of how to write a book on a deep topic in an engaging and beautifully structured way.
- cipheredStones 5y ago
  Tangential to the thread, but do you have any other favorite Scala resources you would recommend? I've had only glancing exposure to it, and will soon be taking a role where it's the primary language.
  - jmfldn 5y ago
    I do indeed. The "red book" aka Functional Programming in Scala I wouldn't recommend to a beginner. It teaches FP at a fairly deep level to the extent of implementing the abstractions yourself. Take a look at that later perhaps. Don't get me wrong, it is utterly brilliant but it wouldn't be the place to start. I would recommend Essential Scala for the basics. Scala with Cats if you're going to be working with the Typelevel stack (a popular set of FP libraries). Lots of other resources but those two alone will take you far. http://underscore.io/books/essential-scala/ http://underscore.io/books/essential-scala/ http://underscore.io/books/scala-with-cats/ http://underscore.io/books/scala-with-cats/
pchiusano 5y ago
One of the authors of the article here, happy to answer any questions about it!
- Touche 5y ago
  How do you perform side effects in Unison (like reading a file as an example)?
  - rlmark 5y ago
    Hi there, the other article author chiming in here! You can perform side effects in Unison via abilities (our name for algebraic effects) - they're described here: https://www.unisonweb.org/docs/abilities/ https://www.unisonweb.org/docs/abilities/ Some basic IO functionality is supported by the `base` library (the standard lib) which contains functions like `openFile` which are effectful functions expressed in terms of the `IO` ability.
- lidatong 5y ago
  I had a few questions: 1. The posts mention Spark, but were you (the Unison team) also inspired by dataflow / stream processing engines (e.g. Flink, Beam, Timely Dataflow etc.) or any other technologies? 2. Relatedly, are there any plans to add a stream processing API? Or perhaps that would belong in a 3rd-party library? 3. Broadly, where do you think (in your opinion) Unison fits in the ecosystem of tooling? Is Unison specialized at solving big data problems that require distributed execution e.g. something I pull out of my toolbox for a problem I'd otherwise solve with Spark? Or is it a truly general-purpose programming language? 4. With the Tree example, you show the "wrong" way and then the "right" way -- one problem I've experienced in the past is how do you as a new user know the right way. For example, I wrap my entire program in IO then .unsafeRunSync it -- technically following the rules, but got nothing out of doing that. Have you thought about how the APIs could guide the user to the idiomatic solution? Perhaps via types? By the way, I really loved the FP in Scala book, it was my first step into FP -- thank you and Runar for writing it
  - rlmark 5y ago
pchiusano 5y ago
Recommend starting with part 1 of the article if you want more of an overview: https://www.unison-lang.org/articles/distributed-datasets/ https://www.unison-lang.org/articles/distributed-datasets/
runT1ME 5y ago
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 edge and so on. In a single standalone system, many argue that a purely immutable conceptual approach has pros and cons. In the Big Data world, I've never heard anyone argue for an imperative approach. Immutability is necessary, and as soon as you need immutability you want all the other goodies that facilitate it in a clean way like monads, lenses, and the like.
- piyh 5y ago
  FP?
  - sethammons 5y ago
    Functional programming
- Scarbutt 5y ago
  Besides performance, what other cons exists for immutable data structures in a single standalone system?
  - Guvante 5y ago
    Sharing immutable data is hard. Mutable throw you throw a lock on it and mutate in place. How do you share mutations when you can't change anything? To be clear it is certainly a solvable problem (as this post shows) but it can make things difficult.
    - romero-jk 5y ago
      This is how clojure does it: https://clojure.org/reference/atoms https://clojure.org/reference/atoms It's very costly though.
lidatong 5y ago
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 the code 4. Immutability, FP, and I like the syntax -- no coincidence in its similarities to Haskell and Scala, I'm sure :) These are all pain points in a lot of existing "big data systems" I've used, where they either solve the problem half-baked or don't address at all. I'm excited to see where this project goes!
- zomglings 5y ago
  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 an asshole.
  - luckysid 5y ago
    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%93computer_interaction) https://en.wikipedia.org/wiki/Transparency_(human%E2%80%93co.... I've mostly seen research papers use transparency with this meaning.
  - lidatong 5y ago
    No offense taken - re-reading what I wrote, you make a fair point. The wiki page luckysid linked calls this out: > Confusingly, the term refers to overall invisibility of the component, it does not refer to visibility of component's internals Indeed, perhaps "invisible" would have been a better word choice.

174 points by pierremenard 5y ago

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.

mopierotti 5y ago
Aren't those the same things? i.e. 2. are just read-only data structures with functions to create new read-only data structures based on them. (e.g. immutable linked lists that you can filter, concat, etc. with) Or are you talking about something more specific, like mutable data structures that provide immutable snapshots of the backing data?
skyde 5y ago
lol the word "persistent" is itself ambiguous an have conflicting meaning: 1-https://en.wikipedia.org/wiki/Persistence_(computer_science) 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 https://en.wikipedia.org/wiki/Persistent_data_structure In computing, a persistent data structure or not ephemeral data structure is a data structure that always preserves the previous version of itself when it is modified.
- armchairhacker 5y ago
  I usually distinguish "readonly" values (references which block mutation, but you can mutate via another reference) and "immutable" values (what OP calls persistent, where modification may copy-on-write but you're certain the original reference won't mutate).
- gpderetta 5y ago
  Yes, first time I read about persistent data structures, I thought it had something to do with mmap :).

jmfldn 5y ago

I really hope Unison succeeds. It looks like a really interesting take on FP / distributed systems. The fact that Paul Chiusano and Runar Bjarnason are at the helm is exciting, especially to Scala / FP devs like me who know them as the writers of the legendary "red book". Just based on the rare quality of that book, I'm super interested in other FP projects that they're involved in.

LandR 5y ago
> writers of the legendary "red book". If you mean the manning book "Functional Programming in Scala", I don't even use Scala, yet I feel I got so much out of that book. It's the best functional programming book I've read. It would recommend the book to anyone that wants to learn FP, regardless if you will be using Scala.
- jmfldn 5y ago
  That's the one. It's great for any FP learner for sure. A great example of how to write a book on a deep topic in an engaging and beautifully structured way.
cipheredStones 5y ago
Tangential to the thread, but do you have any other favorite Scala resources you would recommend? I've had only glancing exposure to it, and will soon be taking a role where it's the primary language.
- jmfldn 5y ago
  I do indeed. The "red book" aka Functional Programming in Scala I wouldn't recommend to a beginner. It teaches FP at a fairly deep level to the extent of implementing the abstractions yourself. Take a look at that later perhaps. Don't get me wrong, it is utterly brilliant but it wouldn't be the place to start. I would recommend Essential Scala for the basics. Scala with Cats if you're going to be working with the Typelevel stack (a popular set of FP libraries). Lots of other resources but those two alone will take you far. http://underscore.io/books/essential-scala/ http://underscore.io/books/essential-scala/ http://underscore.io/books/scala-with-cats/ http://underscore.io/books/scala-with-cats/

pchiusano 5y ago

One of the authors of the article here, happy to answer any questions about it!

Touche 5y ago
How do you perform side effects in Unison (like reading a file as an example)?
- rlmark 5y ago
  Hi there, the other article author chiming in here! You can perform side effects in Unison via abilities (our name for algebraic effects) - they're described here: https://www.unisonweb.org/docs/abilities/ https://www.unisonweb.org/docs/abilities/ Some basic IO functionality is supported by the `base` library (the standard lib) which contains functions like `openFile` which are effectful functions expressed in terms of the `IO` ability.
lidatong 5y ago
I had a few questions: 1. The posts mention Spark, but were you (the Unison team) also inspired by dataflow / stream processing engines (e.g. Flink, Beam, Timely Dataflow etc.) or any other technologies? 2. Relatedly, are there any plans to add a stream processing API? Or perhaps that would belong in a 3rd-party library? 3. Broadly, where do you think (in your opinion) Unison fits in the ecosystem of tooling? Is Unison specialized at solving big data problems that require distributed execution e.g. something I pull out of my toolbox for a problem I'd otherwise solve with Spark? Or is it a truly general-purpose programming language? 4. With the Tree example, you show the "wrong" way and then the "right" way -- one problem I've experienced in the past is how do you as a new user know the right way. For example, I wrap my entire program in IO then .unsafeRunSync it -- technically following the rules, but got nothing out of doing that. Have you thought about how the APIs could guide the user to the idiomatic solution? Perhaps via types? By the way, I really loved the FP in Scala book, it was my first step into FP -- thank you and Runar for writing it
- rlmark 5y ago

pchiusano 5y ago

Recommend starting with part 1 of the article if you want more of an overview: https://www.unison-lang.org/articles/distributed-datasets/ https://www.unison-lang.org/articles/distributed-datasets/

runT1ME 5y ago

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 edge and so on. In a single standalone system, many argue that a purely immutable conceptual approach has pros and cons. In the Big Data world, I've never heard anyone argue for an imperative approach. Immutability is necessary, and as soon as you need immutability you want all the other goodies that facilitate it in a clean way like monads, lenses, and the like.

piyh 5y ago
FP?
- sethammons 5y ago
  Functional programming
Scarbutt 5y ago
Besides performance, what other cons exists for immutable data structures in a single standalone system?
- Guvante 5y ago
  Sharing immutable data is hard. Mutable throw you throw a lock on it and mutate in place. How do you share mutations when you can't change anything? To be clear it is certainly a solvable problem (as this post shows) but it can make things difficult.
  - romero-jk 5y ago
    This is how clojure does it: https://clojure.org/reference/atoms https://clojure.org/reference/atoms It's very costly though.

lidatong 5y ago

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 the code 4. Immutability, FP, and I like the syntax -- no coincidence in its similarities to Haskell and Scala, I'm sure :) These are all pain points in a lot of existing "big data systems" I've used, where they either solve the problem half-baked or don't address at all. I'm excited to see where this project goes!

zomglings 5y ago
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 an asshole.
- luckysid 5y ago
  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%93computer_interaction) https://en.wikipedia.org/wiki/Transparency_(human%E2%80%93co.... I've mostly seen research papers use transparency with this meaning.
- lidatong 5y ago
  No offense taken - re-reading what I wrote, you make a fair point. The wiki page luckysid linked calls this out: > Confusingly, the term refers to overall invisibility of the component, it does not refer to visibility of component's internals Indeed, perhaps "invisible" would have been a better word choice.