Hat Godels Unvollständigkeitstheorem ein Licht auf dynamische und getippte Sprachen aus? [abgeschlossen

Question

Ich bin selbst Clojure -Benutzer. Ich bemühe mich sehr, Haskell zu lernen und das Typsystem besser zu verstehen. Ich habe jedoch das Gefühl, dass der Versuch, alles zu "tippen", ziemlich restriktiv ist, wenn das Problem oder die Daten weniger definiert sind.

Ich habe intuitiv das Gefühl, dass Godels Unvollständigkeitstheorem einen Einblick in die typisierte/untypische Debatte bietet. Was sind einige einfache Probleme, die das Schreibsystem aufstürzen können, aber nicht untypisch sind?

---

Entsprechend http://en.wikipedia.org/wiki/type_theory. "Die Type der Typtheorie wurde von Bertrand Russell als Reaktion auf seine Entdeckung erfunden, dass Gottlob Freges Version der Naive -Set -Theorie mit Russells Paradoxie betroffen war Eine Hierarchie von Typen, die dann jeder mathematischen (und möglicherweise anderen) Entität einem Typ zuweisen. Objekte eines bestimmten Typs werden ausschließlich aus Objekten der vorhergehenden Typen (die in der Hierarchie niedrigeren) erstellt, wodurch Schleifen verhindert werden. "

Godels Theorem hat Principia Mathematica ungültig gemacht. Welche Konsequenz hat es auf Typtheorie?

Answer 1

Also sagt Godels Unvollständigkeitssatz, wenn ich mich richtig erinnere, dass ein ausreichend mächtiges logisches System nicht sowohl konsistent als auch vollständig sein kann. Ein gutes Typ-System ist übereinstimmend, daher muss es unvollständig sein, dh es enthält gut getroffene Programme, die nicht kompiliert werden.

In der Praxis ist dies kein Problem. Wieso den? Weil Inferenz- und Typ -Überprüfung zwei separate Dinge sind. Typinferenz ist normalerweise unentscheidbar und beinhaltet einen Ausdruck und die Bestimmung seiner Art. Die meisten Typ -Inferenzalgorithmen sind unvollkommen, dh sie können nicht immer den Typ eines Ausdrucks schließen.

Die Typ-Überprüfung ist dagegen einfach. Wenn Sie die Arten von Ausdrücken in einem Programm kennen, ist es tot, festzustellen, ob es gut getippt ist. Alles, was Sie tun müssen, ist also die Fälle zu finden, in denen die Inferenzmotorin von Typ Inference Hilfe benötigt, ausdrücklich mitzuteilen, was die Typen sind, und es ist gut, die Überprüfung durchzuführen. Deshalb lassen Haskell und ML Sie immer noch Unterschriften schreiben.

Wie DW sagt, können Sie jedes Problem, das Sie in Clojure lösen können, Sie in Haskell lösen können. Ein Typ Checker ändert dies überhaupt nicht. Alles, was ein Typ Checker tut, findet zum Kompilieren von Zeiten Dinge, die zur Laufzeit Fehler verursachen können.

Wenn es auf Clojure, aber nicht in Haskell funktioniert, bedeutet dies größtenteils, dass es einen Fehler in Ihrem Clojure -Code gibt. Das dynamische Tippen ist beliebt, weil Sie schnell schreiben können, aber gefährlich, weil der Compiler Ihnen nicht sagt, wann Sie es vermasseln.

Answer 2

Haskell ist vervollständigt. Das bedeutet, dass jede Berechnung, die in Clojure ausgedrückt werden kann, auch in Haskell (und umgekehrt) ausgedrückt werden kann. Folglich gibt es keinen Unterschied in der Ausdrucksfähigkeit der beiden Sprachen. Dies bleibt trotz des Typsystems wahr.

Mir ist keine Einsicht bekannt, dass Godels Unvollständigkeitssatz anbietet, ob statisch typisierte Sprachen "besser" sind als nicht -untypische Sprachen (für eine nicht spezifizierte Definition von "besser").