Follow-on feature: method calls

[tlively]

One goal of custom descriptors is to make the common object-oriented vtable pattern more memory efficient by letting descriptors serve as vtables, obviating separate vtable reference fields in other objects. However, custom descriptors do not address the other large pain point with the vtable pattern: receiver casts.

Methods are currently normal immutable fields on the vtable structs (which may also be descriptors). This means they support depth subtyping: a method field in $sub.vtable may be a subtype of the corresponding method field in $super.vtable. However, function types are contravariant in their parameters, so the parameters of the $sub's method must be supertypes of the parameters of $super's method. This is a problem because one of those parameters is the method receiver. In $sub's method, we want the receiver parameter to be a reference to $sub, but instead it must be a reference to a supertype of $super. This means that all overridden methods must start with a cast of the receiver parameter from the supertype that introduced the method to the specific receiver of the particular override. We could save the cost of this cast if we could prove via the type system that the receiver always had the expected type.

Here is a sketch for a type system extension for eliminating receiver casts. No existential types required!

We introduce a new kind of struct field called a method field. A method field is always immutable and contains a reference to a defined function type. A method field may only appear in a descriptor type and the first parameter of its referenced function type must be a reference to a supertype of the described type.

(rec
  (type $foo (sub (descriptor $foo.vtable) (struct)))
  (type $foo.vtable (sub (describes $foo) (struct (method $quack (ref null $foo.quack)))))
  (type $foo.quack (func (param (ref null $foo))))
)

What makes method fields special is that they have different subtyping rules than normal fields. To check whether a method field in a subtype matches the corresponding method field in a supertype, we do not just check that their reference types match like we would for normal fields. Instead, we check that the nullability of the references matches and then check the parameters and results element-wise, checking that all parameters but the first respect contravariance and all the result respect covariance. The first parameter, the receiver, does not matter for this check.

(rec
  (type $bar (sub $foo (descriptor $bar.vtable) (struct)))
  (type $bar.vtable (sub $foo.vtable (describes $bar) (struct (method $quack (ref null $bar.quack)))))
  (type $bar.quack (func (param (ref null $bar))))
)

Note here that $bar.vtable is a valid subtype of $foo.vtable even though $bar.quack is not a subtype of $foo.quack. This makes it unsafe to do a struct.get $foo.vtable $quack on an inexact reference to $foo.vtable because that should return a (ref null $foo.quack), but at runtime the $foo.vtable may actually be a $bar.vtable whose $quack field contains a completely unrelated type. To preserve soundness, struct.get on method fields is only valid with exact struct references.

Since we cannot actually read a method field out of a vtable (except in the uninteresting case where we know the exact type of the receiver), we cannot get a reference to the method to pass to call_ref. Instead, we introduce call_method and return_call_method instructions for calling methods. These instructions take the receiver type and method field index as immediates and take the receiver and other method arguments as operands.

call_method x y : [(ref null x) t1*] -> [t2*]
 -- C.types[x] ~ (descriptor x') (struct fts)
 -- C.types[x'] ~ (struct fts')
 -- fts'[y] = method (ref null? ft)
 -- ft ~ [(ref null x') t1*] -> [t2*]

call_method and return_call_method execute by getting the descriptor of the receiver, looking up the function reference in the method field in the receiver, and calling the function, passing in the receiver and the rest of the arguments. Since the function is looked up on the receiver's descriptor and we required that all method fields take a supertype of the described type as their receiver parameter, there is no need for a cast to prove that the receiver will have the expected type.

;; Works even if local $foo holds a $bar.
(call_method $foo $quack (local.get $foo))

[jakobkummerow]

@leesh3288, any thoughts on this design? Or do you prefer to wait until it's implemented somewhere? :-)

[sjrd]

I don't think this is going to help all that much.

I don't see an obvious soundness issue; and if it were available, I would use it. But I don't think it really solves the problem. It helps with virtual calls on single-inheritance classes. But it won't solve the more general and more problematic calls on interfaces (with multiple-inheritance). The current instruction chain for an interface call of A.method in Scala.js, J2CL and probably also Kotlin is the following:

local.get $receiver
struct.get $jl.Object $vtable ;; or ref.get_desc with custom descriptors
struct.get $vtable $slotForA ;; a generic (ref null struct), because disjoint interfaces end up in the same slot
ref.cast (ref $itableForA) ;; hence, cast it down
struct.get $itableForA $slotForMethod
call_ref $typeOfMethod

and inside the target method, we cast down to the actual receiver type and proceed.

AFAICT, the method fields and call_method instructions of this issue won't be usable in this scenario. So we are still left with two "unnecessary" casts.

Arbitrary interface calls are more common than virtual class method calls. It is fairly rare for concrete class methods to actually be overridden, so most class method calls are statically resolved to begin with. However, abstract interface methods that get implemented in several classes are all over the place, and can rarely be statically resolved.

I understand the proposed design here has a rather small footprint. But IMO it would worth targeting a larger footprint that would handle interface method calls as well (or, in general, method calls in a multiple-inheritance hierarchy).

[rossberg]

I agree with @sjrd. As a Wasm feature, this would be too narrow and too overfitted to one corner of a much more general problem space.

There are many different forms of methods. This would be hardcoding one particular form of object model and one particular implementation strategy, namely the C++/Java-style class method vtable. And it is tying it to descriptors. That seems way too specific to include as a Wasm primitive.

There also are much worse instances of the exact same problem, e.g., when implementing closure environments, which currently require a cast on every single function call. But this proposal would not help those. Would we then add closure environments as a primitive at the next turn? And after that other flavours of methods, closure environments, etc.?

Maybe this is a good time to start a debate about ways to solve the "self type" problem, as well as other casts. But I suggest we look for generic solutions that at least cover some range of use cases. And perhaps to set the right priorities, such a discussion could be informed by some data on the relative cost of various instances of casts in practice (including e.g. the emulation of generics, universal representations, encoding interface methods, expressing closures, encoding datatypes). Did anybody collect any sort of data like that by any chance?

[eqrion]

I agree with the others here that it'd be good to consider other use-cases and bigger solutions. I'm not opposed to something like this proposal, but I'd like to see more research and alternatives before committing to it. I have anecdotally heard that interface calls are the hardest to efficiently lower to wasm, so it'd be great to find a way to solve those too.

It'd be great if someone could sketch out how existential types could work here. I could imagine a world where they're too complicated for the benefit they provide, and smaller targeted solutions like this one are preferable. But it's hard to judge without something concrete.

[tlively]

I would be thrilled to have a more general solution. I do not currently know how one might be constructed. I would be very eager to hear ideas.

[sjrd]

All right, folks, you totally nerd-sniped me. I hold you responsible for my lack of sleep last night. 😅

Here is a proof of concept of self types, encoded as a runnable example in the Scala type system:
https://scastie.scala-lang.org/sjrd/w8uWuPGRQAuUBbQBEoVt6w/2
I use Scala abstract type members and path-dependent types to encode self types. We wouldn't need the full power of path-dependent types in Wasm.

It needs:

• Self types (obviously)
• Exact types from the custom descriptors (but not descriptors per se; that's orthogonal)
• Multiple parent types for struct types (still only with depth and width subtyping; no permutations)
• Multiple parent types for function types

Since Scala does not have exact types, I "encoded" exact types as pairs of abstract class X and final class ExactX extends X. This achieves the corresponding subtyping rules. Only the exact classes can be instantiated, which corresponds to the fact that struct.new always creates exact references.

I'll show below how we can get rid of the last two requirements, but at some run-time cost. First I focus on the full solution.

Full solution

There are two forms of "self types": the real Self types, and "DescribedSelf" types. The former is what we typically expect. In class Foo, the Self type is known to be some subtype of Foo (that's the type Self <: Foo part). We also know it is a supertype of the this value (that's type Self >: this.type); in other words, even though we don't know what Self really is, there's one thing we know: we can assign the this value to Self.

In the exact variant of the classes, we at last know what Self truly stands for. In ExactFoo, type Self = ExactFoo (which is stronger than >: this.type <: ExactFoo).

In Wasm, the Self type could be implicitly defined inside all struct types. We would be able to use it inside the field definitions (somehow).

DescribedSelf is different. It allows to attach an arbitrary struct to apply to the self type of another struct. This is similar to how descriptors reflect properties of the described types, which is why I called it DescribedSelf. Actual descriptors would probably have a corresponding DescribedSelf type; but other, unrelated types can have the same DescribedSelf.

In the PoC, the VTable types have a DescribedSelf for the corresponding structs. For example, AVTable has type DescribedSelf <: A. The exact variants have exact described types: ExactAVTable has type DescribedSelf = ExactA. Note that described self types do not have >: this.type. Indeed, they talk about other types.

The vtables would be descriptors, but we also have itables for interface dispatch. IntfITable also has a type DescribedSelf <: Intf, although the itables would not be descriptors of instances of Intf. Thus the concept of described self type is not tight to custom descriptors.

In A, we specify that the vtable field (which would be an actual descriptor eventually, but making things explicit here) must be a AVTable whose DescribedSelf is exactly my Self type. That's

// in A:
val vtable: AVTable { type DescribedSelf = Self }

We can chain those requirements. The itable for Intf inside the vtable of B must have the same described self type:

// in BVTable:
val itableSlot1: IntfITable { type DescribedSelf = BVTable.this.DescribedSelf }

In Wasm, we could optionally attach a described self type to a struct type (which may be a descriptor struct). For example

(type $AVTable (sub $rootvtable describedself $A ...))

which we would be able to use in the field definitions (somehow).

Overall, you can see that there isn't a single cast in the Scala code. Likewise, there would be no need for any cast in Wasm. It remains to be seen how we would really type the expressions like

a.vtable.foo(a)

or

intf.vtable.itableSlot1.foo(intf)

without full path-dependent types in Wasm, but it's probably a tractable problem, once the correct typing for the structs has been established. In Scala this works because the chained type DescribedSelf = Self ends up with type Self >: this.type; through type substitution, it knows that [this->a] this.type is a.type and hence a is a valid value to pass as the argument to foo(a). For the itable version, it follows one more such relationship.

Finally, note that A and B also contain a function pointer in their instance struct. That models what you would do for closures with an embedded environment. So the model is general enough to also encode that without cast nor extra overhead.

Without multiple parents for structs

If we don't have multiple parents for structs, we cannot have Intf and IntfVTable as actual types. They must disappear in the encoding. Then, a variable typed as Intf in the source language must be typed as Root in the encoding. This is what Scala.js/J2CL/KWasm currently do for interface types.

That means that intf.vtable.itableSlot1 is not known to be a valid IntfITable. It is the generic ITable | Null defined in RootVTable. We must therefore introduce a cast down to IntfITable when performing an interface method call.

That leads to the following variant:
https://scastie.scala-lang.org/sjrd/w8uWuPGRQAuUBbQBEoVt6w/3

This is no worse than what we have to do currently for the interface aspect. We can still avoid the cast inside the target method. That is the most expensive one, since it is not always to a final type. The cast we still have to do targets a final type.

Without multiple parents for functions

There is one hidden aspect in the above, about functions. Function types in Scala are contravariant in their parameter types. That's not the case in Wasm (AFAICT). You have to explicitly declare a (one!) super type for your function type if you want subtyping. Then you can have your parameter contravariance. So you can have A => Int be a subtype of B => Int (given B <: A) if you want. But you cannot also have A => Int be a subtype of X => Int where X is another subtype of A.

So if you have a tree hierarchy on your struct side (which is expected), you cannot have the corresponding "reverse" tree of function types.

So far, we have assumed that we could do that. That would require function types to have multiple parents in Wasm.

What if we cannot have that? Then we must introduce extra forwarders. In our example, B inherits A.bar without overriding it. Previously, we could put the address of A_bar directly in the vtable of B. Without the function subtyping, that does not work. So we need a separate helper B_bar that takes a B, and forwards (without cast!) to A_bar.

That leads to the following variant:
https://scastie.scala-lang.org/sjrd/w8uWuPGRQAuUBbQBEoVt6w/4

Thoughts?

I'll leave you with that. Any thoughts so far?

[rossberg]

@sjrd, interesting! Just some quick questions, as I will need more time to read through this and grok it.

I agree that declared subtyping gets in the way of (extensible) use of contravariance. Unfortunately, I'm not sure what can be done about that, since the efficient implementation of casts depends on it. Just allowing multiple (declared) supertypes probably isn't even good enough, since that still wouldn't be extensible, so would only work in a closed-world setting where all (sub)classes are known?

Your self type has both an upper and lower bound. Is that just an artefact of the Scala encoding? Obviously, it is unlikely that we can afford lower bounds in Wasm, given all the complications they introduce.

FWIW, one possible direction I had been thinking was along the lines of Neal Glew's old OOPSLA paper (https://dl.acm.org/doi/pdf/10.1145/354222.353192). From a superficial look, I think your encoding shares some of the same ideas, in particular, the fact that the self type is a sort of quantified variable bounded by the exact own type. I was hoping this could be integrated into Wasm as some kind of special Self reference (which denotes the bounded variable that would implicitly be associated with each member of a recursive group), but never reached a conclusion on how the scoping should work.

[sjrd]

I agree that declared subtyping gets in the way of (extensible) use of contravariance. Unfortunately, I'm not sure what can be done about that, since the efficient implementation of casts depends on it. Just allowing multiple (declared) supertypes probably isn't even good enough, since that still wouldn't be extensible, so would only work in a closed-world setting where all (sub)classes are known?

Yes, that assumes a closed world. But to be fair, that's already the status quo, pretty much. One needs to put the entire class hierarchy of a system in a single recursive group already today. And if you need to put everything in a single recursive group, you need the whole world.

In theory you can extend with a separate recursive group if the first one never refers to the new one, including in parameter types of methods. But I don't think any toolchain with a class hierarchy does that at the moment.

Your self type has both an upper and lower bound. Is that just an artefact of the Scala encoding? Obviously, it is unlikely that we can afford lower bounds in Wasm, given all the complications they introduce.

It is an artifact of the encoding, yes. In general, abstract type members in Scala are very powerful. In a Wasm context, I would restrict the self type to systematically be upper-bounded by the self-struct type, and then have some dedicated rule that an instance of a struct is assignable to its self type. I wouldn't introduce the lower bound per se in the source Wasm type system. In fact even the upper bound would probably not be specified as is; rather we could have a dedicated subtyping rule such as SomeStruct.Self <: SomeStruct.

My encoding in Scala is a way to argue soundness of the restricted self types by a "type-preserving compilation scheme" to path-dependent types (except I did it by hand). I am definitely not suggesting to add abstract type members with bounds in Wasm.

FWIW, one possible direction I had been thinking was along the lines of Neal Glew's old OOPSLA paper (https://dl.acm.org/doi/pdf/10.1145/354222.353192). From a superficial look, I think your encoding shares some of the same ideas, in particular, the fact that the self type is a sort of quantified variable bounded by the exact own type.

Thanks for the reference. I'll read that tonight.

I was hoping this could be integrated into Wasm as some kind of special Self reference (which denotes the bounded variable that would implicitly be associated with each member of a recursive group), but never reached a conclusion on how the scoping should work.

I believe this is very similar to what I had in mind. I guess your scoping issues are related to the two "somehow"s in my presentation above.

[tlively]

A sketch based on my (very loose) understanding of the Glew paper:

(rec
  ;; method with self type parameter
  (type $f (typeparam $s (sub $super)) (sub (func (param (ref $s))))) 
  ;; vtable with self type parameter containing method
  (type $v (typeparam $s (sub $super)) (sub (struct (field (ref (apply $f $s)))))) 
  ;; struct introducing self type to parameterize vtable
  (type $super (self $s) (sub (struct (field (ref (apply $v $s))))))
)
(rec
  ;; Do it again for a subtype
  (type $f' (typeparam $s (sub $sub)) (sub $f (func (param (ref $s))))))
  (type $v' (typeparam $s (sub $sub)) (sub $v (struct (field (ref (apply $f' $s))))))
  (type $sub (self $s) (sub $super (struct (field (ref (apply $v' $s))))))
)

(func $method-f (type $f) ...)
(func $method-f' (type $f') ...)

(func $alloc-super (result (ref (exact $super)))
  (ref.func $method-f $super) ;; (ref (exact (apply $f $super))))
  (struct.new $v $super)      ;; (ref (exact (apply $v $super))))
  (struct.new $super)         ;; (ref (exact $super))
)

(func $alloc-sub (result (ref (exact $sub)))
  (ref.func $method-f' $sub) ;; (ref (exact (apply $f' $sub))))
  (struct.new $v' $sub)      ;; (ref (exact (apply $v' $sub))))
  (struct.new $sub)          ;; (ref (exact $sub))
)

(func $get-vtable (param $super (ref $super)) (result (ref ???))
  (struct.get $super 0) ;; invalid???
)

(func $get-self-vtable (param $super (ref $super))
  (typelocal $self (sub $super))
  (local $x (ref $self))
  (local.get $super) ;; (ref $super)
  (unpack $self)     ;; (ref $self) - initializes type variable $self to unpacked self type
  (local.tee $x)     ;; (ref $self) - only valid because $s has been initialized
  (local.get $x)     ;; (ref $self) (ref $self)
  (struct.get $self 0)  ;; (ref $self) (ref (apply $v $self))
  (call $call-vtable $self)
)

(func $call-vtable (typeparam $self (sub $super))
    (param $vtable (ref (apply $v $self))) (param $x (ref $self)))
  (local.get $vtable) ;; (ref (apply $v $self))
  (struct.get $v 0)   ;; (ref (apply $f $self))
  (call_ref $f)
)

[sjrd]

The Glew paper indeed seems very similar to what I came up with. In fact, taking inspiration from it and @tlively's "summary", I could simplify my encoding quite a bit. It turns out the DescribedSelfes can be regular type parameters with upper bounds (System F-sub style). That also decouples the exactness of the tables from the exactness of the "normal" structs, which is nice:
https://scastie.scala-lang.org/sjrd/w8uWuPGRQAuUBbQBEoVt6w/9
(for descriptors, we still need the locked-in exactness because of cast soundness, but that's a different story)

It's nice because it dramatically reduces the surface area of path-dependency. There is only the direct connection of a to a.Self such that a <: a.Self <: A.

Edit: funnily enough, I don't even need any of the upper bounds:
https://scastie.scala-lang.org/sjrd/w8uWuPGRQAuUBbQBEoVt6w/31
which means all I need is type Self >: this.type 🤔

A sketch based on my (very loose) understanding of the Glew paper:

It does look like what I understood from the paper as well. The fact that the method functions are polymorphic is a nice trick for Wasm. It removes the requirement for multiple parent types to function types. If we did have full contravariance of function types, they could be monomorphic, as in my encoding.

The unpack instruction looks like it avoids the last "path-dependency", but at the cost of the concept of local type variables. I wonder whether it would be simpler to keep the relationship a <: a.Self as the core feature instead. A possible typing understanding could be:

(func $get-self-vtable (param $sup (ref $super))
  (local.get $sup) ;; (ref (self $sup))
  (local.get $sup) ;; (ref (self $sup))
  (struct.get (self $sup) 0)  ;; (ref (self $sup)) (ref (apply $v (self $sup)))
  (call $call-vtable (self $sup))
)

(self $sup) is a heap type representing a singleton set { $sup }. We know that (self $sup) <: $super because of the declaration of $sup. And by construction, $sup is assignable to (ref (self $sup)).

[rossberg]

Yes, having this kind of self reference instead of an explicit unpack was exactly what I had in mind as well. And I was hoping that that is enough to avoid the separate (self $s) binding on structs as well, by assuming that every type implicitly binds a self variable and a (self $t) denotes that. And you could define

(type $super (sub (struct (field (ref (apply $v (self $super)))))))

But that is where I was running into the scoping question, because it is not clear where the use of (self $t) would be allowed. Perhaps that's overloading it with two different meanings.

[sjrd]

But that is where I was running into the scoping question, because it is not clear where the use of (self $t) would be allowed. Perhaps that's overloading it with two different meanings.

They are a bit different, but not too much. (self $t) within (type $t ...) is like t.this.type in Scala. It's the singleton type of the "this" value of the enclosing type $t. It is scoped to the definition of that type; and is completely meaningless outside of it. (self $a) at the call site is the singleton type of the local.get $a value. In Scala that would be a.type. They look similar, and they behave in the same way in many places, but they're a bit different: t.this.type/(self $t) is subject to type substitution. a.type/(self $a) is a concrete type that can never be substituted again. When you do a (local.get $a) (struct.get $t $x), you look up the declared type of field $x in $t, and you substitute all (self $t) by (self $a). So in your example you start from (ref (apply $v (self $super))) and you substitute (self $super) to get (ref (apply $v (self $a))).

[sjrd]

Wait, no, that's not quite right. Inside (type $t ...), (self $t) cannot be a singleton type. Because at the end of the day, it's the thing we use to instantiate the exact vtable types. So it can be a (ref exact $t), or a (ref exact $u) with $u <: $t, but it can never be a singleton type.

That's probably reconcilable on the other side, though. We could define (self $a) as being the unknown exact type (ref exact $w), where $w is the type used to create $a as a struct.new $w. Then we can still substitute (self $t) by (self $a) on struct.get (I think), and we can definitely assign $a to (self $a), which means the whole thing should typecheck.

So it's not quite like the .types of Scala. They're not singletons in this case. Even (self $a) contains all the other struct.new $ws (although we never get any more subtyping relationship out of that fact, since we don't know what $w is).

[rossberg]

I'm afraid you lost me a little there — I haven't internalised Scala's type system enough to see the connections naturally. :)

Are you saying we could indeed get away with just (self $t) as a heap type? That would certainly be nice. Though I'm not sure I have a clear picture of what the rules would be in terms of Wasm's own type system.

[sjrd]

I'm afraid you lost me a little there — I haven't internalised Scala's type system enough to see the connections naturally. :)

Sorry. It helps me to map it to a type system I know, but I completely understand it's tough if you don't know the ins and outs of Scala.

Are you saying we could indeed get away with just (self $t) as a heap type? That would certainly be nice. Though I'm not sure I have a clear picture of what the rules would be in terms of Wasm's own type system.

Sort of. It's a value type, not a heap type. You also need the call site version of it, which is talking about a local term variable. That's a bit awkward in Wasm because we have no immutable locals. So let's pretend we have immutable locals. Such locals must have a unique local.set or local.tee, and must always be set before being get'ed (even if its type is defaultable). It's OK if the local.set is in a loop.

Now here is how I would imagine the type system would play out:

• Lexically scoped within (type $t ...), we can refer to (self $t) as a value type.
  • C ⊢ (self $t) ≤ (ref $t) in that context
  • Outside that scope, (self $t) is meaningless and therefore illegal. In other words, C ⊢ (self $t) : ok only within (type $t ...)
• In the body of a function with an immutable local (local immut $a (ref $ht)) (or (param immut $a (ref $ht))) where $ht refers to a struct heap type $t, we can refer to (self $a) as a value type.
  • C ⊢ local.get $a : ϵ -> (self $a) if C.locals[$a] = set (ref $ht), which gives a better type for that local
  • C ⊢ (self $a) ≤ (ref $ht) so we still are a subtype of our declared type, obviously.
  • C ⊢ struct.get $t $f : (self $a) -> ft[(self $t) := (self $a)] where ft is the declared type of $f in (type $t ...) (unpack(zt) in the spec)
    • In other words, when you select a field on a (self $a), you get a precise substitution for (self $t).
  • Probably a similar rule for struct.set
• C ⊢ struct.get $t $f : (ref null? exact $t) -> ft[(self $t) := (ref exact $t)]
  • If we have an exact type, we know its self type is exactly itself, so we can substitute it
  • Similarly for struct.set, I believe.
• C ⊢ struct.get $t $f : (ref null? $t) -> ft[(self $t) := (ref $t)], provided that all (self $t) occur in covariant position
  • In other words, when a (self $t) escapes its defining scope, if we have an inexact reference, we cannot replace it with another (self $x), so it must be widened.
  • (Or we just disallow this entirely. We could require an exact type or a self type to access things that refer to the self type.)
  • Illegal if there is a (self $t) in contravariant or invariant position (because it cannot be soundly widened)
  • struct.set is illegal if there is a (self $t) in that case (or we allow it if it appears only in contravariant positions -- but that's probably useless)
• For struct.new $t, we substitute (self $t) by (ref exact $t) when validating the type of the fields. That's OK because we are constructing a (ref exact $t), for which we know the self-type is exactly itself.

And I think that's it? It might need some more rules for nulls.

We may not need to write (self $a) in source programs. It could be an administrative type if we want to. (We must be able to write (self $t) within (type $t ...), obviously.)