Dlaczego nie zostać wpisanym zależnie?

161

Widziałem kilka źródeł powtarzających opinię, że „Haskell stopniowo staje się językiem opartym na typach zależnych”. Wydaje się, że implikacja jest taka, że ​​przy coraz większej liczbie rozszerzeń języka Haskell dryfuje w tym ogólnym kierunku, ale jeszcze go tam nie ma.

Zasadniczo chciałbym wiedzieć o dwóch rzeczach. Po pierwsze, po prostu, co właściwie oznacza „bycie językiem o typie zależnym” ? (Miejmy nadzieję, że nie jest to zbyt techniczne).

Drugie pytanie brzmi ... jaka jest wada? Chodzi mi o to, że ludzie wiedzą, że zmierzamy w tę stronę, więc musi to mieć jakąś przewagę. A jednak jeszcze nas tam nie ma, więc musi istnieć jakiś minus, który powstrzymuje ludzi przed pójściem na całość. Mam wrażenie, że problemem jest gwałtowny wzrost złożoności. Ale nie bardzo rozumiem, czym jest pisanie zależne, nie wiem na pewno.

Wiem tylko , że za każdym razem, gdy zaczynam czytać o zależnym typie języka programowania, tekst jest całkowicie niezrozumiały ... Prawdopodobnie w tym tkwi problem. (?)

MathematicalOrchid
źródło
10
Mówiąc prościej, możesz pisać typy zależne od terminów (obliczeń). To wystarczy, aby określić typy dotyczące każdego aspektu programu, a zatem oznacza, że ​​system typów jest w stanie określić pełną specyfikację programu. Problem polega na tym, że ponieważ typy zależą od obliczeń, sprawdzanie typów jest znacznie trudniejsze (generalnie niemożliwe).
GManNickG
27
@GManNickG: Sprawdzanie typu jest całkowicie możliwe. Rodzaj wnioskowania , to inna sprawa, ale potem znowu różne rozszerzenia GHC mają dawno porzucił ten pomysł, że powinno być możliwe, aby wyprowadzić wszystkie typy.
CA McCann
7
Jeśli dobrze rozumiem, wadą jest to, że poprawne pisanie zależne (np. W sposób użyteczny i dobrze uzasadniony) jest trudne , a nie wiemy jeszcze jak.
nadchodząca burza
1
@CAMcCann: Tak, mój błąd.
GManNickG
4
Nie wydaje mi się, by ktokolwiek wskazał na jedną wielką pragmatyczną wadę: pisanie dowodów na to, że cały kod jest poprawny, jest szalenie żmudne. Ponieważ nie możesz automatycznie przeprowadzać wnioskowania o typie (co odpowiada dowodzeniu twierdzeń w logice „hella potężnej”), musisz napisać adnotacje do swojego programu w postaci dowodów. To oczywiście staje się irytujące i trudne do wykonania po pewnym czasie, szczególnie w przypadku bardziej wyszukanej magii monadycznej, którą ludzie zwykle używają w Haskell. Najbliżej nas w dzisiejszych czasach są języki, które w większości robią to za nas lub dają nam dobry zestaw prymitywów.
Kristopher Micinski,

Odpowiedzi:

21

Typowanie zależne to tak naprawdę tylko ujednolicenie wartości i poziomów typów, więc możesz parametryzować wartości na typach (jest to już możliwe w przypadku klas typów i parametrycznego polimorfizmu w Haskell) i możesz parametryzować typy na wartościach (ściśle mówiąc, nie jest to możliwe jeszcze w Haskell , chociaż DataKindsbardzo się zbliża).

Edycja: Najwyraźniej od tego momentu myliłem się (patrz komentarz @ pigworker). Resztę tego zachowam jako zapis mitów, którymi byłem karmiony. : P


Problem z przejściem na w pełni zależne typowanie, z tego, co słyszałem, polega na tym, że złamałoby to ograniczenie fazy między typem a poziomami wartości, co pozwala skompilować Haskell do wydajnego kodu maszynowego z wymazanymi typami. Przy naszym obecnym poziomie technologii język zależnie typizowany musi w pewnym momencie przejść przez interpreter (albo natychmiast, albo po skompilowaniu do zależnie wpisanego kodu bajtowego lub podobnego).

Niekoniecznie jest to fundamentalne ograniczenie, ale osobiście nie jestem świadomy jakichkolwiek bieżących badań, które wyglądają obiecująco pod tym względem, ale które jeszcze nie dotarły do ​​GHC. Jeśli ktokolwiek wie więcej, byłbym szczęśliwy, gdyby został poprawiony.

Płomień Pthariena
źródło
46
To, co mówisz, jest prawie całkowicie fałszywe. Nie winię cię całkowicie: powtarza standardowe mity jako fakt. Język Edwina Brady'ego, Idris, wykonuje wymazywanie typów (ponieważ żadne zachowanie w czasie wykonywania nie zależy od typów) i generuje dość standardowe kodowanie superkombinatora z podniesioną wartością lambda, z którego kod jest generowany przy użyciu standardowych technik G-machine.
pigworker
3
Na marginesie, ktoś niedawno wskazał mi ten artykuł . Z tego, co wiem, spowodowałoby to, że Haskell byłby zależnym rodzajem (tj. Język na poziomie typu byłby zależny od typu), co jest tak bliskie, jak widzę, że otrzymamy to w najbliższym czasie.
Ptharien's Flame
8
Tak, ten papier w większości pokazuje, jak uzależnić typy od rzeczy na poziomie typu (i wyeliminować rozróżnienie typu / rodzaju). Prawdopodobnym następstwem, już omawianym, jest zezwolenie na rzeczywiste zależne typy funkcji, ale ograniczenie ich argumentów do fragmentu języka, który może istnieć zarówno w warstwie wartości, jak i typu (teraz nietrywialne dzięki promocji typu danych). To wyeliminowałoby potrzebę konstrukcji singletona, która obecnie sprawia, że ​​„udawanie” jest bardziej skomplikowane niż pożądane. Coraz bardziej zbliżamy się do rzeczywistości.
pigworker
13
Istnieje wiele pragmatycznych pytań, dotyczących modernizacji typów zależnych w Haskell. Kiedy już mamy tę ograniczoną formę zależnej przestrzeni funkcyjnej, wciąż stajemy przed pytaniem, jak powiększyć fragment języka wartości, który jest dozwolony na poziomie typów, i jaka powinna być jego teoria równań (tak jak chcemy 2 + 2 do być 4 i takie). Istnieje wiele kłopotliwych problemów (np. Na dole), które od podstaw projektują języki zależne od typów.
pigworker
2
@pigworker Czy istnieje czysty podzbiór Haskella, który jest całkowity? Jeśli tak, to czy nie moglibyśmy po prostu użyć tego dla „fragmentu języka, który może istnieć zarówno w warstwie wartości, jak i w warstwie typu”? Jeśli nie, co należałoby zrobić, aby go wyprodukować?
Ptharien's Flame
223

Zależnie wpisany Haskell, teraz?

Haskell jest w niewielkim stopniu językiem zależnym od typografii. Istnieje pojęcie danych na poziomie typu, teraz dzięki bardziej rozsądnemu typowaniu DataKinds, i są pewne środki ( GADTs), aby nadać reprezentację danych na poziomie typu w czasie wykonywania. W związku z tym wartości elementów czasu wykonywania skutecznie pojawiają się w typach , co oznacza, że ​​język jest wpisywany zależnie.

Proste typy danych są promowane do poziomu rodzaju, dzięki czemu wartości, które zawierają, mogą być używane w typach. Stąd archetypowy przykład

data Nat = Z | S Nat

data Vec :: Nat -> * -> * where
  VNil   :: Vec Z x
  VCons  :: x -> Vec n x -> Vec (S n) x

staje się możliwe, a wraz z nim definicje takie jak

vApply :: Vec n (s -> t) -> Vec n s -> Vec n t
vApply VNil         VNil         = VNil
vApply (VCons f fs) (VCons s ss) = VCons (f s) (vApply fs ss)

co jest miłe. Zauważ, że długość njest czysto statyczną rzeczą w tej funkcji, zapewniając, że wektory wejściowe i wyjściowe mają tę samą długość, nawet jeśli ta długość nie odgrywa żadnej roli w wykonaniu vApply. Natomiast to o wiele trudniejsze (czyli niemożliwe) do realizacji funkcji, które sprawia, że nkopie dana x(co byłoby puredo vApply„s <*>)

vReplicate :: x -> Vec n x

ponieważ ważne jest, aby wiedzieć, ile kopii wykonać w czasie wykonywania. Wpisz singletony.

data Natty :: Nat -> * where
  Zy :: Natty Z
  Sy :: Natty n -> Natty (S n)

Dla dowolnego typu promowanego możemy zbudować rodzinę singletonów, indeksowaną na typie promowanym, zamieszkałą przez duplikaty jej wartości w czasie wykonywania. Natty njest typem kopii wykonawczych poziomu typu n :: Nat. Teraz możemy pisać

vReplicate :: Natty n -> x -> Vec n x
vReplicate Zy     x = VNil
vReplicate (Sy n) x = VCons x (vReplicate n x)

Mamy więc wartość na poziomie typu połączoną z wartością czasu wykonywania: inspekcja kopii wykonawczej poprawia statyczną wiedzę o wartości na poziomie typu. Mimo że terminy i typy są rozdzielone, możemy pracować w sposób zależny od typu, używając konstrukcji singleton jako rodzaju żywicy epoksydowej, tworząc wiązania między fazami. To daleko od dopuszczenia dowolnych wyrażeń w czasie wykonywania w typach, ale to nie jest nic.

Co jest paskudne? Czego brakuje?

Naciskajmy na tę technologię i zobaczmy, co zaczyna się chwiać. Można by pomyśleć, że singletonami powinny być zarządzalne w nieco bardziej niejawny sposób

class Nattily (n :: Nat) where
  natty :: Natty n
instance Nattily Z where
  natty = Zy
instance Nattily n => Nattily (S n) where
  natty = Sy natty

pozwalając nam pisać, powiedzmy,

instance Nattily n => Applicative (Vec n) where
  pure = vReplicate natty
  (<*>) = vApply

To działa, ale teraz oznacza, że ​​nasz oryginalny Nattyp zrodził trzy kopie: rodzaj, rodzina singletonów i klasa singleton. Mamy dość niezgrabny proces wymiany jawnych Natty nwartości i Nattily nsłowników. Co więcej, Nattynie jest Nat: mamy pewien rodzaj zależności od wartości czasu wykonywania, ale nie takiego, o jakim myśleliśmy na początku. Żaden w pełni zależnie typowany język nie sprawia, że ​​typy zależne są tak skomplikowane!

Tymczasem, choć Natmożna awansować, Vecnie można. Nie możesz indeksować według typu indeksowanego. Pełne języków zależnie wpisywanych na maszynie nie narzucają żadnych ograniczeń, aw mojej karierze jako popisywanie się zależnie od maszynistki nauczyłem się uwzględniać przykłady indeksowania dwuwarstwowego w moich przemówieniach, aby uczyć ludzi, którzy zrobili indeksowanie jednowarstwowe Trudno, ale można nie oczekiwać, że złożę się jak domek z kart. Jaki jest problem? Równość. GADT działają, tłumacząc ograniczenia, które uzyskujesz niejawnie, gdy konstruktorowi nadasz określony typ zwracany na jawne wymagania równań. Lubię to.

data Vec (n :: Nat) (x :: *)
  = n ~ Z => VNil
  | forall m. n ~ S m => VCons x (Vec m x)

W każdym z naszych dwóch równań obie strony mają życzliwość Nat.

Teraz spróbuj tego samego tłumaczenia dla czegoś indeksowanego na wektorach.

data InVec :: x -> Vec n x -> * where
  Here :: InVec z (VCons z zs)
  After :: InVec z ys -> InVec z (VCons y ys)

staje się

data InVec (a :: x) (as :: Vec n x)
  = forall m z (zs :: Vec x m). (n ~ S m, as ~ VCons z zs) => Here
  | forall m y z (ys :: Vec x m). (n ~ S m, as ~ VCons y ys) => After (InVec z ys)

a teraz tworzymy ograniczenia równościowe pomiędzy as :: Vec n xi VCons z zs :: Vec (S m) xgdzie obie strony mają różne składniowo (ale dające się udowodnić równe) rodzaje. Rdzeń GHC nie jest obecnie wyposażony w taką koncepcję!

Czego jeszcze brakuje? Cóż, większości Haskell brakuje na poziomie typu. Język terminów, które możesz promować, zawiera tylko zmienne i konstruktory spoza GADT. Gdy już je masz, type familymaszyna pozwala na pisanie programów na poziomie typu: niektóre z nich mogą być całkiem podobne do funkcji, które rozważałbyś napisanie na poziomie terminu (np. Wyposażenie Natw dodawanie, więc możesz podać dobry typ do dołączenia Vec) , ale to tylko zbieg okoliczności!

Inną rzeczą, której brakuje w praktyce, jest biblioteka, która wykorzystuje nasze nowe możliwości do indeksowania typów według wartości. Co robić Functor i czym Monadsię stać w tym nowym, wspaniałym świecie? Myślę o tym, ale wciąż jest dużo do zrobienia.

Uruchamianie programów na poziomie typu

Haskell, podobnie jak większość języków programowania o typach zależnych, ma dwie operacyjne semantyki. Istnieje sposób, w jaki system czasu wykonywania uruchamia programy (tylko wyrażenia zamknięte, po usunięciu typu, wysoce zoptymalizowany), a także sposób, w jaki narzędzie do sprawdzania typów uruchamia programy (rodziny typów, „Prolog klasy typów” z otwartymi wyrażeniami). Dla Haskella normalnie nie pomieszasz tych dwóch, ponieważ wykonywane programy są w różnych językach. Języki z typami zależnymi mają oddzielne modele wykonawcze i statyczne dla tego samego języka programów, ale nie martw się, model czasu wykonywania nadal pozwala na wymazywanie typów i, w rzeczy samej , wymazywanie dowodów: to właśnie jest ekstrakcja Coqamechanizm daje; przynajmniej to robi kompilator Edwina Brady'ego (chociaż Edwin usuwa niepotrzebnie zduplikowane wartości, a także typy i dowody). Rozróżnienie faz może już nie być rozróżnieniem na kategorię syntaktyczną , ale jest żywe i ma się dobrze.

Języki zależnie wpisane na maszynie, będąc całkowitymi, pozwalają sprawdzaczowi typów na uruchamianie programów bez strachu przed czymś gorszym niż długie oczekiwanie. W miarę jak Haskell staje się coraz bardziej zależny, stajemy przed pytaniem, jaki powinien być jego statyczny model wykonania? Jednym podejściem mogłoby być ograniczenie wykonywania statycznego do funkcji całkowitych, co dałoby nam taką samą swobodę działania, ale mogłoby zmusić nas do rozróżnienia (przynajmniej w przypadku kodu na poziomie typu) między danymi a kodowanymi, abyśmy mogli stwierdzić, czy należy wymuszać wypowiedzenie lub produktywność. Ale to nie jedyne podejście. Możemy wybrać znacznie słabszy model wykonania, który niechętnie uruchamia programy, kosztem wykonywania mniejszej liczby równań tylko przez obliczenia. W efekcie to właśnie robi GHC. Zasady typowania dla rdzenia GHC nie wspominają o uruchamianiu programy, ale tylko do sprawdzania dowodów dla równań. Podczas tłumaczenia do rdzenia, solver ograniczeń GHC próbuje uruchomić programy na poziomie typu, generując mały srebrzysty ślad dowodu, że dane wyrażenie jest równe swojej normalnej formie. Ta metoda generowania dowodów jest trochę nieprzewidywalna i nieuchronnie niekompletna: zwalcza na przykład przerażająco wyglądającą rekurencję i jest to prawdopodobnie rozsądne. Jedną rzeczą, o którą nie musimy się martwić, jest wykonywanie IO obliczeń w narzędziu do sprawdzania typów: pamiętaj, że sprawdzanie typów nie musi nadawać launchMissilestego samego znaczenia, co system wykonawczy!

Kultura Hindley-Milner

System typu Hindley-Milner osiąga naprawdę niesamowity zbieg okoliczności czterech odrębnych rozróżnień, z niefortunnym kulturowym efektem ubocznym, że wielu ludzi nie widzi różnicy między różnicami i zakłada, że ​​zbieg okoliczności jest nieunikniony! O czym ja mówię?

  • terminy a typy
  • wyraźnie napisane rzeczy vs niejawnie pisanych rzeczy
  • obecność w czasie wykonywania vs wymazywanie przed uruchomieniem
  • niezależna abstrakcja a kwantyfikacja zależna

Jesteśmy przyzwyczajeni do pisania terminów i pozostawiania typów do wywnioskowania ... a następnie wymazania. Jesteśmy przyzwyczajeni do ilościowego określania zmiennych typu z odpowiednią abstrakcją typu i aplikacją działającą cicho i statycznie.

Nie musisz zbytnio oddalać się od waniliowej Hindley-Milner, zanim te rozróżnienia przestaną być wyrównane, a to nie jest złe . Na początek możemy mieć ciekawsze typy, jeśli zechcemy je napisać w kilku miejscach. W międzyczasie nie musimy pisać słowników klas typów, gdy używamy przeciążonych funkcji, ale te słowniki są z pewnością obecne (lub wbudowane) w czasie wykonywania. W językach z typami zależnymi spodziewamy się wymazania więcej niż tylko typów w czasie wykonywania, ale (tak jak w przypadku klas typów), że niektóre niejawnie wywnioskowane wartości nie zostaną usunięte. Np. vReplicateArgument numeryczny często można wywnioskować z typu żądanego wektora, ale nadal musimy go znać w czasie wykonywania.

Które wybory językowe powinniśmy przeanalizować, ponieważ te zbiegi okoliczności już nie istnieją? Np. Czy to prawda, że ​​Haskell nie daje możliwości forall x. tjawnego utworzenia instancji kwantyfikatora? Jeśli kontroler typu nie może odgadnąć xprzez ujednolicenie t, nie mamy innego sposobu, aby powiedzieć, co xmusi być.

Szerzej, nie możemy traktować „wnioskowania o typie” jako monolitycznej koncepcji, z której mamy wszystko albo nic. Na początek musimy oddzielić aspekt „uogólnienia” (reguła Milnera „pozwól”), który polega w dużej mierze na ograniczaniu istniejących typów, aby zapewnić, że głupia maszyna może je odgadnąć, od aspektu „specjalizacji” (zasada Milnera „var „reguła”), która jest tak samo skuteczna, jak narzędzie do rozwiązywania ograniczeń. Możemy spodziewać się, że typy najwyższego poziomu będą trudniejsze do wywnioskowania, ale informacje o typie wewnętrznym pozostaną dość łatwe do rozpowszechnienia.

Dalsze kroki dla Haskella

Widzimy, że typy i poziomy rodzaju rosną do siebie bardzo podobnie (i mają już wewnętrzną reprezentację w GHC). Równie dobrze możemy je połączyć. Byłoby fajnie * :: *, gdybyśmy mogli: straciliśmy logiczną solidność dawno temu, kiedy pozwoliliśmy na dno, ale solidność typu jest zwykle słabszym wymaganiem. Musimy sprawdzić. Jeśli musimy mieć różne poziomy typu, rodzaju itp., Możemy przynajmniej upewnić się, że wszystko na poziomie typu i wyższym zawsze może być promowane. Byłoby wspaniale po prostu ponownie wykorzystać polimorfizm, który już mamy dla typów, zamiast ponownie wymyślać polimorfizm na poziomie rodzaju.

Powinniśmy uprościć i uogólnić obecny system ograniczeń, dopuszczając niejednorodne równania, w a ~ bktórych rodzaje ai bnie są syntaktycznie identyczne (ale można udowodnić, że są równe). To stara technika (w mojej pracy magisterskiej z ubiegłego wieku), która znacznie ułatwia radzenie sobie z uzależnieniem. Moglibyśmy wyrazić ograniczenia w wyrażeniach w GADT, a tym samym złagodzić ograniczenia dotyczące tego, co można promować.

Powinniśmy wyeliminować potrzebę budowy singleton przez wprowadzenie zależnego od typu funkcyjnego pi x :: s -> t. Funkcja z takim typem może być jawnie zastosowana do dowolnego wyrażenia typu, sktóre znajduje się na przecięciu języka typu i terminów (a więc zmienne, konstruktory, a więcej w przyszłości). Odpowiednia lambda i aplikacja nie zostałyby usunięte w czasie wykonywania, więc moglibyśmy pisać

vReplicate :: pi n :: Nat -> x -> Vec n x
vReplicate Z     x = VNil
vReplicate (S n) x = VCons x (vReplicate n x)

bez wymiany Natprzez Natty. Domena pimoże być dowolnego typu, który można promować, więc jeśli można promować GADT, możemy pisać zależne sekwencje kwantyfikatorów (lub „teleskopy”, jak je nazwał de Briuijn)

pi n :: Nat -> pi xs :: Vec n x -> ...

na dowolną długość, jakiej potrzebujemy.

Celem tych kroków jest wyeliminowanie złożoności poprzez bezpośrednią pracę z bardziej ogólnymi narzędziami, zamiast zadowalać się słabymi narzędziami i niezgrabnym kodowaniem. Obecne częściowe poparcie sprawia, że ​​korzyści wynikające z zależnych typów Haskella są droższe, niż powinny.

Zbyt trudne?

Typy zależne denerwują wielu ludzi. Denerwują mnie, ale lubię się denerwować, a przynajmniej trudno mi się nie denerwować. Ale to nie pomaga, że ​​wokół tematu jest taka mgła ignorancji. Po części wynika to z faktu, że wszyscy wciąż musimy się wiele nauczyć. Wiadomo jednak, że zwolennicy mniej radykalnych podejść budzą strach przed typami zależnymi, nie zawsze jednak upewniając się, że fakty są całkowicie zgodne z nimi. Nie będę wymieniać imion. Te „nierozstrzygalne sprawdzanie typów”, „niekompletne Turinga”, „brak rozróżnienia fazowego”, „brak wymazywania typu”, „wszędzie dowody” itd., Utrzymują się, mimo że są śmieciami.

Z pewnością nie jest tak, że programy napisane zależnie muszą zawsze być poprawne. Można poprawić podstawową higienę swoich programów, wymuszając dodatkowe niezmienniki w typach bez konieczności przechodzenia do pełnej specyfikacji. Małe kroki w tym kierunku dość często skutkują znacznie silniejszymi gwarancjami z niewielkimi lub żadnymi dodatkowymi zobowiązaniami dowodowymi. Nie jest prawdą, że programy napisane na typie zależnym są nieuchronnie pełne dowodów, w istocie zazwyczaj biorę obecność jakichkolwiek dowodów w moim kodzie jako wskazówkę do zakwestionowania moich definicji .

Podobnie jak w przypadku każdego wzrostu artykulacji, możemy swobodnie mówić zarówno ohydne, jak i nowe rzeczy. Na przykład istnieje wiele kiepskich sposobów definiowania drzew wyszukiwania binarnego, ale to nie znaczy, że nie jest to dobry sposób . Ważne jest, aby nie zakładać, że złych doświadczeń nie da się poprawić, nawet jeśli przyznanie się do tego wypacza ego. Projektowanie definicji zależnych to nowa umiejętność, która wymaga uczenia się, a bycie programistą Haskell nie czyni cię automatycznie ekspertem! A nawet jeśli niektóre programy są obrzydliwe, dlaczego miałbyś odmawiać innym wolności do bycia sprawiedliwym?

Dlaczego nadal zawracać sobie głowę Haskellem?

Naprawdę lubię typy zależne, ale większość moich projektów hakerskich wciąż jest w Haskell. Czemu? Haskell ma klasy typów. Haskell ma przydatne biblioteki. Haskell ma praktyczne (choć dalekie od ideału) podejście do programowania z efektami. Haskell ma kompilator siły przemysłowej. Języki z typami zależnymi są na znacznie wcześniejszym etapie rozwoju społeczności i infrastruktury, ale dojdziemy do tego z prawdziwą zmianą pokoleniową w tym, co jest możliwe, np. Za pomocą metaprogramowania i typów generycznych. Ale wystarczy rozejrzeć się wokół tego, co ludzie robią w wyniku kroków Haskella w kierunku typów zależnych, aby zobaczyć, że można uzyskać wiele korzyści, popychając również obecną generację języków do przodu.

świniarz
źródło
6
Naprawdę nie obchodzą mnie jeszcze rzeczy DataKinds. Głównie dlatego, że chcę zrobić coś takiego: fmap read getLine >>= \n -> vReplicate n 0. Jak zauważyłeś, Nattyjest daleko od tego. Ponadto vReplicate powinno dać się przetłumaczyć na rzeczywistą tablicę pamięci, na przykład newtype SVector n x = SVector (Data.Vector.Vector x), gdzie nma rodzaj Nat(lub podobny). Być może kolejny punkt demonstracyjny „popisywania się zależnie od typu”?
John L
7
Czy możesz powiedzieć, co masz na myśli, aby idealnie potraktować programowanie z efektami?
Steven Shaw
6
Dzięki za wspaniały opis. Chciałbym zobaczyć kilka przykładów zależnie wpisanego kodu, w którym niektóre dane pochodzą spoza programu (np. Odczytane z pliku), aby poczuć, jak promowanie wartości do typów wyglądałoby w takim ustawieniu. Mam wrażenie, że wszystkie przykłady obejmują wektory (zaimplementowane jako listy) o statycznie znanych rozmiarach.
tibbe
4
@pigworker Traktujesz „brak rozróżnienia fazowego” jako mit (inne, z którymi się zgadzam, to mity). Ale nie zdemontowałeś tego w artykułach i wykładach, które widziałem, a tymczasem inna osoba, którą szanuję, mówi mi: „Teoria typów zależnych różni się od typowego kompilatora, ponieważ nie możemy w znaczący sposób oddzielić faz sprawdzania typu, kompilacji i wykonywania. " (patrz najnowszy post Andreja z 8 listopada 2012 r.) Z mojego doświadczenia wynika, że ​​„udając” czasami przynajmniej zacieramy rozróżnienie fazowe, chociaż nie musimy go usuwać. Czy mógłbyś rozwinąć tę kwestię, jeśli nie tutaj, to gdzie indziej?
sclv
4
@sclv Moja praca nie była specjalnie ukierunkowana na mit „braku rozróżnienia fazowego”, ale inni tak. Polecam odrzucenie „Phase Distinctions in the Compilation of Epigram” Jamesa McKinny i Edwina Brady'ego jako dobre miejsce na rozpoczęcie. Ale zobacz także dużo starsze prace nad wyodrębnianiem programów w Coq. Otwarta ocena dokonywana przez typechecker jest całkowicie niezależna od wykonania poprzez ekstrakcję do ML i jest jasne, że ekstrakcja usuwa typy i dowody.
Pigworker
20

John to kolejne błędne przekonanie dotyczące typów zależnych: nie działają one, gdy dane są dostępne tylko w czasie wykonywania. Oto jak możesz zrobić przykład getLine:

data Some :: (k -> *) -> * where
  Like :: p x -> Some p

fromInt :: Int -> Some Natty
fromInt 0 = Like Zy
fromInt n = case fromInt (n - 1) of
  Like n -> Like (Sy n)

withZeroes :: (forall n. Vec n Int -> IO a) -> IO a
withZeroes k = do
  Like n <- fmap (fromInt . read) getLine
  k (vReplicate n 0)

*Main> withZeroes print
5
VCons 0 (VCons 0 (VCons 0 (VCons 0 (VCons 0 VNil))))

Edycja: Hm, to miał być komentarz do odpowiedzi świniarza. Wyraźnie zawodzę w SO.

ulfnorell
źródło
Twoje pierwsze zdanie wydaje się nieco dziwne; Chciałbym powiedzieć, że punkt typów zależnych jest to, że zrobić pracę, gdy dane są dostępne tylko w czasie wykonywania. Jednak ta technika w stylu CPS nie jest taka sama. Załóżmy, że masz funkcję Vec Zy -> IO String. Nie możesz tego użyć withZeroes, ponieważ typ Zynie może być ujednolicony z forall n. Może uda ci się to obejść w jednym lub dwóch specjalnych przypadkach, ale szybko wymyka się to spod kontroli.
John L
Kluczową kwestią przy pobieraniu po prostu wpisanej wartości (takiej jak String z getLine) i przekształcaniu jej w coś z silniejszym typem (jak Natty n powyżej) jest przekonanie kontrolera typów, że wykonujesz niezbędne testy dynamiczne. W swoim przykładzie czytasz dowolną liczbę, więc forall nma to sens. Bardziej precyzyjne ograniczenia można wprowadzić w ten sam sposób. Czy masz lepszy przykład niż Vec Zy(program nadal musiałby obsługiwać użytkownika wprowadzającego 5 zamiast 0)?
ulfnorell
1
W pierwszym zdaniu chciałem powiedzieć, że od czasu do czasu spotykam ludzi, którzy uważają, że nie można używać typów zależnych, jeśli otrzymujesz dane poprzez interakcję ze światem zewnętrznym. Chodzi mi o to, że jedyne, co musisz zrobić, to napisać zależnie typowany parser, co zwykle jest proste.
ulfnorell
1
ulfnorell: Przepraszam, nie było jasne. Załóżmy, że masz jedną funkcję, z którą będzie działać, Vec Zy -> IO Stringa drugą Vec n -> IO String, i chcesz użyć pierwszej tylko wtedy, gdy typ jest zgodny. Tak, jest to możliwe, ale mechanizmy umożliwiające to są niezgrabne. I to jest bardzo prosta logika; jeśli masz bardziej złożoną logikę, jest gorzej. Może być również konieczne ponowne napisanie dużej ilości kodu w CPS. I nadal nie masz wyrażenia na poziomie typu, które jest zależne od terminu na poziomie wartości
John L,
Ach, rozumiem, co mówisz. Do tego służy Natty, na przykład w vReplicate, gdzie robimy różne rzeczy w zależności od n. Rzeczywiście, może to być trochę niezgrabne. Alternatywą do stylu CPS jest do pracy z spakowali existentials: zeroes :: IO (Some (Flip Vec Int)).
ulfnorell
19

pigworker podaje doskonałą dyskusję, dlaczego powinniśmy zmierzać w kierunku typów zależnych: (a) są niesamowite; (b) faktycznie uprościłyby wiele z tego, co już robi Haskell.

A jeśli chodzi o "dlaczego nie?" pytanie, myślę, że jest kilka punktów. Pierwszą kwestią jest to, że chociaż podstawowe pojęcie leżące u podstaw typów zależnych jest łatwe (zezwalaj na zależność typów od wartości), konsekwencje tego podstawowego pojęcia są zarówno subtelne, jak i głębokie. Na przykład rozróżnienie między wartościami i typami jest wciąż żywe i dobre; ale omawianie różnicy między nimi jest dalekobardziej zniuansowany niż u Hindleya - Milnera czy Systemu F. W pewnym stopniu wynika to z faktu, że typy zależne są zasadniczo trudne (np. logika pierwszego rzędu jest nierozstrzygalna). Ale myślę, że większym problemem jest tak naprawdę to, że brakuje nam dobrego słownictwa do wychwytywania i wyjaśniania, co się dzieje. W miarę jak coraz więcej ludzi uczy się o typach zależnych, rozwiniemy lepsze słownictwo, dzięki czemu rzeczy staną się łatwiejsze do zrozumienia, nawet jeśli podstawowe problemy są nadal trudne.

Druga kwestia dotyczy faktu, że Haskell rośniewobec typów zależnych. Ponieważ czynimy stopniowe postępy w realizacji tego celu, ale tak naprawdę go nie osiągamy, utknęliśmy w języku, który ma przyrostowe łaty na przyrostowych. To samo wydarzyło się w innych językach, gdy popularne stały się nowe pomysły. Java nie miała (parametrycznego) polimorfizmu; a kiedy w końcu go dodali, było to oczywiście stopniowe ulepszenie z pewnymi wyciekami abstrakcji i okaleczoną mocą. Okazuje się, że mieszanie podtypów i polimorfizmu jest z natury trudne; ale to nie jest powód, dla którego generiki Java działają tak, jak działają. Działają tak, jak robią, ze względu na ograniczenie polegające na stopniowym ulepszaniu starszych wersji Javy. Jak wyżej, dalej w czasach, kiedy wynaleziono OOP i ludzie zaczęli pisać „obiektywne” C (nie mylić z Objective-C) itd. Pamiętaj, że C ++ zaczynał się pod pozorem bycia ścisłym nadzbiorem C. Dodanie nowych paradygmatów zawsze wymaga zdefiniowania języka od nowa, albo też doprowadziło do jakiegoś skomplikowanego bałaganu. Chodzi mi o to, że dodanie do Haskella typów prawdziwie zależnych będzie wymagało pewnej ilości patroszenia i restrukturyzacji języka - jeśli mamy to zrobić dobrze. Ale naprawdę ciężko jest zaangażować się w tego rodzaju remont, podczas gdy stopniowy postęp, jaki poczyniliśmy, wydaje się tańszy w krótkim okresie. Naprawdę nie ma zbyt wielu ludzi, którzy włamują się do GHC, ale istnieje spora ilość starszego kodu, który można zachować przy życiu. To jest jeden z powodów, dla których istnieje tak wiele języków spin-off, takich jak DDC, Cayenne, Idris itp. C ++ zaczął się pod pozorem bycia ścisłym nadzbiorem C. Dodanie nowych paradygmatów zawsze wymaga zdefiniowania języka od nowa, albo kończy się na skomplikowanym bałaganie. Chodzi mi o to, że dodanie do Haskella typów prawdziwie zależnych będzie wymagało pewnej ilości patroszenia i restrukturyzacji języka - jeśli mamy to zrobić dobrze. Ale naprawdę ciężko jest zaangażować się w tego rodzaju remont, podczas gdy stopniowy postęp, jaki poczyniliśmy, wydaje się tańszy w krótkim okresie. Naprawdę nie ma zbyt wielu ludzi, którzy włamują się do GHC, ale istnieje spora ilość starszego kodu, który można zachować przy życiu. To jest jeden z powodów, dla których istnieje tak wiele języków spin-off, takich jak DDC, Cayenne, Idris itp. C ++ zaczął się pod pozorem bycia ścisłym nadzbiorem C. Dodanie nowych paradygmatów zawsze wymaga zdefiniowania języka od nowa, albo kończy się na skomplikowanym bałaganie. Chodzi mi o to, że dodanie do Haskella typów prawdziwie zależnych będzie wymagało pewnej ilości patroszenia i restrukturyzacji języka - jeśli mamy to zrobić dobrze. Ale naprawdę ciężko jest zaangażować się w tego rodzaju remont, podczas gdy stopniowy postęp, jaki poczyniliśmy, wydaje się tańszy w krótkim okresie. Naprawdę nie ma zbyt wielu ludzi, którzy włamują się do GHC, ale istnieje spora ilość starszego kodu, który można zachować przy życiu. To jest jeden z powodów, dla których istnieje tak wiele języków spin-off, takich jak DDC, Cayenne, Idris itp. albo skończy się na jakimś skomplikowanym bałaganie. Chodzi mi o to, że dodanie do Haskella typów prawdziwie zależnych będzie wymagało pewnej ilości patroszenia i restrukturyzacji języka - jeśli mamy to zrobić dobrze. Ale naprawdę ciężko jest zaangażować się w tego rodzaju remont, podczas gdy stopniowy postęp, jaki poczyniliśmy, wydaje się tańszy w krótkim okresie. Naprawdę nie ma zbyt wielu ludzi, którzy włamują się do GHC, ale istnieje spora ilość starszego kodu, który można zachować przy życiu. To jest jeden z powodów, dla których istnieje tak wiele języków spin-off, takich jak DDC, Cayenne, Idris itp. albo skończy się na jakimś skomplikowanym bałaganie. Chodzi mi o to, że dodanie do Haskella typów prawdziwie zależnych będzie wymagało pewnej ilości patroszenia i restrukturyzacji języka - jeśli mamy to zrobić dobrze. Ale naprawdę ciężko jest zaangażować się w tego rodzaju remont, podczas gdy stopniowy postęp, jaki poczyniliśmy, wydaje się tańszy w krótkim okresie. Naprawdę nie ma zbyt wielu ludzi, którzy włamują się do GHC, ale istnieje spora ilość starszego kodu, który można zachować przy życiu. To jest jeden z powodów, dla których istnieje tak wiele języków spin-off, takich jak DDC, Cayenne, Idris itp. Naprawdę ciężko jest zaangażować się w tego rodzaju remont, podczas gdy stopniowy postęp, jaki poczyniliśmy, wydaje się tańszy w krótkim okresie. Naprawdę nie ma zbyt wielu ludzi, którzy włamują się do GHC, ale istnieje spora ilość starszego kodu, który można zachować przy życiu. To jest jeden z powodów, dla których istnieje tak wiele języków spin-off, takich jak DDC, Cayenne, Idris itp. Naprawdę ciężko jest zaangażować się w tego rodzaju remont, podczas gdy stopniowy postęp, jaki poczyniliśmy, wydaje się tańszy w krótkim okresie. Naprawdę nie ma zbyt wielu ludzi, którzy włamują się do GHC, ale istnieje spora ilość starszego kodu, który można zachować przy życiu. To jest jeden z powodów, dla których istnieje tak wiele języków spin-off, takich jak DDC, Cayenne, Idris itp.

wren romano
źródło