2015-10-13 29 views
37

Mam dość przyzwoitą intuicję co do typów, które Haskell zakazuje jako "niepredukcyjne": mianowicie te, w których forall pojawia się w argumencie do konstruktora typu innego niż ->. Ale co to jest predykatywność? Co sprawia, że ​​jest to ważne? W jaki sposób odnosi się do słowa "orzecznik"?Co to jest predykatywność?

Odpowiedz

21

Pozwolę sobie tylko dodać punkt dotyczący kwestii "etymologii", ponieważ druga odpowiedź @DanielWagner obejmuje wiele aspektów technicznych.

Predykat na coś podobnego do a to a -> Bool. Teraz logika predykatów jest taka, która może w pewnym sensie rozumować o predykatach - więc jeśli mamy jakiś predykat P i możemy mówić o, dla danego a, P(a), teraz w "logice predykatów" (takich jak logika pierwszego rzędu) możemy również powiedzieć: ∀a. P(a). Możemy więc określić ilościowo zmienne i omówić zachowanie predykatów nad takimi rzeczami.

Teraz z kolei mówimy, że instrukcja jest predykatywna, jeśli wszystkie elementy, do których stosuje się predykat, zostały wprowadzone przed przed. Zatem stwierdzenia są "oparte na" rzeczach, które już istnieją. Z kolei stwierdzenie jest mało znaczące, jeśli może w pewnym sensie odnosić się do siebie poprzez "ładunki początkowe".

Tak więc w przypadku np. Przykład id powyżej, okazuje się, że możemy dać typ do id takie, że ma coś z typu z id do czegoś innego od typu z id. Teraz możemy nadać funkcji typ, w którym zmienna kwantyfikowana (wprowadzona przez forall a.) może "rozwinąć się", aby być tego samego typu, co funkcja samej funkcji!

W związku z tym niepraktyczność wprowadza możliwość pewnego "odniesienia do siebie". Ale czekaj, możesz powiedzieć, czy taka rzecz nie doprowadziłaby do sprzeczności? Odpowiedź brzmi: "cóż, czasami". W szczególności "System F", który jest polimorficznym rachunkiem lambda i istotnym "rdzeniem" języka "podstawowego" GHC, pozwala na formę nieprzezwyciężania, która ma jednak dwa poziomy - poziom wartości i poziom, który może określić ilościowo. W tej dwupoziomowej stratyfikacji możemy mieć nieprzewidywalność i sprzeczność/paradoks.

Chociaż uwaga, że ​​ta sztuczka jest schludny bardzo delikatne i łatwe do zepsuć dodając więcej funkcji, jak tego zbioru artykułów Oleg wskazuje: http://okmij.org/ftp/Haskell/impredicativity-bites.html

40

Podstawową kwestią tego typu systemów jest: "Czy można podstawić typ polimorficzny dla zmiennej typu?". Systemy predykcyjne to bezsensowne szkolne odpowiedzi, "ABSOLUTNIE NIE", podczas gdy niepodobne systemy typu są twoim beztroskim kumplem, który myśli, że to brzmi jak zabawny pomysł i co może pójść nie tak?

Haskell mętnie omawia tę dyskusję, ponieważ uważa, że ​​polimorfizm powinien być przydatny, ale niewidoczny. W związku z tym do końca tego wpisu będę pisać w dialekcie Haskella, w którym użycie forall jest nie tylko dozwolone, ale wymagane. W ten sposób możemy odróżnić typ a, który jest typem monomorficznym, który czerpie swoją wartość ze środowiska pisania, które możemy zdefiniować później, oraz typu forall a. a, który jest jednym z trudniejszych polimorficznych typów, które należy zamieszkać. Zezwalamy też na to, aby forall był prawie wszędzie w typie - jak zobaczymy, GHC ogranicza raczej jego składnię typu jako mechanizm "fail-fast", niż jako wymóg techniczny.

Załóżmy, że powiedzieliśmy kompilatorowi id :: forall a. a -> a. Czy możemy później poprosić o użycie id tak, jakby miał on typ (forall b. b) -> (forall b. b)? Nieprawidłowe systemy typu są w porządku z tym, ponieważ możemy utworzyć kwantyfikator w rodzaju id na forall b. b i zastąpić forall b. b dla wszędzie w wyniku. Układy typu prognozowanego są nieco bardziej ostrożny, że: tylko jednokształtnym typy są dozwolone w

Jest podobna historia o [] :: forall a. [a] i (:) :: forall a. a -> [a] -> [a]. (Więc jeśli mieliśmy szczególną b, moglibyśmy napisać id :: b -> b.). Podczas gdy twój beztroski kumpel może być w porządku z [] :: [forall b. b] i (:) :: (forall b. b) -> [forall b. b] -> [forall b. b], orzecznik szkoły nie jest, tak bardzo. W rzeczywistości, jak widać z jedynych dwóch konstruktorów list, nie ma możliwości utworzenia list zawierających wartości polimorficzne bez tworzenia zmiennej typu w swoich konstruktorach na wartość polimorficzną. Więc chociaż typ [forall b. b] jest dozwolone w naszym dialekcie Haskell, to nie jest naprawdę sensowne - nie ma terminów (kończących) tego typu. To motywuje decyzję GHC do złożenia skargi, nawet jeśli myślisz o takim typie - jest to sposób, w jaki kompilator mówi ci "nie zawracaj sobie głowy". *

Cóż, co czyni szkołę tak surową? Jak zwykle, odpowiedź polega na utrzymywaniu kontroli typów i wnioskowania o typ. Typ wnioskowania dla typów nieistotnych jest już dostępny. Sprawdzanie typu seems like it might be possible, ale jest cholernie skomplikowane i nikt nie chce tego utrzymywać.

Z drugiej strony, niektórzy zarzucają, że GHC jest całkowicie zadowolony z niektórych typów, które wydają się wymagać impredicativity:

> :set -Rank2Types 
> :t id :: (forall b. b) -> (forall b. b) 
{- no complaint, but very chatty -} 

Okazuje się, że niektórzy lekko ograniczone wersje impredicativity nie są zbyt złe: specjalnie , sprawdzanie typu, typy wyższego rzędu (które pozwalają na zastąpienie zmiennych typu polimorficznego typami, gdy są tylko argumentami dla (->)), jest stosunkowo proste. Tracisz wnioskowanie typu powyżej rangi 2 i główne typy powyżej rangi 1, ale czasami wyższe rangi są tym, co zalecił lekarz.

Jednak Dunno o etymologii słowa!


* Można się zastanawiać, czy można zrobić coś takiego:

data FooTy a where 
    FooTm :: FooTy (forall a. a) 

Wtedy dostaniesz termin (FooTm), którego typ coś polimorficzny jako argument do czegoś innego niż (->) (a mianowicie, FooTy), nie musisz przekraczać szkoły, aby to zrobić, więc przekonanie, że stosowanie "non-(->)" do typów polimorficznych jest nieprzydatne, ponieważ nie możesz ich zrobić "byłoby unieważnione. GHC nie pozwala ci pisać FooTy i przyznaję, że nie jestem pewien, czy istnieje zasadniczy powód ograniczenia, czy też nie.

+0

Nie ma żadnych dobrych terminów typu 'forall a. a', ale istnieje wiele rozsądnych terminów polimorficznych. Nie rozumiem, dlaczego nie chciałbym * tych * ... – dfeuer

+1

@dfeuer Tak, istnieje wiele rozsądnych terminów polimorficznych. Ale (w systemie predykatywnym) nie ma żadnych terminów, których typem jest lista z typem polimorficznym, bez względu na to, który typ polimorficzny wybierzesz! –

+0

@ Danielhagner, ah, myślę, że widzę, co masz teraz na myśli. – dfeuer

13

Chciałbym, aby komentarz na problem etymologii, ponieważ odpowiedź @ sclv nie jest całkiem poprawna (etymologicznie, nie koncepcyjnie).

Cofnij się w czasie, do dni Russella, kiedy wszystko jest ustawione w teorii - w tym w logice.Jednym z logicznych pojęć o szczególnym znaczeniu jest "zasada rozumienia"; to znaczy, biorąc pod uwagę jakiś logiczny predykat, chcielibyśmy mieć jakąś zasadę, aby ustalić zestaw wszystkich elementów spełniających ten predykat, zapisany jako "{x | φ(x) }" lub jego odmianę. Kluczową kwestią, o której należy pamiętać, jest to, że "zestawy" i "orzeczniki" są postrzegane jako zasadniczo różne rzeczy: predykaty to odwzorowania z obiektów na wartości prawdy, a zestawy są obiektami. Tak więc, na przykład, możemy pozwolić na kwantyfikację przez zestawy, ale nie na kwantyfikację przez predykaty.

Teraz Russell był raczej zaniepokojony jego tytułowym paradoksem i szukał sposobu, aby się go pozbyć. Istnieje wiele poprawek, ale jednym z interesujących tutaj jest ograniczenie zasady rozumienia. Najpierw jednak formalna definicja zasady: ∃S.∀x.S x ↔︎ φ(x); to znaczy, dla naszego szczególnego φ istnieje jakiś obiekt (tj. zestaw) S taki, że dla każdego obiektu (również zestawu, ale uważanego za element) x, mamy to S x (możesz myśleć o tym jako o znaczeniu "x∈S ", chociaż logicy z tamtych czasów nadawali" "inne znaczenie niż zwykłe zestawienie) jest prawdziwe tylko w przypadku, gdy φ(x) jest prawdziwe. Jeśli przyjmiemy zasadę dokładnie tak, jak jest to napisane, wówczas otrzymamy teorię nieprzedstawiającą. Możemy jednak wprowadzić ograniczenia, na podstawie których możemy uzyskać zrozumienie. (Na przykład, jeśli powiemy, że φ nie może zawierać kwantyfikatorów drugiego rzędu). W związku z tym, dla każdego ograniczenia R, jeśli zbiór S jest określany (tj. Generowany przez zrozumienie) przez jakiś kod , to mówimy, że S jest "R -preykatywny". Jeśli każdy zestaw w naszym języku to R -przykładowy, mówimy, że naszym językiem jest "R -predicative". A potem, jak to często bywa w przypadku dzielonych wyrazów przedrostkowych, prefiks zostaje odrzucony i pozostawiony bezwarunkowo, skąd bierze się "predykatywne" języki. I oczywiście języki, które nie są predykatywne, są "nieprzewidywalne".

To jest stara etymologia szkoły. Od tego czasu terminy poszły w zapomnienie i zdobyły własne życie. Sposoby, w jakie używamy dzisiaj "predykatywny" i "nieprzydatny", są zupełnie inne, ponieważ rzeczy, których dotyczą, uległy zmianie. Więc czasami może być trochę trudniej zobaczyć, jak do cholery nasze nowoczesne użycie wiąże się z tymi rzeczami. Szczerze mówiąc, nie sądzę, że wiedza na temat etymologii naprawdę pomaga każdemu, jeśli chodzi o zrozumienie, o czym naprawdę mówią te słowa (te dni).

+2

Dzięki za ten dodatkowy kontekst historyczny tutaj. Bardzo doceniane! – sclv

+0

Tak więc, dla pewnego niedbałego ograniczenia 'R', nie kupuje on zbyt wiele, aby być' R'-predykatywnym pod względem spójności, prawda? "Predykatywny" w tym znaczeniu nie oznacza konsekwencji, jak w "wolnym od paradoksów", jeśli się nie mylę ... –