Abhängige Typen vs. Verfeinerungstypen

Könnte jemand den Unterschied zwischen abhängigen Typen und Verfeinerungstypen erklären? So wie ich es verstehe, enthält ein Verfeinerungstyp alle Werte eines Typs, der ein Prädikat erfüllt. Gibt es ein Merkmal abhängiger Typen, das sie unterscheidet?

Wenn es hilft, bin ich über das Liquid Haskell-Projekt auf verfeinerte Typen und über Coq und Agda auf abhängige Typen gestoßen. Trotzdem suche ich nach einer Erklärung, wie sich die Theorien unterscheiden.

terminology programming-languages type-theory functional-programming dependent-types jmite
quelle

Antworten:

Die Hauptunterschiede liegen in zwei Dimensionen - in der zugrunde liegenden Theorie und in der Art und Weise, wie sie verwendet werden können. Konzentrieren wir uns nur auf Letzteres.

Als Benutzer ist die "Logik" von Spezifikationen in LiquidHaskell- und Verfeinerungssystemen im Allgemeinen auf entscheidbare Fragmente beschränkt, so dass die Verifizierung (und Inferenz) vollständig automatisch erfolgt, dh, man benötigt keine "Beweisbegriffe" der Art, die vollständig benötigt werden abhängige Einstellung. Dies führt zu einer erheblichen Automatisierung. Vergleichen Sie beispielsweise die Einfügesortierung in LH:

http://ucsd-progsys.github.io/lh-workshop/04-case-study-insertsort.html#/ordered-lists

in Idris

https://github.com/davidfstr/idris-insertion-sort/blob/master/InsertionSort.idr

Die Automatisierung hat jedoch einen Preis. Man kann keine willkürlichen Funktionen als Spezifikationen verwenden, wie man es in der vollständig abhängigen Welt kann, was die Klasse von Eigenschaften einschränkt, die man schreiben kann.

Ein Ziel von Verfeinerungssystemen besteht daher darin , die Klasse des Spezifizierbaren zu erweitern, während das Ziel von vollständig abhängigen Systemen darin besteht, das zu automatisieren, was bewiesen werden kann. Vielleicht gibt es einen glücklichen Treffpunkt, auf dem wir das Beste aus beiden Welten bekommen können!

Ranjit Jhala
quelle

Gibt es eine Möglichkeit, auf irgendeine Weise eine mechanische Zuordnung von auf Verfeinerungstypen basierenden Spezifikationen zu auf abhängigen Typen basierenden Spezifikationen vorzunehmen? Oder wurde ein solcher "Isomorphismus" noch nicht genug untersucht?

Erik Allik

AFAIK ein solcher "Isomorphismus" ist nicht viel untersucht worden. Es gibt jedoch einige neuere Arbeiten, siehe: "Formalisierung einfacher Verfeinerungstypen in Coq" von Lehmann und Tanter (die bald erscheinen werden ... hier ist ein GH-Repo: github.com/pleiad/Refinements )

Ranjit Jhala

Wie wäre es mit pfadabhängigen Typen in Scala?

Yang Bo

@RanjitJhala Ich denke, Sie haben versehentlich Ihre Ziele im letzten Absatz falsch herum erreicht?

Noldorin

@Noldorin Ich würde sagen, Ranjit hat seinen letzten Absatz richtig verstanden. msgstr "Verfeinerungstyp ... ist auf entscheidbare Fragmente beschränkt, so dass die Verifizierung (und Inferenz) vollautomatisch erfolgt" vs "Proofbegriffe ... erforderlich in ... abhängigen [Typen]". Daher versuchen die Leute, die in Verfeinerungstypen arbeiten, zu erweitern, wie viel in einem Verfeinerungstyp spezifiziert werden kann, während sie immer noch automatisch ableitbar / überprüfbar sind, während diejenigen, die in abhängigen Typen arbeiten, versuchen, die Erzeugung von Beweisausdrücken zu automatisieren.

Raiph

$T$ $P$ $T$

{v : T ∣ P (v)}

$\{v:T \mid P(v)\}$

T

$T$ .

$\{x:T_1 \to T_2 \mid P\}$ [1]. Beachten Sie, dass vollständig abhängige Typen (wie Sigma-Typen) nicht zulässig sind.

Das in [1] beschriebene Liquid Type-System ist in der Tat entscheidend, und Liquid Haskell verwendet SMT-Löser. Für Liquid Haskell sind jedoch auch Proofbegriffe (oder Werte, wie sie in einer nicht abhängig typisierten Sprache genannt werden) erforderlich: Wenn Sie sich hinsetzen, um ein Liquid Haskell-Programm zu schreiben, schreiben Sie Ihre eigenen Funktionen, nicht nur die Typen.

[1] http://goto.ucsd.edu/~rjhala/liquid/liquid_types.pdf

Daniil
quelle

Sigma kann mit pi unter Verwendung einer kirchenähnlichen Codierung codiert werden, aber die Verfeinerungsfunktionstypen von AFAIK liquid haskell sind keine pi-Typen (abhängige Funktion).

fread2281

Abhängige Typen sind Typen, die in irgendeiner Weise von Werten abhängen. Ein klassisches Beispiel ist "die Art der Vektoren der Länge n", wobei nein Wert ist. Verfeinerungstypen bestehen, wie Sie in der Frage sagen, aus allen Werten eines bestimmten Typs, die ein bestimmtes Prädikat erfüllen. ZB die Art der positiven Zahlen. Diese Konzepte sind nicht besonders verwandt (das weiß ich). Natürlich können Sie auch vernünftigerweise abhängige Verfeinerungstypen haben, wie "Typ aller Zahlen größer als n".

Alexey Romanov
quelle

Ist einer eine Untergruppe des anderen? Verfeinerungstypen scheinen mit SMT lösbar zu sein, aber abhängige Typen erfordern Ihre eigenen Beweisbedingungen ...

jmite

"Ist einer eine Untergruppe des anderen?" Nein. Deshalb habe ich Beispiele für einen Verfeinerungstyp angegeben, der nicht abhängig ist, und für einen abhängigen Typ, der keine Verfeinerung ist.

Alexey Romanov

Können Verfeinerungstypen nicht mit Sigma codiert werden?

fread2281

Ihr Beispiel scheint Ihren Standpunkt nicht zu verdeutlichen. Die positiven Zahlen sind definiert als jene Zahlen , die größer als 0 bedeutet dies nicht , dass „die Art der positiven Zahlen“ Gerade „die Art aller Zahlen größer als 0“?

Akdom

Ist es nicht möglich, dass es ein Verfeinerungsprädikat gibt, das auch die Länge des Vektors erzwingt?

CMCDragonkai