The Fatal Flaw of Ownership Semantics
gingerbill.org
gingerbill.org
But they were spot-on about what is arguably Rust's biggest weakness, and the things people do to work around it, and I think there's kind of an open question whether that status-quo can be improved upon. I.e. Rust right now is excellent at certain things ("linear things"), and okay at non-linear things. But could it be made to be really good for the latter too? Or will it remain somewhat confined to its specialization? The language occupies uncharted territory either way, so these kinds of questions are not surprising, and I for one am excited to see where things go.
Having written programs in Rust and Haskell, which are in this regard quite similar, I think that you can express most of your application in a "linear" fashion and only have a bit of "non-linear" things at the top.
For example if you have to handle some "non-linear" things like events from the system or a gui library, then you might have - in Rust terminology - a 'RefCell<Rc<AppState>>' to be able to have shared mutable access to the application state.
At the top of the event handler you would transform the 'RefCell<Rc<AppState>>' into a '&mut AppState', which is the switch from the "non-linear world" to the "linear world" and involves a runtime check that there's only one mutable reference. All the following code of the handler can then be verified at compile time.
This also makes the reasoning about the application easier, because you might even reduce the mutation of your application state to the switching area. So most of the event handling could be a pure transformation of the application state.
I think one should just assume headlines are hyperbole and live with it. No one would read the article "A nuanced critique of ownership semantics" no matter how good it was. The only reason we are discussing it is because someone chose to make it hyperbolic. That's unfortunate but it is what it is.
The article is crap overall given what the title promised.
As for where other languages can go in this area, it would be interested to explore the idea of tracking "uses" in general. It might be useful for the compiler but not necessarily an intrinsic language feature. My issue with Rust is that it went headlong into an unproven idea and those issues are now showing.
Maybe that's an interesting way to think about the article too. The obvious way to think about a graph using ownership is to start with a root node, then to say that nodes own other nodes through their edges. But that model won't generalise to disjoint graphs (eg, social network with separate friend groups) and it isn't always clear which node is the "root" node.
struct Graph {
nodes: Vec<Node>,
edges: Vec<Edge>,
}
The article suggests that handles are better than references anyway (I'd tend to agree in this case) so Edge would be a pair of handles. That seems totally fine, so maybe the "fatal flaw" is overstated...
EDIT: Alright, I’ve skimmed to the end and it seems to me it is a very r/iamverysmart way of saying “I prefer to use RefCell”.
Honestly, I have trouble trusting someone’s judgement in programming language semantics when they can’t seem to be a good judge of their own written language semantics.
Why define an agent at the beginning, but leave “agency” undefined? What does even “capability to act in a certain environment” mean? Is a function/method something with “capability to act in a certain environment”? Is a C++ class that??
Also:
> It is also a category error to treat them as “real objects” since “real objects” and “programming objects” have little connection with each other ontologically.
Mate, you link to the Wikipedia article about categorical errors, where it says that a CE is defined as comparing things that are ontologically different, thus showing your whole sentence as a tautology. What’s the value added for the reader??
https://www.sciencemag.org/careers/2016/01/how-read-scientif...
One difference I see between these two escape hatches are switching costs. Rewriting the Java standard library to use composition and not inheritance borders on impossibly difficult. Rewriting the rust standard library to use RefCell instead of &mut everywhere would be arduous and possibly automatable, but not impossible.
Rewriting the Rust std lib to use RefCell everywhere would be possible, but would make it almost entirely useless.
> Rewriting the Rust std lib to use RefCell everywhere would be possible, but would make it almost entirely useless.
Maybe not useless, but certainly worse than it currently is. The point is that you can switch one function to using RefCell (a breaking change, but) totally possible
As soon as a piece of code "knows" about this chunk of memory it has certain responsibilities, like not randomly scribbling over values or freeing the memory while others pieces of code might attempt the same.
"Ownership" and "Move Semantics" are entirely artificial conventions to give some structure to those responsibilties. Casting those conventions into "hard language rules" introduces tradeoffs, evaluating those tradeoffs is important when deciding what language to use to solve certain problems. And this is where Rust comes in. Rust just enforces a couple of such "made up" conventions, none of those rules are dictated by the "real world" (e.g. the hardware the code runs on)... it's easy to get all tangled up in theoretical concepts like type systems, and functional programming, but in the end the only thing that counts is the machine code that's running on a concrete CPU. Sometimes I feel that language designers are losing sight on this simple reality ;)
> ...ownership/move semantics is fundamentally based around the _responsibilities of values_ by tracking value usage. > ... > If we were to call Ownership Semantics a paradigm, it would be the orientation around the responsibility of values in a hierarchical fashion, placing emphasis on this system of responsibility, shifting focus from data structures and algorithms.
I am not a brilliant writer (which I already knew, even though loads of people have commented on that), but I was trying to get an idea I had in my head onto paper. I wanted to explain that this abstraction is not as good as it is being advertized and does have its limitations. It's not a criticism of the concept, but its application to a bunch of problems.
My thesis here is that Rc<RefCell<_>> and similar are an effective escape hatch to ownership semantics, but they’re much less convenient than a garbage-collected type in a scripting language specifically because of the language’s low-level memory model. A GC language with ownership semantics might be able to obviate RefCell, which is the cause of Rc<RefCell<_>>’s inconvenience.
I’d be interested to see experimentation with ownership semantics in languages with higher-level memory models (which broadly means GC languages). My thesis could turn out to be quite wrong, and I haven’t worked out all the details of how the combination would work (especially I’m hazy on parts of removing RefCell, which is pretty critical), but I think it could be worth some research—ownership semantics for its own sake, rather than ownership semantics for memory safety.
> 10. Getting used bypassing the borrow checker to reduce fighting implies people have just found a way to cope with the constraints it imposes.
Here’s the thing, though: it’s not just about finding a way to cope with the constraints it imposes; it’s also about thriving within the constraints it imposes, because it stops you from doing problematic things and guides you in the path of better designs much of the time (though non-linearity can definitely be a problem; it’s not all buttercups and daisies). When I work in JavaScript, I spend half the time missing ownership semantics, occasionally feeling downright miserable because ownership semantics would have made a problem far easier or less dangerous. Remember what I said about ownership semantics for its own sake rather than ownership semantics for memory safety? Yeah, most of the time I love Rust’s ownership semantics for the modelling rather than the memory safety.
Ownership is an attempt to partition that with the goal of simplifying things and say that particular area of memory can only be modified/accessed at particular time by particular code. Isolated memory between processes does that at OS level, Rust and OOP try it inside a particular process, but they do it in a different way.
My point here isn't to be pedantic but to argue this point: The fundamental quality of computing is that it abstracts a physical system to a logical one. In this light the realness of a data type is the same realness of a bit, since they are both structures that give way to a more defined logical system, one built on the next.
To speak to the OP's claim of a category mistake I think he misses this valuable insight. The "realness" of programming objects and the semantics of moving them and copying them is the same "realness" of the bit or the data type. This is to say that the category that programming objects are contained within is, for lack of a better phrase, "the category of logical abstractions built on physical systems". The reuse of "move" and "copy" to represent similar processes to those we use with physical systems is a "logical encoding", not an error. In fact, the op makes the categorical mistake by saying that we mean "physically move" when we mean "logically move".
That said, this was an interesting read in spite of my disagreements with some assertions.
Haskell might give a few hints how well this works. [1]
> Here’s the thing, though: it’s not just about finding a way to cope with the constraints it imposes; it’s also about thriving within the constraints it imposes, because it stops you from doing problematic things and guides you in the path of better designs much of the time (though non-linearity can definitely be a problem; it’s not all buttercups and daisies).
Oh yes, and how nice it is to have these constraints verified by the compiler. Perhaps it's this kind of assumption, that less constraints give you more power, without realizing that also the responsibility increases, and at a certain point the complexity overburdens the human mind.
Different software domains need different constraints, so the question might be where the sweet spot between languages with different constraints and a language with programmable constraints (aka dependent types) lies.
[1] https://www.tweag.io/blog/2020-06-19-linear-types-merged/
This is an extremely important point! Most people try to make a language act like another language, rather than try and embrace how it does things. "When in Rome(, do as the Romans do)"
It's like when people try and make C into another language by abusing the macro system, you get a horrible mess compared to if you embraced what the language likes to do normally.
Personally, I think Rust's memory model is quite high level, and coupled with its ownership semantics, I cannot do many things such as custom allocators. (Not a singular custom global allocator)
The article also suffers from the syndrome of taking a feature of a language and pretending that everything has to be seen through the lens of that feature. Well, newsflash: ownership semantics apply to only some things in Rust. They apply to values and bindings. But they don't apply to e.g. indices. I can take as create as many i's, where i=5, all referring to the same Vec, which later are going to be used to mutate the Vec, as I like, and Rust won't stop me. Similarly, there is Rc and Arc.
It also included one of those "wise" thoughts along the lines of "You know what? The true nature of computers/economy/life/love is..." - one of the templates of meaningless sentences. In this case it was "however virtually all computers are fundamentally mutable things". Hmm... Did we suddenly forget about pipelining, instruction ordering, caching, instruction-level parallelism, C/C++'s problems with memory aliasing? C is not a low-level language[1].
[1]: https://queue.acm.org/detail.cfm?id=3212479
If we were to write a statement analogous to the one advocated for in the article, but talking about mathematics instead, it could be "the fatal flaw of mathematics is that a lot of it is about reducing problems to linear algebra". How ridiculous does that sound?
I don't disagree with you that C is not a low level language, but a very high level language. But you have made a false dichotomy regarding "mutable things" and then talking about other things about a computer. I am not saying "a computer is only X", but "a computer is X, but also Y, Z, W, ..."
The "fatal flaw" bit is purposeful click bait. "A critique of ownership semantics" is not necessarily a good.
If there are important things in your language that aren't values, that's a problem in your language. You really don't need any non-values; just look at, say, Haskell.
> As I have described above, both the OOP and OS both share similarities:
> Traditional-OOP: A (linear) value hierarchy of behaviour. The values act as agents.
> Ownership Semantics: A (linear) value hierarchy of responsibility. Agents are responsible for values.
This is just bollocks once you actually look at the details of it. An inheritance hierarchy is fixed once and for all at compile time, and can't ever change; either there's no way to change which class a given class inherits from at all, or at best there's some uncontrolled dark magic you can do. Whereas a defining characteristic of ownership semantics is that ownership can be safely passed from one owner to another in a controlled way.
"There are many criticisms of OOP456789 but my general criticism is that by placing emphasis on trying to solve problem in the type system, it shifts focus from the data structures and algorithms, the core of what a program fundamentally is."
We are not interested in solving all problems by programming. We should solve with programming what is best solved that way.
"anything solved in the type system drops off the list of what needs to be solved" AT A HUGE COST. Everything has a cost to it and even if you could hypothetically most solve things at compile time (you cannot), it might take a damn long time to compile it.
What is a “non linear logic” or a “non linear problem “ in this context?
In the case of these fancier data structures, it is perhaps also worth pointing out that many of them actually do follow ownership semantics, down to things like allowing shared access to multiple nodes, or exclusive access to a single node, so that no runtime checks are necessary. This is where I think the original article severely missteps in calling it a fatal flaw—because people are successfully building safe ownership-oriented abstractions using unsafe code. That’s a super-important capability of Rust.
To put it in my own words, and bear in mind that the last time I've worked with linear logic was 15 years ago. A linear logic restricts how often you are allowed to use a proposition in a derviation or proof tree.
The borrow checker is more like a linear type system. In linear type systems you restrict how often an identifier of a linear typed variable may be used. See, e.g. Phil Wadler's paper "Linear types can change the world", where he explores the idea to use linear types as an alternative to model the World(tm) in pure functional programming, i.e. an alternative to the IO monad.
Ha! I always felt like OOP is a natural outgrowth of Scholasticism, which is basically saying the same thing.
(Also: what distinction is being made between "oriented" and "orientated", and why?)
The author appears to believe that the analogies used to invent convenient names for language constructs are supposed to really be the construct, rather than a shorthand description.
Language features, once they map to actual semantics, become pure mechanisms with their own ironclad logic, with only an analogical relationship to whatever concept motivated and, usually, named them.
Thinking in terms of the concept, or (worse) the word chosen to refer to it, as the author does again and again, can only generate confusion.
The author is also confused about the role of inheritance in C++. Unlike in Java, which offers practically nothing else to organize a program, in C++ inheritance is wholly optional, and is typically used only where it solves a specific problem.
The author further confuses regular and virtual member functions, and their respective roles in design space.
The sorts of confusion seen here are quite common in philosophy, which has great difficulty staying grounded to facts of experience, something I think Wittgenstein complained of. In programming most of us don't have that problem, because the facts of problems to be solved and, moreso, of the physical machines we use in solving them provide ground truth.
Computer Science perennially tries to cut itself loose from that ground truth, but is always brought to heel by the demand of its graduates for employability.
IMO this sentence is completely unnecessary.
> Unlike in Java, which offers practically nothing else to organize a program, in C++ inheritance is wholly optional, and is typically used only where it solves a specific problem.
As someone with extensive experience in both Java and a number of other languages (before and after learning Java) this just isn't true.
It detracts from your point for everyone who knows Java and it adds unnecessary anxiety for people who will learn Java in the future if they belive this.
Java has flaws, but inheritance is not the only way to compose Java programs.
Edit: As a general rule I'd suggest everyone stop pretending Java is generally bad until they have some actual experience from real world systems in Java and a couple of other languages under their belt.
In practical terms of course a bit of boilerplate to declare a class where none was needed, doesn't matter a great deal.
This is correct but not what GP wrote. What GP wrote is:
> Unlike in Java, which offers practically nothing else [than inheritance] to organize a program,
To point out why GP is wrong:
- In Java you can organize files by packages
- by purpose (different folders for test vs production code),
- you can use composition to combine classes (in fact this is the recommended way these days)
- etc
I normally don't care about language wars but I think it is OK to point out when someone writes something that is clearly wrong.
I don't know why people say that you can't use composition in Java or that it is unique to purely functional languages. You can achieve composition by using Streams, decorator, composite and chain of responsability patterns.
Bonus points for having a somewhat long list of definitions that explains that the words are used in their usual meaning, yet does this by the way of introducing more undefined terms, sometimes tautological: an Agent is an actor with the capacity to act, marvellous. "A Doer is a doing entity that can do things"--agent and actor are both derived from the same Latin verb that means "to do". And that list misses the definition for "linear", which is definitely not used in any usual sense of the word: trees are linear, but graphs are not... huh?
The whole thing would be much more obvious if they ditched half the philosophising and gave a concrete example of the problem and their solution. Then by all means talk about the philosophy behind how it generalises.
While I agree with your overall point, this is a usual definition of linear: each item (eg graph/tree node) is used (eg pointed to) at most[0] once (eg each tree node has at most one parent node, whereas a graph node can have multiple edges from other nodes).
0→2 0→2
↓ ↓ ↓ ↓
1 3 1→3
This sense comes from linear functions, which can be expressed with at most one use of their argument in the form λx(Ax+B) for A and B constant in x. (Under this scheme, x² would have to be expressed as x·x, which repeats x; linearity in programming languages generally allows numeric values to be duplicated freely, so this is only of etymological relevance.)
0: or possibly exactly once; I can never remember which of those is "linear" and which is "affine".
I was also using the term "linear" with respect to graphs: * All trees are graphs, but not all graphs are trees. All linear graphs are a form of tree.
Whereabouts was I using the term _linear_ in two different senses?
As for two different senses, look at the the first paragraph in the "Mathematical Formalism of Ownership Semantics": it uses "linear graph" and "linear logic" in the same sentence. Unless you define "linear graphs" as "graphs that are described by linear logic", but to the best of my knowledge, linear logic describes the structure of computation (that's why it's logic, it describes the proofs and you get code via Curry-Howard isomorphism), not of data. Unless you equate the graphs with their traverses? But again, that's all highly non-trivial and non-widespread knowledge and terminology, unlike "value is a piece of data" and "agent is an actor".
All hierarchies can be described using graphs, and hierarchy is a relationship between different things in that graph through some dominating aspect (whatever that might be). A "linear hierarchy" is a hierarchy with no overlapping parts, no cycles, and a unique way to traverse up the hierarchy, e.g. you father is your son is not allowed, a node cannot be part of multiple hierarchies, a node has two parents which share a common ancestor, etc.
I am not sure why you brought up my "Value" definition, that was a little random.
> Unless you equate the graphs with their traverses?
I mostly am because data structures on their own without algorithms are useless things. Type systems try to encode information about the values effectively restricting what algorithms can do to them. Ownership semantics are another aspect of the type system of some languages which encodes a responsibility dependency graph to values. This means it explicitly restricts what data structures can be like _by default_. It encourages linear data structures, where the dependency between the values can be model through linear logic. This is why something as basic as a linked list is difficult to implement in languages designed around ownership semantics. It is of course possible but either requires restricting what the linked lists can do, or doing something to bypass the ownership semantics entirely.
Because your definition of "Value" is uncontroversial and customary, unlike your definition of "linear graph"--I have met it in your article for the first time. Granted, my knowledge is limited but that's my point exactly: if you bother to introduce the most basic concepts that your readers are most likely already accustomed with, then also please introduce the advanced concepts that you're about to discuss. If you feel that it makes the article too long, maybe consider removing the trivial definitions of the basic concepts, but not the other way around.
I don't want to come off sounding aggressive or rude, and in fact I've read some other articles on your site with great interest, but this particular one leaves a bit of a taste of a maths article written by a crackpot: it starts with talking about what is a number, what is addition, talks about how numbers can also be multiplied and divided, a-a-a-and then in a blink of an eye it goes into very remoted areas of the number theory which may not actually exist (at least Googling them doesn't show anything relevant).
In fact, googling "linear hierarchy" suggests that it's a term from biology, and it doesn't describe a graph or a tree at all: "In a linear hierarchy, there is one individual who dominates all the other group members, a second who dominates all but the top individual, and so on, down to the last individual who dominates no one" (Ivan D. Chase, Kristine Seitz, "Aggression", in Advances in Genetics, 2011). So "linear hierarchy" is apparently a linear (or "total", as it's also called) order, and it's actually consistent with the customary definition of "linear data structure": the one that arranges it's elements in a sequence, so arrays and linked lists (in fact, those used to be called "linear lists", see Wirth's "Algorithms + Data Structures = Programs" from the seventies) are linear data structures, but trees and graphs are not.
To sum it: your usage of the term "linear" seems to be novel, and so it's confusing for someone who hasn't met it already, and arguably most of the readers haven't, maybe define it, even at the expense of defining what a "value" or an "agent" is? Those words you use in their customary senses.
That gave me a good laugh! I do understand the issue and I am not a brilliant writer in this regard. I was trying to make it understandable to the average programmer but also be at least "correct", and I think I have kind of failed at both in this article. I wanted to make sure that the ideas I was trying to express made sense not just to me or in speech form, but in written form too. I added all those definitions, including "value", because I know so many people who use the terms "value" and "object" interchangeably and assume all values are "objects" in the OOP sense. So I wanted to make a distinction between the two, as I wanted to emphasize the object-ness as the key relationship, not the value-ness.
I am quite interested in how people build mental models of things and how they think about programming in general, but there is very little on the topic currently. And ownership semantics (even the name alone) has a lot of implicit assumptions tagged along to it that I wanted to understand. In sum, "ownership" is the wrong word but oh well, silly history.
And yes, "linear hierarchy" does come from biology. It does mean "linear order" in that sense. That is a much better way of explaining it succinctly.
Interesting you brought up Wirth, since he is one of my idols and that book is absolutely amazing. I always recommend Wirth to beginners wanting to learn how to write compilers.
My guess is that he's just explicitly acknowledging the Commonwealth English preference for using the verb "to orientate" to mean "to focus/to position", while on the other hand the verb "to orient" is traditionally understood as literally meaning to orientate something in an easterly (=oriental) direction.
I'm a British English speaker, I use the verb "to orientate", but "object-orientated programming" still sounds unnatural to me. It's a bit like "program" and "programme"–we use "program" for software, "programme" for everything else.
I have to comment this, being myself a multi-class character (both computer science and philosophy graduate). The confusion seen here is quite common when somebody without a proper philosophy background is trying to hold a discourse on abstract philosophical topics. Obviously it happens often in philosophy, but often due to the outsiders (computer scientists, physicists, sociologists, artists) who believe, they have revolutionary ideas ;) Wittgenstein's (or rather Kripkenstein's, depending on the interpretation) were rather of a different, more profound, nature.
In my opinion author has decent ideas but lacks skills in communication to express them properly.
> because the facts of problems to be solved and, moreso, of the physical machines we use in solving them provide ground truth.
It is a very optimistic view of the programming as a knowledge domain. IMHO in real life "The facts of problems" are often very blurry and prone to similar problems seen in the philosophy. I am not talking about academic toy problems, but real-life problems that have to be solved.
I do enjoy reading philosophy but there is very little in terms of "philosophy of programming" in order to have a common language to talk about. I could either go full mathematical and most people will not know what I am talking about, or go full example based, but then lose the essence of the problem.
What I wanted to say is that ownership semantics can only deal with "linear" problems whilst most problems are "non-linear" in nature. And that designing an entire language around this idea to ensure "safety", especially without it being "proven" in a smaller language, is/was very risky and dodgy.
I also wanted to explain the mentality that many (not all) people have with regards to ownership semantics and how it regards to a certain concept of "agency", and how it is related (not the same) as the OOP mentality.
P.S. The original commenter is confused about my views, and made mistakes about what I stated. https://news.ycombinator.com/item?id=24999902
You make a good point, however:
1) > And that designing an entire language around this idea to ensure "safety", especially without it being "proven" in a smaller language, is/was very risky and dodgy
It's not exactly true that ownership models weren't "proven" in different languages. Objective-C comes from the top of my head; the main memory management technique there was reference counting (with the memory pool/manual management fallback). And yes, the non-linearity of some structures was a pain in the ass, one had to be careful to not create a "strong reference loop", but... in the end it worked quite well :) The difference is that in Obj-C one had to do it manually/in runtime, Rust checks it automatically/during compilation.
2) quoting your article "Ownership semantics [...] cannot be used to express non-linear problems".
This is a very strong claim. What does it mean for the problem to be non-linear? I would say, that linearity (in programming) may be ascribed to a model of the problem, not the problem itself, i.e. Traveling Salesman Problem is a problem involving a non-linear structure and still the best known solvers (e.g. Concorde) use linear models to solve it.
It is true that ownership semantics has to be bypassed in the non-linear model, but the question stays whether the given problem really requires one.
I have to agree with the author that ownership is a tail that should not be allowed to wag the language dog.
In the article, I define inheritance as the following:
> Most people generally view inheritance as a combination of subtyping and dynamic dispatch through virtual method tables (vtables).
So I did not confuse anything between regular and virtual member functions.
You have made a lot of assumptions about my views which are not even in the text.
And I agree Computer Science is very much not a science in the natural sense. I do with many more people would either say it is just mathematics (formal science) or start giving empirical evidence for their claims that "X is the best way to Y" (natural science).