Longer-lived borrows

[mark-koch]

The Problem

Currently, Guppy only allows borrowing of values for the scope of a function call. In particular, we don't allow returning borrowed values or storing them in data structures.

We made this restriction to avoid Rust-style lifetime annotations, however it is quite annoying sometimes:

def foo[n: nat](qs: array[qubit, n]) -> None: ...

def bar(q1: qubit, q2: qubit):
    foo(array(q1, q2))  # error: not allowed to move borrowed q1, q2

Calling foo is impossible since we're not allowed to pack the borrowed qubits into an array.

Similarly, we run into this issue when trying to implement the "iterators without ownership" language feature:

def foo(qs1: array[qubit, 10], qs2: array[qubit, 10]) -> None:
    for q1, q2 in zip(qs1, qs2):
        cx(q1, q2)

Constructing the zip iterator would require borrowing qs1 and qs2 for the duration of the entire loop which is not possible using the current borrowing semantics.

Luckily, I think I came up with a way to solve these problems without requiring lifetime annotations!

Proposal

Basic Example

We add a new @borrows annotation for function return types that specifies that the returned value contains some borrowed inputs:

@guppy.struct
class MyStruct:
    q: qubit
    x: int

@guppy
def foo(q: qubit) -> MyStruct @borrows(q):
    h(q)
    # We're allowed to treat q like an owned value since it's mentioned
    # in the `@borrows` annotation
    r = q
    return MyStruct(r, 42)

Whenever the user writes a function with an @borrows return annotation, we also force them to register a second function that "unborrows" the value (better name suggestions welcome :D).

@guppy.unborrow(foo)
def _foo_unborrow(v: MyStruct @owned) -> qubit:
    return v.q

Calls to foo will only be allowed in borrowed positions:

@guppy
def bar(s: MyStruct) -> None: ...

@guppy
def baz(q: qubit) -> None:
    bar(foo(q))  # Ok!
    s = foo(q)  # error: not allowed to move out of borrow

The compiler desugars the bar(foo(q)) call into

_s = foo(q)
_s = bar(_s)
q = _foo_unborrow(_s)

Need for unborrow function

Note that the unborrow function needs to be user-provided and cannot be inferred by the compiler in general:

@guppy
def foo(q1: qubit, q2: qubit, b: bool) -> tuple[qubit, qubit] @borrows(q1, q2):
    return (q1, q2) if b else (q2, q1)

Here, the unborrow logic depends on runtime information:

@guppy.unborrow(foo)
def _foo_unborrow(v: tuple[qubit, qubit] @owned, b: bool) -> tuple[qubit, qubit]:
    return v if b else (v[1], v[0])

Of course, the user could provide an unborrow implementation that is incorrect, in which case they would get unexpected semantics. We shouldn't try to validate the user implementation and just take it at face value. If it's wrong then it's the user's fault!

Performance

Note that the computation inside unborrow functions should ideally be cheap. Indeed, all cases I'm thinking of that are needed for the standard library just involve unpacking a struct or index into an array.

Of course the system could also be abused and imo it wouldn't be worth trying to prevent that - if the user decides to write an unborrow function with bad time complexity, then they're responsible for the performance hit.

Standard Library

In general, I'm envisioning this as an advanced feature that is mostly only used in the standard library. E.g. having borrowing versions of array and tuple constructors as well as iterator combinators would already go a long way in improving usability, without the users having to write unborrow functions themselves.

Importantly, these alternative array constructor should borrow all passed inputs - we can't handle arrays containing a mix of borrowed and owned values.

Structs

We could also consider similar annotations on struct types:

@guppy.struct
class MyStruct:
    x: int
    q: qubit @borrowed

In that case, the auto-generated constructor would have the following signature:

@guppy
def __new__(x: int, q: qubit) -> MyStruct @borrows(q): ...

@guppy.unborrow(__new__)
def _unborrow___new__(val: MyStruct @owned, x: int) -> qubit:
    return val.q

Non-borrowed Inputs

As seen in the previous examples, we should also allow @borrows functions to take other inputs. However, there is the following question:

Should we allow other non-copyable + owned inputs?

If we allow this, then they must be removed from the signature of the unborrow function - otherwise we wouldn't be able to emit the unborrow call since the previous value has been consumed!

@guppy
def foo(q1: qubit, q2: qubit @owned) -> qubit @borrows(q1):
    discard(q2)
    return q1

@guppy.unborrow(foo)
def foo_unborrow(val: qubit) -> qubit:  # No second qubit here!
    return val

Connection to Subscripts

Note that this proposal basically generalises the current system we have for borrowing out of subscripts. When borrowing x[idx], we call x.__getitem__(idx) and make sure that the "unborrow function" x.__setitem__ is called when the borrow expires.

Implementation-wise, this means that this feature probably wouldn't be that much work, we just need to generalise the SubscriptAccess place to work for arbitrary pairs borrow-unborrow functions.

Connection to Aeneas

This proposal is actually equivalent to what Aeneas is doing: They show how lifetime annotations in Rust code can be used to automatically generate these unborrow functions. We're doing it the other way around: We make people write unborrow functions so they don't have to deal with lifetime annotations.

Assigning Borrowed Values

An optional orthogonal extension would be to allow assigning borrowed values. This is motivated by the fact that following would still fail to compile following the proposal up to this point:

def foo[n: nat](qs: array[qubit, n]) -> None: ...

def bar(q1: qubit, q2: qubit):
    qs = array(q1, q2)  # error: not allowed to move array
    foo(qs)

Instead, we would have to call foo(array(q1, q2)). Allowing assignments of borrowed values to temporary variables would make things more convenient.

However, this would require some significant changes to the borrow checker. Some relevant literature from Rust:

• Non-lexical lifetimes: https://rust-lang.github.io/rfcs/2094-nll.html
• Region inference: https://rustc-dev-guide.rust-lang.org/borrow_check/region_inference.html

I think this would be a good idea longer term, but I need to think more about it before making a concrete proposal.

[hkengo-qtnm]

This sounds like a great idea!
You can also write a one-line-circuit with this notation

q = H(X(qubit()))

by defining X and H using @borrows notation like:

@guppy
def X(q: qubit) -> qubit @borrows(q): ...
@guppy
def H(q: qubit) -> qubit @borrows(q): ...

with the trivial unborrowing:

@guppy.unborrow(X)
def _X_unborrow(q: qubit @owned) -> qubit:
    return q
@guppy.unborrow(H)
def _H_unborrow(q: qubit @owned) -> qubit:
    return q

Can we also consider adding built-in higher-order function with_owned that takes def f(x: T) -> None and return def f'(x: T) -> T @borrows(x) with the trivial identity unborrowing, so that we can just write as

q = with_owned(h)(with_owned(x)(qubit()))

without user-defined X or H? Or can we define something like @borrows.trivial to indicate that unborrowing does nothing?

[tatiana-s]

I really like the idea in general, though I think having to provide a function to unborrow (maybe return_borrow?) might end up with a lot of "boilerplate" code for trivial returns - but I think this is fine for a mainly advanced feature for library writing!

[mark-koch]

Maybe we could have a special rule where the trivial unborrow function can be inferred if we have -> T @borrows(x) where also x: T?

[ss2165]

Great idea. Question: it is not obvious to me what the type of the unborrows function is supposed to be? In the case of return (q1, q2) if b else (q2, q1) it also needs to take the b parameter. Can it take any subset of the parameters of the original function, or is it that it has to take the @borrows annotated return type + the remaining parameters of not included inside the @borrows?

[mark-koch]

Let's say the original function has a combination of the following:

1. takes some non-copyable owned inputs
2. takes some non-copyable borrowed inputs that are mentioned in @borrows
3. takes some non-copyable borrowed inputs that are not mentioned in @borrows
4. takes some copyable inputs (always owned!)
5. returns any output

The unborrow function will:

• Take owned inputs (4, 5) and borrowed inputs (3)
• Return (2)

The question I alluded to in the "Non-borrowed Inputs" section is whether we should allow (1) even though it won't be given to the unborrow function. I can't think of a situation where this would be useful, on the other hand allowing it also wouldn't hurt.

[mark-koch]

Example: array.__getitem__ has:

1. N/A
2. N/A
3. the array
4. the index
5. the extracted element

Consequently, array.__setitem__ takes the borrowed array (3), the index (4), the element (5), and returns nothing (2)

[nicolaassolini-qntm]

I like this idea, and I think there’s even more we could explore here.

Consider the example:

@guppy.struct
class MyStruct:
    q: qubit
    x: int

@guppy
def foo(q: qubit) -> MyStruct @borrows(q):
    h(q)
    # We're allowed to treat q as owned, since it's listed in @borrows
    r = q
    return MyStruct(r, 42)

@guppy
def bar(s: MyStruct) -> None: ...

@guppy
def baz(q: qubit) -> None:
    bar(foo(q))  # Ok!

Desugared, this expands roughly to:

_s = foo(q)
_s = bar(_s)
q = _foo_unborrow(_s)

The inline notation here is essentially encoding Rust-like lifetime information. So why not allow this directly, without requiring annotations?

Rewriting the previous example, the intent becomes clearer:

@guppy
def baz(q: qubit) -> None:
    # q is available
    ...

    s = foo(q)   # s is now live
    
    ...         # q is not allowed here

    bar(s)       # last use of s
    # q becomes usable again here

This mirrors Rust’s lifetime model: the lifetime of s must be strictly within that of q, and q cannot be used while s is live. It should be straightforward for the compiler to enforce this, and I think it would be quite useful.

We might even express this explicitly with a with block:

@guppy
def baz(q: qubit) -> None:
    # q is available
    ...

    with s = foo(q):   # s is live within this block
        ...
        
        bar(s)         # last use of s

    # q is available again here
    measure(q)

[mark-koch]

So why not allow this directly, without requiring annotations?

Which annotations should be dropped, can you elaborate?

We might even express this explicitly with a with block:

Assignment in with is not allowed by Python's grammar

[nicolaassolini-qntm]

Which annotations should be dropped, can you elaborate?

I was referring to Rust lifetime in general, the idea is to get lifetime info automatically (keep the @ borrows in the functions)

Assignment in with is not allowed by Python's grammar

yes, sorry, we should have with foo(q) as s: instead

[mark-koch]

I was referring to Rust lifetime in general, the idea is to get lifetime info automatically (keep the @ borrows in the functions)

Yes, that was the intention with this proposal! However, note that these "unborrow functions" essentially encode the same information as lifetime annotations. In particular, see this reference: https://dl.acm.org/doi/10.1145/3547647

yes, sorry, we should have with foo(q) as s: instead

Sure, but I don't see what this gives you over just writing s = foo(q) and inferring the borrow lifetime automatically? We can essentially do the same as Rust's automatic region inference

[nicolaassolini-qntm]

Sure, but I don't see what this gives you over just writing s = foo(q) and inferring the borrow lifetime automatically? We can essentially do the same as Rust's automatic region inference

Right, the with will be a way just to make the user aware of what is happening, but I think also without the with is good

[GBoydQ]

This would be nice to avoid some of the struct unpacking code I am having to write at the moment.

Would it desirable to add some syntax to give a clue that variables are borrowed? E.g. in an above example, it is not necessarily clear from the callsite that this is happening. Maybe there is no pythonic way to do this other than with

@guppy
def baz(q: qubit) -> None:
    # q is available
    ...

    s = foo(q)   # s is now live
    
    ...         # q is not allowed here

    bar(s)       # last use of s
    # q becomes usable again here

[alexarice]

Would this system allow something like this? (Sorry if I got guppy syntax wrong)

@guppy.struct
class MyStruct:
    b: bool

@guppy
def foo(q: qubit) -> MyStruct @borrows(q):
    h(q)
    # We're allowed to treat q like an owned value since it's mentioned
    # in the `@borrows` annotation, so presumably we can measure it
    b = measure q
    return MyStruct(b)

@guppy.unborrow(foo)
def _foo_unborrow(v: MyStruct @owned) -> qubit:
    # I don't know the syntax but allocate a new qubit here
    return new_qubit