Di beberapa bidang pemrograman, adalah normal untuk ingin menulis struktur data atau algoritma yang dapat bekerja dengan elemen dari tipe yang berbeda. Misalnya, daftar obat generik atau algoritma pengurutan yang hanya membutuhkan fungsi perbandingan. Dalam berbagai bahasa, berbagai cara untuk memecahkan masalah ini ditawarkan: mulai dari sekadar menunjukkan fungsi umum yang sesuai (C, Go) hingga programmer ke sistem generik yang sangat kuat sehingga mereka menjadi Turing lengkap (
Rust ,
C ++ ). Pada artikel ini saya akan berbicara tentang sistem generik dari berbagai bahasa dan implementasinya. Saya akan mulai dengan memecahkan masalah dalam bahasa tanpa sistem seperti itu (seperti C), dan kemudian saya akan menunjukkan bagaimana penambahan ekstensi secara bertahap mengarah ke sistem dari bahasa lain.
Saya menemukan obat generik menjadi pilihan yang menarik karena mereka adalah kasus khusus sederhana dari tugas metaprogramming umum: menulis program yang dapat menghasilkan kelas dari program lain. Sebagai bukti, saya akan menunjukkan bagaimana tiga metode metaprogramming yang berbeda dan sepenuhnya umum dapat dianggap sebagai ekstensi multi arah dalam ruang sistem generik: bahasa dinamis seperti Python, sistem makro prosedural seperti
Template Haskel, dan kompilasi bertahap seperti
Zig dan
Terra .
Ulasan
Saya menggambar diagram blok semua sistem yang dijelaskan dalam artikel sehingga Anda dapat membayangkan isinya dan bagaimana sistem ini saling berhubungan:
Ide utama
Misalkan kita menulis dalam bahasa tanpa sistem generik, dan kami ingin membuat struktur data stack struktur data generik yang bekerja dengan data jenis apa pun. Masalahnya adalah bahwa setiap definisi fungsi dan tipe hanya akan bekerja dengan data dengan ukuran yang sama dan disalin dalam satu cara, dan umumnya bekerja dengan cara yang sama.
Ada dua cara untuk menyiasatinya: pastikan semua tipe data bertindak dengan cara yang sama dalam struktur kami, atau buat banyak salinan struktur data dengan perubahan kecil agar berfungsi dengan benar untuk setiap tipe data. Ide-ide ini membentuk dasar dari dua kelompok besar solusi dengan obat generik: tinju dan monomorfisasi.
Pengemasan berarti menempatkan segala sesuatu dalam satu baris ke dalam "kotak" terpadu yang bekerja dengan cara yang sama. Ini biasanya dilakukan seperti ini: data diletakkan di heap, dan pointer ke sana ditempatkan di struktur data. Anda dapat membuat pointer ke semua jenis yang akan bekerja dengan cara yang sama, sehingga kode yang sama akan bekerja dengan data jenis apa pun! Namun, ini mengarah pada peningkatan konsumsi memori, pencarian dinamis, dan kehilangan cache. Dalam C, ini berarti bahwa struktur data Anda menyimpan
void* pointer dan hanya cache data ke dan dari
void* (jika data tidak ada di heap, itu menempatkannya di sana).
Monomorphization berarti berulang kali menyalin kode untuk berbagai jenis data yang ingin kami simpan. Kemudian setiap instance kode dapat langsung menggunakan metode ukuran dan data yang berfungsi tanpa pencarian dinamis. Dengan pendekatan ini, kode berjalan paling cepat, tetapi ukuran dan waktu kompilasi meningkat, karena kami berulang kali mengkompilasi kode yang sama dengan perubahan kecil. Dalam C, ini sesuai dengan
definisi seluruh struktur data sebagai makro , diikuti dengan pemanggilannya untuk setiap tipe data.
Secara umum, selama kompilasi, kode mengkompilasi lebih cepat, tetapi kinerjanya dapat memburuk selama eksekusi, sementara selama monomorphization kami menghasilkan kode cepat, tetapi butuh lebih banyak waktu untuk mengkompilasi dan mengoptimalkan semua contoh kode. Perbedaan lainnya adalah ketika ekstensi kemasan memungkinkan Anda membuat perilaku yang lebih dinamis dari kode yang dapat dieksekusi, dan monomorfisasi memungkinkan Anda untuk secara lebih fleksibel memisahkan berbagai contoh kode generik. Perlu juga dicatat bahwa dalam beberapa program besar, manfaat monomorfisasi dapat diimbangi dengan meleset dalam cache instruksi tambahan dari kode yang dihasilkan.
Setiap skema yang dijelaskan untuk bekerja dengan obat generik dapat diperluas ke arah yang berbeda, jika Anda memerlukan lebih banyak fitur atau keamanan, dan penulis berbagai bahasa telah menghasilkan solusi yang sangat menarik. Sebagai contoh, kedua pendekatan dapat digunakan di Rust dan C #!
Pengepakan
Mari kita mulai dengan contoh kemasan dasar di Go:
type Stack struct { values []interface{} } func (this *Stack) Push(value interface{}) { this.values = append(this.values, value) } func (this *Stack) Pop() interface{} { x := this.values[len(this.values)-1] this.values = this.values[:len(this.values)-1] return x }
Juga, kemasan digunakan dalam C (
void* ), Go (
interface{} ), Java pra-generik (
Object ) dan Objective-C (
id ) pra-generik.
Generik yang Dikemas dengan Jenis Penghancuran
Metode pengemasan utama memiliki kelemahan:
- Bergantung pada bahasanya, kita sering harus memberikan nilai ke atau dari tipe yang benar setiap kali kita membaca atau menulis ke struktur data.
- Tidak ada yang mencegah kita memasukkan elemen dari tipe yang berbeda ke dalam struktur, yang dapat memancing bug yang terlihat seperti macet selama eksekusi kode.
Kedua masalah dapat diselesaikan dengan menambahkan obat generik ke sistem jenis fungsionalitas, sambil menggunakan metode pengemasan utama dengan cara yang sama seperti sebelumnya selama eksekusi kode. Pendekatan ini sering disebut tipe erasure, karena tipe dalam sistem generik ditimpa dan menjadi satu tipe di bawah tenda (seperti
Object ).
Java dan Objective-C mulai dengan kemasan biasa, dan kemudian memperoleh alat bahasa untuk generik dengan tipe mashing, demi kompatibilitas, menggunakan tipe koleksi yang sama seperti sebelumnya, tetapi dengan parameter opsional tipe generik. Pertimbangkan contoh dari artikel Wikipedia tentang
obat generik di Jawa :
List v = new ArrayList(); v.add("test");
Turunan Generik Paket dengan Kinerja Terpadu
OCaml lebih lanjut mengembangkan gagasan pandangan terpadu. Tidak ada tipe primitif yang membutuhkan penempatan kemasan tambahan (karena sebuah
int harus berubah menjadi
Integer untuk masuk ke dalam
ArrayList di Jawa), karena semuanya sudah dikemas atau diwakili oleh nilai integer ukuran pointer, yaitu semuanya cocok menjadi satu kata mesin. Tetapi ketika pengumpul sampah melihat data yang disimpan dalam struktur generik, ia perlu membedakan pointer dari angka, sehingga angka-angka tersebut ditandai dengan satu bit, ditempatkan di mana pointer yang tepat tidak memiliki satu bit, meninggalkan kisaran hanya 31 atau 63 bit.
OCaml juga memiliki sistem inferensi tipe, sehingga Anda dapat menulis suatu fungsi dan kompiler akan menampilkan tipe generik yang paling cocok jika Anda tidak membubuhi keterangan, dan fungsi tersebut akan terlihat seperti itu adalah bahasa yang diketik secara dinamis:
let first (head :: tail) = head (* inferred type: 'a list -> 'a *)
Tipe yang diberikan dapat disebut "fungsi dari daftar elemen tipe
'a menjadi sesuatu dengan tipe
'a ". Ini berarti bahwa tipe pengembalian akan sama dengan tipe daftar, dan itu bisa berupa tipe apa pun.
Antarmuka
Keterbatasan lain dari kemasan konvensional adalah jenis kemasannya
benar -
benar buram. Ini bukan masalah untuk struktur data seperti tumpukan, tetapi alat seperti pengurutan fungsi generik memerlukan fitur tambahan, seperti fungsi perbandingan tipe-spesifik. Ada banyak cara untuk mengimplementasikan ini dalam runtime dan mencerminkan dalam bahasa, secara teknis ini adalah arah yang berbeda, dan Anda dapat
menerapkan bahasa yang sama dengan beberapa pendekatan serupa . Namun, fitur-fitur dari bahasa yang berbeda memengaruhi implementasinya, dan hanya dengan demikian ekstensi meningkatkan kekuatan implementasi yang dipilih. Ini berarti bahwa ada dua keluarga bahasa berdasarkan pendekatan yang berbeda untuk runtime: tabel metode virtual (vtables) dan transfer kamus.
Tabel Metode Antarmuka
Jika kita ingin menyediakan fungsi tipe-spesifik, mengikuti strategi pengemasan demi pekerjaan terpadu dengan segalanya, maka cukup memiliki cara terpadu untuk menemukan fungsi serupa yang perlu kita dapatkan dari objek. Pendekatan ini disebut "tabel metode virtual" (vtables, tabel metode virtual), meskipun tidak ada yang menggunakan nama lengkap. Diimplementasikan sebagai berikut: pada nol offset di setiap objek struktur generik, ada pointer ke tabel pointer fungsi dengan sirkuit yang konsisten. Dalam tabel ini, kode umum mencari pointer untuk mengetik fungsi-fungsi spesifik dengan mengindeks pointer spesifik pada offset tetap.
Ini adalah bagaimana tipe
interface diimplementasikan dalam Go dan
dyn trait objects di Rust. Saat Anda melemparkan sebuah tipe ke tipe antarmuka dari apa yang diterapkannya, pembungkus dibuat untuk antarmuka yang berisi pointer ke objek sumber dan pointer ke vtable fungsi tipe-spesifik. Tetapi ini membutuhkan tingkat tambahan dari pengalamatan pointer secara tidak langsung dan skema lain. Oleh karena itu, pengurutan dalam Go menggunakan
antarmuka untuk wadah dengan metode Swap , dan tidak mengambil sepotong antarmuka Sebanding, karena ini akan membutuhkan menempatkan sepotong memori yang sama sekali baru dari jenis antarmuka yang akan diurutkan alih-alih potongan asli!
Pemrograman berorientasi objek
OOP adalah properti bahasa yang memanfaatkan kemampuan tabel tipe virtual. Alih-alih memisahkan objek antarmuka dengan vtables, bahasa OOP seperti Java cukup menyisipkan pointer ke tabel jenis virtual di awal setiap objek. Bahasa seperti Java memiliki sistem warisan dan antarmuka yang dapat sepenuhnya diimplementasikan menggunakan tabel objek tipe virtual ini.
Selain menyediakan fitur-fitur tambahan, menanamkan vtable di setiap objek memecahkan masalah kebutuhan untuk membangun tipe antarmuka baru dengan pengalamatan tidak langsung (tipuan). Tidak seperti Go, di Java
, fungsi sortir dapat menerapkan antarmuka
Comparable dengan tipe yang diimplementasikan.
Refleksi
Jika Anda memiliki tabel tipe virtual, maka tidak akan sulit bagi Anda untuk memaksa kompiler untuk menghasilkan tabel dari tipe informasi lain, misalnya, nama bidang, tipe, dan lokasi. Ini akan memungkinkan akses ke semua data jenis ini menggunakan kode yang dapat melihat semua data dari jenis lain. Perilaku ini dapat digunakan untuk menambahkan "refleksi" ke bahasa, yang memungkinkan serialisasi dan tampilan yang indah dari jenis sewenang-wenang. Refleksi, sebagai perpanjangan dari paradigma pengemasan, memiliki kelemahan: untuk itu, hanya satu salinan kode yang cukup, tetapi Anda perlu melakukan banyak pencarian dinamis, yang mengurangi kecepatan serialisasi.
Bahasa yang menggunakan refleksi untuk serialisasi dan fungsi lainnya: Java, C # dan Go.
Bahasa yang diketik secara dinamis
Refleksi adalah alat yang sangat kuat yang memungkinkan Anda untuk menyelesaikan banyak tugas pemrograman metap berbeda. Tetapi itu tidak memungkinkan Anda untuk membuat tipe baru atau mengedit informasi tentang tipe nilai yang ada. Jika kami menambahkan fitur ini dan membuat akses data dan sintaks modifikasi menggunakan refleksi secara default, kami mendapatkan bahasa yang diketik secara dinamis! Fleksibilitas yang luar biasa dari metaprogramming dalam bahasa seperti Python dan Ruby telah muncul berkat sistem refleksi yang efektif dan kuat yang digunakan untuk menyelesaikan masalah.
Anda bisa mengatakan: "Tapi bahasa dinamis tidak berfungsi seperti itu, mereka hanya mengimplementasikan semuanya menggunakan tabel hash!" Tabel hash hanyalah struktur data yang bagus untuk membuat tabel yang dapat diedit dengan informasi tipe. Selain itu, beberapa penerjemah, seperti CPython, bekerja dengan cara ini. Dalam JIT berkinerja tinggi, katakanlah V8,
ada banyak tabel tipe virtual dan informasi refleksi. Di V8, kelas tersembunyi (vtable dan informasi refleksi) dan struktur objek mirip dengan apa yang dapat Anda lihat di Java VM, dengan kemampuan untuk mengganti objek dengan tabel tipe virtual baru saat runtime. Ini bukan kebetulan, karena tidak ada kebetulan:
pencipta V8 digunakan untuk
bekerja pada Java VM kinerja tinggi .
Transfer Kamus
Cara lain untuk mengimplementasikan antarmuka dinamis adalah mentransfer tabel dengan pointer fungsi yang diperlukan ke fungsi generik yang membutuhkannya. Ini agak mirip dengan membangun objek antarmuka berbentuk Go di tempat panggilan, hanya dalam kasus kami tabel dilewatkan sebagai argumen tersembunyi, dan tidak dikemas ke dalam bundel sebagai salah satu argumen yang ada.
Pendekatan ini digunakan dalam
kelas tipe di Haskell , meskipun GHC memungkinkan Anda untuk melakukan beberapa jenis monomorphization menggunakan inlining dan spesialisasi. OCaml menggunakan transfer kamus dengan argumen eksplisit dalam bentuk
modul kelas satu , tetapi telah diusulkan untuk
menambah kemampuan untuk membuat parameter implisit .
Meja saksi di Swift
Penulis Swift menggunakan solusi yang menarik: mentransfer kamus, serta menempatkan data pada ukuran jenis dan cara memindahkan, menyalin, dan melepaskannya ke dalam tabel, memungkinkan Anda untuk memberikan semua informasi yang diperlukan untuk pekerjaan terpadu dengan jenis apa pun tanpa mengemasnya. Dengan demikian, Swift dapat mengimplementasikan obat generik
tanpa monomorfisasi dan penempatan dalam memori dalam representasi terpadu dari semua entitas! Ya, Anda harus membayar untuk pencarian dinamis, seperti karakteristik seluruh keluarga yang menggunakan kemasan, tetapi menghemat sumber daya untuk penempatan dalam memori, konsumsi dan inkonsistensi cache. Menggunakan fungsi yang
dijelaskan sebagai @inlinable , kompiler Swift juga dapat mengkhususkan (monomorf) dan inline generik di dalam modul atau antar modul untuk menghindari biaya yang disebutkan. Mungkin penilaian heuristik dari efek pada ukuran kode digunakan.
Ini juga menjelaskan bagaimana Swift dapat
menerapkan stabilitas ABI , sambil tetap memungkinkan Anda untuk menambah dan mendistribusikan kembali bidang dalam struktur, meskipun penulis menyediakan atribut
@frozen untuk menolak pencarian dinamis untuk kinerja yang lebih baik.
Analisis Jenis Intensional
Ada cara lain untuk mengimplementasikan antarmuka untuk tipe paket. Kami menambahkan pengenal tipe ke bagian tertentu dari objek, mengikuti contoh dari pointer vtable, dan kemudian menghasilkan fungsi untuk setiap metode antarmuka yang memiliki ekspresi
switch besar untuk semua jenis yang menerapkan metode ini dan meneruskannya ke metode spesifik tipe yang benar.
Saya tidak memperingatkan untuk tidak menggunakan bahasa yang menggunakan pendekatan ini, tetapi kompiler C ++ dan mesin virtual Java bertindak dengan cara yang sama, ketika menggunakan optimasi berdasarkan profil, mereka mengetahui bahwa suatu tempat panggilan generik kebanyakan bekerja dengan objek dari tipe tertentu. Compiler dan VM mengganti titik panggilan dengan cek untuk setiap jenis biasa, dan kemudian mengirim jenis ini secara statis, sebagai fallback menggunakan pengiriman dinamis konvensional. Oleh karena itu, algoritma prediksi cabang dapat memprediksi cabang mana yang akan melanjutkan kode, dan akan terus mengirim instruksi menggunakan panggilan statis.
Monomorisasi
Ini adalah alternatif untuk pengemasan. Dengan monomorphization, kita perlu menemukan cara untuk menghasilkan beberapa versi kode untuk setiap jenis yang ingin kita gunakan. Compiler memiliki beberapa fase presentasi yang dilalui oleh kode, dan, secara teoritis, dapat disalin ke salah satu tahapan ini.
Pembuatan kode sumber
Cara termudah untuk membuat monomorf adalah menyalin pada tahap presentasi pertama: salin kode sumber! Maka kompiler bahkan tidak harus mendukung generik, dan ini kadang-kadang dilakukan oleh pengguna bahasa C dan Go, yang kompilernya tidak memiliki dukungan seperti itu.
Di C, Anda bisa menggunakan preprocessor dan menentukan struktur data di makro atau header dengan memasukkannya berulang kali dengan
#define berbeda. Go memiliki skrip seperti
jin yang membuatnya mudah untuk menghasilkan kode.
Kerugian dari menduplikasi kode sumber adalah bahwa, tergantung pada bahasanya, mungkin perlu untuk berurusan dengan banyak masalah dan kasus tepi, apalagi, kompiler mem-parsing dan memeriksa berkali-kali untuk jenis sebenarnya untuk kode yang sama. Sekali lagi, tergantung pada bahasa dan alat-alatnya, metode-metode umum ini mungkin sulit untuk ditulis dan digunakan, seolah-olah di dalam makro-C setiap baris diakhiri dengan garis miring terbalik dan semua jenis dan nama fungsi harus secara manual direkatkan ke dalam pengidentifikasi mereka untuk menghindari tabrakan.
Mixin string dalam D
Namun, pembuatan kode memiliki kelebihan, seperti fakta bahwa Anda dapat menghasilkan kode menggunakan bahasa pemrograman lengkap, serta menggunakan tampilan yang familier bagi pengguna.
Beberapa bahasa di mana obat generik diimplementasikan secara berbeda juga memungkinkan Anda untuk menghasilkan kode untuk kasus pemrograman metam yang lebih umum yang tidak dipertimbangkan dalam sistem generiknya, misalnya, untuk serialisasi. Contoh yang paling dimengerti adalah
string mixin dalam D , yang memungkinkan kompilasi D-code dalam bentuk nilai-nilai string di tengah kompilasi, menggunakan semua fitur bahasa.
Macro prosedural karat
Contoh serupa, hanya dengan representasi dalam kompiler hanya pada satu tahap.
Makro prosedural karat menggunakan aliran token sebagai input dan output, menyediakan utilitas untuk mengubah aliran ini menjadi string dan sebaliknya. Keuntungan dari pendekatan ini adalah bahwa token stream dapat menyimpan informasi lokasi dari kode sumber. Kode yang ditulis oleh pengguna, makro dapat dimasukkan sebagai token langsung dari input hingga akhir pekan. Dan jika kode ini menyebabkan kesalahan kompilasi dalam output dari makro, kompiler akan menampilkan pesan dan secara akurat menunjuk ke file, baris dan kolom dari bagian kode yang rusak. Tetapi jika makro menghasilkan kode yang rusak, maka pesan kesalahan akan menunjukkan panggilan makro. Misalnya, jika Anda menggunakan
makro yang membungkus suatu fungsi dalam mencatat panggilan dan membuat kesalahan dalam menerapkan fungsi yang dibungkus, maka pesan kesalahan akan langsung menunjuk ke kesalahan dalam file, dan bukan ke kode yang dihasilkan oleh makro.
Sintaks Pohon Makro
Beberapa bahasa bahkan melangkah lebih jauh dan menawarkan alat untuk menggunakan dan membuat berbagai jenis pohon sintaksis abstrak dalam makro (Abstract Syntax Tree, AST). Contohnya termasuk
Template Haskell ,
makro Nim ,
OCaml PPX, dan hampir semua
Lisp .
Kelemahan dari makro AST adalah Anda tidak ingin memaksa pengguna untuk mempelajari banyak fungsi untuk membangun tipe AST, serta bahasa dasar. Dalam keluarga Lisp bahasa, ini diselesaikan dengan bantuan penyederhanaan yang kuat dan korespondensi maksimum antara sintaks dan struktur AST, namun, membuat struktur tidak selalu mudah.
Jadi, dalam semua bahasa yang saya sebutkan, dalam satu atau lain bentuk ada "kutipan" primitif yang Anda berikan sepotong kode dalam bahasa, dan yang mengembalikan pohon sintaksis. Primitif ini dapat menggabungkan nilai-nilai pohon sintaksis menggunakan kesamaan interpolasi string. Berikut ini adalah contoh pada Template Haskell:
, , , . . , PPX OCaml
/ , . Rust ,
parsing quotation , , . Rust
, , !
Pola
— . ++ D , « ». , , , , .
template <class T> T myMax(T a, T b) { return (a>b?a:b); } template <class T> struct Pair { T values[2]; }; int main() { myMax(5, 6); Pair<int> p { {5,6} };
, , . , , .
D , , : , , . D;
if (
! ):
C++20 «» , , .
D , (compile time function evaluation)
static if , , , , - runtime-. , , , ++ , .
, « ». , Zig:
fn Stack(comptime T: type) type { return struct { items: []T, len: usize, const Self = @This(); pub fn push(self: Self, item: T) { // ... } }; }
Zig , ,
comptime .
Terra , . Terra — Lua, - , Lua API , quoting splicing:
function MakeStack(T) local struct Stack { items : &T;
Terra
- (domain specific) ,
Java Go . Terra runtime , .
Rust
, . , , ++, . , , , , . , . Rust, — Swift Haskell.
Rust « » (trait bounds).
Trait — , , . Rust , - , , , . - Rust
. , -.
fn my_max<T: PartialOrd>(a: T, b: T) -> T { if a > b { a } else { b } } struct Pair<T> { values: [T; 2], } fn main() { my_max(5,6); let p: Pair<i32> = Pair { values: [5,6] };
, . Rust . Rust 2018 ,
v: &impl SomeTrait ,
v: &dyn SomeTrait . GHC Swift Haskell , .
— , . , (placeholders) -, , .
memcpy , ! , . . JIT, , .
, , , , , , ! , , , . , , .