Voll funktionsfähige Programmiersprache ohne statische Typprüfung

Alle Papiere mit dem Thema der vollständigen Funktionsprogrammierung verwenden eine Art statische Typprüfung, um die Gesamtheit sicherzustellen. Dies ist sinnvoll, wenn man bedenkt, dass es leicht ist, eine Sprache Turing-vollständig zu machen. Die Frage ist: Gibt es einen untypisierten / dynamisch typisierten Formalismus, der Gesamtfunktionen sicherstellt?

Bearbeiten

Mit anderen Worten, es gibt einen Formalismus, der nur die Konstruktion von Gesamtfunktionen ermöglicht, wobei die Konstruktion von Teilfunktionen unmöglich ist, sodass keine Filterstufe wie eine Typprüfung oder eine Terminierungsanalyse erforderlich ist.

Die Frage ist, wie Sie Begriffe entfernen, die für immer laufen:

Insbesondere dürfen Dinge wie und der Y-Kombinator NICHT in Ihrer Sprache sein, da sie zum Berechnungen verwendet werden können, die nicht anhalten.$(\lambda x \ldotp x\ x)(\lambda x \ldotp x\ x)$

Durch statische Typisierung in Dingen wie System F werden diese eliminiert: Sie beginnen mit einem vollständigen Lambda-Kalkül und filtern dann schlecht typisierte Begriffe heraus.

Wenn Sie dies jedoch in einer untypisierten Umgebung tun, müssen Sie diese Begriffe konstruktionsbedingt entfernen . Sie können in Ihrer Sprache nicht ausgedrückt werden.

Ich kann mir einige dumme Wege vorstellen, wie die Sprache von imperativen Programmen ohne Funktionen oder nur mit Schleifen über Listen. Im Allgemeinen sind diese problematischen Konstrukte jedoch konstruierbar, sobald Sie Funktionen höherer Ordnung haben. Obwohl ich nicht sagen werde, dass es unmöglich ist, ist es wahrscheinlich sehr schwierig, dies auf eine Weise zu tun, die viel Sinn macht.

Es ist für Sie möglich, diese Dinge statisch mit etwas herauszufiltern, das kein Typsystem ist, mit Terminierungsprüfern, aber diese werfen immer falsch positive Ergebnisse aus, und obwohl sie keine statische Typisierung sind, sind sie dennoch ein statischer Filter Ihre Programme.

Beachten Sie, dass Sie abhängig davon, was Sie als "dynamisch typisiert" betrachten, solche Programme eliminieren können, indem Sie die Typen mithilfe von Inferenz verfolgen, aber nur zur Laufzeit Fehler auslösen. So etwas wie der Y-Kombinator wird erst später abgelehnt. Dies wird dynamisch eingegeben, aber wahrscheinlich nicht das, wonach Sie suchen.

Absolut! Es gibt sogar eine bestehende Implementierung! Ich habe dieses loop.pyProgramm in Python geschrieben:

while True:
    print "Hello world!"
    print "20 GOTO 10"

Und lief es so : timeout 10 python loop.py. Tadaa!

Was halten Sie für eine "statische Analyse"? Eine Programmiersprache, die nur for-Schleifen enthält, wird immer beendet. Ist das Parsen "statische Analyse"? Wie wäre es mit einem Compiler, der ein C-Programm kompiliert und 10 Sekunden lang ausführt und den kompilierten Code nur zurückgibt, wenn das Programm beendet wird?

In der theoretischen CS haben wir immer die Möglichkeit, ein Programm einige Schritte zur "Kompilierungszeit" auszuführen, um zu sehen, was passiert. Zur Laufzeit haben Sie immer die Möglichkeit, ein Programm vorzeitig zu beenden, wenn es zu lange dauert. In der Tat ist es das, was die überwiegende Mehrheit der Programme tut, anstatt "Terminierungsprüfung". Es gibt sogar eine solche Funktion für Javascript-Skripte im Browser (oder das berüchtigte "Programm reagiert nicht" -Nachrichten).