Modelling UniquePtr and SharedPtr

[DmT021]

At some point there will be a need to write bridges to code written in different paradigms. One of the things that will be needed is heap objects and ownership management of them.
I might be completely wrong, but IMO Hylo's value semantics is almost ready to express concepts of UniquePtr and SharedPtr, but not quite yet.
I'd like to discuss approaches to this.

SharedPtr
For SharedPtr it seems everything should be fine. SharedPtr type is handling a side table, in which we store a reference counter and the destination pointer. When SharedPtr is copied it increases the refcounter, when it's deinited it decreases the refcounter, when refcounter reaches 0 - releases the destintion resource. WeakPtr is pretty much the same.
One thing that bothers me is the lack of guarantees about deinit calls. IIUC exit of a variable's lexical scope is not a guaranteed point for deinit call. It could be postponed or be called earlier. It's more or less acceptable, but lexical lifetimes make it easier to reason about lifetime of a resource behind SharedPtr.

UniquePtr
UniquePtr could be expressed as a type with only the Moveable trait implemented, and the Copyable trait is intentionally dropped. But move-only types are pretty much impossible to work with when we don't know at compile time will the value sink or not.

type UniquePtr: Moveable { ... }

fun foo(_ x: [let|sink] UniquePtr) {
  if .random() {
    // do actual sinking operation
  } else {
    // do nothing
  }
}

let ptr: UniquePtr = ...
foo(ptr)

We can't know what passing convention to use here, as it depends on runtime random.
We can overcome this by returning Optional<UniquePtr> with nil if x was actually sinked, or with original x if it wasn't.
But this approach has two inconvenient consequences:

• Return type of functions gets polluted with a bunch of Optionals of unused parameters passed by sink. And it has kinda viral effect.
• We can't guarantee that the passed by sink parameter x and the returned from the call Optional<UniquePtr> are the same value.

A solution I came up with is a new parameter passing convention and a type of binding - sinkable. It's like sink but if by the end of lifetime of a binding it was not used - a special block of code will be invoked. And in this block the source of the binding is restored.

fun foo(_ x: sinkable UniquePtr) {
  if .random() {
    // do actual sinking operation
  } else {
    // do nothing
  }
}

let ptr: UniquePtr = ...
sinkable ptr2 = sink ptr restore {
  // ptr is accessible here again
  // ptr2 isn't accessible
}
foo(ptr2)
// ptr2 isn't accessible, but if it wasn't sinked by the return from `foo` - the `restore` block is invoked.

A sinkable value can be a result of a subscript (or function) call. In this case the restore block is invoked as part of the coroutine continuation.

fun bar(x: sinkable UniquePtr) -> sinkable UniquePtr {
  yield_sinkable x
}

*Note: In this examples:

• sink X restore { ... } is expression that produces a sinkable binding from X
• yield_sinkable is just like the regular yield for inout, but yields sinkable binding.

With this type of binding we can express a method for Optional, that yield itself by mutating to nil, and if the yielded binding wasn't sinked - restores its state.

extension Optional {
inout fun take() -> sinkable Optional<Wrapped> {
  let s = self
  self = nil
  sinkable s2 = sink s restore {
    self = s
  }
  yield_sinkable s2
}

Usage example:

fun foo(_ resource: sinkable UniquePtr) {
  if .random() {
    // consume resource
  }
}


var resource: Optional<UniquePtr> = ... // Just a value

sinkable r = resource.take() // mutate `resource`
// `resource` is still accessible, and equal to nil
if sinkable r2 = r { // optional unwrap
  // `r` isn't accessible anymore
  // `r2` is accessible and has type `UniquePtr`
  foo(r2)
  // `r2` isn't accessible anymore
}

// if `foo` didn't consume the resource, the original `resource` variable will restore its state here.

[lucteo]

Like you said, we are taking about two programming paradigms:

• the one coming from C++, in which we are encouraged to shared data
• the one that Hylo tries to stick to, which tries to follow the law of exclusivity

At the point of SharedPtr and UniquePtr, these two paradigms are not well aligned.

Law of exclusivity says that an object can be mutated only by one part of the code, and while somebody is mutating the object, nobody else can have access to it. That is:

• multiple read access to the objects are fine
• multiple write accesses to the same object are not ok
• a write access with a read access to the same object is not ok.
  Note that having an access to an object counts as having access to all its sub-objects.

A SharedPtr<T> object, by design, breaks the law of exclusivity: multiple parts of the code can have write references to the same object.
See also: https://youtu.be/W2tWOdzgXHA?si=hkGN-opW6qWM9p3y&t=2923. Later in the vide, Sean argues that "a shared pointer is as good as a global variable".

Hylo, imposed rules to prevent these things to happen (on regular, non-unsafe, code).
We can find a lot of examples in which the simple use of shared pointers in a relatively straight-forward way will make local reasoning impossible and will break safety.

UniquePtr is less problematic, but simply copying the C++ interface will still lead to problems with local reasoning and safety.
In Hylo, because by default the law of exclusivity is enforced, there is no need for UniquePtr. Ownership of the objects are straightforward from the definition of the objects.

---

That being said, there are cases in which one need to implement shared caches, in which multiple actors need to read and update, without upholding the law of exclusivity. These can be written by using unsafe keyword.

Following Sean's advice from the video posted above, we should write abstractions for these higher level constructs, and not necessarily for shared pointers.

Hope that makes sense.

[lucteo]

Yes, there are multiple things that require sharing of data. stdout is a good example; in general, everything that is I/O falls into this category. Caches of different forms are also prime examples.

See https://kennethlange.com/functional-core-imperative-shell/ pattern. In general, things that we may want to put in the imperative shell may be hard to implement by following the law of exclusivity.

Note that a shared_ptr<const T> does not break the law.

There are also ways to avoid incidental data structures, which don't break the law. For example, you can model a graph by storing all the nodes in an array, and representing all the links with indices in the array. Modifying parts of a larger object can be done in the spirit of the law of exclusivity if one partitions the data; i.e., in a quick-sort algorithm one would split the access to the array in two slices, and thus the two parts can be accessed independently (instead of sharing the entire array).

[DmT021]

Let's just agree that print is an exception.

I agree. But also GUI, audio, devices, system clocks, some system calls like mmap, and even malloc. Some patterns for improving performance like caches (what @lucteo mentioned) or lazy.

So we're not very keen on the idea of adding sharing utilities to the standard library or as language features. Most of Hylo's guarantees fly out the window when you introduce shared mutation.

Please, don't get me wrong, I'm not trying to convince you to add first class support for heap objects, or something like that. I do like the idea of local reasoning. I'm pretty sure the all business logic could be expressed without losing it.
But I'm affraid we can have different understanding of what is local reasoning? For example, reading a lazy value may or may not mutate the storage behind the wrapper. Does it count as losing local reasoning?

I started this thread with: "there will be a need to write bridges". So I meant that everything that's independent from the outside world is fine, but edge cases are my worry. If the answer is "stick to unsafe code" - I'm totally ok with it, but I though there might be other grades between "completely safe" and "completely unsafe".

Note that a shared_ptr does not break the law.

Yeah, I watched the video. It's pretty good talk and matches my look at architecture.

See https://kennethlange.com/functional-core-imperative-shell/ pattern. In general, things that we may want to put in the imperative shell may be hard to implement by following the law of exclusivity.

This is kinda the pattern I was thinking of as well. But it seems it's most useful when you have more or less equal amount of code in two styles, and relationship is always one way. If you think about implementing a wrapper for WebKit, for example, it will require passing a ton of objects of different kinds back and forth. Something from the WebKit you should own, something you produce will be held by the WebKit.

[lucteo]

The point I'm trying to make is that you can write good abstractions on top of things that will use unsafe features. I believe we can do this for all the things that you mentioned. Some of the things may be more complicated (seems like your WebKit example), in that case, we would need to use unsafe more often, but still doable.

Let me pick the example with mmap/malloc, and, for the sake of argument let's say we are building a memory allocator. We have a set of low-level data structures (common control structure, per-thread control structures, free lists, etc.). It's ok to use unsafe for implementing these abstractions. Then, on top of these, we would provide an API that would not expose to the users unsafe behaviour. For, example, the allocator will provide you exclusive write access to memory whenever a new allocation is requested. That memory buffer can be used like a regular array for the rest of the user code, without breaking the law of exclusivity.

[kyouko-taiga]

I agree. But also GUI, audio, devices, system clocks, some system calls like mmap, and even malloc. Some patterns for improving performance like caches (what @lucteo mentioned) or lazy.

Note that most of what you mentioned are low-level operating system interactions that are likely to require some custom made abstraction to be usable in a high-level language anyway. But I get your point and do not fundamentally disagree.

For example, reading a lazy value may or may not mutate the storage behind the wrapper. Does it count as losing local reasoning?

If the underlying value of the storage can be significant in different places of the program, then yes, you've lost local reasoning. There might be ways to still reason about such shared data structures. For example, I'm pretty convinced that there's a way to reason about monotonic updates, but that is beside the point.

If the laziness only serves to avoid creating unnecessary intermediate data structures (e.g., chaining map applications), then I think we're better off exposing effects to the type system. Hylo has a way to not erase the type of lambdas that might come handy here.

If you think about implementing a wrapper for WebKit, for example, it will require passing a ton of objects of different kinds back and forth. Something from the WebKit you should own, something you produce will be held by the WebKit.

I think this discussion is related: https://github.com/orgs/hylo-lang/discussions/731. I have the intuition that implicit parameters are a really interesting lead to solve the "plumbing" problem a strict MVS discipline can cause.

For example:

fun foo(some_arg x: Int, handle: @implicit inout SomeHandle) {
  if x < 0 {  print("A") }
  else { print(bar()) }
}

fun bar(handle: @implicit inout SomeHandle) -> String {
  &handle.read_some()
}

public fun main() {
  implicit var h = some_io_thing()
  foo(some_arg: 10)
}

[DmT021]

If the laziness only serves to avoid creating unnecessary intermediate data structures (e.g., chaining map applications), then I think we're better off exposing effects to the type system.

Yep, I meant the type of lazy when you can't observe if the value is loaded or not, and only can get the value (measuring time to load the value doesn't count as observation).

I think this discussion is related: https://github.com/orgs/hylo-lang/discussions/731. I have the intuition that implicit parameters are a really interesting lead to solve the "plumbing" problem a strict MVS discipline can cause.

Wow. Thanks for pointing this out. It's funny because we(at my work) just implemented a poor-man's implicits for swift.

For, example, the allocator will provide you exclusive write access to memory whenever a new allocation is requested. That memory buffer can be used like a regular array for the rest of the user code, without breaking the law of exclusivity.

Ok, that's a good example as well. Let's take one more step further. Imagine you're implementing a multithreaded analysis on the data in this buffer. Each thread may work on its own part of the buffer, so we can split it to chunks(slices) and run the threads without losing the exclusivity principle. But we don't know when or in what order the chunks will be released by the threads. We have to dealloc the memory when we don't need it, but we can't know at compile time when this will happen. So we probably need reference counting here, right?

[dabrahams]

I might be completely wrong, but IMO Hylo's value semantics is almost ready to express concepts of UniquePtr and SharedPtr, but not quite yet.

I don't think we've left anything important out.

move-only types are pretty much impossible to work with when we don't know at compile time will the value sink or not.

That's an anti-pattern, and supporting it is part of the poor trade-off that C++ non-destructive move semantics makes. Not supporting this directly in safe code is an intentional part of Hylo's design. After the call, one has to assume that the value was consumed anyway, so one might as well pass it by sink. To a first approximation (and probably a 2nd) there is no code that passes a type by mutable reference and then checks to see if it's been moved from. If you ever need to do this, you can pass a non-nil inout Optional<T> and let the called code optionally consume the T leaving the Optional as nil.

[DmT021]

To a first approximation (and probably a 2nd) there is no code that passes a type by mutable reference and then checks to see if it's been moved from. If you ever need to do this, you can pass a non-nil inout Optional and let the called code optionally consume the T leaving the Optional as nil.

I thought about this at first and my generalization about sinkable passing convention is the result of that thought. The aspect of this solution I dislike is that we provide no guarantee that passed value will not be nil. A better signature would be (sink T) -> Optional<T>. But this will make a mess.
The sinkable passing convention provides guarantee of existing of a value "in", and provides a way "out" back to the source, without boilerplate code. And I think it doesn't break local reasoning too, but I'm not so sure about it, as I'm not really confident what exactly this term implies.

I don't think we've left anything important out.

Do you think lexical lifetimes are not important? (My apologies if this's too obvious question, but I'm asking because I don't have a strong opinion)

[dabrahams]

A SharedPtr<T> object, by design, breaks the law of exclusivity: multiple parts of the code can have write references to the same object.

That's not quite precise; the key word is can. Dereferencing a SharedPtr<T> would break static LoE checking, which means the LoE must be upheld another way. If we're talking about SharedPtr being exactly C++ shared_ptr that would mean dereferencing would have to be an unsafe operation. Rust has a reference-counted pointer whose LoE is upheld dynamically by the program (by trapping if it is violated).

[dabrahams]

I started this thread with: "there will be a need to write bridges".

We share your concern about this.

So I meant that everything that's independent from the outside world is fine, but edge cases are my worry. If the answer is "stick to unsafe code" - I'm totally ok with it, but I though there might be other grades between "completely safe" and "completely unsafe".

We don't believe there are useful grades in the middle. "A little unsafe" is still unsafe; it allows undefined behavior, which means it allows everything no matter how bad. What we do acknowledge is that entire types are not necessarily unsafe; copying a shared_ptr, for example, is completely safe. Only its dereference operation needs to be unsafe.

[dabrahams]

The sinkable passing convention provides guarantee of existing of a value "in", and provides a way "out" back to the source, without boilerplate code.

That's all true but it's an additional language wrinkle for an extremely marginal use-case and a pattern that we want to discourage. On balance it's better to say "no" to features like that, to keep language complexity down.

I don't think we've left anything important out.

Do you think lexical lifetimes are not important? (My apologies if this's too obvious question, but I'm asking because I don't have a strong opinion)

I think they're not just unimportant; they're more harmful than helpful. If you need something done at the end of a scope, there should be a first-class, explicit way of saying so, rather than piggybacking the functionality on destruction semantics, whose exact timing almost never matters in practice. Again, it's a trade-off.

[kyouko-taiga]

I think they're not just unimportant; they're more harmful than helpful. If you need something done at the end of a scope, there should be a first-class, explicit way of saying so, rather than piggybacking the functionality on destruction semantics, whose exact timing almost never matters in practice. Again, it's a trade-off.

There's another tradeoff to consider because one could argue that lexical scopes are helpful to reason about lifetimes, not only RAII. For example, the following style would make reasoning about lifetimes more obvious:

public fun main() {
  var x = 42 in {
    let y = x in {
      use(y, and: x)
      modify(&x) // obviously illegal
    }
    modify(&x)
  }
}

The advantage is that we can easily "see" lifetimes. The drawback is that code gets littered with lexical scopes. That's a different tradeoff than the one about piggybacking on destruction semantics.

[DmT021]

That's all true but it's an additional language wrinkle for an extremely marginal use-case and a pattern that we want to discourage. On balance it's better to say "no" to features like that, to keep language complexity down.

Makes sense, I accept this.