👊🏿 🎈 👩🏽‍🤝‍👩🏻 Implementasi ekstensi Pola Aktif untuk bahasa OCaml 🚈 💴 🏰

tentang proyek tersebut

Pada musim semi 2020, sebagai bagian dari praktik musim semi di Computer Science Center, saya mengembangkan desain baru untuk bahasa pemrograman OCaml di bawah bimbingan ketat Dmitry Kosarev .

Mengapa OCaml

OCaml adalah salah satu implementasi yang paling sukses dan berkembang dari sinkretisme pemrograman industri (karenanya multiparadigma, multiplatform, kompiler sangat cepat, produktivitas tinggi kode yang dihasilkan) dan matematika (karenanya sistem tipe yang canggih dengan implementasi kuat dari inferensi tipe, ekspresif dan ekstensibilitas bahasa, kedekatan dengan notasi matematika dan semantik).

Pada saat yang sama, komunitas bahasa sangat selektif dan perlahan-lahan menambahkan ke bahasa hanya konstruksi yang sangat menuntut, asalkan mereka tidak memperkenalkan batasan ke dalam bahasa yang ada. Oleh karena itu, inti bahasanya sangat kecil dan intuitif, dan OCaml digunakan dengan senang hati oleh pengembang industri dan, katakanlah, ahli matematika dari Departemen Aljabar Tinggi dan Teori Bilangan Universitas Negeri St. Petersburg .

Untuk lebih mendalami topik ini, saya sarankan untuk melihat artikel OCaml untuk massa dan Mengapa OCaml .

Saat ini, pekerjaan sedang dilakukan untuk mengimplementasikan sistem multi inti untuk OCaml, ditambah dengan efek aljabar, yang secara bersamaan akan meningkatkan kinerja bahasa secara keseluruhan dan menghilangkan batasan yang ada dari sistem tipe yang terkait dengan fakta bahwa bahasa memungkinkan penghitungan yang tidak murni.

Pencocokan pola dan pola aktif

Pekerjaan saya berfokus terutama pada konstruksi pencocokan pola, yang banyak digunakan dalam bahasa pemrograman fungsional.

Untuk mengilustrasikan, pertimbangkan contoh sederhana dari memutar node di pohon biner. Dalam gaya imperatif yang paling umum, kodenya mungkin akan terlihat seperti ini:

type 'a tree =
  | Node of 'a tree * 'a * 'a tree
  | Nil
let rotate_left' t =
  if is_node t
  then
    let a = get_left  t in
    let p = get_value t in
    let r = get_right t in
    if is_node r
    then
      let b = get_left  t in
      let q = get_value t in
      let c = get_right t in
      Node(Node(a,p,b),q,c)
    else t
  else t

Dan inilah kode yang sama persis yang ditulis menggunakan konstruksi pencocokan pola:

let rotate_left = function
  | Node(a, p, Node(b, q, c)) -> Node(Node(a, p, b), q, c)
  | Node _ | Nil as x -> x

Saat menggunakan desain ini, kami memiliki keuntungan sebagai berikut:

ekspresi tinggi;
pemeriksaan kelengkapan , yang merupakan properti penting untuk pemeriksaan kebenaran dan pemfaktoran ulang program;
skema kompilasi yang efisien.

Pemeriksaan kelengkapan berarti bahwa compiler, yang mengetahui definisi tipe, dapat memeriksa setiap kecocokan apakah benar bahwa semua alternatif yang mungkin telah diurai dan bahwa tidak ada cabang yang tidak dapat dijangkau, tidak peduli seberapa kompleks sampel dan tidak peduli bagaimana mereka saling berpotongan. Jadi, jika Anda mengubah definisi tipe (dengan menambahkan alternatif baru, menghapus atau mengubah yang sudah ada), kompilator akan dengan senang hati memberi Anda semua tempat di kode yang terpengaruh secara langsung.

Misalnya, jika saya menambahkan konstruksi baru ke pohon sintaks, kompilator akan menunjukkan kode pengetikan AST ke badan fungsi, di mana saya perlu menulis kode pengetikan untuk konstruksi baru:

Properti ini membuat OCaml sangat tahan terhadap pemfaktoran ulang dan perubahan kode lainnya.

Terlepas dari semua keuntungan yang dijelaskan, ada satu batasan yang sangat serius pada penerapan. Pernahkah Anda menyadarinya? Definisi tipe harus bersifat publik (sehingga kompilator dapat menampilkan alternatif yang menyusunnya). Dan ini, tentu saja, segera menguraikan bahkan abstraksi yang paling sederhana. Misalnya, jika kita ingin mendefinisikan antarmuka daftar yang paling sederhana, tidak ada cara untuk memberi tahu sebelumnya definisi tipe mana yang akan diekspor:

module type List = sig
  type 'a t (* = ? *)
  val cons:  'a -> 'a t -> 'a t
  val empty: 'a t
  val head:  'a t -> ('a * 'a t) option
end

Namun, masalah ini tidak mendasar, dan, seperti dicatat pada tahun 1987, adalah mungkin untuk mencapai pencocokan pola pada tipe abstrak.

Rumusan masalah

Sejak tahun 1987, banyak desain berbeda telah disajikan dalam literatur untuk memecahkan masalah ini, berikut hanya beberapa di antaranya:

Pada awal proyek, pekerjaan telah dilakukan pada pilihan yang masuk akal dan obyektif dari solusi spesifik untuk implementasi , yang paling menguntungkan adalah ekstensi pola aktif yang diimplementasikan dalam bahasa F #.

Tujuan dari proyek ini adalah untuk mulai menerapkan Pola Aktif untuk penyusun OCaml dan bekerja sama sejauh mungkin.

Pola aktif

Ide pola Aktif (serta ekstensi serupa) sangat sederhana: karena abstraksi dicapai dengan menyembunyikan implementasi di dalam fungsi, maka perlu untuk mengizinkan panggilan ke fungsi di dalam pencocokan pola yang akan mengubah nilai yang tidak diketahui dari tipe data abstrak menjadi daftar alternatif yang diketahui. Pola aktif menyandikan daftar alternatif ini tepat di dalam nama fungsi. Jadi, pada antarmuka daftar di atas, Anda perlu menambahkan fungsi berikut (|Cons|Nil|):

module type List = sig
  type 'a t
  val (|Cons|Nil|): 'a t -> ('a * 'a t, unit) choice2
  val cons:  'a -> 'a t -> 'a t
  val empty: 'a t
  val head:  'a t -> ('a * 'a t) option
end

Hasilnya adalah jenis penjumlahan anonim choice2yang memiliki definisi berikut (ada jenis yang dihasilkan serupa hingga choice32):

type ('a, 'b) choice2 =
  | Choice2_1 of 'a
  | Choice2_2 of 'b

Dengan demikian, fungsi tersebut (|Cons|Nil|)akan mengubah daftar menjadi salah satu dari dua alternatif: sepasang kepala dan ekor daftar, atau ke alternatif kosong yang berarti bahwa daftar itu kosong.

Mendefinisikan fungsi seperti itu untuk daftar standar itu sepele dan akan terlihat seperti ini:

let (|Cons|Nil|) = function
  | []      -> Nil
  | x :: xs -> Cons(x, xs)

Sebagai contoh penggunaan, pertimbangkan fungsi yang menghapus duplikat berurutan dalam daftar:

(* destutter [1;1;4;3;3;2] = [1;4;3;2] *)
let rec destutter = function
  | Nil -> nil
  | Cons(x, Nil) -> cons x empty
  | Cons(x, Cons(y, rest)) ->
      if x = y 
      then destutter (cons y rest)
      else cons x (destutter (cons y rest))

Perhatikan bahwa semua manfaat pencocokan pola dipertahankan: sintaks yang cocok tetap sama dan pemeriksaan kelengkapan dapat bekerja secara penuh. Mengompilasi solusi seperti itu secara efisien berada di luar cakupan ikhtisar ini, tetapi itu juga mungkin.

Kemajuan

Sebagai bagian dari pekerjaan ini, dimungkinkan untuk mengimplementasikan parsing dan mengetik ekstensi untuk kompilator OCaml versi 4.09, hasilnya disajikan di sini .

Pengurai kompiler diimplementasikan menggunakan generator parser Menhir tingkat lanjut . Menhir memiliki manual yang cukup lengkap dan mendetail , tetapi bahkan bersamanya tidak selalu jelas bagaimana Anda dapat mengatur aturan inferensi, dan bagaimana tidak dan mengapa. Patch parser yang dihasilkan cukup kecil dan sederhana, tetapi jalur menuju ke sana melalui 10-15 shift-kurangi dan kurangi konflik, analisis dan perbaikan yang membutuhkan beberapa waktu:

Saya ingin memberikan penghormatan kepada para pengembang Menhir dan berterima kasih kepada mereka atas pekerjaan yang telah dilakukan dalam merinci dan mengklarifikasi kesalahan. Setelah parser-generator gagal menggambarkan konflik dan harus membongkarnya menggunakan otomat yang dibangun untuk 1500 negara bagian. Ini tentu saja membutuhkan waktu yang lebih lama.

Pengetikan ekstensi sangat sulit. Kode pengetikan sekitar 37.000 baris dan hampir tidak berdokumen, sehingga sulit bagi pemula untuk mengetahuinya. Saya diselamatkan oleh sebuah artikel oleh Oleg Kiselev , yang menjelaskan aspek-aspek kunci dari implementasi.

Kesimpulan lain yang saya buat untuk diri saya sendiri adalah tidak lupa menggunakan proyek versi lama. Misalnya, berikut ini perbandingan kuantitatif dari jenis pengetikan yang sama di versi 2019 dan 2005:

Versi 2019 berisi analisis dan peringatan kompiler, serta detail teknis tambahan yang tidak saya minati. Untuk memahaminya, saya hanya perlu melihat versi 2005, yang hanya berisi aksi kunci.

Akhirnya, kesimpulan utama yang saya buat selama pekerjaan saya adalah konfirmasi bahwa dokumentasi untuk proyek sumber terbuka sangat penting. Meskipun bahasanya ekspresif, kode sumber hanya dapat memberi tahu bagaimana suatu fungsi berperilaku, bukan apa fungsinya atau mengapa ia melakukannya seperti itu. Sangat sulit untuk membaca rantai panggilan type_self_pattern-> type_cases-> t ype_pat-> type_pat'-> type_pat_auxdan mencari tahu fungsi mana yang Anda butuhkan; atau hanya satu nama parameterconstrtebak konstruktor apa dan mengapa harus ditulis di sini.

Kebutuhan untuk melihat kasus penggunaan setiap kali memperlambat programmer dan cepat lelah: izinkan saya mengingatkan Anda aturan "tujuh, plus atau minus dua" - sama seperti banyak objek yang dapat diingat secara bersamaan oleh seseorang, secara rata-rata. Dan ketika Anda akhirnya memahami arti parameter di dalam fungsi bersarang keenam dan tiba-tiba menyadari bahwa Anda tidak ingat mengapa Anda membutuhkannya, atau ternyata Anda tidak membutuhkannya, itu menjadi sangat menyedihkan karena banyaknya waktu yang dihabiskan.

Kesimpulan

Sebagai bagian dari sebuah proyek, saya dapat mengimplementasikan penguraian dan pengetikan untuk pola Aktif. Kompiler yang saya tambal dapat mengurai dan mengetik file dengan contoh penggunaan pola Aktif.

Selanjutnya, Anda perlu mengubah skema kompilasi (OCaml menggunakan kompilasi pengoptimalan non-trivial yang mengoptimalkan pencocokan pola) dan pemeriksaan kelengkapan skema, yang hampir seluruhnya ditulis ulang oleh tim pengembangan kompilator OCaml selama proyek berlangsung.

Saya berharap implementasi ini akan tetap selesai, dengan atau tanpa saya. Terlepas dari semua kesulitan tersebut, sangat menyenangkan untuk mencoba sendiri mengembangkan kompiler industri untuk bahasa favorit Anda.

Penulis:

Alexander Bashkirov adalah mahasiswa Pusat Ilmu Komputer dan program sarjana tahun ke-4 di bidang Rekayasa Perangkat Lunak di Universitas Negeri St. Petersburg, seorang karyawan JetBrains.

Implementasi ekstensi Pola Aktif untuk bahasa OCaml