Sumber daya pemrograman tipe scala

Menurut pertanyaan ini , sistem tipe Scala adalah Turing lengkap . Sumber daya apa yang tersedia yang memungkinkan pendatang baru untuk memanfaatkan kekuatan pemrograman tingkat tipe?

Berikut adalah sumber daya yang saya temukan sejauh ini:

• Sihir Tinggi Daniel Spiewak di Negeri Scala
• Pemrograman Tingkat-Jenis Apocalisp di Scala
• HList Jesper

Sumber daya ini bagus, tetapi saya merasa seperti kehilangan dasar-dasarnya, sehingga tidak memiliki fondasi yang kuat untuk membangun. Misalnya, di mana ada pengenalan definisi tipe? Operasi apa yang dapat saya lakukan pada tipe?

Apakah ada sumber pengantar yang bagus?

Gambaran

Pemrograman tingkat-tipe memiliki banyak kesamaan dengan pemrograman tingkat-nilai tradisional. Namun, tidak seperti pemrograman tingkat nilai, di mana komputasi terjadi pada waktu proses, dalam pemrograman tingkat-tipe, komputasi terjadi pada waktu kompilasi. Saya akan mencoba menarik kesejajaran antara pemrograman pada tingkat nilai dan pemrograman pada tingkat tipe.

Paradigma

Ada dua paradigma utama dalam pemrograman level-tipe: "berorientasi objek" dan "fungsional". Sebagian besar contoh yang ditautkan dari sini mengikuti paradigma berorientasi objek.

Contoh yang bagus dan cukup sederhana dari pemrograman level-tipe dalam paradigma berorientasi objek dapat ditemukan dalam implementasi apocalisp dari kalkulus lambda , yang direplikasi di sini:

// Abstract trait
trait Lambda {
  type subst[U <: Lambda] <: Lambda
  type apply[U <: Lambda] <: Lambda
  type eval <: Lambda
}

// Implementations
trait App[S <: Lambda, T <: Lambda] extends Lambda {
  type subst[U <: Lambda] = App[S#subst[U], T#subst[U]]
  type apply[U] = Nothing
  type eval = S#eval#apply[T]
}

trait Lam[T <: Lambda] extends Lambda {
  type subst[U <: Lambda] = Lam[T]
  type apply[U <: Lambda] = T#subst[U]#eval
  type eval = Lam[T]
}

trait X extends Lambda {
  type subst[U <: Lambda] = U
  type apply[U] = Lambda
  type eval = X
}

Seperti dapat dilihat pada contoh, paradigma berorientasi objek untuk pemrograman level-tipe berlangsung sebagai berikut:

• Pertama: tentukan sifat abstrak dengan berbagai jenis bidang abstrak (lihat di bawah untuk mengetahui apa itu bidang abstrak). Ini adalah template untuk menjamin bahwa beberapa jenis kolom ada di semua implementasi tanpa memaksa implementasi. Dalam contoh lambda kalkulus, berkorespondensi ini untuk trait Lambdamenjamin bahwa jenis berikut ada: subst, apply, dan eval.
• Berikutnya: tentukan subtraits yang memperluas sifat abstrak dan implementasikan berbagai bidang tipe abstrak
  • Seringkali, subtraits ini akan diberi parameter dengan argumen. Dalam contoh kalkulus lambda, subtipe trait App extends Lambdayang diparameterisasi dengan dua tipe ( Sdan T, keduanya harus merupakan subtipe dari Lambda), trait Lam extends Lambdadiparameterisasi dengan satu tipe ( T), dan trait X extends Lambda(yang tidak berparameterisasi).
  • field type sering diimplementasikan dengan mengacu pada parameter type dari subtrait dan terkadang mereferensikan field type mereka melalui operator hash: #(yang sangat mirip dengan operator titik: .untuk nilai). Dalam sifat Appdari contoh lambda kalkulus, jenis evaldiimplementasikan sebagai berikut: type eval = S#eval#apply[T]. Ini pada dasarnya memanggil evaljenis parameter sifat S, dan memanggil applydengan parameter Tpada hasil. Catatan, Sdijamin memiliki evaltipe karena parameter menetapkannya sebagai subtipe dari Lambda. Demikian pula, hasil dari evalmust have a applytype, karena itu ditentukan sebagai subtipe dari Lambda, seperti yang ditentukan dalam sifat abstrak Lambda.

Paradigma fungsional terdiri dari banyak definisi konstruktor tipe berparameter yang tidak dikelompokkan bersama dalam sifat.

Perbandingan antara pemrograman tingkat nilai dan pemrograman tingkat tipe

• kelas abstrak
  • tingkat nilai: abstract class C { val x }
  • tipe-level: trait C { type X }
• jenis yang bergantung pada jalur
  • C.x (mereferensikan nilai bidang / fungsi x di objek C)
  • C#x (mereferensikan tipe bidang x pada sifat C)
• fungsi tanda tangan (tidak ada implementasi)
  • tingkat nilai: def f(x:X) : Y
  • type-level: type f[x <: X] <: Y(ini disebut "tipe konstruktor" dan biasanya terjadi dalam sifat abstrak)
• implementasi fungsi
  • tingkat nilai: def f(x:X) : Y = x
  • tipe-level: type f[x <: X] = x
• bersyarat
  • Lihat disini
• memeriksa kesetaraan
  • tingkat nilai: a:A == b:B
  • tipe-level: implicitly[A =:= B]
  • tingkat nilai: Terjadi di JVM melalui pengujian unit pada waktu proses (yaitu, tidak ada kesalahan waktu proses):
    • intinya adalah pernyataan: assert(a == b)
  • type-level: Terjadi di kompilator melalui pemeriksaan ketik (yaitu, tidak ada kesalahan kompilator):
    • pada dasarnya adalah jenis perbandingan: mis implicitly[A =:= B]
    • A <:< B, mengkompilasi hanya jika Amerupakan subtipe dariB
    • A =:= B, mengkompilasi hanya jika Aadalah subtipe dari Bdan Bmerupakan subtipe dariA
    • A <%< B, ("terlihat sebagai") mengkompilasi hanya jika Adapat dilihat sebagai B(yaitu ada konversi implisit dari Ake subtipe dari B)
    • sebuah contoh
    • lebih banyak operator pembanding

Mengonversi antara tipe dan nilai

• Dalam banyak contoh, tipe yang didefinisikan melalui ciri-ciri seringkali bersifat abstrak dan tertutup, dan oleh karena itu tidak dapat dibuat instance-nya secara langsung atau melalui subkelas anonim. Jadi, biasanya digunakan nullsebagai nilai placeholder saat melakukan penghitungan tingkat nilai menggunakan beberapa jenis minat:

  • misalnya val x:A = null, di mana Atipe yang Anda pedulikan

• Karena tipe-erasure, semua tipe berparameter terlihat sama. Selain itu, (seperti yang disebutkan di atas) nilai yang Anda kerjakan cenderung semuanya null, dan karena itu pengondisian pada tipe objek (misalnya melalui pernyataan kecocokan) tidak efektif.

Triknya adalah dengan menggunakan fungsi dan nilai implisit. Kasus dasar biasanya berupa nilai implisit dan kasus rekursif biasanya merupakan fungsi implisit. Memang, pemrograman level-tipe membuat banyak penggunaan implikasinya.

Pertimbangkan contoh ini ( diambil dari metascala dan apocalisp ):

sealed trait Nat
sealed trait _0 extends Nat
sealed trait Succ[N <: Nat] extends Nat

Di sini Anda memiliki pengkodean peano dari bilangan asli. Artinya, Anda memiliki tipe untuk setiap bilangan bulat non-negatif: tipe khusus untuk 0, yaitu _0; dan setiap bilangan bulat yang lebih besar dari nol memiliki jenis formulir Succ[A], di mana Ajenis yang mewakili bilangan bulat yang lebih kecil. Misalnya, tipe yang mewakili 2 adalah: Succ[Succ[_0]](penerus diterapkan dua kali ke tipe yang mewakili nol).

Kami dapat membuat alias berbagai bilangan asli untuk referensi yang lebih nyaman. Contoh:

type _3 = Succ[Succ[Succ[_0]]]

(Ini sangat mirip dengan mendefinisikan a valsebagai hasil dari suatu fungsi.)

Sekarang, misalkan kita ingin mendefinisikan fungsi tingkat-nilai def toInt[T <: Nat](v : T)yang mengambil nilai argumen v,, yang sesuai dengan Natdan mengembalikan integer yang mewakili bilangan asli yang dikodekan dalam vtipe. Misalnya, jika kita memiliki nilai val x:_3 = null( nulltipe Succ[Succ[Succ[_0]]]), kita ingin toInt(x)mengembalikan 3.

Untuk menerapkannya toInt, kita akan menggunakan kelas berikut:

class TypeToValue[T, VT](value : VT) { def getValue() = value }

Seperti yang akan kita lihat di bawah, akan ada objek yang dibangun dari kelas TypeToValueuntuk masing-masing Natdari _0atas hingga (misalnya) _3, dan masing-masing akan menyimpan representasi nilai dari tipe yang sesuai (yaitu TypeToValue[_0, Int]akan menyimpan nilai 0, TypeToValue[Succ[_0], Int]akan menyimpan nilai 1, dll.). Catatan, TypeToValuediparameterisasi oleh dua jenis: Tdan VT. Tsesuai dengan jenis yang kita coba tetapkan nilainya (dalam contoh kita, Nat) dan VTsesuai dengan jenis nilai yang kita tetapkan padanya (dalam contoh kita, Int).

Sekarang kita membuat dua definisi implisit berikut:

implicit val _0ToInt = new TypeToValue[_0, Int](0)
implicit def succToInt[P <: Nat](implicit v : TypeToValue[P, Int]) = 
     new TypeToValue[Succ[P], Int](1 + v.getValue())

Dan kami menerapkan toIntsebagai berikut:

def toInt[T <: Nat](v : T)(implicit ttv : TypeToValue[T, Int]) : Int = ttv.getValue()

Untuk memahami cara toIntkerjanya, mari pertimbangkan apa yang dilakukannya pada beberapa input:

val z:_0 = null
val y:Succ[_0] = null

Saat kita memanggil toInt(z), kompilator mencari argumen implisit ttvbertipe TypeToValue[_0, Int](karena zbertipe _0). Ia menemukan objek _0ToInt, ia memanggil getValuemetode objek ini dan kembali 0. Hal penting yang perlu diperhatikan adalah bahwa kita tidak menentukan objek mana yang akan digunakan pada program, kompilator menemukannya secara implisit.

Sekarang mari kita pertimbangkan toInt(y). Kali ini, kompilator mencari argumen implisit ttvbertipe TypeToValue[Succ[_0], Int](karena ybertipe Succ[_0]). Ia menemukan fungsi succToInt, yang bisa mengembalikan objek dari type ( TypeToValue[Succ[_0], Int]) yang sesuai dan mengevaluasinya. Fungsi ini sendiri mengambil argumen implisit ( v) dari tipe TypeToValue[_0, Int](yaitu, di TypeToValuemana parameter tipe pertama memiliki satu lebih sedikit Succ[_]). Kompilator menyediakan _0ToInt(seperti yang dilakukan dalam evaluasi di toInt(z)atas), dan succToIntmembangun TypeToValueobjek baru dengan nilai 1. Sekali lagi, penting untuk dicatat bahwa kompilator menyediakan semua nilai ini secara implisit, karena kita tidak memiliki akses secara eksplisit.

Memeriksa pekerjaan Anda

Ada beberapa cara untuk memverifikasi bahwa penghitungan tingkat tipe Anda melakukan apa yang Anda harapkan. Berikut ini beberapa pendekatan. Buat dua jenis Adan B, yang ingin Anda verifikasi adalah sama. Kemudian periksa kompilasi berikut:

• Equal[A, B]
  • dengan: sifat Equal[T1 >: T2 <: T2, T2]( diambil dari apocolisp )
• implicitly[A =:= B]

Alternatifnya, Anda dapat mengonversi jenis menjadi nilai (seperti yang ditunjukkan di atas) dan melakukan pemeriksaan waktu proses terhadap nilai tersebut. Misalnya assert(toInt(a) == toInt(b)), di mana atipe Adan btipe B.

Sumber daya tambahan

Kumpulan lengkap dari konstruksi yang tersedia dapat ditemukan di bagian tipe dari manual referensi skala (pdf) .

Adriaan Moors memiliki beberapa makalah akademis tentang konstruktor tipe dan topik terkait dengan contoh dari scala:

• Generik dari jenis yang lebih tinggi (pdf)
• Type Constructor Polymorphism for Scala: Theory and Practice (pdf) (PhD tesis, yang mencakup makalah sebelumnya oleh Moors)
• Ketik Konstruktor Polimorfisme Inferensi

Apocalisp adalah blog dengan banyak contoh pemrograman level-tipe dalam skala.

• Pemrograman Tingkat-Jenis di Scala adalah tur terpandu yang fantastis dari beberapa pemrograman tingkat-jenis yang mencakup boolean, bilangan asli (seperti di atas), bilangan biner, daftar heterogen, dan banyak lagi.
• Lebih banyak Scala Typehackery adalah implementasi kalkulus lambda di atas.

ScalaZ adalah proyek yang sangat aktif yang menyediakan fungsionalitas yang memperluas API Scala menggunakan berbagai fitur pemrograman tingkat tipe. Ini adalah proyek yang sangat menarik yang memiliki banyak pengikut.

MetaScala adalah pustaka tingkat jenis untuk Scala, termasuk jenis meta untuk bilangan asli, boolean, unit, HList, dll. Ini adalah proyek oleh Jesper Nordenberg (blognya) .

The Michid (blog) memiliki beberapa contoh yang mengagumkan dari pemrograman jenis-tingkat di Scala (dari jawaban lain):

• Pemrograman Meta dengan Scala Bagian I: Penambahan
• Meta-Programming dengan Scala Part II: Perkalian
• Meta-Programming dengan Scala Part III: Aplikasi fungsi parsial
• Meta-Programming dengan Scala: Kompilasi Bersyarat dan Loop Unrolling
• Pengkodean tingkat jenis scala dari kalkulus SKI

Debasish Ghosh (blog) juga memiliki beberapa posting yang relevan:

• Abstraksi tingkat tinggi dalam skala
• Pengetikan statis memberi Anda permulaan
• Scala mengimplikasikan kelas tipe, ini aku datang
• Refactoring menjadi kelas tipe skala
• Menggunakan batasan tipe umum
• Bagaimana kata-kata sistem jenis scalas untuk Anda
• Memilih di antara anggota tipe abstrak

(Saya telah melakukan beberapa penelitian tentang subjek ini dan inilah yang telah saya pelajari. Saya masih baru dalam hal itu, jadi harap tunjukkan ketidakakuratan dalam jawaban ini.)

Selain link lain disini, ada juga postingan blog saya tentang tipe level meta programming di Scala:

• Pemrograman Meta dengan Scala Bagian I: Penambahan
• Meta-Programming dengan Scala Part II: Perkalian
• Meta-Programming dengan Scala Part III: Aplikasi fungsi parsial
• Meta-Programming dengan Scala: Kompilasi Bersyarat dan Loop Unrolling
• Pengkodean tingkat jenis scala dari kalkulus SKI

Seperti yang disarankan di Twitter: Shapeless: Eksplorasi pemrograman generik / polytypic di Scala oleh Miles Sabin.

• Sing , pustaka metaprogramming level tipe di Scala.
• Awal Pemrograman Tingkat-Tipe di Scala

Scalaz memiliki kode sumber, wiki dan contoh.