Programmiersprachen mit kanonischen Funktionen

29

Gibt es (funktionale?) Programmiersprachen, in denen alle Funktionen eine kanonische Form haben? Das heißt, zwei beliebige Funktionen, die für alle Eingaben die gleichen Werte zurückgeben, werden auf die gleiche Weise dargestellt, z. B. wenn f (x) x + 1 und g (x) x + 2 zurückgibt, dann f (f (x) )) und g (x) erzeugen nicht unterscheidbare ausführbare Dateien, wenn das Programm kompiliert wird.

Was vielleicht noch wichtiger ist: Wo und wie finde ich weitere Informationen zur kanonischen Repräsentation von Programmen (Googeln mit "kanonischen Repräsentationsprogrammen" war weniger als erfolgreich)? Es scheint eine natürliche Frage zu sein, und ich fürchte, ich kenne einfach nicht den richtigen Begriff für das, wonach ich suche. Ich bin neugierig, ob es möglich ist, dass eine solche Sprache vollständig ist, und wenn nicht, wie ausdrucksstark eine Programmiersprache ist, die Sie haben können, während Sie eine solche Eigenschaft behalten.

Mein Hintergrund ist eher begrenzt, daher bevorzuge ich Quellen mit weniger Voraussetzungen, aber Verweise auf weiterführende Quellen können auch cool sein, da ich auf diese Weise weiß, worauf ich hinarbeiten möchte.

math4tots
quelle

Antworten:

38

Inwieweit dies überhaupt möglich ist, ist in der Theorie der Lambda-Rechnung eine große offene Frage. Hier ist eine kurze Zusammenfassung dessen, was bekannt ist:

  • Der einfach typisierte Lambda-Kalkül mit Einheit, Produkten und Funktionsraum hat eine einfache kanonische Formulareigenschaft. Zwei Terme sind genau dann gleich, wenn sie dieselbe Beta-normale, eta-lange Form haben. Das Berechnen dieser Normalformen ist ebenfalls recht einfach.

  • Das Hinzufügen von Summentypen erschwert die Sache erheblich. Das Gleichheitsproblem ist noch zu entscheiden (das Schlüsselwort, nach dem gesucht werden soll, ist "Koproduktgleichheit"), aber die bekannten Algorithmen funktionieren aus äußerst schwierigen Gründen, und meines Wissens gibt es keinen vollständig befriedigenden Satz über die normale Form. Hier sind die vier mir bekannten Ansätze:

  • Die Hinzufügung unbegrenzter Typen, wie beispielsweise natürlicher Zahlen, macht das Problem unentscheidbar. Grundsätzlich können Sie jetzt Hilberts zehntes Problem codieren.

  • Die Hinzufügung von Rekursion macht das Problem unentscheidbar, weil normale Formen die Gleichheit entscheidbar machen, und das würde es Ihnen ermöglichen, das Problem des Anhaltens zu lösen.

Neel Krishnaswami
quelle
In diesem Artikel wird die Äquivalenz mit Nebenprodukten auf die Äquivalenz mit Summen ausgedehnt. Es gibt jedoch keine "einzelne" kanonische Formsyntax. Sie wählen eine "Sättigungsfunktion" aus, die intelligent genug ist, um zu erkennen, ob die beiden zu vergleichenden Begriffe Subtermen aufweisen, die sich als falsch erweisen. Es ist Ahmed-Licata-Harper am ähnlichsten, da beide die Fokussierung verwenden.
Max New
Mit nur Einheiten, Produkten und Funktionen ist die Kardinalität von allem, was Sie aufschreiben können, 1, während Sie plötzlich viele verschiedene Kardinalitäten erhalten, wenn Sie Summen addieren (und "nützliche Berechnungen" ausführen können). Stehen diese Tatsachen im Zusammenhang?
Glaebhoerl
1
bλx:b.λy:b.xλx:b.λy:b.y