ZuriHac: mempraktikkan pemrograman fungsional

Pada bulan Juni tahun ini, sebuah acara yang disebut ZuriHac diadakan untuk kesepuluh kalinya di kota kecil Swiss Rapperswil. Kali ini lebih dari lima ratus pecinta Haskell berkumpul dari pemula hingga pendiri bahasa. Meskipun penyelenggara menyebut acara ini hackathon, itu masih bukan konferensi atau hackathon dalam arti klasik. Formatnya berbeda dari pemrograman tradisional. Kami belajar tentang ZuriHac karena kebetulan yang kebetulan, berpartisipasi di dalamnya, dan sekarang kami menganggapnya sebagai tugas kami untuk memberi tahu tentang penemuan yang tidak biasa!

Tentang kami

Artikel ini disiapkan oleh dua siswa tahun ke-3 dari program Matematika dan Ilmu Komputer Terapan Sekolah Tinggi Ekonomi - St. Petersburg: Vasily Alferov dan Elizaveta Vasilenko. Gairah untuk pemrograman fungsional untuk kami berdua dimulai dengan serangkaian kuliah oleh D.N. Moskvin di tahun ke-2 universitas. Saat ini, Vasily berpartisipasi dalam program Google Summer of Code, dalam kerangka yang ia terlibat dalam implementasi grafik aljabar dalam bahasa Haskell di bawah bimbingan tim proyek Alga . Elizabeth menerapkan keterampilan yang diperoleh dari pemrograman fungsional dalam pekerjaan kursus yang ditujukan untuk implementasi algoritma anti-unifikasi dengan penggunaan selanjutnya dalam teori tipe.

Format Acara

Target audiens adalah pemilik proyek open source, programmer yang ingin berpartisipasi dalam pengembangan mereka, peneliti pemrograman fungsional dan hanya orang-orang yang bersemangat tentang Haskell. Tahun ini, tempat HSR Hochschule für Technik Rapperswil University menyatukan pengembang dari lebih dari lima puluh proyek Haskell open-source dari seluruh dunia untuk berbicara tentang produk mereka dan menarik minat orang-orang baru dalam pengembangan mereka.



Foto dari Twitter ZuriHac

Skema ini sangat sederhana: Anda perlu menulis beberapa proposal sebelumnya tentang proyek Anda dan mengirimkannya ke penyelenggara, yang akan memposting informasi tentang proyek Anda di halaman acara. Selain itu, pada hari pertama, para penulis proyek memiliki waktu tiga puluh detik untuk menceritakan secara singkat dari tahap apa yang mereka lakukan dan apa yang perlu dilakukan. Kemudian, orang yang tertarik mencari penulis dan bertanya secara detail tentang tugas.

Kami belum memiliki proyek terbuka kami sendiri, tetapi kami benar-benar ingin berkontribusi pada yang sudah ada, jadi kami mendaftar sebagai peserta reguler. Selama tiga hari kami bekerja dengan dua tim pengembangan. Ternyata studi bersama kode dan komunikasi langsung membuat interaksi antara penulis dan kontributor proyek sangat produktif - di ZuriHac kami dapat menemukan area baru untuk kami dan dapat membantu dua tim yang sangat berbeda dengan menutup tugas di setiap proyek.

Selain latihan yang berharga, beberapa kuliah dan kelas master juga diberikan di ZuriHac. Kami terutama mengingat dua kuliah. Pada yang pertama ini, Andrei Mokhov dari University of Newcastle berbicara tentang fungsi aplikatif selektif - suatu kelas tipe yang harus menjadi perantara antara fungsi aplikator dan monad. Dalam kuliah lain, salah satu pendiri Haskell, Simon Peyton Jones, berbicara tentang bagaimana inferensi tipe bekerja di kompiler GHC.



Kuliah oleh Simon Peyton Jones. Foto dari Twitter ZuriHac

Kelas master yang diadakan selama hackathon dibagi menjadi tiga kategori tergantung pada tingkat pelatihan para peserta. Tugas yang ditawarkan kepada peserta yang bergabung dalam pengembangan proyek juga memiliki catatan dengan tingkat kesulitan. Komunitas kecil tetapi ramah dari programmer fungsional senang untuk menyambut pendatang baru ke jajaran mereka. Namun, untuk memahami kuliah Andrei Mokhov dan Simon Peyton Jones, program pemrograman fungsional yang lulus di universitas sangat berguna bagi kami.

Untuk peserta biasa dan penulis proyek, pendaftaran untuk acara ini gratis. Kami melamar untuk berpartisipasi pada awal Juni, setelah itu kami dengan cepat dipindahkan dari daftar tunggu ke daftar peserta yang dikonfirmasi.

Dan sekarang kita akan berbicara tentang proyek dalam pengembangan yang kami ikuti.

Pandoc

Pandoc adalah konverter universal dari dokumen teks, pada kenyataannya - dari format apa saja ke apa saja. Misalnya, dari docx ke pdf, atau dari Markdown ke MediaWiki. Penulisnya, John MacFarlane, adalah seorang profesor filsafat di University of California, Berkeley. Secara umum, Pandoc cukup terkenal, dan beberapa teman kami terkejut ketika mereka mengetahui bahwa Pandoc ditulis dalam Haskell.



Daftar format dokumen yang didukung oleh Pandoc. Situs ini juga memiliki grafik lengkap, tetapi gambar ini tidak cocok dengan artikel.

Tentu saja, Pandoc tidak menerapkan konversi langsung untuk setiap pasangan format. Untuk mendukung serangkaian transformasi yang sedemikian luas, solusi arsitektur standar digunakan: pertama, seluruh dokumen diterjemahkan ke dalam representasi perantara internal khusus, dan kemudian dokumen dalam format yang berbeda dihasilkan dari representasi internal ini. Pengembang menyebut representasi internal "AST", yang merupakan singkatan dari Pohon Sintaksis Abstrak, atau pohon sintaksis abstrak . Anda dapat melihat representasi perantara dengan sangat sederhana: untuk ini Anda hanya perlu menetapkan "asli" sebagai format output

$ cat example.html <h1>Hello, World!</h1> $ pandoc -f html -t native example.html [Header 1 ("hello-world",[],[]) [Str "Hello,",Space,Str "World!"]] 

Pembaca yang telah bekerja dengan Haskell setidaknya sedikit sudah dapat berasumsi bahwa Pandoc ditulis secara khusus dalam Haskell: output dari perintah ini adalah representasi struktur internal Pandoc sebagai string, dibuat dalam rupa bagaimana biasanya dilakukan di Haskell, misalnya, di perpustakaan standar.

Jadi, di sini Anda dapat melihat bahwa representasi internal adalah struktur rekursif, di setiap simpul internal yang ada daftar. Misalnya, di tingkat paling atas ada daftar satu elemen - header tingkat pertama dengan atribut "hello-world", [], []. Di dalam tajuk ini adalah daftar string "Halo,", spasi dan string "Dunia!".

Seperti yang Anda lihat, representasi internal tidak jauh berbeda dari HTML. Ini adalah pohon, di mana setiap simpul internal melaporkan beberapa informasi tentang pemformatan turunannya, dan dedaunan berisi isi dokumen yang sebenarnya.

Jika Anda turun ke tingkat implementasi tertentu, tipe data untuk seluruh dokumen didefinisikan seperti ini:

 data Pandoc = Pandoc Meta [Block] 

Di sini, Block adalah puncak internal yang disebutkan di atas, dan Meta adalah meta-informasi tentang dokumen, seperti judul, tanggal pembuatan, penulis - ini berbeda untuk format yang berbeda, dan Pandoc mencoba menyimpan informasi tersebut kapan pun memungkinkan saat mentransfer dari format ke format.

Hampir semua konstruktor dari tipe Blok - misalnya, Header atau Para (paragraf) - mengambil atribut dan daftar simpul dari level yang lebih rendah - Sebaris, sebagai aturan, sebagai argumen. Misalnya, Space atau Str adalah desainer dari tipe Inline, dan tag HTML juga dikonversi menjadi Inline khusus. Kami tidak melihat alasan apa pun untuk memberikan definisi lengkap tentang tipe-tipe ini, namun, kami perhatikan bahwa hal itu dapat dilihat di sini .

Menariknya, tipe Pandoc adalah monoid. Ini berarti ada semacam dokumen kosong, dan dokumen itu bisa ditumpuk di antara mereka sendiri. Ini nyaman digunakan saat menulis Pembaca - Anda dapat memecah dokumen menjadi beberapa bagian dengan logika sewenang-wenang, parsing masing-masing secara individu, dan kemudian meletakkan semuanya menjadi satu dokumen. Dalam hal ini, meta-informasi akan dikumpulkan dari semua bagian dokumen sekaligus.

Ketika mengkonversi, katakanlah, dari LaTeX ke HTML, pertama modul khusus bernama LaTeXReader mengubah dokumen input menjadi AST, kemudian modul lain yang disebut HTMLWriter mengubah AST ke HTML. Berkat arsitektur ini, Anda tidak perlu menulis jumlah konversi kuadrat - cukup menulis Reader dan Penulis untuk setiap format baru, dan semua pasangan konversi yang memungkinkan akan secara otomatis didukung.

Jelas bahwa arsitektur ini juga memiliki kelemahan, lama diprediksi oleh para ahli di bidang arsitektur perangkat lunak. Yang paling signifikan adalah biaya untuk membuat perubahan pada pohon sintaksis. Jika perubahannya cukup serius, Anda harus mengubah kode di semua Pembaca dan Penulis. Sebagai contoh, salah satu tantangan yang dihadapi pengembang Pandoc adalah untuk mendukung format tabel yang kompleks. Sekarang Pandoc hanya bisa di tabel paling sederhana, dengan tajuk, kolom, dan nilai di setiap sel. Katakanlah atribut colspan dalam HTML hanya akan diabaikan. Salah satu alasan untuk perilaku ini adalah kurangnya skema representasi tabel tunggal dalam semua atau setidaknya banyak format - karena itu, tidak jelas dalam bentuk apa tabel harus disimpan dalam representasi internal. Tetapi bahkan setelah memilih tampilan tertentu, akan perlu untuk mengubah sepenuhnya semua Pembaca dan Penulis yang mendukung bekerja dengan tabel.

Haskell dipilih tidak hanya dari kecintaan besar penulis pada pemrograman fungsional. Haskell dikenal karena kemampuan pengolah kata yang kuat. Salah satu contoh adalah parsec library - perpustakaan yang secara aktif menggunakan konsep pemrograman fungsional - monoids, monads, aplikator dan functors alternatif - untuk menulis parser sewenang-wenang. Kekuatan penuh Parsec dapat dilihat pada contoh HaskellWiki, yang mem-parsing parser penuh dari bahasa pemrograman imperatif sederhana. Tentu saja, Parsec juga aktif digunakan di Pandoc.

Singkatnya, monads digunakan untuk pengurutan berurutan ketika satu datang pertama dan kemudian yang lainnya. Misalnya, dalam contoh ini:

 whileParser :: Parser Stmt whileParser = whiteSpace >> statement 

Pertama, Anda perlu mempertimbangkan spasi, dan kemudian pernyataan - yang juga memiliki tipe Parser Stmt.

Fungsi alternatif digunakan untuk memutar kembali jika parse gagal. Sebagai contoh

 statement :: Parser Stmt statement = parens statement <|> sequenceOfStmt 

Berarti Anda harus mencoba membaca pernyataan dalam tanda kurung, atau secara berurutan mencoba membaca beberapa pernyataan.

Fungsional aplikatif terutama digunakan sebagai pintasan untuk monad. Misalnya, biarkan fungsi tok membaca semacam token (ini adalah fungsi sebenarnya dari LaTeXReader). Mari kita lihat kombinasi seperti itu

 const <$> tok <*> tok 

Dia akan membaca dua token berturut-turut dan mengembalikan yang pertama.

Haskell memiliki operator simbolik yang indah untuk semua kelas ini, yang membuat pemrograman Pembaca terlihat seperti seni ASCII. Cukup kagumi kode indah ini.

Tugas kami terkait dengan LaTeXReader. Tugas Vasily adalah untuk mendukung perintah \ mbox dan \ hbox, berguna saat menulis paket di LaTeX. Elizabeth bertanggung jawab atas dukungan tim epigraf, yang memungkinkan pelaksanaan epigraf dalam dokumen LaTeX.

Hatrace

Pada sistem operasi mirip UNIX, panggilan sistem ptrace sering diterapkan. Berguna dalam debugging dan simulasi lingkungan program, memungkinkan Anda untuk melacak panggilan sistem yang dibuat oleh program. Sebagai contoh, utilitas strace yang sangat berguna menggunakan ptrace di dalamnya.

Hatrace adalah perpustakaan yang menyediakan antarmuka untuk ptrace di Haskell. Faktanya adalah ptrace itu sendiri sangat canggih dan cukup sulit untuk menggunakannya secara langsung, terutama dari bahasa fungsional.

Hatrace saat startup berjalan seperti strace dan menerima argumen serupa. Perbedaannya dari strace adalah ia juga merupakan perpustakaan yang menyediakan antarmuka yang lebih sederhana dari sekadar ptrace.

Hatrace telah menangkap satu bug yang tidak menyenangkan di kompiler Haskell GHC - ketika terbunuh pada waktu yang salah, ia menghasilkan file objek yang salah dan tidak mengkompilasi ulang mereka ketika restart. Scripting pada panggilan sistem memungkinkan untuk mereproduksi kesalahan dalam satu kali proses, ketika pembunuhan acak mereproduksi kesalahan dalam waktu sekitar dua jam.

Kami menambahkan antarmuka system call ke perpustakaan - Elizabeth menambahkan brk, dan Vasily menambahkan mmap. Menurut hasil pekerjaan kami, kami dapat lebih mudah dan akurat menggunakan argumen panggilan sistem ini saat menggunakan perpustakaan.