ZuriHac: berlatih pemrograman fungsional

Pada bulan Juni tahun ini, di kota kecil Rapperswil di Swiss, sebuah acara bernama ZuriHac. Kali ini mempertemukan lebih dari lima ratus pecinta Haskell, dari pemula hingga pendiri bahasa tersebut. Meskipun pihak penyelenggara menyebut acara ini sebagai hackathon, namun ini bukanlah konferensi atau hackathon dalam pengertian klasik. Formatnya berbeda dari programmer tradisional. Kami beruntung mengetahui tentang ZuriHac, mengambil bagian di dalamnya, dan sekarang kami menganggap tugas kami untuk menceritakan tentang penemuan yang tidak biasa ini!

Tentang kami

Artikel ini disiapkan oleh dua mahasiswa tahun ke-3 program “Matematika Terapan dan Informatika” di Sekolah Tinggi Ekonomi Universitas Riset Nasional - St. Petersburg: Vasily Alferov dan Elizaveta Vasilenko. Ketertarikan kami berdua terhadap pemrograman fungsional dimulai dengan serangkaian kuliah oleh D. N. Moskvin di tahun ke-2 kuliah. Vasily saat ini berpartisipasi dalam program Google Summer of Code, di mana ia mengimplementasikan grafik aljabar di Haskell di bawah bimbingan tim proyek Ganggang. Elizaveta menerapkan keterampilan pemrograman fungsional yang diperoleh dalam tugas kursus yang ditujukan untuk implementasi algoritma anti-unifikasi dengan penerapan selanjutnya dalam teori tipe.

Format acara

Target audiensnya adalah pemilik proyek sumber terbuka, pemrogram yang ingin berpartisipasi dalam pengembangannya, peneliti pemrograman fungsional, dan orang-orang yang tertarik dengan Haskell. Tahun ini, para pengembang lebih dari lima puluh proyek open source Haskell dari seluruh dunia berkumpul di tempat tersebut - HSR Hochschule für Technik Rapperswil - untuk membicarakan produk mereka dan membuat orang-orang baru tertarik dengan pengembangannya.

Foto dari Twitter ZuriHac

Skemanya sangat sederhana: Anda perlu menulis beberapa proposal tentang proyek Anda terlebih dahulu dan mengirimkannya ke penyelenggara, yang akan memposting informasi tentang proyek Anda di halaman acara. Selain itu, pada hari pertama, penulis proyek memiliki waktu tiga puluh detik untuk menceritakan secara singkat dari panggung apa yang mereka lakukan dan apa yang perlu dilakukan. Kemudian pihak yang berkepentingan mencari penulisnya dan menanyakan secara detail tentang tugasnya.

Kami belum memiliki proyek terbuka sendiri, tapi kami sangat ingin berkontribusi pada proyek yang sudah ada, jadi kami mendaftar sebagai peserta tetap. Selama tiga hari, kami bekerja dengan dua kelompok pengembang. Ternyata studi bersama tentang kode dan komunikasi langsung membuat interaksi antara penulis proyek dan kontributor menjadi sangat produktif - di ZuriHac kami dapat memahami bidang-bidang yang baru bagi kami dan mampu membantu dua tim yang sangat berbeda, menyelesaikan satu tugas di masing-masing tim. dari proyek-proyek tersebut.

Selain latihan yang berharga, beberapa ceramah dan kelas master juga diberikan di ZuriHac. Kami terutama mengingat dua ceramah. Pada pembahasan pertama, Andrey Mokhov dari Universitas Newcastle berbicara tentang fungsi aplikatif selektif - kelas tipe yang harus menjadi perantara antara fungsi aplikatif dan monad. Dalam kuliah lainnya, salah satu pendiri Haskell, Simon Peyton Jones, berbicara tentang cara kerja inferensi tipe di kompiler GHC.

Ceramah oleh Simon Peyton Jones. Foto dari Twitter ZuriHac

Kelas master yang diadakan selama hackathon dibagi menjadi tiga kategori tergantung pada tingkat pelatihan peserta. Tugas yang ditawarkan kepada peserta yang mengikuti pengembangan proyek juga ditandai dengan tingkat kesulitannya. Komunitas pemrogram fungsional yang kecil namun ramah dengan senang hati menyambut pendatang baru ke dalam jajarannya. Namun, untuk memahami perkuliahan Andrey Mokhov dan Simon Peyton Jones, kursus pemrograman fungsional yang kami ambil di universitas sangat berguna.

Pendaftaran acara ini gratis untuk peserta reguler dan penulis proyek. Kami mengajukan permohonan partisipasi pada awal Juni, setelah itu kami dengan cepat dipindahkan dari daftar tunggu ke daftar peserta yang dikonfirmasi.

Dan sekarang kita akan berbicara tentang proyek-proyek yang pengembangannya kita ikuti.

Pandoc

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

Daftar format dokumen yang didukung oleh Pandoc. Ada juga grafik lengkap di situs ini, tetapi gambar ini tidak sesuai dengan artikel.

Tentu saja Pandoc tidak menyediakan konversi langsung untuk setiap pasangan format. Untuk mendukung berbagai macam transformasi, solusi arsitektur standar digunakan: pertama, seluruh dokumen diterjemahkan ke dalam representasi perantara internal khusus, dan kemudian dokumen dalam format berbeda dihasilkan dari representasi internal ini. Pengembang menyebut representasi internal "AST", yang merupakan singkatan dari Abstrak Syntax Tree, atau pohon sintaksis abstrak. Anda dapat melihat representasi perantara dengan sangat sederhana: yang perlu Anda lakukan hanyalah mengatur format keluaran ke "asli"

$ 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 dari contoh kecil ini bahwa Pandoc ditulis dalam Haskell: output dari perintah ini adalah representasi string dari struktur internal Pandoc, dibuat serupa dengan yang biasanya dilakukan di Haskell, misalnya di perpustakaan standar.

Jadi, di sini Anda dapat melihat bahwa representasi internal adalah struktur rekursif, di setiap node internal terdapat daftar. Misalnya, di tingkat atas terdapat daftar satu elemen - header tingkat pertama dengan atribut “hello-world”,[],[]. Tersembunyi di dalam header ini adalah daftar string “Halo”, diikuti dengan spasi dan string “Dunia!”.

Seperti yang Anda lihat, representasi internal tidak jauh berbeda dengan HTML. Ini adalah pohon di mana setiap node internal memberikan beberapa informasi tentang format turunannya, dan daunnya berisi konten sebenarnya dari dokumen tersebut.

Jika kita turun ke level implementasi, tipe data untuk seluruh dokumen didefinisikan seperti ini:

data Pandoc = Pandoc Meta [Block]

Di sini Blok tepatnya adalah simpul internal yang disebutkan di atas, dan Meta adalah metainformasi tentang dokumen, seperti judul, tanggal pembuatan, penulis - ini berbeda untuk format yang berbeda, dan Pandoc mencoba, jika mungkin, untuk menyimpan informasi tersebut ketika menerjemahkan dari format ke format format.

Hampir semua konstruktor tipe Blok - misalnya, Header atau Para (paragraf) - menggunakan atribut dan daftar simpul tingkat rendah sebagai argumen - Inline, sebagai aturan. Misalnya, Space atau Str adalah konstruktor bertipe Inline, dan tag HTML juga berubah menjadi Inline khususnya. Kami melihat tidak ada gunanya memberikan definisi lengkap tentang tipe-tipe ini, namun perhatikan bahwa definisi tersebut dapat ditemukan di sini di sini.

Menariknya, tipe Pandoc adalah monoid. Artinya ada semacam dokumen kosong, dan dokumen tersebut dapat ditumpuk menjadi satu. Ini nyaman digunakan saat menulis Pembaca - Anda dapat memecah dokumen menjadi beberapa bagian menggunakan logika arbitrer, menguraikan masing-masing bagian secara terpisah, dan kemudian menggabungkan semuanya menjadi satu dokumen. Dalam hal ini, metainformasi akan dikumpulkan dari seluruh bagian dokumen sekaligus.

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

Jelas bahwa arsitektur seperti itu juga memiliki kekurangan, yang telah 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. Misalnya, salah satu tantangan yang dihadapi pengembang Pandoc adalah mendukung format tabel yang kompleks. Sekarang Pandoc hanya bisa membuat tabel yang sangat sederhana, dengan header, kolom dan nilai di setiap sel. Misalnya, atribut colspan dalam HTML akan diabaikan begitu saja. Salah satu alasan perilaku ini adalah kurangnya skema terpadu untuk merepresentasikan tabel dalam semua atau setidaknya banyak format - oleh karena itu, tidak jelas dalam bentuk apa tabel harus disimpan dalam representasi internal. Namun bahkan setelah memilih tampilan tertentu, Anda harus benar-benar mengubah semua Pembaca dan Penulis yang mendukung bekerja dengan tabel.

Bahasa Haskell dipilih bukan hanya karena kecintaan penulisnya yang besar terhadap pemrograman fungsional. Haskell dikenal dengan kemampuan pemrosesan teksnya yang luas. Salah satu contohnya adalah perpustakaan Parsec adalah perpustakaan yang secara aktif menggunakan konsep pemrograman fungsional - monoid, monad, fungsi aplikatif dan alternatif - untuk menulis parser arbitrer. Kekuatan penuh Parsec dapat dilihat di contoh dari HaskellWiki, di mana parser lengkap dari bahasa pemrograman imperatif sederhana diurai. Tentu saja Parsec juga aktif digunakan di Pandoc.

Dijelaskan secara singkat, monad digunakan untuk penguraian berurutan, ketika satu hal didahulukan, lalu hal lainnya. Misalnya, dalam contoh ini:

whileParser :: Parser Stmt
whileParser = whiteSpace >> statement

Pertama, Anda perlu menghitung spasi, lalu pernyataan - yang juga bertipe Parser Stmt.

Fungsi alternatif digunakan untuk melakukan rollback jika penguraian gagal. Misalnya,

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

Ini berarti Anda perlu mencoba membaca pernyataan dalam tanda kurung, atau mencoba membaca beberapa pernyataan secara berurutan.

Fungsi aplikatif digunakan terutama sebagai jalan pintas untuk monad. Misalnya, biarkan fungsi tok membaca beberapa token (ini adalah fungsi nyata dari LaTeXReader). Mari kita lihat kombinasi ini

const <$> tok <*> tok

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

Untuk semua kelas ini, Haskell memiliki operator simbolik yang indah, yang membuat pemrograman Reader terlihat seperti seni ASCII. Kagumi saja kode yang luar biasa ini.

Tugas kami terkait dengan LaTeXReader. Tugas Vasily adalah mendukung perintah mbox dan hbox, berguna untuk menulis paket dalam LaTeX. Elizabeth bertanggung jawab untuk mendukung perintah epigraf, yang memungkinkan Anda membuat prasasti dalam dokumen LaTeX.

kebencian

Sistem operasi mirip UNIX sering mengimplementasikan panggilan sistem ptrace. Ini berguna dalam debugging dan simulasi lingkungan program, memungkinkan Anda melacak panggilan sistem yang dibuat oleh program. Misalnya, utilitas strace yang sangat berguna menggunakan ptrace secara internal.

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

Hatrace berjalan seperti strace saat startup dan menerima argumen serupa. Ini berbeda dari strace karena ia juga merupakan perpustakaan yang menyediakan antarmuka yang lebih sederhana dari sekedar ptrace.

Dengan bantuan hatrace, kami telah menemukan satu bug yang tidak menyenangkan di kompiler GHC Haskell - dimatikan pada saat yang salah, ia menghasilkan file objek yang salah dan tidak mengkompilasi ulangnya saat dimulai ulang. Pembuatan skrip dengan panggilan sistem memungkinkan untuk mereproduksi kesalahan secara andal dalam satu kali proses, sementara pembunuhan acak mereproduksi kesalahan dalam waktu sekitar dua jam.

Kami menambahkan antarmuka panggilan sistem ke perpustakaan - Elizaveta menambahkan brk, dan Vasily menambahkan mmap. Berdasarkan hasil pekerjaan kami, argumen panggilan sistem ini dapat digunakan dengan lebih sederhana dan akurat saat menggunakan perpustakaan.

Sumber: www.habr.com