We hebben Traits bij ons thuis

Er is aanzienlijk geschreven over Zig-interfaces, en terecht. Hoewel het geen officiële taalfunctie is, zijn interfaces de de-facto manier om runtime-polymorfisme in Zig te implementeren. Nog meer is er gezegd over de comptime van Zig, en hoe dit kan worden ingezet om de prestatieproblemen van dynamische dispatch te vermijden en slanke, data-georiënteerde code te schrijven.

Kort gezegd wordt polymorfisme in Zig conventioneel op een van de twee volgende manieren bereikt:

• Dynamische Interfaces: Gebruik van ondoorzichtige pointers (opaque pointers), virtuele tabellen (VTables) en dynamische dispatch om runtime-polymorfisme te bereiken.
• Comptime Duck Typing: Gebruik van type-reflectie, switch-statements en monomorfisme tijdens het compileren om statisch polymorfisme te bereiken.

Deze gang van zaken is tot nu toe zeer effectief gebleken, maar is niet zonder compromissen.

Interfaces bieden het soort type-contracten dat we kennen uit andere talen. Een functie die een interface accepteert, heeft een garantie over de methodesignaturen, maar niet over de implementatie. Omdat interfaces echter per ontwerp modulair zijn tijdens runtime, introduceren ze ook een harde barrière voor de compiler en dus een overhead in de prestaties. Er is genoeg indirectie waardoor de compiler vaak niet effectief de optimalisaties kan toepassen die hij wel bij monomorfe code zou doen.

Voor prestatiekritische code vertrouwt Zig-code doorgaans op comptime duck typing. Een functie-argument is ofwel anytype of wordt geparametriseerd door een type-argument T. De functie-implementatie voert vervolgens reflectie uit tijdens het compileren of maakt aannames over de methoden van het type die tijdens het compileren kunnen worden gecontroleerd. Implementaties kunnen vervolgens worden gemonomorfiseerd, vergelijkbaar met C++ templating of C-macro's. Dit is iets veiliger dan runtime duck typing, omdat eventuele schendingen van de interface tijdens het compileren worden opgemerkt in plaats van tijdens runtime. Toch moeten zowel de aanroeper als de aangeroepene zorgvuldig documenteren en volgen welk type er precies doorgegeven mag worden.

Als je uit een andere sterk getypeerde taal komt, is het begrijpelijk dat je deze regeling nogal simplistisch vindt. Dit is wellicht bewust; Zig streeft naar eenvoud. Echter, als je gewend bent aan de traits van Rust of de typeclasses van Haskell, lijkt er geen direct equivalent in Zig te zijn.

Ik wil betogen dat het, met een kleine aanpassing, perfect mogelijk is om soortgelijke abstracties over types in Zig-userland uit te drukken. Ik stel een nieuwe conventie voor om compile-time type-contracten te definiëren als Traits in Zig. Dit vereist geen bibliotheken of complexe mechanismen — sterker nog, het past uitstekend binnen standaard Zig. Het is geïnspireerd door de functionele programmeerwereld in het algemeen, en OCaml in het bijzonder.

Definitie: Een Trait is een compile-time struct die gerelateerde functies bevat over een bepaald type.

Om direct ter zake te komen, begin ik met een kort voorbeeld van hoe we een trait kunnen definiëren voor het vouwen (folding of reducing) van een type.

/// T vormt een Reducer onder een lege waarde en een combine-operatie
fn Reducer(T: type) type {
    return struct {
        empty: T,
        combine: fn (T, T) T,
        fn reduce(self: @This(), xs: []const T) T {
            var accum = self.empty;
            for (xs) |x| accum = self.combine(accum, x);
            return accum;
        }
    };
}

/// i32 vormt een sum reducer onder 0 en optelling
const sum_trait = impl(Reducer(i32), struct {
    pub const empty = 0;
    pub fn combine(x: T, y: T) T { return x + y; }
});

/// i32 vormt een product reducer onder 1 en vermenigvuldiging
const product_trait = impl(Reducer(i32), struct {
    pub const empty = 1;
    pub fn combine(x: T, y: T) T { return x * y; }
});

export fn run(buf: [*c]i32, n: usize) i32 {
    const sum = sum_trait.reduce(buf[0..n]);
    const product = product_trait.reduce(buf[0..n]);
    return sum + product;
}

Is dat niet fantastisch? Het contract is duidelijk, LSP-autocompletion pikt het op, en de compiler weet zelfs dat hij het moet inlinen en de loop moet unrollen.

Traits zijn simpelweg verzamelingen van functies en types die de ontvangende functie vertellen hoe subtaken moeten worden uitgevoerd waar de functie zelf niet verantwoordelijk voor is. Ze gedragen zich veel als vtables, behalve dat ze tijdens comptime worden geëvalueerd in plaats van tijdens runtime.

Conventioneel Polymorfisme vs. Traits

Om traits te rechtvaardigen, maken we een tour door Zig-polymorfisme met een veelvoorkomend voorbeeld: rekenkundige operaties. Ik heb in de loop der jaren enkele klachten gehoord over hoe ongemakkelijk het is om wiskunde in Zig te doen met door de gebruiker gedefinieerde types. In zijn streven naar expliciete control flow heeft Zig operator overloading weggelaten, wat jarring kan zijn als je uit andere getypeerde talen komt.

Stel dat we enkele door de gebruiker gedefinieerde types hebben zoals Rational en Complex, en we willen hun basisrekenoperaties definiëren. We zouden waarschijnlijk uitkomen op iets als het volgende:

const Rational = struct {
    numerator: i32,
    denominator: i32,
    fn add(lhs: Rational, rhs: Rational) Rational {...}
    fn sub(lhs: Rational, rhs: Rational) Rational {...}
    fn mul(lhs: Rational, rhs: Rational) Rational {...}
    fn div(lhs: Rational, rhs: Rational) Rational {...}
};

const Complex = struct {
    real: f32,
    imaginary: f32,
    fn add(lhs: Complex, rhs: Complex) Complex {...}
    fn sub(lhs: Complex, rhs: Complex) Complex {...}
    fn mul(lhs: Complex, rhs: Complex) Complex {...}
    fn div(lhs: Complex, rhs: Complex) Complex {...}
};

Laten we zeggen dat we de Möbius-transformatie willen berekenen: (a x + b) / (c x + d), wat nuttig is voor zowel complexe getallen als rationaal getallen. Om het simpel te houden, gaan we ervan uit dat alle argumenten voor de functie van hetzelfde type zijn.

Comptime Duck Typing

Als we de Möbius-transformatie naïef zouden implementeren, zouden we gewoon de ingebouwde operatoren kunnen gebruiken.

fn mobius(T: type, x: T, a: T, b: T, c: T, d: T) T {
    return (a * x + b) / (c * x + d);
}

Dit zou prima werken, zolang de inputs allemaal floats van hetzelfde type zijn. Delen zou breken voor integers, en natuurlijk zou het niet werken met onze eigen types.

We zouden kunnen merken dat beide door ons gedefinieerde types rekenfuncties hebben met overeenkomstige namen en gelijkaardige signaturen, wat zich leent voor duck typing.

fn mobius(T: type, x: T, a: T, b: T, c: T, d: T) T {
    const numerator = a.mul(x).add(b);
    const denominator = c.mul(x).add(d);
    return numerator.div(denominator);
}

Dit werkt voor onze eigen types, maar overduidelijk niet met de primitieve types van Zig. We zouden die in onze eigen types moeten wrappen. Wat problematischer is, is dat dit ons bindt aan een objectgeoriënteerd patroon: de de-facto manier om aan dit abstractiecontract te voldoen, is het definiëren van methoden op de struct.

Het goede nieuws is dat alles tijdens compile-time wordt gemonomorfiseerd, waardoor de compiler deze functieaanroepen kan vereenvoudigen en inlinen.

Interfaces & VTables

Als we wilden dat dit dynamisch tijdens runtime zou werken, zouden we een Num interface kunnen declareren die een VTable en een ondoorzichtige pointer gebruikt om deze rekenoperaties dynamisch te dispatcheren.

const Num = struct {
    value: [32]u8,
    vtable: *const VTable,
    const VTable = struct {
        add: *const fn([*]u8, [*]u8) Num,
        sub: *const fn([*]u8, [*]u8) Num,
        mul: *const fn([*]u8, [*]u8) Num,
        div: *const fn([*]u8, [*]u8) Num,
    };
    fn add(lhs: Num, rhs: Num) Num { ... }
    fn sub(lhs: Num, rhs: Num) Num { ... }
    fn mul(lhs: Num, rhs: Num) Num { ... }
    fn div(lhs: Num, rhs: Num) Num { ... }
    fn mobius(x: Num, a: Num, b: Num, c: Num, d: Num) {
        const numerator = a.mul(x).add(b);
        const denominator = c.mul(x).add(d);
        return numerator.div(denominator);
    }
}

We zouden dan Complex en Rational moeten koppelen om een functie zoals fn num(self: *Self) Num bloot te stellen die onze rekenfuncties wrapt. Dit is een tijdrovend proces om hier volledig te reproduceren, maar het zou werken. Je moet echter voorzichtig zijn: er is niets dat voorkomt dat je complexe en rationele getallen mengt in je functieaanroepen, wat zou leiden tot ongedefinieerd gedrag.

Niet alleen is dit lomper dan comptime duck typing, het is ook trager. We eisen effectief dynamische dispatch telkens wanneer we een rekenoperatie willen uitvoeren, wat de compiler hindert en een significante impact op de prestaties heeft bij veel berekeningen.

Traits

Wanneer we de mobius functie definiëren, willen we eigenlijk zeggen: "Ik weet niet met welk type ik te maken heb, maar het moet rekenkundige operaties hebben." In dit soort gevallen vind ik het meest zinvol om simpelweg de functies die nodig zijn tijdens compile-time mee te geven. Dit neemt alle ambiguïteit weg, ten koste van meer explicietheid.

fn mobius(
    comptime T: type,
    comptime add: fn (T, T) T,
    comptime mul: fn (T, T) T,
    comptime div: fn (T, T) T,
    x: T,
    a: T,
    b: T,
    c: T,
    d: T,
) T {
    const numerator = add(mul(a, x), b);
    const denominator = add(mul(c, x), d);
    return div(numerator, denominator);
}

Dit is effectief compile-time dependency injection op een zeer fijnmazig niveau. De signature is vrij uitgebreid, maar er is eigenlijk veel minder boilerplate te schrijven voor Complex of Rational vergeleken met runtime interfaces.

mobius(Complex, Complex.add, Complex.mul, Complex.div, x, a, b, c, d);
mobius(Real, Real.add, Real.mul, Real.div, x, a, b, c, d);

Vanuit hier is de stap naar traits klein. We ruimen de functie-signature simpelweg op door de rekenfuncties samen te brengen in één struct.

fn Num(T: type) type {
    return struct {
        add: fn (T, T) T,
        sub: fn (T, T) T,
        mul: fn (T, T) T,
        div: fn (T, T) T,
    };
}

fn mobius(T: type, num: Num(T), x: T, a: T, b: T, c: T, d: T) T {
    const numerator = num.add(num.mul(a, x), b);
    const denominator = num.add(num.mul(c, x), d);
    return num.div(numerator, denominator);
}

Meestal declareer ik de trait-implementatie vervolgens als onderdeel van mijn type.

const Complex = struct {
    // velden...
    const num = Num(Complex) { .add = add, .sub = sub, .mul = mul, .div = div };
    // functies (add, sub, mul, div...)
};

mobius(Complex, Complex.num, x, a, b, c, d);

Wat ik echt waardeer aan deze aanpak is de flexibiliteit, terwijl het contract tussen de functie en het type zeer duidelijk blijft. Stel bijvoorbeeld dat we onze definitie van Num willen uitbreiden naar primitieve types zoals i32 en f32.

fn builtinNum(T: type) Num(T) {
    const inner = struct {
        fn add(lhs: T, rhs: T) T { return lhs + rhs; }
        fn sub(lhs: T, rhs: T) T { return lhs - rhs; }
        fn mul(lhs: T, rhs: T) T { return lhs * rhs; }
    };
    const div = switch (@typeInfo(T)) {
        .int, .comptime_int => struct {
            fn div(lhs: T, rhs: T) T { return @divTrunc(lhs, rhs); }
        }.div,
        .float, .comptime_float => struct {
            fn div(lhs: T, rhs: T) T { return lhs / rhs; }
        }.div,
        else => @compileError("unsupported type: " ++ @typeName(T)),
    };
    return .{ .add = inner.add, .sub = inner.sub, .mul = inner.mul, .div = div };
}

mobius(f32, builtinNum(f32), x, a, b, c, d);

Traits zijn bovendien transparant voor de compiler, die deze functies met plezier zal monomorfiseren en inlinen. Ik geef dit de voorkeur boven runtime polymorfisme, vooral in "hot loops" of voor bibliotheekfuncties die geen mening hebben over de data-layout.

Beperkingen

Je zult merken dat traits expliciet geconditioneerd moeten worden op een bekend type. In tegenstelling tot interfaces is er geen manier om te zeggen "geef me een getal, het maakt me niet uit welk soort". Voor sommige toepassingen zou het fijn zijn als we een geassocieerd type zouden hebben.

fn Iter(Elem: type) type {
    return struct {
        T: type,
        next: fn (T) ?Elem,
    };
}

Helaas is het bovenstaande geen geldige Zig, en het is onduidelijk hoe dat op taalniveau zou werken. In plaats daarvan eisen traits dat de types waarop ze opereren vooraf bekend zijn.

fn Iter(T: type, Elem: type) type {
    return struct {
        next: fn (T) ?Elem,
    };
}

Ik heb nog geen ergonomische manier gevonden om dit te omzeilen. Traits werken niet erg goed samen met type-erasure.

Trait-hulpfuncties

Voordat we verder gaan, wil ik enkele kleine hulpfuncties introduceren die mijn werk met traits hebben gestroomlijnd.

impl

Als je traits als programmeerpatroon adopteert, zul je snel functies definiëren en deze doorgeven. Je hebt waarschijnlijk al gemerkt dat ik veel tijdelijke inner-structs definieer, puur om functies eruit te kunnen trekken. Dit heeft geleid tot de volgende gemakz 함수 voor het declareren van trait-implementaties, wat wat boilerplate verwijdert.

pub fn impl(comptime Trait: type, comptime Impl: type) Trait {
    comptime {
        var result: Trait = undefined;
        for (@typeInfo(Trait).@"struct".field_names) |field_name| {
            @field(result, field_name) = @field(Impl, field_name);
        }
        return result;
    }
}

Ik gebruik dit overal om trait-implementaties af te leiden van anonieme structs. Zo kunnen we builtinNum beknopter maken (let op: declaraties moeten publiek zijn voor type-reflectie).

fn builtinNum(T: type) Num(T) {
    return impl(Num(T), struct {
        pub fn add(lhs: T, rhs: T) T { return lhs + rhs; }
        pub fn sub(lhs: T, rhs: T) T { return lhs - rhs; }
        pub fn mul(lhs: T, rhs: T) T { return lhs * rhs; }
        pub const div = switch (@typeInfo(T)) {
            .int, .comptime_int => struct {
                fn div(lhs: T, rhs: T) T { return @divTrunc(lhs, rhs); }
            }.div,
            .float, .comptime_float => struct {
                fn div(lhs: T, rhs: T) T { return lhs / rhs; }
            }.div,
            else => @compileError("unsupported type: " ++ @typeName(T)),
        };
    });
}

getTrait

De meeste tijd vind ik het niet erg om trait-implementaties expliciet door te geven. Echter, wanneer ik met mijn eigen structs werk, is de trait-implementatie in 99% van de gevallen gedeclareerd als een const op de struct zelf. Ik gebruik de volgende functie om deze eenvoudig op te halen of te construeren.

fn getTrait(Trait: type, Impl: type) Trait {
    comptime {
        // probeer de trait expliciet als lid te vinden
        for (@typeInfo(Impl).@"struct".decl_names) |decl_name| {
            if (@TypeOf(@field(Impl, decl_name)) == Trait) {
                return @field(Impl, decl_name);
            }
        }
        // gooi anders een foutmelding
        @compileError("trait " ++ @typeName(Trait) ++ " not found on " ++ @typeName(Impl));
    }
}

Dit is in feite hetzelfde als zeggen: "het is duck typed, zoek het maar uit". Zelfs als we expliciet zijn, betekent dat niet dat we niet lui kunnen zijn. Als we terug willen naar duck typing, kunnen we zelfs trait-functoren definiëren die vertrouwen op getTrait.

fn duckMobius(T: type) fn(T, T, T, T) T {
    comptime {
        const num = getTrait(Num(T), T);
        return makeMobius(T, num);
    }
}

Trait-functoren

Nu we hulpfuncties hebben, keren we terug naar het Num voorbeeld.

Traits in Zig lijken op traits in Rust, typeclasses in Haskell, of modules in OCaml. In Rust of Haskell worden ze opgelost via een globaal register dat door de compiler wordt beheerd. Dit kan handig voelen, maar het schendt Zig's principe van expliciete control flow. Bovendien kan het zoeken naar waar een trait gedefinieerd is tijdrovend zijn, vooral als de LSP het niet correct oplost.

OCaml-modules werken echter veel meer als Zig-traits: modules zijn first-class objecten en worden als argumenten doorgegeven aan de functies die ze consumeren. Er is geen inferentie van welke modules op een type van toepassing zijn — je zoekt ze op en geeft ze expliciet door.

Omdat modules in OCaml first-class waarden zijn, kunnen ze nog een stap verder gaan met "module functors": functies die modules als argumenten nemen en nieuwe modules teruggeven. Dit vertaalt zich direct naar Zig.

fn Mobius(T: type) type {
    return struct {
        mobius: fn(T, T, T, T, T) T,
    };
}

fn makeMobius(T: type, num: Num(T)) Mobius(T) {
    return impl(Mobius(T), struct {
        fn mobius(x: T, a: T, b: T, c: T, d: T) T {
            const numerator = num.add(num.mul(a, x), b);
            const denominator = num.add(num.mul(c, x), d);
            return num.div(numerator, denominator);
        }
    });
}

const complex_mobius = MakeMobius(Complex, Complex.num);
complex_mobius.mobius(x, a, b, c, d);

Ik vind het echter nog eenvoudiger om de functor direct in Mobius(T) te plaatsen:

fn Mobius(T: type) type {
    return struct {
        mobius: fn(T, T, T, T, T) T,
        fn make(num: Num(T)) Mobius(T) {
            return impl(Mobius(T), struct {
                fn mobius(x: T, a: T, b: T, c: T, d: T) T {
                    const numerator = num.add(num.mul(a, x), b);
                    const denominator = num.add(num.mul(c, x), d);
                    return num.div(numerator, denominator);
                }
            });
        }
    };
}

const complex_mobius = Mobius(Complex).make(Complex.num);
complex_mobius.mobius(x, a, b, c, d);

Voor enkele functies zou ik echter geneigd zijn om het gewoon als een type-curried functie te implementeren in plaats van een volledige trait:

fn makeMobius(T: type, num: Num(T)) fn(T, T, T, T) T {
    return struct {
        fn mobius(x: T, a: T, b: T, c: T, d: T) T {
            const numerator = num.add(num.mul(a, x), b);
            const denominator = num.add(num.mul(c, x), d);
            return num.div(numerator, denominator);
        }
    }.mobius;
}

const complexMobius = makeMobius(Complex, Complex.num);
complexMobius(x, a, b, c, d);

De veelzijdigheid van Zig's comptime maakt al deze benaderingen min of meer gelijk voor de compiler. Het is een stilistische keuze.

Nuttige Traits

Hier zijn een paar traits die ik zo regelmatig gebruik dat ik een bestand met deze definities bewaar. Dit zijn eenvoudige maar breed toepasbare abstracties die ik heb overgenomen uit andere talen.

Into / From

Ik moet constant types converteren. Vaak zijn er meerdere manieren om dit te doen, afhankelijk van hoe je het brontype wilt interpreteren. Ik gebruik Into en From om methoden voor conversie te canonicaliseren.

/// T kan worden geconverteerd naar Out
fn Into(T: type, Out: type) type {
    return struct {
        into: fn(T) Out,
    };
}

/// T kan worden afgeleid van In
fn From(T: type, In: type) type {
    return struct {
        from: fn(In) T,
    };
}

Index

Soms hebben we toegang tot een waarde via een sleutel nodig in plaats van via iteratie. De container kan een slice of een hashtabel zijn. Hiervoor gebruik ik Index.

/// T vormt een index over Key en Value
fn Index(T: type, Key: type, Value: type) type {
    return struct {
        get: fn(T, Key) ?Value,
    };
}

Iterator / Iterable

Een ander veelvoorkomend geval: we hebben een functie die over een type itereert, maar we geven niet om het soort iterable datastructuur. We hebben dan meestal twee traits nodig: één voor de Iterable collectie, en een andere voor de Iterator die de voortgang bijhoudt.

/// T kan worden gebruikt om over Elem-elementen te itereren
fn Iterator(T: type, Elem: type) type {
    return struct {
        next: fn(*T) ?Elem,
    };
}

/// T kan een Iter-iterator teruggeven over Elem-elementen
fn Iterable(T: Type, Elem: type, Iter: type) type {
    return struct {
        iter: fn(T) IterPair,
        pub const IterPair = struct {impl: Iter, trait: Iterator(Iter, Elem)};
    };
}

Dit is een beetje ongemakkelijk, omdat we meestal niet geven om de implementatie van de iterator. Ik heb ervoor gekozen om het zo te laten; het is meestal geen groot probleem.

Waarschuwingen

Ik wil niet dat je na dit artikel denkt: "Ik moet al mijn code omzetten naar traits". Traits moeten niet worden gezien als een allesomvattend patroon. Het laatste wat ik wil is dat Zig-code gaat lijken op Rust of Haskell.

Traits zijn een "soms-lekkers". Ze zijn nuttig voor functies die abstracties nodig hebben binnen hot loops, waar je weet dat je monomorfisme en statische dispatch wilt. Ze kunnen leesbare bouwstenen worden voor slimme metaprogrammering-trucs. Echter, meestal grijp ik er alleen naar op basis van behoefte: ik heb een functie waar het nuttig is om een trait te consumeren, omdat een implementatie-detail nog onbeslist is.

Onjuist gebruikt kunnen traits de grootte van je binary doen exploderen en hem zelfs trager maken. Elke functie die geparametriseerd is op comptime-parameters krijgt zijn eigen ge-templated assembly. Als je deze een paar lagen diep nest, is het makkelijk om in een combinatorische explosie terecht te komen. Dit kan je CPU-cache belasten en, afhankelijk van de situatie, worden overtroffen door dynamische dispatch en vtables.

Aanmoedigingen

Traits zijn uiteindelijk handig en zeer krachtig. Ik zou graag meer codebases zien die ze gebruiken, vooral voor abstractie binnen hot loops. Ik hou ervan dat ze meer een designpatroon zijn dan een taalfunctie, wat je veel expliciete controle geeft over wanneer en hoe je ze gebruikt. Ik zocht lange tijd naar een oplossing als deze, en ik ben blij dat ik hem heb gevonden.

Ik ben er zeker van dat andere Zig-gebruikers op deze truc zijn gestuit, maar ik heb het nog niet "in het wild" gezien. Ik denk dat een deel van de reden is dat het zich niet goed leent voor een bibliotheek. Het is meer een conventie die je kunt kiezen om te gebruiken of te negeren.

Mijn hoop is dat traits voor de lezer het juiste instrument voor de klus zijn.

***

Voetnoten:

1. Zig 0.17 ten tijde van schrijven.
2. Zig Interfaces door Karl Seguin.
3. Figuurlijk.
4. Zig Interface Revisited door William Wong.
5. Inside Zig's new Writer door Joe McKay.
6. Interfaces in Zig door Brad Cypert.
7. A Practical Guide to Applying Data-Oriented Design door Andrew Kelley.
8. Zig Comptime is Bonkers Good door Scott Redit.
9. "Traits" zijn direct geïnspireerd door OCaml-modules, maar de term "module" verwijst al naar iets anders in Zig.
10. (Geen tekst beschikbaar).
11. Dit is een vrij simplistische definitie van een numerieke trait. In de praktijk zou je kunnen kijken naar std::ops uit Rust of Num uit Haskell.