Lyx – Rekursion

Lyx unterstützt rekursive Funktionsaufrufe unter Einhaltung der plattformspezifischen ABIs. Da Lyx auf deterministische Laufzeiten optimiert ist, bietet der Compiler spezielle Werkzeuge zur Überwachung des Stack-Verbrauchs.

1) Grundlagen & Safety-Constraints

Rekursion folgt dem Muster aus Abbruchbedingung und Rekursionsschritt.

Zertifizierungs-Hinweis (DAL A/B):
In hochkritischen Systemen ist Rekursion nur zulässig, wenn eine maximale Rekursionstiefe nachgewiesen werden kann. Lyx unterstützt dies durch das Attribut @stack_limit.

@stack_limit(2048) // Der Compiler prüft, ob die Rekursion den Stack sprengt
fn Factorial(n: int64): int64 {
    if (n <= 1) { return 1; }
    return n * Factorial(n - 1);
}

2) Technische Implementierung & Calling Convention

Beim rekursiven Aufruf muss der Compiler den Zustand der Register sichern. Hier treten oft die „Unresolved Jump Patches“ auf, wenn der Emitter die Zieladresse des Eigenaufrufs noch nicht final im Speicher fixiert hat.

Architektur	Rücksprung-Mechanismus	Besonderheit
x86_64	Stack (`push rip`)	Nutzt Call-Stack Frame Pointer (RBP).
ARM64	Link Register (X30)	Adresse wird in X30 geladen; bei Rekursion muss X30 auf den Stack gerettet werden!
RISC-V	Return Address (ra)	Ähnlich wie ARM; erfordert explizites Sichern des `ra`-Registers im Prolog.

3) Tail-Call Optimization (TCO)

Um den Stack-Verbrauch bei tiefen Rekursionen (z. B. in Scannern oder Parsern) auf $O(1)$ zu reduzieren, wandelt Lyx Endrekursionen in einfache Sprünge (jmp) um.

// Dank TCO wird hier kein neuer Stack-Frame erzeugt
fn CountDown(n: int64) {
    if (n <= 0) { return; }
    PrintInt(n);
    CountDown(n - 1); // Der Compiler ersetzt 'call' durch 'jmp'
}

Wichtig für Compiler-Entwickler: Wenn TCO aktiv ist, müssen die „Jump Patches“ im Backend besonders sorgfältig gesetzt werden, da der Rücksprung-Pfad des ursprünglichen Aufrufers erhalten bleibt.

4) Rekursion in Datenstrukturen (OOP)

Rekursion ist das Standardwerkzeug für das Traversieren von Bäumen (z. B. dem Abstract Syntax Tree im Lyx-Compiler).

type Node = class {
    Value: int64;
    Next: Node?; 
 
    fn PrintAll() {
        PrintInt(self.Value);
        // Sicherer Aufruf über den Safe-Navigation Operator
        self.Next?.PrintAll();
    }
};

5) Debugging & Stack-Integrität

Wenn ein bootstrap-kompilierter Compiler bei Rekursionen abstürzt, liegt das oft an:

Falschem Prolog/Epilog: Das Link-Register (ARM/RISC-V) wird vor dem rekursiven Call nicht gesichert.
Stack Alignment: Die ABI verlangt oft ein 16-Byte Alignment. Ein rekursiver Call bei ungeradem Stack führt zu Abstürzen in SIMD-Instruktionen oder beim `open()` Syscall.
Missing Patches: Der Emitter markiert den rekursiven Sprung als „extern“, obwohl er die Adresse innerhalb der eigenen Unit finden müsste.