Gibt es eine mathematische Modell oder Theorie hinter Programmiersprachen? [geschlossen]

Question

RDBMS basieren auf Relationale Algebra sowie Codds Modell. Haben wir etwas Ähnliches wie für Programmiersprachen oder OOP?

Answer 1

  

Haben wir [ein zugrunde liegendes Modell] für Programmiersprachen?

Mein Gott, ja. Und weil es so viele Programmiersprachen gibt es mehrere Modelle zur Auswahl. Wichtigste zuerst:

• Kirche nicht typisierten Lambda-Kalkül ist ein Berechnungsmodell, das als Turing-Maschine so mächtig ist (nicht mehr und nicht weniger). Die berühmte „Church-Turing-Hypothese“ ist, dass diese zwei gleichwertigen Modelle des allgemeinste Modell der Berechnung dar, dass wir wissen, wie zu implementieren. Das Lambda-Kalkül ist denkbar einfach; in seiner Gesamtheit ist die Sprache

  e ::= x | e1 e2 | \x.e
  

  , welche darstellen Variablen Funktionsanwendungen und Funktionsdefinitionen . Das Lambda-Kalkül kommt auch mit einer ziemlich großen Sammlung von „Reduktionsregeln“ für Ausdrücke zu vereinfachen. Wenn Sie einen Ausdruck finden, die nicht reduziert werden kann, die eine „Normalform“ bezeichnet wird und einen Wert darstellt.

  Das Lambda-Kalkül ist so allgemein, dass man es in mehrere Richtungen erfolgen kann.

  • Wenn Sie alle verfügbaren Regeln verwenden, können Sie spezialisierte Tools wie Teil Gutachtern und Teile von Compilern.

  schreiben

  • Wenn Sie subexpression unter einem Lambda vermeiden reduzieren, aber sonst alle die Regeln zur Verfügung verwenden, Sie winden sie mit einem Modell einer faulen funktionalen Sprache wie Haskell oder reinigen. In diesem Modell kann, wenn eine Reduktion beenden, ist es garantiert, und es ist einfach unendliche Datenstrukturen darzustellen. Sehr mächtig.

  • Wenn Sie subexpression unter einem Lambda vermeiden reduzieren, und wenn Sie darauf bestehen, auch jedes Argument in einer normalen Form vor einer Funktion auf der Reduzierung angewandt wird, dann haben Sie ein Modell einer eifrig funktionale Sprache wie F #, Lisp, Objective Caml, Schema oder Standard ML.

• Es gibt auch mehrere Varianten von getippt Lambda-Kalküle, von denen die bekanntesten unter dem Namen gruppiert sind System F , die von Girard unabhängig entdeckt wurde ( in der Logik) und von Reynolds (in der Informatik). System F ist ein ausgezeichnetes Modell für Sprachen wie CLU, Haskell und ML, die polymorphen sind, aber die Kompilierung Typüberprüfung. Hindley (in der Logik) und Milner (in der Informatik) entdeckten eine eingeschränkte Form von System F (jetzt Hindley-Milner-Typ-System genannt), die es möglich macht, System F Ausdrücke von einigen Ausdrücken der untypisierten Lambda-Kalkül. Damas und Milner entwickelten einen Algorithmus diese Folgerung tun, die in Standard ML verwendet wird, und hat in anderen Sprachen.

verallgemeinert

• Lambda-Kalkül treibt nur Symbole um. Dana Scotts Pionierarbeit in den denotational Semantik hat gezeigt, dass Ausdrücke in dem Lambda-Kalkül tatsächlich entspricht mathematische Funktionen, und er welche diejenigen identifiziert. Scotts Arbeit ist besonders wichtig bei der Herstellung Sinne von „rekursive Definitionen“, die in der Informatik alltäglich sind, aber unsinnig aus mathematischer Sicht. Scott und Christopher Stracheys zeigten, daß eine rekursive Definition auf die dest definierten Lösung auf eine Rekursionsgleichung äquivalent ist, und darüber hinaus gezeigt, wie man diese Lösung aufgebaut werden könnte. Jede Sprache, die Rekursion erlaubt und vor allem Sprachen, die Rekursion an beliebigem Typ (wie Haskell und Clean) erlauben verdanken etwas Scotts Modell.

• Es gibt eine ganze Familie von Modellen basierend auf abstrakte Maschinen . Hier gibt es nicht so sehr ein individuelles Modell als eine Technik. Sie können durch die Verwendung einer Zustandsmaschine ist und Übergänge an der Maschine eine Sprache definieren. Diese Definition umfasst alles von Maschinen bis Von-Neumann-Maschinen Begriff-Neuschreiben-Systeme Turing, aber in der Regel die abstrakte Maschine ist so konzipiert, dass „so nah an den language wie möglich.“Die Konstruktion solcher Maschinen, und das Geschäft der Sätze über sie beweisen, kommt unter der Überschrift operationale Semantik .

  

Was ist die objektorientierte Programmierung?

Ich bin nicht so gut erzogen, wie ich über abstrakte Modelle für OOP verwendet werden soll. Die Modelle, die ich bin sehr vertraut mit sehr eng verbunden Umsetzungsstrategien. Wenn ich diesen Bereich untersuchen wollte, weiter würde ich mit William Cook denotational Semantik für Smalltalk starten. (Smalltalk als eine Sprache ist sehr einfach, fast so einfach wie das Lambda-Kalkül, so dass es für die Modellierung komplizierter objektorientierte Sprachen eine gute Fallstudie macht.)

Wei Hu erinnert mich, dass Martin Abadi und Luca Cardelli haben gemeinsam ein ehrgeiziges Körper der Arbeit auf grundlegende Kalküle (analog dem Lambda-Kalkül) für objektorientierte Sprachen. Ich habe nicht die Arbeit gut genug verstehen, um es zu fassen, aber hier ist eine Passage aus dem Prolog ihres Buchs, die ich fühle, ist ein Zitat wert:

  

sind Verfahrenssprachen im Allgemeinen gut verstanden; ihre Konstrukte sind mittlerweile Standard, und ihre formale Untermauerung sind solide. Die grundlegenden Funktionen dieser Sprachen wurden in Formalismen destilliert, die bei der Identifizierung und erläutern Fragen der Umsetzung, statische Analyse, Semantik und Verifikation als nützlich erweisen.

     

Ein analoges Verständnis hat für die objektorientierten Sprachen noch nicht aufgetaucht. Dort auf einer Sammlung von Basiskonstrukte keine weitgehende Übereinstimmung ist und auf ihre Eigenschaften ... Diese Situation könnte sich verbessern, wenn wir ein besseres Verständnis der Grundlagen der objektorientierten Sprachen hatte.

     

... wir nehmen Objekte als primitiv und konzentrieren sich auf die inneren Regeln, dass Objekte gehorchen sollten. Wir stellen Objekt Kalküle und entwickeln um sie herum eine Theorie der Objekte. Diese Aufgabe Kalküle sind so einfach wie Funktion Kalküle, sondern Objekte direkt darstellen.

Ich hoffe, dass dieses Zitat gibt Ihnen eine Vorstellung von dem Geschmack der Arbeit.

Answer 2

Lisp basiert auf Lambda-Kalkül, und ist die Inspiration für viel von dem, was wir heute in der modernen Sprachen zu sehen.

Von-Neumann-Maschinen sind die Grundlage des modernen Computers, der ersten in Assemblersprache programmiert wurden, dann in der Formel Setzer. Dann wird die formale Sprachtheorie von kontextfreien Grammatiken-aufgetragen und liegt unter der Syntax aller modernen Sprachen.

Computability Theorie (formal Automaten) eine Hierachie von Maschinentypen, die die Hierarchie der formalen Grammatiken Parallelen zum Beispiel regelmäßige Grammatik = Finite-State-Maschine, kontextfreie Grammatik = Pushdown--Automat, kontextsensitiven -grammar = turing-Maschine.

Es ist auch der Informationstheorie, von zwei Typen, Shannon und Kolmogorov, die auf die Berechnung angewendet werden kann.

Es gibt weniger bekannte Modelle der Berechnung, wie rekursive-function-Theorie, registrieren Maschinen und Post-Maschinen.

Und nicht Prädikat-Logik in seinen verschiedenen Formen vergessen.

hinzugefügt: I diskrete Mathematik vergessen zu erwähnen - Gruppentheorie und Gittertheorie. Die Gitter sind insbesondere (IMHO) ein besonders geschicktes Konzept alle Booleschen Logik, und einige Modelle der Berechnung, wie denotational Semantik zugrunde liegen.

Answer 3

Funktionale Sprachen wie Lisp erben ihre grundlegenden Konzepte von Kirche "Lambda calculs" (Wikipedia-Artikel hier ). Grüße

Answer 4

kann ein Konzept sein Turing-Maschine .

Answer 5

Wenn Sie Sprachen studieren zu programmieren. (ZB: an einer Universität), gibt es eine ganze Menge Theorie, und nicht eine wenig Mathematik beteiligt

Beispiele sind:

• Finite State Machines
• Formal lanugages (und Context Free Grammatiken wie BNF verwendet, um sie zu beschreiben)
• Der Bau von irischen Parser Tabellen

Answer 6

Die nächste Analogie, die ich denken kann, ist Gurevich Evolving Algebras, die heutzutage sind mehr bekannt unter dem Namen von „Gurevich Abstract State Machines“ (gasm).

Ich habe lange gehofft reale Anwendungen der Theorie, um zu sehen, wenn Gurevich Microsoft verbunden, aber es scheint, dass nur sehr wenige herauskommen. Sie können die ASML-Seite auf der Microsoft-Website überprüfen.

Der gute Punkt über gasm ist, dass sie eng Pseudo-Code ähneln, auch wenn ihre semantischen formal angegeben ist. Dies bedeutet, dass Praktiker können sie leicht erreichen.

Schließlich denke ich, dass ein Teil des Erfolgs von relationalen Algebra ist, dass es die formale Grundlage der Konzepte ist, die leicht ergriffen werden kann, nämlich Tabellen, Fremdschlüssel, schließt sich, etc.

Ich denke, wir brauchen etwas Ähnliches für die dynamischen Komponenten eines Softwaresystems.

Answer 7

Es gibt viele Dimensionen Ihre Frage zu beantworten, in den Antworten Streuung.

Vor allem die Syntax einer Sprache zu beschreiben und angeben, wie ein Parser funktionieren würde, die wir verwenden kontextfreie Grammatiken.

Dann müssen Sie assign Bedeutungen der Syntax. Formale Semantik kommt in praktisch; die wichtigsten Akteure sind operationale Semantik, denotational Semantik und axiomatische Semantik.

schlechte Programme Um auszuschließen, das Typ-System hast.

Am Ende werden alle Computerprogramme können reduzieren (oder kompilieren, wenn man so will) sehr einfache Rechenmodelle. Imperative Programme sind leichter zu Turing-Maschinen abgebildet und funktionale Programme sind Lambda-Kalkül abgebildet.

Wenn Sie all diese Dinge selbst noch lernen, empfehle ich http: / /www.uni-koblenz.de/~laemmel/paradigms0910/ , da die Vorlesungen werden auf Video aufgezeichnet und online gestellt.

Answer 8

Der Geschichte Abschnitt von Wikipedias Objektorientierte Programmierung erleuchtet werden.

Answer 9

Viel wurde von der Anwendung der Mathematik Computational Theorie und Semantik erwähnt. Ich mag die Erwähnung der Art Theorie und ich bin froh, dass jemand Gittertheorie erwähnt. Hier sind nur ein paar mehr.

Niemand hat explizit Kategorie Theorie erwähnt, die zeigt, bis mehr in funktionalen Sprachen als anderswo, wie durch die Konzepte von Monaden und functors. Dann gibt es Modelltheorie und die verschiedenen Inkarnationen der Logik, dass tatsächlich in Theorembeweisern oder der Logik Sprache Prolog zeigen. Darüber hinaus gibt es mathematische Anwendungen zu Grundlagen und Probleme in Concurrent Sprachen.

Answer 10

Es gibt kein mathematisches Modell für OOP.

Relationale Algebra im mathemaical Modell für SQL. Es wurde bt E. F. Codd erstellt. C. J. Datum war auch ein reknown cientist, die mit dieser Theorie half. Die ganze Idee ist, dass Sie jede Operation als eine Set-Operation zu tun, viele Werte in der gleichen Zeit zu beeinflussen. Das bedeutet natürlich, dass der Datenbank-Engine werden hat gesagt, was raus, und die Datenbank ist in der Lage Ihre Abfrage zu optimieren.

Sowohl Codd und Datum kritisiert SQL, weil sie in der Theorie beteiligt waren, aber sie waren bei der Erstellung von SQL nicht beteiligt.

Sehen Sie dieses Video: http://player.oreilly.com/videos/9781491908853? toc_id = 182.164

Es gibt eine Menge von Informationen von Chris Datum. Ich erinnere mich, dass seit der SQL-Programmiersprache kritisiert als eine schreckliche Sprache, aber ich kann das Papier nicht finden.

Teh Kritik war im Grunde genommen, dass die meisten Sprachen erlauben Schreib Ausdrücke und assign Variablen auf diese Ausdrücke, aber SQL nicht.

Da SQL eine Art logischer Sprache ist, ich denke, man relationale Algebra in Prolog schreiben konnte. Wenigstens würden Sie eine echte Sprache haben. So könnten Sie Abfragen in Prolog schreiben. Und da in Prologs Sie viele Programme haben natürliche Sprache zu interpretieren, könnten Sie Ihre Datenbank mit natürlicher Sprache abgefragt werden.

Nach Uncle Bob, Datenbanken werden nicht benötigt werden, wenn jeder SSD hat, weil die Architektur von SSDs Mitteln, dass der Zugang so schnell wie RAM ist. So können Sie alle Ihre Objekte im RAM haben.

https://www.youtube.com/watch?feature= player_detailpage & v = t86v3N4OshQ # t = 3287

Das einzige Problem mit SQL Notwasserung ist, dass Sie ohne eine Abfragesprache für die Datenbank enden würden.

Also ja und nein, relationale Algebra als Inspiration für SQL verwendet wurde, aber SQL ist nicht wirklich eine Implementierung der relationalen Algebra.

Im Fall des Lisp, sind die Dinge anders. Die Grundidee war, dass die Funktion eval in Lisp Implementierung könnten Sie die ganze Sprache umgesetzt haben. Das ist WHE die erste Lisp Implementierung nur eine halbe Seite des Codes ist.

http://www.michaelnielsen.org / DDI / Lisp-as-the-maxwells-Gleichungen-of-Software /

ein wenig lachen: https://www.youtube.com/watch?v= hzf3hTUKk8U

Die Bedeutung der funktionalen Programmierung kommt alle zu curried Funktionen nach unten und faul Anrufen. Und nie Umgebungen und Schließungen vergessen. Und Karten reduzieren. Das alles bedeutet, dass wir in 20 Jahren Codierung in funktionalen Sprachen sein.

Nun zurück zu OOP, gibt es keine Formalisierung der OOP.

Interessanterweise ist die zweite OO Sprache jemals geschaffen wurden, Smalltalk, nur Objekte hat, hat es keine Primitive oder so etwas. Und der Schöpfer, Alan Kay, explizit Blöcke Arbeit erstellt genau wie Lisp-Funktionen.

Einige Leute behaupten, OOP vielleicht formalisiert werden könnten Kategorie Theorie, die Art der Mengenlehre ist aber mit morphisms. Ein Morphismus ist eine Struktur, die Erhaltung Karte zwischen Objekten. Also generell kann man Karte (f, Sammlung) und eine Sammlung wieder mit allen Elementen ist f angewendet.

Ich bin mir ziemlich sicher, dass Lisp, aber Lisp hat auch Funktionen, die ein Element in einer Sammlung zurückgeben, die die Struktur zerstört, so dass ein morphism eine besondere Art von Funktion ist und aus diesem Grunde würden Sie müssen reduzieren und begrenzen die Funktionen in Lisp, so dass sie alle morphisms.

https://www.youtube.com/watch?feature= player_detailpage & v = o6L6XeNdd_k # t = 250

Das Hauptproblem dabei ist, dass Funktionen existieren nicht unabhängig von Objekten in OOP, aber in der Kategorie Theorie sie tun. Sie sind daher nicht kompatibel. Sie könnten eine neue Sprache, in der die Entwicklung der Kategorientheorie zum Ausdruck bringen.

Eine experimentelle erstellt theoretische Sprache explizit versuchen OOP zu formalisieren sind Z. Z von Anforderungen Formalismus abgeleitet wird.

Ein weiterer Versuch ist Luca Cardelli Formalismus:

Java href="http://lucacardelli.name/Papers/PrimObjImp.pdf" rel="nofollow"> http://lucacardelli.name/Papers/PrimObjImp.pdf Java http://lucacardelli.name/Papers/PrimObj1stOrder.A4.pdf Java http://lucacardelli.name/Papers/PrimObjSemLICS.A4.pdf

Ich bin nicht in der Lage diese Notation zu lesen und zu verstehen. Es scheint wie eine nutzlose Übung, da soweit ich weiß, niemand dies den Weg lamba Kalkül in Lisp implementiert wurde implementiert hat.

Answer 11

Wie ich weiß, Formale Grammatiken für die Beschreibung der Syntax verwendet wird.