Inheritance, variants and protocols: a design sketch

1. The problem¶

In Python, you can write a base class, derive classes from it, and call a method on an object without knowing its exact class:

class Shape:
    def area(self) -> float:
        raise NotImplementedError

class Circle(Shape):
    def __init__(self, r: float) -> None:
        self.r = r

    def area(self) -> float:
        return self.r * self.r * 3.14159

def print_area(s: Shape) -> None:
    print(s.area())     # which `area`? It depends on the object received.

In an interpreter, dynamic dispatch is a dictionary lookup, which is slow but simple. SPy is a compiler, so it needs a cheaper mechanism. This page presents three of them, each adapted to a different situation:

Situation	Tool	Dispatch
a family of classes, open to extension by anyone	single inheritance + vtable (section 3)	dynamic, through a pointer stored in the object
a fixed list of alternatives, known in advance	variants (section 4)	dynamic, a `switch` on a tag stored in the object
unrelated types that happen to have the same methods	protocols (section 5)	dynamic, through a pointer stored next to the reference

There is also a fourth way, which needs nothing new: generic functions, for which the compiler produces one copy per type and dispatches statically (see the end of section 5).

2. Starting point: structs and the `@heap` pattern¶

All the “lowerings” below (the code that the compiler would generate from the user’s class) reuse the pattern of the @heap experiment (exp-heap-allocated-class). A reminder, simplified: this user code

@heap
class Point:
    x: i32
    y: i32

    def __init__(self, x: i32, y: i32) -> None:
        self.x = x
        self.y = y

    def norm2(self) -> i32:
        return self.x * self.x + self.y * self.y

is lowered to something like

from unsafe import gc_ptr, gc_alloc

@struct
class Point_data:            # the data: a plain struct (a value type)
    x: i32
    y: i32

@struct
class Point:                 # the wrapper: holds only a pointer to the data
    __ll__: gc_ptr[Point_data]

    def __new__(x: i32, y: i32) -> Point:
        self = Point.__make__(gc_alloc[Point_data](1))   # allocate one Point_data
        self.__ll__.x = x
        self.__ll__.y = y
        return self

    def norm2(self) -> i32:
        return self.__ll__.x * self.__ll__.x + self.__ll__.y * self.__ll__.y

gc_alloc[T](1) allocates one T on the garbage-collected heap and returns a gc_ptr[T].
Point.__make__(ptr) builds a Point from a pointer.
Copying a Point copies only the pointer, so two variables can refer to the same data: that is what gives reference semantics.
In the real @heap experiment, p.x is written instead of p.__ll__.x, thanks to a generated __getattribute__. In the lowerings below, we write __ll__ explicitly so that nothing is hidden.

The “class metaclass” (Antonio’s design)¶

A class statement is executed in three steps:

the type is “declared”;
the body is executed and its content is collected into a ClassBody;
the ClassBody is given to a metaclass, a function that creates the actual type.

Today @struct class selects the struct metaclass, and any other kind of class is rejected (see metaclass_for_classdef in spy/vm/astframe.py). The proposal is that a plain class selects a class metaclass, written in SPy itself (for example in stdlib/_class.spy), which turns the class into structs like the ones in this page. So inheritance needs no new runtime concept, only a generator of structs.

3. Single inheritance with a vtable¶

3.1 What the user writes¶

@heap
class Shape:
    def area(self) -> float:
        raise NotImplementedError

@heap
class Circle(Shape):
    r: float

    def __init__(self, r: float) -> None:
        self.r = r

    def area(self) -> float:
        return self.r * self.r * math.pi

@heap
class Rect(Shape):
    w: float
    h: float

    def __init__(self, w: float, h: float) -> None:
        self.w = w
        self.h = h

    def area(self) -> float:
        return self.w * self.h

def print_area(s: Shape) -> None:
    print(s.area())

def main() -> None:
    print_area(Circle(1.0))     # a Circle is accepted where a Shape is expected
    print_area(Rect(2.0, 3.0))

The goal is that print_area is compiled once, and still calls the right area for each object.

3.2 The idea: a table of functions per class¶

Here Shape has one virtual method, so the vtable of Shape has one slot, area. The vtable of Circle has the same layout, with the slot pointing to the function that computes the area of a circle.

Another constraint: a Circle must look like a Shape in memory, so that the code compiled for Shape works on it. This is obtained by putting the parent’s data first in the data of the child. A CircleObject starts with a ShapeObject, so a pointer to the former is also (at the same address) a pointer to the latter.

3.3 What the compiler generates (lowering)¶

For the user code above, the class metaclass would produce something like the following. First the root class, Shape:

from unsafe import gc_ptr, static_ptr, gc_alloc, ptr_cast, addr_of   # ptr_cast, addr_of: invented

@struct
class ShapeVTable:
    # One slot per virtual method. The first argument is always a pointer to the
    # *root* object: this way, every subclass can put in the slot a function with
    # exactly this type.
    area: FnPtr[[gc_ptr[ShapeObject]], float]    # invented: a pointer to a function

@struct
class ShapeObject:
    _vtable: static_ptr[ShapeVTable]    # first field of every object of the hierarchy

@struct
class Shape:
    __ll__: gc_ptr[ShapeObject]

    # The method seen by the callers: it only looks up the function in the vtable.
    def area(self) -> float:
        return self.__ll__._vtable.area(self.__ll__)

    # The body written by the user in `class Shape`, under another name.
    def _area_impl(self) -> float:
        raise NotImplementedError

# An adapter (see below) stored in the vtable of Shape.
def Shape_area_thunk(obj: gc_ptr[ShapeObject]) -> float:
    return Shape.__make__(obj)._area_impl()

Shape_vtable = ShapeVTable(area=Shape_area_thunk)    # a constant, created once

Note that _vtable is a plain static_ptr, not a gc_ptr: the vtables are constants created once, not objects allocated on the garbage-collected heap.

Then each subclass. Here is Circle (Rect is the same with w and h):

@struct
class CircleObject:
    parent: ShapeObject      # the parent's data comes first
    r: float

@struct
class Circle:
    __ll__: gc_ptr[CircleObject]

    def __new__(r: float) -> Circle:
        self = Circle.__make__(gc_alloc[CircleObject](1))
        # The vtable must be set *before* calling __init__, so that a virtual
        # call made from an __init__ already works.
        self.__ll__.parent._vtable = addr_of(Circle_vtable)
        self.__init__(r)
        return self

    def __init__(self, r: float) -> None:
        self.__ll__.r = r

    # Free upcast: same address, seen as a pointer to the parent's data.
    def __upcast__(self) -> Shape:
        return Shape.__make__(ptr_cast[gc_ptr[ShapeObject]](self.__ll__))

    # The body written by the user in `class Circle`, under another name.
    def _area_impl(self) -> float:
        return self.__ll__.r * self.__ll__.r * math.pi

def Circle_area_thunk(obj: gc_ptr[ShapeObject]) -> float:
    return Circle.__make__(ptr_cast[gc_ptr[CircleObject]](obj))._area_impl()

Circle_vtable = ShapeVTable(area=Circle_area_thunk)

Circle has no method area of its own in the lowered code. When the compiler sees c.area() with c: Circle, the lookup finds the method of the parent, and the receiver is converted with __upcast__. So c.area() is the same as c.__upcast__().area().

3.4 What happens at a call¶

print_area(Circle(1.0))

# 1. the argument is upcast (implicit conversion inserted by the compiler):
print_area(Circle(1.0).__upcast__())

# 2. inside print_area, `s.area()` is the dispatcher of Shape:
s.__ll__._vtable.area(s.__ll__)

# 3. the object was created by Circle.__new__, so _vtable points to Circle_vtable,
#    and the `area` slot holds Circle_area_thunk. The call becomes:
Circle_area_thunk(s.__ll__)

# 4. which calls the user's code:
Circle.__make__(...)._area_impl()      # r * r * pi

In memory:

 object (on the GC heap)            Circle_vtable (constant)
+--------------------------+       +---------------------------------+
| _vtable   ---------------+-----> | area  ->  Circle_area_thunk     |
| r = 1.0                  |       +---------------------------------+
+--------------------------+

The cost of a virtual call is two memory reads and an indirect call, instead of a direct call. It is a small cost, but a direct call can be inlined by the C compiler, which an indirect call cannot, so this is where most of the overhead comes from in tight loops.

3.5 Should methods be virtual by default?¶

(Antonio’s design, undecided.) There are three options:

Option	For	Against
every method is virtual	simplest, same as Python	every call pays; Python itself relies on a JIT to hide this cost
methods are virtual only if marked (as in C++)	best performance	verbose; Antonio dislikes the “C++ vibes”
a method is virtual if some subclass overrides it (as in RPython)	automatic	needs to see the whole program at once, which prevents separate compilation

Antonio’s tentative compromise: virtual by default, with a way to devirtualize, plus advice to use variants (section 4) when the set of alternatives is closed.

“Virtual by default” does not mean that every call pays. Redshift knows the static type of the receiver:

@final                       # invented: no subclass allowed
class Circle(Shape):
    ...

def f(c: Circle) -> float:
    return c.area()          # direct call to Circle._area_impl: no vtable

def g(s: Shape) -> float:
    return s.area()          # a Shape can be anything: vtable call

3.6 Still to settle¶

Function pointers do not exist in SPy yet, and are the first prerequisite.
isinstance and downcasts need an identifier of the class stored in the vtable, to check the real class of an object.
A subclass that adds a virtual method needs a longer vtable, whose first slots are those of the parent: CircleVTable would start with a parent: ShapeVTable field, exactly like the data does.
Overriding rules: the signature of an override must be compatible with the signature of the overridden method, checked when the class is created.
Multiple inheritance is out of scope, except possibly a limited “mixin” form (low priority). Protocols (section 5) may remove the need since they can carry default methods (section 5.8).

4. Variants¶

4.1 The idea¶

Sometimes the list of alternatives is fixed and known in advance: a shape is a circle or a rectangle, and nothing else. Several languages have a construct for this, often called sum type, enum with data, or variant. For example in Rust:

enum Shape {
    Circle(f64),
    Rect(f64, f64),
}

fn area(s: &Shape) -> f64 {
    match s {
        Shape::Circle(r)  => r * r * std::f64::consts::PI,
        Shape::Rect(w, h) => w * h,
    }
}

Zig has union(enum), OCaml has type shape = Circle of float | Rect of float * float. Python has nothing equivalent. Antonio thinks that SPy should have them (name: Variant) and that they would be one of its big advantages over Python.

4.2 What the user writes¶

(Antonio’s first sketch declared Circle and Rect as separate classes deriving from Shape, which creates three public classes for one concept. Here the cases are declared inside the variant, so only Shape is visible outside, as in Rust.)

@variant                         # invented
class Shape:
    @struct
    class Circle:
        r: float

    @struct
    class Rect:
        w: float
        h: float

    def area(self) -> float:
        match self:              # invented: match on a variant
            case Shape.Circle(r):
                return r * r * math.pi
            case Shape.Rect(w, h):
                return w * h

def main() -> None:
    a = Shape.Circle(1.0)        # both have the same type: Shape
    b = Shape.Rect(2.0, 3.0)
    print(a.area())
    print(b.area())

There is one type, Shape. Shape.Circle(1.0) and Shape.Rect(2.0, 3.0) are two ways to build a value of this type. There are no virtual methods and no overriding: a method is written once, and it handles each case with match.

4.3 What the compiler generates (lowering)¶

@struct
class ShapeCircle:
    r: float

@struct
class ShapeRect:
    w: float
    h: float

@struct
class ShapeObject:
    discriminant: i32                               # 0: Circle, 1: Rect
    payload: ll_union[ShapeCircle, ShapeRect]     # invented

@struct
class Shape:
    __ll__: gc_ptr[ShapeObject]

    def area(self) -> float:
        obj = self.__ll__
        if obj.discriminant == 0:                   # case Circle
            r = obj.payload.Circle.r                # invented: read as a Circle
            return r * r * math.pi
        if obj.discriminant == 1:                   # case Rect
            w = obj.payload.Rect.w
            h = obj.payload.Rect.h
            return w * h
        unreachable()                               # invented: the tag is always 0 or 1

    # One constructor per case: `Shape.Circle(1.0)` and `Shape.Rect(2.0, 3.0)`
    # in the user code call these class methods.
    @classmethod
    def Circle(cls, r: float) -> Shape:
        obj = gc_alloc[ShapeObject](1)
        obj.discriminant = 0
        obj.payload.Circle = ShapeCircle(r)
        return cls.__make__(obj)

    @classmethod
    def Rect(cls, w: float, h: float) -> Shape:
        obj = gc_alloc[ShapeObject](1)
        obj.discriminant = 1
        obj.payload.Rect = ShapeRect(w, h)
        return cls.__make__(obj)

The constructors belong to Shape, like __new__ in section 2: they are attributes of the type, which is why the user writes Shape.Circle(1.0). They are class methods (they receive the class, cls, instead of an instance), because there is no Shape to call them on yet.

So a.area() is a direct call to Shape.area, which tests the tag. There is no vtable and no function pointer.

4.4 Why `match` is the natural partner¶

The match statement is not just a prettier if chain:

It reads the right data. case Shape.Rect(w, h) checks the tag and gives names to the fields of that case in one step. Written by hand, as in the lowering above, it is easy to read payload.Rect while the tag says Circle, which reads garbage. With match, the compiler generates the read right after the check, so this error cannot happen.
It can be checked for completeness. Since the list of cases is fixed, the compiler knows them all. If a match forgets Shape.Rect, it is a compile-time error instead of a bug found later. When a Triangle case is added to the variant, the compiler points at every match to update. With a class hierarchy, this is impossible, because other packages may add subclasses that the compiler has never seen.
It is fast. A match is a comparison of the tag, which the C compiler turns into a jump table. Nothing needs to be followed through a pointer.

4.5 The price: a sealed hierarchy¶

The set of cases is sealed: nobody can add a case from another package (it would need a larger union and new branches in every match). The two designs trade flexibility in opposite directions:

You want to...	with classes (vtable)	with variants
add a new kind of shape	easy: write a subclass, nothing else changes	hard: every `match` must be updated (the compiler lists them)
add a new operation (`perimeter`)	hard: every class must be updated	easy: one new method with one `match`

This is why both exist. Antonio’s suggestion is “virtual methods by default, and teach people to use variants when it makes sense”, because there are cases where plain object-oriented programming remains the best choice.

4.6 By reference or by value?¶

In the lowering above, Shape holds a gc_ptr[ShapeObject]: every Shape.Circle(1.0) allocates an object on the heap, and copying a Shape copies the pointer (reference semantics). This is Antonio’s version.

Rust and Zig do it differently: the variant is a value, stored inline in the variable, with no allocation:

@struct
class Shape:
    discriminant: i32
    payload: ll_union[ShapeCircle, ShapeRect]    # invented

Its size is that of the tag plus the largest case. Copying a Shape copies all of it (a few words), and there is no pointer to follow. It is cheaper for small cases like these, but expensive to copy if one case is large, and it cannot be shared between variables. Which one is the default, and whether both are offered, is an open question.

5. Protocols¶

5.1 What the user writes¶

A protocol describes a set of methods. Any type that has these methods conforms to it, without declaring it:

@protocol
class Shape:
    def area(self) -> float: ...

@heap
class Circle:                    # no mention of Shape
    r: float

    def __init__(self, r: float) -> None:
        self.r = r

    def area(self) -> float:
        return self.r * self.r * math.pi

@heap
class Rect:                      # no mention of Shape either
    w: float
    h: float

    def __init__(self, w: float, h: float) -> None:
        self.w = w
        self.h = h

    def area(self) -> float:
        return self.w * self.h

def print_area(s: Shape) -> None:
    print(s.area())

def main() -> None:
    print_area(Circle(1.0))      # works: Circle has `area(self) -> float`
    print_area(Rect(2.0, 3.0))   # works too

The interest compared to inheritance: Circle and Rect need no common base class, and a protocol can be defined after the classes, for classes written by someone else.

5.2 The problem¶

print_area must be compiled once, but Circle and Rect have different layouts and different area functions, and they have no common vtable pointer at the start (they do not share a parent). Where can the table of functions be stored?

Antonio’s answer: next to the reference, not in the object. This is what Rust does for dyn Trait and Go for its interfaces.

5.3 What the compiler generates (lowering)¶

First, the protocol itself becomes a two-word struct and a table type:

@struct
class ShapeVTable:
    # self is "erased": an untyped pointer
    area: FnPtr[[gc_ptr[void]], float]           # invented (`void`: untyped)

@struct
class Shape:                        # what `@protocol class Shape` becomes
    data: gc_ptr[void]              # word 1: the object, type erased
    vtable: static_ptr[ShapeVTable] # word 2: its table of methods

    def area(self) -> float:      # a call on a protocol value
        return self.vtable.area(self.data)

Then, for each pair (protocol, concrete type) that the compiler sees used together, it generates a table and a conversion. Here for (Shape, Circle), triggered by the call print_area(Circle(1.0)):

# 1. a thunk: restores the type of the erased pointer and calls the real method
def Circle_as_Shape_area(data: gc_ptr[void]) -> float:
    c = Circle.__make__(ptr_cast[gc_ptr[Circle_data]](data))
    return c.area()

# 2. the table, created once (a constant)
Circle_as_Shape_vtable = ShapeVTable(area=Circle_as_Shape_area)

# 3. the conversion, inserted by the compiler at the call site
def Circle_to_Shape(c: Circle) -> Shape:
    return Shape(
        data=ptr_cast[gc_ptr[void]](c.__ll__),
        vtable=addr_of(Circle_as_Shape_vtable),
    )

# so `print_area(Circle(1.0))` is compiled as:
print_area(Circle_to_Shape(Circle(1.0)))

(Circle_data is the data struct of the @heap class Circle, as Point_data in section 2.) The pair (Shape, Rect) gets its own thunk, table and conversion, built the same way.

Why a pair, and why a thunk? The table depends on both sides: the protocol decides which slots exist and in which order, and the concrete type decides which functions go in them. And the slot has a fixed type (it receives an untyped pointer, since print_area does not know the type), while Circle.area expects a Circle: the thunk is the adapter, as in section 3.3.

In memory, for s = Circle_to_Shape(Circle(1.0)):

 s (two words, in registers or on the stack)
+-----------+-----------+
|   data    |  vtable   |
+-----+-----+-----+-----+
      |           |
      v           v
 +----------+   +----------------------------------------+
 | r = 1.0  |   | area -> Circle_as_Shape_area           |   (constant)
 +----------+   +----------------------------------------+
 Circle object (GC heap)

5.4 Calling through a protocol¶

def print_area(s: Shape) -> None:
    print(s.area())
# is compiled as:
#   s.vtable.area(s.data)
#   -> Circle_as_Shape_area(s.data)     (when s came from a Circle)
#   -> Circle.__make__(...).area()      (the user's code)

The code of print_area is the same for any type, and it is compiled once.

5.5 Comparison with the inheritance vtable¶

	inheritance vtable (section 3)	protocol fat pointer
where the pointer to the table is	in every object (first field)	next to each reference
size of a reference	1 word	2 words
cost per object	1 word	none
which types can conform	subclasses only, declared when the class is written	any type, including existing ones (types of another package, or even `i32` if boxed)
conversion to the general type	free upcast (same address)	builds the two-word value; the table already exists

5.6 Restrictions to expect¶

These are the restrictions that Rust (“object safety”) and Go also have:

No Self in the signatures. A protocol method cannot take or return “another object of the same concrete type” (def merge(self, other: Self)), since the concrete type is erased.
No generic or blue methods in the protocol, since a table needs one fixed function per slot.
Attributes are harder. typing.Protocol allows r: float. Here, each attribute would need a generated getter thunk in the table (a function def get_r(data: gc_ptr[void]) -> float, like the method thunks), and a setter for writable attributes. Probably methods only, at first. (Section 5.9 shows that default methods can still rely on required attributes without any getter, since they are compiled for each class. Only reading an attribute through the fat pointer needs one.)
Value types must be boxed. The data word is a pointer, so a plain struct (a value on the stack) has to be copied to the heap before it can be converted to a protocol.
Converting a protocol to a smaller one (Shape to a protocol that has only some of its methods) needs a new table, and cannot be done for free from the erased Shape alone.

5.7 The static alternative: protocols as constraints¶

A protocol can also describe what a generic function needs from its parameter, without any fat pointer:

def print_area_generic[T: type.implements(Shape)](s: T) -> None:      # invented syntax
    print(s.area())

print_area_generic[Circle](Circle(1.0))
print_area_generic[Rect](Rect(2.0, 3.0))

So the same protocol would have two modes: static when the parameter is generic (no cost, one copy of the code per type), and dynamic when the parameter is typed Shape itself (a fat pointer, one copy of the code). The dynamic mode is really needed only for values of different types stored together, such as a list[Shape] containing circles and rectangles.

5.8 Default methods and explicit conformance¶

So far, a protocol only describes: it lists methods that other types must provide. But the types that conform often need the same helper method, which could be written once, in terms of the required methods. We would like the protocol to carry such a method, and a class to be able to take it, in order to share code.

What the user writes. The protocol Shape gets a default method show, and Circle declares that it implements Shape:

@protocol
class Shape:
    def area(self) -> float: ...          # required method: no body

    def show(self) -> None:               # default method: has a body
        print(self.area())

@heap
class Circle(Shape):                      # explicit conformance
    r: float

    def __init__(self, r: float) -> None:
        self.r = r

    def area(self) -> float:
        return self.r * self.r * math.pi
    # no `show` here: it comes from Shape

def print_area(s: Shape) -> None:
    print(s.area())

def main() -> None:
    c = Circle(1.0)
    c.show()                              # works: Circle received `show` from Shape
    print_area(c)                         # works as in section 5.1

class Circle(Shape) reuses the syntax of inheritance, but it is not the inheritance of section 3: no data is inherited, and no vtable pointer is added to the objects. The class only receives methods. This may deserve another spelling (see the open questions).

What the compiler generates. First, the class. The class metaclass (section 2) sees that Shape is a protocol. It checks that every required method is present in Circle (otherwise the error is reported when the class is created, not later), and it adds to Circle a copy of each default method that Circle does not define:

@struct
class Circle_data:
    r: float

@struct
class Circle:
    __ll__: gc_ptr[Circle_data]

    def __new__(r: float) -> Circle:
        self = Circle.__make__(gc_alloc[Circle_data](1))
        self.__init__(r)
        return self

    def __init__(self, r: float) -> None:
        self.__ll__.r = r

    def area(self) -> float:                      # the user's code
        return self.__ll__.r * self.__ll__.r * math.pi

    def show(self) -> None:                       # a copy of the default method, for Circle
        print(self.area())                        # = print(Circle.area(self)): a direct call

In the copy, self has type Circle. So self.area() is resolved at compile time to Circle.area: it is a direct call, without vtable. This is the monomorphization of section 5.7. The protocol keeps show as a generic function of the class, and the metaclass instantiates it for each class that implements the protocol. Written with the tools of SPy, the mechanism is:

@blue.generic
def Shape_show(Self):                  # the default method, as kept by the protocol
    def impl(self: Self) -> None:
        print(self.area())
    return impl

# done by the class metaclass, once the type Circle exists:
#     Circle.show = Shape_show[Circle]       # invented

Then the fat pointer (section 5.3). For the code that receives a Shape, a default method is a method like any other: it has a slot in the table, and the thunk calls the copy made for the class.

@struct
class ShapeVTable:
    area: FnPtr[[gc_ptr[void]], float]            # invented
    show: FnPtr[[gc_ptr[void]], None]             # invented: a default method has a slot too

@struct
class Shape:
    data: gc_ptr[void]
    vtable: static_ptr[ShapeVTable]

    def area(self) -> float:
        return self.vtable.area(self.data)

    def show(self) -> None:
        self.vtable.show(self.data)

# thunks for the pair (Shape, Circle), as in section 5.3
def Circle_as_Shape_area(data: gc_ptr[void]) -> float:
    c = Circle.__make__(ptr_cast[gc_ptr[Circle_data]](data))
    return c.area()

def Circle_as_Shape_show(data: gc_ptr[void]) -> None:
    c = Circle.__make__(ptr_cast[gc_ptr[Circle_data]](data))
    c.show()

Circle_as_Shape_vtable = ShapeVTable(
    area=Circle_as_Shape_area,
    show=Circle_as_Shape_show,
)

The thunk Circle_as_Shape_show has exactly the same form as the one for area: it does not know whether show was written in Circle or came from Shape. So the table has no special case for default methods.

Why a copy for each class? The other possibility is to compile show only once, with self: Shape (a fat pointer). The code is smaller, but then self.area() inside show is a dynamic call through the table, and self is type-erased, so the attributes of the class cannot be read (section 5.9). The copy per class gives a direct call and access to the fields, at the price of one more compiled function per class, which is the usual price of monomorphization.

Rules. They are chosen to stay simple:

Required or default is decided by the presence of a body.
The class wins. If Circle defines show, this version is used, and the default is not copied.
Two protocols with the same default method is an error, unless the class defines the method itself. This avoids the “which parent first” rules of Python’s multiple inheritance (the MRO).
Only methods are shared. A protocol never adds data to the objects (see section 5.9 for attributes). Otherwise the layout of a class would depend on its protocols, and there would be the diamond problem again.
Only explicit conformance gives the methods to the class. A class that does not name the protocol never receives show.

What about implicit conformance? Consider Rect, which defines area but does not name Shape. Two choices:

Rect conforms only if it has all the methods of Shape, including show. Simple, but a protocol with default methods is then useful only to classes that name it.
Rect conforms if it has the required methods. When the compiler builds the table for (Shape, Rect), it fills the show slot with the default method instantiated for Rect. Then print_area(Rect(...)) works, but Rect(...).show() does not exist, which is a bit surprising.

Choice 1 is the simplest to explain. Choice 2 keeps the main interest of protocols (types that were written without knowing the protocol). Open question.

5.9 Required attributes¶

A default method often needs data, not only the other methods. For example, a mass method needs a density. This looks contradictory with “a protocol has no data”. The way out is to separate requiring an attribute from storing it.

What the user writes. The attribute is declared in the protocol, and declared again in each class, which owns the storage:

@protocol
class Shape:
    density: float                        # required attribute: a requirement, not a field

    def area(self) -> float: ...          # required method

    def mass(self) -> float:              # default method, uses the attribute
        return self.density * self.area()

@heap
class Circle(Shape):
    r: float
    density: float                        # must be declared: the class owns the storage

    def __init__(self, r: float, density: float) -> None:
        self.r = r
        self.density = density

    def area(self) -> float:
        return self.r * self.r * math.pi

Why does the class declare the attribute again? Three reasons:

The class stays the only place that decides its memory layout, and the order of its fields. If a protocol could add fields, the layout would depend on the order of the protocols in the class statement.
If two protocols require the same attribute, there is a single field in the class (the one that the user wrote), and not two fields with the same name.
A class that conforms implicitly has to declare the attribute anyway. With this rule, explicit and implicit conformance require exactly the same thing from the class. The only difference is that explicit conformance also brings the default methods.

If the user wants the protocol to provide the field too, this is inheritance of data, which is the job of classes (section 3).

What the compiler generates. The metaclass checks that Circle has a field density of type float (exactly this type: the offset and the size of the field must be the ones that the default method expects). Then it copies mass into Circle, as it did for show:

@struct
class Circle_data:
    r: float
    density: float                                # declared by the user in Circle

@struct
class Circle:
    __ll__: gc_ptr[Circle_data]

    def __new__(r: float, density: float) -> Circle:
        self = Circle.__make__(gc_alloc[Circle_data](1))
        self.__init__(r, density)
        return self

    def __init__(self, r: float, density: float) -> None:
        self.__ll__.r = r
        self.__ll__.density = density

    def area(self) -> float:                      # the user's code
        return self.__ll__.r * self.__ll__.r * math.pi

    def mass(self) -> float:                      # a copy of the default method, for Circle
        return self.__ll__.density * self.area()

In the copy, self.density became self.__ll__.density: a read at a fixed offset, known at compile time because self is a Circle. This is the second reason (after the direct call to area) to compile the default method for each class. With an erased self, the offset of density would be unknown.

The table is built as in section 5.8. It has a slot for mass, and none for density:

@struct
class ShapeVTable:
    area: FnPtr[[gc_ptr[void]], float]            # invented
    mass: FnPtr[[gc_ptr[void]], float]            # invented

def Circle_as_Shape_mass(data: gc_ptr[void]) -> float:
    c = Circle.__make__(ptr_cast[gc_ptr[Circle_data]](data))
    return c.mass()

What is visible through the fat pointer. Only the methods:

def total_mass(s: Shape) -> float:
    return s.mass()            # fine: a method, so a slot of the table
    # return s.density         # error: `s.data` is erased, the offset of `density` is unknown

Reading s.density on a Shape value would need a getter thunk in the table (section 5.6). In this first version, a required attribute is guaranteed to exist in the class, and it can be used by the default methods and by generic functions (section 5.7, where s: Circle is a known type), but not through the fat pointer.

Spelling. Python’s typing.Protocol already offers two ways to write a requirement, which could be reused:

Spelling	Example	For	Against
bare annotation	`density: float`	the spelling of `typing.Protocol`, no new syntax; read-write (a default method may assign it)	in a normal class the same line is a field, so the reader must know that the base is a protocol
explicit marker	`density: Required[float]`	visible at the first glance	a new name in the language
property	`@property` then `def density(self) -> float: ...`	read-only; satisfied by a field or a computed property; works through the fat pointer, since it is a method, so a getter slot	read-only only, and longer to write

The bare annotation is the simplest for a first version. The property form is the right tool for read-only requirements, and it also solves the access through the fat pointer, because a property is just a method. The two can coexist.

5.10 What this does not give¶

Default methods share code, not data, and only for types that name the protocol. In particular, a protocol cannot add a method to a type that you do not control (a type of another package, or a built-in type): that would need a separate construct, such as impl Protocol for Type in Rust, which is left out here.

6. Choosing¶

You have...	Use
a family of classes with shared data and behavior, which other packages may extend	classes with inheritance (vtable)
a closed list of alternatives, and you want `match` with checks and the best speed	variants
unrelated types that share some operations, or types you do not control	protocols (generics if the types are known at compile time)

Antonio notes that these concepts overlap, and that the aim is to find what is really needed without making the language too complicated.

7. What differs from Antonio’s first sketch¶

The vtable slot function and the user’s method are separated: the root class has a dispatcher (Shape.area, which reads the vtable) and every class has an implementation (_area_impl). In the first sketch, Circle.area both contained the user’s code and called the vtable, which would loop forever.
All the slots of a vtable have the same type (a pointer to the root object), with a thunk per class, instead of a type depending on the class. This also removes the need for a hidden conversion in the call.
Variant cases are declared inside the variant, and the methods are written on the variant with match.
Vtable pointers are static_ptr to constants instead of gc_ptr.
The protocol lowering and the by-value variant are not detailed in the first sketch (the fat pointer was only mentioned); they are fully written here.

8. Open questions¶

Virtual by default? Which syntax to devirtualize (@final, sealed classes, automatic for variants)?
By reference or by value for variants (section 4.6)?
What is Shape.Circle exactly? It is a constructor (Shape.Circle(1.0)), but also appears in a pattern (case Shape.Circle(r)). In Python, a class pattern requires a class there. Either Shape.Circle is a small nested type whose __new__ returns a Shape and which match knows how to test and destructure, or match has a special rule for variant cases (as in Rust, where a case is a constructor and a pattern, not a type).
How should required attributes be spelled (section 5.9): a bare annotation, a marker, or a read-only @property? Should they be readable through the fat pointer (getter slots)?
Is the limited mixin-style multiple inheritance still needed once protocols exist? Default methods (section 5.8) already share code between classes. What is left for mixins is shared data.
Spelling of explicit conformance: class Circle(Shape) looks like inheritance, but only methods are received. Would implements, or another word, be clearer?
Implicit conformance and default methods (section 5.8): must the type have the default methods too, or does the compiler fill the slot with the default?
How should @heap be shaped so that the class metaclass can be built on it (the parent’s data as first field, room for the vtable pointer)?