unipoly

The lib is aimed to support really existential type in difference language, which support the most powerful dynamic polymorphic, which is nearly powerful like static polymorphism.

motivation

In most of programming languages, they provide dynamic reflections, which is hard to implement. Even if somebody implement it, it's still hard to understand, slowly and full of bugs and limitations. However, do we really need dynamic reflection? In most of dynamic reflection cases, people just use dynamic reflection to recover some type information we already know but wrongly erased previously. And we erase these type information because original sub-type polymorphism is not powerful enough to represent them. If we use existential type, we can keep these type information so no need for dynamic reflection.

use polymorphic generic for dynamic dispatch

static polymorphic is more powerful expressive

Let we study a Rust word: dyn compatibility. In Rust, not all trait can be convert to dyn trait, only dyn compatibility trait can. Rust use trait for static polymorphic and use dyn trait for dynamic polymorphic, that means, static polymorphic is more powerful expressive than dynamic polymorphic. The key reason is: for static polymorphic, all parameter type is static, the compiler know all type information. But for dynamic polymorphic, parameters loose some type information, so the compiler cannot guarantee type safe and forbidden such usage.

Keep more type information

As mentioned above, in originally dynamic polymorphic (or call it sub-type polymorphic), it loose type information. If we can keep more type information, then dynamic polymorphic can be more powerful. For example, suppose we have a clone function T->T: In OOP sub type polymorphic, we convert T->T to obj->obj. In existential type polymorphic, we convert T->T to obj->obj, too. But except that, we keep the type information that obj and obj have same underlying type.

One existential type and one generic function

As mentioned above, we keep the type information that two unknown type are same. To type safe use such type information, we will use One existential type accept one generic function at once. With exact one:

1. we just keep the same type information between one existential package, we don't know whether type are same or not between different existential package.
2. existential package contains unknow type, so the function must be generic, which can support all type.
3. we have to return an concrete type, so the generic function must return a concrete type too. In fact, that's just the church encoding of existential type.

polymorphic generic function

We want the generic function support all type, not only in type system, but also in binary. Let we call such generic function as polymorphic generic function. In some program language, all generic function is polymorphic. But in some language like Rust/C++, their generic function is monomorphism. For such programming language, we have two choice:

1. convert monomorphism generic function to polymorphic generic function;
2. find the polymorphic generic function; 1 is easy to understand. Let carefully explain 2, Even though the programming only support monomorphism generic function, some of the generic function is naturally polymorphism. For example, in c++

template <typename T>
bool selfCompareT(
    T *obj,
    bool (*compare)(T *, T *)
) {
    return compare(obj, obj);
}

Such function is naturally polymorphism. No matter what really type T is, every type T has same binary implementation, we can use these generic function for existential type. In fact, it's zero-cost-abstraction, in static situation, the compiler can optimize it as monomorphism generic function; in dynamic situation, it has same binary implementation like dyn trait.

implement really existential type in different programming language

Swift

Swift is the only non-functional programming language that support existential type. The code will be like:

func speakGeneric<T: Speak>(_ animal: T) {
    animal.speak()
}

for animal in animals {
    speakGeneric(animal)
}

let comps : [any Comparable] = [1, 2.0, "hello"]

func selfCompare<T: Comparable>(_ a: T) -> Bool {
    return a < a
}

for c in comps {
    print(selfCompare(c))
}

protocol SortableCollection: MutableCollection, RandomAccessCollection where Element: Comparable {
}

extension Array: SortableCollection where Element: Comparable {}

func sortCollection<C: SortableCollection>(_ collection: C) {
    let sored_collection = collection.sorted()
    print(sored_collection)
}

var intergers: [Int] = [5, 2, 9, 1]
sortCollection(intergers)

var floats: [Double] = [3.0, 2.0, 1.0, 100.0]
sortCollection(floats)

var collections: [any SortableCollection] = [intergers, floats]
for index in collections.indices {
    let collection = collections[index]
    sortCollection(collection)
}

However, Swift doesn't really follow the rule that one existential package accept one generic function. It pass existential package as parameters for generic function. Even though Swift has done extra check to guarantee type safe, its implementation is still mess sometimes.

C

We can implement existential type in C like:

#include <stddef.h>
#include <stdbool.h>
#include <stdio.h>
#include <string.h>

// ==================== Implementation for int array ====================

typedef struct {
    int* data;
    size_t size;
} IntArray;

// Get size of int array
size_t int_array_get_size(const IntArray* arr) {
    return arr->size;
}

// Get pointer to int array element
int* int_array_get_elem(IntArray* arr, size_t index) {
    if (index < arr->size) {
        return &arr->data[index];
    }
    return NULL;
}

// Swap two int elements
void int_swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Compare two int elements (ascending)
bool int_compare_asc(const int* a, const int* b) {
    return *a > *b;
}

// Print int element
void int_print_element(const int* elem) {
    printf("%d", *elem);
}

// ==================== Implementation for double array ====================

typedef struct {
    double data[8]; // Fixed size array of 8
} DoubleArray;

// Get size of double array - always returns 8
size_t double_array_get_size(const DoubleArray* arr) {
    return 8;
}

// Get pointer to double array element
double* double_array_get_elem(DoubleArray* arr, size_t index) {
    if (index < 8) { // Always check index < 8
        return &arr->data[index];
    }
    return NULL;
}

// Swap two double elements
void double_swap(double* a, double* b) {
    double temp = *a;
    *a = *b;
    *b = temp;
}

// Compare two double elements (ascending)
bool double_compare_asc(const double* a, const double* b) {
    return *a > *b;
}

// Print double element
void double_print_element(const double* elem) {
    printf("%.2f", *elem);
}

// ==================== Sortable struct definition ====================

// Define generic Container and Element types
typedef struct Container Container;
typedef struct Element Element;
// Sortable struct macro definition - now includes print function pointer
#define DEFINE_SORTABLE(Container, Element) \
typedef struct { \
    Container* container; \
    size_t (*get_size)(const Container*); \
    Element* (*get_elem)(Container*, size_t); \
    void (*swap)(Element*, Element*); \
    bool (*compare)(const Element*, const Element*); \
    void (*print_element)(const Element*); \
} Sortable##Container##Element
DEFINE_SORTABLE(Container, Element);

// Sorting algorithm implementation
static void bubble_sort(SortableContainerElement* sortable) {
    size_t size = sortable->get_size(sortable->container);
    for (size_t i = 0; i < size; i++) {
        for (size_t j = 0; j < size - i - 1; j++) {
            Element* elem1 = sortable->get_elem(sortable->container, j);
            Element* elem2 = sortable->get_elem(sortable->container, j + 1);
            if (sortable->compare(elem1, elem2)) {
                sortable->swap(elem1, elem2);
            }
        }
    }
}

// Generic function to print array - uses print_element from Sortable struct
void print_array(SortableContainerElement* sortable) {
    size_t size = sortable->get_size(sortable->container);
    printf("Array (Size: %zu): [", size);
    
    for (size_t i = 0; i < size; i++) {
        Element* elem = sortable->get_elem(sortable->container, i);
        sortable->print_element(elem);
        
        if (i < size - 1) {
            printf(", ");
        }
    }
    printf("]\n");
}

// Additional formatted print function
void print_array_formatted(SortableContainerElement* sortable, const char* label) {
    printf("=== %s ===\n", label);
    print_array(sortable);
    printf("\n");
}

// Print all arrays in batch
void print_all_arrays(SortableContainerElement* sortables[], size_t count) {
    printf("=== All Arrays Status ===\n");
    for (size_t i = 0; i < count; i++) {
        printf("Array %zu: ", i + 1);
        print_array(sortables[i]);
    }
    printf("===================\n\n");
}

// Use macro to define two Sortable structs
DEFINE_SORTABLE(IntArray, int);
DEFINE_SORTABLE(DoubleArray, double);

int main() {
    // Create mixed-type Sortable pointer array
    SortableContainerElement* sortables[2];
    
    // Manually create int array
    int int_data[] = {5, 2, 8, 1, 9, 3};
    IntArray int_array = {int_data, 6};
    
    // Create and configure int Sortable struct (using pointer)
    SortableIntArrayint int_sortable;
    int_sortable.container = &int_array;
    int_sortable.get_size = int_array_get_size;
    int_sortable.get_elem = int_array_get_elem;
    int_sortable.swap = int_swap;
    int_sortable.compare = int_compare_asc;
    int_sortable.print_element = int_print_element;
    
    sortables[0] = (SortableContainerElement*)(&int_sortable);
    
    // Manually create double array
    DoubleArray double_array = {{3.14, 1.41, 2.71, 0.99, 4.56, 7.89, 6.28, 5.43}};
    
    // Create and configure double Sortable struct (using pointer)
    SortableDoubleArraydouble double_sortable;
    double_sortable.container = &double_array;
    double_sortable.get_size = double_array_get_size;
    double_sortable.get_elem = double_array_get_elem;
    double_sortable.swap = double_swap;
    double_sortable.compare = double_compare_asc;
    double_sortable.print_element = double_print_element;
    
    sortables[1] = (SortableContainerElement*)(&double_sortable);
    
    printf("=== Dynamic Polymorphism Demo: Mixed-Type Array Sorting ===\n\n");
    
    // Initial state
    printf("=== Before Sorting ===");
    print_all_arrays(sortables, 2);
    
    // Sort each array
    for (int i = 0; i < 2; i++) {
        bubble_sort(sortables[i]);
    }
    
    // Final state
    printf("=== After Sorting ===");
    print_all_arrays(sortables, 2);
    
    return 0;
}

We use incomplete type, which is always a pointer without any other type information. So the generic function most be polymorphic generic function. But there are still some problems:

1. we use get_elem function, which is virtual and slowly, the best choice in performance is provide Type size directly. However, it's not type safe, need to decide how to do it better. In my understanding, it's something like partially type erasure, the type erasure doesn't support all type, but support partially special types. So the function get_elem has common logic that only return by Tsize.
2. We can easily support generic function in C. But we don't have a good way to support generic structural, which introduce type constructor and too complex. At current, I would like support high order function that only happens in compile time, it compute function table to function table, which is enough to replace type constructor.

C#

C# support generic function in interface, so it can support existential type now, and for JIT, it can do more optimize that combine virtual functions in runtime directly, it should be even more faster that C/C++/Rust in these situation. However, C# interface doesn't support TSelf and associate type now, which is had to use.

using System;
using System.Runtime.CompilerServices;

// exists T where T : IComparable<T>. Array<T>
public interface IComparableArray
{
    void Accept(IArrayAlgorithm algorithm);
}

public interface IArrayAlgorithm
{
    void Invoke<T>(Span<T> values)
        where T : IComparable<T>;
}

public sealed class ArrayBox<T> : IComparableArray
    where T : IComparable<T>
{
    private readonly T[] _values;

    public ArrayBox(T[] values)
    {
        ArgumentNullException.ThrowIfNull(values);
        _values = values;
    }

    public void Accept(IArrayAlgorithm algorithm)
    {
        ArgumentNullException.ThrowIfNull(algorithm);

        algorithm.Invoke<T>(_values);
    }

    public ReadOnlySpan<T> Values => _values;
}

public sealed class InsertionSort : IArrayAlgorithm
{
    public void Invoke<T>(Span<T> values)
        where T : IComparable<T>
    {
        for (int i = 1; i < values.Length; i++)
        {
            T current = values[i];
            int j = i - 1;

            while (j >= 0 && Compare(values[j], current) > 0)
            {
                values[j + 1] = values[j];
                j--;
            }

            values[j + 1] = current;
        }
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private static int Compare<T>(T left, T right)
        where T : IComparable<T>
    {
        return left.CompareTo(right);
    }
}

public sealed class ReverseAlgorithm : IArrayAlgorithm
{
    public void Invoke<T>(Span<T> values)
        where T : IComparable<T>
    {
        int left = 0;
        int right = values.Length - 1;

        while (left < right)
        {
            (values[left], values[right]) =
                (values[right], values[left]);

            left++;
            right--;
        }
    }
}

public static class Program
{
    public static void Main()
    {
        var storage = new ArrayBox<int>(
            new[] { 5, 2, 9, 1, 3, 8, 4 });

        IComparableArray array = storage;

        Print("原始数组", storage.Values);

        IArrayAlgorithm sort = new InsertionSort();
        array.Accept(sort);

        Print("after sort", storage.Values);

        IArrayAlgorithm reverse = new ReverseAlgorithm();
        array.Accept(reverse);

        Print("after reverse", storage.Values);
    }

    private static void Print<T>(
        string title,
        ReadOnlySpan<T> values)
    {
        Console.Write(title);
        Console.Write(": ");

        for (int i = 0; i < values.Length; i++)
        {
            if (i != 0)
            {
                Console.Write(", ");
            }

            Console.Write(values[i]);
        }

        Console.WriteLine();
    }
}

4. if a function use [[any_type]], it should be [[always_inline]], then it's faster as template.

After that, we should provide some c libs by that.