Improvements für nebenläufige call-by-need funktionale Programmiersprachen.
Sicherheit und Verlässlichkeit, Betriebs-, Kommunikations- und verteilte Systeme
Theoretische Informatik
Zusammenfassung der Projektergebnisse
In diesem DFG-Projekt werden verschiedene Analysen des Speicherverbrauchs und des Laufzeitverhaltens in Kernsprachen von Haskell bzw. Concurrent Haskell durchgeführt. In bisherigen Arbeiten wurden die folgenden Ergebnisse erzielt: • Theoretische Grundlagen: Platzmessung, verschiedene Programmeigenschaften zur Beschreibung des Speicher- und Laufzeitverhaltens einer Transformation und Context Lemmas als wichtige Hilfswerkzeuge bei Nachweisen eben besagter Eigenschaften. Diese Grundlagen werden zum Nachweis zahlreicher Eigenschaften von Programmtransformationen genutzt. • Total Garbage Collection als nicht implementierbarer, aber fast optimaler Garbage Collector, wird eingeführt, um die erzielten Nachweis-Ergebnisse bezüglich Programmtransformationen möglichst unabhängig vom gewählten Garbage Collector zu halten. • CHF∗ wird um die zusätzliche parallele Auswertungsstrategie erweitert sowie Improvement-Definitionen für sequentielle und parallele Auswertungsreihenfolgen gegeben. Sowohl für sequentielle als auch parallele Auswertungsreihenfolge werden zahlreiche Time Improvements gezeigt. • Ein effizienter Algorithmus wird entwickelt, welcher den benötigten Speicherplatz bezüglich Scheduling von N Prozessen, die am Anfang und Ende synchron sind, berechnet. Die Hinzunahme von Synchronisierungs-Beschränkungen wird bezüglich Komplexität analysiert [SSD19a]. Die verschiedenen verwendeten Maße für Speicherverbrauch und Laufzeit ermöglichen zahlreiche erfolgreiche Speicher- und Laufzeitanalysen. Ein Ziel zukünftiger Arbeiten ist die Automatisierung dieser Analysen.
Projektbezogene Publikationen (Auswahl)
-
Space improvements and equivalences in a functional core language. In Horatiu Cirstea and David Sabel, editors, Proceedings Fourth International Workshop on Rewriting Techniques for Program Transformations and Evaluation, Oxford, UK, 8th September 2017, volume 265 of Electronic Proceedings in Theoretical Computer Science, pages 98–112. Open Publishing Association, 2018
Schmidt-Schauss, M., Dallmeyer, N.
-
Sequential and parallel improvements in a concurrent functional programming language. In Proceedings of the 20th International Symposium on Principles and Practice of Declarative Programming, PPDP ’18, pages 20:1–20:13, New York, NY, USA, 2018. ACM
Schmidt-Schauss, M., Sabel, D., Dallmeyer, N.
-
Optimizing space of parallel processes. In Joachim Niehren and David Sabel, editors, Proceedings Fifth International Workshop on Rewriting Techniques for Program Transformations and Evaluation, Oxford, UK, 8th July 2018, volume 289 of Electronic Proceedings in Theoretical Computer Science, pages 68–87. Open Publishing Association, 2019
Schmidt-Schauss, S., Dallmeyer, N.
