Warum Naturals statt Integer?

28

Mich interessiert, warum natürliche Zahlen bei den Autoren von Büchern über Programmiersprachentheorie und Typentheorie so beliebt sind (z. B. J. Mitchell, Grundlagen für Programmiersprachen und B. Pierce, Typen und Programmiersprachen). Die Beschreibung des einfach getippten Lambda-Kalküls und insbesondere der PCF-Programmiersprache basiert normalerweise auf Nat's und Bool's. Für die Menschen, die industrielle PL für allgemeine Zwecke verwenden und unterrichten, ist es viel natürlicher, Ganzzahlen anstelle von natürlichen Werten zu behandeln. Können Sie einige gute Gründe nennen, warum PL-Theoretiker Nat's bevorzugen? Ansonsten ist es etwas unkomplizierter. Gibt es fundamentale Gründe oder ist es nur eine Ehre der Tradition?

UPD Bei all diesen Kommentaren zur „Fundamentalität“ von Naturals: Ich bin mir all dieser coolen Dinge durchaus bewusst, aber ich würde lieber ein Beispiel sehen, wenn es wirklich wichtig ist, diese Eigenschaften in der Typentheorie der PL-Theorie zu haben. ZB häufig erwähnte Induktion. Wenn wir irgendeine Art von Logik haben (die einfach LC ist), wie grundlegende Logik erster Ordnung, verwenden wir wirklich Induktion - aber Induktion auf Ableitungsbaum (die wir auch in Lambda haben).

Meine Frage kommt hauptsächlich von Leuten aus der Industrie, die eine grundlegende Theorie der Programmiersprachen erlernen wollen. Früher hatten sie ganze Zahlen in ihren Programmen und ohne konkrete Argumente und Anwendungen für die Theorie, die studiert wurde (in unserem Fall Typentheorie), warum sie sich ziemlich enttäuscht fühlen, wenn sie Sprachen nur mit Nat lernen.

Artem Pelenitsyn
quelle
Ich denke, dies ist keine Frage auf Forschungsebene, obwohl es eine interessante ist.
Raphael
4
Das ist nicht so, aber es ist eine Art große Frage, die wir akzeptieren.
Suresh Venkat
1
Ich frage mich, ob die Menge der nicht-negativen ganzen Zahlen in irgendeiner Weise aufgrund der einzigartigen Eigenschaften des 0-Werts, die es in letzterem nicht gibt, noch fundamentaler sein könnte als natürliche Zahlen. Ich würde auch vorschlagen, dass dies als die Wahl des grundlegenden numerischen Typs für digitale Computer angesichts der Wichtigkeit von 0 mehr Gültigkeit hat.
Richard Cook
Ich verstehe dein UPD nicht . Naturals sind fundamentaler als ganze Zahlen, und die Antworten geben Beispiele dafür, warum dies der Fall ist.
Radu GRIGore
Betreff: UPD. Ich bin mir nicht sicher, warum "Leute aus der Industrie" "enttäuscht" werden. (Ich habe meine Karriere in der Industrie selbst verbracht.) Warum sollte man erwarten, dass diese Theorie eine offensichtliche Erweiterung dessen ist, was sie bereits kennt? Es ist durchaus üblich, dass bestimmte in der Industrie übliche Dinge, ähnlich wie ganzzahlige Variablen, eher aus "historischen Gründen" als aus tiefgehenden theoretischen Gründen vorliegen.
Marc Hamann

Antworten:

24

Kurze Antwort: Die Naturals sind die ersten Grenzwerte. Daher spielen sie eine zentrale Rolle in der axiomatischen Mengenlehre (z. B. ist das Axiom der Unendlichkeit die Behauptung, dass sie existieren) und in der Logik, und PL-Theoretiker neigen dazu, grundlegende Interessen mit Logikern zu teilen. Wir wollen Zugang zum Prinzip der Induktion haben, um die vollständige Korrektheit, Beendigung und ähnliche Eigenschaften zu beweisen, und die Naturtöne sind eine (er) natürliche Wahl der Ordnung.

Ich möchte nicht implizieren, dass binäre Ganzzahlen mit endlicher Breite weniger coole Objekte sind. Sie sind Darstellungen der p-adics und erlauben uns, Potenzreihenmethoden in der Zahlentheorie und in der Kombinatorik anzuwenden. Dies bedeutet, dass ihre Bedeutung in der Algorithmik sichtbarer wird als in PL, da wir uns dann mehr um Komplexität als um Terminierung kümmern.

Neel Krishnaswami
quelle
20

Naturals sind ein viel grundlegenderes Konzept als die ganzen Zahlen.

Die Induktion erfolgt über die natürlichen Zahlen, und die ganzen Zahlen können aus den natürlichen Zahlen abgeleitet werden, indem einfach ein unärer inverser Operator hinzugefügt wird.

Eigentlich möchte ich die umgekehrte Frage stellen: Warum haben frühe Programmiersprachen- (und Registermaschinen-) Designer Ganzzahlen als Basisdatentyp festgelegt, wenn sie so zweitrangig sind und sich so leicht von Naturals ableiten lassen?

Ich vermute, es liegt nur daran, dass es einige coole Binärkodierungen gab, die ganze Zahlen elegant handhaben konnten. ;-)

Überlegen Sie, wie oft Sie den negativen Bereich einer programmatischen Ganzzahl ignorieren möchten, und betrachten Sie den Impuls, einen vorzeichenlosen Ganzzahltyp zu haben, um das verlorene Bit wiederherzustellen.

Marc Hamann
quelle
5
Ein weiterer Grund: Wenn Sie so etwas wie Church-Zahlen wollen, müsste eine negative Ganzzahl die Funktionsinversion bezeichnen. In diesem Kontext wären also ganze Zahlen in einem Kalkül von rechnerisch bijektiven Funktionen natürlicher.
Per Vognsen
@Per Vognsen: Ich bin mir nicht sicher, wie du da argumentierst. Aber ich denke, man kann mit Sicherheit sagen, dass die rechnerisch bijektiven Funktionen die meiste Zeit weniger grundlegend sind als willkürlich berechenbare Funktionen. ;-)
Marc Hamann
Es steht außer Frage, dass komplexe Zahlen, die an der Spitze der Zahlenhierarchie stehen, natürliche Zahlen -> ganze Zahlen -> rationale Zahlen -> reelle Zahlen -> komplexe Zahlen grundlegender sind als die anderen, weil sie "schönere" algebraische Eigenschaften haben. Sie sind überall in der Wissenschaft zu finden, fehlen aber auffällig in den "Grundlagen" der Mathematik. Die Antwort auf "grundlegendere" Ganzzahlen oder natürliche Zahlen hängt also wirklich davon ab, wen Sie fragen: Algorithmusiker oder Algebraist.
Tegiri Nenashi
Da es sich um eine TCS-Site handelt, sind wir meiner Meinung nach in der Lage, die Sichtweise der Informatik zu schützen. ;-) Computerisch gesehen ist diese Hierarchie progressiv: Jeder neue Eintrag baut buchstäblich auf dem vorherigen auf. Da sich "fundamental" normalerweise auf etwas an der Basis bezieht, denke ich, dass das natürliche Ende das richtige ist, um diesen Titel zu verleihen.
Marc Hamann
17

Zwischen und besteht eine berechenbare Trennung . Daher ist es ausreichend, über die Berechenbarkeit und dergleichen nur mit natürlichen Zahlen zu argumentieren. Dabei müssen Sie stets wissen, dass sich Ihre Ergebnisse auf ganze Zahlen (und rationale Zahlen sowie alle anderen rekursiv aufzählbaren Mengen) verallgemeinern lassen.NZ

Nur auf natürliche Weise zu argumentieren ist praktisch, weil Sie eine Induktion haben und eine fundierte Menge mit der natürlichen Ordnung . Letzteres ist besonders wichtig, da es in Termination Proofs instrumentalisiert werden kann. Sie können zwar eine fundierte Reihenfolge in , dies ist jedoch weniger praktisch, da sie nicht der üblichen Reihenfolge entspricht.NZ

Raphael
quelle
11

Ein weiterer Grund (im Zusammenhang mit den bereits gegebenen, aber diese Antwort fügt neue Informationen hinzu) ist, dass es eine sehr einfache, quotientenfreie Konstruktion der Naturals gibt, die mit einem schönen Induktionsprinzip einhergeht [wie bereits gesagt]. . Was nicht erweitert wurde, ist, wie schwierig es ist, eine quotientenfreie Konstruktion der ganzen Zahlen zu finden.

Je mehr Programme ich dort programmiere, wo ich eine hohe Sicherheit haben möchte, desto mehr brauche ich die natürlichen Werte und nur die für mich vordefinierten ganzen Zahlen zu haben, ist für mich ein echtes Problem.

Jacques Carette
quelle
Es gibt Sprachen, die einen Grundtyp für Naturmenschen haben, wissen Sie.
Raphael
@ Raffael: Ich weiß. Aber nicht die, die ich sonst mag (nämlich Haskell und OCaml). Ich bin noch nicht ganz bereit, mit dem Programmieren in Agda oder Coq zu beginnen.
Jacques Carette
Was ist so schlimm an Quotienten?
David Harris
3
Quotienten sind in der Semantik großartig. Sie sind in tatsächlichen Berechnungen und in konkreten Darstellungen sehr viel schwieriger zu handhaben. Es gibt unzählige Artikel darüber, wie man mit Coq, Isabelle, Agda (Typentheorie im Allgemeinen) usw. umgeht. Ich habe nur angenommen, dass es Folklorewissen in allen Gemeinschaften ist, dass Quotienten nur ein Schmerz sind, mit „in der Realität“ umzugehen.
Jacques Carette
2
Ich denke, dies ist die stärkste Antwort der Gruppe: Naturals sind der einfachste nicht-triviale induktive Datentyp. Sobald Sie eine Definition gegeben und einfache Eigenschaften für natürliche Zahlen bewiesen haben, haben Sie den Weg für komplexere induktive Datentypen wie Listen oder Bäume geebnet.
Cody
7

Gibt es gute Gründe, warum PL-Theoretiker Naturals anstelle von ganzen Zahlen bevorzugen? Es gibt einige, aber in einem Lehrbuch über die Semantik von Programmiersprachen gibt es meines Erachtens keinen technischen Grund, warum dies erforderlich ist. Ich kann mir keinen anderen Ort als abhängige Typsysteme vorstellen, an dem die Induktion von Daten in der PL-Theorie wichtig ist. Andere Lehrbücher von Mike Gordon , David Schmidt , Bob Tennent und John Reynolds machen das nicht. (Und diese Bücher wären wahrscheinlich viel besser geeignet, um Menschen beizubringen, die sich für industrielle Allzweck-PL interessieren!)

Sie haben also den Beweis, dass dies nicht notwendig ist. Tatsächlich würde ich behaupten, dass ein gutes Lehrbuch zur PL-Theorie in den primitiven Typen der Programmiersprache parametrisch sein sollte , und es ist irreführend, etwas anderes vorzuschlagen.

Uday Reddy
quelle
6

Naturals und Bools und Operationen auf ihnen können auf einfache Weise in der reinen Lambda-Rechnung als sogenannte Church-Ziffern (und Church-Bools, nehme ich an) kodiert werden. Es ist nicht klar, wie man ganze Zahlen schön codieren würde, obwohl dies offensichtlich möglich ist.

Dave Clarke
quelle
Ich meinte zuallererst typisierte Lambda-Kalkül. Der Verlauf der Bücher, die ich oben erwähnt habe, basiert darauf. Ich denke, nicht typisiertes Lambda ist heutzutage in der Typentheorie und in der PL-Theorie nicht so wichtig (ich kann mich irren, aber das sehe ich in diesen Büchern.). Trotzdem danke!
Artem Pelenitsyn