Was ist der Unterschied zwischen den semantischen und syntaktischen Ansichten der Funktionstypen?

Question

Bearbeiten: Meine ursprüngliche Frage genannt nicht konstruktiv und konstruktiv Definitionen von Funktionstypen. Ich habe die Terminologie in der Frage und den Titel geändert zu semantisch und syntaktisch, was die Antwort anzeigt, ist die korrekte Terminologie für diese Unterscheidung.

Ich kann mich an zwei Möglichkeiten erinnern, Funktionen in der festgelegten Theorie- und Programmiersprachen mit set-theoretischen Grundlagen zu definieren. Der Funktionstyp $ tau bis sigma $ kann definiert werden semantisch Als Satz aller Karten von $ tau $ $ sigma cup { bot } $, dh alle Objekte $ f $ so, dass $ x in tau $ $ f (x) in sigma cup { bot } $. Alternativ kann der Funktionstyp $ tau bis sigma $ definiert werden syntaktisch Als Satz aller Begriffe in einer bestimmten Sprache, deren Typ $ tau bis sigma $ ist (möglicherweise modulo eine Äquivalenzbeziehung). Als Programmierer arbeite ich mit der letzteren Definition, aber ich tue oft vor, dass ich mit der früheren Definition arbeite.

Was sind die Unterschiede zwischen den Bewohnern von $ tau bis sigma $ gemäß den beiden oben genannten Definitionen? Sind beispielsweise unzureichende Funktionen in der ersten, aber nicht in der zweiten Definition enthalten?

Um genau zu sein, interessiere ich mich für die Situation, in der die Begriffe stark getippt werden, Funktionen kostenlos sind und möglicherweise nicht terminiert werden, und die Funktionen sind gleich IFF, für alle Eingaben divergieren sie beide denselben Wert.

Answer 1

Diese werden nicht als konstruktiv und nicht konstruktiv bezeichnet! Derjenige, den Sie "nicht konstruktiv" nennen, funktioniert genauso gut in der konstruktiven Mathematik (Sie müssen ein wenig vorsichtig sein, wie Sie den Wert $ bot $ haben, aber das ist ein technisches Detail).

Sie fragen eher nach semantisch und syntaktisch Unterscheidungen. Wir stellen uns vor, dass die Ausdrücke, die wir in einem Programm schreiben, abstrakten mathematischen Objekten entsprechen. Zum Beispiel der syntaktische Ausdruck (fun n => 2 + n) 2 bezeichnet die Nummer $ 4 $. (Unter dieser Ansicht "Bewertung eines Programms" geht es darum, herauszufinden, welches abstrakte mathematische Objekt es bezeichnet.)

Wir können dann fragen, welche mathematischen Objekte, die Ausdrücken vom Typ entsprechen a -> b. Vermutlich sind sie tatsächliche mathematische Funktionen (obwohl dies bei Vorhandensein von Recheneffekten nicht so klar ist). Aber sie sind nicht alle Funktionen, weil diese Funktionen, die in einer Programmiersprache ausgedrückt werden können, spezielle Eigenschaften haben, wie z.

1. sie sind Rechenbar (Weil das Programmieren von Langaugen durch Turing Machiens interpretiert werden kann).

2. sie sind kontinuierlich (Denn in endlicher Zeit können wir nur begrenzte Informationen über Eingaben erhalten, und die Kontinuität besagt im Wesentlichen, dass nur eine endliche Menge an Eingabe erforderlich ist, um eine endliche Ausgabemenge zu erzeugen).

Es kann also sinnvoll sein, auf besondere Arten von mathematischen Funktionen zu beschränken (nur berechnete, nur kontinuierliche). Auf diese Weise werden unsere mathematischen Objekte unseren Programmen genauer entsprechen, und so werden wir vermutlich ein besseres Setup haben. (Sobald wir eine Sprache mit Rekursion haben, können wir uns nicht an Ausdrücke des Typs vorstellen a -> b Als nur gewöhnliche Funktionen, aber eher irgendwie wie die kontinuierlichen-lassen Sie mich jetzt nicht jetzt dorthin gehen.)

Wie Sie sagen, nehmen die meisten Programme eine syntaktisch Ansicht, in welchen Funktionen sind syntaktische Ausdrücke. Dies ist sicherlich eine Möglichkeit, die einen langen Weg zurücklegen kann. Aber die semantisch Ansicht, in dem wir Programme als Bezeichnung mathematischer Objekte betrachten, hat auch seine Vorteile. Mathematiker wissen sehr viel über Berechnbarkeit und Kontinuität, und Sie können das Wissen einbringen, wenn Sie die semantische Sichtweise vertreten.

Eine triviale Anwendung der semantischen Methode lautet: Angenommen, wir möchten den Vergleich von Funktionen implementieren eq : (nat -> nat) -> (nat -> nat) -> bool Das sagt uns, ob zwei Funktionen f, g : nat -> nat sind gleich. Wie machen wir es? Die Antwort ist, dass wir es nicht implementieren können, da dies uns eine diskontinuierliche Funktion geben würde. Es ist jedoch viel schwieriger, diese Tatsache mit nur syntaktischen Methoden zu beweisen. Tatsächlich weiß ich nicht, wie es geht, ohne eine Computerbarkeitstheorie zu verwenden, was wiederum eine semantische Methode ist. Sie mögen denken, dass es offensichtlich ist, dass eq kann nicht implementiert werden, in diesem Fall sollten Sie sich fragen, warum eq : (nat -> bool) -> (nat -> bool) -> bool kann implementiert werden (Und die Implementierung wurde zunächst mit semantischen Methoden gefunden).

Ein weiterer Bereich, in dem die semantische Ansicht benötigt wird, ist die numerische Berechnung. Es ist absurd zu behaupten, dass ein Programm (syntaktisches Unternehmen) zur Lösung einer Differentialgleichung nichts mit Differentialgleichungen (semantische Entität) zu tun hat.

Lassen Sie mich auch sagen, was die konstruktiv-nicht-konstruktiv Unterscheidung ist. Hier geht es um die Logik Sie verwenden Mathe. Wenn wir eine nicht konstruktive Logik verwenden, die die traditionelle Möglichkeit ist, dies zu tun, können wir beweisen, dass es nicht überquerbare Funktionen gibt. Infolgedessen werden wir Funktionen geben, die wir nicht implementieren können. Wenn wir jedoch eine konstruktive Logik verwenden, ist es unmöglich, die Existenz einer nicht erfüllbaren Funktion zu beweisen. (Tatsächlich können wir konstruktiven Logik ein Axiom hinzufügen, in dem "alle Karten berechnet werden", obwohl ich dagegen raten würde: Woher wissen Sie, dass alle externen Eingaben, die aus dem Universum in Ihren Computer kommen? ist nicht der traditionelle Weg, aber es ist eine, mit der Programmierer sympathisieren können.

Zuletzt möchte ich etwas über etwas, das Sie in Ihrem Titel schreiben. Definitionen sind nicht konstruktiv oder nicht konstruktiv. Sie sind es einfach. Konstruktivität ist wichtig, wenn wir beweisen und konstruieren Dinge. Funktionstypen in einer Programmiersprache werden a la Typentheorie in Bezug auf:

• ein Typkonstruktor, wie z. ->
• Regeln für Bildung Begriffe wie $ lambda $ -abstraktion
• Regeln für Verwendung Begriffe wie Anwendung
• Gleichungen die halten sollen, wie $ Beta $ -Reduktion.

Dies funktioniert gleich gut in der konstruktiven und nicht konstruktiven Logik, da es sich nur um Syntax handelt. Es gibt Meta-Theoreme, die sagen, dass für endliche diskrete Objekte (Syntax, natürliche Zahlen, endliche Graphen, Listen, ...) keinen Unterschied zwischen konstruktiver und nicht konstruktiver Logik gibt (ich überspringe viele Details). Aber wenn Sie nach dem fragen Semantik Ihr Typ, dh, welches mathematische Objekt es entspricht, macht es einen Unterschied.