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.