💻 computer science

Dependent Multiplicities in Dependent Linear Type Theory

Dieser Artikel stellt eine neue abhängige lineare Typtheorie vor, die es ermöglicht, dass Variabilitätsmultiplizitäten von anderen Variablen abhängen, und dadurch präzise Ressourcenannotationen für verzweigende und rekursive Programme durch eine Einbettung der linearen Logik in die abhängige Typtheorie bereitstellt, unterstützt durch eine kategorische Semantik und eine Agda-Implementierung.

Ursprüngliche Autoren: Maximilian Doré

Veröffentlicht 2026-05-20

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Maximilian Doré

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Die große Idee: Ein „intelligenter" Ressourcenmanager

Stellen Sie sich vor, Sie schreiben ein Computerprogramm. In der Welt der Informatik sind einige Dinge wie Ressourcen (wie eine geöffnete Datei, eine entladene Batterie oder ein verwendeter geheimer Schlüssel). Sie möchten sicherstellen, dass Ihr Programm diese Ressourcen genau die richtige Anzahl an Malen verwendet: nicht zu oft (was sie verschwendet oder Fehler verursacht) und nicht zu selten (was Arbeit unvollendet lässt).

Seit langem nutzen Wissenschaftler ein System namens Lineare Logik, um diese Ressourcen zu verfolgen. Denken Sie daran wie an einen strengen Bibliothekar, der sagt: „Sie können dieses Buch genau einmal ausleihen. Wenn Sie versuchen, es zweimal auszuleihen, stoppt Sie das System."

Dieser strenge Bibliothekar hat jedoch ein Problem: Er ist zu starr. Er kann keine Situationen handhaben, in denen die Anzahl der benötigten Ressourcen von einer Entscheidung abhängt, die während der Programmausführung getroffen wird.

Das Problem mit den alten Regeln:
Stellen Sie sich vor, Sie haben eine Funktion, die basierend auf einem booleschen Schalter (Wahr/Falsch) entscheidet, ob Sie einen Kuchen backen oder einen Salat zubereiten.

Wenn der Schalter Wahr ist, benötigen Sie möglicherweise 3 Eier.
Wenn der Schalter Falsch ist, benötigen Sie möglicherweise 0 Eier.

Alte Systeme konnten nicht sagen: „Die Anzahl der Eier hängt vom Schalter ab." Sie zwangen Sie zu sagen: „Sie benötigen 3 Eier, egal was passiert," oder „Sie benötigen 0 Eier, egal was passiert." Dies ist ineffizient und oft unmöglich für komplexe Programme, die Schleifen oder verzweigte Logik beinhalten.

Die Lösung: „Abhängige Multiplizitäten"

Dieses Papier stellt ein neues System vor, bei dem die Anzahl der Verwendungen einer Ressource (die Multiplizität) von anderen Variablen im Programm abhängen kann.

Denken Sie daran wie an einen intelligenten Automaten statt an einen strengen Bibliothekar.

Altes System: Der Automat sagt: „Sie können genau 1 Soda kaufen." (Punkt).
Neues System: Der Automat sagt: „Sie können so viele Sodas kaufen, wie Dollar in Ihrem Portemonnaie sind." Wenn Sie 5 € einwerfen, erhalten Sie 5 Sodas. Wenn Sie 2 € einwerfen, erhalten Sie 2. Die Regel hängt vom von Ihnen bereitgestellten Wert ab.

In dieser neuen Theorie ist die „Multiplizität" (die Anzahl der Verwendungen einer Variable) keine in Stein gemeißelte feste Zahl. Es ist eine dynamische Berechnung, die während der Programmausführung stattfindet.

Wie es funktioniert: Die zwei Schichten

Der Autor, Maximilian Doré, baut dieses System, indem er zwei verschiedene Denkweisen über Logik kombiniert:

Die „Host"-Theorie (Das Gehirn): Dies ist die Standard-Logik, die in den meisten modernen Programmiersprachen verwendet wird und flexibel ist. Sie übernimmt den „Denk"-Teil: Entscheidungen treffen, Zahlen berechnen und Bedingungen prüfen.
Die „Lineare" Theorie (Das Portemonnaie): Dies ist die strenge Logik, die Ressourcen verfolgt.

Die Magie dieses Papiers liegt darin, wie sie diese beiden verbinden. Anstatt dass das „Portemonnaie" (Lineare Logik) eine separate, starre Box ist, ist es in das „Gehirn" (Host-Theorie) eingebettet.

Die Analogie: Stellen Sie sich vor, das „Gehirn" ist ein Koch und das „Portemonnaie" ist der Vorrat an Zutaten.
- In alten Systemen musste der Koch ein festes Rezept aufschreiben: „Verwenden Sie 2 Eier."
- In diesem neuen System kann der Koch sagen: „Verwenden Sie n Eier," wobei n eine Zahl ist, die der Koch während des Kochens berechnet, basierend darauf, wie hungrig die Kunden sind. Das Vorratssystem (Lineare Logik) aktualisiert sich in Echtzeit basierend auf der Berechnung des Kochs.

Wichtige Merkmale einfach erklärt

1. Dynamische Verzweigung (Das „Wenn/Anders"-Problem)
In dem Papier zeigt der Autor, wie man „Wenn/Anders"-Anweisungen perfekt handhabt.

Szenario: Sie haben einen booleschen Schalter.
Alter Weg: Sowohl der „Wenn"-Pfad als auch der „Anders"-Pfad mussten exakt die gleiche Menge an Ressourcen verwenden.
Neuer Weg: Der „Wenn"-Pfad kann 5 Ressourcen verwenden, und der „Anders"-Pfad kann 2 verwenden. Das System weiß genau, wie viele Ressourcen verwendet wurden, da es den Schalterwert bevor die Pfadentscheidung getroffen wird, betrachtet.

2. Rekursive Daten (Das „Baum"-Problem)
Das Papier behandelt komplexe Datenstrukturen wie Bäume (eine Liste von Listen oder ein Stammbaum).

Szenario: Sie möchten eine Funktion auf jedes Blatt eines Baums anwenden.
Alter Weg: Sie konnten nicht einfach sagen: „Verwenden Sie die Funktion genau so oft, wie es Blätter gibt," da das System nicht wusste, wie viele Blätter es gab, bis das Programm fertig ausgeführt war.
Neuer Weg: Das System berechnet zuerst die Anzahl der Blätter und setzt dann die Regel: „Verwenden Sie die Funktion BlattAnzahl Mal." Es funktioniert perfekt, selbst für Bäume jeder Größe.

3. Das „Reale" vs. die „Spezifikation"
Das Papier unterscheidet zwischen zwei Arten von Code:

Die Spezifikation (Der Bauplan): Dies ist der Teil, in dem Sie Zahlen berechnen und Entscheidungen treffen. Er ist flexibel.
Die Ausführung (Die Konstruktion): Dies ist der Teil, in dem Ressourcen tatsächlich verbraucht werden.
Das System erlaubt es Ihnen, den „Bauplan"-Teil zu löschen, nachdem Sie die Mathematik durchgeführt haben, und nur den effizienten „Konstruktions"-Teil übrig zu lassen. Das bedeutet, dass das endgültige Programm schnell ist und keinen unnötigen Berechnungsrucksack mit sich herumträgt.

Warum das wichtig ist

Der Autor hat dieses System in einer Programmiersprache namens Agda implementiert. Er bewies, dass:

Es mathematisch fundiert ist (es logisch funktioniert).
Es Programme typisieren kann, die frühere Systeme nicht handhaben konnten (wie komplexe Verzweigungen und rekursive Funktionen).
Es für jedes Programm eine präzise „Quittung" liefert, die genau zeigt, wie oft jede Ressource verwendet wurde, selbst wenn diese Zahl sich basierend auf der Programmlogik ändert.

Zusammenfassende Metapher

Stellen Sie sich vor, Sie leiten eine Baustelle.

Alte Systeme: Sie haben einen Polier, der sagt: „Wir brauchen genau 100 Ziegelsteine für diese Mauer," unabhängig davon, ob die Mauer groß oder klein ist. Wenn die Mauer klein ist, haben Sie Ziegelsteine übrig. Wenn sie groß ist, gehen sie aus.
Das System dieses Papiers: Sie haben einen intelligenten Polier, der die Baupläne betrachtet, die für diese spezifische Mauer benötigten Ziegelsteine zählt und genau diese Menge bestellt. Wenn sich die Mauergröße halbwegs ändert, passt der Polier die Bestellung sofort an.

Dieses Papier gibt Informatikern die Möglichkeit, diesen „intelligenten Polier" für Software zu bauen und sicherzustellen, dass Programme sowohl flexibel als auch perfekt effizient mit ihren Ressourcen sind.

Problemstellung
Bestehende quantitative Typtheorien, wie die Quantitative Type Theory (QTT) und die Graded Modal Type Theory, erlauben Ressourcenannotationen, bei denen Variablen Multiplizitäten besitzen, die angeben, wie oft sie verwendet werden. Diese Systeme verlassen sich jedoch typischerweise auf statische Multiplizitäten, die aus einer festen Ressourcenalgebra (z. B. natürlichen Zahlen oder Halbringen) stammen. Diese statische Natur schafft erhebliche Einschränkungen, wenn es um Programlogik geht, die Ressourcen nicht direkt repräsentiert, sondern organisiert, wie etwa Verzweigungen (Bedingungen) und Rekursion.

In aktuellen Systemen erfordert eine boolesche Bedingung, die zur Auswahl zwischen zwei Zweigen dient, dass beide Zweige identische Ressourcen verbrauchen, was oft unpraktisch ist, da verschiedene Zweige typischerweise unterschiedliche Operationen ausführen. Ebenso hängt bei höherstufigen Funktionen oder induktiven Typen (wie binären Bäumen) die Anzahl der Anwendungen einer Funktion oder des Verbrauchs einer Ressource oft von Werten ab, die erst zur Laufzeit bekannt sind (z. B. die Anzahl der Blätter in einem Baum). Frühere Versuche, abhängige Typtheorie (DTT) mit linearer Logik zu kombinieren, hatten Schwierigkeiten mit der Frage, ob Typen, die von Termen abhängen, eine „Verwendung" dieser Terme darstellen. Während McBride und Atkey argumentierten, dass Typen der Kontemplation und nicht der Berechnung dienen (was die Abhängigkeit von linearen Variablen erlaubt), schränkt ihre resultierende QTT die Multiplizitäten dennoch auf statische Elemente ein und erfasst nicht die dynamische Ressourcennutzung, die rekursiven Programmen und datenabhängigen Verzweigungen innewohnt.

Methodik
Der Artikel schlägt eine neuartige abhängige lineare Typtheorie vor, die die lineare Logik direkt in eine standardmäßige intuitionistische abhängige Typtheorie (die „Wirtstheorie") einbettet. Die Kerninnovation besteht darin, Multiplizitäten nicht als statische algebraische Elemente, sondern als Terme innerhalb der Wirtstheorie selbst zu behandeln.

Zwei Folgerungsrelationen: Das System unterscheidet zwischen zwei Urteilen:
- $\vdash$ : Die standardmäßige intuitionistische DTT (Wirtstheorie), die zur Definition von Typen, Termen und Abhängigkeiten verwendet wird.
- $\Vdash$ : Ein ressourcenbewusstes Kalkül, bei dem Terme aus „Versorgungen" (linearen Kontexten) abgeleitet werden.
Versorgungen als intuitionistische Typen: Im Gegensatz zu traditionellen linearen Kontexten sind Versorgungen in diesem System Terme der Wirtstheorie. Dies ermöglicht es der Wirtstheorie, mit Ressourcenannotationen zu rechnen. Konkret nutzt das System die natürlichen Zahlen der Wirtstheorie, um eine „Multiplikation" von Versorgungen ( $\Delta \hat{m}$ ) zu definieren, wobei $m$ ein Term vom Typ $\mathbb{N}$ ist. Diese Operation erlaubt es, eine Versorgung $m$ -fach zu duplizieren, wobei $m$ von anderen Variablen im Kontext abhängen kann.
Dynamische Multiplizitäten: Indem die Multiplizität $m$ als offener Term der Wirtstheorie zugelassen wird, unterstützt das System dynamische Ressourcenannotationen. Beispielsweise kann eine Funktion, die über einen Baum abbildet, spezifizieren, dass eine Funktion $f$ genau leafs(t)-mal verwendet wird, wobei leafs(t) aus der Struktur des Eingabebaums $t$ berechnet wird.
Typbildner: Der Artikel definiert lineare Versionen standardmäßiger DTT-Typbildner (Funktionen, Paare, Boolesche Werte und W-Typen), die mit diesen dynamischen Multiplizitäten annotiert sind. Entscheidend ist, dass die Eliminationsregeln für boolesche Werte und W-Typen es erlauben, Ressourcen basierend auf Laufzeitwerten unterschiedlich über Zweige oder Konstruktoren zu verteilen.
Semantik: Die Semantik wird als „Lineare Kategorien mit Familien" (lCwF) charakterisiert, die Kategorien mit Familien (CwF) sind, die in symmetrischen monoidalen Kategorien indiziert sind. Diese Struktur verallgemeinert Quantitative CwFs, die für QTT verwendet werden.

Hauptbeiträge

Syntax mit abhängigen Multiplizitäten: Der Artikel präsentiert eine Syntax, bei der Variablenmultiplizitäten Terme der Wirtstheorie sind, was eine präzise Typisierung von Programmen ermöglicht, die Verzweigungen und Rekursion beinhalten und die in linearen Systemen zuvor nicht typisierbar waren.
Lineare W-Typen: Eine prinzipielle Behandlung induktiver Typen (insbesondere W-Typen mit endlichen Positionen) in einem linearen Setting. Das System liefert Einführungs- und Eliminationsregeln, die den dynamischen Ressourcenverbrauch rekursiver Strukturen korrekt berücksichtigen.
Semantische Charakterisierung: Die Autoren definieren lCwFs als semantisches Modell für die Theorie und zeigen, wie sich Modelle der standardmäßigen DTT und Modelle der linearen Logik kombinieren. Sie demonstrieren, dass dieses Modell die komplexen Regeln für lineare W-Typen rechtfertigt und bestehende Modelle für QTT verallgemeinert.
Realisierbarkeit und Löschung: Ein Realisierbarkeitsmodell wird konstruiert (basierend auf BCI-Algebren), um zu zeigen, dass der intuitionistische Fragment ( $\vdash$ ) für die Berechnung gelöscht werden kann, wobei nur der lineare Fragment ( $\Vdash$ ) für die Ausführung übrig bleibt, ähnlich den 0- und 1-Fragmenten der QTT.
Implementierung: Die Theorie ist in Agda implementiert. Die Implementierung nutzt die semantische Interpretation (die lineare Urteile auf intuitionistische Terme abbildet, die mit Versorgungszeugen ausgestattet sind), um einen rigorosen, wenn auch noch nicht praktischen, Typchecker zu erstellen.

Ergebnisse

Ausdrucksstärke: Das System typisiert erfolgreich Programme, die eine dynamische Ressourcenanzählung erfordern, wie etwa eine map-Funktion für binäre Bäume, bei der die Verwendung der abbildenden Funktion proportional zur Anzahl der Blätter ist.
Vollständigkeit: Der Artikel beweist ein Vollständigkeitsresultat für „klar lineare Terme" (intuitionistische Terme, die Werte nicht durch spezifische Eliminatoren verwerfen oder duplizieren), indem er zeigt, dass sie im linearen System präzise typisiert werden können.
Wiederherstellung der intuitionistischen Logik: Durch die Einführung eines linearen exponentiellen Komonaden („!") kann das System die vollständige intuitionistische Logik innerhalb des linearen Fragments wiederherstellen, was eine uneingeschränkte Verwendung von Ressourcen dort erlaubt, wo dies notwendig ist.
Entscheidbarkeitskompromiss: Die Autoren räumen ein, dass die Typüberprüfung im allgemeinen Fall unentscheidbar ist, da sie den Vergleich offener Terme natürlicher Zahlen erfordert (z. B. die Prüfung, ob $\Delta \hat{m}$ gleich $\Delta \hat{n}$ ist). Sie stellen jedoch fest, dass die propositionale Gleichheit in der Wirtstheorie verwendet werden kann, um den Typchecker von der Ressourcenäquivalenz zu überzeugen.

Bedeutung
Der Artikel beansprucht, eine ausdrucksstärkere Version der Quantitative Type Theory bereitzustellen, indem er von statischen Ressourcenalgebren zu dynamischen, berechenbaren Multiplizitäten übergeht, die aus der Wirtstheorie abgeleitet werden. Indem die lineare Logik in die DTT eingebettet wird, anstatt sie als separate Logiken zu behandeln, vermeidet das System die einschränkende Dichotomie zwischen intuitionistischen und linearen Variablen, die in früheren Arbeiten zu finden war. Dies ermöglicht eine „prinzipielle ressourcenbewusste Behandlung" einer großen Klasse induktiver Typen und höherstufiger Funktionen. Die Arbeit zeigt, dass existierende abhängige typisierte Sprachen mit diesem System erweitert werden können, und bietet einen Weg zu einer präziseren Ressourcenverwaltung in der funktionalen Programmierung, ohne die Ausdrucksstärke abhängiger Typen aufzugeben. Die Autoren positionieren ihre Arbeit als eine Verallgemeinerung der QTT, die die Einschränkungen statischer Multiplizitäten bei der Handhabung von ressourcennutzung, die von der Laufzeit abhängt, auflöst.