Dalam catatan singkat ini, kita akan melihat bagaimana Anda dapat mengimplementasikan di Lisp seperti mekanisme perangkat lunak yang saat ini sangat populer sebagai aplikasi parsial dan fungsi kari. Dalam melakukannya, saya akan menggunakan implementasi Homelisp saya (ini adalah penerjemah Lisp murni dengan beberapa fitur tambahan).
Menggunakan aplikasi parsial di Common Lisp mungkin akan rumit (karena Anda perlu menggunakan funcall / apply untuk memanggil objek fungsi yang dihitung); di Skema seharusnya lebih mudah. Saya berencana untuk segera memposting versi baru HomeLisp, yang tidak memerlukan funcall / apply untuk memanggil objek fungsi yang dihitung. Dalam kasus di mana perilaku kode berbeda, saya akan menekankan ini.
Aplikasi parsial dan kari adalah operasi matematika yang ketat. Tapi kami akan mempertimbangkannya "dengan jari", tanpa menggunakan kalkulus lambda dan logika kombinatorial.
Aplikasi parsial dari fungsi f mendapatkan dari fungsi f fungsi baru f 'yang telah mengambil argumen yang diberikan dan siap untuk menerima sisanya. Untuk apa aplikasi parsial? Misalnya, agar nilai fungsional dapat dikembalikan dari suatu fungsi.
Mari pertimbangkan penerapan parsial dengan contoh sederhana. Misalkan fungsi f diberikan dengan rumus:
f (x, y, z) = x + y ** 2 + z ** 3
maka penerapan parsial fungsi ini dengan argumen x = 1 dan y = 2 harus menghasilkan fungsi:
f '(z) = 1 + 4 + z ** 3 = 5 + z ** 3
Di Haskell, sebagian aplikasi tidak membebani programmer:
Prelude> f x y z = x+y**2+z**3 --
f :: Floating a => a -> a -> a -> a
Prelude> f 1 2 3 -- ...
32.0 -- !
it :: Floating a => a
Prelude> f' = f 1 2 -- x=1 y=2 f'
f' :: Floating a => a -> a
Prelude> f' 3 -- f'
32.0 --
it :: Floating a => a
Namun, di Lisp, upaya seperti itu akan gagal:
(defun f (x y z) (+ x (* y y) (* z z z))) ;;
==> F
(f 1 2 3) ;;
==> 32 ;;
(f 1 2) ;; ...
PairLis:
: F
: (X Y Z)
: (1 2)
==> ERRSTATE
Tentu saja, Lisp memiliki mekanisme untuk membuat fungsi dengan sejumlah argumen (konstruksi & rest); Anda dapat membuat fungsi yang akan mengambil dua atau tiga (atau sepuluh) parameter:
(defun s (&rest x) ;; - x
(apply '+ x)) ;;
==> S
(s 1 2) ;;
==> 3
(s 1 2 3) ;;
==> 6
Namun penting untuk memahami perbedaannya: fungsi ini memproses semua parameter dan mengembalikan hasil penghitungan, sedangkan aplikasi parsial menghasilkan fungsi baru yang "siap melanjutkan penghitungan".
Mari kita lihat bagaimana kita dapat mengimplementasikan mekanisme aplikasi fungsi parsial di Lisp. Dan itu akan membantu kita dalam hal ini ... ya, aparatus fungsi anonim (lambda). Beberapa programmer berpikir bahwa fungsi anonim diperlukan hanya untuk menyimpan nama (kata mereka, tempat mereka di stream-map-filter-reduce untuk melakukan tindakan singkat pada elemen urutan). Faktanya, fungsi anonim mampu melakukan lebih banyak lagi, yang sekarang akan kita lihat.
Mari kita mulai dengan melihat bagaimana suatu fungsi dapat mengembalikan fungsi lain sebagai hasilnya. Di Lisp, ini sangat sederhana:
(defun func-gen (x)
(lambda (y) (+ x (* y y))))
==> FUNC-GEN
(func-gen 5)
==> (CLOSURE (Y) ((+ X (* Y Y))) ((X 5)))
Seperti yang Anda lihat, fungsi mengembalikan penutupan di mana nilai variabel bebas x tetap (sama dengan 5). Hasil dari suatu fungsi bisa disebut sebagai fungsi. Untuk melakukan ini, di Common Lisp dan HomeLisp (dengan revisi kernel <= 13.53), Anda harus menggunakan funcall:
(funcall (func-gen 5) 7)
==> 54
Sekarang jelas bagaimana kita bisa melanjutkan jika kita ingin mengambil fungsi f dari n argumen dan satu nilai x, dan sebagai hasilnya mendapatkan fungsi dari (n-1) argumen. Mari kita tunjukkan daftar parameter formal fungsi kita dengan plist. Maka yang harus Anda lakukan adalah membuat ekspresi lambda seperti ini:
(lambda (-plist) (apply f (cons x -plist)))
Idenya sangat sederhana: kita membangun ekspresi lambda, yang di dalamnya kita cukup memanggil fungsi asli pada daftar parameter, di mana head diganti dengan nilai x.
Ini berarti bahwa untuk aplikasi parsial dari fungsi, Anda perlu membuat ekspresi lambda berdasarkan fungsi ini, yang akan memiliki satu argumen lebih sedikit, dan argumen yang ditentukan selama aplikasi parsial akan "diperhitungkan" dalam panggilan internal fungsi kita di badan ekspresi lambda.
Bagaimana cara menerapkan ini? Mudah ... HomeLisp memiliki fungsi getd yang menyediakan akses ke fungsi yang menentukan ekspresi atau makro:
(defun g (x y z) (+ x (* x y) (* x y z)))
==> G
(getd 'g)
==> (EXPR (X Y Z) (+ X (* X Y) (* X Y Z)))
Seperti yang Anda lihat, getd mengembalikan ekspresi yang menentukan dari fungsi tersebut, di mana "sebagai ganti" lambda ada atom EXPR khusus. Kita dapat mengambil daftar parameter dari fungsi kita (elemen kedua dari hasil) dan membuat ekspresi lambda, parameter yang akan menjadi ekor dari daftar parameter asli, dan di badan ekspresi lambda kita akan memanggil fungsi asli dengan daftar parameter lengkap.
(defun part-apply (f a)
(let* ((plist (cadr (getd f))) ;;
(rlist (cdr plist)) ;;
(clist (cons a rlist))) ;; a
`(lambda ,rlist (apply (quote ,f) (list ,@clist)))))
Dari kode di atas, mudah untuk dipahami bahwa plist adalah daftar asli dari fungsi f yang ingin kita terapkan sebagian. rlist adalah daftar asli tanpa elemen pertama, dan clist adalah daftar lengkap parameter, dengan elemen pertama diganti dengan x. Khusus untuk fungsi g di atas, plist = (xyz), rlist = (yz), dan clist = (ayz). Sekarang mari kita periksa bagaimana aplikasi parsial bekerja:
(part-apply 'g 111)
==> (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 111 Y Z)))
Anda dapat memastikan bahwa ini persis seperti yang direncanakan: part-apply mengembalikan fungsi baru, dengan jumlah argumen yang lebih sedikit. Jika fungsi baru ini dipanggil dengan parameter y dan z, hasilnya sama persis dengan memanggil fungsi asli g dengan tiga argumen: 111 y dan z:
(g 111 1 2)
==> 444 ;;
(funcall (part-apply 'g 111) 1 2) ;; "--"
==> 444
((part-apply 'g 111) 1 2) ;; "-"
==> 444
Di bawah saya (untuk singkatnya) tidak akan menentukan funcall. Di inti HomeLisp berikutnya, skema untuk menghitung fungsi akan diubah - sintaks "skema" akan tersedia.
Mari melangkah lebih jauh. Sekarang akan ada dorongan alami untuk menerapkan kembali hasil permohonan ulang. Ini ternyata cukup sederhana - bagaimanapun juga, hasil dari aplikasi parsial adalah ekspresi lambda, dan terstruktur hampir identik dengan hasil yang dikembalikan oleh getd. Daftar parameter ekspresi lambda adalah item kedua dalam daftar. Semua pertimbangan ini memungkinkan kami membangun solusi akhir untuk masalah ini:
(defun part-apply (f a)
(cond ((and (atom f) (member 'expr (proplist f))) ;; *** ***
(let* ((plist (cadr (getd f))) ;;
(rlist (cdr plist)) ;;
(clist (cons a rlist))) ;; a
`(lambda ,rlist (apply (quote ,f) (list ,@clist)))))
((eq 'lambda (car f)) ;; *** - ***
(let* ((plist (cadr f)) ;;
(rlist (cdr plist)) ;;
(clist (cons x rlist))) ;; x
`(lambda ,rlist (apply (quote ,f) (list ,@clist)))))
(t (raiseerror "part-apply: "))))
Di sini analisis parameter pertama ditambahkan: jika itu adalah atom, maka itu harus "mewakili" fungsi (jenis EXPR); jika parameter pertama bukan atom "valid" atau ekspresi lambda, maka kondisi kesalahan akan dimunculkan. Kode tersebut, tentu saja, dapat lebih dipersingkat, dua cabang yang hampir identik dibiarkan agar lebih jelas. Sekarang mari kita lihat kemampuan fungsi ini:
(part-apply (part-apply 'g 1) 2) ;;
==> (LAMBDA (Z) (APPLY (QUOTE (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 1 Y Z)))) (LIST 2 Z)))
((part-apply (part-apply 'g 1) 2) 3) ;;
==> 9
(part-apply (part-apply (part-apply 'g 111) 1) 2) ;;
==> (LAMBDA NIL (APPLY (QUOTE (LAMBDA (Z) (APPLY (QUOTE (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 111 Y Z)))) (LIST 1 Z)))) (LIST 2)))
((part-apply (part-apply (part-apply 'g 111) 1) 2)) ;; ...
==> 444
(setq u (part-apply 'g 111)) ;;
==> (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 111 Y Z)))
;; U
(part-apply u 1) ;;
==> (LAMBDA (Z) (APPLY (QUOTE (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 111 Y Z)))) (LIST 1 Z)))
((part-apply u 1) 2) ;;
==> 444
Sekarang mari kita membuat kari. Fungsi curried, yang menerima jumlah argumen yang tidak mencukupi, mengembalikan fungsi yang bisa menangani sisanya. Tujuan utama kari adalah untuk aplikasi parsial. Kami pergi dari ujung yang lain: sekarang mari kita lihat bagaimana kari dapat diimplementasikan jika ada aplikasi parsial.
Misalkan fungsi g dari beberapa argumen diberikan. Kami akan membuat versi kari dengan nama yang berbeda! Inti dari konstruksinya adalah sebagai berikut: function! G akan mengambil sejumlah argumen yang tidak terbatas. Setelah panggilan, itu harus memeriksa jumlah argumen yang diteruskan. Jika angka ini sama dengan jumlah argumen dari fungsi asli g, maka dari harus diteruskan ke input g. Jika ada lebih banyak argumen daripada yang bisa diterima g, maka kondisi kesalahan harus dimunculkan. Tetapi jika jumlah argumen kurang dari fungsi g, maka ... ya, ya - Anda perlu melakukan aplikasi parsial berurutan. Kembalikan hasil dari aplikasi ini.
Dalam kasus ini, akan lebih mudah menggunakan makro. Kode dengan komentar ada di bawah ini:
(defmacro curry (f)
(let* ((parmlist (cadr (getd f))) ;; f
(body (cddr (getd f))) ;; f
(lp (length parmlist)) ;; f
(cf (implode (cons '! (explode f))))) ;;
`(defun ,cf (&rest x)
(let ((lx (length x))) ;;
(cond ((= lx ,lp) ;;
(let ((e `(lambda ,parmlist ,@body)))
(apply e x)))
((> lx ,lp) ;;
(raiseerror "curry: "))
(t (let ((tmp nil)) ;;
(iter (for a in x) ;;
(setq tmp (if (null tmp) (part-apply (quote ,f) a) (part-apply tmp a))))
tmp)))))))
Perlu mengomentari pembangunan nama fungsi baru di sini. Untuk melakukan ini, gunakan fungsi ledakan HomeLisp, yang membangun daftar simbol penyusunnya dari atom, dan meledak, yang memampatkan simbol daftar menjadi satu, membuat atom baru.
Sekarang mari kita periksa makro kita beraksi:
(curry g) ;; g
==> !G ;;
(!g 1 2 3) ;;
==> 9 ;; g
(!g 1 2) ;; -
==> (LAMBDA (Z) (APPLY (QUOTE (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 1 Y Z)))) (LIST 2 Z)))
;; :
((!g 1 2) 3) ;;
==> 9
((!g 1) 2 3) ;;
==> 9
(!g 1 2 3 4) ;;
curry:
==> ERRSTATE
Pembuatan kari dilakukan tanpa kontrol tambahan. Dan kami belum menerapkan ekspresi lambda kari. Jika mau, Anda dapat melakukan semua ini ...
Ini adalah bagaimana Anda dapat menerapkan aplikasi fungsi parsial dan kari di Lisp tanpa banyak usaha. Lisp adalah bahasa yang luar biasa!
Terima kasih atas perhatian Anda.