Lyx – Generics & Traits

Generics und Traits sind das Typsystem-Fundament für wiederverwendbaren Code in Lyx. Generics erlauben es, Funktionen und Datenstrukturen einmal zu schreiben und für beliebig viele konkrete Typen zu verwenden. Traits definieren die Anforderungen, die ein Typ erfüllen muss, damit er als generischer Parameter zulässig ist.

Der entscheidende Unterschied zu Interfaces in Java oder Go: Lyx löst Generics durch Monomorphisierung auf — der Compiler erzeugt für jede verwendete Typ-Kombination eine vollständig eigenständige, optimierte Version der Funktion. Es entsteht kein Laufzeit-Overhead, keine V-Table, kein Dispatch. Das Ergebnis ist identisch mit handgeschriebenem spezialisierten Code — und WCET-berechenbar.

Der Typparameter wird in spitzen Klammern hinter dem Funktionsnamen deklariert und kann dann im Parametertyp und Rückgabetyp verwendet werden.

fn Identity<T>(value: T): T {
    return value;
}

fn Swap<T>(var a: T, var b: T): void {
    let temp: T := a;
    a := b;
    b := temp;
}

fn main(): int64 {
    var x: int64 := 10;
    var y: int64 := 20;
    Swap<int64>(x, y);
    // x = 20, y = 10

    var s: int64 := Identity<int64>(42);

    return 0;
}

Der Compiler leitet den Typparameter in vielen Fällen automatisch her — die explizite Angabe <int64> ist dann optional:

var result: int64 := Identity(42);    // T wird zu int64 inferiert
var pi: f64       := Identity(3.14);  // T wird zu f64 inferiert

Generische Funktionen können beliebig viele Typparameter haben:

fn Pair<A, B>(first: A, second: B): (A, B) {
    return (first, second);
}

fn MapApply<In, Out>(value: In, fn transform: fn(In): Out): Out {
    return transform(value);
}

fn main(): int64 {
    var p: (int64, f64) := Pair(1, 3.14);

    var doubled: int64 := MapApply<int64, int64>(21, fn(x: int64): int64 {
        return x * 2;
    });

    return 0;
}

Ein Trait ist eine benannte Menge von Methodensignaturen. Er beschreibt, was ein Typ kann, ohne festzulegen, wie er es tut. Ein Typ erfüllt einen Trait, indem er alle geforderten Methoden implementiert.

trait Printable {
    fn Print(): void;
    fn ToString(): int64;   // Rückgabe: Zeiger auf String
}

Ein Trait wird mit impl TraitName for TypeName für einen bestimmten Typ implementiert:

type Point = struct {
    x: f64;
    y: f64;
};

impl Printable for Point {
    fn Print(): void {
        PrintStr("Point(");
        PrintF64(self.x);
        PrintStr(", ");
        PrintF64(self.y);
        PrintStr(")");
    }

    fn ToString(): int64 {
        // Gibt einen formatierten String zurück
        return StrFormat("Point(%f, %f)", self.x, self.y);
    }
}

Und analog für einen anderen Typ — ohne den aufrufenden Code zu ändern:

type Color = struct {
    r: int64;
    g: int64;
    b: int64;
};

impl Printable for Color {
    fn Print(): void {
        PrintStr("rgb(");
        PrintInt(self.r); PrintStr(", ");
        PrintInt(self.g); PrintStr(", ");
        PrintInt(self.b); PrintStr(")");
    }

    fn ToString(): int64 {
        return StrFormat("rgb(%d,%d,%d)", self.r, self.g, self.b);
    }
}

Damit eine generische Funktion Methoden eines Typparameters aufrufen darf, muss der entsprechende Trait als Constraint angegeben werden. Ohne Constraint weiß der Compiler nicht, welche Operationen auf T zulässig sind.

// T muss Printable implementieren
fn PrintTwice<T: Printable>(value: T): void {
    value.Print();
    PrintStr("\n");
    value.Print();
    PrintStr("\n");
}

fn main(): int64 {
    var p: Point := Point { x: 3.0, y: 4.0 };
    var c: Color := Color { r: 255, g: 128, b: 0 };

    PrintTwice(p);   // OK: Point impl Printable
    PrintTwice(c);   // OK: Color impl Printable
    // PrintTwice(42);  // Compiler-Fehler: int64 impl nicht Printable

    return 0;
}

Ein Typparameter kann mehrere Traits gleichzeitig fordern — verknüpft mit + (ähnlich wie in Rust mit + oder Java & ):

trait Comparable {
    fn LessThan(other: self): bool;
    fn Equals(other: self): bool;
}

trait Serializable {
    fn Serialize(): int64;    // Zeiger auf Byte-Puffer
    fn SerializeLen(): int64; // Länge des Puffers
}

// T muss sowohl Comparable als auch Serializable sein
fn SortAndStore<T: Comparable + Serializable>(items: T[], n: int64): void {
    // Sortieren (Comparable erlaubt LessThan)
    // ... Sortier-Logik ...

    // Speichern (Serializable erlaubt Serialize)
    var i: int64 := 0;
    while (i < n) limit(65536) {
        var buf: int64 := items[i].Serialize();
        var len: int64 := items[i].SerializeLen();
        WriteToStorage(buf, len);
        i := i + 1;
    }
}

Traits können Methoden mit einer Default-Implementierung versehen. Typen, die den Trait implementieren, erben diese Implementierung automatisch — können sie aber überschreiben.

trait Describable {
    fn Name(): int64;    // Abstrakt — muss implementiert werden

    // Default-Implementierung — optional überschreibbar
    fn Describe(): void {
        PrintStr("Ich bin: ");
        PrintStr(self.Name());
        PrintStr("\n");
    }
}

type Sensor = struct {
    id: int64;
};

impl Describable for Sensor {
    fn Name(): int64 {
        return "Drucksensor";   // Pflicht-Implementierung
    }
    // Describe() wird von der Default-Implementierung geerbt
}

type Actuator = struct {
    id: int64;
};

impl Describable for Actuator {
    fn Name(): int64 {
        return "Steuerventil";
    }

    // Describe() wird überschrieben
    fn Describe(): void {
        PrintStr("[Aktor] ");
        PrintStr(self.Name());
        PrintStr(" (ID=");
        PrintInt(self.id);
        PrintStr(")\n");
    }
}

Nicht nur Funktionen, sondern auch Datenstrukturen können generisch sein.

type Optional<T> = struct {
    value:    T;
    has_value: bool;
};

fn OptionalOf<T>(v: T): Optional<T> {
    return Optional<T> { value: v, has_value: true };
}

fn OptionalEmpty<T>(): Optional<T> {
    return Optional<T> { has_value: false };
}

fn OptionalGet<T>(opt: Optional<T>): T {
    if (!opt.has_value) {
        panic("Optional ist leer");
    }
    return opt.value;
}

fn main(): int64 {
    var maybe_int:  Optional<int64> := OptionalOf(42);
    var maybe_none: Optional<f64>   := OptionalEmpty<f64>();

    if (maybe_int.has_value) {
        PrintInt(OptionalGet(maybe_int));
        PrintStr("\n");
    }

    return 0;
}

con STACK_MAX: int64 := 256;

type Stack<T> = struct {
    data: T[256];
    top:  int64;
};

fn StackNew<T>(): Stack<T> {
    return Stack<T> { top: 0 };
}

fn StackPush<T>(var s: Stack<T>, value: T): bool {
    if (s.top >= STACK_MAX) { return false; }
    s.data[s.top] := value;
    s.top := s.top + 1;
    return true;
}

fn StackPop<T>(var s: Stack<T>): T {
    if (s.top <= 0) { panic("Stack underflow"); }
    s.top := s.top - 1;
    return s.data[s.top];
}

fn StackIsEmpty<T>(s: Stack<T>): bool {
    return s.top == 0;
}

fn main(): int64 {
    var int_stack: Stack<int64> := StackNew<int64>();
    StackPush(int_stack, 10);
    StackPush(int_stack, 20);
    StackPush(int_stack, 30);

    while (!StackIsEmpty(int_stack)) limit(STACK_MAX) {
        PrintInt(StackPop(int_stack));
        PrintStr("\n");
    }
    // Ausgabe: 30, 20, 10

    return 0;
}

Ein zentrales Einsatzfeld für Traits in Lyx ist die Hardware-Abstraktion: Treiberschnittstellen werden als Trait definiert, der Applikationscode ist generisch dagegen geschrieben. Für jede Zielplattform gibt es eine eigene Implementierung — der Anwendungscode ändert sich nicht.

// ── Schnittstelle (für jede UART-Hardware gleich) ──────────────────────────

trait UART {
    fn Init(baudrate: int64): bool;
    fn SendByte(b: uint8): void;
    fn RecvByte(): uint8;
    fn IsReady(): bool;
}

// ── Implementierung für ESP32 ───────────────────────────────────────────────

type ESP32UART = struct {
    base_addr: int64;
};

impl UART for ESP32UART {
    fn Init(baudrate: int64): bool {
        // ESP32-spezifische Register setzen
        return true;
    }
    fn SendByte(b: uint8): void { /* UART0_FIFO schreiben */ }
    fn RecvByte(): uint8        { return 0u8; /* UART0_FIFO lesen */ }
    fn IsReady(): bool          { return true; }
}

// ── Implementierung für RISC-V ─────────────────────────────────────────────

type RiscVUART = struct {
    base_addr: int64;
};

impl UART for RiscVUART {
    fn Init(baudrate: int64): bool {
        // SiFive UART-Register konfigurieren
        return true;
    }
    fn SendByte(b: uint8): void { /* txdata schreiben */ }
    fn RecvByte(): uint8        { return 0u8; /* rxdata lesen */ }
    fn IsReady(): bool          { return true; }
}

// ── Applikationscode — hardware-unabhängig ─────────────────────────────────

fn SendString<U: UART>(var uart: U, msg: int64): void {
    var p: int64 := msg;
    while ((p as uint8) != 0u8) limit(65536) {
        uart.SendByte(p as uint8);
        p := p + 1;
    }
}

fn main(): int64 {
    var esp_uart: ESP32UART := ESP32UART { base_addr: 0x3FF40000 };
    esp_uart.Init(115200);
    SendString(esp_uart, "Hallo ESP32!\n");

    var rv_uart: RiscVUART := RiscVUART { base_addr: 0x10013000 };
    rv_uart.Init(9600);
    SendString(rv_uart, "Hallo RISC-V!\n");

    return 0;
}

Der Compiler monomorphisiert SendString zweimal — einmal für ESP32UART, einmal für RiscVUART. Der generierte Code ist identisch mit dem einer manuell spezialisierten Version.

Ein Trait kann einen anderen Trait als Voraussetzung deklarieren. Wer den abgeleiteten Trait implementiert, muss auch den Basis-Trait implementieren.

trait Readable {
    fn Read(buf: int64, len: int64): int64;
}

trait Writable {
    fn Write(buf: int64, len: int64): int64;
}

// ReadWrite setzt Readable und Writable voraus
trait ReadWrite : Readable + Writable {
    fn Flush(): void;
    fn Seek(offset: int64): void;
}

type FileHandle = struct {
    fd: int64;
};

impl Readable for FileHandle {
    fn Read(buf: int64, len: int64): int64 {
        return SysRead(self.fd, buf, len);
    }
}

impl Writable for FileHandle {
    fn Write(buf: int64, len: int64): int64 {
        return SysWrite(self.fd, buf, len);
    }
}

impl ReadWrite for FileHandle {
    fn Flush(): void { SysFsync(self.fd); }
    fn Seek(offset: int64): void { SysLseek(self.fd, offset, 0); }
}

// Diese Funktion akzeptiert jeden Typ mit vollem ReadWrite-Trait
fn CopyData<S: Readable, D: Writable>(src: S, dst: D, len: int64): void {
    var buf: uint8[4096];
    var remaining: int64 := len;
    while (remaining > 0) limit(65536) {
        var chunk: int64 := remaining > 4096 ? 4096 : remaining;
        var n: int64 := src.Read(buf as int64, chunk);
        dst.Write(buf as int64, n);
        remaining := remaining - n;
    }
}

Monomorphisierung ist die Strategie, durch die Lyx Generics auflöst. Der Compiler erzeugt für jede eindeutige Typ-Kombination eine eigene, spezialisierte Funktion — kein Dispatch, kein Overhead.

fn Max<T: Comparable>(a: T, b: T): T {
    if (a.LessThan(b)) { return b; }
    return a;
}

// Verwendung mit verschiedenen Typen:
var a: int64 := Max(3, 7);         // → Max_int64(3, 7)
var b: f64   := Max(1.5, 2.3);    // → Max_f64(1.5, 2.3)
var c: int64 := Max(10, 5);       // → Max_int64(10, 5) — selbe Instanz wie oben

Der Compiler erzeugt intern:

Binärgröße: Jede neue Typ-Kombination fügt eine Kopie hinzu. Bei eingebetteten Systemen mit wenig Flash-Speicher sollte die Anzahl der Typ-Instanzen bewusst gehalten werden. Der Compiler gibt mit –symbol-sizes eine Übersicht der Größe jeder monomorphisierten Funktion aus.

lyxc src/main.lyx --symbol-sizes | grep "Max_"
# Max_int64    28 bytes
# Max_f64      32 bytes

Lyx bevorzugt statischen Dispatch (Monomorphisierung) als Standard. Dynamischer Dispatch über eine V-Table ist ab v0.9.5 als explizite Option verfügbar — sinnvoll, wenn die Menge an Typ-Instanzen die Binärgröße dominiert.

// Statisch — Compiler kennt den Typ zur Compile-Zeit
fn DrawStatic<T: Drawable>(shape: T): void {
    shape.Draw();
}

// Dynamisch — Typ erst zur Laufzeit bekannt (dyn-Keyword)
fn DrawDynamic(shape: dyn Drawable): void {
    shape.Draw();
}

Im Safety-Umfeld (DAL-A, DAL-B) gilt: Immer statischen Dispatch verwenden. Dynamischer Dispatch erzeugt indirekte Sprünge, die in der WCET-Analyse nicht exakt gebunden werden können.

Generics und Traits funktionieren vollständig mit den Safety-Pragmas zusammen — Constraints werden vor der Monomorphisierung geprüft, die erzeugte Funktion ist gewöhnlicher nativer Code.

trait SensorReader {
    fn Read(): int64;
    fn IsValid(): bool;
}

@dal(B)
@flight_crit
@stack_limit(256)
@wcet(100)
fn ReadValidSensor<S: SensorReader>(var sensor: S): int64 {
    if (!sensor.IsValid()) {
        return -1;
    }
    return sensor.Read();
}

@wcet, @stack_limit und @flight_crit gelten für die erzeugte monomorphisierte Funktion — der Compiler prüft das Budget für jede Typ-Instanz separat. Wird der Stack-Limit für ReadValidSensor<PressureSensor> überschritten, entsteht ein Compiler-Fehler mit dem konkreten Typ im Fehlertext.

Best Practices im Safety-Umfeld:

Ein Ringpuffer (Circular Buffer) ist eine klassische Datenstruktur für Embedded-Systeme und Echtzeit-Kommunikation. Die generische Version funktioniert für beliebige Elementtypen.

unit RingBuffer;

con RING_CAPACITY: int64 := 64;

type RingBuffer<T> = struct {
    data:  T[64];
    head:  int64;   // Nächster Schreibindex
    tail:  int64;   // Nächster Leseindex
    count: int64;   // Aktuell enthaltene Elemente
};

fn RingNew<T>(): RingBuffer<T> {
    return RingBuffer<T> { head: 0, tail: 0, count: 0 };
}

fn RingIsEmpty<T>(r: RingBuffer<T>): bool {
    return r.count == 0;
}

fn RingIsFull<T>(r: RingBuffer<T>): bool {
    return r.count >= RING_CAPACITY;
}

fn RingPush<T>(var r: RingBuffer<T>, value: T): bool {
    if (RingIsFull(r)) { return false; }
    r.data[r.head] := value;
    r.head := (r.head + 1) % RING_CAPACITY;
    r.count := r.count + 1;
    return true;
}

fn RingPop<T>(var r: RingBuffer<T>): (T, bool) {
    if (RingIsEmpty(r)) { return (r.data[0], false); }
    var value: T := r.data[r.tail];
    r.tail := (r.tail + 1) % RING_CAPACITY;
    r.count := r.count - 1;
    return (value, true);
}

fn RingLen<T>(r: RingBuffer<T>): int64 {
    return r.count;
}

// ── Verwendung ────────────────────────────────────────────────────────────────

fn main(): int64 {
    // Ringpuffer für Sensor-Messwerte
    var sensor_buf: RingBuffer<f64> := RingNew<f64>();
    RingPush(sensor_buf, 101.3);
    RingPush(sensor_buf, 101.5);
    RingPush(sensor_buf, 100.9);

    while (!RingIsEmpty(sensor_buf)) limit(RING_CAPACITY) {
        var (val, ok): (f64, bool) := RingPop(sensor_buf);
        if (ok) {
            PrintF64(val);
            PrintStr(" hPa\n");
        }
    }

    // Derselbe Puffer-Code für Kommandos (int64)
    var cmd_buf: RingBuffer<int64> := RingNew<int64>();
    RingPush(cmd_buf, 0x01);
    RingPush(cmd_buf, 0x02);

    PrintStr("Kommandos im Puffer: ");
    PrintInt(RingLen(cmd_buf));
    PrintStr("\n");

    return 0;
}