Apakah ada alasan untuk memiliki tipe terbawah dalam bahasa pemrograman?

Tipe dasar adalah konstruk yang terutama muncul dalam teori tipe matematika. Ini juga disebut tipe kosong. Ini adalah tipe yang tidak memiliki nilai, tetapi merupakan subtipe dari semua tipe.

Jika tipe pengembalian fungsi adalah tipe bawah, itu berarti ia tidak kembali. Titik. Mungkin loop selamanya, atau mungkin melempar pengecualian.

Apa gunanya memiliki tipe aneh ini dalam bahasa pemrograman? Ini tidak umum, tetapi ada di beberapa, seperti Scala dan Lisp.

Saya akan mengambil contoh sederhana: C ++ vs Rust.

Berikut adalah fungsi yang digunakan untuk melempar pengecualian di C ++ 11:

[[noreturn]] void ThrowException(char const* message,
                                 char const* file,
                                 int line,
                                 char const* function);

Dan inilah yang setara di Rust:

fn formatted_panic(message: &str, file: &str, line: isize, function: &str) -> !;

Pada masalah sintaksis murni, konstruksi Rust lebih masuk akal. Perhatikan bahwa konstruk C ++ menetapkan tipe pengembalian meskipun ia juga menentukan tidak akan kembali. Agak aneh.

Pada catatan standar, sintaks C ++ hanya muncul dengan C ++ 11 (itu ditempel di atas), tetapi berbagai kompiler telah menyediakan berbagai ekstensi untuk sementara waktu, sehingga alat analisis pihak ketiga harus diprogram untuk mengenali berbagai cara atribut ini dapat ditulis. Memiliki standar itu jelas sangat superior.

Sekarang, untuk manfaatnya?

Fakta bahwa suatu fungsi tidak kembali dapat berguna untuk:

• optimasi: seseorang dapat memangkas kode apa pun setelah itu (tidak akan kembali), tidak perlu menyimpan register (karena tidak perlu mengembalikannya), ...
• analisis statis: ini menghilangkan sejumlah jalur eksekusi potensial
• rawatan: (lihat analisis statis, tetapi oleh manusia)

Jawaban Karl baik. Ini adalah penggunaan tambahan yang menurut saya tidak ada orang lain yang sebutkan. Tipe dari

if E then A else B

harus tipe yang mencakup semua nilai dalam tipe Adan semua nilai dalam tipe B. Jika jenisnya Badalah Nothing, maka jenis ifekspresi dapat berupa jenis A. Saya akan sering menyatakan rutinitas

def unreachable( s:String ) : Nothing = throw new AssertionError("Unreachable "+s) 

untuk mengatakan bahwa kode tidak diharapkan tercapai. Karena tipenya adalah Nothing, unreachable(s)sekarang dapat digunakan dalam ifatau (lebih sering) switchtanpa mempengaruhi jenis hasil. Sebagai contoh

 val colour : Colour := switch state of
         BLACK_TO_MOVE: BLACK
         WHITE_TO_MOVE: WHITE
         default: unreachable("Bad state")

Scala memiliki tipe Nothing.

Kasus penggunaan lain untuk Nothing(sebagaimana disebutkan dalam jawaban Karl) adalah Daftar [Tidak Ada] adalah jenis daftar yang masing-masing anggotanya bertipe Tidak Ada. Dengan demikian dapat menjadi jenis daftar kosong.

Properti utama Nothingyang membuat use case ini bekerja adalah tidak memiliki nilai - walaupun dalam Scala, misalnya, tidak memiliki nilai - itu adalah subtipe dari setiap tipe lainnya.

Misalkan Anda memiliki bahasa tempat setiap jenis berisi nilai yang sama - sebut saja (). Dalam bahasa seperti itu, tipe unit, yang ()hanya memiliki nilai, bisa menjadi subtipe dari setiap tipe. Itu tidak membuatnya menjadi tipe terbawah dalam arti bahwa OP berarti; OP jelas bahwa tipe bawah tidak mengandung nilai. Namun, karena ini adalah tipe yang merupakan subtipe dari setiap tipe, ini dapat memainkan peran yang sama dengan tipe terbawah.

Haskell melakukan sesuatu yang sedikit berbeda. Di Haskell, ekspresi yang tidak pernah menghasilkan nilai dapat memiliki skema tipe forall a.a. Sebuah instance dari skema tipe ini akan menyatu dengan tipe lainnya, sehingga ia secara efektif bertindak sebagai tipe terbawah, meskipun (standar) Haskell tidak memiliki gagasan tentang subtyping. Misalnya, errorfungsi dari pendahuluan standar memiliki skema jenis forall a. [Char] -> a. Jadi kamu bisa menulis

if E then A else error ""

dan tipe ekspresi akan sama dengan tipe A, untuk ekspresi apa pun A.

Daftar kosong di Haskell memiliki skema jenis forall a. [a]. Jika Aadalah ekspresi yang tipenya adalah tipe daftar, maka

if E then A else []

adalah ekspresi dengan tipe yang sama dengan A.

Jenis membentuk monoid dalam dua cara, bersama-sama membuat semiring . Itulah yang disebut tipe data aljabar . Untuk tipe hingga, semiring ini secara langsung berkaitan dengan semiring bilangan asli (termasuk nol), yang berarti Anda menghitung berapa banyak nilai yang mungkin dimiliki tipe tersebut (tidak termasuk "nilai nonterminating").

• Jenis bawah (saya akan menyebutnya Vacuous) memiliki nilai nol ^† .
• Jenis unit memiliki satu nilai. Saya akan memanggil tipe dan nilai tunggal ().
• Komposisi (yang didukung sebagian besar bahasa pemrograman secara langsung, melalui catatan / struct / kelas dengan bidang publik) adalah operasi produk . Misalnya, (Bool, Bool)memiliki empat nilai yang mungkin, yaitu (False,False), (False,True), (True,False)dan (True,True).
  Jenis unit adalah elemen identitas dari operasi komposisi. Misalnya ((), False)dan ((), True)merupakan satu-satunya nilai tipe ((), Bool), jadi tipe ini isomorfik untuk Booldirinya sendiri.
• Jenis-jenis alternatif agak diabaikan di sebagian besar bahasa (bahasa-bahasa OO semacam mendukungnya dengan warisan), tetapi mereka tidak kurang bermanfaat. Alternatif antara dua jenis Adan Bpada dasarnya memiliki semua nilai A, ditambah semua nilai B, maka jenis penjumlahan . Misalnya, Either () Boolmemiliki tiga nilai, saya akan memanggilnya Left (), Right Falsedan Right True.
  Tipe bawah adalah elemen identitas jumlah: hanyaEither Vacuous A memiliki nilai formulir , karena tidak masuk akal ( tidak memiliki nilai).Right aLeft ...Vacuous

Yang menarik dari monoids ini adalah, ketika Anda memperkenalkan fungsi ke bahasa Anda, kategori jenis ini dengan fungsi sebagai morfisme adalah kategori monoid . Di antara hal-hal lain, ini memungkinkan Anda untuk mendefinisikan fungsi aplikatif dan monad , yang ternyata menjadi abstraksi yang sangat baik untuk perhitungan umum (mungkin melibatkan efek samping, dll.) Dalam istilah yang berfungsi murni.

Sekarang, sebenarnya Anda bisa bertindak cukup jauh dengan hanya mengkhawatirkan satu sisi masalah (komposisi monoid), maka Anda tidak benar-benar membutuhkan jenis bottom secara eksplisit. Misalnya, bahkan Haskell untuk waktu yang lama tidak memiliki tipe bottom standar. Sekarang sudah, itu disebut Void.

Tetapi ketika Anda mempertimbangkan gambaran lengkap, sebagai kategori tertutup bicartesian , maka sistem jenisnya sebenarnya setara dengan seluruh kalkulus lambda, jadi pada dasarnya Anda memiliki abstraksi sempurna atas segala yang mungkin terjadi dalam bahasa lengkap Turing. Sangat bagus untuk bahasa khusus domain tertanam, misalnya ada proyek tentang pengkodean sirkuit elektronik secara langsung dengan cara ini .

Tentu saja, Anda mungkin mengatakan bahwa ini semua omong kosong teoretis semua . Anda tidak perlu tahu tentang teori kategori sama sekali untuk menjadi programmer yang baik, tetapi ketika Anda melakukannya, itu memberi Anda cara yang kuat dan luar biasa umum untuk alasan tentang kode, dan invarian invarian.

^† _{mb21 mengingatkan saya untuk mencatat bahwa ini tidak boleh dikacaukan dengan nilai-nilai terbawah . Dalam bahasa malas seperti Haskell, setiap jenis berisi "nilai" terbawah, dilambangkan ⊥. Ini bukan hal konkret yang bisa Anda berikan secara eksplisit, melainkan apa yang "dikembalikan" misalnya ketika fungsi berulang selamanya. Bahkan Voidtipe Haskell "mengandung" nilai terbawah, demikian namanya. Dari sudut pandang itu, tipe dasar Haskell benar-benar memiliki satu nilai dan tipe unitnya memiliki dua nilai, tetapi dalam diskusi kategori-teori ini pada umumnya diabaikan.}

Mungkin loop selamanya, atau mungkin melempar pengecualian.

Kedengarannya seperti tipe yang berguna untuk dimiliki dalam situasi itu, meskipun jarang.

Juga, meskipun Nothing(nama Scala untuk tipe bawah) tidak dapat memiliki nilai, List[Nothing]tidak memiliki batasan itu, yang menjadikannya berguna sebagai jenis daftar kosong. Sebagian besar bahasa mengatasi hal ini dengan membuat daftar string kosong jenis yang berbeda dari daftar kosong bilangan bulat, yang masuk akal, tetapi membuat daftar kosong lebih verbose untuk ditulis, yang merupakan kelemahan besar dalam bahasa berorientasi daftar.

Berguna untuk analisis statis untuk mendokumentasikan fakta bahwa jalur kode tertentu tidak dapat dijangkau. Misalnya jika Anda menulis yang berikut dalam C #:

int F(int arg) {
 if (arg != 0)
  return arg + 1; //some computation
 else
  Assert(false); //this throws but the compiler does not know that
}
void Assert(bool cond) { if (!cond) throw ...; }

Kompiler akan mengeluh bahwa Ftidak mengembalikan apa pun di setidaknya satu jalur kode. Jika Assertditandai sebagai tidak-kembali kompiler tidak perlu memperingatkan.

Dalam beberapa bahasa, nullmemiliki tipe terbawah, karena subtipe dari semua jenis dengan baik mendefinisikan apa yang menggunakan null untuk bahasa (meskipun kontradiksi ringan memiliki nullkeduanya sendiri dan fungsi yang mengembalikan sendiri, menghindari argumen umum tentang mengapa botharus tidak dihuni).

Ini juga dapat digunakan sebagai fungsi tangkap semua ( any -> bot) untuk menangani pengiriman yang serba salah.

Dan beberapa bahasa memungkinkan Anda untuk benar-benar menyelesaikannya botsebagai kesalahan, yang dapat digunakan untuk menyediakan kesalahan penyusun khusus.

Ya ini adalah tipe yang cukup berguna; sementara perannya sebagian besar interior ke sistem tipe, ada beberapa kesempatan di mana tipe bawah akan muncul secara terbuka.

Pertimbangkan bahasa yang diketik secara statis di mana conditionals adalah ekspresi (sehingga konstruksi if-then-else berfungsi ganda sebagai operator ternary C dan teman-teman, dan mungkin ada pernyataan kasus multi-arah yang serupa). Bahasa pemrograman fungsional memiliki ini, tetapi itu terjadi dalam bahasa imperatif tertentu juga (sejak ALGOL 60). Maka semua ekspresi cabang pada akhirnya harus menghasilkan jenis ekspresi bersyarat keseluruhan. Orang bisa saja meminta tipenya sama (dan saya pikir ini adalah kasus untuk operator ternary di C) tetapi ini terlalu membatasi terutama ketika kondisional juga dapat digunakan sebagai pernyataan kondisional (tidak mengembalikan nilai berguna). Secara umum seseorang ingin setiap ekspresi cabang menjadi (secara implisit) dapat dikonversi ke tipe umum yang akan menjadi tipe ekspresi penuh (mungkin dengan batasan yang lebih atau kurang rumit untuk memungkinkan tipe umum tersebut ditemukan secara efektif oleh kompiler, lih. C ++, tapi saya tidak akan membahas detailnya di sini).

Ada dua jenis situasi di mana jenis konversi umum akan memungkinkan fleksibilitas yang diperlukan dari ekspresi kondisional tersebut. Satu sudah disebutkan, di mana tipe hasil adalah tipe unitvoid; ini adalah tipe super dari semua tipe lainnya, dan memungkinkan tipe apa pun untuk (secara sepele) dikonversi menjadi memungkinkan untuk menggunakan ekspresi kondisional sebagai pernyataan kondisional. Yang lain melibatkan kasus di mana ekspresi memang mengembalikan nilai yang berguna, tetapi satu atau lebih cabang tidak mampu menghasilkan satu. Mereka biasanya akan memunculkan eksepsi atau melibatkan lompatan, dan mengharuskan mereka untuk (juga) menghasilkan nilai dari tipe keseluruhan ekspresi (dari titik yang tidak terjangkau) tidak akan ada gunanya. Situasi seperti inilah yang dapat ditangani dengan anggun dengan memberikan klausa kenaikan-kenaikan, lompatan, dan panggilan yang akan memiliki efek seperti itu, tipe terbawah, tipe yang dapat (secara sepele) diubah menjadi tipe lain.

Saya akan menyarankan menulis jenis bawah *untuk menyarankan konvertibilitasnya ke jenis sewenang-wenang. Ini dapat melayani tujuan bermanfaat lainnya secara internal, misalnya ketika mencoba untuk menyimpulkan tipe hasil untuk fungsi rekursif yang tidak menyatakan apa pun, tipe penyimpulan dapat menetapkan tipe *untuk panggilan rekursif apa pun untuk menghindari situasi ayam dan telur; jenis aktual akan ditentukan oleh cabang non-rekursif, dan yang rekursif akan dikonversi ke jenis umum yang non-rekursif. Jika tidak ada cabang non-rekursif sama sekali, jenisnya akan tetap *, dan dengan benar menunjukkan bahwa fungsi tidak memiliki cara yang mungkin untuk kembali dari rekursi. Selain ini dan sebagai jenis hasil fungsi melempar pengecualian, seseorang dapat menggunakan*sebagai jenis komponen urutan panjang 0, misalnya daftar kosong; lagi jika suatu elemen dipilih dari ekspresi tipe [*](tentu daftar kosong), maka tipe yang dihasilkan *akan dengan benar menunjukkan bahwa ini tidak akan pernah bisa kembali tanpa kesalahan.

Dalam beberapa bahasa, Anda dapat membuat anotasi fungsi untuk memberi tahu kompiler dan pengembang bahwa panggilan ke fungsi ini tidak akan kembali (dan jika fungsi ditulis dengan cara yang bisa kembali, kompiler tidak akan mengizinkannya ). Itu hal yang berguna untuk diketahui, tetapi pada akhirnya Anda dapat memanggil fungsi seperti ini seperti yang lainnya. Kompiler dapat menggunakan informasi untuk optimisasi, untuk memberi peringatan tentang kode mati, dan sebagainya. Jadi tidak ada alasan yang sangat kuat untuk memiliki tipe ini, tetapi tidak ada alasan yang sangat kuat untuk menghindarinya juga.

Dalam banyak bahasa, suatu fungsi dapat mengembalikan "void". Apa artinya sebenarnya tergantung pada bahasa. Dalam C berarti fungsi tidak mengembalikan apa pun. Dalam Swift, itu berarti fungsi mengembalikan objek dengan hanya satu nilai yang mungkin, dan karena hanya ada satu nilai yang mungkin nilai mengambil nol bit dan sebenarnya tidak memerlukan kode apa pun. Dalam kedua kasus, itu tidak sama dengan "bawah".

"bottom" adalah tipe tanpa nilai yang memungkinkan. Itu tidak akan pernah ada. Jika suatu fungsi mengembalikan "bottom", ia tidak dapat benar-benar kembali, karena tidak ada nilai dari tipe "bottom" yang dapat dikembalikan.

Jika seorang perancang bahasa merasa menyukainya, maka tidak ada alasan untuk tidak memiliki tipe itu. Implementasinya tidak sulit (Anda dapat mengimplementasikannya persis seperti fungsi yang mengembalikan batal dan ditandai sebagai "tidak kembali"). Anda tidak dapat mencampur pointer ke fungsi yang kembali ke bawah dengan pointer ke fungsi yang mengembalikan batal, karena mereka bukan tipe yang sama).