Typy zależne a typy wyrafinowania

Czy ktoś mógłby wyjaśnić różnicę między typami zależnymi a typami wyrafinowania? W moim rozumieniu typ uściślenia zawiera wszystkie wartości typu spełniającego predykat. Czy istnieje cecha typów zależnych, która je odróżnia?

Jeśli to pomoże, natknąłem się na typy rafinowane za pośrednictwem projektu Liquid Haskell, a typy zależne za pośrednictwem Coq i Agdy. To powiedziawszy, szukam wyjaśnienia różnic między teoriami.

— jmite
źródło

Odpowiedzi:

Główne różnice dotyczą dwóch wymiarów - leżącej u podstaw teorii i sposobu ich wykorzystania. Skupmy się na tym drugim.

Jako użytkownik „logika” specyfikacji w systemach LiquidHaskell i typach udoskonalania ogranicza się do rozstrzygających fragmentów, dzięki czemu weryfikacja (i wnioskowanie) jest całkowicie automatyczna, co oznacza, że nie wymaga się „wymaganych warunków dowodowych” w rodzaju potrzebnym w całości ustawienie zależne. Prowadzi to do znacznej automatyzacji. Na przykład porównaj sortowanie według wstawiania w LH:

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

vs. w Idris

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

Jednak automatyzacja ma swoją cenę. Nie można używać dowolnych funkcji jako specyfikacji, jak można to zrobić w całkowicie zależnym świecie, który ogranicza klasę właściwości, które można napisać.

Dlatego jednym z celów systemów udoskonalania jest rozszerzenie klasy tego, co można określić, podczas gdy celem systemów w pełni zależnych jest zautomatyzowanie tego, co można udowodnić. Być może istnieje szczęśliwe miejsce spotkań, w którym możemy uzyskać to, co najlepsze z obu światów!

— Ranjit Jhala
źródło

Czy istnieje sposób, aby w jakiś sposób mechanicznie zmapować specyfikacje oparte na typie zawężenia do specyfikacji opartych na typie zależnym? A może taki „izomorfizm” nie został jeszcze wystarczająco zbadany?

— Erik Allik

AFAIK taki „izomorfizm” nie był często badany. Jest jednak kilka ostatnich prac, patrz: „Formalizowanie prostych typów uściślenia w Coq” Lehmanna i Tantera (które pojawią się wkrótce ... oto repozytorium GH: github.com/pleiad/Refinements )

— Ranjit Jhala

Co powiesz na typy zależne od ścieżki w Scali?

— Yang Bo

@RanjitJhala Myślę, że przypadkowo osiągnąłeś swoje cele w ostatnim akapicie w niewłaściwy sposób?

— Noldorin,

@Noldorin Powiedziałbym, że Ranjit poprawił swój ostatni akapit. „typ uściślenia… ograniczony do rozstrzygających fragmentów, dzięki czemu weryfikacja (i wnioskowanie) jest całkowicie automatyczna„ dowody „kontra”… potrzebne w… zależnych [typach] ”. Dlatego osoby pracujące w typach udoskonalania starają się zwiększyć, ile można określić w typie udoskonalenia, a jednocześnie są automatycznie wnioskowane / weryfikowalne, podczas gdy osoby pracujące w typach zależnych starają się zautomatyzować generowanie terminów próbnych.

— raiph

Typy uściślenia to po prostu zwykłe typy z predykatami. To znaczy, biorąc pod uwagę, że jest typowym typem, a jest pewnym predykatem na $T$ $P$ $T$

{v : T ∣ P (v)}

$\{v:T \mid P(v)\}$ jest rodzajem udoskonalenia. w tym przypadku nazywany jest typem podstawowym .

T

$T$

AFAIK, w Liquid Haskell, pozwalają również na niektóre typy funkcji zależnych , to znaczy typy [1]. Zauważ, że typy w pełni zależne (jak typy sigma) są niedozwolone. $\{x:T_1 \to T_2 \mid P\}$

Układ typu cieczy opisany w [1] jest rzeczywiście rozstrzygalny, a Liquid Haskell używa solverów SMT. Jednak Liquid Haskell wymaga również terminów próbnych (lub wartości, ponieważ są one wywoływane w języku niezależnym od typu): jeśli usiądziesz, aby napisać program Liquid Haskell, napiszesz własne funkcje, a nie tylko typy.

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

— Daniil
źródło

Sigma może być kodowana za pomocą pi przy użyciu kodowania podobnego do kościelnego, ale typy funkcji udoskonalania płynnego AFAIK haskell nie są typami pi (funkcja zależna).

— fread2281

Typy zależne to typy, które w jakikolwiek sposób zależą od wartości. Klasycznym przykładem jest „typ wektorów długości n”, gdzie njest wartością. Typy uściślenia, jak mówisz w pytaniu, składają się ze wszystkich wartości danego typu, które spełniają dany predykat. Np. Rodzaj liczb dodatnich. Te pojęcia nie są szczególnie powiązane (o których wiem). Oczywiście możesz również mieć zależne typy uściślenia, takie jak „typ wszystkich liczb większy niż n”.

— Aleksiej Romanow
źródło

Czy jeden jest podzbiorem drugiego? Typy udoskonalania wydają się być możliwe do rozwiązania za pomocą SMT, ale typy zależne wymagają twoich własnych warunków dowodu ...

— jmite

„Czy jeden jest podzbiorem drugiego?” Nie. Dlatego podałem przykłady typu udoskonalenia, który nie jest zależny, i typu zależnego, który nie jest udoskonaleniem.

— Aleksiej Romanow

czy typy udoskonalania nie mogą być kodowane za pomocą sigma?

— fread2281

Twój przykład nie wydaje się dowodzić twojej racji. Liczby dodatnie są zdefiniowane jako liczby większe niż 0. Czy to nie znaczy, że „typ liczb dodatnich” jest dokładnie „rodzajem wszystkich liczb większych niż 0”?

— akdom

Czy nie jest możliwe predykat uściślenia, który wymusza również długość wektora?

— CMCDragonkai