Was sind die theoretischen Grenzen der Stratego-Programmiersprache?

10

Stratego ist eine Programmiertransformationssprache / Rewriting DSL.

Anthony Sloane hat einige Arbeiten an einer Implementierung durchgeführt, die auf Scala ausgeführt wird .

Was sind die theoretischen Grenzen von Stratego als funktionale Sprache? (unabhängig von der Implementierung). Könnte man in Stratego einen Ycombinator für die Anwendungsbestellung schreiben?

Falkenauge
quelle
Eine sehr interessante Frage.
Dave Clarke
Wollten Sie wirklich auf zwei triviale Varianten desselben Papiers verweisen?
Randall Schulz
Eine Verfeinerung dieser Frage: Welche Vor- und Nachteile hat die Erweiterung einer Programmiersprache auf diese Weise im Gegensatz zur Makrotechnik?
Charles Stewart

Antworten:

6

Ich werde die Antwort ausprobieren, obwohl ich kein konkretes Programm habe, das Sie ausprobieren können. In einem Blogeintrag von Eelco Visser sehen Sie einen Screenshot, der im Wesentlichen den in Stratego codierten Lambda-Kalkül enthält (ich bin sicher, dass dieser Code an anderer Stelle verfügbar ist). Er präsentiert einen Dolmetscher für die Lambda-Rechnung in Stratego. Vermutlich reicht dies aus, um zu zeigen, dass Stratego Turing-vollständig ist.

Wenn Sie an einem spezifischeren Begriff der Ausdruckskraft interessiert sind, empfehle ich Ihnen, Ihre Frage neu zu formulieren.

In Bezug auf den praktischen Gebrauch fand ich die Hauptbeschränkung von Stratego, dass es nur über eine Datenstruktur betrieben wurde, nämlich den zu transformierenden Baum. Die Verwendung anderer Datenstrukturen wie einer Symboltabelle war unnatürlich (zumindest in Stratego vor mehr als 5 Jahren). Obwohl Stratego ideal für Transformationen an einem einzelnen Baum ist, ist es nicht einfach, Operationen an zwei Bäumen gleichzeitig durchzuführen.

Dave Clarke
quelle