Paul Graham menggambarkan LISP sebagai titik konvergensi untuk semua bahasa pemrograman. Pengamatannya adalah seiring dengan semakin matangnya bahasa, rata-rata bahasa terus menurun menuju LISP. Oleh karena itu memahami LISP adalah memahami model dasar pemrograman modern.
Yang lain memuji LISP sebagai kebutuhan untuk menjadi programmer yang lebih baik. Eric Raymond lebih jauh mengatakan bahwa memahami LISP adalah “pengalaman pencerahan yang mendalam.”
Untuk mencari pemahaman ini, saya pergi ke sumbernya. Makalah asli John McCarthy “Fungsi Rekursif Ekspresi Simbolik dan Perhitungannya dengan Mesin” yang meletakkan dasar bagi LISP.
Ini adalah makalah eksplorasi yang padat yang ditulis oleh seorang jenius untuk ilmuwan komputer awal. Bukan dokumentasi yang mudah dicerna yang dimaksudkan untuk memandu orang lain dalam memahami LISP. Saya bersusah payah membaca setiap kalimat sebelum menemukan artikel Paul Graham The Roots of LISP. Kejelasannya membantu membimbing saya menuju pemahaman yang sulit dipahami.
Namun baru setelah saya menulis artikel ini saya memahami sepenuhnya bahasa tersebut dan kekuatannya. Saya meninggalkan langkah saya di sini untuk siapa saja yang telah menempuh jalan yang sama dan masih kesulitan untuk memahaminya.
Sesuai dengan Paul Graham, saya mengimplementasikan versi LISP ini di Arc. Anda dapat menemukan kode lengkapnya di sini.
Daftar ekspresi
Awalnya, John McCarthy telah mendefinisikan ekspresi simbolik (ekspresi S) dan ekspresi meta (ekspresi M). Ekspresi S berisi daftar simbol, sedangkan ekspresi M untuk menunjukkan fungsi.
; S-expression ((ab . c) . d . nil) ; M-expression eq[x; x] ; returns t
Namun, komputer yang mereka gunakan untuk pertama kali mengimplementasikan LISP tidak memiliki tanda kurung siku, jadi semuanya ditulis dalam notasi ekspresi S. Titik-titik dihilangkan dan nil
yang mengakhiri daftar diasumsikan.
Jadi ekspresi M di atas menjadi
(eq x x) ; returns t
yang menjadi sintaks standar untuk LISP, menjadikan bahasa tersebut seragam secara sintaksis.
Fungsi dasar
Ada sangat sedikit fungsi dasar yang diperlukan untuk menjadikan LISP bahasa yang lengkap. Banyak kerumitan, seperti alokasi memori dan pengumpulan sampah, ditangani oleh kompiler.
Pengenalan singkat tentang sintaks LISP sangat membantu karena beberapa aspek tidak intuitif. Khususnya, kutipan dan evaluasi luar dalam.
Kutipan diperlukan untuk LISP karena tidak ada pemisahan data dan kode. Urutan karakter dapat diartikan sebagai variabel atau nilai tergantung pada konteksnya. Mengutip karakter menyelesaikan masalah ini dengan memaksakan interpretasi nilai secara literal.
Berbekal pemahaman dasar ini, Anda siap untuk 5 fungsi dasar yang diperlukan untuk LISP.
atom
Memeriksa apakah suatu elemen merupakan simbol tunggal.
(atom 'x) ; returns t (atom '(a b)) ; returns nil
eq
Memeriksa apakah dua simbol atom sama. Di Arc, ini ditulis sebagai is
.
(eq 'x 'x) ; returns t (eq 'x 'y) ; returns nil (eq '(a b) '(a b)) ; (a b) is a list and cannot be evaluated by eq ; returns nil
mobil
Singkatan dari isi register alamat. Ini mengembalikan item pertama dalam daftar, selama itu bukan atomik.
(car '(x a)) ; returns x (car '((x a) y)) ; returns (x a)
cdr
Singkatan dari isi register penurunan. Ia mengembalikan semuanya setelah item pertama dalam daftar.
(cdr '(x a)) ; returns a (cdr '((x a) y)) ; returns y (cdr '((x a) (y b))) ; returns (y b)
kontra
Digunakan untuk membuat daftar dari atom atau daftar lainnya.
(cons 'x 'a) ; returns (x . a) ; lists should typically end in nil ; so it is better to write (cons x (cons a nil)) ; which returns (x . a . nil) ; and can be written as (x a) (cons '(x a) 'y) ; returns ((x a) . y) (cons '(x a) '(y b)) ; returns ((x a) y b)
Fungsi dasar
Fungsi-fungsi ini merupakan inti dari “fungsi universal” yang merupakan tujuan akhir dari implementasi ini.
Jika Anda kesulitan mengikuti sintaksisnya, saya sarankan membaca tutorial Arc Paul Graham terlebih dahulu.
_batal
Mengevaluasi apakah ekspresi kosong.
(def _null (x) (is x nil)) (_null nil) ; returns t (_null '(x a)) ; returns nil
_Dan
Mengevaluasi apakah kedua kondisi tersebut benar. Di Arc, t
mewakili benar, dan nil
mewakili salah.
(def _and (x y) (if (is x t) (is y t) t nil)) (_and 'x 'y) ; returns t (_and 'x nil) ; returns nil
_bukan
Mengevaluasi apakah kondisinya nil
.
(def _not (x) (if (is x nil) t)) (_not nil) ; returns t (_not 'x) ; returns nil
_caar, _cadr, _caddr, _cadar, dan _caddar
Ini adalah singkatan dari kombinasi car
dan cdr
. Hal ini sering terjadi sehingga singkatannya membuat kode Anda KERING.
(def _caar (x) (car (car x))) (def _cadr (x) (car (cdr x))) (def _cadar (x) (car (cdr (car x)))) (def _caddr (x) (car (cdr (cdr x)))) (def _caddar (x) (car (cdr (cdr (car x))))) (_cadr '(a b c d)) ; returns b (_caddr '(a b c d)) ; returns c (_cadar '((a b c d) (e f g))) ; returns b (_caddar '((a b c d) (e f g))) ; returns c
_menambahkan
Memungkinkan Anda untuk bergabung dengan daftar.
(def _append (x y) (if (_null x) y (cons (car x) (_append (cdr x) y)))) (_append '(a b) '(c d)) ; returns (a b c d)
_daftar
Ini menjaga integritas daftar yang Anda berikan sebagai argumen dan menghilangkan kebutuhan akan cons
tambahan saat menggabungkan dua atom.
(def _list (x y) (cons x (cons y nil))) (_list 'a 'b) ; returns (a b) (_list '(a b) '(c d)) ; returns ((a b) (c d))
_pasangan
Menggabungkan dua daftar yang membuat pasangan berdasarkan posisi masing-masing elemen.
(def _pair (x y) (if (_and (_null x) (_null y)) nil (_and (_not (atom x)) (_not (atom y))) (cons (_list (car x) (car y)) (_pair (cdr x) (cdr y))))) (_pair '(x y z) '(a b c)) ; returns ((x a) (y b) (z c))
_rekan
Mendapatkan nilai dari pasangan kunci-nilai, dengan argumen pertama adalah kunci dan argumen kedua adalah daftar pasangan.
(def _assoc (x y) (if (is (caar y) x) (_cadar y) (_assoc x (cdr y)))) (_assoc 'y '((x a) (y b))) ; returns b (_assoc 'x '((w (a b)) (x (c d)) (y (e f)))) ; returns (c d)
Fungsi universal
Kekuatan sebenarnya dari LISP adalah kemampuannya untuk mengevaluasi dirinya sendiri dari beberapa elemen dasar. Seperti yang dilakukan John McCarthy, kami akan mendefinisikan _eval
yang dapat mengevaluasi LISP di LISP.
Ini adalah aspek bahasa yang paling mengejutkan dan kuat. Dengan 5 primitif dan 12 fungsi, Anda memiliki blok penyusun untuk membangun seorang interpreter.
(def _eval (e a) (if (atom e) (_assoc e a) (atom (car e)) (if (is (car e) 'quote) (_cadr e) (is (car e) 'atom) (atom (_eval (_cadr e) a)) (is (car e) 'eq) (is (_eval (_cadr e) a) (_eval (_caddr e) a)) (is (car e) 'car) (car (_eval (_cadr e) a)) (is (car e) 'cdr) (cdr (_eval (_cadr e) a)) (is (car e) 'cons) (cons (_eval (_cadr e) a) (_eval (_caddr e) a)) (is (car e) 'cond) (_evcon (cdr e) a) (_eval (cons (_assoc (car e) a) (cdr e)) a)) (is (caar e) 'label) (_eval (cons (_caddar e) (cdr e)) (cons (_list (_cadar e) (car e)) a)) (is (caar e) 'lambda) (_eval (_caddar e) (_append (_pair (_cadar e) (_evlis (cdr e) a)) a)))) (def _evcon (c a) (if (_eval (_caar c) a) (_eval (_cadar c) a) (_evcon (cdr c) a))) (def _evlis (m a) (if (_null m) nil (cons (_eval (car m) a) (_evlis (cdr m) a))))
Saat menggunakan _eval
, sintaksis ekspresi yang terkandung akan spesifik untuk penerjemah. Kami tidak lagi menulis dalam Arc, tetapi dalam bahasa yang benar-benar baru. Bentuk primitif LISP.
Bahkan jika Anda telah mengikuti, ada banyak hal yang perlu diuraikan di sini, jadi mari kita melewatinya.
Menafsirkan fungsi dasar
_eval
mengambil e
sebagai ekspresi yang akan dievaluasi dan a
sebagai daftar pasangan yang akan direferensikan oleh e
.
Jika e
bersifat atomik _assoc
dipanggil untuk mengembalikan nilai yang cocok dengan kunci e
di a
.
(_eval 'x '((x a) (y b))) ; returns a (_eval 'y '((x a) (y b))) ; returns b
Dalam kasus quote
simbol yang mengikuti quote
dikembalikan secara harfiah.
(_eval '(quote x) nil) ; nil is needed because _eval requires two arguments ; returns x (_eval '(quote (x a)) nil) ; returns (x a)
Dengan fungsi dasar lainnya, e
berbentuk (function key)
, dimana key
digunakan untuk mendapatkan nilai dari a
yang akan dievaluasi oleh function
.
Penggunaan _eval
berikut ini setara dengan (atom 'y)
yang lebih sederhana tetapi merupakan inti untuk memahami fungsi _eval
. Perhatikan bagaimana x
digunakan untuk mereferensikan nilai pada parameter kedua, a
.
(_eval '(atom x) '((x y))) ; returns t (_eval '(atom x) '((x (a b)))) ; returns nil
Untuk setiap fungsi dasar kecuali quote
ada panggilan _eval
rekursif yang dilakukan hingga mencapai _assoc
atau quote
.
Inilah langkah-langkah yang dilakukan _eval
untuk mengevaluasi atom
.
(_eval '(atom x) '((x y))) ; (atom (_eval (_cadr e) a)) ; (atom (_eval x ((x y)))) ; (atom (_assoc x ((x y)))) ; (atom y) ; returns t
car
dan cdr
memiliki struktur yang sangat mirip dengan atom
karena hanya satu ekspresi yang harus dievaluasi.
(_eval '(car x) '((x (a b c)))) ; returns a (_eval '(cdr x) '((x (a b c)))) ; returns (b c)
cons
dan eq
memiliki dua ekspresi yang perlu dievaluasi. Oleh karena itu, a
harus berisi dua pasang.
(_eval '(eq x y) '((x a) (y a))) ; returns t (_eval '(cons x y) '((x a) (y b))) ; returns (a . b)
cond
menggunakan fungsi baru, _evcon
yang mengambil daftar pasangan dengan format (condition expression)
. Ketika kondisi sebenarnya ditemukan, ekspresi tersebut dievaluasi.
(def _evcon (c a) (if (_eval (_caar c) a) (_eval (_cadar c) a) (_evcon (cdr c) a))) (_evcon '(((atom c1) a1) ((atom c2) a2) ((atom c3) a3)) '((c1 (a b)) (a1 not_atom) (c2 (c d)) (a2 still_not_atom) (c3 e) (a3 is_atom))) ; returns is_atom
Berikut adalah ekspresi yang sama menggunakan _eval
.
(_eval '(cond ((atom c1) a1) ((atom c2) a2) ((atom c3) a3)) '((c1 (a b)) (a1 not_atom) (c2 (c d)) (a2 still_not_atom) (c3 e) (a3 is_atom))) ; returns is_atom
Menafsirkan fungsi label
dan lambda
Jika e
bersifat atomik tetapi bukan merupakan fungsi dasar, maka harus berupa fungsi label
atau lambda
yang ditentukan oleh pengguna.
Ekspresi lambda
mengambil format (lambda (param) (expression) arg)
di mana arg
akan diteruskan ke expression
hingga param
.
(_eval '((lambda (param)
(cond ((atom param) (quote is_atom))
((quote t) (quote not_atom))))
arg)
'((arg (a b))))
; returns not_atom
Perhatikan bahwa (quote t)
digunakan di sini sebagai kondisi else
eksplisit. Arc menangani kasus ini dengan baik, tetapi karena kita terikat pada aturan penerjemah, kita harus menggunakan sintaksis ini.
Selama evaluasi, ekspresi lambda
di atas menjadi
(_eval '(cond ((atom param) (quote is_atom))
((quote t) (quote not_atom)))
'((param (a b)) (arg (a b))))
Perhatikan bagaimana argumen diperluas hingga memuat pasangan untuk param
. Ini memanfaatkan fungsi tambahan _evlis
yang secara rekursif membuat daftar pasangan dari arg
untuk setiap param
di lambda
. Hal ini memungkinkan lambda
untuk menangani daftar parameter apa pun.
((lambda (
p1...
pn)
e)
a1...
an)
adalah definisi formal .
label
memungkinkan fungsi dipanggil berdasarkan namanya, yang bisa dibilang merupakan fitur terpenting dari bahasa pemrograman apa pun.
Di sini, McCarthy mendefinisikan ff
sebagai fungsi untuk mengembalikan atom pertama dalam daftar. Itu menggunakan rekursi berlabel.
(_eval '((label ff (lambda (x)
(cond ((atom x) x)
((quote t) (ff (car x))))))
y)
'((y ((a b) c))))
; returns a
Ketika _eval
menemukan label
, fungsi tersebut akan disimpan di a
untuk digunakan nanti. Ini juga akan mulai mengevaluasi fungsi lambda
yang ditentukan oleh label
. Selama evaluasi, ekspresi di atas menjadi
(_eval '((lambda (x)
(cond ((atom x) x)
((quote t) (ff (car x)))))
y)
'((ff (label ff (lambda (x)
(cond ((atom x) x)
((quote t) (ff (car x)))))))
(y ((a b) c))))
Evaluasi penuh, seperti yang dikatakan McCarthy, adalah “suatu aktivitas yang lebih cocok untuk komputer elektronik daripada manusia.” Saya setuju dan tidak akan mencantumkan setiap langkah evaluasi.
Menyederhanakan _eval
Menggunakan _eval
dalam bentuk mentahnya agak bertele-tele, jadi McCarthy mendefinisikan _apply
sebagai pembungkus _eval
yang membantu membuat ekspresi lebih pendek dan mudah dipahami.
Ini akan mengambil parameter untuk _eval
dan membungkusnya seperti (quote (param))
. Ini juga menerapkan argumen secara langsung ke fungsi tersebut.
(def _appq (m) (if (_null m) nil (cons (_list 'quote (car m)) (_appq (cdr m)))))
(def _apply (f args) (_eval (cons f (_appq args)) nil))
Dengan menggunakan fungsi ini, fungsi ff
dapat ditulis sebagai
(_apply '(label ff (lambda (x)
(cond ((atom x) x)
((quote t) (ff (car x))))))
'(a b))
yang memanggil _eval
sebagai
(_eval '((label ff (lambda (x)
(cond ((atom x) x)
((quote t) (ff (car x))))))
(quote a) (quote b))
'nil)
_apply
dapat digunakan untuk apa pun yang ingin Anda tulis menggunakan _eval
. Namun ada gunanya memahami _eval
terlebih dahulu sebelum menambahkan lapisan abstraksi ini.
Kesimpulan
Kemampuan untuk mendefinisikan bahasa baru, dan memantau keadaan internalnya menjadikan LISP bahasa yang sangat baik untuk eksplorasi dan eksperimen.
Hilang sudah keajaiban kompilasi dan executable. Anda dapat melihat sendiri setiap langkah evaluasinya. Hal ini membuat latihan tersandung pada sintaksis kuno menjadi memuaskan.
Saya tidak melihat diri saya menggunakan LISP dalam produksi. Namun, saya akan terus menggunakannya sebagai alat untuk memperluas pemahaman saya tentang pemrograman tingkat rendah.
Langkah selanjutnya bagi saya adalah memahami cara mengimplementasikan kompiler yang akan mengubahnya menjadi kode mesin. Saya berencana membaca Struktur dan Interpretasi Program Komputer untuk melakukannya.
Selain itu, saya ingin memodernisasi penerjemah ini. Seperti yang ditulis Paul Graham, “Bahasa yang dia [John McCarthy] tulis pada tahun 1960 banyak yang hilang. Tidak ada efek samping, tidak ada eksekusi berurutan, tidak ada angka praktis, dan cakupan dinamis.” Namun hal ini bisa diatasi.
Paul Graham mengisyaratkan artikel Steele dan Sussman, “The Art of the Interpreter” tanpa menjelaskan secara spesifik. Mungkin saya akan membahasnya di artikel lain.
Menggali sejarah pemrograman, Anda akan menemukan pengaruh LISP di mana-mana. Latihan menyesuaikan diri dengan sintaksisnya merupakan upaya yang layak dilakukan, tetapi mengembangkan pemahaman yang sebenarnya akan membuka jendela ke dalam cara kerja semua bahasa. Itulah tujuan memahami LISP.
Awalnya diterbitkan di https://joshbradley.me pada tanggal 4 April 2020.