Berapa banyak cara yang bisa saya tulis faktorial untuk Skema?

Bahasa-bahasa jahat mengklaim bahwa bahasa pemrograman fungsional adalah “bahasa penulisan faktorial”. Ini paling sering didefinisikan sebagai bahasa Haskell, tetapi kita akan mulai dengan bahasa fungsional yang sangat mempengaruhi Haskell dan subset alat pemrograman fungsional untuk banyak bahasa lainnya - Skema. Setidaknya map dan for-each , filter dan reduce , serta apply dan eval datang ke bahasa pemrograman favorit kami, jika bukan dari Skema, lalu dari sana.

Pertimbangkan beberapa cara yang mungkin untuk menulis perhitungan faktorial. Pada saat yang sama, Anda mendapatkan semacam ode ke bahasa pemrograman Skema. Saya pikir bahasa yang indah ini layak untuk itu.

Saya mendapat 10 opsi untuk menulis definisi fungsi, yang dapat direduksi menjadi 3 metode utama perhitungan: proses komputasi rekursif linier tradisional, iterasi, pembuatan urutan angka, diikuti oleh perkalian konvolusi. Saya mengusulkan untuk mempertimbangkan opsi-opsi ini secara lebih rinci. Sepanjang jalan, kita akan mempertimbangkan: pengoptimalan rekursi ekor, fungsi dan metaprogramming tingkat tinggi, perhitungan yang ditunda, daftar tanpa akhir, memoisasi, cara untuk membuat variabel statis dalam Skema, dan makro kebersihan.

Untuk percobaan, kami menggunakan Skema dialek lama yang baik R5RS dan prinsip populer seni rupa "sarana minimum - tayangan maksimum".

Semua contoh Skema disiapkan dalam DrRacket 6.2 dalam mode R5RS. Pengukuran Runtime dilakukan di Guile 2.0 di lingkungan OpenSUSE Leap 15 OS.

Untuk memulai, Anda dapat mengambil definisi faktorial rekursif dan cukup menulis ulang rumus pada Skema:

 (define (factorial-classic n) (if (zero? n) 1 (* n (factorial-classic (- n 1))))) 

Hasilnya adalah definisi fungsi (dalam hal Skema - prosedur, meskipun sebenarnya itu adalah fungsi) untuk menghitung faktorial, yang dapat dilihat dalam panduan pemrograman yang tak terhitung jumlahnya, dimulai dengan buku abadi H. Abelson dan D. Sassman “Struktur dan interpretasi program komputer” .

Anda dapat membaca dan memahami kode ini seperti ini: faktorial $$$n$ada disana $$$1$jika $$$n = 0$jika tidak - $$$n \ cdot (n-1)!$. Dengan demikian, kode ini sesuai dengan definisi rekursif faktorial, yang diadopsi dalam matematika. Satu-satunya hal yang kami tidak memeriksa afiliasi $$$n$angka non-negatif.

Menjadi rekursif, kode di atas berisi batasan yang jelas pada nilai $$$n$: data panggilan rekursif akan menumpuk di tumpukan hingga $$$n$tidak akan mencapai 0. Hal ini dapat menyebabkan tumpukan meluap $$$n$.

Bagaimana saya bisa menghapus batasan ini? Penting untuk mengoptimalkan rekursi ekor: menulis ulang kode sehingga panggilan rekursif menjadi buntut (yaitu, yang terakhir dalam prosedur). Ini akan memungkinkan juru bahasa Skema untuk melakukan optimasi - ganti perhitungan rekursif dengan yang iteratif.

Jika Anda menggunakan rekomendasi dari penulis buku di atas, Anda bisa mendapatkan yang berikut:

 (define (factorial-classic-tco n) (define (iteration product counter) (if (> counter n) product (iteration (* product counter) (+ counter 1)))) (iteration 1 1)) 

Kode ini adalah contoh umum, dan dimulai dengan buku "Struktur dan interpretasi program komputer", di situ optimalisasi rekursi ekor biasanya dijelaskan.

Itu klasik. Tetapi Skema adalah fleksibilitas itu sendiri, mungkinkah menulis hal yang sama dengan cara yang secara fundamental berbeda? Dan lebih disukai lebih pendek? Misalnya sesuai dengan entri $$$n! = 1 \ cdot 2 \ cdot 3 \ cdot ~ \ cdots ~ \ cdot n$membentuk urutan dari $$$1$sebelumnya $$$n$(atau dari $$$n$sebelumnya $$$1$) dan kemudian runtuh dengan multiplikasi? Untungnya, dalam Skema ini cukup sederhana berkat prosedur apply bawaan, yang menerapkan prosedur dengan jumlah argumen sewenang-wenang ke daftar:

 (define (iota n) (define (iteration sequence i) (if (> in) sequence (iteration (cons i sequence) (+ i 1)))) (iteration '() 1)) (define (factorial-fold n) (apply * (iota n))) 

Skema terkenal karena kemudahannya untuk perhitungan simbolik karena "kesatuan kode dan data" (seperti yang kadang-kadang dikatakan tentang bahasa keluarga Lisp). Kami menggunakan fitur ini: kami membentuk ekspresi untuk menghitung faktorial suatu angka $$$n$dan kemudian hitung:

 (define (factorial-eval n) (define expression `(* ,@(iota n))) (eval expression (interaction-environment))) 

Simbol "back single quote" berarti quasiquotation. Tanpa kuasi-kutipan, memperoleh ekspresi untuk perhitungan lebih lanjut dapat diperoleh dengan menggunakan kode (cons '* (iota n)) . Kutipan tunggal (kutip, kutip) berarti bahwa * harus diganti ke dalam ekspresi persis seperti nama (simbol), dan bukan nilai yang sesuai (di sini - prosedur). Jadi, dengan $$$n = 3$kita dapatkan (* 3 2 1) . Daftar ini adalah ekspresi dalam Skema. Nilainya dapat dilakukan dalam lingkungan yang sesuai, terbaik dari semuanya - dalam lingkungan (interaction-environment) mengandung prosedur bawaan dan prosedur yang ditentukan oleh kami dalam program. Sebenarnya, inilah yang kami lakukan dalam tubuh factorial-eval .

Skema mendukung komputasi yang ditangguhkan. Haskell, yang sangat dipengaruhi oleh Skema, menggunakan model perhitungan yang malas, yaitu tidak menghitung nilai ekspresi sampai hasil perhitungan ini diklaim. Hal ini memungkinkan program untuk memiliki struktur data khusus seperti daftar tanpa akhir. Jika hanya bagian yang diperlukan untuk perhitungan lebih lanjut diambil dari mereka, program tidak akan berjalan dalam siklus:

 ghci> take 4 [1 ..] [1,2,3,4] 

Ekspresi [1 ..] menghasilkan daftar bilangan bulat tak terbatas. Ekspresi take 4 mendapatkan 4 elemen pertama dari daftar ini. Karena item daftar berikutnya tetap tidak diklaim, mereka tidak dihitung.

Di Haskell mendapatkan $$$n!$dari daftar tanpa akhir Anda dapat menulis seperti ini:

 factorials :: [Integer] factorials = next 0 1 where next n fact = let n' = n + 1 in fact : next n' (fact * n') factorial :: Integer -> Integer factorial n = factorials !! fromIntegral n 

 ghci> take 7 $ factorials [1,1,2,6,24,120,720] ghci> factorial 6 720 

Menggunakan beberapa bentuk delay Skema / force mari kita coba melakukan sesuatu yang serupa. Kata kunci delay menciptakan janji untuk mengevaluasi nilai ekspresi. Kata kunci force menginstruksikan untuk melakukan perhitungan ini, nilai yang dihasilkan dihitung dan disimpan. Setelah akses berulang, perhitungan baru tidak dilakukan, tetapi nilai yang dihitung sebelumnya dikembalikan.

Dalam bahasa keluarga Lisp, daftar dibuat dari pasangan. Untuk membangun daftar yang tidak terbatas, kami memperkenalkan jenis "pasangan malas" - pasangan di mana elemen pertama adalah nilai yang dihitung, dan yang kedua adalah janji untuk menghitung nilai. Untuk melakukan ini, kita perlu melengkapi "trinitas suci" bahasa keluarga Lisp ( cons , car , cdr ) dengan versi malas mereka:

 (define-syntax lazy-cons (syntax-rules () ((_ first second) (cons first (delay second))))) (define lazy-car car) (define (lazy-cdr lazy-pair) (force (cdr lazy-pair))) 

Konstruktor pasangan lazy-cons diimplementasikan sebagai makro. Hal ini dilakukan untuk menghindari penghitungan nilai elemen kedua dari pasangan saat membuatnya.

Idenya adalah untuk membuat daftar nilai yang tak ada habisnya, dan kemudian mengambil apa yang Anda butuhkan. Untuk melakukan ini, tentukan versi malas dari prosedur untuk memperoleh elemen dengan indeks:

 (define (lazy-list-ref lazy-list index) (if (zero? index) (lazy-car lazy-list) (lazy-list-ref (lazy-cdr lazy-list) (- index 1)))) (define (generate-factorials) (define (next nn!) (define n+1 (+ n 1)) (lazy-cons n! (next n+1 (* n! n+1)))) (next 0 1)) 

Di sini n! dan n+1 adalah nama-nama variabel. Dalam Skema, dibandingkan dengan bahasa lain, ada sangat sedikit karakter yang tidak dapat digunakan dalam pengidentifikasi.

Perhatikan bahwa generator daftar faktor tak terhingga tidak mengandung jalan keluar dari rekursi. Namun, itu tidak akan diulang, karena ketika dipanggil, hanya kepala daftar akan dihitung, sementara ekor akan diwakili oleh janji untuk menghitung nilai.

Sekarang Anda bisa mendefinisikan $$$n!$bagaimana cara mendapatkannya $$$n$Unsur ke-5 daftar faktorial:

 (define lazy-factorials (generate-factorials)) (define (factorial-lazy n) (lazy-list-ref lazy-factorials n)) 

Itu bekerja. Pada saat yang sama, jika faktorial angka yang berbeda dihitung dalam satu sesi juru bahasa, maka perhitungan akan terjadi lebih cepat daripada dalam versi yang ketat, karena beberapa nilai dalam daftar malas sudah akan dihitung.

Ngomong-ngomong, kode pada Skema sangat dekat dengan yang ada di Haskell. Jadi, terima pernyataannya !! kira-kira sesuai dengan prosedur lazy-list-ref konstruktor lazy-list-ref : sesuai dengan lazy-cons . Sejalan dengan itu, karena Haskell, meskipun mengaku model perhitungan malas, namun, tidak seperti delay / force dalam Skema, ia tidak ingat nilai yang dihitung.

Omong-omong, untuk meningkatkan produktivitas, Anda dapat menerapkan menghafal nilai yang sudah dihitung - memoisasi. Kami akan menyimpan nilai yang dihitung dalam daftar asosiatif, di mana kuncinya adalah angka, dan nilai adalah faktorialnya. Saat dipanggil, kita akan melihat daftar untuk nilai yang sudah dihitung. Jika nilainya ada dalam daftar, kami akan mengembalikan nilai yang disimpan ini. Jika nilainya tidak ada dalam daftar, kami akan menghitungnya, memasukkannya ke dalam daftar, dan baru mengembalikannya. Untuk memastikan bahwa daftar ini selalu dengan fungsi yang dipanggil, dan bukan di lingkungan global, kami menempatkannya dalam variabel statis:

 (define factorial-memoized (let ((memo '())) (lambda (n) (let ((memoized (assq n memo))) (if memoized (cadr memoized) (if (zero? n) 1 (let ((computed (* n (factorial-memoized (- n 1))))) (set! memo (cons (list n computed) memo)) computed))))))) 

 (define proc (let ((static-var initial-value)) (lambda args ...))) 

 (define count (let ((n 0)) (lambda () (set! n (+ n 1)) n))) 

 (define count ((lambda (n) (lambda () (set! n (+ n 1)) n)) 0)) 

Implementasi ini juga menjanjikan keuntungan kinerja dengan berulang kali menghitung faktor-faktor dari berbagai angka dalam satu sesi juru bahasa.

Tentu saja, pengoptimalan rekursi ekor juga dimungkinkan di sini:

 (define factorial-memoized-tco (let ((memo '())) (lambda (n) (define (iteration product counter) (cond ((> counter n) product) (else (set! memo (cons (list counter product) memo)) (iteration (* product counter) (+ counter 1))))) (iteration 1 1)))) 

"Mengapa tarian ini dengan rebana?", Pembaca mungkin berkata. Dalam bahasa pemrograman imperatif, hal yang sama ditulis sederhana - melalui loop, ia bekerja dengan cepat dan tanpa biaya memori yang tidak perlu. Skema memiliki subset untuk pemrograman imperatif, ia juga memiliki sarana untuk mengatur loop - bentuk khusus do . Prosedur untuk menghitung faktorial, ditulis dengan bantuannya, mungkin terlihat seperti ini:

 (define (factorial-do n) (define product 1) (do ((i 1 (+ i 1))) ((> in) product) (set! product (* product i)))) 

Konstruk do cukup serbaguna, dan itulah sebabnya itu tidak terlalu mudah dibaca. Bukankah lebih baik mengatur siklus Anda sendiri dengan gaya imperatif? Makro akan membantu dengan ini:

 (define-syntax for (syntax-rules () ((_ (variable init test step) . body) (let loop ((variable init)) (if test (begin (begin . body) (loop step))))))) 

Berkat optimalisasi rekursi ekor oleh penerjemah, kami mendapatkan loop yang biasa kami gunakan dalam bahasa pemrograman imperatif. Dengan mengoptimalkan rekursi ekor, tumpukan tidak akan tumbuh.

Menentukan faktorial yang digunakan for :

 (define (factorial-for n) (define product 1) (for (i 1 (<= in) (+ i 1)) (set! product (* product i))) product) 

 for → _ i → variable 1 → init (<= in) → test (+ i 1) → step (set! product (* product i)) → body 

 (define (factorial-for n) (define product 1) (let loop ((i 1)) ;   (if (<= in) ;  (begin (begin (set! product (* product i))) ;  (loop (+ i 1))))) ;  for product) 

Ada opsi lain yang terlihat mirip dengan keharusan for loop - dengan prosedur bawaan for-each :

 (define (factorial-for-each n) (define product 1) (for-each (lambda (i) (set! product (* product i))) (iota n)) product) 

Bahasa Skema yang hebat dan kuat! Bagaimana dengan kinerja?

Kami akan menggunakan GNU Guile untuk mengukur kinerja - dalam lingkungan ini Anda dapat mengukur waktu yang diperlukan untuk mengevaluasi ekspresi secara sederhana.

Tipu daya bekerja sebagai berikut: mengkompilasi kode sumber program ke dalam bytecode, yang kemudian dieksekusi oleh mesin virtual. Ini hanya salah satu implementasi dan salah satu dari beberapa cara yang mungkin untuk menjalankan program Skema, ada yang lain: Racket (menggunakan kompilasi JIT), Skema Ayam (menggunakan interpretasi atau kompilasi “jujur” ke dalam subset C), dll. Jelas, baik keterbatasan maupun kinerja program di lingkungan ini mungkin sedikit berbeda.

Kami akan melakukan pengukuran pada nilai tertentu $$$n$. Apa yang seharusnya $$$n$? Jadi dengan yang terhebat $$$n$akan dapat "mengatasi" dengan opsi yang diusulkan. Dengan pengaturan default Guile 2.0, pada PC dengan Intel Core i5 dan 4 GB RAM, saya mendapatkan yang berikut ini:

Dari sini, tes kinerja dilakukan di $$$n = 8 \, $ 00$. Hasilnya disajikan dalam tabel di bawah ini, di mana $$$t_ {run}$- waktu memimpin $$$t_ {GC}$- pengumpul sampah menjalankan waktu dalam hitungan detik.
Untuk semua prosedur kecuali malas dan memoised, nilai terkecil dari runtime dan waktu yang sesuai dari pengumpul sampah diperoleh, diperoleh dari hasil tiga dimulai pada $$$n = 8 \, $ 00$.
Untuk prosedur memoized dan lazy, waktu pelaksanaan panggilan pertama ditunjukkan, kemudian yang lebih kecil dari tiga panggilan.

Kami memiliki 4 opsi yang dapat bekerja dengan besar $$$n$. Di $$$n = 100 \, $ 00$mereka memiliki perhitungan berikut dan waktu pengumpulan sampah:

Anda bisa melihatnya dengan tidak terlalu besar $$$n$yang tercepat dan, pada saat yang sama, yang terpendek adalah yang pertama. Pilihan yang sama paling konsisten dengan definisi matematis faktorial. Opsi optimisasi rekursi ekor tidak kalah dengan performa. Kedua opsi ini secara idiomatis direkomendasikan oleh penulis bahasa. Kesimpulannya sebagian besar jelas: kecuali ditentukan lain, pendekatan, yang "khas" untuk bahasa, lebih disukai, setidaknya untuk implementasi pertama dari suatu algoritma atau metode.

Pada saat yang sama, bahasa Skema memungkinkan kami untuk menulis banyak opsi untuk mengimplementasikan perhitungan faktorial menggunakan seperangkat primitif yang sangat terbatas ("sarana minimum - tayangan maksimum"). Oleh karena itu, meskipun usianya sudah tua dan tidak terlalu luas, bahasa ini masih dapat direkomendasikan untuk pemrograman penelitian: tampaknya Anda dapat menerapkan apa pun di dalamnya dengan cara apa pun (dan dengan cara apa pun ) yang nyaman .