6
$\begingroup$

I am an object-oriented developer professionally, but I have researched functional programming and (believe that) I understand the key principles which to varying degrees are applied in FP languages.

I've seen how languages which are not FP only have been bringing some of the FP ideas into their languages. I'm interested in seeing how many of the ideas of FP can be brought into an OO language concept I've been working on.

One interesting concept is how Clojure approaches collections. It uses persistent data structures to make collection immutability cheap. I wonder if a similar approach could be taken in an object oriented language, to allow local mutation of an object instance, but not have these mutations affect other instances.

I have watched many of Rich Hickey's talks about the ideas behind Clojure, and in his talk "Are We There Yet?" (Available at: https://www.youtube.com/watch?v=ScEPu1cs4l0), he says:

I’ll leave this an open question for everybody else – is there a way to reconcile this with Object Orientation? Could we separate perception of an object from its identity enough so that we’d still get the benefits of objects but we don’t get a mess later?

This is what I'm interested in exploring.

Are there examples of languages which have tried to implement objects as persistent data structures?

For objects, it would mean they are implemented as a trie which, when aliased, creates a copy of the root nodes, thereby sharing the structure. Then if the instance is mutated the path is copied and the reference points to the new path, leaving the original unaffected.

This is a diagram used in Hickey's "Clojure Concurrency" talk: A diagram showing a visual representation of the trie structure used in Clojure's collections

Each instance of the collection (or class in our case) is the yellow node at the top, and the dashed lines show the copied values. The second instance shares the deep structure of the original collection. On the far right we see a modification in the second instance. A node which is 3 layers deep is added, so a copy of the path to its parent (orange and purple) is taken along with each of their direct children (dashed lines). Then the node is added to the copied purple node. The original path (with a red border) is unaffected.

*** UPDATE ***

For clarification, an implementation doesn't have to be a trie (that's just an example used in Clojure), but any tree-like structure with path-copying on mutation (or similar) could be used to implement objects.

$\endgroup$
16
  • $\begingroup$ Just to clarify the question, "records" in C# would not be an example of what you're talking about because "with" creates a copy of the immutable structure, not a trie -- is that correct? learn.microsoft.com/en-us/dotnet/csharp/language-reference/… $\endgroup$ Commented Jan 30 at 16:38
  • 1
    $\begingroup$ Yes, that's correct. A copy of the class should be closer to constant time than linear time because you only need to copy the root properties not the whole deep structure. $\endgroup$ Commented Jan 30 at 16:41
  • 1
    $\begingroup$ No problem, I'll attach a diagram. $\endgroup$ Commented Jan 30 at 16:46
  • 1
    $\begingroup$ Ah yes, instance modification. I'm not, in this question, discussing the structure of subtypes/inheritance etc. $\endgroup$ Commented Jan 30 at 17:40
  • 1
    $\begingroup$ Thanks for the clarification, that was helpful. I guess I am interested in OO designs where objects don't have discernable identity as the default, regardless of the implementation. I think the implementation aspects of my question were more geared towards narrowing the answers down to avoid, "all these languages have immutable objects as an option and a way to copy them (inefficiently)", but instead to find languages where object persistence is the core (and perhaps only) way to use objects. $\endgroup$ Commented Feb 1 at 20:10

1 Answer 1

Reset to default
4
$\begingroup$

Are there examples of languages which have tried to implement objects as persistent data structures?

Objects generally have a handful of fields, whose names and types are fixed for all objects of a given class, so in practice each object's size is O(1) and copying an object takes O(1) time.

Particularly, it's O(1) with not a very large constant: even 8-10 fields plus some type metadata is only a hundred bytes or so. So there is no need for tries or other complicated data structures ─ if you want immutable objects, just make a new copy for every logical change. (One logical change might mutate multiple fields.)

It's rare that an object has more than a handful of fields, but when it does, the object can be refactored as a composition of multiple subobjects. Then the immutable subobjects will naturally be shared when a new outer object doesn't change the subobject, giving the same benefits as a persistent data structure: copying a smaller outer object is faster, and components which aren't changed don't need to be duplicated in memory.

But it makes more sense for the programmer (i.e. the language user) to do this refactoring explicitly, since they know which fields it makes sense to group together, and it makes their code more maintainable not to have huge classes with hundreds of fields. Then if the programmer does it explicitly, the compiler or language runtime doesn't need to do it for them automatically.

All of this is to say, I don't know any object-oriented languages which do this, and there seem to be good reasons not to.

I’ll leave this an open question for everybody else – is there a way to reconcile this with Object Orientation? Could we separate perception of an object from its identity enough so that we’d still get the benefits of objects but we don’t get a mess later?

This seems like a quite separate question, but I'll take a stab at it. I think you are asking whether a language where all objects are immutable could really be OO.

I think: yes, absolutely. Different people conceptualise OO in different ways, but the "message passing" interpretation is a common one. That is, when you invoke an object's method, it's like you pass a message to the object, the object chooses what to do upon receiving the message, and then returns its response to you if any. This interpretation follows naturally from the principles of encapsulation and polymorphism, both of which can be achieved by immutable objects.

For a mental image, suppose you send a message to an object and it responds with, "OK, and by the way please direct further messages to this other object". This is a perfectly valid OO interpretation of a method on an immutable object which returns a new object with changes applied, where a mutable object would have an equivalent mutator method returning just "OK" (i.e. void). Or the response could be "here is my answer, by the way please direct further messages to this other object"; that would be a method which returns a pair like (response, newObject).

$\endgroup$
19
  • $\begingroup$ Thanks for your response. I'll consider your points in detail, but just in case you missed it, the quote is from Rich Hickey in his talk. He made the statement after describing how mutable objects conflate identity and state by allowing in-place mutation $\endgroup$ Commented Jan 31 at 20:05
  • 1
    $\begingroup$ I saw that it was a quote, but you followed it with "This is what I'm interested in exploring.", suggesting that you were asking the same yourself. If not, then I misunderstood. $\endgroup$ Commented Jan 31 at 20:06
  • $\begingroup$ I understand where you're coming from now. I am indeed asking the same question, but with an eye to answering it somewhat. I'm looking at whether immutability is the only answer, or whether it's actually shared mutability which is the problem. $\endgroup$ Commented Jan 31 at 20:08
  • $\begingroup$ I see what you're saying about objects usually being small, but doesn't what you say about object composition highlight the issue with that approach (which is what records are in C#)? In object oriented languages the object is the basic unit of decomposition, so you would expect objects to be composed of sub-objects, and then these sub-objects are composed of other sub-objects. This leads to deep rather than wide objects. This is problem if you want to promote ubiquitous immutability... $\endgroup$ Commented Jan 31 at 21:03
  • $\begingroup$ ...in an object oriented language, because OO is all about objects operating on their own state. So, if an object is deeply nested, then every change it makes requires a deep clone of the entire structure in order for the whole object to remain persistent. $\endgroup$ Commented Jan 31 at 21:06

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.