Ada alasan mengapa scala tidak secara eksplisit mendukung tipe dependen?

Ada tipe yang bergantung pada jalur dan saya pikir dimungkinkan untuk mengekspresikan hampir semua fitur bahasa seperti Epigram atau Agda di Scala, tetapi saya bertanya-tanya mengapa Scala tidak mendukung ini secara lebih eksplisit seperti yang dilakukannya dengan sangat baik di area lain (katakanlah , DSLs)? Adakah yang saya lewatkan seperti "tidak perlu"?

Kenyamanan sintaksis samping, kombinasi jenis tunggal, jenis jalan-dependent dan nilai-nilai implisit berarti bahwa Scala memiliki dukungan mengejutkan baik untuk mengetik tergantung, karena saya sudah mencoba untuk menunjukkan di berbentuk .

Dukungan intrinsik Scala untuk tipe dependen adalah melalui tipe yang bergantung pada jalur . Ini memungkinkan tipe bergantung pada jalur pemilih melalui grafik objek- (mis. Nilai-) seperti itu,

scala> class Foo { class Bar }
defined class Foo

scala> val foo1 = new Foo
foo1: Foo = Foo@24bc0658

scala> val foo2 = new Foo
foo2: Foo = Foo@6f7f757

scala> implicitly[foo1.Bar =:= foo1.Bar] // OK: equal types
res0: =:=[foo1.Bar,foo1.Bar] = <function1>

scala> implicitly[foo1.Bar =:= foo2.Bar] // Not OK: unequal types
<console>:11: error: Cannot prove that foo1.Bar =:= foo2.Bar.
              implicitly[foo1.Bar =:= foo2.Bar]

Dalam pandangan saya, pertanyaan di atas seharusnya cukup untuk menjawab pertanyaan "Apakah Scala merupakan bahasa yang diketik dengan ketergantungan?" di positif: jelas bahwa di sini kami memiliki tipe yang dibedakan oleh nilai yang merupakan awalannya.

Namun, sering kali ada keberatan bahwa Scala bukanlah bahasa jenis yang "sepenuhnya" bergantung karena tidak memiliki jumlah dan jenis produk yang bergantung seperti yang ditemukan di Agda atau Coq atau Idris sebagai intrinsik. Saya pikir ini mencerminkan fiksasi pada bentuk atas dasar-dasar sampai batas tertentu, namun, saya akan mencoba dan menunjukkan bahwa Scala jauh lebih dekat dengan bahasa lain ini daripada yang biasanya diakui.

Terlepas dari terminologi, tipe penjumlahan dependen (juga dikenal sebagai tipe Sigma) hanyalah sepasang nilai di mana tipe nilai kedua bergantung pada nilai pertama. Ini secara langsung dapat direpresentasikan di Scala,

scala> trait Sigma {
     |   val foo: Foo
     |   val bar: foo.Bar
     | }
defined trait Sigma

scala> val sigma = new Sigma {
     |   val foo = foo1
     |   val bar = new foo.Bar
     | }
sigma: java.lang.Object with Sigma{val bar: this.foo.Bar} = $anon$1@e3fabd8

dan faktanya, ini adalah bagian penting dari pengkodean tipe metode dependen yang diperlukan untuk keluar dari 'Bakery of Doom' di Scala sebelum 2.10 (atau sebelumnya melalui opsi compiler Scala tipe metode dependen eksperimental).

Tipe produk dependen (alias tipe Pi) pada dasarnya adalah fungsi dari nilai ke tipe. Mereka adalah kunci untuk representasi vektor berukuran statis dan turunan poster lainnya untuk bahasa pemrograman yang diketik secara dependen. Kita bisa mengenkode tipe Pi di Scala menggunakan kombinasi tipe path dependent, tipe singleton dan parameter implisit. Pertama kita mendefinisikan sifat yang akan mewakili fungsi dari nilai tipe T ke tipe U,

scala> trait Pi[T] { type U }
defined trait Pi

Kita dapat mendefinisikan metode polimorfik yang menggunakan tipe ini,

scala> def depList[T](t: T)(implicit pi: Pi[T]): List[pi.U] = Nil
depList: [T](t: T)(implicit pi: Pi[T])List[pi.U]

(perhatikan penggunaan tipe yang bergantung pi.Upada jalur dalam tipe hasil List[pi.U]). Diberikan nilai tipe T, fungsi ini akan mengembalikan (n kosong) daftar nilai tipe yang sesuai dengan nilai T tertentu.

Sekarang mari kita tentukan beberapa nilai yang sesuai dan saksi implisit untuk hubungan fungsional yang ingin kita pegang,

scala> object Foo
defined module Foo

scala> object Bar
defined module Bar

scala> implicit val fooInt = new Pi[Foo.type] { type U = Int }
fooInt: java.lang.Object with Pi[Foo.type]{type U = Int} = $anon$1@60681a11

scala> implicit val barString = new Pi[Bar.type] { type U = String }
barString: java.lang.Object with Pi[Bar.type]{type U = String} = $anon$1@187602ae

Dan sekarang inilah fungsi penggunaan tipe-Pi kami yang sedang beraksi,

scala> depList(Foo)
res2: List[fooInt.U] = List()

scala> depList(Bar)
res3: List[barString.U] = List()

scala> implicitly[res2.type <:< List[Int]]
res4: <:<[res2.type,List[Int]] = <function1>

scala> implicitly[res2.type <:< List[String]]
<console>:19: error: Cannot prove that res2.type <:< List[String].
              implicitly[res2.type <:< List[String]]
                    ^

scala> implicitly[res3.type <:< List[String]]
res6: <:<[res3.type,List[String]] = <function1>

scala> implicitly[res3.type <:< List[Int]]
<console>:19: error: Cannot prove that res3.type <:< List[Int].
              implicitly[res3.type <:< List[Int]]

(perhatikan bahwa di sini kami menggunakan <:<operator menyaksikan subtipe Scala daripada =:=karena res2.typedan res3.typemerupakan tipe tunggal dan karenanya lebih tepat daripada tipe yang kami verifikasi di RHS).

Dalam praktiknya, bagaimanapun, di Scala kami tidak akan mulai dengan mengkodekan tipe Sigma dan Pi dan kemudian melanjutkan dari sana seperti yang kami lakukan di Agda atau Idris. Sebagai gantinya kita akan menggunakan tipe yang bergantung pada jalur, tipe tunggal dan implikasinya secara langsung. Anda dapat menemukan banyak contoh bagaimana hal ini dimainkan dalam bentuk tak berbentuk: tipe ukuran , catatan yang dapat diperluas , Daftar HL yang komprehensif , memo plat boiler Anda , Resleting generik dll. Dll.

Keberatan yang tersisa yang dapat saya lihat adalah bahwa dalam pengkodean tipe Pi di atas kita membutuhkan tipe tunggal dari nilai dependen agar dapat diekspresikan. Sayangnya di Scala ini hanya mungkin untuk nilai tipe referensi dan bukan untuk nilai tipe non-referensi (esp. Misalnya Int). Ini adalah rasa malu, tapi bukan kesulitan intrinsik: Scala jenis checker merupakan jenis tunggal dari nilai-nilai non-referensi internal, dan telah ada beberapa dari percobaan dalam membuat mereka secara langsung dinyatakan. Dalam praktiknya kita dapat mengatasi masalah dengan pengkodean tingkat tipe yang cukup standar dari bilangan asli .

Bagaimanapun, menurut saya batasan domain kecil ini tidak dapat digunakan sebagai keberatan terhadap status Scala sebagai bahasa yang diketik secara dependen. Jika ya, maka hal yang sama dapat dikatakan untuk Dependent ML (yang hanya memungkinkan ketergantungan pada nilai bilangan asli) yang akan menjadi kesimpulan yang aneh.

Saya akan berasumsi itu karena (seperti yang saya ketahui dari pengalaman, telah menggunakan tipe dependen dalam asisten bukti Coq, yang sepenuhnya mendukung mereka tetapi masih tidak dengan cara yang sangat nyaman) tipe dependen adalah fitur bahasa pemrograman yang sangat canggih yang sangat sulit untuk digunakan. menjadi benar - dan dapat menyebabkan ledakan eksponensial dalam kompleksitas dalam praktiknya. Mereka masih menjadi topik penelitian ilmu komputer.

Saya percaya bahwa tipe-tipe yang bergantung pada jalur Scala hanya dapat mewakili tipe-but, tetapi tidak tipe-Π. Ini:

trait Pi[T] { type U }

bukanlah tipe Π. Menurut definisi, Π-type, atau dependent product, adalah suatu fungsi yang jenis hasilnya bergantung pada nilai argumen, mewakili pembilang universal, yaitu ∀x: A, B (x). Namun, dalam kasus di atas, ini hanya bergantung pada tipe T, tetapi tidak pada beberapa nilai tipe ini. Sifat pi sendiri adalah tipe-, pembilang eksistensial, yaitu ∃x: A, B (x). Referensi diri objek dalam hal ini bertindak sebagai variabel terkuantifikasi. Ketika diteruskan sebagai parameter implisit, bagaimanapun, itu mereduksi menjadi fungsi tipe biasa, karena diselesaikan berdasarkan tipe. Pengkodean untuk produk dependen di Scala mungkin terlihat seperti berikut:

trait Sigma[T] {
  val x: T
  type U //can depend on x
}

// (t: T) => (∃ mapping(x, U), x == t) => (u: U); sadly, refinement won't compile
def pi[T](t: T)(implicit mapping: Sigma[T] { val x = t }): mapping.U 

Bagian yang hilang di sini adalah kemampuan untuk membatasi bidang x secara statis ke nilai t yang diharapkan, secara efektif membentuk persamaan yang mewakili properti dari semua nilai yang mendiami tipe T. Bersama dengan tipe-Σ kami, digunakan untuk mengungkapkan keberadaan objek dengan properti yang diberikan, logika terbentuk, di mana persamaan kita menjadi teorema yang harus dibuktikan.

Di samping catatan, dalam kasus nyata teorema mungkin sangat tidak sepele, sampai pada titik di mana ia tidak dapat secara otomatis diturunkan dari kode atau diselesaikan tanpa usaha yang signifikan. Hipotesis Riemann bahkan dapat dirumuskan dengan cara ini, hanya untuk menemukan tanda tangan tidak mungkin diterapkan tanpa benar-benar membuktikannya, mengulang selamanya atau membuat pengecualian.

Pertanyaannya adalah tentang penggunaan fitur pengetikan dependen secara lebih langsung dan, menurut saya, akan ada manfaatnya memiliki pendekatan pengetikan dependen yang lebih langsung daripada yang ditawarkan Scala.
Jawaban saat ini mencoba untuk memperdebatkan pertanyaan pada tipe tingkat teoritis. Saya ingin melakukan putaran yang lebih pragmatis. Ini mungkin menjelaskan mengapa orang-orang terbagi pada tingkat dukungan dari tipe-tipe yang bergantung dalam bahasa Scala. Kami mungkin memiliki definisi yang agak berbeda dalam pikiran. (bukan untuk mengatakan yang satu benar dan yang satu salah).

Ini bukan upaya untuk menjawab pertanyaan seberapa mudah mengubah Scala menjadi sesuatu seperti Idris (menurut saya sangat sulit) atau untuk menulis perpustakaan yang menawarkan dukungan lebih langsung untuk kemampuan seperti Idris (seperti singletonsmencoba berada di Haskell).

Sebaliknya, saya ingin menekankan perbedaan pragmatis antara Scala dan bahasa seperti Idris.
Apa bit kode untuk ekspresi tingkat nilai dan tipe? Idris menggunakan kode yang sama, Scala menggunakan kode yang sangat berbeda.

Scala (mirip dengan Haskell) mungkin dapat mengenkode banyak penghitungan level tipe. Ini ditunjukkan oleh perpustakaan seperti shapeless. Perpustakaan ini melakukannya dengan menggunakan beberapa trik yang sangat mengesankan dan pintar. Namun, kode level tipe mereka (saat ini) sangat berbeda dari ekspresi level nilai (saya menemukan celah itu agak lebih dekat di Haskell). Idris memungkinkan untuk menggunakan ekspresi tingkat nilai pada tingkat tipe SEBAGAIMANA ADANYA.

Manfaat yang jelas adalah penggunaan kembali kode (Anda tidak perlu membuat kode ekspresi level secara terpisah dari level nilai jika Anda membutuhkannya di kedua tempat). Seharusnya lebih mudah untuk menulis kode tingkat nilai. Seharusnya lebih mudah untuk tidak berurusan dengan peretasan seperti lajang (belum lagi biaya kinerja). Anda tidak perlu mempelajari dua hal, Anda mempelajari satu hal. Pada tingkat pragmatis, kita akhirnya membutuhkan lebih sedikit konsep. Ketik sinonim, jenis keluarga, fungsi, ... bagaimana dengan fungsi saja? Menurut pendapat saya, manfaat pemersatu ini jauh lebih dalam dan lebih dari sekadar kenyamanan sintaksis.

Pertimbangkan kode terverifikasi. Lihat:
https://github.com/idris-lang/Idris-dev/blob/v1.3.0/libs/contrib/Interfaces/Verified.idr
Pemeriksa jenis memverifikasi bukti undang-undang monadik / functor / aplikatif dan buktinya benar implementasi dari monad / functor / aplikatif dan bukan beberapa setara tingkat tipe yang dikodekan yang mungkin sama atau tidak sama. Pertanyaan besarnya adalah apa yang kita buktikan?

Hal yang sama dapat saya lakukan dengan menggunakan trik pengkodean yang cerdas (lihat yang berikut untuk versi Haskell, saya belum melihatnya untuk Scala)
https://blog.jle.im/entry/verified-instances-in-haskell.html
https: // github.com/rpeszek/IdrisTddNotes/wiki/Play_FunctorLaws
kecuali jenisnya sangat rumit sehingga sulit untuk melihat hukumnya, ekspresi tingkat nilai diubah (secara otomatis tetapi tetap) untuk mengetik hal-hal tingkat dan Anda perlu mempercayai konversi itu juga . Ada ruang untuk kesalahan dalam semua ini yang agak bertentangan dengan tujuan penyusun bertindak sebagai asisten pembuktian.

(EDITED 2018.8.10) Berbicara tentang bantuan pembuktian, berikut adalah perbedaan besar antara Idris dan Scala. Tidak ada di Scala (atau Haskell) yang dapat mencegah penulisan bukti yang menyimpang:

case class Void(underlying: Nothing) extends AnyVal //should be uninhabited
def impossible() : Void = impossible()

sedangkan Idris memiliki totalkata kunci yang mencegah kode seperti ini untuk dikompilasi.

Pustaka Scala yang mencoba menyatukan nilai dan kode level tipe (seperti Haskell singletons) akan menjadi ujian yang menarik untuk dukungan Scala pada tipe-tipe dependen. Dapatkah pustaka semacam itu dilakukan jauh lebih baik di Scala karena tipe yang bergantung pada jalur?

Saya terlalu baru di Scala untuk menjawab pertanyaan itu sendiri.