Hari ini kami sedang menyelesaikan serangkaian artikel tentang pemrograman fungsional. Ternyata 11 bagian. Saya percaya ini adalah prestasi. Pada artikel ini, kami menerapkan tumpukan kalkulator sederhana (juga dikenal sebagai "notasi Polandia terbalik"). Implementasinya hampir sepenuhnya dibangun di atas fungsi, dengan hanya satu jenis khusus, dan umumnya tanpa perbandingan dengan sampel, jadi ini adalah tempat pengujian yang sangat baik untuk konsep-konsep yang tercakup dalam seri kami.
Saya ingin mengucapkan terima kasih kepada @kleidemos secara terpisah. Dialah yang bertindak sebagai penerjemah utama dan manajer dari seluruh rangkaian artikel. Terima kasih
Jika Anda tidak terbiasa dengan kalkulator seperti itu, maka berfungsi sebagai berikut: angka didorong ke tumpukan, dan operasi, seperti penambahan dan perkalian, pilih angka dari bagian atas tumpukan, dan kemudian kembalikan hasil operasi.
Skema perhitungan sederhana pada stack:
Sebelum merancang sistem seperti itu, Anda harus mempertimbangkan bagaimana sistem itu akan digunakan. Mengikuti sintaks yang mirip, kami akan memberi setiap tindakan label yang sesuai sehingga pada contoh di atas Anda dapat menulis sesuatu seperti:
EMPTY ONE THREE ADD TWO MUL SHOW
Mungkin mustahil untuk mendapatkan sintaksis ini, tapi mari kita coba sedekat mungkin dengan ini.
Stack tipe data
Pertama, Anda perlu menentukan struktur data untuk stack. Untuk kesederhanaan, Anda dapat menggunakan daftar angka floating point.
type Stack = float list
Tetapi lebih baik untuk membungkusnya dalam satu jenis case union untuk membuat jenis lebih visual, seperti ini:
type Stack = StackContents of float list
Mengapa lebih baik melakukan hal itu, Anda dapat membaca di sini .
Sekarang buat tumpukan baru menggunakan StackContents sebagai konstruktor:
let newStack = StackContents [1.0;2.0;3.0]
Untuk mengekstrak konten dari Stack yang ada, gunakan pencocokan pola StackContents :
let (StackContents contents) = newStack // "contents" // float list = [1.0; 2.0; 3.0]
Fungsi dorong
Selanjutnya, kita perlu cara untuk meletakkan angka di tumpukan ini. Untuk melakukan ini, tambahkan saja nilai baru ke atas daftar menggunakan " :: ".
Contoh fungsi:
let push x aStack = let (StackContents contents) = aStack let newContents = x::contents StackContents newContents
Fitur ini memiliki sejumlah fitur yang layak dibahas.
Pertama, Anda harus memperhatikan fakta bahwa struktur list tidak dapat diubah, yang berarti bahwa fungsi tersebut harus mengambil tumpukan yang ada dan mengembalikan yang baru. Ini bukan hanya perubahan ke tumpukan yang ada. Faktanya, semua fungsi dalam contoh ini akan memiliki format yang serupa:
Input: Stack - Output: Stack
Kedua, mengapa parameter dilakukan dalam urutan itu? Mengapa tumpukan harus pertama atau terakhir? Pada bagian tentang merancang fungsi dengan aplikasi parsial, dikatakan bahwa parameter yang paling sering berubah adalah yang terakhir. Segera mungkin untuk memverifikasi bahwa rekomendasi ini sedang diikuti.
Akhirnya, fungsi dapat dibuat lebih ringkas dengan mencocokkan dengan pola dalam parameter fungsi itu sendiri, alih-alih let dalam fungsi tubuh.
Versi yang ditulis ulang:
let push x (StackContents contents) = StackContents (x::contents)
Jauh lebih baik!
Omong-omong, lihat tanda tangannya yang anggun:
val push : float -> Stack -> Stack
Seperti yang disebutkan sebelumnya , tanda tangan banyak memberi tahu kita.
Dalam hal ini, saya bisa menebak apa fungsi ini, hanya dengan tanda tangannya, bahkan tanpa mengetahui bahwa itu disebut "push".
Ini adalah alasan lain mengapa ide mengetik jenis eksplisit adalah ide yang bagus. Jika tumpukan itu hanya daftar angka floating point, maka fungsinya tidak akan begitu mendokumentasikan diri.
Dengan satu atau lain cara, periksa:
let emptyStack = StackContents [] let stackWith1 = push 1.0 emptyStack let stackWith2 = push 2.0 stackWith1
Bagus sekali!
Tumpuk superskrip atas menggunakan push
Dengan fungsi sederhana ini, Anda dapat dengan mudah menentukan operasi yang mendorong nomor tertentu pada tumpukan.
let ONE stack = push 1.0 stack let TWO stack = push 2.0 stack
Tapi tunggu dulu! Anda melihat bahwa parameter stack disebutkan di kedua sisi ekspresi? Bahkan, tidak perlu menyebutkannya dua kali. Sebagai gantinya, Anda dapat menghilangkan parameter dan menulis fungsi dengan aplikasi parsial:
let ONE = push 1.0 let TWO = push 2.0 let THREE = push 3.0 let FOUR = push 4.0 let FIVE = push 5.0
Sekarang jelas bahwa jika fungsi push memiliki urutan parameter yang berbeda, stack harus disebutkan dua kali.
Anda juga perlu mendefinisikan fungsi yang membuat tumpukan kosong:
let EMPTY = StackContents []
Periksa fungsi yang diterima:
let stackWith1 = ONE EMPTY let stackWith2 = TWO stackWith1 let stackWith3 = THREE stackWith2
Apakah tumpukan menengah ini mengganggu? Apakah mungkin untuk menyingkirkan mereka? Tentu saja! Perhatikan bahwa fungsi SATU, DUA, dan TIGA memiliki tanda tangan yang sama:
Stack -> Stack
Jadi, mereka saling terhubung dengan sempurna! Output dari satu fungsi dapat dimasukkan sebagai berikut:
let result123 = EMPTY |> ONE |> TWO |> THREE let result312 = EMPTY |> THREE |> ONE |> TWO
Muncul keluar dari tumpukan
Dengan tambahan pada stack yang ditemukan, tetapi bagaimana dengan fungsi pop ?
Saat mengambil dari tumpukan, jelas perlu mengembalikan bagian atas tumpukan, tetapi apakah hanya itu?
Dalam gaya berorientasi objek, jawabannya adalah ya . Tetapi dalam kasus OOP, tumpukan akan diubah di belakang layar, sehingga item teratas akan dihapus.
Namun, dalam gaya fungsional, tumpukan tidak berubah. Hanya ada satu cara untuk menghapus elemen atas - buat tumpukan baru tanpa elemen ini. Agar pemanggil memiliki akses ke tumpukan yang dikurangi baru, itu harus dikembalikan bersama dengan elemen atas.
Dengan kata lain, fungsi pop harus mengembalikan dua nilai, elemen atas dan tumpukan baru. Cara paling sederhana untuk melakukan ini di F # adalah dengan menggunakan tuple.
Implementasi:
/// /// let pop (StackContents contents) = match contents with | top::rest -> let newStack = StackContents rest (top,newStack)
Fungsi yang dihasilkan juga sangat sederhana.
Seperti sebelumnya, contents diekstraksi langsung dari parameter.
Kemudian, isi contents diperiksa menggunakan match..with ekspresi.
Kemudian elemen atas dipisahkan dari sisa daftar, tumpukan baru dibuat berdasarkan elemen yang tersisa, dan akhirnya semua ini dikembalikan sebagai pasangan tuple.
Coba jalankan kode ini dan lihat apa yang terjadi. Anda akan mendapatkan kesalahan kompilasi!
Compiler telah mendeteksi sebuah case yang belum dikerjakan - apa yang terjadi jika stack kosong?
Anda harus memutuskan bagaimana cara menanganinya.
Saya biasanya lebih suka menggunakan keadaan khusus untuk kesalahan, tetapi dalam kasus khusus ini, saya lebih suka untuk melemparkan pengecualian. Versi pop diperbaiki dengan penanganan case kosong:
let pop (StackContents contents) = match contents with | top::rest -> let newStack = StackContents rest (top,newStack) | [] -> failwith "Stack underflow"
Periksa:
let initialStack = EMPTY |> ONE |> TWO let popped1, poppedStack = pop initialStack let popped2, poppedStack2 = pop poppedStack
dan tes pengecualian:
let _ = pop EMPTY
Fungsi aritmatika
Sekarang setelah penambahan dan penghapusan sudah ada, Anda dapat mulai bekerja dengan fungsi "tambah" dan "multiply":
let ADD stack = let x,s = pop stack // let y,s2 = pop s // let result = x + y // push result s2 // let MUL stack = let x,s = pop stack // let y,s2 = pop s // let result = x * y // push result s2 //
Pengujian Online:
let add1and2 = EMPTY |> ONE |> TWO |> ADD let add2and3 = EMPTY |> TWO |> THREE |> ADD let mult2and3 = EMPTY |> TWO |> THREE |> MUL
Itu berhasil!
Waktu refactoring ...
Jelas, sejumlah besar kode digandakan dalam dua fungsi ini. Bagaimana kita memperbaikinya?
Kedua fungsi mengekstrak dua nilai dari stack, menerapkan fungsi biner tertentu untuknya, dan kemudian mendorong hasilnya kembali ke stack. Anda dapat menampilkan kode umum ke fungsi biner, yang mengambil fungsi matematika dengan dua parameter:
let binary mathFn stack = // let y,stack' = pop stack // let x,stack'' = pop stack' // let z = mathFn xy // push z stack''
Perhatikan bahwa dalam implementasi ini, versi berbeda dari objek "sama" ditandai dengan jumlah tanda kutip yang berbeda. Ini karena sufiks numerik dapat dengan mudah menyebabkan kebingungan.
Pertanyaan: mengapa parameter memiliki urutan yang persis seperti ini, alih-alih mathFn datang setelah stack ?
Sekarang Anda memiliki fungsi binary , lebih mudah untuk mendefinisikan ADD dan fungsi lainnya:
Upaya pertama untuk mengimplementasikan ADD menggunakan binary :
let ADD aStack = binary (fun xy -> x + y) aStack
Tetapi Anda dapat menyingkirkan lambda, karena itu mewakili definisi yang tepat dari fungsi + :
let ADD aStack = binary (+) aStack
Sekali lagi, sebagian aplikasi dapat digunakan untuk menyembunyikan parameter stack. Definisi akhir:
let ADD = binary (+)
Definisi fungsi matematika lainnya:
let SUB = binary (-) let MUL = binary (*) let DIV = binary (../)
Cobalah online:
let div2by3 = EMPTY |> THREE|> TWO |> DIV let sub2from5 = EMPTY |> TWO |> FIVE |> SUB let add1and2thenSub3 = EMPTY |> ONE |> TWO |> ADD |> THREE |> SUB
Demikian pula, Anda dapat membuat fungsi bantu untuk operasi unary
let unary f stack = let x,stack' = pop stack push (fx) stack'
Dan tentukan beberapa fungsi unary:
let NEG = unary (fun x -> -x) let SQUARE = unary (fun x -> x * x)
Mode interaktif:
let neg3 = EMPTY |> THREE|> NEG let square2 = EMPTY |> TWO |> SQUARE
Menyatukan semuanya | Menyatukan semuanya
Dalam persyaratan awal disebutkan bahwa kami ingin dapat menunjukkan hasilnya, jadi ada baiknya mendefinisikan fungsi SHOW.
let SHOW stack = let x,_ = pop stack printfn "The answer is %f" x stack //
Harap dicatat bahwa dalam kasus ini, versi baru tumpukan yang diterima melalui pop diabaikan. Hasil akhirnya adalah tumpukan asli, seolah-olah itu tidak pernah berubah.
Akhirnya, Anda dapat menulis contoh berikut dari persyaratan aslinya
EMPTY |> ONE |> THREE |> ADD |> TWO |> MUL |> SHOW
Pindah
Ini menyenangkan, tetapi apa lagi yang bisa Anda lakukan?
Anda dapat menetapkan beberapa fungsi tambahan:
/// let DUP stack = // let x,_ = pop stack // push x stack /// let SWAP stack = let x,s = pop stack let y,s' = pop s push y (push x s') /// let START = EMPTY
Dengan menggunakan fungsi-fungsi tambahan ini, Anda dapat menulis beberapa contoh elegan:
START |> ONE |> TWO |> SHOW START |> ONE |> TWO |> ADD |> SHOW |> THREE |> ADD |> SHOW START |> THREE |> DUP |> DUP |> MUL |> MUL // 27 START |> ONE |> TWO |> ADD |> SHOW // 3 |> THREE |> MUL |> SHOW // 9 |> TWO |> SWAP |> DIV |> SHOW // 9 div 2 = 4.5
Menggunakan komposisi alih-alih pipelining
Tapi itu belum semuanya. Bahkan, ada cara lain yang menarik untuk mewakili fungsi-fungsi ini.
Seperti disebutkan sebelumnya, mereka semua memiliki tanda tangan yang sama:
Stack -> Stack
Karena input dan output adalah dari jenis yang sama, fungsi-fungsi ini juga dapat digabungkan menggunakan operator komposisi >> , dan tidak hanya melalui operator pipeline.
Beberapa contoh:
// let ONE_TWO_ADD = ONE >> TWO >> ADD START |> ONE_TWO_ADD |> SHOW // let SQUARE = DUP >> MUL START |> TWO |> SQUARE |> SHOW // let CUBE = DUP >> DUP >> MUL >> MUL START |> THREE |> CUBE |> SHOW // let SUM_NUMBERS_UPTO = DUP // n >> ONE >> ADD // n+1 >> MUL // n(n+1) >> TWO >> SWAP >> DIV // n(n+1) / 2 START |> THREE |> SQUARE |> SUM_NUMBERS_UPTO |> SHOW
Dalam masing-masing contoh ini, fungsi baru didefinisikan menggunakan komposisi fungsi lainnya. Ini adalah contoh yang baik dari pendekatan "kombinasi" untuk membangun fungsionalitas.
Konveyor vs. Komposisi
Kami melihat dua cara berbeda untuk menggunakan model kami; menggunakan conveyor dan komposisi. Tapi apa bedanya? Dan mengapa seseorang harus lebih disukai daripada yang lain?
Perbedaannya adalah bahwa pipa, dalam arti tertentu, merupakan operasi "transformasi waktu nyata". Pada saat menggunakan pipa, operasi dilakukan segera, melalui transfer tumpukan tertentu.
Di sisi lain, komposisi adalah sesuatu seperti "rencana" yang ingin kita terapkan, membangun fungsi dari serangkaian komponen tanpa aplikasi langsung.
Misalnya, Anda dapat membuat "rencana" untuk menghitung kuadrat angka melalui kombinasi operasi kecil:
let COMPOSED_SQUARE = DUP >> MUL
Saya tidak bisa memberikan yang setara berdasarkan jaringan pipa.
let PIPED_SQUARE = DUP |> MUL
Ini akan menghasilkan kesalahan kompilasi. Saya perlu beberapa contoh stack khusus agar ekspresi berfungsi:
let stackWith2 = EMPTY |> TWO let twoSquared = stackWith2 |> DUP |> MUL
Dan bahkan dalam kasus ini, saya bisa mendapatkan jawaban hanya untuk input khusus ini, dan bukan rencana perhitungan umum berdasarkan input apa pun, seperti dalam contoh dengan COMPOSED_SQUARE .
Cara lain untuk membuat "rencana" adalah dengan secara eksplisit meneruskan lambda ke fungsi yang lebih primitif:
let LAMBDA_SQUARE = unary (fun x -> x * x)
Ini adalah cara yang lebih eksplisit (dan kemungkinan besar lebih cepat), tetapi semua keuntungan dan kejelasan dari pendekatan komposisi hilang.
Secara umum, jika mungkin, Anda harus berusaha untuk pendekatan komposisi!
Kode lengkap
Kode lengkap untuk semua contoh di atas:
// ============================================== // // ============================================== type Stack = StackContents of float list // ============================================== // // ============================================== /// let push x (StackContents contents) = StackContents (x::contents) /// /// let pop (StackContents contents) = match contents with | top::rest -> let newStack = StackContents rest (top,newStack) | [] -> failwith "Stack underflow" // ============================================== // () // ============================================== // // // let binary mathFn stack = let y,stack' = pop stack let x,stack'' = pop stack' let z = mathFn xy push z stack'' // // // let unary f stack = let x,stack' = pop stack push (fx) stack' // ============================================== // () // ============================================== /// let SHOW stack = let x,_ = pop stack printfn "The answer is %f" x stack // /// let DUP stack = let x,s = pop stack push x (push xs) /// let SWAP stack = let x,s = pop stack let y,s' = pop s push y (push x s') /// let DROP stack = let _,s = pop stack // s // // ============================================== // , // ============================================== // // ------------------------------- let EMPTY = StackContents [] let START = EMPTY // // ------------------------------- let ONE = push 1.0 let TWO = push 2.0 let THREE = push 3.0 let FOUR = push 4.0 let FIVE = push 5.0 // // ------------------------------- let ADD = binary (+) let SUB = binary (-) let MUL = binary (*) let DIV = binary (../) let NEG = unary (fun x -> -x) // ============================================== // , // ============================================== let SQUARE = DUP >> MUL let CUBE = DUP >> DUP >> MUL >> MUL let SUM_NUMBERS_UPTO = DUP // n >> ONE >> ADD // n+1 >> MUL // n(n+1) >> TWO >> SWAP >> DIV // n(n+1) / 2
Kesimpulan
Kami memiliki kalkulator berbasis tumpukan sederhana. Kami melihat bagaimana, dimulai dengan beberapa operasi primitif ( push , pop , binary , unary ) dan lainnya, Anda dapat membangun DSL penuh, mudah diimplementasikan dan digunakan.
Seperti yang Anda tebak, contoh ini cukup banyak didasarkan pada bahasa Forth. Saya sangat merekomendasikan buku gratis "Thinking Forth" , yang tidak hanya menceritakan tentang bahasa Forth, tetapi juga tentang metode lain ( bukan berorientasi objek!) Untuk menguraikan tugas yang sama-sama berlaku untuk pemrograman fungsional secara umum.
Saya mendapat ide untuk artikel ini dari blog Ashley Feniello yang cantik. Jika Anda ingin terjun lebih dalam ke emulasi bahasa berbasis stack berdasarkan F #, mulailah dengan itu. Selamat bersenang-senang!
Sumber Daya Tambahan
Ada banyak tutorial untuk F #, termasuk materi untuk mereka yang datang dengan pengalaman C # atau Java. Tautan berikut mungkin berguna saat Anda masuk lebih dalam ke F #:
Beberapa cara lain untuk mulai belajar F # juga dijelaskan.
Akhirnya, komunitas F # sangat ramah pemula. Ada obrolan yang sangat aktif di Slack, didukung oleh F # Software Foundation, dengan kamar pemula yang dapat Anda gabung dengan bebas . Kami sangat menyarankan Anda melakukan ini!
Jangan lupa untuk mengunjungi situs komunitas berbahasa Rusia F # ! Jika Anda memiliki pertanyaan tentang belajar bahasa, dengan senang hati kami akan membahasnya di ruang obrolan:
Tentang penulis terjemahan
Diterjemahkan oleh @kleidemos
Perubahan terjemahan dan editorial dilakukan oleh upaya komunitas pengembang F # berbahasa Rusia . Kami juga berterima kasih kepada @schvepsss dan @shwars karena telah menyiapkan artikel ini untuk dipublikasikan.