Was bedeutet es für eine Sprache statisch typisiert werden?

StackOverflow https://stackoverflow.com/questions/3623323

Frage

Mein Verständnis ist, dass es bedeutet, dass man möglicherweise ein Programm schreiben kann formal beweisen, dass ein Programm in einer statisch typisierten Sprache geschrieben werden frei sein von einer bestimmten (kleinen) Teilmenge von Defekten.

Mein Problem dabei ist wie folgt:

Nehmen wir an, wir zwei Turing komplette Sprachen haben, A und B. A angenommen wird, zu sein ‚Typ sicher‘ und ‚B‘ angenommen wird, nicht zu sein. Angenommen, ich bin ein Programm L gegeben, um die Korrektheit eines Programms in A. geschrieben zu überprüfen Was mich in B zu A aus der Umrechnung jedes Programms geschrieben zu stoppen ist, die Anwendung L. Wenn P von A nach B übersetzt dann warum nicht PL a gültig Typprüfer für jedes Programm in B geschrieben?

Ich bin in Algebra trainiert und bin erst am Anfang CS zu studieren, so könnte es einiger offensichtlicher Grund dafür sein, dass dies nicht funktioniert, aber ich würde sehr gerne wissen. Dieses ganze ‚Typ Sicherheit‘ Ding hat für eine Weile zu mir riecht fischig.

War es hilfreich?

Lösung

Es sei A Ihre Turing-complete Sprache, die angeblich statisch typisiert werden und A lasst uns sein, die Sprache, die Sie von A, wenn Sie die Typprüfung entfernen (aber nicht die Typenannotationen, weil sie auch anderen Zwecken dienen). Die akzeptierten Programme von A wird eine Teilmenge der genehmigten Programme von A‘sein. So insbesondere, A‘wird auch sein Turing-vollständig.

Ihr Übersetzer P von B nach A Given (und umgekehrt). Was soll es tun? Es könnte ein von zwei Dingen tun:

  1. Erstens ist es jedes Programm y von B zu einem Programm von A. In diesem Fall übersetzen könnte, würde LPY immer wahr zurück, wie Programme von A nach Definition ist richtig eingegeben hat.

  2. Zweitens P jedes Programm y von B zu einem Programm von A‘übersetzen könnte. In diesem Fall würde LPY Wahr zurück, wenn Py ein Programm von A und falsch sein passiert, wenn es nicht.

Wie der erste Fall nichts interessant ergeben, lassen Sie uns mit dem zweiten Fall bleiben, was wahrscheinlich ist, was du meinst. Ist die Funktion LP definiert auf Programme von B sagen uns etwas Interessantes über die Programme von B? Ich sage nein, weil es nicht invariant unter einer Veränderung von P. Als A ist Turing-vollständig, auch im zweiten Fall P gewählt werden, so dass sein Bild liegt in A. geschieht Dann würde LP ständig wahr sein. Auf der anderen Seite könnte P so gewählt werden, dass einige Programme auf das Komplement von A in A‘abgebildet werden. In diesem Fall würde LP für einige falsche ausspucken (möglicherweise alle) Programme von B. Wie Sie sehen können, erhalten Sie nicht alles, was auf y hängt nur.

Ich kann es auch mehr setzen mathematisch in folgender Weise: Es gibt eine Kategorie C Sprachen zu programmieren, deren Objekte sind die Programmiersprachen und deren Morphismen sind Übersetzer von einer Programmiersprache in eine andere. Insbesondere, wenn es ein Morphismus P: X -> Y, Y mindestens so ausdrucksstark wie X. Zwischen jedem Paar von Turing-complete Sprachen gibt morphisms in beiden Richtungen ist. Für jedes Objekt X von C (dh für jede Programmiersprache) wir einen zugehörigen Satz, sagen wir {X} (schlechte Schreibweise, ich weiß) dieser teilweise definierten Funktionen, die von Programmen von X. Jeder Morphismus P berechnet werden kann: X - > Y induziert dann eine Einfügung {X} -> {y} von Sätzen. Lassen Sie uns formal Invertzucker all jene morphisms P: X -> Y, dass die Identität {X} induzieren -> {Y}. Ich werde die resultierende Kategorie nennen (was mathematisch ist, eine Lokalisierung von C) durch C‘. Nun ist die Aufnahme A -> A 'ein Morphismus in C'. Es ist jedoch nicht unter automorphisms Konservierte ‚die die morphism A -> A‘ ist keine unveränderliche von A ‚in C‘. Mit anderen Worten: Von dieser abstrakten Sicht ist das Attribut „statisch typisierte“ nicht definierbar und kann beliebig an eine Sprache gebunden sein

.

Um meinen Punkt klarer machen Sie auch von C‘als die Kategorie der denken kann, sagen wir, geometrische Formen im dreidimensionalen Raum zusammen mit den euklidischen Bewegungen als morphisms. A ‚und B sind dann zwei geometrische Formen und P und Q sind euklidische Bewegungen B zu A zu bringen‘, und umgekehrt. Zum Beispiel, A‘und B zwei Kugeln sein könnte. Lassen Sie uns nun einen Punkt an einer Lösung ‚die für die Teilmenge A von A stehen wird‘. Lassen Sie uns diesen Punkt als „statisch typisiert“. Wir wollen wissen, ob ein Punkt von B statisch typisiert wird. Also haben wir ein solcher Punkt y nehmen, wo es sich über P auf A ‚und Test, ob es unsere markierten Punkt auf A‘. Wie man leicht sehen kann, hängt dies von der gewählten Karte P, oder mit anderen Worten ausgedrückt: ein Punkt auf einer Kugel markierte nicht durch automorphisms erhalten wird (die euklidischen Bewegungen werden, dass die Kugel auf mich selbst abbilden) diese Kugel

Andere Tipps

Wenn können Sie übersetzen alle B '(ein Programm in B geschrieben) in eine äquivalenten A' (was richtig ist, wenn B‘), dann die Sprache B genießen nur so viel „Typsicherheit“ als Sprache A (in einem theoretischen Sinn, natürlich ;-) - im Grunde würde dies bedeuten, dass B ist, so dass Sie perfekte Art Inferenz tun können. Aber das für eine dynamische Sprache extrem begrenzt ist - zum Beispiel betrachten: 

if userinput() = 'bah':
    thefun(23)
else:
    thefun('gotcha')

wo thefun (nehmen wir an) typsicher für int-Argument ist, aber nicht für str Argument. Nun - wie übersetzen Sie diese Sprache A an erster Stelle ...

Eine andere Möglichkeit, den gleichen Punkt zu machen, wie gemacht worden ist, ist, dass Ihre Frage ein Widerspruchsbeweis dar, dass entweder:

  • A kann nicht auf B abgebildet werden
  • Typsicherheit ist keine lexikalische Eigenschaft einer Sprache

oder beides. Meine Intuition sagt, dass das letztere ist wohl der Knackpunkt:., Dass Typ-Sicherheit ist eine metasprachlichen Eigenschaft

Es gibt nichts „fischigen“ darüber. ;)

Der Satz von Turing-complete Sprachen, die in Bezug auf eine nicht-triviale typsicher sind [ 1 ] Typ-System T ist ein strenge Teilmenge der Turing-complete Sprachen. Als solche im allgemeinen Fall, kein Übersetzer P -1 von B A existiert; daher auch nicht jedes translator- cum -Typ-checker LP -1 .

Ein reflexartige Reaktion auf diese Art von Anspruch könnte sein: Unsinn! Sowohl A und B sind Turing-vollständig, so kann ich ausdrücken alle berechenbare Funktion in entweder Sprache! Und in der Tat, das ist richtig - Sie können jede berechenbare Funktion in jeder Sprache ausdrücken; jedoch recht häufig, können Sie auch ausdrücken ein bisschen mehr . Insbesondere Sie Ausdrücke, dessen denotational Semantik ist nicht gut definiert, wie sie konstruieren können, die glücklich die arithmetische Summe der Zeichenkette „foo“ zu nehmen versuchen könnten, und „bar“ (das ist der Kern von Chubsdad Alex Martelli 's Antwort). Diese Art von Ausdrücken kann „in“ die Sprache sein, B , kann aber einfach nicht in der Sprache ausdrückbar sein A , weil die denotational Semantik nicht definiert ist, so gibt es keine vernünftige Art und Weise, sie zu übersetzen.

Dies ist eine der großen Stärken der statischen Typisierung: Wenn Ihr Typ-System nicht in der Lage ist, zu beweisen, bei der Kompilierung, dass die oben genannte Funktion all Parameter erhalten, aber diejenigen, für die das Ergebnis des arithmetischen Additionsoperators ist wohldefiniert kann es als schlecht getippt abgelehnt werden.

Beachten Sie, dass während über die die übliche Art Beispiel ist gegeben, die Vorzüge eines statischen Typsystem zu erklären, ist es vielleicht zu bescheiden ist. Im Allgemeinen wird ein statisches Typsystem muß nicht nur die Durchsetzung typ Richtigkeit der Parameter beschränkt sein, sondern in der Tat zum Ausdruck bringen kann jeder gewünschte Eigenschaft eines Programms, das zum Zeitpunkt der Kompilierung nachgewiesen werden kann. Zum Beispiel ist es möglich, Typ-Systeme, die die Einschränkung erzwingen, dass ein Release ein Dateisystem Griff ( zB in einer Datenbank, Datei, Netzwerk-Socket, etc. ) innerhalb der konstruieren gleicher Umfang, in dem sie erworben wurden. Offensichtlich ist dies ungeheuer wertvoll in solchen Bereichen wie Lebenserhaltungssysteme, unter anderem, wo beweisbar Korrektheit wie viele Parameter des Systems wie möglich absolut notwendig ist. Wenn Sie den statischen Typ-System erfüllen, können Sie diese Art von Beweisen kostenlos.

[ 1 ] Durch die nicht-triviale, ich meine, dass nicht alle möglichen Ausdrücke sind gut getippt.

Mein Verständnis ist, dass diese mit Compile-Zeit vs. Laufzeit zu tun haben. In einer statisch typisierten Sprache ist die Mehrheit der Typprüfung während der Kompilierung Zeit durchgeführt. In einer dynamisch typisierte Sprache, ist die Mehrheit der Typprüfung zur Laufzeit durchgeführt wird.

Lassen Sie mich beantworten andersrum:

Es gibt zwei verschiedene Arten von "dynamic" Programmierung.

ist „dynamisch typisiert“, was bedeutet, dass Sie irgendeine Art von einer Shell haben, wo Sie durch Eingabe Definitionen in dieser Shell programmieren können, denken Sie daran, wie Python IDLE-Shell.

Die andere Art der dynamischen Programmierung, ist ein theoretischer. Ein dynamisches Programm, ist eine, die seine eigene Quelle ändern kann. Es braucht ein gewisses Maß an introjection und wird oft auf Mikrocontrollern ändern Programmspeicher verwendet. In manchen Tabellen zu erzeugen Lookup für Anzahl Knirschen wird die dynamische Programmierung genannt.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top