Menghadirkan tipe data aljabar untuk C99

 (github.com/Hirrolot)
1 poin oleh GN⁺ 2024-05-10 | 1 komentar | Bagikan ke WhatsApp
  • Datatype99 adalah library berbasis makro yang menyediakan tipe data aljabar, pattern matching yang exhaustive, dan introspeksi saat kompilasi di C99 murni
  • Library ini bertujuan menangkap variant yang salah pengetikan tipenya, pattern matching yang tidak lengkap, dan akses field yang keliru pada waktu kompilasi, serta hanya memerlukan compiler C99 yang patuh standar
  • Secara internal, datatype diperluas menjadi tagged union dan value constructor, sedangkan match diperluas menjadi pernyataan switch, dan layout data yang dihasilkan mengikuti semantik generasi kode yang diformalkan
  • Instalasi dilakukan dengan menambahkan datatype99.h dan dependensi Metalang99 ke jalur include, dan pada GCC/Clang disarankan memakai opsi kompilasi untuk mengurangi keluaran error ekspansi makro
  • Dapat diintegrasikan ke codebase C dengan #include <datatype99.h>, diketahui berjalan di GCC, Clang, MSVC, dan TCC, serta juga mendukung C++11 ke atas

Apa yang disediakan Datatype99

  • Datatype99 menyediakan tipe data aljabar yang aman dan intuitif di C99
  • Cakupan fiturnya mencakup pattern matching yang exhaustive dan introspeksi saat kompilasi
  • Berjalan tanpa alat generasi kode eksternal, dan implementasinya berbasis C99 murni
  • Fitur utama
    • Keamanan tipe: menangkap variant yang salah pengetikan tipenya, pattern matching yang non-exhaustive, dan akses field yang salah pada waktu kompilasi
    • Portabilitas: memerlukan compiler C99 yang patuh standar, dan tidak membutuhkan library standar, fitur spesifik compiler/platform, maupun VLA
    • Prediktabilitas: semantik generasi kode didefinisikan sehingga menjamin layout data yang dihasilkan selalu sama
    • Error yang mudah dipahami: library itu sendiri mendeteksi sebagian error sintaks pada kode yang salah
    • Kasus penggunaan nyata: dipakai di OpenIPC untuk pengembangan perangkat lunak streaming real-time bagi kamera IP, termasuk implementasi RTSP 1.0 dan sekitar 50 ribu baris kode privat

Instalasi dan konfigurasi build

  • Datatype99 terdiri dari satu file header datatype99.h dan dependensi Metalang99
  • Untuk memakainya di proyek, tambahkan datatype99 dan metalang99/include ke direktori include
  • Di GCC, disarankan menetapkan -ftrack-macro-expansion=0, dan di Clang -fmacro-backtrace-limit=1, untuk mengurangi keluaran error ekspansi makro yang tidak perlu
  • Saat menggunakan CMake, direkomendasikan memakai FetchContent
    • datatype99/CMakeLists.txt bawaan akan mengunduh Metalang99 v1.13.5 dari GitHub Releases
    • Perilaku ini dapat dioverride dengan memanggil FetchContent_Declare sebelumnya
  • Header yang bergantung pada Datatype99 dapat dijadikan precompiled header, sehingga tidak perlu dikompilasi ulang setiap kali di-include dan waktu kompilasi bisa dipangkas

Cara penggunaan: memakai tagged union dengan lebih aman

  • Pada dasarnya, Datatype99 adalah syntactic sugar untuk tagged union, yang memberikan bentuk yang lebih aman dan ringkas
  • Dalam C biasa, untuk merepresentasikan pohon biner Anda harus menulis sendiri enum tag dan union
  • Di Datatype99, struktur yang sama bisa dideklarasikan seperti berikut
datatype(
    BinaryTree,
    (Leaf, int),
    (Node, BinaryTree *, int, BinaryTree *)
);
  • Dalam pendekatan switch biasa, compiler mungkin tidak memberi peringatan walau Anda keliru mengakses tree->data.node setelah case Leaf:
  • Dengan match dan of, binding per-variant hanya terlihat di cabang tersebut, dan akses yang tidak semestinya akan membuat kompilasi gagal
int sum(const BinaryTree *tree) {
    match(*tree) {
        of(Leaf, x) return *x;
        of(Node, lhs, x, rhs) return sum(*lhs) + * x + sum(*rhs);
    }

    return -1;
}
  • Binding yang disediakan of berupa variabel seperti x, lhs, rhs, dan bertipe pointer sehingga nilainya bisa diubah
  • Untuk membuat variant digunakan value constructor yang dihasilkan secara internal
BinaryTree leaf5 = Leaf(5);
BinaryTree leaf7 = Leaf(7);
BinaryTree node = Node(&leaf5, 123, &leaf7);

Sintaks dan semantik generasi

  • Datatype99 menyediakan sintaks makro seperti datatype, record, match, of, otherwise, MATCHES, ifLet, dan lainnya
  • Nama makro singkat dan versi ber-postfix tersedia bersamaan
    • Contoh: match99, of99, derive99
    • Untuk menghindari konflik nama, Anda dapat mendefinisikan DATATYPE99_NO_ALIASES sebelum include datatype99.h
    • Pada header library, disarankan memakai makro versi postfix
  • datatype menghasilkan elemen-elemen berikut
    • typedef forward
    • struct untuk setiap variant yang tidak kosong
    • typedef untuk tipe field variant
    • typedef untuk sum type
    • tagged union yang mencakup enum tag dan union
    • value constructor inline static untuk tiap variant
    • pemanggilan deriver yang ditentukan di derive(...)
  • Walau semua variant kosong, standar C tetap mengharuskan union memiliki setidaknya satu anggota, sehingga ditambahkan char dummy;
  • record adalah struct dengan proses derivation yang didefinisikan, dan jika tidak punya field juga akan menghasilkan char dummy;
  • match membandingkan instance sum type dengan variant secara berurutan, menjalankan pernyataan pada cabang yang berhasil, lalu berpindah ke instruksi berikutnya
  • Bentuk lengkap match dan ifLet masing-masing diperluas menjadi satu pernyataan C
  • MATCHES memeriksa benar/salah apakah instance sum type termasuk variant tertentu
  • matches sudah deprecated dan disarankan menggunakan MATCHES

derive dan atribut pembantu

  • derive(...) digunakan untuk menghasilkan kode global bagi sum type atau record
  • Deriver untuk sum type dipanggil dalam bentuk makro yang kompatibel dengan Metalang99, dan daftar variant dikirim sebagai tuple list
  • Deriver untuk record juga dipanggil sebagai makro kompatibel Metalang99, dan daftar field dikirim sebagai tuple list berbentuk (<type>, <field-name>)
  • Derive helper attribute adalah argumen bernama yang diteruskan ke deriver
  • Helper attribute menggunakan bentuk object-like macro
#define <variant-name>_<namespace>_<attribute-name> attr(/* attribute value */)
  • Makro manipulasi atribut yang disediakan
    • DATATYPE99_attrIsPresent / DATATYPE99_ATTR_IS_PRESENT: memeriksa apakah atribut ada
    • DATATYPE99_attrValue / DATATYPE99_ATTR_VALUE: mengambil nilai atribut yang ada
    • DATATYPE99_assertAttrIsPresent: memunculkan fatal error jika atribut wajib tidak ada

Pola penggunaan yang perlu diperhatikan

  • Jangan memakai break/continue tingkat teratas di dalam pernyataan yang diberikan ke of dan ifLet
    • continue di dalam loop for/while internal tetap aman
    • Alur kontrol tingkat teratas harus diganti dengan label goto
  • Jika ingin menetapkan array sebagai parameter variant, array tersebut harus dimasukkan ke struct terpisah
  • Binding yang diperkenalkan of selalu mutable, jadi bila nilai yang diberikan ke match adalah const, berhati-hatilah agar tidak mengubahnya
  • Agar definisi datatype tetap rapi, Anda bisa memakai // clang-format off dan // clang-format on di Clang-Format
  • Derive helper attribute harus selalu di-#undef setelah definisi datatype terkait untuk menghindari polusi namespace
  • Jika makna parameter variant tidak jelas hanya dari konteks, Anda dapat memberi nama yang lebih deskriptif melalui type alias atau struct terpisah

Error, IDE, kompatibilitas

  • Sebagian error sintaks dideteksi oleh library itu sendiri
    • bentuk yang bukan tuple seperti Bar(int)
    • comma yang hilang
    • trailing comma yang dilarang
  • Error lainnya akan muncul lewat diagnostik compiler biasa
    • nama tipe yang tidak ada
    • match yang non-exhaustive
    • binder berlebih pada of
    • argumen variant dengan tipe yang salah
    • pengembalian tanpa melakukan dereferensi pada binding pointer
  • Berdasarkan pengalaman, hampir 95% error dikatakan terlihat bermakna
  • Jika error sulit dipahami, Anda bisa memeriksa kode hasil generasi dengan -E, dan karena semantik generasi kode didefinisikan secara formal, biasanya tidak akan muncul kode yang tak terduga
  • VS Code otomatis mengaktifkan saran untuk tipe yang dihasilkan, tetapi tidak mendukung highlighting sintaks makro
  • Datatype99 diketahui berjalan di GCC, Clang, MSVC, dan TCC
  • C++11 ke atas juga didukung

Alasan menargetkan C dan keterbatasannya

  • Perangkat lunak lama yang ditulis dalam C murni dapat memperoleh manfaat dari Datatype99
  • Pada codebase C yang sudah ada, integrasi cukup dengan #include <datatype99.h>
  • Di beberapa lingkungan, C murni tetap dipertahankan karena alasan historis, seperti pada perangkat embedded, Linux, dan sistem operasi lain
  • ABI C yang stabil penting bagi proyek sistem plugin seperti MetaCall
  • C diposisikan sebagai bahasa yang matang dengan spesifikasi lengkap dan banyak library
  • Jika Anda bisa memakai bahasa yang lebih modern atau lebih high-level, disarankan memakai bahasa tersebut alih-alih C lama, tetapi bagi banyak orang pilihan itu tidak tersedia atau biayanya besar
  • Perbedaan Datatype99 dan Metalang99 terletak pada perannya
    • Metalang99 adalah bahasa fungsional untuk metaprogramming
    • Datatype99 adalah implementasi tipe data aljabar yang ditulis dengan Metalang99

Bacaan terkait

1 komentar

 
GN⁺ 2024-05-10
Komentar Hacker News
  • Setiap kali memakai bahasa imperatif, hampir selalu merasa rindu pada algebraic data type
    Di pekerjaan saya harus memakai Java, dan sekarang saya merasa Java tidak seburuk yang dulu sering saya kritik, tetapi ada puluhan momen ketika saya berpikir, “andai Java punya discriminated union seperti F#”
    Memang bisa ditiru dengan berbagai teknik, dan kadang enum saja sudah cukup, tetapi kebanyakan pendekatan itu tidak punya fleksibilitas dan keringkasan dari algebraic data type yang sesungguhnya. Yang paling utama, tidak ada pattern matching keren yang biasa didapat di bahasa fungsional
    Ekstensi C ini terlihat punya pattern matching yang saya inginkan, jadi tampak cukup bagus, dan saya harus lihat apakah ini bisa dipakai untuk proyek Arduino
    • Orang yang belum pernah memakai algebraic data type dan pattern matching tidak paham apa yang istimewa, dan bahkan orang yang sudah akrab dengannya pun sering baru benar-benar paham setelah bekerja dengan bahasa yang tidak memilikinya
      Orang yang baru menemukannya biasanya tidak bisa berhenti bicara seolah ini penemuan terbaik sejak roti :)
    • Dengan sealed interface di Java 21, pattern matching dimungkinkan
    • Kotlin kompatibel dengan JVM dan punya algebraic data type
      Untuk Java ada https://github.com/functionaljava/functionaljava, dan meski dukungannya sudah dihentikan, library itu stabil
    • Algebraic data type dan pattern matching sebenarnya juga bekerja sangat baik di bahasa imperatif. Contohnya Rust
  • Jika saya mengimplementasikan ulang produk dari nol, discriminated union dengan pattern matching lengkap yang dipaksakan compiler akan jadi syarat mutlak
    Itu terlalu kuat untuk tidak dimiliki
    • Hal yang paling saya inginkan di Dart adalah union type, tetapi sayangnya tampaknya belum akan ditambahkan dalam waktu dekat
      Baru-baru ini sudah ada dukungan pattern matching yang dipaksakan compiler di atas sealed class, jadi rasanya sudah setengah jalan
    • Bahasa apa saja yang sekarang cocok dengan deskripsi itu? Saya tidak yakin benar apa maksudnya, tetapi sepertinya saya akan lebih paham jika melihat contoh dari bahasa yang mendukungnya
  • Ini jelas terlihat lebih baik dan mungkin bekerja lebih baik daripada percobaan saya dulu [1], tetapi kodenya 8 kali lebih banyak dan bergantung pada toolkit makro Metalang9 yang hebat namun agak menakutkan
    Jika ingin melihat bagaimana algebraic data type bekerja di balik layar, menurut saya libsum adalah bahan pengantar yang bagus
    [1] https://github.com/naasking/libsum
    • Melihat saya sudah memberi bintang pada repositori itu, sepertinya saya memang sempat melihatnya saat merancang Datatype99 :)
  • Ini karya seorang penyihir
    Saya sudah mengenal C hampir 20 tahun, tetapi tidak pernah menyangka sistem makro cukup kuat untuk memungkinkan sihir hitam seperti ini
    Benar-benar keren
    • Penulisnya baru 19 tahun. Tiba-tiba saya merasa seperti orang bodoh
    • metalang99 buatan penulis yang sama juga mungkin menarik
    • x-macro, yaitu gaya penggunaan makro seperti ini, memang cukup mencolok
      Secara tradisional ini dipakai untuk membuat dan mengakses generic yang type-safe, atau untuk mengurangi kode berulang pada definisi register perangkat keras dan interupsi
      Rasanya memang agak terkutuk, tetapi intinya sebenarnya sangat sederhana, dan ini adalah alat yang andal untuk mengurangi kompleksitas kognitif dan boilerplate dalam proyek berbasis C
    • Algebraic data type pada dasarnya hanyalah generic struct dan union dengan tag union yang ditempelkan melalui substitusi string
      Untuk ukuran penggunaan makro, ini tidak terlalu rumit
  • Ada hal menarik terkait ini di Wikipedia. Union diimplementasikan sebagai “hierarki kelas dalam pemrograman berorientasi objek”
    https://en.wikipedia.org/wiki/Tagged_union#Class_hierarchies...
    Ada juga tulisan blog panjang yang membahas hal yang sama, tetapi penulisnya tampaknya belum melihat bagian Wikipedia itu
    https://nandakumar.org/blog/2023/12/paradigms-in-disguise.ht...
    Patut dipuji bahwa pengembang datatype99 langsung menunjukkan masalah dari solusi tambal sulam seperti ini di README
  • Ada juga https://melt.cs.umn.edu/, ekstensi yang menambahkan template dan algebraic data type ke C
    https://github.com/melt-umn/ableC-template-algebraic-data-ty...
  • Kalimat “jangan gunakan break/continue tingkat teratas di dalam statement yang diberikan ke of dan ifLet, gunakan goto label sebagai gantinya” tampak seperti jebakan besar
    Meski begitu, selain itu semuanya sangat keren
    • Memakai goto sendiri bukan masalah, tetapi kita memang harus tahu bahwa break/continue tidak boleh dipakai di dalam blok seperti itu
      Ini mengingatkan saya pada UI mode instan yang dulu pernah saya buat dengan makro. Dalam kasus saya itu bukan masalah, tetapi di beberapa blok, "break" memang bisa dipakai
      Misalnya, di blok win_form kita bisa keluar dengan "break" dan "goto" juga berfungsi. Sebaliknya, blok win_command tidak menangkap "break", jadi jika memakai break atau goto di dalam win_command, itu akan keluar dari blok luar yang membungkus win_command tersebut, mungkin blok win_form. Biasanya ini dipakai untuk hal seperti tombol "Cancel"
    • Hal yang bagus dari ranah makro Rust adalah bukan hanya memungkinkan untuk menulis kode yang memeriksa syarat seperti ini, tetapi itu juga realistis untuk dilakukan, masuk akal untuk dibayangkan, dan bisa dibantu oleh library open source yang mudah dipasang
      Bukan sekadar sedikit lebih baik dalam beberapa hal, melainkan menghaluskan banyak ketidaknyamanan kecil yang menumpuk seiring waktu di seluruh ekosistem. Efek kumulatifnya besar, seperti masalah terlalu banyak tipe leksikal bawaan di keluarga CPython, atau seperti yang terjadi di library komputasi performa tinggi
      Misalnya, bagian dari makro ini yang menimbulkan masalah seperti ini kemungkinan sejak awal tidak akan jadi masalah jika ditulis sebagai makro Rust yang baik. Ini adalah produk sampingan dari orang-orang pintar yang berusaha mengakali keterbatasan C

Namun, makro ini sendiri pada dasarnya adalah port dari fitur native Rust, jadi di Rust kemungkinan besar ini memang sejak awal tidak perlu ditulis, dan karena itu bisa dimanfaatkan secara alami dalam perangkat lunak komunitas

  • goto hanya jadi jebakan saat dipakai untuk berpindah dari satu fungsi ke fungsi lain, dan sebenarnya “goto considered harmful” juga menyorot praktik itu
    Praktik seperti itu sudah hilang, dan sekarang goto di dalam fungsi sendiri cukup tidak berbahaya, pada praktiknya hampir sama dengan break/continue
  • Misalkan Anda harus menulis program C, dan benar-benar membutuhkan pattern matching yang lengkap untuk tagged union. Yang disediakan Datatype99 juga, "singkatnya, hanyalah gula sintaks di atas tagged union"
    Dan misalkan Anda juga sudah tahu bahwa Rust itu ada, tetapi karena alasan yang sudah dipahami semua orang yang menulis program C, Anda tidak akan memakai Rust
    Meski begitu, setidaknya Zig layak dipertimbangkan. Dua hari lalu saya menulis kode seperti ini dalam Zig
    Dengan inline else milik comptime, saya menghasilkan semua cabang dari pernyataan switch di atas tagged union, lalu menambahkan offset ke anggota union yang memiliki field "l". Jika informasinya adalah informasi tipe yang bisa diketahui saat kompilasi, sifat cabangnya bisa diubah dengan berbagai cara, dan informasi seperti itu cukup banyak. Karena semua kondisi diputuskan saat kompilasi, setiap cabang switch hanya berisi logika yang diperlukan untuk menangani varian tersebut
    “Tapi program saya sudah C dan saya hanya membutuhkannya di satu berkas,” kalau begitu pun tetap ada baiknya mencoba Zig. Mungkin Anda akan menyukainya
  • Bukankah dengan struct + union + enum kita sudah bisa mendapatkan sebagian besar manfaat tipe data aljabar? Saya pernah memakai pola yang menaruh union dari beberapa tipe lalu menambahkan enum untuk membedakan mana yang dipilih
    std::variant juga tampaknya sampai taraf tertentu bekerja seperti sum type
    Satu-satunya masalah adalah kita tidak bisa membuat switch yang rapi berdasarkan nilai tertentu dari field, tetapi switch bertingkat juga tidak terlalu berantakan
    • Benar. Hanya dengan konvensi dan disiplin pun kita bisa mendapatkan banyak manfaat pemrograman berorientasi objek, tetapi untuk melakukannya kita harus, misalnya, menangani vtable secara manual, sehingga kita sering harus turun ke detail implementasi
      Masalah pendekatan ini adalah beban mental untuk menjaga semua detail itu tetap lengkap sangat besar. Karena lelah, kita jadi mulai memaksakan fitur ke kelas yang sudah ada alih-alih membuat kelas baru
      Pada akhirnya abstraksi terasa mahal, dan akibatnya kita jadi lebih jarang menggunakannya meskipun sebenarnya abstraksi bisa menyelesaikan masalah dengan lebih elegan
      Singkatnya, kemampuan untuk mengatakan “Darmok and Jalad at Tanagra” alih-alih harus mengulang cerita panjang setiap kali ingin merujuk pada gagasan yang rumit itu bersifat transformatif
    • Aspek pemodelannya bisa ditiru. Tetapi itu bahkan bukan setengah dari manfaat tipe data aljabar
      Pattern matching adalah keuntungan kegunaan yang besar
    • Saat menangani nilai sum type, sangat penting untuk memastikan bahwa semua alternatif sudah diperiksa
      Ini sulit dilakukan dengan makro, tetapi bukan tidak mungkin. Pada dasarnya dibutuhkan makro yang memulai konteks matching, memperkenalkan variabel untuk melacak semua alternatif yang sudah diperiksa, lalu di akhir konteks matching memeriksa apakah semua alternatif memang sudah dicek
    • Untuk sebagian besar kode, memakai C++ saat benar-benar perlu umumnya cukup masuk akal, tetapi saya tidak terlalu suka std::variant
      Cara mencocokkan semua kasus tanpa ada yang terlewat dengan std::visit terasa agak hacky. Kalau ini benar-benar menjadi fitur bahasa kelas satu, manfaatnya akan besar
      Dampaknya pada kode sehari-hari bisa lebih besar daripada fitur-fitur lain yang selama ini sedang dikerjakan, seperti coroutine
  • Benar-benar mengesankan bahwa ini berhasil diimplementasikan. Hormat saya