Apakah sistem tipe Haskell secara formal setara dengan Java? [Tutup]

66

Saya menyadari beberapa hal lebih mudah / lebih sulit dalam satu bahasa daripada yang lain, tetapi saya hanya tertarik pada fitur terkait jenis yang mungkin dalam satu bahasa dan tidak mungkin / tidak relevan dengan yang lain. Untuk membuatnya lebih spesifik, mari kita abaikan ekstensi jenis Haskell karena ada begitu banyak di luar sana yang melakukan semua jenis hal gila / keren.

GlenPeterson
sumber
4
Saya juga penasaran mendengar teori kategori bertele-tele menjawab pertanyaan ini; meskipun saya ragu saya akan memahaminya secara khusus, saya masih tertarik dengan perincian ini. Kecenderungan saya dari hal-hal yang saya baca adalah bahwa sistem tipe HM memungkinkan kompiler untuk mengetahui banyak tentang apa yang kode Anda lakukan, itulah mengapa ia mampu menyimpulkan tipe begitu banyak serta memberikan begitu banyak jaminan tentang perilaku tersebut. Tapi itu hanya naluri saya dan saya yakin ada hal-hal lain yang sama sekali tidak saya sadari.
Jimmy Hoffa
1
Ini adalah pertanyaan yang bagus - saatnya untuk mengirimkan tweet ke pengikut untuk debat hebat Haskell / JVM!
Martijn Verburg
6
@ m3th0dman: Scala memiliki dukungan yang sama persis untuk fungsi tingkat tinggi seperti yang dimiliki Java. Dalam Scala, fungsi kelas satu hanya direpresentasikan sebagai instance dari kelas abstrak dengan metode abstrak tunggal, seperti halnya Java. Tentu saja, Scala memiliki gula sintaksis untuk mendefinisikan fungsi-fungsi ini, dan ia memiliki pustaka standar yang kaya dari kedua tipe fungsi dan metode yang telah didefinisikan yang menerima fungsi, tetapi dari perspektif sistem tipe , yang menjadi pertanyaan pertanyaan ini, tidak ada perbedaan . Jadi, jika Scala bisa melakukannya, maka Java juga bisa, dan sebenarnya ada perpustakaan FP yang terinspirasi Haskell untuk Java.
Jörg W Mittag
2
@ m3th0dman: Bukan itu pertanyaannya.
Phil
7
@ m3th0dman Mereka tipe yang sangat biasa. Tidak ada yang istimewa dari daftar kecuali beberapa sifat sintaksis. Anda dapat dengan mudah menentukan tipe data aljabar Anda sendiri yang setara dengan tipe daftar bawaan kecuali untuk sintaks literal dan nama-nama konstruktor.
sepp2k

Jawaban:

63

("Java", seperti yang digunakan di sini, didefinisikan sebagai standar Java SE 7 ; "Haskell", seperti yang digunakan di sini, didefinisikan sebagai standar Haskell 2010. )

Hal-hal yang dimiliki sistem tipe Java tetapi Haskell tidak:

  • polimorfisme subtipe nominal
  • informasi jenis runtime parsial

Hal-hal yang dimiliki sistem tipe Haskell tetapi Java tidak:

  • polimorfisme ad-hoc terbatas
    • memunculkan polimorfisme subtipe "berbasis kendala"
  • polimorfisme parametrik yang lebih tinggi
  • pengetikan utama

SUNTING:

Contoh masing-masing poin yang tercantum di atas:

Unik untuk Jawa (dibandingkan dengan Haskell)

Polimorfisme subtipe nominal

/* 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 */

Informasi jenis runtime parsial

/* 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'

Unik untuk Haskell (dibandingkan dengan Jawa)

Polimorfisme ad-hoc terbatas

-- 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")

Polimorfisme subtipe "berbasis kendala" (berdasarkan polimorfisme ad-hoc terbatas)

-- 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

Polimorfisme parametrik yang lebih baik

-- 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

Pengetikan kepala sekolah

Yang ini sulit untuk memberikan contoh langsung, tetapi itu berarti bahwa setiap ungkapan memiliki tepat satu jenis umum secara maksimal (disebut jenis utamanya ), yang dianggap sebagai jenis kanonik dari ungkapan itu. Dalam hal polimorfisme subtipe "berbasis kendala" (lihat di atas), tipe utama dari sebuah ekspresi adalah subtipe unik dari setiap jenis yang mungkin digunakan untuk ekspresi tersebut. Kehadiran pengetikan utama dalam (tidak diperluas) Haskell adalah yang memungkinkan inferensi tipe lengkap (yaitu, inferensi tipe yang berhasil untuk setiap ekspresi, tanpa anotasi jenis apa pun yang diperlukan). Ekstensi yang melanggar pengetikan utama (yang jumlahnya banyak) juga merusak kelengkapan inferensi tipe.

Api Ptharien
sumber
7
Jangan gunakan lsebagai variabel huruf tunggal, itu SANGAT sulit untuk dibedakan 1!
recursion.ninja
5
Mungkin perlu dicatat, bahwa walaupun Anda benar bahwa Java memiliki beberapa informasi tipe runtime dan Haskell tidak, Anda dapat menggunakan kelas tipe-tipe di Haskell untuk menyediakan sesuatu yang berperilaku seperti informasi tipe runtime untuk banyak jenis (dengan PolyKinded yang lebih baru kelas di jalan, itu akan menjadi semua jenis iirc), meskipun saya pikir itu tergantung pada situasi apakah itu benar-benar melewati informasi jenis apa pun pada saat runtime atau tidak.
3
@DarkOtter saya tahu Typeable, tapi Haskell 2010 tidak memilikinya (mungkin Haskell 2014 akan melakukannya?).
Flame Ptharien,
5
Bagaimana dengan tipe penjumlahan (tertutup)? Mereka adalah salah satu mekanisme yang lebih penting untuk kendala pengkodean.
tibbe
3
Nullability? Kesehatan (tidak ada kovarians sillinses)? Jenis / pola jumlah tertutup cocok? Jawaban ini terlalu sempit
Peaker
32

Sistem tipe Java tidak memiliki polimorfisme jenis yang lebih tinggi; Sistem tipe Haskell memilikinya.

Dengan kata lain: di Jawa, konstruktor tipe dapat abstrak lebih dari tipe, tetapi tidak lebih dari tipe konstruktor, sedangkan di Haskell, tipe konstruktor dapat abstrak lebih dari tipe konstruktor serta tipe.

Dalam bahasa Inggris: di Java generik tidak dapat mengambil tipe generik lain dan parameterisasi itu,

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

sementara di Haskell ini cukup mudah

higherKinded :: Functor f => f Int -> f String
higherKinded = fmap show
Jörg W Mittag
sumber
28
Pikiran menjalankan itu oleh kita lagi, dalam bahasa Inggris saat ini? : P
Mason Wheeler
8
@ Matt: Sebagai contoh saya tidak bisa menulis ini di Jawa, tapi aku bisa menulis setara dalam Haskell: <T<_> extends Collection> T<Integer> convertStringsToInts(T<string> strings). Idenya di sini adalah bahwa jika seseorang memanggilnya karena convertStringsToInts<ArrayList>akan mengambil arraylist string dan mengembalikan arraylist integer. Dan jika mereka malah digunakan convertStringsToInts<LinkedList>, itu akan sama dengan daftar yang terhubung sebagai gantinya.
sepp2k
8
Bukankah ini polimorfisme jenis yang lebih tinggi, daripada peringkat 1 vs n?
Adam
8
@ JörgWMittag: Pemahaman saya adalah bahwa polimorfisme tingkat tinggi menyangkut di mana Anda dapat memasukkan foralltipe Anda. Dalam Haskell, suatu tipe a -> bsecara implisit forall a. forall b. a -> b. Dengan ekstensi, Anda bisa membuatnya lebih foralleksplisit dan memindahkannya.
Tikhon Jelvis
8
@ Adam adalah rigtht: peringkat yang lebih tinggi dan jenis yang lebih tinggi sama sekali berbeda. GHC juga dapat melakukan jenis peringkat yang lebih tinggi (yaitu untuk semua jenis) dengan beberapa ekstensi bahasa. Java tidak tahu jenis yang lebih tinggi atau jenis peringkat yang lebih tinggi.
Ingo
11

Untuk melengkapi jawaban lainnya, sistem tipe Haskell tidak memiliki subtyping , sedangkan bahasa berorientasi objek yang diketikkan seperti halnya Java.

Dalam teori bahasa pemrograman , subtipe (juga subtipe polimorfisme atau polimorfisme inklusi ) adalah bentuk polimorfisme tipe di mana subtipe adalah tipe data yang terkait dengan tipe data lain ( supertipe ) oleh beberapa gagasan tentang substitusi , artinya elemen program, biasanya subrutin atau fungsi, ditulis untuk beroperasi pada elemen supertype juga dapat beroperasi pada elemen subtipe. Jika S adalah subtipe dari T, relasi subtyping sering dituliskan S <: T, yang berarti bahwa setiap istilah tipe S dapat digunakan dengan aman dalam konteks di manaistilah tipe T diharapkan. Semantik yang tepat dari subtyping secara krusial tergantung pada keterangan dari apa yang "aman digunakan dalam konteks di mana" berarti dalam bahasa pemrograman yang diberikan. The jenis sistem dari bahasa pemrograman dasarnya mendefinisikan hubungan subtyping sendiri, yang mungkin sepele.

Karena hubungan subtyping, suatu istilah dapat memiliki lebih dari satu jenis. Subtyping karena itu merupakan bentuk polimorfisme tipe. Dalam pemrograman berorientasi objek, istilah 'polimorfisme' umumnya digunakan untuk merujuk semata-mata pada polimorfisme subtipe ini , sedangkan teknik-teknik polimorfisme parametrik akan dianggap sebagai pemrograman generik ...

Petr Pudlák
sumber
4
Meskipun itu tidak berarti Anda tidak mendapatkan polimorfisme ad-hoc. Anda lakukan, hanya dalam bentuk yang berbeda (ketik kelas bukan polimorfisme subtipe).
3
Subclassing bukan subtyping!
Frank Shearar
8

Satu hal yang tidak ada yang disebutkan sejauh ini adalah tipe inferensi: kompiler Haskell biasanya dapat menyimpulkan jenis ekspresi tetapi Anda harus memberi tahu kompiler Java tipe Anda secara detail. Sebenarnya, ini adalah fitur dari kompiler tetapi desain bahasa dan sistem tipe menentukan apakah inferensi tipe layak atau tidak. Secara khusus, tipe inferensi berinteraksi buruk dengan polimorfisme subtipe Java dan kelebihan ad hoc. Sebaliknya, para perancang Haskell berusaha keras untuk tidak memperkenalkan fitur-fitur yang berdampak pada inferensi tipe.

Hal lain yang tampaknya belum disebutkan orang sejauh ini adalah tipe data aljabar. Yaitu, kemampuan untuk membangun tipe dari penjumlahan ('atau') dan produk ('dan') dari tipe lain. Kelas Java melakukan produk (bidang a dan bidang b, katakanlah) baik-baik saja. Tetapi mereka tidak benar-benar melakukan penjumlahan (bidang a atau bidang b, katakanlah). Scala harus menyandikan ini sebagai beberapa kelas kasus, yang tidak persis sama. Dan sementara ini bekerja untuk Scala, agak sulit untuk mengatakan bahwa Java memilikinya.

Haskell juga dapat membuat tipe fungsi menggunakan function constructor, ->. Meskipun metode Java memiliki tanda tangan jenis, Anda tidak bisa menggabungkannya.

Sistem tipe Java memang memungkinkan jenis modularitas yang tidak dimiliki Haskell. Akan lama sebelum ada OSGi untuk Haskell.

GarethR
sumber
1
@MattFenwick, saya memodifikasi paragraf ke-3 berdasarkan umpan balik Anda. Kedua jenis sistem tersebut memperlakukan fungsi dengan sangat berbeda.
GarethR
Saya tidak akan menyebut ADT sebagai fitur dari sistem tipe. Anda dapat sepenuhnya (jika canggung) meniru mereka dengan pembungkus OO.
leftaroundabout
@ Leftaroundabout Saya pikir ini bisa dibilang. Misalnya, mungkin ada hal-hal yang berasal dari sistem tipe satu bahasa, tetapi dapat diimplementasikan dengan pola desain dalam bahasa lain. Jelas, cara pola desain, dibandingkan dengan yang asli, adalah solusi. Solusi karena sistem tipe yang lebih lemah.
Hi-Angel
Jawaban yang dipilih disebutkan 'inferensi tipe lengkap' di bagian 'Pengetikan kepala sekolah'. Java dapat mengurutkan jumlah yang ditiru dengan subtipe dan informasi jenis runtime, tetapi seperti yang Anda katakan itu tidak sama dengan jumlah bukanlah atribut holistik dari sistem tipe.
Shelby Moore III