Klarifikasi tentang Jenis Eksistensial di Haskell

Saya mencoba memahami tipe Eksistensial di Haskell dan menemukan PDF http://www.ii.uni.wroc.pl/~dabi/courses/ZPF15/rlasocha/prezentacja.pdf

Harap perbaiki pemahaman saya di bawah yang saya miliki sampai sekarang.

• Jenis Eksistensial tampaknya tidak tertarik pada jenis yang dikandungnya tetapi pola yang cocok dengan mereka mengatakan bahwa ada beberapa jenis kita tidak tahu apa jenisnya sampai & kecuali kita menggunakan Typeable atau Data.
• Kami menggunakannya ketika kami ingin Sembunyikan jenis (mis: untuk Daftar Heterogen) atau kami tidak benar-benar tahu jenis apa pada Waktu Kompilasi.
• GADT's menyediakan sintaks yang jelas & lebih baik untuk kode menggunakan Jenis eksistensial dengan menyediakan implisit forall' s

Keraguan saya

• Dalam PDF di atas disebutkan untuk kode di bawah ini bahwa tidak mungkin bagi suatu Fungsi untuk meminta Buffer tertentu. Kenapa gitu? Ketika saya menyusun Fungsi Saya tahu persis jenis buffer yang akan saya gunakan walaupun saya mungkin tidak tahu data apa yang akan saya masukkan ke dalamnya. Apa yang salah dalam Memiliki :: Worker MemoryBuffer IntJika mereka benar-benar ingin abstrak lebih dari Buffer mereka dapat memiliki tipe Sum data Buffer = MemoryBuffer | NetBuffer | RandomBufferdan memiliki tipe suka:: Worker Buffer Int

data Worker x = forall b. Buffer b => Worker {buffer :: b, input :: x}
data MemoryBuffer = MemoryBuffer

memoryWorker = Worker MemoryBuffer (1 :: Int)
memoryWorker :: Worker Int

• Karena Haskell adalah bahasa Erasure Jenis Lengkap seperti C lalu Bagaimana ia tahu di Runtime yang berfungsi untuk memanggil. Apakah itu sesuatu seperti kita akan menyimpan sedikit informasi dan meneruskan dalam V-Table of Functions yang Besar dan pada saat runtime akan mencari tahu dari V-Table? Jika demikian maka Informasi macam apa yang akan disimpannya?

GADT menyediakan sintaks yang jelas & lebih baik untuk kode menggunakan Jenis Eksistensial dengan menyediakan forall's implisit

Saya pikir ada kesepakatan umum bahwa sintaks GADT lebih baik. Saya tidak akan mengatakan bahwa itu karena GADTs menyediakan foralls implisit, tetapi lebih karena sintaks asli, diaktifkan dengan ExistentialQuantificationekstensi, berpotensi membingungkan / menyesatkan. Sintaks itu, tentu saja, terlihat seperti:

data SomeType = forall a. SomeType a

atau dengan batasan:

data SomeShowableType = forall a. Show a => SomeShowableType a

dan saya pikir konsensusnya adalah bahwa penggunaan kata kunci di forallsini memungkinkan jenisnya mudah dikacaukan dengan jenis yang sama sekali berbeda:

data AnyType = AnyType (forall a. a)    -- need RankNTypes extension

Sintaks yang lebih baik mungkin menggunakan existskata kunci terpisah , jadi Anda akan menulis:

data SomeType = SomeType (exists a. a)   -- not valid GHC syntax

Sintaks GADT, apakah digunakan dengan implisit atau eksplisit forall, lebih seragam di semua tipe ini, dan tampaknya lebih mudah dipahami. Bahkan dengan eksplisit forall, definisi berikut menemukan gagasan bahwa Anda dapat mengambil nilai dari jenis apa pun adan memasukkannya ke dalam monomorfik SomeType':

data SomeType' where
    SomeType' :: forall a. (a -> SomeType')   -- parentheses optional

dan mudah untuk melihat dan memahami perbedaan antara tipe itu dan:

data AnyType' where
    AnyType' :: (forall a. a) -> AnyType'

Jenis Eksistensial tampaknya tidak tertarik pada jenis yang dikandungnya tetapi pola yang cocok dengan mereka mengatakan bahwa ada beberapa jenis kita tidak tahu apa jenisnya sampai & kecuali kita menggunakan Typeable atau Data.

Kami menggunakannya ketika kami ingin Sembunyikan jenis (mis: untuk Daftar Heterogen) atau kami tidak benar-benar tahu jenis apa pada Waktu Kompilasi.

Saya kira ini tidak terlalu jauh, meskipun Anda tidak harus menggunakan Typeableatau Datamenggunakan tipe eksistensial. Saya pikir akan lebih akurat untuk mengatakan tipe eksistensial menyediakan "kotak" yang diketik dengan baik di sekitar tipe yang tidak ditentukan. Kotak itu memang "menyembunyikan" jenis itu dalam arti tertentu, yang memungkinkan Anda membuat daftar kotak yang heterogen, mengabaikan jenis yang dikandungnya. Ternyata eksistensial tanpa SomeType'kendala , seperti di atas cukup berguna, tetapi tipe dibatasi:

data SomeShowableType' where
    SomeShowableType' :: forall a. (Show a) => a -> SomeShowableType'

memungkinkan Anda untuk mencocokkan pola untuk mengintip ke dalam "kotak" dan membuat fasilitas kelas tipe tersedia:

showIt :: SomeShowableType' -> String
showIt (SomeShowableType' x) = show x

Perhatikan bahwa ini berfungsi untuk semua tipe kelas, bukan hanya Typeableatau Data.

Berkenaan dengan kebingungan Anda tentang halaman 20 dari slide deck, penulis mengatakan bahwa tidak mungkin untuk suatu fungsi yang memerlukan eksistensial Worker untuk menuntut Workermemiliki Bufferinstance tertentu . Anda dapat menulis fungsi untuk membuat Workermenggunakan jenis tertentu Buffer, seperti MemoryBuffer:

class Buffer b where
  output :: String -> b -> IO ()
data Worker x = forall b. Buffer b => Worker {buffer :: b, input :: x}
data MemoryBuffer = MemoryBuffer
instance Buffer MemoryBuffer

memoryWorker = Worker MemoryBuffer (1 :: Int)
memoryWorker :: Worker Int

tetapi jika Anda menulis fungsi yang menggunakan Workerargumen, ia hanya dapat menggunakan Bufferfasilitas kelas tipe umum (mis., fungsi output):

doWork :: Worker Int -> IO ()
doWork (Worker b x) = output (show x) b

Itu tidak dapat mencoba untuk meminta bjenis buffer tertentu, bahkan melalui pencocokan pola:

doWorkBroken :: Worker Int -> IO ()
doWorkBroken (Worker b x) = case b of
  MemoryBuffer -> error "try this"       -- type error
  _            -> error "try that"

Akhirnya, informasi runtime tentang tipe-tipe eksistensial tersedia melalui argumen "kamus" implisit untuk typeclasses yang terlibat. The Workertipe di atas, selain produk yang memiliki kolom untuk buffer dan masukan, juga memiliki medan implisit tak terlihat yang menunjuk ke Bufferkamus (agak seperti v-meja, meskipun itu tidak besar, karena hanya berisi pointer ke sesuai outputfungsi).

Secara internal, kelas tipe Bufferdirepresentasikan sebagai tipe data dengan bidang fungsi, dan instance adalah "kamus" dari tipe ini:

data Buffer' b = Buffer' { output' :: String -> b -> IO () }

dBuffer_MemoryBuffer :: Buffer' MemoryBuffer
dBuffer_MemoryBuffer = Buffer' { output' = undefined }

Jenis eksistensial memiliki bidang tersembunyi untuk kamus ini:

data Worker' x = forall b. Worker' { dBuffer :: Buffer' b, buffer' :: b, input' :: x }

dan fungsi seperti doWorkitu beroperasi pada Worker'nilai-nilai eksistensial diimplementasikan sebagai:

doWork' :: Worker' Int -> IO ()
doWork' (Worker' dBuf b x) = output' dBuf (show x) b

Untuk kelas tipe dengan hanya satu fungsi, kamus sebenarnya dioptimalkan untuk tipe baru, jadi dalam contoh ini, Workertipe eksistensial mencakup bidang tersembunyi yang terdiri dari penunjuk fungsi ke outputfungsi buffer, dan itulah satu-satunya informasi runtime yang diperlukan oleh doWork.

Dalam PDF di atas disebutkan untuk kode di bawah ini bahwa tidak mungkin bagi suatu Fungsi untuk meminta Buffer tertentu. Kenapa gitu?

Karena Worker, sebagaimana didefinisikan, hanya membutuhkan satu argumen, jenis bidang "input" (tipe variabel x). Misalnya Worker Intadalah tipe. Variabel tipe b, sebaliknya, bukan parameter dari Worker, tetapi merupakan semacam "variabel lokal", jadi untuk berbicara. Itu tidak bisa diteruskan seperti di Worker Int String- yang akan memicu kesalahan ketik.

Jika kita mendefinisikan:

data Worker x b = Worker {buffer :: b, input :: x}

maka Worker Int Stringakan berfungsi, tetapi jenisnya tidak lagi eksistensial - kita sekarang selalu harus melewati jenis penyangga juga.

Karena Haskell adalah bahasa Erasure Jenis Lengkap seperti C lalu Bagaimana ia tahu di Runtime yang berfungsi untuk memanggil. Apakah itu sesuatu seperti kita akan menyimpan sedikit informasi dan meneruskan dalam V-Table of Functions yang Besar dan pada saat runtime akan mencari tahu dari V-Table? Jika demikian maka Informasi macam apa yang akan disimpannya?

Ini kira-kira benar. Secara singkat, setiap kali Anda menerapkan konstruktor Worker, GHC menyimpulkan bjenis dari argumen Worker, dan kemudian mencari contoh Buffer b. Jika itu ditemukan, GHC menyertakan pointer tambahan ke instance dalam objek. Dalam bentuknya yang paling sederhana, ini tidak terlalu berbeda dari "pointer to vtable" yang ditambahkan ke setiap objek dalam OOP ketika ada fungsi virtual.

Dalam kasus umum, ini bisa menjadi jauh lebih kompleks. Compiler mungkin menggunakan representasi yang berbeda dan menambahkan lebih banyak pointer daripada satu (katakanlah, langsung menambahkan pointer ke semua metode contoh), jika itu mempercepat kode. Juga, kadang-kadang kompiler perlu menggunakan beberapa instance untuk memenuhi batasan. Misalnya, jika kita perlu menyimpan instance untuk Eq [Int]... maka tidak hanya ada satu tetapi dua: satu untuk Intdan satu untuk daftar, dan keduanya perlu digabungkan (pada saat run time, kecuali optimasi).

Sulit untuk menebak dengan tepat apa yang dilakukan GHC dalam setiap kasus: itu tergantung pada satu ton optimisasi yang mungkin atau mungkin tidak memicu.

Anda bisa mencoba googling untuk implementasi kelas tipe "berbasis kamus" untuk melihat lebih banyak tentang apa yang terjadi. Anda juga dapat meminta GHC untuk mencetak Core yang dioptimalkan internal dengan -ddump-simpldan mengamati kamus yang dibangun, disimpan, dan diedarkan. Saya harus memperingatkan Anda: Core agak rendah, dan mungkin sulit dibaca pada awalnya.