Template for a possible future object model

The Val Object Model

Val is a Swift-inspired language being developed by @dabrahams, @Alvae, and a handful of others.

Beyond trivial syntactic similarity, Val draws on Swift for its object model, re-imagining how we think it would look if Swift:

  • Started with support for non-copyable types.
  • Had the benefit of insights gained during its development, especially the law of exclusivity and _modify/_read accessors.
  • Did not start with support for (single-thread safe) reference semantics at its core.

This post is not an attempt to sell Val to anyone, and we certainly don't believe Swift can adopt Val's object model wholesale, immediately, or without modification. That said, we think Swift might be evolved in the direction of Val's model, and that doing so could result in a simpler, better Swift. Because Val was designed with noncopyable types in mind, the model is cleaner than what's currently being contemplated for the future of Swift, which understandably shows signs of a retrofit. At @Joe_Groff's suggestion we are starting this thread to introduce the big picture in one place, tuned to be appropriate for the Swift evolution audience.

Significant portions of this post synthesize parts of Val's language tour, with additional comments describing how Val relates to Swift. We have omitted detailed explanations of things we think this audience can easily intuit on their own, but please feel free to ask questions about anything.

Pure Value Semantics

Val's originating question was: What does programming look like when there is only mutable value semantics?

Therefore we started with Swift, omitting the three sources of reference semantics in Swift's (single-thread) safe subset:

  • classes
  • mutable global variables
  • closure captures with reference semantics

The approach is a major departure from that of Swift, but we believe the design is relevant nonetheless, and that reference semantics in the style of Swift can be reconstructed on top of Val's core object model. [Note that shared mutable state is accessible in the Val model's unsafe subset via pointer dereferences].

Explicit, necessary copies

The way Swift passes arguments to functions showed us that arguments passed by value don't need to be copied or moved, which led us to realize that the semantics of a let binding (which can be viewed as passing by-value to a continuation function) doesn't necessarily imply a copy or move either.

When these copies are eliminated, the need for copying becomes rare enough that:

  • It becomes reasonable to make all copies, even those of trivial types like Int, explicit via x.copy(), thus simplifying the story for generic code that must operate on both kinds of type.
  • Many generic algorithms written straightforwardly to operate on copyable types “just work” on non-copyable types without modification, so the need to add a generic Copyable requirement becomes rare.
  • Since a copy is only needed when the source of a let binding is modified during the let binding's lifetime, it turns out that the compiler can issue a “fix-it” suggesting exactly the necessary copies, and can warn about those that are unnecessary. The user experience is analogous to the one Swift provides around let and var.
  • Finally, since the compiler can identify necessary and unnecessary copies, we can add a way to turn on implicit copies.

In the latter mode the programming model for copyable types is practically identical to the one that Swift offers today, but with only the necessary copies actually being made. It is this overlap that makes us think it may be possible to evolve Swift toward Val's model. We also think this model provides a suitable platform for interoperating with C++. Swift may need to use the opposite default for backward compatibility reasons of course.

Examples

Missing copy detection:

The ability to create a let binding without an implicit copy means that immutability must be conferred upon the source of the binding during the binding's lifetime.

fun f(x: inout Int) {
  let y = x // <-------------------------------------------+
  x += 1    // error: x is let-bound.  Insert a copy here -+
  print(x, y)
}

If Swift ever gets local inout bindings, an analogous coupling will confer inaccessiblity on source values during the lifetime of the binding.

Because by-value parameters are borrowed, they can't be stored or returned without a copy:

type Vector2 {
  var x: Double
  var y: Double

  /// Creates an instance whose `x` and `y` values are `buffer[0]` and 
  /// `buffer[1]` respectively.
  init(_ buffer: Double[2]) {
    x = buffer[0].copy()
    y = buffer[1] // error: `buffer[1]` cannot escape; insert a copy here.
  }
}

An alternative would be to pass buffer as a sink parameter, which would allow it to be consumed to create the new Vector2 instance. More on passing conventions later.

Opt-in implicit copying

Because the compiler can know where copies would have been made in a language with implicit copying, we can allow the user to enable implicit copies, resulting in a model that mimics Swift.

@implicitcopy

type Vector2 {
  var x: Double
  var y: Double

  init(_ buffer: Double[2]) {
    x = buffer[0] // implicit copy here
    y = buffer[1] // and here
  }
}

Note: you can use @implicitcopy at any scope, or can parameterize it with specific types or traits (e.g. CheaplyCopyable), allowing the effect to be controlled when it matters.

Copyability

Copyability is enable by making types conform to the Copyable trait. A trait is like Swift protocol.

type Vector2: Copyable {
  var x: Double
  var y: Double
}

Just as in Swift, conformance to traits like Copyable, Equatable and Hashable can be synthesized when stored properties have those conformances.

Parameter passing conventions

A parameter passing convention describes how an argument is passed from caller to callee. In Val, there are four: let, inout, sink and set. The next series of examples define four corresponding functions to offset this 2-dimensional vector type:

type Vector2: Copyable {
  var x: Double
  var y: Double
}

let parameters

let is the default convention and does not need to be spelled explicitly. At the user level, let parameters can be understood just like reglar parameters in Swift. They are (notionally) passed by value, and are truly immutable.

fun offset_let(_ v: Vector2, by delta: Vector2) -> Vector2 {
  Vector2(x: v.x + delta.x, y: v.y + delta.y)
}

The let convention does not transfer ownership of the argument to the callee, meaning, for example, that without first copying it, a let parameter can't be returned, or stored anywhere that outlives the call.

fun duplicate(_ v: Vector2) -> Vector2 {
  v // error: `v` cannot escape; return `v.copy()` instead.
}

inout parameters

inout behaves almost exactly like in Swift. Arguments to inout parameters must be unique, mutable, and marked with an ampersand (&) at the call site.

fun offset_inout(_ target: inout Vector2, by delta: Vector2) {
  &target.x += delta.x
  &target.y += delta.y
}

One syntactic difference from Swift you'll notice is that in Val there are no exceptions to the rule that mutated objects are marked with &, so you'll see it in uses of operators and mutating methods.

Another difference from Swift is that, although inout parameters are required to be valid at function entry and exit, a callee is entitled to do anything with the value of such parameters, including destroying them, as long as it puts a value back before returning. That makes it convenient to temporarily move an argument into an object that encapsulates some computation.

type Processor {
  var ast: AST
  fun process() inout { ... }
  fun process_expr() inout { ... }
  fun process_decl() inout { ... }
  fun finalize() sink -> {AST, Result} { ... }
}

fun process(_ ast: inout AST) -> Result {
  // Move `ast` into `p`, without copying it
  var p = Processor(ast)
  
  // Execute the computation encapsulated by `Processor`
  &p.process()

  // Move `p` back into `ast`.
  let result: Result
  (ast, result) = p.finalize()
  return result
}

Note: In Val, the passing convention for the self parameter to a method is written after the parameter list, so mutating methods are marked with a postfix inout.

sink parameters

The sink convention indicates a transfer of ownership, so unlike previous examples the parameter can escape the lifetime of the callee.

fun offset_sink(_ base: sink Vector2, by delta: Vector2) -> Vector2 {
  &base.x += delta.x
  &base.y += delta.y
  return base        // OK; base escapes here!
}

Just as with inout parameters, the compiler enforces that arguments to sink parameters are unique. Because of the transfer of ownership, though, the argument becomes inaccessible in the caller after the callee is invoked.

fun main()
  let v = Vector2(x: 1, y: 2)
  
  print(offset_sink(v, (x: 3, y: 5)))  // prints (x: 4, y: 7)
  
  print(v) // <== error: v was consumed above.
}          // to use v here, pass v.copy() to offset_sink.

The conventions we've seen so far are closely related; so much so that offset_sink can be written in terms of offset_inout, and vice versa:

fun offset_sink2(_ v: sink Vector2, by delta: Vector2) -> Vector2 {
  offset_inout(&v, by: delta)
  return v
}

fun offset_inout2(_ v: inout Vector2, by delta: Vector2) {
  v = offset_sink(v, by: delta)
}

Furthermore, either one can be written in terms of offset_let:

fun offset_sink3(_ v: sink Vector2, by delta: Vector2) -> Vector2 {
  offset_let(v, by: delta)
}

fun offset_inout3(_ v: inout Vector2, by delta: Vector2) {
  v = offset_let(v, by: delta)
}

set parameters

The set convention lets a callee initialize an uninitialized value. An argument to a set parameter is unique, mutable and guaranteed uninitialized at the function's entry.

fun init_vector(_ target: set Vector2, x: sink Double, y: sink Double) {
  target = Vector2(x: x, y: y)
}

public fun main() {
  var v: Vector2
  init_vector(&v, x: 1.5, y: 2.5)
  print(v)                         // (x: 1.5, y: 2.5)
}

Method bundles

When multiple methods have the same functionality but differ only in the passing convention of their receiver, they can be grouped into a single bundle.

extension Vector2 {
  fun offset(by delta: Vector2) -> Vector2 {
    let {
      Vector2(x: x + delta.x, y: y + delta.y)
    }
    inout {
      &x += delta.x
      &y += delta.y
    }
    sink {
      &x += delta.x
      &y += delta.y
      return self
    }
  }
}

public fun main() {
  let unit_x = Vector2(x: 1.0, y: 0.0)
  var v1 = Vector2(x: 1.5, y: 2.5)
  
  &v1.offset(by: unit_x)          // inout
  let v2 = v1.offset(by: unit_x)  // let
  print(v1.offset(by: unit_x))    // sink
  print(v2)
}

At the call site, the compiler determines the variant to apply depending on the context of the call. In this example, the first call applies the inout variant as the receiver has been marked for mutation. The second call applies the let variant as the receiver is used in the next line The third call applies the sink variant as it is receiver's last use.

Thanks to the link between conventions, the compiler is able to synthesize one implementation from the other as long as the type is Sinkable. This feature can be used to avoid code duplication in cases where custom implementations of the different variants do not offer any performance benefit, or where performance is not a concern. For example, in the case of Vector2.offset(by:), it is sufficient to write the following declaration and let the compiler synthesize the missing variants.

extension Vector2 {
  fun offset(by delta: Vector2) -> Vector2 {
    let { Vector2(x: x + delta.x, y: y + delta.y) }
  }
}

The Copyable and Sinkable traits.

The Copyable trait is a refinement of Sinkable, the trait for types that can be moved. They are defined as follows in the standard library, using method bundles:

trait Sinkable {
  // Gives `self` the value of a consumed `source`.
  fun take_value(from source: sink Self) {
    // The pattern `let x: T = f()` is compiled as `let x: T; x.take_value(from: f())`.
    set { /* synthesized memberwise */ }   // move-initialization

    // The pattern `x = f()` is compiled as `x.take_value(from: f())`.
    inout { /* synthesized memberwise */ } // move-assignment
  }
}

trait Copyable: Sinkable {
  // Gives `self` the copied value of `source`.
  fun copy_value(from source: sink Self) {
    // The pattern `let x: T = expr.copy()` is compiled as `let x: T; x.copy_value(from: expr)`.
    set { take_value(from: source.copy()) }   // copy-initialization

    // The pattern `x = y.copy()` is compiled as `x.copy_value(from: y)`.
    inout { take_value(from: source.copy()) } // copy-assignment
  }
}

The compiler chooses an implementation based on the whether the left-hand-side is initialized and whether the RHS is consumed.

Projections

A subscript or computed property projects a value rather than returning one. Unlike in Swift, a subscript in Val can be named and can be freestanding, like a function (as opposed to a method). Otherwise, it operates similarly to a Swift subscript.

// A freestanding named subscript.
subscript min<T: Comparable>(_ x: T, _ y: T): T {
  if y < x { yield y } else { yield x }
}

fun main() {
  let one = 1
  let two = 2
  print(min[one, two]) // 1
}

Note that, because min[_:_:] yields rather than returning a value, its parameters do not escape from the subscript.

A projection can be assigned to a local binding and used over multiple statements. For example:

fun main() {
  var numbers = Array([3, 1, 6, 5, 4, 1, 2, 0])
  inout slice = numbers[in: 1 ..< 5] // slice is projected out of `numbers`
  &slice.sort()
  print(numbers) // [3, 1, 4, 5, 6, 1, 2, 0]
}

Just like methods, subscripts and properties can bundle multiple implementations to represent different variants of the same functionality.

type Angle {
  var radians: Double
  
  property degrees: Double {
    let {
      radians * 180.0 / Double.pi
    }
    inout {
      var d = radians * 180.0 / Double.pi
      yield &d
      radians = d * Double.pi / 180.0
    }
    set(new_value) {
      radians = new_value * Double.pi / 180.0
    }
    sink {
      radians * 180.0 / Double.pi
    }
  }
}

Most of Val's accessors correspond to Swift's:

  • A let subscript is like Swift's _read accessor. It is the default in Val, as it allows to project values without transferring their ownership.
  • An inout subscript is like Swift's _modify accessor.
  • A set subscript is like Swift's set accessor.

However, sink subscripts are a bit different. They can be used to "destructure" a value and extract some of its parts. Although they overlap with sink methods, they serve to optimize cases where the value from which a projection is created is no longer used, and, crucially, their results can escape.

fun main() {
  var numbers = Array([3, 1, 6, 5, 4, 6, 2, 0])
  var slice = numbers[in: 1 ..< 5] // last use of 'numbers'
  _ = slice.pop_first()
  print(slice)
}
52 Likes

Thanks for the write up! A couple small questions:

Have you considered a mechanism to “pin” which variant of a method bundle is used at a particular callsite? I’d imagine that in performance sensitive code (i.e. any code that actually cares which parameter passing convention is used) could end up having unexpected performance regressions if the code subtly changes (for instance, if a subsequent revision added another use of numbers to your last example, forcing the subscript to change from sink to copy). Perhaps some more value-level control of this functionality may be beneficial. This may be relevant to the move operation currently under discussion for Swift.


Also, if I’m understanding correctly, then the return value is really just a special set argument? Seems like a nice way to model this.

1 Like

Yes. All entities have a name in Val. So you can refer to one particular implementation in a bundle by appending the convention to the function name:

public fun main() {
  var a = Array([4, 1, 6, 3, 9, 8])
  Array.sort.inout(&a)
  print(a)
}

Though set parameters can represent return values, that is not their primary purpose. We do have "proper" return values so, for example, you can:

fun factorial(_ n: Int) -> Int {
  if n < 2 { 1 } else { n * factorial(n - 1) }
}

The primary purpose of set parameters is to express assignment and initialization across function boundaries.

Minor typo

The comment on the print statement appears to be missing the second occurrence of 6.

1 Like

I’m not sure if these make sense as regular protocols in Swift. There’s already a precedent of using marker protocols for more abstract features that are closer to compiler checks than regular, protocol capabilities. My biggest concern with choosing regular protocols is that many types will be polluted with takeValue and copyValue functions that most users will likely need to know after some experience with Swift. Although ownership is really important for writing efficient algorithms and giving developers a clear view of the low-level operations, it is still a niche feature. At the end of the day, Swift is still a general-purpose language that has given rise to many powerful, high-level APIs, such as SwiftUI, and (to my limited understanding) server frameworks. So I think that Val has a great low-level model, but more adaptations, other than implicit copies, will be required to bring that model over to Swift. Another such adaptation could be to automatically add a Copyable conformance to internal types, similar to how it is for Sendable, in addition to synthesizing it.

This is really interesting, as I would expect that implementing some basic algorithms, such as the ones found in the standard library would require some copies. What code/algorithms has been written in Val as an example? I think it would help if we had some concrete metrics to justify this source-breaking change.


Also, thanks for the writeup! I think Val has a great potential to learn from Swift’s mistakes into develop into a major low-level language.

4 Likes

It‘s interesting to see Val having named subscripts. What made you change your mind compared to the short conversation we had 6 years ago?

3 Likes

Thank you, @Nevin, I corrected that (and changed it a little to be less misleading)

1 Like

It looks like 6 years ago I wasn't saying “that's a bad feature,” but ”this is how you do that in Swift as it exists today.” I probably wouldn't have supported adding a feature for it to Swift, though, because in the Swift of 6 years ago, it was purely a bit of nice syntactic sugar.

In Val, we realized that the distinction between projections and functions could help us solve the “property vs method” problem: if you need a projected semantics, you make it a property. If a result with independent lifetime is more appropriate, you make it a function/method. Then the question became how do you make a projection that has no receiver. We have freestanding functions; symmetry kind of demands that there are freestanding subscripts, like min. The case you see in that example is interesting if you consider noncopyable types, which would have to be consumed if you used a function to select the mininum. For a case that's interesting with “normal” types, consider this:

subscript min<T: Comparable>(_ x: inout T, _ y: inout T): inout T {
  if y < x { yield y } else { yield x }
}

Now you can write something like this:

min[&x, &y] += 1 // increment the lesser of x and y

Of course in Val you'd define min as a bundle so one implementation could handle all the cases.

7 Likes

To be 1000% clear, nobody's claiming they do. How and whether to adapt these ideas to Swift's future are decisions for the Swift community to make. @Alvae and I are here to answer questions.

However, with respect to your biggest concern, if I were still working on the design of Swift I would consider the additional names (and “polluted” is a value judgement I wouldn't make!) a relatively minor issue that can be mitigated in all kinds of ways including via tooling, and way way less important than arriving at the right object model. But, y'know, Swift's priorities may not be the same as mine :slight_smile:

more adaptations, other than implicit copies, will be required to bring that model over to Swift

Certainly, nobody thinks otherwise.

It is true that some algorithms require copies, but they are rare. It's also true that many (sorts, parititions, rotate, remove adjacent duplicates, also almost anything that's non-mutating) don't require any copies. We are still at a very early stage with Val and looking forward to building up its generic algorithm library, so yes, full disclosure: by that standard, this model is completely unproven.

Lastly, let me say, nobody is proposing a source-breaking change to Swift. Nobody's proposing anything at all in particular. We think some of what we've put together here could be really useful for Swift, should y'all choose to dig into and run with it. We'd love to see that happen and are happy to consult on ways to do it, but it's not obvious to me that using some or all of these ideas has to break source, and whether or not that eventually happens is of course totally up to Swift. I'd certainly be surprised Swift could end up looking exactly like the design of Val without breaking source, but that's not your only available option.

10 Likes

@dabrahams I have a few questions on the "&" usage in the sample code while reading the tour guide page, but not sure what's the right place to ask about them. Is it the issue section on Github?

My Questions

First I understand why "&" is required in += operation. It's because += is a function taking inout parameter.

Question 1) A minor question. "&" is missing in the sample code about binding's lifetime. Is it a typo?

    public fun main() {
      let weight = 1.0
      let base_length = 2.0
      var length = base_length 
      length += 3.0            
      // Q: shouldn't it be "&length += 3.0"?
      ...
    }

Question 2) I find it quite confusing to require "&" in +=, but not in =. See the example code (I haven't been able to compile Val to verify the code, but from my understanding it's valid).

    public fun main() {
      var length = 1
      length = 2
      &length += 2
    }

If I understand it correctly, the difference is caused by the fact that = is not a function. However, from an user's perspective, I'd think both mutate length value and hence should have same syntax. Am I misunderstanding anything here?

Thanks.

1 Like

If names subscripts made their way into Swift, we could perhaps update callAsFunction to have more parity between functions and subscripts.

How did you settle on these four parameter-passing conventions? In any language, these conventions are bound to have overlaps, so why was this model chosen? For example, why not just return a tuple with the primary return value and what would otherwise be a set parameter. I guess my questions extends to whether you used a matrix of reading a parameter, consuming it and writing to it (or something to that effect), to come up with your parameter-passing conventions.

1 Like

Hi @rayx, since your questions are not exactly relevant to the object model and Swift's future, yeah, maybe filing issues would be a good idea (and thanks for finding that typo!). @Alvae maybe we should start thinking about how to enable general community discussion.

1 Like

We started with a few ideas, like that passing a parameter to a function in the normal way should neither copy nor consume it, and that Swift's inout was probably just about perfect, and tried to see where following those ideas to their conclusions might lead if we wanted to handle move-only types. It wasn't as formal as laying out a matrix. @Alvae writes more about the reasons for the set convention here (but please bring any questions back to this thread). I am not sure that it's a crucial part of the model, but if you look at the Copyable and Sinkable protocols defined above I think it creates a very understandable relationship between intialization and assignment.

1 Like

The basic model is that copies are always explicit, and there is no copy convention, so the subscript can't “change to copy,” and we believe this sort of silent perfomance regression can't occur unless you opt into @implicitcopy. But I'm very glad you asked this question because it gave me the opportunity to clarify. Thanks!

[A previously-reported wrinkle turned out to be a non-issue, I think]

1 Like

This makes sense. Is it also true that the addition or removal of a method or subscript variant cannot change which variant is used at a callsite, without source changes at that callsite?

In a sense, yes: the compiler synthesizes all the possible variants you haven't explicitly provided, so that which variant gets used is only dependent on the call site (and lifetimes of participating values). But those synthesized variants will be implemented using the variants you did write. So in a debugger it might appear to be directly calling one of those. In the absence of explicit specification of the variant at the call site, though, the intention is that you can add a variant and have that get used (which is definitely changing which of your written variants is ultimately called), because the new variant is a direct match for the conditions at the call site.

I should say that whole the point of this design is that you should normally never need to worry that there's a more-efficient way to call the method or projection you're using (unless of course that way hasn't been provided in the bundle). It's designed to relieve the constant worry about the sorts of things you're asking about, so you can focus on expressing the high-level semantics of your code. Using these features effectively requires a certain amount of trust that the language design is doing the right thing for you, in exchange for you having given it enough information to do so, in the form of method bundles.

2 Likes

Could you go over or point me to a document that outlines how this synthesis happens exactly? Or is this more in the realm of the implementation details of compilation, and thus depend on what the compiler sees more fit? Also, I wonder whether Val recommends certain types of user-provided bundles, e.g. that users a let and a sink accessor by default.

The compiler does the following synthesis (see our specification):

  • sink from let
  • sink from inout
  • inout from sink (and set, if present)

The choice of the variant is part of the language semantics. Unfortunately, I haven't described it in our specification yet. So let me elaborate here.

The choice depends on what we call "last use analysis". That's a mandatory compiler pass that essentially does definite initialization and liveness analysis. People interested in implementation details may look at our code.

Whenever a binding is passed as an argument, the analysis can tell whether:

  • it is used in a mutable context (a)
  • it is initialized (b)
  • it is used later in the program (c)

The variant selection operates as follows:

  • a && !b => set
  • a && b && c => inout
  • !a && b && c => let
  • b && !c => sink

Every other configuration is an error.

4 Likes

This is neat, thank you for writing it up! I love the evolution of “assignment methods” and the formalization of projection. Whether or not these things end up in Swift they are cool to see.

This is the Swift forums, but I’d note that the base model here is very very similar to Rust’s: @implicitcopy is Copy, Copyable is Clone, most values are non-copyable, let/inout/sink corresponds to &/&mut/by-value (though Rust puts more guarantees on the representations of references). Method bundles and subscripts-as-projections take the language in a different direction, but all of the high-level insights feel very much the same, in a way I’m eagerly awaiting for Swift. I hope there’s cross-pollination there too!

My one point of confusion is Sinkable. What’s an example of a type that is not Sinkable? Is that a “move-never” type?

9 Likes

The link to the language tour seems broken, Val | The Val Programming Language