Polymorphic Is Polymorphic

1

Polymorphic Is Polymorphic

Usually, when people talk about polymorphism, they mean OOP polymorphism.

Objects of different subclasses are converted to a common base type, and different concrete objects produce different behavior.

In Rust, this corresponds to converting values of different concrete types into a dyn Trait, and then getting different behavior depending on the underlying concrete type.

But Rust also has another kind of polymorphism: generic polymorphism—-Zpolymorphize.

Normally, a generic function is compiled into different binary instances for different Ts:

foo::<i32>
foo::<f64>
foo::<String>

These usually produce different compiled functions.

However, if a generic function produces the same binary code for every T, then that generic function is itself polymorphic.

My point is:

These two forms of polymorphism are actually the same thing.

Or, more precisely, generic polymorphism is the essence, while OOP-style dynamic polymorphism is only one special case of it.

A Polymorphic Generic Function

Consider this generic function:

bool selfCompareT(
    T *obj,
    bool (*compare)(T *, T *)
) {
    return compare(obj, obj);
}

This function does only one thing:

compare(obj, obj);

It does not inspect T.

It does not use:

sizeof(T)

It does not access any fields of T.

It only forwards the pointer to the function pointer.

Now instantiate it for int:

bool selfCompareInt(
    int *obj,
    bool (*compare)(int *, int *)
) {
    return compare(obj, obj);
}

And instantiate it for double:

bool selfCompareDouble(
    double *obj,
    bool (*compare)(double *, double *)
) {
    return compare(obj, obj);
}

Although the C types are different, the generated binary logic is the same.

Both functions do this:

load obj
load compare
call compare(obj, obj)
return

So selfCompareInt and selfCompareDouble are binary-compatible.

For this function, T is not really used.

Only the pointer and the function pointer are used.

Binary Compatibility Means They Can Be Mixed

Since selfCompareInt and selfCompareDouble have the same binary behavior, they can be mixed at the binary level.

Suppose we have:

bool compareInt(int *a, int *b) {
    return *a == *b;
}

Then:

int x = 42;

selfCompareDouble(
    (double *)&x,
    (bool (*)(double *, double *))compareInt
);

From the binary point of view, this still follows the same protocol.

Even though the function is called as:

selfCompareDouble

the actual object is still an int, and the actual comparison function is still compareInt. Only the outer type view has changed, so the code still works.

This shows the important point:

The generic function itself does not care what T is.

It only cares that obj and compare belong to the same T.

The Problem: Separate Arguments Can Be Mismatched

Now the real problem appears.

Because the original function takes two independent arguments:

selfCompareT(obj, compare)

it is possible to pass mismatched arguments.

For example:

bool compareDouble(double *a, double *b) {
    return *a == *b;
}

Then:

int x = 42;

selfCompareDouble(
    (double *)&x,
    compareDouble
);

This is wrong.

The object is actually an int, but the comparison function expects double *.

Therefore, the memory of an int is interpreted as a double, so the code cannot work.

The Solution: Package the Pair, Then Cast the Whole Package Once

The solution is not to cast obj and compare separately.

That means: package them together first, and then erase the whole package at once.

For int, define:

typedef struct {
    int *obj;
    bool (*compare)(int *, int *);
} ComparableInt;

For double, define:

typedef struct {
    double *obj;
    bool (*compare)(double *, double *);
} ComparableDouble;

Now construct an int comparable object:

int x = 42;

ComparableInt ci = {
    &x,
    compareInt
};

At this point, the pair is correct:

int object
+
int comparison function

Now define an incomplete erased type:

typedef struct T T;

There is no definition of struct T.

Therefore, we do not know:

sizeof(T)
the layout of T
the fields of T

Define the erased comparable type:

typedef struct {
    T *obj;
    bool (*compare)(T *, T *);
} ComparableT;

Now erase the whole package once:

ComparableT ct = *(ComparableT *)&ci;

Erasing it once means that we no longer know the real type of T, but all fields of ComparableT still come from the same T. Every field still matches every other field.

Now write:

bool selfCompareT(ComparableT c) {
    return c.compare(c.obj, c.obj);
}

And call:

selfCompareT(ct);

selfCompareT is binary-compatible. It does not need to know the concrete type of T, because all the types inside the package are the same. It only needs to call the function.

The accept Form

To make this truly type-safe, I propose the accept form:

comparable.accept(selfCompareT)

Or, more generally:

dyn_trait.accept(generic_function)

This is type-safe if the following conditions are satisfied:

  1. Every dyn_trait can only be created once, and afterward it can only be accessed or modified through accept.
  2. We use dyn_trait.accept, so each call to accept unpacks only one dyn_trait at a time. This means values from different dyn_traits can never be mixed together.
  3. dyn_trait.accept(generic_function) needs to return a type. Its return type is the return type of generic_function, which means that generic_function must return one exact type.

Comparison with Traditional dyn_trait.virtual_function

Traditional dynamic dispatch is written as:

dyn_trait.virtual_function(...)

The alternative form is:

dyn_trait.accept(generic_function)

Both of them will:

load object pointer
load function pointer
call function pointer

Therefore:

dyn_trait.virtual_function(...)

can be rewritten as:

dyn_trait.accept(generic_function)

This is not only a syntactic equivalence. The generated binary is equivalent as well.

But the Reverse Is Not True

The reverse is not true.

Some programs can be expressed as:

dyn_trait.accept(generic_function)

but cannot be expressed as:

dyn_trait.virtual_function(...)

For example:

trait Comparable {
    fn compare(&self, other: &Self) -> bool;
}

fn self_compare<T: Comparable>(x: &T) -> bool {
    x.compare(x)
}

Traditional Rust dyn Trait rejects this because:

fn compare(&self, other: &Self) -> bool

is not dyn-compatible.

Therefore, this form:

comparable.accept(selfCompareT)

can express, with zero-cost abstraction, something that the traditional form:

dyn_trait.virtual_function(...)

cannot express.

Therefore:

dyn_trait.accept(generic_function)

is strictly more expressive.

The Real Requirement Behind Dyn Compatibility

From this perspective, Rust's current dyn-compatibility rules are too restrictive. We do not care whether Self appears only in the receiver. Self and associated types are both acceptable. We only care whether they are used behind a pointer or reference.

For example:

fn clone(&self) -> Self

is not binary-compatible. But:

fn clone_box(&self) -> Box<Self>

is binary-compatible because it returns Self through a box.

What's more, as mentioned above, "generic_function must return one exact type.", if we want to clone, we cannot return Box direclty, but wrapper it in generic function and rewrapped it to exact type, which can help us get rid of dyn clone marco.

How to Handle Two dyn Values

As we all know, Rust needs dyn compatibility because we cannot safely use two independent dyn values at the same time:

compare(dyn a, dyn b)

Yes, this is unsafe, because a and b may have different concrete types. The new accept form cannot automatically make this type-safe. As mentioned above, this code would not compile under the new accept form.

But the question is: do a and b really come from different types?

In most situations, the answer is no. Developers already know that a and b have the same type, but the type system cannot represent that fact. The same-type information has been lost.

The accept form provides a way to preserve it. For example:

struct Pair<T> {
    a: T,
    b: T,
}

With the accept mechanism, we can erase the type of the entire pair at once while preserving the information that a and b have the same type.

In traditional OOP, we can only erase the types of a and b separately, because dyn Trait does not support this kind of associated type relationship.

Widely Used UB

Earlier, we used casts in C. In theory, this is UB. However, for a virtual function, the first param is this, this has type, but this always has been type erasure to void*. So, people has used such type cast long time ago and main compiler and main compiler option (even with O3) can compile it correct.

Forget the UB, the most important thing is: **It is not a new invention. We have simply rediscovered what type erasure really is. **

Conclusion

dyn_trait.accept(generic_function)

is more powerful than:

dyn_trait.virtual_function(...)

because:

  1. Every virtual_function can be represented by a generic_function, and the generated binary is the same.
  2. A generic_function can safely represent more situations.

In other words, we have increased the expressive power of dyn Trait with type safe and without sacrificing performance. This is zero-cost abstraction.
We have not invented anything new. We have simply used existential types to provide a broader explanation of type erasure which has long been implemented in C, C++, and Rust.

I do not want to spend too much time discussing type theory, but from the perspective of existential types, this is basically the expressive limit of type erasure.

Further Thoughts

  1. We know that RTTI fundamentally violates LSP, so the ideal situation is to never use RTTI. This is also the core motivation of this article. Can this approach truly eliminate RTTI? I think it may be possible, because much of the real need for RTTI comes from the loss of type information in traditional OOP, which then has to be recovered through RTTI. Whether every use of RTTI can be eliminated is difficult to say. The issue is complex, but for now I have not found a counterexample.

  2. Can we somehow use the size information of T so that value types can also be used with dyn? To some extent, I think this is possible, but it would introduce overhead and make the syntax more complicated. I have not fully worked it out. At the same time, the current expressive power is already sufficient, because every value can be placed on the heap.

PS: Originally discussed here, hope these one more clear.

2

If you're proposing extensions to the language, that is probably better suited for IRLO.

Only if Self: Sized. If that is not the case, Box<Self> is not a single pointer, it's a pointer and some metadata.

3

personally this seems like an extension of the language with little to no utilty.
i'd be interested in seeing an real life example where you'd use it.

5

What is the actual problem you want to solve? I don't get it.