Agda

Agda ist ein abhängig eingegeben funktionale Programmiersprache ursprünglich von Ulf Norell an der Chalmers University of Technology mit der Umsetzung in seiner Doktorarbeit beschrieben entwickelt. Die aktuelle Version von Agda wurde ursprünglich bekannt als Agda Agda 2. Der ursprüngliche System wurde an der Chalmers von Catarina Coquand im Jahr 1999 entwickelt die aktuelle Version ist eine komplette Neufassung, die eine neue Sprache, die einen Namen und Tradition teilt die berücksichtigt werden sollten.

Agda, im Gegensatz zu Coq, hat keine Unterstützung für Taktik und Nachweise sind in der funktionalen Programmierung Stil geschrieben. Die Sprache hat gewöhnliche Programmierkonstrukte wie Datentypen, Pattern-Matching, Datensätzen, lassen Sie Ausdrücke und Modulen und eine Haskell-ähnliche Syntax. Das System verfügt über einen Emacs-Schnittstelle, kann aber auch im Batch-Modus über die Befehlszeile ausgeführt werden.

Agda auf Luos UTT basierend eine Art Theorie ähnlich wie Martin Löf Typentheorie.

Eigenschaften

Induktive Typen

Die wichtigste Art der Definition Datentypen in Agda ist über induktive Datentypen, die ähnlich wie algebraische Datentypen in nicht abhängig typisierte Programmiersprachen.

Hier ist eine Definition von Peano Zahlen in Agda:

Grundsätzlich bedeutet dies, dass es zwei Möglichkeiten, eine natürliche Zahl zu konstruieren. Zero ist eine natürliche Zahl ist, und wenn n eine natürliche Zahl ist, dann suc n ist eine natürliche Zahl zu.

Hier ist eine Definition von weniger als oder gleich Verhältnis:

Der erste Konstruktor können wir feststellen, daß Null von weniger als oder gleich irgendeiner Zahl. Der zweite Konstruktor heißt es, dass, wenn n & lt; = m dann & lt; = suc m.

Abhängig eingegeben Mustervergleich

In Kern-Theorie werden Induktion und Rekursion Prinzipien verwendet werden, um Sätze über induktive Typen beweisen. In agda wird abhängig eingegeben Mustererkennung stattdessen verwendet. Beispielsweise können natürliche Zahl ist zusätzlich wie folgt definiert werden:

Diese Art des Schreibens rekursive Funktionen / induktive Beweise ist natürlicher, als die Anwendung roher Induktionsprinzipien. In agda ist abhängig eingegeben Mustervergleich ein primitiver der Sprache, wird die Kernsprache keine Induktions / Rekursion Prinzipien, die Mustererkennung übersetzt.

Metavariablen

Eine der Besonderheiten des agda, wenn sie mit anderen ähnlichen Systemen wie coq verglichen wird, ist starke Abhängigkeit von Metavariablen für die Programmkonstruktion. Zum Beispiel können wir Funktion wie diese zu schreiben in agda:

? Hier ist ein Metavariable. Bei der Interaktion mit dem System in Emacs-Modus, wird der Benutzer erwartet Typ zeigen und ihnen erlauben, die Meta-Variable zu suchen, dh, es mit ausführlicheren Code ersetzen. Mit dieser Funktion können inkrementale Programm Konstruktion in ähnlicher Weise wie die Taktik der Grundlage Beweis Hilfsmittel wie coq.

Proof Automation

Programmierung in reinem Typentheorie erfordert eine Menge langweilige und sich wiederholende Beweise und Agda keine Unterstützung für die Taktik. Agda hat die Unterstützung für Automatisierung über Reflexion. Die Reflexionsmechanismus erlaubt es, unquote Fragmente von Programmen in / aus abstrakten Syntaxbaum zitieren /. Die Art der Reflexion verwendet wird, ist ähnlich der Art Template Haskell funktioniert.

Ein weiterer Mechanismus für den Nachweis Automatisierung ist der Beweis, Suchaktion in der Emacs-Modus. Es renumerates möglichen Beweis Begriffe, und wenn man die Bedingungen der Spezifikation entspricht, wird es in der Meta-Variable in dem die Aktion aufgerufen wird genommen werden. Diese Aktion übernimmt Hinweise, dh die Sätze und aus denen Module können verwendet werden, ob die Aktion Mustervergleich usw. verwenden

Kündigung Checking

Agda Insgesamt Sprache, dh jedes Programm muss zu kündigen. Ohne diese Funktion wird die Logik hinter der Sprache widersprüchlich, und es wird möglich, beliebige Tatsachen beweisen. Als Ergebnis wird die Sprache nicht Turing vollständig. Für eine Kündigung verwendet Überprüfung agda Annäherung des Foetus Abschlussprüfung.

Standardbibliothek

Agda verfügt über eine umfangreiche de facto Standard-Bibliothek, die viele nützliche Definitionen und Sätze über grundlegende Datenstrukturen, wie natürlichen Zahlen, Listen und Vektoren umfasst. Die Bibliothek ist in der Betaphase und wird aktiv weiterentwickelt.

Unicode

Eine der bemerkenswertesten Eigenschaften von Agda ist eine starke Abhängigkeit von Unicode in Programm-Quellcode. Die Standard-Emacs-Modus verwendet Shortcuts für die Eingabe, wie "\ Sigma" für Σ.

Backends

Es gibt drei Compiler-Backends, Malonzo die Haskell, einen JavaScript-Backend-Ziele und eine epische Backend.

Referenzen

  • ^ Ulf Norell. Auf dem Weg zu einem praktischen Programmiersprache basierend auf abhängige Typentheorie. Dissertation. Chalmers University of Technology, 2007 id = "cite_note-2"> ^ "Agda: An Interactive Proof-Editor". Abgerufen 2014.10.20.
  • ^ Coquand, Catarina; Synek, Dan. "Ein Emacs-Schnittstelle für Art gerichteten Unterstützung konstruieren Beweise und Programme". Europäische Gemeinsame Konferenzen über Theorie und Praxis der Software 2005 fehlt in Liste der Künstler
  • ^ Luo, Zhaohui. Berechnung und Begründung: eine Art Theorie für Informatik. Oxford University Press, Inc., 1994.
  • ^ "Nat von Agda Standard-Bibliothek". Abgerufen 2014.07.20.
  • ^ Van der Walt, Paul, und Wouter Swierstra. "Engineering Beweis durch Reflexion in Agda." In Umsetzung und Anwendung der funktionalen Sprachen, pp. 157-173. Springer Berlin Heidelberg, 2013. id = "cite_note-7"> ^ Kokke, Pepijn und Wouter Swierstra. "Auto in Agda." id = "cite_note-8"> ^ Abel, Andreas. "Fötus-Abschlussprüfer für einfache funktionale Programme." Programmieren Lab Report 474. http://www.tcs.informatik.uni-muenchen.de/~abel/foetus.pdf
  0   0
Vorherige Artikel Denver Fire Department

Kommentare - 0

Keine Kommentare

Fügen Sie einen Kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Zeichen übrig: 3000
captcha