Could ownership be inferred?

Question

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.

Answer 1

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}

Answer 2

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