Gibt es (statische) Systeme, die versuchen, die Leistungsmerkmale von Programmen zu formalisieren? Ich kann solche Versuche anscheinend nicht finden.
Da Typsysteme (eines der) mächtigsten Werkzeuge im Arsenal des Programmierers sind, um Aussagen über Programme zu treffen, und da es viele Fälle gibt, in denen die Leistung kritisch ist, scheint es nicht weit hergeholt zu sein, sich vorzustellen, dass Versuche unternommen wurden Erstellen Sie ein Typsystem, das versucht, zumindest einige Aussagen über die Speicher- und Laufzeitmerkmale von Programmen zu treffen.
language-design
Klaas van Schelven
quelle
quelle
if condition then expensive_operation else cheap_operation?if (likely(operation_went_fine)) { // Do something } else if (unlikely(error_occured)) { // Do something else }Antworten:
Sie können sich ein Typsystem vorstellen, das so ausgefeilt ist, dass es mit WCET oder der Komplexität des Programms zusammenhängt. Dann geht es darum, einen Sound Type Analyzer (oder Checker) - dh Typisierungsregeln - zu erstellen, um dies zu ermöglichen, und ihn effizient genug zu implementieren, um dies einigermaßen nützlich zu machen.
Die meisten Typsysteme sind einfach genug, um in der Praxis schnell berechnet zu werden (zumindest für die vernünftigen Programme, die ein menschlicher Entwickler manuell schreiben könnte).
Einige akademische Programmiersprachen (z. B. AGDA ) verfügen über sehr ausgefeilte Typsysteme, die Turing-vollständig sind, so dass ihr Compiler eine große (möglicherweise unendliche) Zeit in Anspruch nehmen kann.
(Wenn ich das gut verstehe, hängt Jérémie Salvuccis Doktorarbeit am LIP6 in Paris mit Ihrer Frage zusammen. Ich habe ihm eine E-Mail darüber gesendet. Vielleicht suchen Sie nach Regionen und Typen ...).
Seien Sie sich jedoch des Satzes von Rice und des Halteproblems bewusst . Typsysteme sind möglicherweise nicht immer die Silberkugel, die Sie möchten (siehe das alte Buch ohne Silberkugel ).
quelle
Es scheint hervorragend möglich zu sein, ein Typensystem zu erstellen, das die Leistungsmerkmale von Typen kategorisiert(z. B. "schnell / langsam für den seriellen Zugriff", "schnell / langsam für den wahlfreien Zugriff", "speichereffizient / ineffizient"). Diese Merkmale können abstrakte Typen sein, die so in die Hierarchie eingefügt werden, dass die konkreteren Typen von ihnen geerbt werden. Die Leistung eines Programms, das diese Typen verwendet, hängt jedoch von der Art und Weise ab, in der sie tatsächlich verwendet werden / auf die zugegriffen wird. Damit das Typsystem Aussagen über das Programm selbst treffen kann, muss die Verwendung (der Zugriff auf) diese Typen selbst als Typen dargestellt werden Dies würde bedeuten, auf die Verwendung integrierter Steuerungsstrukturen (z. B. for / while-Schleifen) zu verzichten und stattdessen Typen zu verwenden, die diese implementieren. Daher könnte die Hierarchie einen abstrakten Typ für seriellen Zugriff und einen Nachkommen-Listen-Seriell-Zugriff, Baum-Seriell, haben -Zugriffstypen und so weiter.Die Effizienz der Nutzung könnte dann zumindest teilweise durch die Kombination und Anwendung dieser Typen untereinander ausgedrückt werden.
In einer funktionalen Sprache wie Haskell - die sowieso fast keine Kontrollstrukturen hat - erscheint mir dies ziemlich praktisch und durchsetzbar. In Java, jedoch scheint ein solches System viel weniger erreichbar (nicht so viel von der Umsetzung von der Durchsetzbarkeit / Vertrauenswürdigkeit des Ergebnisses).
Mit Haskell können wir bereits definitiv angeben, wie viel von einem Programm rein ist, und es gibt Möglichkeiten, bestimmte Aktivitäten in versiegelten Kartons einzuschränken. Da Parallelität / Parallelität in Haskell über das Typsystem implementiert wird , könnte argumentiert werden, dass es bereits Teil des Weges dorthin ist (zu dem, was Sie wollen). Im Gegensatz dazu bieten imperative Sprachen (auch statisch typisierte wie Java) dem Codierer viele, viele Möglichkeiten, jeden Versuch zu untergraben.
quelle