Czy system typów Haskell jest formalnie równoważny z systemem Java? [Zamknięte]

66

Zdaję sobie sprawę, że niektóre rzeczy są łatwiejsze / trudniejsze w jednym języku niż w drugim, ale interesują mnie tylko funkcje związane z typem, które są możliwe w jednym, a niemożliwe / nieistotne w drugim. Mówiąc dokładniej, zignorujmy rozszerzenia typu Haskell, ponieważ jest ich tak wiele, że robią różne szalone / fajne rzeczy.

GlenPeterson
źródło
4
Ja też jestem ciekawy, jak długo rozwiązywani teoretycy kategorii odpowiadają na to pytanie; choć wątpię, czy to szczególnie zrozumiem, nadal jestem zainteresowany szczegółami tego. Moja skłonność od rzeczy czytałem, że system typu HM umożliwia kompilator wiedzieć mnóstwo o tym, co robi Twój kod, który dlatego jest zdolny do wnioskowania typy tak dużo jak również daje tyle gwarancje o zachowanie. Ale to tylko mój instynkt i jestem pewien, że są w tym inne rzeczy, których jestem całkowicie nieświadomy.
Jimmy Hoffa,
1
To świetne pytanie - pora opublikować tweety dla fanów podczas wielkiej debaty Haskell / JVM!
Martijn Verburg
6
@ m3th0dman: Scala ma dokładnie taką samą obsługę funkcji wyższego rzędu jak Java. W Scali funkcje pierwszej klasy są po prostu reprezentowane jako instancje klas abstrakcyjnych za pomocą jednej metody abstrakcyjnej, podobnie jak Java. Jasne, Scala ma cukier syntaktyczny do definiowania tych funkcji i ma bogatą bibliotekę standardowych predefiniowanych typów funkcji i metod, które akceptują funkcje, ale z perspektywy systemu typów , o co chodzi w tym pytaniu, nie ma różnicy . Tak więc, jeśli Scala może to zrobić, to Java też, a tak naprawdę istnieją biblioteki FP inspirowane Haskell dla Javy.
Jörg W Mittag
2
@ m3th0dman: Nie o to chodzi w tym pytaniu.
Phil
7
@ m3th0dman Są to zupełnie zwyczajne typy. Nie ma nic specjalnego w listach, z wyjątkiem niektórych subtelności synchronicznych. Możesz łatwo zdefiniować własny typ danych algebraicznych, który jest równoważny wbudowanemu typowi listy, z wyjątkiem dosłownej składni i nazw konstruktorów.
sepp2k

Odpowiedzi:

63

(„Java”, w znaczeniu stosowanym w niniejszym dokumencie, jest zdefiniowane jako standardowy Java SE 7 ; „Haskell”, w znaczeniu stosowanym w niniejszym dokumencie, jest zdefiniowany jako standardowy Haskell 2010 ).

Rzeczy, które ma system typów Java, ale Haskell nie:

  • nominalny polimorfizm podtypu
  • informacje o częściowym typie środowiska wykonawczego

Rzeczy, które ma system typów Haskella, ale Java nie:

  • ograniczony polimorfizm ad-hoc
    • powoduje polimorfizm podtypu „oparty na ograniczeniach”
  • lepiej dobrany polimorfizm parametryczny
  • podstawowe pisanie

EDYTOWAĆ:

Przykłady każdego z powyższych punktów:

Unikalny dla Java (w porównaniu do Haskell)

Nominalny polimorfizm podtypu

/* declare explicit subtypes (limited multiple inheritance is allowed) */
abstract class MyList extends AbstractList<String> implements RandomAccess {

    /* specify a type's additional initialization requirements */
    public MyList(elem1: String) {
        super() /* explicit call to a supertype's implementation */
        this.add(elem1) /* might be overridden in a subtype of this type */
    }

}

/* use a type as one of its supertypes (implicit upcasting) */
List<String> l = new ArrayList<>() /* some inference is available for generics */

Informacje o częściowym typie środowiska wykonawczego

/* find the outermost actual type of a value at runtime */
Class<?> c = l.getClass // will be 'java.util.ArrayList'

/* query the relationship between runtime and compile-time types */
Boolean b = l instanceOf MyList // will be 'false'

Unikalny dla Haskell (w porównaniu z Javą)

Ograniczony polimorfizm ad-hoc

-- declare a parametrized bound
class A t where
  -- provide a function via this bound
  tInt :: t Int
  -- require other bounds within the functions provided by this bound
  mtInt :: Monad m => m (t Int)
  mtInt = return tInt -- define bound-provided functions via other bound-provided functions

-- fullfill a bound
instance A Maybe where
  tInt = Just 5
  mtInt = return Nothing -- override defaults

-- require exactly the bounds you need (ideally)
tString :: (Functor t, A t) => t String
tString = fmap show tInt -- use bounds that are implied by a concrete type (e.g., "Show Int")

Polimorfizm podtypu „oparty na ograniczeniach” (oparty na ograniczonym polimorfizmie ad-hoc)

-- declare that a bound implies other bounds (introduce a subbound)
class (A t, Applicative t) => B t where -- bounds don't have to provide functions

-- use multiple bounds (intersection types in the context, union types in the full type)
mtString :: (Monad m, B t) => m (t String)
mtString = return mtInt -- use a bound that is implied by another bound (implicit upcasting)

optString :: Maybe String
optString = join mtString -- full types are contravariant in their contexts

Lepszy parametryczny polimorfizm

-- parametrize types over type variables that are themselves parametrized
data OneOrTwoTs t x = OneVariableT (t x) | TwoFixedTs (t Int) (t String)

-- bounds can be higher-kinded, too
class MonadStrip s where
  -- use arbitrarily nested higher-kinded type variables
  strip :: (Monad m, MonadTrans t) => s t m a -> t m a -> m a

Główne pisanie

Trudno podać bezpośredni przykład tego, ale oznacza to, że każde wyrażenie ma dokładnie jeden maksymalnie ogólny typ (zwany jego głównym rodzajem ), który jest uważany za kanoniczny typ tego wyrażenia. W kategoriach polimorfizmu podtypu „opartego na ograniczeniach” (patrz wyżej), głównym typem wyrażenia jest unikalny podtyp każdego możliwego typu, którego można użyć tego wyrażenia. Obecność podstawowego pisania w (nie rozwiniętym) języku Haskell pozwala na pełne wnioskowanie o typie (czyli pomyślne wnioskowanie o typie dla każdego wyrażenia, bez potrzeby adnotacji typu). Rozszerzenia, które łamią podstawowe typowanie (których jest wiele), również łamią kompletność wnioskowania o typie.

Płomień Pthariena
źródło
7
Nie używaj ljako zmiennej jednuliterowej, bardzo BARDZO trudno ją odróżnić 1!
recursion.ninja
5
Warto zauważyć, że chociaż masz całkowitą rację, że Java ma pewne informacje o typie środowiska wykonawczego, a Haskell nie, możesz użyć klasy Typeable w Haskell, aby uzyskać coś, co zachowuje się jak informacja o typie środowiska wykonawczego dla wielu typów (z nowszym PolyKinded po drodze będą to wszystkie typy iirc), choć myślę, że zależy to od sytuacji, czy faktycznie przekazuje jakąkolwiek informację o typie w czasie wykonywania, czy nie.
3
@DarkOtter Jestem tego świadomy Typeable, ale Haskell 2010 go nie ma (może Haskell 2014 to zrobi?).
Ptharien's Flame,
5
Co z (zamkniętymi) rodzajami sum? Są jednym z ważniejszych mechanizmów kodowania ograniczeń.
tibbe
3
Nullability? Zdrowość (bez sillinów kowariancji)? Typy zamkniętych sum / dopasowania wzorca? Ta odpowiedź jest zbyt wąska
Peaker
32

W systemie typu Java brakuje polimorfizmu wyższego rzędu; System typów Haskell ma to.

Innymi słowy: w Javie konstruktory typów mogą abstrakcyjnie konstruować typy, ale nie konstruktory typów, podczas gdy w Haskell konstruktory typów mogą konstruować typy i konstruktory typów.

W języku angielskim: w Javie rodzajowy nie może przyjąć innego typu ogólnego i sparametryzować go,

public void <Foo> nonsense(Foo<Integer> i, Foo<String> j)

będąc w Haskell jest to dość łatwe

higherKinded :: Functor f => f Int -> f String
higherKinded = fmap show
Jörg W Mittag
źródło
28
Mógłbyś to powtórzyć, tym razem po angielsku? : P
Mason Wheeler,
8
@Matt: Jako przykład nie mogę napisać to w Javie, ale mogę napisać równowartość w Haskell: <T<_> extends Collection> T<Integer> convertStringsToInts(T<string> strings). Chodzi o to, że jeśli ktoś convertStringsToInts<ArrayList>nazwałby to tak, jak gdyby wziął tablicę ciągów znaków i zwrócił tablicę liczb całkowitych. A gdyby zamiast tego użyli convertStringsToInts<LinkedList>, to byłoby to samo z połączonymi listami.
sepp2k
8
Czy nie jest to bardziej uprzejmy polimorfizm niż ranga 1 vs n?
Adam,
8
@ JörgWMittag: Rozumiem, że polimorfizm wyższego rzędu dotyczy miejsc, w których można umieścić forallswoje typy. W Haskell typ a -> bjest niejawny forall a. forall b. a -> b. Dzięki rozszerzeniu możesz foralljawnie je przesuwać i przenosić.
Tikhon Jelvis
8
@Adam jest sztywny: wyższa ranga i wyższy rodzaj są zupełnie inne. GHC może również wykonywać typy o wyższej pozycji (tj. Wszystkie typy) z pewnym rozszerzeniem języka. Java nie zna typów o wyższym typie ani wyższego rankingu.
Ingo
11

Aby uzupełnić inne odpowiedzi, system typów Haskell nie ma podtytułów , podczas gdy pisane są zorientowane obiektowo języki jak Java.

W teorii języków programowania , podtypów (również podtypu polimorfizm lub polimorfizm integracji ) jest formą polimorfizmu typu , w którym podtyp to typ danych , który jest związany z innym typem danych (The supertypem ) przez jakiegoś pojęcia zastępowalności , co oznacza, że elementy programu, zazwyczaj Podprogramy lub funkcje napisane do działania na elementach nadtypu mogą również działać na elementach podtypu. Jeśli S jest podtypem T, relacja podtypu jest często zapisywana S <: T, co oznacza, że ​​dowolny termin typu S może być bezpiecznie używany w kontekście, w którymoczekuje się określenia typu T. Dokładna semantyka podtytułu zależy przede wszystkim od tego, co „bezpiecznie stosuje się w kontekście, w którym” oznacza w danym języku programowania. System typów języka programowania zasadniczo definiuje własną relację podsieci, która może być trywialna.

Ze względu na relację podtypu termin może należeć do więcej niż jednego typu. Podtypowanie jest zatem formą polimorfizmu typu. W programowaniu obiektowym termin „polimorfizm” jest powszechnie używany w odniesieniu do wyłącznie tego polimorfizmu podtypu , podczas gdy techniki polimorfizmu parametrycznego można by uznać za programowanie ogólne ...

Petr Pudlák
źródło
4
Chociaż nie oznacza to, że nie występuje polimorfizm ad hoc. Robisz to tylko w innej formie (klasy typów zamiast polimorfizmu podtypów).
3
Podklasa nie jest podtypem!
Frank Shearar
8

Jedną rzeczą, o której nikt dotąd nie wspominał, jest wnioskowanie o typie: kompilator Haskell zazwyczaj może wnioskować o typie wyrażeń, ale musisz szczegółowo powiedzieć kompilatorowi Java. Ściśle rzecz biorąc, jest to cecha kompilatora, ale konstrukcja języka i systemu typów określa, czy wnioskowanie typu jest możliwe. W szczególności wnioskowanie typu źle współdziała z polimorfizmem podtypu Java i przeciążeniem ad hoc. Natomiast projektanci Haskell starają się nie wprowadzać funkcji, które wpływają na wnioskowanie o typie.

Inną rzeczą, o której ludzie dotychczas nie wspominali, są algebraiczne typy danych. Oznacza to zdolność do konstruowania typów z sum („lub”) oraz produktów („i”) innych typów. Klasy Java wykonują produkty (powiedzmy pole A i pole B). Ale tak naprawdę nie robią sum (powiedzmy pole A LUB pole b). Scala musi zakodować to jako wiele klas spraw, co nie jest dokładnie takie samo. I choć działa dla Scali, to trochę trudno powiedzieć, że Java ma.

Haskell może także konstruować typy funkcji za pomocą konstruktora funkcji, ->. Chociaż metody Java mają podpisy typów, nie można ich łączyć.

System typów Java umożliwia modułowość, której Haskell nie ma. Upłynie trochę czasu, zanim pojawi się OSGi dla Haskella.

GarethR
źródło
1
@MattFenwick, zmodyfikowałem akapit trzeci na podstawie opinii użytkowników. Oba systemy typu traktują funkcje bardzo różnie.
GarethR
Nie nazwałbym ADT funkcją systemu typów. Możesz w pełni (jeśli niezręcznie) emulować je za pomocą opakowań OO.
leftaroundabout
@leftaroundabout Myślę, że to prawdopodobnie. Na przykład mogą istnieć rzeczy, które są rodzime dla systemu typów jednego języka, ale mogą być zaimplementowane z wzorcami projektowymi w innym. Oczywiście sposób wzorca projektowego, w porównaniu z rodzimym, jest obejściem. Obejście ze względu na słabszy system typów.
Cześć Anioł
Wybrana odpowiedź wspomniała o „pełnym wnioskowaniu o typie” w sekcji „Główne typowanie”. Java może w pewien sposób emulować sumy z podtypami i informacjami o typie środowiska wykonawczego, ale jak mówisz, nie jest to to samo, ponieważ suma nie jest holistycznym atrybutem systemu typów.
Shelby Moore III