Dlaczego nie być niezawodnie wpisywane?

Widziałem kilka źródeł potwierdzających opinię, że "Haskell stopniowo staje się językiem zależnym". Implikacja wydaje się być taka, że z coraz większą liczbą rozszerzeń językowych, Haskell dryfuje w tym ogólnym kierunku, ale jeszcze tego nie ma.

Są dwie rzeczy, które chciałbym wiedzieć. Po pierwsze, co właściwie oznacza" bycie językiem zależnym " ? (Mam nadzieję, że nie będąc zbyt technicznym o to.)

Drugie pytanie brzmi:.. jaka jest wada? Ludzie wiedzą, że zmierzamy w tamtą stronę, więc musi być w tym jakaś przewaga. A jednak jeszcze nie jesteśmy, więc muszą być jakieś minusy, które powstrzymują ludzi przed pójściem na całość. Mam wrażenie, że problemem jest gwałtowny wzrost złożoności. Ale nie do końca rozumiejąc, co to jest pisanie zależne, Nie wiem na pewno.

To, co robię wiem, że za każdym razem, gdy zaczynam czytać o zależnym wpisie język programowania, tekst jest zupełnie niezrozumiały... Prawdopodobnie w tym problem. (?)

Author: hammar, 2012-10-18
Source

4 answers

Pisanie zależne jest tak naprawdę tylko unifikacją poziomów wartości i typów, więc możesz parametryzować wartości typów (już możliwe z klasami typów i parametrycznym polimorfizmem w Haskell) i możesz parametryzować typy na wartości (nie, ściśle mówiąc, możliwe jeszcze w Haskell, chociaż DataKinds jest bardzo blisko).

Edit: najwyraźniej od tej chwili się myliłem(patrz komentarz @ pigworker). Resztę zachowam jako zapis mitów, którymi byłem fed. : P

Problem z przejściem do pełnego, zależnego pisania, z tego co słyszałem, polega na tym, że złamałoby to ograniczenie fazowe między poziomem typu i wartości, które pozwala haskellowi skompilować do wydajnego kodu maszynowego z usuniętymi typami. Przy obecnym poziomie technologii, język zależnie wpisany musi przejść przez interpreter w pewnym momencie (albo natychmiast, albo po skompilowaniu do zależnie wpisanego kodu bajtowego lub podobnego).

To nie jest koniecznie fundamentalne ograniczenie, ale nie jestem osobiście świadomy żadnych bieżących badań, które wyglądają obiecująco w tym względzie, ale które jeszcze nie weszły do GHC. Jeśli ktoś jeszcze wie więcej, chętnie się poprawię.

 22
Author: Ptharien's Flame,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-10-18 19:14:23

/ Align= "Left" / Haskell jest w niewielkim stopniu zależnym językiem pisanym. Istnieje pojęcie danych na poziomie typu, teraz bardziej sensownie wpisywanych dzięki DataKinds, i istnieje kilka sposobów (GADTs), aby dać czas wykonywania reprezentacja danych na poziomie typu. Stąd, wartości run-time stuff skutecznie pojawiają się w typach, co oznacza, że język musi być zależnie wpisywany.

Proste typy danych są promowane do poziomu rodzaju, więc że wartości zawierają one mogą być stosowane w typach. Stąd przykład archetypu 

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ść n jest rzeczą czysto statyczną w tej funkcji, zapewniając, że wektory wejściowe i wyjściowe mają tej samej długości, mimo że długość ta nie odgrywa żadnej roli w realizacji vApply. Natomiast znacznie trudniejsze (tzn. niemożliwe) jest zaimplementować funkcję, która tworzy n kopie given x (which będzie pure do vApply ' s <*>) 
vReplicate :: x -> Vec n x

Ponieważ ważne jest, aby wiedzieć, ile kopii zrobić w czasie wykonywania. Enter singletony.

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

Dla dowolnego typu możemy zbudować rodzinę singletonów, indeksowaną nad promowanym typem, zamieszkanym przez duplikaty jego wartości. Natty n jest typem kopii run-time poziomu typu n :: Nat. Możemy teraz napisać 

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

Więc tam masz wartość poziomu typu yoked do wartości run-time: Kontrola run-time copy udoskonala statyczną wiedzę o wartość poziomu typu. Mimo, że terminy i typy są rozdzielone, możemy pracy w sposób zależny, wykorzystując konstrukcję singletonową jako rodzaj żywicy epoksydowej, tworzącej wiązania między fazami. To jest długa droga od zezwalania na dowolne wyrażenia run-time w typach, ale to nic takiego.

Co jest paskudne? Czego brakuje?

[56]}wywrzyjmy trochę presję na tę technologię i zobaczmy, co się zacznie chwieje się. Może wpadniemy na pomysł, że singletony powinny być zarządzalne a bit more implicite 
class Nattily (n :: Nat) where
  natty :: Natty n
instance Nattily Z where
  natty = Zy
instance Nattily n => Nattily (S n) where
  natty = Sy natty

Pozwala nam napisać, powiedzmy, 

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

To działa, ale teraz oznacza to, że nasz oryginalny typ Nat narodził się trzy egzemplarze: Rodzaj, Rodzina singletonów i klasa singletonów. My mają dość niezgrabny proces wymiany jawnych wartości Natty n i Nattily n słowniki. Ponadto Natty nie jest Nat: mamy pewnego rodzaju zależności od wartości run-time, ale nie od typu we pierwsza myśl. Nie w pełni zależny język pisany uzależnia typy takie skomplikowane!

Tymczasem, chociaż Nat można promować, Vec nie można. Nie możesz. indeks według typu zindeksowanego. Pełna wersja językowa nie ma takich ograniczeń, a w mojej karierze jako zależnego od siebie popisu, Nauczyłem się zawierać przykłady dwuwarstwowego indeksowania w moich rozmowach, tylko po to, by nauczyć ludzi, którzy stworzyli jednowarstwowe indeksowanie trudne-ale-możliwe, że nie oczekuję, że złożę się jak Dom z karty. W czym problem? Równość. Gadt praca tłumacząc ograniczenia, które osiągasz w sposób niejawny, gdy dajesz konstruktorowi specyficzny typ powrotu do wyraźnych wymagań równościowych. W ten sposób.

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ą rodzaj Nat.

Teraz spróbuj tego samego tłumaczenia dla czegoś indeksowanego przez wektory.

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)

I teraz tworzymy ograniczenia równościowe między as :: Vec n x a VCons z zs :: Vec (S m) x gdzie obie strony mają składniową odrębny (ale provably equal) rodzaje. GHC core nie jest obecnie wyposażony do takiej koncepcji!

Czego jeszcze brakuje? Cóż, większość Haskell brakuje w typie poziom. Język terminów, które można promować, ma tylko zmienne i nie-GADT konstruktorzy, naprawdę. Gdy już je posiadasz, maszyneria type family pozwala na pisanie programów typu: niektóre z to może być coś w rodzaju funkcji, które rozważyłbyś pisząc na poziomu terminowego (np. wyposażanie Nat W dodawanie, dzięki czemu można give a dobry typ do dodania dla Vec), ale to tylko zbieg okoliczności!

Inną rzeczą, której brakuje w praktyce, jest biblioteka , która sprawia, że wykorzystanie naszych nowych możliwości do indeksowania typów według wartości. Co zrobić Functor i stać się w tym nowym, odważnym świecie? Myślę o tym, ale jest jeszcze wiele do zrobienia.

Uruchamianie Programów Typu

Haskell, podobnie jak większość zależnych języków programowania, ma dwa]} semantyki operacyjne. Jest sposób na run-time system runs programów (tylko wyrażenia zamknięte, po usunięciu typu, wysoce zoptymalizowany) i jest jeszcze sposób, w jaki typechecker uruchamia programy (twoje rodziny typów, Twoja "klasa typu Prolog" , z otwartymi wyrażeniami). Dla Haskell ' a normalnie nie mieszasz dwa w górę, ponieważ uruchamiane programy są w różnych języki. Języki zależne mają osobny czas działania i statyczne modele wykonawcze dla tego samego języka programów, ale nie worry, the run-time model nadal pozwala na wpisywanie wymazywania i, rzeczywiście, dowód kasowania: to właśnie daje mechanizm Coq ekstrakcji ; tak przynajmniej robi kompilator Edwina Brady ' ego (chociaż Edwin usuwa niepotrzebnie zduplikowane wartości, a także typy i dowody). Rozróżnienie fazowe nie może być rozróżnieniem kategorii składniowej dłużej, ale żyje i ma się dobrze.

Języki zależne, będące całkami, pozwalają na uruchamianie typechecker programy wolne od strachu przed niczym to gorsze niż długie oczekiwanie. Jako Haskell staje się bardziej zależny, stajemy przed pytaniem, co jego statyczny model wykonania powinien być? Jednym z podejść może być ograniczyć statyczne wykonywanie do funkcji całkowitych, co pozwoli nam na tej samej wolności biegania, ale może zmusić nas do rozróżniania (przynajmniej dla kodu poziomu typu) pomiędzy danymi a codata, dzięki czemu możemy stwierdzić czy wymuszać wypowiedzenie umowy, czy produktywność. Ale to nie jedyny podejdźcie. Mamy swobodę wyboru znacznie słabszego wykonania model, który jest niechętnie uruchamiać programy, kosztem zmniejszenia liczby równań tylko na podstawie obliczeń. I w efekcie, tak naprawdę GHC tak. Zasady typowania dla GHC core nie wspominają o uruchomieniu programy, ale tylko do sprawdzania dowodów na równania. Kiedy tłumacząc to na rdzeń, GHC ' s constraint solver próbuje uruchomić programy na poziomie typu, generowanie trochę srebrzystego śladu dowodów, że dane wyrażenie równa się jego normalnej formie. Ten dowód-pokolenie metoda jest trochę nieprzewidywalne i nieuchronnie niekompletne: walczy nieśmiało z przerażająco wyglądająca rekurencja, na przykład, i to pewnie mądre. Jeden to, o co nie musimy się martwić, to wykonanie IO obliczenia w typechecker: pamiętaj, że typechecker nie musi dawać launchMissiles to samo, co system run-time!

Kultura Hindleya-Milnera

System typu Hindley-Milner osiąga naprawdę niesamowity zbieg okoliczności z czterech odrębnych wyróżnień, z niefortunną kulturą efekt uboczny, że wiele osób nie widzi różnicy między rozróżnienia i załóżmy, że zbieg okoliczności jest nieunikniony! Czym jestem o czym?

  • terms vs typy
  • rzeczy napisane jawnie vs rzeczy napisane jawnie
  • obecność w czasie biegu vs wymazywanie przed czasem biegu
  • abstrakcja zależna vs kwantyfikacja zależna

Jesteśmy przyzwyczajeni do pisanie terminów i pozostawianie typów do wywnioskowania...oraz potem wymazane. Jesteśmy przyzwyczajeni do kwantyfikacji zmiennych typu z odpowiedni typ abstrakcji i aplikacji dzieje się cicho i statycznie.

Nie musisz się zbytnio oddalać od wanilii Hindley-Milner zanim te rozróżnienia wyjdą z równowagi, a to nie jest zła rzecz . Na początek możemy mieć bardziej interesujące typy, jeśli chcemy je napisać w kilku miejsca. Tymczasem nie musimy pisać typu słowniki klas gdy używamy przeciążonych funkcji, ale te słowniki są z pewnością obecny (lub inlined) w czasie pracy. W językach zależnych, my spodziewaj się wymazać więcej niż tylko typy w czasie wykonywania, ale (jak w przypadku typu klas) , że niektóre wartości dorozumiane nie będą wymazane. Na przykład, vReplicate's argument liczbowy jest często nie do odróżnienia od typu pożądanego wektora, ale nadal musimy znać go w czasie wykonywania.

Jakie wybory projektowe języka powinniśmy przejrzeć, ponieważ te zbiegi okoliczności już nie istnieją? Na przykład, czy to prawda, że Haskell zapewnia nie da się jednoznacznie utworzyć kwantyfikatora forall x. t? Jeśli typechecker nie może zgadnąć x przez unifiying t, nie mamy innego sposobu na powiedz co x musi być.

Szerzej, nie możemy traktować "wnioskowania typu" jako pojęcia monolitycznego że mamy albo wszystko, albo nic. Na początek musimy się rozdzielić. poza aspektem " uogólnienia "(zasada" let " Milnera), która w dużej mierze opiera się na ograniczanie istniejących typów aby zapewnić, że głupia maszyna może odgadnąć, od aspektu " specjalizacji "(zasada "var" Milnera) co jest równie skuteczne, jak rozwiązywanie ograniczeń. Możemy się spodziewać, że typy najwyższego poziomu staną się trudniejsze do wywnioskowania, ale ten wewnętrzny typ informacje pozostaną dość łatwe do rozpowszechnienia.

Kolejne Kroki Dla Haskell

Widzimy, że poziom rodzaju i rodzaju rośnie bardzo podobnie (a oni już podzielają wewnętrzną reprezentację w GHC). Możemy równie dobrze połącz je. Byłoby fajnie. wziąć * :: * jeśli możemy: przegraliśmy logiczne solidność dawno temu, kiedy pozwoliliśmy na dno, ale Typ solidność jest zwykle słabszym wymogiem. Musimy sprawdzić. Jeśli musimy mieć różne poziomy typu, rodzaju itp., możemy przynajmniej upewnić się, że wszystko na poziomie typu i powyżej mogą być zawsze promowane. Byłoby świetnie. tylko po to, aby ponownie wykorzystać polimorfizm, który już mamy dla typów, a nie ponowne wynalezienie polimorfizmu na poziomie rodzaju.

Powinniśmy uprościć i uogólnić obecny system ograniczeń przez dopuszczając heterogeniczne równania a ~ b gdzie rodzaje a i b nie są identyczne składniowo (ale można udowodnić, że są równe). To jest stara technika (w mojej pracy, ubiegłego wieku), która sprawia, że wiele łatwiej sobie z tym poradzić. Bylibyśmy w stanie wyrazić ograniczenia na wyrażeń w gadach, a tym samym rozluźnić ograniczenia tego, co może być awans.

Powinniśmy wyeliminować potrzebę budowy singletonu przez wprowadzenie zależnego typ funkcji, pi x :: s -> t. Funkcja z takim typem można zastosować jawnie do dowolnego wyrażenia typu s, które mieszka w przecięciu typu i terminu języki (tak, zmienne, konstruktory, a później więcej). Odpowiednie lambda i aplikacja nie będą kasowane w czasie wykonywania, Więc będziemy w stanie napisać 

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

Bez zastąpienia Nat przez Natty. Domeną pi może być dowolna promotable type, więc jeśli Gadty mogą być promowane, możemy zapis zależny w 2005 roku został wybrany do Izby Reprezentantów.]} 

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

Na dowolną długość.

Celem tych kroków jest wyeliminowanie złożoności poprzez bezpośrednią pracę z bardziej ogólnymi narzędziami, zamiast robić to ze słabymi narzędziami i niezgrabnymi kodowaniami. Obecne częściowe wpisowe sprawia, że korzyści z rodzajów zależnych od Haskella są droższe niż muszą być.

Zbyt Trudne?

Typy zależne sprawiają, że wiele ludzie się denerwują. Denerwują mnie., ale lubię się denerwować, a przynajmniej trudno mi się nie denerwować w każdym razie. Ale to nie pomaga, że jest taka mgła ignorancji wokół tematu. Część z tego wynika, że wszyscy wciąż muszę się wiele nauczyć. Ale zwolennicy mniej radykalnych podejść mają wiadomo, że podsyca lęk przed zależnymi typami, nie zawsze upewniając się, że fakty są całkowicie z nimi związane. Nie wymienię nazwisk. Tych "niedecydowalnych typów", "Turinga niekompletnego", " nie rozróżnienie fazowe", "brak wymazywania typu", "dowody wszędzie" itp., mity się utrzymują, mimo że są śmieciami.

Z pewnością nie jest tak, że zależne programy muszą zawsze sprawdzaj poprawność. Można poprawić podstawową higienę własnego programów, wymuszanie dodatkowych niezmienników w typach bez przechodzenia wszystkich sposób na pełną specyfikację. Małe kroki w tym kierunku całkiem często skutkują znacznie silniejszymi gwarancjami z nielicznymi lub bez dodatkowych obowiązki dowodowe. To nieprawda. że odpowiednio dobrane programy są nieuchronnie pełne dowodów, w rzeczy samej zwykle biorę obecność jakichkolwiek dowody w moim kodzie jako sygnał do kwestionują moje definicje .

Ponieważ, jak przy każdym wzroście artykulacji, możemy swobodnie mówić nowe rzeczy, jak i sprawiedliwe. Np. istnieje wiele nędznych sposobów na zdefiniuj binarne drzewa wyszukiwania, ale to nie znaczy, że nie ma dobrego sposobu. Ważne jest, aby nie zakładać, że złe doświadczenia nie mogą być bettered, nawet jeśli to wgnieci ego, żeby to przyznać. Konstrukcja zależna definicje to nowa umiejętność, która wymaga nauki i bycia Haskell programista nie czyni cię automatycznie ekspertem! A nawet jeśli niektóre programy są złe, dlaczego miałbyś odmawiać innym wolności, by byli sprawiedliwi?

Po Co Ci Haskell?

Naprawdę lubię typy zależne, ale większość moich projektów hakerskich to nadal w Haskell. Dlaczego? Haskell ma klasy typów. Haskell ma przydatne biblioteki. Haskell ma wykonalne (choć dalekie od ideału) leczenie programowania z efektami. Haskell ma siłę przemysłową kompilator. Języki zależne są na znacznie wcześniejszym etapie w rozwijającej się społeczności i infrastrukturze, ale dotrzemy tam, z realnej zmiany pokoleniowej w tym, co jest możliwe, np. poprzez metaprogramowanie i typ danych generycznych. Ale musisz tylko spojrzeć wokół tego, co ludzie robią w wyniku działań Haskella w kierunku zależne typy, aby zobaczyć, że jest wiele korzyści, aby być zdobyte przez popychanie do przodu obecnej generacji języków.

 225
Author: pigworker,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-05-23 11:54:53

John to kolejne błędne przekonanie o typach zależnych: że nie działają, 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))))

Edit: Hm, to miał być komentarz do odpowiedzi pigworkera. Najwyraźniej mi się to nie udaje.

 21
Author: ulfnorell,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-11-06 08:08:51

Pigworker daje doskonałą dyskusję o tym, dlaczego powinniśmy kierować się w stronę zależnych typów: (a) są niesamowite; (B) faktycznie uprościliby wiele z tego, co Haskell już robi.

A co do "dlaczego nie?"pytanie, myślę, że jest kilka punktów. Pierwszym punktem jest to, że podczas gdy podstawowe pojęcie typów zależnych jest łatwe (pozwól typom zależeć 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ąż żywa i dobrze; ale omawianie różnicy między nimi staje się daleko bardziej niuansowe niż w yer Hindley-Milner czy System F. do pewnego stopnia wynika to z faktu, że typy zależne są zasadniczo trudne (np. logika pierwszego rzędu jest nie do podjęcia decyzji). Ale myślę, że większym problemem jest to, że brakuje nam dobrego słownictwa do uchwycenia i wyjaśnienia, co się dzieje. W miarę jak coraz więcej osób uczy się typów zależnych, rozwijamy lepsze słownictwo i tak rzeczy staną się łatwiejsze do zrozumienia, nawet jeśli podstawowe problemy są nadal trudne.

Drugi punkt ma do czynienia z faktem, że Haskell jest rośnie w kierunku zależnych typów. Ponieważ robimy stopniowy postęp w kierunku tego celu, ale bez osiągnięcia tego celu, utknęliśmy z językiem, który ma przyrostowe łaty na szczycie przyrostowych łat. To samo działo się w innych językach, gdy nowe idee stały się popularne. Java nie używała do mieć (parametryczny) polimorfizm; a kiedy w końcu go dodali, to było oczywiście stopniowe ulepszenie z pewnymi wyciekami abstrakcji i kaleką mocy. Okazuje się, że mieszanie podtypów i polimorfizmu jest z natury trudne, ale nie dlatego Generyki Javy działają tak, jak działają. Działają one tak, jak robią, ponieważ ograniczają się do stopniowego ulepszania starszych wersji Javy. Tak samo, bo jeszcze w czasach kiedy OOP został wymyślony i ludzie zaczęli pisać "obiektywne" C (nie mylić z Objective-C), itp. Pamiętaj, że C++ zaczynało się pod pozorem bycia ścisłym supersetem C. dodanie nowych paradygmatów zawsze wymaga zdefiniowania języka na nowo, albo kończy się jakimś skomplikowanym bałaganem. Chodzi mi o to, że dodanie prawdziwych typów zależnych do Haskella będzie wymagało pewnej ilości patroszenia i restrukturyzacji języka - - - jeśli mamy to zrobić dobrze. Ale naprawdę trudno się zaangażować w tego typu remont, podczas gdy przyrostowe postęp, który robimy, wydaje się w krótkim czasie tańszy. Naprawdę, nie ma zbyt wielu ludzi, którzy włamują się do GHC, ale istnieje spora ilość kodu legacy, aby utrzymać się przy życiu. Jest to jeden z powodów, dla których istnieje tak wiele języków spinoff, takich jak DDC, Cayenne, Idris itp.

 19
Author: wren romano,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2020-06-01 08:57:15