15
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ Lobster does this, I think $\endgroup$
    – user
    May 20, 2023 at 16:11
  • 1
    $\begingroup$ @user Nice one ─ I found a summary of the algorithm Lobster uses here, 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. $\endgroup$
    – kaya3
    May 20, 2023 at 16:49

2 Answers 2

9
$\begingroup$

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¹ 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². 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.

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

$\endgroup$
5
$\begingroup$

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, 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...

$\endgroup$
11
  • 1
    $\begingroup$ "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? $\endgroup$
    – kaya3
    May 21, 2023 at 8:27
  • 2
    $\begingroup$ 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. $\endgroup$
    – kaya3
    May 21, 2023 at 9:03
  • 3
    $\begingroup$ I know this isn't Stack Overflow, but... what's with all the emojis? Are they really communicating anything of essence? meta.stackoverflow.com/q/378226/11107541 $\endgroup$
    – starball
    May 21, 2023 at 18:58
  • 1
    $\begingroup$ 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? $\endgroup$ Jun 27, 2023 at 20:29
  • 1
    $\begingroup$ @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. $\endgroup$ Jun 28, 2023 at 8:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .