Polimorfizm parametryczny vs polimorfizm Ad hoc

Question

Polimorfizm parametryczny vs polimorfizm Ad hoc

Chciałbym zrozumieć kluczową różnicę między parametrycznym polimorfizmem, takim jak polimorfizm klas/funkcji generycznych w językach Java/Scala/C++ i polimorfizmem "ad-hoc" w systemie typu Haskell. Znam pierwszy rodzaj języków, ale nigdy nie pracowałem z Haskell.

Dokładniej:

W Jaki Sposób algorytm wnioskowania typu np. w Javie różni się od wnioskowania typu w Haskell?
Proszę, daj mi przykład sytuacji, gdy coś może być napisane w Javie / Scali, ale nie może być napisane w Haskell (zgodnie z modułowymi cechami tych platform też), i vice-versa.

Z góry dzięki.

65

java haskell types polymorphism type-inference

Author: Vikas Tikoo, 2011-07-18

Source

3 answers

Polimorfizm parametryczny oznacza, że nie zależy nam na typie, zaimplementujemy funkcję tak samo dla każdego typu. Na przykład w Haskell:

length :: [a] -> Int
length [] = 0          
length (x:xs) = 1 + length xs

Nie obchodzi nas, jaki jest typ elementów listy, zależy nam tylko, ile ich jest.

Polimorfizm Ad-hoc (aka metoda overloading) oznacza jednak, że będziemy używać innej implementacji w zależności od typu parametru.

Oto przykład w Haskell. Powiedzmy, że chcesz zdefiniować funkcję o nazwie makeBreakfast.

Jeśli parametr wejściowy to Eggs, chcę makeBreakfast zwrócić wiadomość o tym, jak zrobić jajka.

Jeśli parametr wejściowy to Pancakes, chcę makeBreakfast zwrócić komunikat jak zrobić naleśniki.

Stworzymy typeklasę o nazwie BreakfastFood, która implementuje funkcję makeBreakfast. Implementacja makeBreakfast będzie różna w zależności od typu wejścia do makeBreakfast.

class BreakfastFood food where
  makeBreakfast :: food -> String

instance BreakfastFood Eggs where
  makeBreakfast = "First crack 'em, then fry 'em"

instance BreakfastFood Toast where
  makeBreakfast = "Put bread in the toaster until brown"

Według koncepcji Johna Mitchella W Języki Programowania ,

Zasadnicza różnica między parametrycznym polimorfizmem a przeciążeniem (aka polimorfizm ad-hoc) polega na tym, że parametryczne funkcje polimorficzne wykorzystują jeden algorytm do operowania na argumentach wielu różnych typów, podczas gdy przeciążone funkcje mogą używać innego algorytmu dla każdego typu argumentu.

31

Author: Rose Perrone,
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-24 15:42:34

Pełna dyskusja na temat tego, co znaczą polimorfizm parametryczny i polimorfizm ad-hoc i do jakiego stopnia są one dostępne w Haskell i w Javie jest długa; jednak twoje konkretne pytania można rozwiązać znacznie prościej:

Jak algorytm wnioskowania typu np. w Javie różni się od wnioskowania typu w Haskell?

Z tego co wiem, Java nie zajmuje się wnioskowaniem typu. Różnica polega na tym, że Haskell to robi.

Proszę podać mi przykład sytuacja, w której coś może być napisane w Javie / Scali, ale nie może być napisane w Haskell (zgodnie z modułowymi cechami tych platform zbyt), i vice-versa.

Bardzo prostym przykładem czegoś, co potrafi Haskell, czego Java nie potrafi, jest zdefiniowanie maxBound :: Bounded a => a. Nie znam wystarczająco dużo Javy, aby wskazać coś, co potrafi, czego Haskell nie potrafi.

0

Author: Daniel Wagner,
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
2011-07-19 02:28:11

score 80 · Accepted Answer

Zgodnie z TAPL, §23.2:

Polimorfizm parametryczny (...), pozwala na wykonanie jednego kawałka kod, który należy wpisać "ogólnikowo", używając zmiennych zamiast rzeczywistych typów, oraz następnie instancjonowane z poszczególnych typów w razie potrzeby. Definicje parametryczne są jednolite: wszystkie ich instancje zachowują się tak samo. (...)

Polimorfizm Ad hoc, natomiast pozwala na wykazanie wartości polimorficznej różne zachowania podczas "oglądania" na różnych typach. Najbardziej często przykładem polimorfizmu ad hoc jest przeciążenie, co wiąże się z pojedynczym symbol funkcji z wieloma implementacjami; kompilator (lub System runtime, w zależności od tego, czy rozdzielczość przeciążenia jest statyczna czy dynamiczna) wybiera odpowiednią implementację dla każdej aplikacji funkcji, na podstawie typów argumentów.

Jeśli więc weźmiemy pod uwagę kolejne etapy historii, nie-generyczna Oficjalna Java (a. K. A pre - J2SE 5.0 , bef. wrzesień 2011 2004) miał polimorfizm ad hoc - więc można przeciążać metodę - ale nie polimorfizm parametryczny, więc nie można napisać metody ogólnej . Potem możesz oczywiście robić obie rzeczy.

Dla porównania, od samego początku w 1990 roku , Haskell był parametrycznie polimorficzny, co oznacza, że można było napisać: {]}

swap :: (A; B) -> (B; A)
swap (x; y) = (y; x)

Gdzie A i B są zmiennymi typu, można utworzyć instancję na wszystkie typy, BEZ założeń.

Ale nie było wcześniej construct dającyad-hoc polimorfizm, który pozwala pisać funkcje, które dotyczą kilku typów, ale Nie wszystkich typów. Jako sposób na osiągnięcie tego celu zostały wdrożone klasy typu.

Pozwalają ci opisać klasę (coś podobnego do interfejsu Java), dając podpis typu funkcji, które chcesz zaimplementować dla Twojego typu ogólnego. Następnie można zarejestrować niektóre (i miejmy nadzieję, kilka) instancje pasujące do tej klasy. W międzyczasie możesz napisać metodę generyczną, taką jak:

between :: (Ord a)  a -> a -> a -> Bool
between x y z = x ≤ y ^ y ≤ z

Gdzie Ord jest klasą, która definiuje funkcję (_ ≤ _). W przypadku użycia, (between "abc" "d" "ghi") jest rozwiązane statycznie, aby wybrać właściwą instancję dla łańcuchów (a nie np. liczb całkowitych) - dokładnie w momencie przeciążenia metody (Javy).

Możesz zrobić coś podobnego w Javie za pomocą ograniczonych symboli wieloznacznych . Ale kluczowa różnica między Haskell i Java z przodu jest taka, że tylko Haskell może automatycznie przekazywać słownik : W obu językach, biorąc pod uwagę dwie instancje Ord T, powiedzmy b0 i b1, można zbudować funkcję f, która bierze je za argumenty i tworzy instancję dla typu pary (b0, b1), używając, powiedzmy, porządku leksykograficznego. Powiedz teraz, że otrzymałeś (("hello", 2), ((3, "hi"), 5)). W Javie musisz zapamiętać instancje string i int i przekazać poprawną instancję (złożoną z czterech aplikacji f!) w celu zastosowania between do tego obiektu. Haskell może zastosować składowość i dowiedzieć się, jak zbudować poprawną instancję, biorąc pod uwagę tylko instancje naziemne i konstruktor f (dotyczy to oczywiście innych konstruktorów) .

Teraz, jeśli chodzi o wnioskowanie typu (i prawdopodobnie powinno to być odrębne pytanie), dla obu języków jest to niekompletne, w tym sensie, że zawsze można napisać bez adnotacji program, dla którego kompilator nie będzie być w stanie określić typ.

Dla Haskella jest tak dlatego, że ma impredicative (a. k. a. first-class) polimorfizm, dla którego wnioskowanie typu jest niedecydowalne. Zauważ, że w tym punkcie Java ogranicza się do polimorfizmu pierwszego rzędu (czegoś, na czym scala się rozszerza).
W przypadku Javy jest to spowodowane tym, że obsługuje Podtyp kontrasty.

Ale te języki różnią się głównie w zakresie programu wyrażenia, do których w praktyce stosuje się wnioskowanie typu, oraz w znaczenie nadane poprawności wyników wnioskowania typu.

W przypadku Haskella wnioskowanie odnosi się do wszystkich "nie-wysoce polimorficznych" terminów i podejmuje poważne wysiłki, aby przywrócić wyniki dźwięku na podstawie opublikowanych rozszerzeń znanego algorytmu.]}
- w swej istocie wnioskowanie Haskella opiera się na Hindley-Milner, co daje pełne wyniki, gdy tylko przy wnioskowaniu typu aplikacji, zmienne typu (np. A i B w powyższym przykładzie) mogą być utworzone tylko z typami nie-polimorficznymi (upraszczam, ale jest to zasadniczo polimorfizm w stylu ML, który można znaleźć np. w Ocaml.).
- ostatni GHC upewni się, że adnotacja typu może być wymagana tylko dla let-bindowania lub λ-abstrakcji, która ma typ nie Damas-Milner .
- Haskell starał się pozostać względnie w pobliżu tego niepłodnego rdzenia nawet w jego najbardziej owłosionych rozszerzeniach(np. gadów). W każdym razie proponowane rozszerzenia prawie zawsze są dostarczane w dokumencie z dowodem poprawności wnioskowania typu rozszerzonego .
W Javie wnioskowanie typu ma zastosowanie w sposób znacznie bardziej ograniczony w każdym razie:

Przed wydaniem Java 5, nie było wnioskowania typu w Javie. Według kultury języka Java, Typ każdej zmiennej, metody i dynamicznie przydzielanego obiektu musi być jawnie zadeklarowany przez programistę . W Javie 5 wprowadzono generyki (klasy i metody parametryzowane przez typ), język zachował to wymaganie dla zmiennych, metod i alokacji . Jednak wprowadzenie metod polimorficznych (parametryzowanych przez typ) podyktowało, że albo (i) programista podaje argumenty typu metody w każdym miejscu wywołania metody polimorficznej, albo (ii) język obsługa wnioskowania argumentów typu metody. Aby uniknąć dodatkowego obciążenia dla programistów, projektanci Java 5 zdecydowali się wykonać wnioskowanie typu, aby określić argumenty typu dla wywołań metod polimorficznych. (źródło , podkreślenie moje)

Algorytm wnioskowania jest zasadniczo algorytmem GJ , ale z nieco kludgy dodanie symboli wieloznacznych (zauważ, że nie jestem do Data ewentualnych korekt dokonanych w J2SE 6.0). Duża różnica pojęciowa w podejściu polega na tym, że wnioskowanie Javy jest lokalne , w tym sensie, że wnioskowany typ wyrażenia zależy tylko od ograniczeń generowanych przez system typów i od typów jego pod-wyrażeń, ale nie od kontekstu.

Zauważ, że linia strony dotycząca niekompletnego i czasami błędnego wnioskowania typu jest stosunkowo luźna. Zgodnie z spec :

Zauważ również, że wnioskowanie typu w żaden sposób nie wpływa na poprawność dźwięku. Jeśli wnioskowane typy są bezsensowne, wywołanie spowoduje błąd typu. Algorytm wnioskowania typu powinien być postrzegany jako heurystyczny, zaprojektowany tak, aby w praktyce dobrze się rozwijał. Jeśli nie uda się wywnioskować pożądanego rezultatu, zamiast tego można użyć jawnych parametrów typu.