<p>Rust famously has the concept of ownership vs. borrowing as part of its type system. This allows some level of automatic memory management ─ that is, heap allocations are freed when their owner goes out of scope without being moved to another owner ─ without the programmer having to explicitly <code>free</code> anything, and with guarantees about memory safety, and without the need for reference counting or a full garbage collector.</p>
<p>In exchange for these benefits, however, the programmer must use type annotations to decide which values are owned and which values are borrowed. For example, <code>Foo</code> is an owned type whereas <code>&amp;Foo</code> or <code>&amp;mut Foo</code> are borrowed. Would it be feasible ─ in at least some cases ─ for a language to let the programmer just write <code>Foo</code> everywhere, and for the compiler to infer which occurrences should be owned and which should be borrowed? If so, what rules could the compiler use to determine this?</p>
<p>I am thinking about this in the context of a language like Java, where all non-primitive values semantically behave like references, but a sufficiently clever compiler might be able to eliminate some of these references by embedding objects directly within their owners. This could improve performance through less indirection and less work for the garbage collector.</p>

<compilers><ownership><memory-safety><memory-management>
Could ownership be inferred?
CC BY-SA 4.0
2023-05-20T16:11:58.207Z
[Lobster](https://strlen.com/lobster/) does this, I think
user
CC BY-SA 4.0
2023-05-20T16:49:00.423Z
@user Nice one ─ I found a summary of the algorithm Lobster uses [here](http://aardappel.github.io/lobster/memory_management.html), it's very relevant to this question. If someone understands this algorithm already, it would make for a good answer; otherwise I'll investigate it more myself and maybe write an answer in a few days.
kaya3
<p>In the general case — no, of course it cannot!  And there are several reasons for that.</p>
<p>First, the very pragmatic reason is that ownership is a <em>design decision</em> of yours as a programmer. You can decide to own everything and copy everything as needed — there's nothing inherently wrong with it, as long as it fits your requirements. From this perspective borrowing is unnecessary at all, a kind of manual optimization you <em>might</em> chose to implement. On the other hand you might have a particular requirement or other strong reason to have a <em>reference</em> in a certain part of your program, and thus <em>borrow</em> it. In that case design kinda flips and you want to architect the rest of your program in a way this particular reference (or set of references) stays <em>valid</em> during all the possible executions.</p>
<p>As long as a compiler can't read your mind it can't decide which option you want and what to infer, and what to change. </p>
<p>Second, if we're talking about <em>static</em> inference, essentially <em>type</em> inference, the question boils down to the properties of a logic system we employ. For ownership reasoning we need some kind of a <a href="https://en.wikipedia.org/wiki/Substructural_logic" rel="noreferrer">substructural logic</a>, and any such logic expressive enough for practical programming is bound to be undecidable (in general, only pretty simple and constrained logics are decidable, unfortunately). So ownership inference is even theoretically impossible. </p>
<p>But that's from the perspective of general sound ownership inference. If we're talking about &quot;ownership inference&quot; as a possible local compiler optimization, then yeah, compilers do it for ages. Unpacking structures and objects on the stack, passing fields through registers, escape analysis in general and so on...</p>

CC BY-SA 4.0
2023-05-21T08:16:16.910Z
2023-05-21T08:16:16.910Z
Alex Chichigin
CC BY-SA 4.0
2023-05-21T08:27:42.983Z
"Copying everything as needed" ─ this only works if all objects are immutable and object identity doesn't matter. Mutating a copy won't affect the owner's copy of the same data, but mutating via a reference will, so these are not semantically equivalent. The question is, if you start from the position that *everything* is a reference ─ as Java and similar languages do ─ then can you choose an owner for each reference, or at least for some references, and if so how?
kaya3
CC BY-SA 4.0
2023-05-21T08:58:48.863Z
"this only works if all objects are immutable and object identity doesn't matter" — this works as long as it fits your requirements and your _design_ accounts for it. :)
Alex Chichigin
CC BY-SA 4.0
2023-05-21T08:59:21.697Z
But it doesn't fit the requirements, as stated in the question. And even with only immutable objects, something like like `Box`, `Vec` or `String` in Rust cannot implement `Copy` safely because they own heap allocations which must be deallocated when the owning object is dropped; so you would have to have strict immutability but also make deep copies of nested data structures, which is a strange combination (usually, deep copies are only used to avoid unwanted mutation).
kaya3
CC BY-SA 4.0
2023-05-21T09:03:29.507Z
@kaya3 I don't understand what you don't understand about my answer. :) Most likely I didn't understand your question. But in particular I don't understand what you don't understand about undecidability argument, and if you already learned about escape analysis in compilers and its limitations.
Alex Chichigin
CC BY-SA 4.0
2023-05-21T09:03:50.520Z
I'm not saying I don't understand your answer. I'm saying it doesn't answer the question. Regarding undecidability, the exact same argument could be made against type inference and yet nobody says that is impossible; you just have a conservative checker that only approves programs that it *can* decide are correct, or a conservative inference engine that gives an error when it can't infer.
kaya3
CC BY-SA 4.0
2023-05-21T18:58:44.607Z
I know this isn't Stack Overflow, but... what's with all the emojis? Are they really communicating anything of essence? https://meta.stackoverflow.com/q/378226/11107541
starball
CC BY-SA 4.0
2023-05-24T05:52:25.340Z
@starball that's just me trying to be friendly... and failing miserably!  Oh wait, are emojis acceptable in comments?  Anyway, thanks for the link to discussion, I'll read it and reconsider my use of emojis.
Alex Chichigin
CC BY-SA 4.0
2023-06-27T20:29:58.430Z
I'm not sure I understand what you mean by ownership being a design decision. How does the compiler have to read my mind? Isn't the goal perfectly objective, to minimize how many clones are needed in favor of references, and minimize the lifetimes of those references without creating the possibility of a dangling pointer?
rydwolf
CC BY-SA 4.0
2023-06-28T08:39:13.693Z
@RydwolfPrograms a compiler can't read your mind, that's why in Rust (and other languages) you have to put explicit annotations on what you want owned, and what you want borrowed. And you decide what and where you want owned, and what and where — borrowed, a compiler merely _checks_ the requirements of different parts of code are compatible. Similarly, I can't see how a _compiler_ can minimize "how many clones are needed", and whether it should in the first place. You as a programmer might _decide_ to minimize. Or decide against it.
Alex Chichigin
CC BY-SA 4.0
2023-06-28T19:21:23.733Z
@AlexChichigin But I don't get why I need to be the one who decides what is the owner and what's a reference; why can't the compiler look at some code written the way you'd write it for a GC lang, and decide where to add borrows to make it compile?
rydwolf
CC BY-SA 4.0
2023-06-30T14:12:29.947Z
@RydwolfPrograms because of https://en.wikipedia.org/wiki/Rice's_theorem An object (a piece of memory) life-time is a runtime property, thus you can't (precisely) figure it out _before_ the runtime.
Alex Chichigin
<p>This question is complicated by exactly what we mean by &quot;ownership&quot;. There are several different models of ownership in the literature, each with different implications (owners-as-dominators, owners-as-modifiers, owners-as-accessors, dynamic ownership, multiple ownership, ...), each has generally been imposing a correctness concept on the object graph, and what <em>Rust</em> has doesn't match any of them. On the other hand, they have largely been envisaging Java-like systems, so they are a semantic match here.</p>
<p>The <a href="https://dl.acm.org/doi/pdf/10.1145/286936.286947" rel="noreferrer">work that originally introduced the concept of ownership types</a>¹ noted:</p>
<blockquote>
<p>It is nonsensical to infer which objects are representation; such information is part of the programmer’s intention.</p>
</blockquote>
<p>In this perspective, to own an object is to have it as part of your inner representation, and that can only be a design choice: it's a correctness constraint on unauthorised state changes. There's no way to detect what is inherent to the object, and so outside access is an error, and what is intended to be an external shared value, and so outside access is expected. For rejecting incorrect programs, some imposed idea of what is correct is required, and this is why &quot;ownership inference&quot; is sometimes seen as a contradiction in terms.</p>
<p>Nonetheless, <strong>there <em>have</em> been ownership-inference systems</strong>, notably Huang et al. at ECOOP 2012 <a href="https://doi.org/10.1007/978-3-642-31057-7_9" rel="noreferrer"><em>Inference and Checking of Object Ownership</em></a>². This approach infers many valid typings across the whole (Java) program based on how values are accessed, and attempts to choose the &quot;best&quot; one. This generation exhaustively produces the consistent ownership annotations the program permits and winnows them down to one. The heuristic for &quot;best&quot; is about finding a deep ownership tree, seen as providing the best encapsulation, then choosing the tightest modifiers.</p>
<p>A key element is that <strong>it will be wrong if the program is</strong>, or at least a more general owner will be inferred than the programmer may have intended. However, for the compilation optimisation case that it seems you're interested in, this could well be good enough! As long as it identifies <em>some</em> inlineable objects, that's an improvement.</p>
<p>This system supported both -dominators (classical ownership) and -modifiers models, with only very rare annotations in the former case and none in the latter. Owners-as-dominators specifically prohibits all incoming pointers, so these are strong inlining candidates. The inference system occasionally requires programmer input to resolve conflicts here, which could come from explicit manual annotations, but they estimate these at six per thousand lines of code. They give 40% of all objects as being representation, though not all of these are likely to be real inlining candidates, so that is a cap on how much impact there could be. The actual tool (for Java) is available <a href="https://www.cs.rpi.edu/%7Ehuangw5/cf-inference/" rel="noreferrer">here</a>.</p>
<p>Subsequent work has investigated other variants, immutability, and more interactive systems. Feeding back run-time information to the compiler may also give useful information about what arises in practice, which could inform automatic inference or determine layout itself. All ownership systems may be imposing more structure on the program than you want for purely identifying inlineable or GC-excluded objects, rather than correctness or concurrency-safe code, but the other properties they provide may be useful as well.</p>
<hr />
<p>¹<sub>David G. Clarke, John M. Potter, and James Noble. 1998. Ownership types for flexible alias protection. In Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications (OOPSLA '98). Association for Computing Machinery, New York, NY, USA, 48–64. <a href="https://doi.org/10.1145/286936.286947" rel="noreferrer">https://doi.org/10.1145/286936.286947</a></sub></p>
<p>²<sub>Huang, W., Dietl, W., Milanova, A., Ernst, M.D. (2012). Inference and Checking of Object Ownership. In: Noble, J. (eds) ECOOP 2012 – Object-Oriented Programming. ECOOP 2012. Lecture Notes in Computer Science, vol 7313. Springer, Berlin, Heidelberg. <a href="https://doi.org/10.1007/978-3-642-31057-7_9" rel="noreferrer">https://doi.org/10.1007/978-3-642-31057-7_9</a></sub></p>

CC BY-SA 4.0
2023-05-28T23:42:11.437Z
2023-05-28T23:42:11.437Z
Michael Homer
# Could ownership be inferred?
Posted by: username_0 on 2023-05-20
Rust famously has the concept of ownership vs. borrowing as part of its type system. This allows some level of automatic memory management ─ that is, heap allocations are freed when their owner goes out of scope without being moved to another owner ─ without the programmer having to explicitly `free` anything, and with guarantees about memory safety, and without the need for reference counting or a full garbage collector.

In exchange for these benefits, however, the programmer must use type annotations to decide which values are owned and which values are borrowed. For example, `Foo` is an owned type whereas `&Foo` or `&mut Foo` are borrowed. Would it be feasible ─ in at least some cases ─ for a language to let the programmer just write `Foo` everywhere, and for the compiler to infer which occurrences should be owned and which should be borrowed? If so, what rules could the compiler use to determine this?

I am thinking about this in the context of a language like Java, where all non-primitive values semantically behave like references, but a sufficiently clever compiler might be able to eliminate some of these references by embedding objects directly within their owners. This could improve performance through less indirection and less work for the garbage collector.
**Tags:** compilers ownership memory-safety memory-management
> **Comments:**
> **username_1**: [Lobster](https://strlen.com/lobster/) does this, I think  
> **username_0**: @user Nice one ─ I found a summary of the algorithm Lobster uses [here](http://aardappel.github.io/lobster/memory_management.html), it's very relevant to this question. If someone understands this algorithm already, it would make for a good answer; otherwise I'll investigate it more myself and maybe write an answer in a few days.  
---
## 2 answers
### Answer by username_5 on 2023-05-28. Score: 9 | Accepted answer
This question is complicated by exactly what we mean by "ownership". There are several different models of ownership in the literature, each with different implications (owners-as-dominators, owners-as-modifiers, owners-as-accessors, dynamic ownership, multiple ownership, ...), each has generally been imposing a correctness concept on the object graph, and what *Rust* has doesn't match any of them. On the other hand, they have largely been envisaging Java-like systems, so they are a semantic match here.

The [work that originally introduced the concept of ownership types](https://dl.acm.org/doi/pdf/10.1145/286936.286947)¹ noted:

> It is nonsensical to infer which objects are representation; such information is part of the programmer’s intention.

In this perspective, to own an object is to have it as part of your inner representation, and that can only be a design choice: it's a correctness constraint on unauthorised state changes. There's no way to detect what is inherent to the object, and so outside access is an error, and what is intended to be an external shared value, and so outside access is expected. For rejecting incorrect programs, some imposed idea of what is correct is required, and this is why "ownership inference" is sometimes seen as a contradiction in terms.

Nonetheless, **there *have* been ownership-inference systems**, notably Huang et al. at ECOOP 2012 [*Inference and Checking of Object Ownership*](https://doi.org/10.1007/978-3-642-31057-7_9)². This approach infers many valid typings across the whole (Java) program based on how values are accessed, and attempts to choose the "best" one. This generation exhaustively produces the consistent ownership annotations the program permits and winnows them down to one. The heuristic for "best" is about finding a deep ownership tree, seen as providing the best encapsulation, then choosing the tightest modifiers.

A key element is that **it will be wrong if the program is**, or at least a more general owner will be inferred than the programmer may have intended. However, for the compilation optimisation case that it seems you're interested in, this could well be good enough! As long as it identifies *some* inlineable objects, that's an improvement.

This system supported both -dominators (classical ownership) and -modifiers models, with only very rare annotations in the former case and none in the latter. Owners-as-dominators specifically prohibits all incoming pointers, so these are strong inlining candidates. The inference system occasionally requires programmer input to resolve conflicts here, which could come from explicit manual annotations, but they estimate these at six per thousand lines of code. They give 40% of all objects as being representation, though not all of these are likely to be real inlining candidates, so that is a cap on how much impact there could be. The actual tool (for Java) is available [here](https://www.cs.rpi.edu/%7Ehuangw5/cf-inference/).

Subsequent work has investigated other variants, immutability, and more interactive systems. Feeding back run-time information to the compiler may also give useful information about what arises in practice, which could inform automatic inference or determine layout itself. All ownership systems may be imposing more structure on the program than you want for purely identifying inlineable or GC-excluded objects, rather than correctness or concurrency-safe code, but the other properties they provide may be useful as well.

---

¹David G. Clarke, John M. Potter, and James Noble. 1998. Ownership types for flexible alias protection. In Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications (OOPSLA '98). Association for Computing Machinery, New York, NY, USA, 48–64. <https://doi.org/10.1145/286936.286947>

²Huang, W., Dietl, W., Milanova, A., Ernst, M.D. (2012). Inference and Checking of Object Ownership. In: Noble, J. (eds) ECOOP 2012 – Object-Oriented Programming. ECOOP 2012. Lecture Notes in Computer Science, vol 7313. Springer, Berlin, Heidelberg. <https://doi.org/10.1007/978-3-642-31057-7_9>
---
### Answer by username_2 on 2023-05-21. Score: 5
In the general case — no, of course it cannot! And there are several reasons for that.

First, the very pragmatic reason is that ownership is a *design decision* of yours as a programmer. You can decide to own everything and copy everything as needed — there's nothing inherently wrong with it, as long as it fits your requirements. From this perspective borrowing is unnecessary at all, a kind of manual optimization you *might* chose to implement. On the other hand you might have a particular requirement or other strong reason to have a *reference* in a certain part of your program, and thus *borrow* it. In that case design kinda flips and you want to architect the rest of your program in a way this particular reference (or set of references) stays *valid* during all the possible executions.

As long as a compiler can't read your mind it can't decide which option you want and what to infer, and what to change.

Second, if we're talking about *static* inference, essentially *type* inference, the question boils down to the properties of a logic system we employ. For ownership reasoning we need some kind of a [substructural logic](https://en.wikipedia.org/wiki/Substructural_logic), and any such logic expressive enough for practical programming is bound to be undecidable (in general, only pretty simple and constrained logics are decidable, unfortunately). So ownership inference is even theoretically impossible.

But that's from the perspective of general sound ownership inference. If we're talking about "ownership inference" as a possible local compiler optimization, then yeah, compilers do it for ages. Unpacking structures and objects on the stack, passing fields through registers, escape analysis in general and so on...
> **Comments:**
> **username_0** (2023-05-21): "Copying everything as needed" ─ this only works if all objects are immutable and object identity doesn't matter. Mutating a copy won't affect the owner's copy of the same data, but mutating via a reference will, so these are not semantically equivalent. The question is, if you start from the position that *everything* is a reference ─ as Java and similar languages do ─ then can you choose an owner for each reference, or at least for some references, and if so how?  
> **username_2** (2023-05-21): "this only works if all objects are immutable and object identity doesn't matter" — this works as long as it fits your requirements and your _design_ accounts for it. :)  
> **username_0** (2023-05-21): But it doesn't fit the requirements, as stated in the question. And even with only immutable objects, something like like `Box`, `Vec` or `String` in Rust cannot implement `Copy` safely because they own heap allocations which must be deallocated when the owning object is dropped; so you would have to have strict immutability but also make deep copies of nested data structures, which is a strange combination (usually, deep copies are only used to avoid unwanted mutation).  
> **username_2** (2023-05-21): @kaya3 I don't understand what you don't understand about my answer. :) Most likely I didn't understand your question. But in particular I don't understand what you don't understand about undecidability argument, and if you already learned about escape analysis in compilers and its limitations.  
> **username_0** (2023-05-21): I'm not saying I don't understand your answer. I'm saying it doesn't answer the question. Regarding undecidability, the exact same argument could be made against type inference and yet nobody says that is impossible; you just have a conservative checker that only approves programs that it *can* decide are correct, or a conservative inference engine that gives an error when it can't infer.  
> **username_3** (2023-05-21): I know this isn't Stack Overflow, but... what's with all the emojis? Are they really communicating anything of essence? https://meta.stackoverflow.com/q/378226/11107541  
> **username_2** (2023-05-24): @starball that's just me trying to be friendly... and failing miserably!  Oh wait, are emojis acceptable in comments?  Anyway, thanks for the link to discussion, I'll read it and reconsider my use of emojis.  
> **username_4** (2023-06-27): I'm not sure I understand what you mean by ownership being a design decision. How does the compiler have to read my mind? Isn't the goal perfectly objective, to minimize how many clones are needed in favor of references, and minimize the lifetimes of those references without creating the possibility of a dangling pointer?  
> **username_2** (2023-06-28): @RydwolfPrograms a compiler can't read your mind, that's why in Rust (and other languages) you have to put explicit annotations on what you want owned, and what you want borrowed. And you decide what and where you want owned, and what and where — borrowed, a compiler merely _checks_ the requirements of different parts of code are compatible. Similarly, I can't see how a _compiler_ can minimize "how many clones are needed", and whether it should in the first place. You as a programmer might _decide_ to minimize. Or decide against it.  
> **username_4** (2023-06-28): @AlexChichigin But I don't get why I need to be the one who decides what is the owner and what's a reference; why can't the compiler look at some code written the way you'd write it for a GC lang, and decide where to add borrows to make it compile?  
> **username_2** (2023-06-30): @RydwolfPrograms because of https://en.wikipedia.org/wiki/Rice's_theorem An object (a piece of memory) life-time is a runtime property, thus you can't (precisely) figure it out _before_ the runtime.  
---
