Unterschiede zwischen Agda und Idris

164

Ich fange an, mich mit abhängiger Programmierung zu beschäftigen, und habe festgestellt, dass die Sprachen Agda und Idris Haskell am nächsten kommen, also habe ich dort angefangen.

Meine Frage ist: Was sind die Hauptunterschiede zwischen ihnen? Sind die Typsysteme in beiden gleichermaßen ausdrucksstark? Es wäre großartig, einen umfassenden Vergleich und eine Diskussion über die Vorteile zu haben.

Ich konnte einige erkennen:

  • Idris hat Typklassen à la Haskell, während Agda Instanzargumente verwendet
  • Idris enthält eine monadische und eine anwendungsbezogene Notation
  • Beide scheinen eine Art wiederbindbare Syntax zu haben, obwohl sie nicht wirklich sicher sind, ob sie gleich sind.

Bearbeiten : Auf der Reddit-Seite dieser Frage finden Sie weitere Antworten: http://www.reddit.com/r/dependent_types/comments/q8n2q/agda_vs_idris/

Serras
quelle
1
Vielleicht möchten Sie einen Blick auf coq aswel werfen, die Syntax ist nicht eine Million Meilen von haskell entfernt und es gibt einfach zu verwendende Typklassen :)
4
Für die Aufzeichnung: Agda hat heutzutage auch monadische und anwendbare Notationen.
Gallais

Antworten:

189

Ich bin möglicherweise nicht die beste Person, um dies zu beantworten, da ich nach der Implementierung von Idris wahrscheinlich ein bisschen voreingenommen bin! Die FAQ - http://docs.idris-lang.org/en/latest/faq/faq.html - hat etwas zu sagen, aber um das ein wenig zu erweitern:

Idris wurde von Grund auf so konzipiert, dass es die Allzweckprogrammierung vor dem Beweis des Theorems unterstützt, und verfügt daher über Funktionen auf hoher Ebene wie Typklassen, Notation, Redewendungen, Listenverständnis, Überladung usw. Idris stellt die Programmierung auf hoher Ebene vor den interaktiven Beweisen. Da Idris auf einem taktikbasierten Entwickler basiert, gibt es eine Schnittstelle zu einem taktikbasierten interaktiven Theorembeweiser (ein bisschen wie Coq, aber noch nicht so fortgeschritten, zumindest noch nicht).

Eine andere Sache, die Idris gut unterstützen möchte, ist die Implementierung von Embedded DSL. Mit Haskell können Sie mit der Do-Notation einen langen Weg zurücklegen, und mit Idris auch, aber Sie können bei Bedarf auch andere Konstrukte wie Anwendung und Variablenbindung neu binden. Weitere Details hierzu finden Sie im Tutorial oder ausführliche Informationen in diesem Dokument: http://eb.host.cs.st-andrews.ac.uk/drafts/dsl-idris.pdf

Ein weiterer Unterschied besteht in der Zusammenstellung. Agda geht hauptsächlich über Haskell, Idris über C. Es gibt ein experimentelles Backend für Agda, das das gleiche Backend wie Idris über C verwendet. Ich weiß nicht, wie gut es gewartet wird. Ein primäres Ziel von Idris wird es immer sein, effizienten Code zu generieren - wir können viel besser als derzeit, aber wir arbeiten daran.

Die Typsysteme in Agda und Idris sind in vielen wichtigen Punkten ziemlich ähnlich. Ich denke, der Hauptunterschied liegt im Umgang mit Universen. Agda hat Universumspolymorphismus, Idris hat Kumulativität (und Sie können Set : Setin beiden haben, wenn Sie dies zu restriktiv finden und nichts dagegen haben, dass Ihre Beweise möglicherweise nicht stimmen).

Edwin Brady
quelle
48
Was meinst du mit "... nicht die beste Person, um zu antworten ..."? Sie sind einer der besten Antwortenden, da Sie Idris genau kennen. Jetzt brauchen wir nur noch NAD, um zu antworten, und wir haben das ganze Bild :) Vielen Dank, dass Sie sich die Zeit genommen haben, um zu antworten.
Alex R
9
Gibt es einen Ort, an dem ich mehr über Kumulativität lesen kann? Ich habe noch nie davon gehört ...
Serras
13
Adam Chlipalas Buch ist wahrscheinlich der beste Ort:
Edwin Brady
8
Das erste Kapitel des HoTT-Buches beschreibt es auch ziemlich klar, wenn auch kurz.
David Christiansen
50

Ein weiterer Unterschied zwischen Idris und Agda besteht darin, dass die Satzgleichheit von Idris heterogen ist, während die von Agda homogen ist.

Mit anderen Worten, die mutmaßliche Definition von Gleichheit in Idris wäre:

data (=) : {a, b : Type} -> a -> b -> Type where
  refl : x = x

in Agda ist es

data _≡_ {l} {A : Set l} (x : A) : A → Set a where
    refl : x ≡ x

Das l in der Agda-Definition kann ignoriert werden, da es mit dem Universumspolymorphismus zu tun hat, den Edwin in seiner Antwort erwähnt.

Der wichtige Unterschied besteht darin, dass der Gleichheitstyp in Agda zwei Elemente von A als Argumente verwendet, während er in Idris zwei Werte mit möglicherweise unterschiedlichen Typen annehmen kann .

Mit anderen Worten, in Idris kann man behaupten, dass zwei Dinge mit unterschiedlichen Typen gleich sind (auch wenn es sich um eine unbeweisbare Behauptung handelt), während in Agda die Aussage Unsinn ist.

Dies hat wichtige und weitreichende Konsequenzen für die Typentheorie, insbesondere hinsichtlich der Machbarkeit der Arbeit mit der Homotopietypentheorie. Aus diesem Grund funktioniert heterogene Gleichheit einfach nicht, da ein Axiom erforderlich ist, das nicht mit HoTT übereinstimmt. Andererseits ist es möglich, nützliche Theoreme mit heterogener Gleichheit zu formulieren, die mit homogener Gleichheit nicht einfach ausgedrückt werden können.

Das vielleicht einfachste Beispiel ist die Assoziativität der Vektorkettung. Gegebene längenindizierte Listen, sogenannte Vektoren, definiert wie folgt:

data Vect : Nat -> Type -> Type where
  Nil : Vect 0 a
  (::) : a -> Vect n a -> Vect (S n) a 

und Verkettung mit dem folgenden Typ:

(++) : Vect n a -> Vect m a -> Vect (n + m) a

wir möchten vielleicht beweisen, dass:

concatAssoc : (xs : Vect n a) -> (ys : Vect m a) -> (zs : Vect o a) ->
              xs ++ (ys ++ zs) = (xs ++ ys) ++ zs

Diese Aussage ist Unsinn unter homogener Gleichheit, weil die linke Seite der Gleichheit Typ Vect (n + (m + o)) aund die rechte Seite Typ hat Vect ((n + m) + o) a. Es ist eine absolut vernünftige Aussage mit heterogener Gleichheit.

David Christiansen
quelle
26
Sie scheinen die Agda-Standardbibliothek mehr zu kommentieren als die zugrunde liegende Theorie von Agda, aber selbst die Standardbibliothek enthält sowohl homogene als auch heterogene Gleichheit ( cse.chalmers.se/~nad/listings/lib/… ). Die ersteren werden nach Möglichkeit nur häufiger verwendet. Letzteres entspricht einer Aussage, dass die Typen gleich sind, gefolgt von einer Aussage über die Werte. In einer Welt, in der Typgleichheit seltsam ist (HoTT), ist heteq eine seltsamere Aussage.
Geheimnisvoller Dan
6
Ich verstehe nicht, wie diese Aussage unter homogener Gleichheit Unsinn ist. Es sei denn , ich irre, (n + (m + o))und ((n + m) + o)sind gleich judgmentally von Assoziativität +auf (aus dem Induktionsprinzip abgeleitet). Dementsprechend hat jede Seite der Gleichheit den gleichen Typ. Der Unterschied zwischen den Arten der Gleichheit ist wichtig, aber ich sehe nicht, wie dies ein Beispiel dafür ist.
5
@Abhishek ist Urteilsgleichheit nicht dasselbe wie Definitionsgleichheit? Ich denke, Sie wollen damit sagen, dass (n + (m + o)) und ((n + m) + o) aussagekräftig, aber nicht definitiv / wertend gleich sind.
Tom Crockett
3
richtig. Ich meinte Satzgleichheit, als ich Urteilsgleichheit sagte. Es tut uns leid. Hier ist der korrigierte Kommentar: (n + (m + o)) und ((n + m) + o) sind aussagekräftig, aber definitiv nicht gleich. Wenn Sie a: A haben, gilt a: B nur, wenn A und B definitiv gleiche Typen sind. Für die Entscheidbarkeit der Typprüfung muss die definitive Gleichheit entscheidbar sein. In Theorien des Extensionstyps fällt die definitive Gleichheit mit der Aussagengleichheit zusammen, und daher ist die Typprüfung nicht zu entscheiden. In Coq umfasst die definitive Gleichheit nur Berechnung, Alpha-Gleichheit und definitive Entfaltung.
Abhishek Anand