ทำความเข้าใจกับพลังของ LISP

Paul Graham อธิบายว่า LISP เป็นจุดบรรจบกันของภาษาการเขียนโปรแกรมทั้งหมด ข้อสังเกตของเขาคือเมื่อภาษาเติบโต ภาษาโดยเฉลี่ยยังคงเลื่อนไปทาง LISP ต่อไป ดังนั้นการทำความเข้าใจ LISP คือการเข้าใจโมเดลพื้นฐานของการเขียนโปรแกรมสมัยใหม่

คนอื่นๆ โน้มน้าว LISP ว่าจำเป็นต่อการเป็นโปรแกรมเมอร์ที่ดีขึ้น เอริค เรย์มอนด์กล่าวไปไกลถึงขนาดที่กล่าวว่าการเข้าใจ LISP นั้นเป็น “ประสบการณ์การรู้แจ้งอันลึกซึ้ง”

เพื่อค้นหาความเข้าใจนี้ ฉันไปที่แหล่งที่มา บทความต้นฉบับของ John McCarthy เรื่อง "ฟังก์ชันแบบเรียกซ้ำของนิพจน์สัญลักษณ์และการคำนวณด้วยเครื่องจักร" ที่วางรากฐานสำหรับ LISP

เป็นรายงานเชิงสำรวจที่มีความหนาแน่นสูงซึ่งเขียนโดยอัจฉริยะสำหรับนักวิทยาศาสตร์คอมพิวเตอร์ยุคแรกๆ ไม่ใช่เอกสารประกอบที่เข้าใจง่ายซึ่งมีวัตถุประสงค์เพื่อเป็นแนวทางให้ผู้อื่นเข้าใจ LISP ฉันพยายามอ่านแต่ละประโยคก่อนที่จะสะดุดกับบทความเรื่อง The Roots of LISP ของ Paul Graham ความชัดเจนของเขาช่วยนำทางฉันไปสู่ความเข้าใจที่เข้าใจยากนั้น

แต่จนกระทั่งฉันเขียนบทความนี้ ฉันจึงเข้าใจภาษาและพลังของมันอย่างถ่องแท้ ฉันขอฝากไว้ที่นี่เพื่อใครก็ตามที่เดินไปตามเส้นทางที่คล้ายกันและยังคงพยายามทำความเข้าใจ

ตามความจริงของ Paul Graham ฉันจึงนำ LISP เวอร์ชันนี้ไปใช้ใน "Arc" คุณสามารถค้นหารหัสเต็มได้ ที่นี่

รายการนิพจน์

เดิมที John McCarthy ได้กำหนดนิพจน์สัญลักษณ์ (S-expressions) และนิพจน์เมตา (M-expressions) S-expressions จะต้องมีรายการสัญลักษณ์ ในขณะที่ M-expressions จะต้องแสดงถึงฟังก์ชัน

; S-expression
((ab . c) . d . nil)
; M-expression
eq[x; x]
; returns t

อย่างไรก็ตาม คอมพิวเตอร์ที่พวกเขาใช้ LISP ครั้งแรกไม่มีวงเล็บเหลี่ยม ดังนั้นทุกอย่างจึงเขียนในรูปแบบ S-expression ละเว้นจุดและถือว่า nil ที่ยุติรายการ

ดังนั้น M-expression ข้างต้นจึงกลายเป็น

(eq x x)
; returns t

ซึ่งกลายเป็นไวยากรณ์มาตรฐานสำหรับ LISP ทำให้ภาษามีความเหมือนกันทางวากยสัมพันธ์

ฟังก์ชันเบื้องต้น

มีฟังก์ชันพื้นฐานเพียงเล็กน้อยที่จำเป็นในการทำให้ LISP เป็นภาษาที่สมบูรณ์ ความซับซ้อนหลายอย่าง เช่น การจัดสรรหน่วยความจำและการรวบรวมขยะ ได้รับการจัดการโดยคอมไพเลอร์

การแนะนำไวยากรณ์ของ LISP โดยย่อมีประโยชน์เนื่องจากบางแง่มุมไม่เป็นไปตามสัญชาตญาณ โดยเฉพาะราคาและการประเมินจากภายในสู่ภายนอก

เครื่องหมายคำพูดเป็นสิ่งจำเป็นสำหรับ LISP เนื่องจากไม่มีการแยกข้อมูลและโค้ด ลำดับของอักขระสามารถตีความได้ว่าเป็นตัวแปรหรือค่าขึ้นอยู่กับบริบท อักขระที่ยกมาช่วยแก้ปัญหานี้ด้วยการบังคับให้ตีความค่าตามตัวอักษร

ด้วยความเข้าใจพื้นฐานนี้ คุณก็พร้อมสำหรับฟังก์ชันพื้นฐาน 5 ประการที่จำเป็นสำหรับ LISP

อะตอม

ตรวจสอบว่าองค์ประกอบเป็นสัญลักษณ์เดียวหรือไม่

(atom 'x)
; returns t
(atom '(a b))
; returns nil

eq

ตรวจสอบว่าสัญลักษณ์อะตอมสองอันเหมือนกันหรือไม่ ใน Arc เขียนเป็น 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

รถ

หมายถึงเนื้อหาของการลงทะเบียนที่อยู่ มันจะส่งคืนไอเท็มแรกในรายการ ตราบใดที่มันไม่ใช่อะตอมมิก

(car '(x a))
; returns x
(car '((x a) y))
; returns (x a)

ซีดี

ย่อมาจากเนื้อหาของการลงทะเบียนการลด มันจะส่งคืนทุกอย่างหลังจากรายการแรกในรายการ

(cdr '(x a))
; returns a
(cdr '((x a) y))
; returns y
(cdr '((x a) (y b)))
; returns (y b)

ข้อเสีย

ใช้เพื่อสร้างรายการจากอะตอมหรือรายการอื่นๆ

(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)

หน้าที่พื้นฐาน

ฟังก์ชันเหล่านี้เป็นแกนหลักของ "ฟังก์ชันสากล" ซึ่งเป็นจุดสิ้นสุดสูงสุดของการดำเนินการนี้

หากคุณมีปัญหาในการติดตามไวยากรณ์ ฉันขอแนะนำให้อ่าน "บทช่วยสอนส่วนโค้ง" ของ Paul Graham ก่อน

_โมฆะ

ประเมินว่านิพจน์ว่างเปล่าหรือไม่

(def _null (x)
  (is x nil))
(_null nil)
; returns t
(_null '(x a))
; returns nil

_และ

ประเมินว่าเงื่อนไขทั้งสองเป็นจริงหรือไม่ ใน Arc นั้น t แสดงถึงความจริง และ nil แสดงถึงเท็จ

(def _and (x y)
  (if (is x t) (is y t) t nil))
(_and 'x 'y)
; returns t
(_and 'x nil)
; returns nil

_ไม่

ประเมินว่าเงื่อนไขคือ nil หรือไม่

(def _not (x)
  (if (is x nil) t))
(_not nil)
; returns t
(_not 'x)
; returns nil

_caar, _cadr, _caddr, _cadar และ _caddar

เหล่านี้เป็นชวเลขสำหรับการรวมกันของ car และ cdr สิ่งเหล่านี้เกิดขึ้นบ่อยครั้งดังนั้นชวเลขทำให้โค้ดของคุณแห้ง

(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

_ผนวก

ช่วยให้คุณเข้าร่วมรายการ

(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)

_รายการ

วิธีนี้จะรักษาความสมบูรณ์ของรายการที่คุณส่งเป็นอาร์กิวเมนต์ และไม่จำเป็นต้องเพิ่ม cons เมื่อรวมสองอะตอม

(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))

_คู่

รวมสองรายการเข้าด้วยกันโดยสร้างคู่ตามตำแหน่งของแต่ละองค์ประกอบ

(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))

_รศ

รับค่าจากคู่คีย์-ค่า โดยที่อาร์กิวเมนต์แรกคือคีย์ และอาร์กิวเมนต์ที่สองคือรายการคู่

(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)

ฟังก์ชั่นสากล

พลังที่แท้จริงของ LISP คือความสามารถในการประเมินตัวเองจากองค์ประกอบบางอย่าง เช่นเดียวกับที่ John McCarthy ทำ เราจะกำหนด _eval ซึ่งสามารถประเมิน LISP ใน LISP

นี่เป็นลักษณะที่น่าประหลาดใจและทรงพลังที่สุดของภาษา ด้วย 5 พื้นฐานและ 12 ฟังก์ชัน คุณจะมีองค์ประกอบหลักในการสร้างล่าม

(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))))

เมื่อใช้ _eval ไวยากรณ์ของนิพจน์ที่มีอยู่จะเฉพาะเจาะจงกับล่าม เราไม่ได้เขียนด้วยภาษา Arc อีกต่อไป แต่เป็นภาษาใหม่โดยสิ้นเชิง รูปแบบดั้งเดิมของ LISP

แม้ว่าคุณจะติดตามไปแล้ว แต่ก็ยังมีหลายสิ่งที่ต้องแยกย่อยที่นี่ ดังนั้นเรามาก้าวผ่านมันไปกันเถอะ

การตีความฟังก์ชันเบื้องต้น

_eval ใช้ e เป็นนิพจน์ที่จะประเมิน และ a เป็นรายการคู่ที่ e จะอ้างอิง

หาก e เป็นอะตอมมิก _assoc จะถูกเรียกให้ส่งคืนค่าที่ตรงกับคีย์ e ใน a

(_eval 'x '((x a) (y b)))
; returns a
(_eval 'y '((x a) (y b)))
; returns b

ในกรณีของ quote สัญลักษณ์ที่ตามหลัง quote จะถูกส่งกลับตามตัวอักษร

(_eval '(quote x) nil)
; nil is needed because _eval requires two arguments
; returns x
(_eval '(quote (x a)) nil)
; returns (x a)

สำหรับฟังก์ชันพื้นฐานอื่นๆ e จะอยู่ในรูปแบบ (function key) โดยที่ key ถูกใช้เพื่อรับค่าจาก a ซึ่งจะถูกประเมินโดย function

การใช้ _eval ต่อไปนี้เทียบเท่ากับ (atom 'y) ที่ง่ายกว่ามาก แต่สิ่งสำคัญคือการทำความเข้าใจฟังก์ชัน _eval สังเกตว่า x ถูกใช้เพื่ออ้างอิงค่าในพารามิเตอร์ตัวที่สอง a อย่างไร

(_eval '(atom x) '((x y)))
; returns t
(_eval '(atom x) '((x (a b))))
; returns nil

สำหรับทุกฟังก์ชันพื้นฐานยกเว้น quote จะมีการเรียก _eval แบบเรียกซ้ำจนกว่าจะถึง _assoc หรือ quote

นี่คือขั้นตอนที่ _eval ใช้ในการประเมิน 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 และ cdr มีโครงสร้างที่คล้ายกันมากกับ atom เนื่องจากต้องมีการประเมินเพียงนิพจน์เดียวเท่านั้น

(_eval '(car x) '((x (a b c))))
; returns a
(_eval '(cdr x) '((x (a b c))))
; returns (b c)

cons และ eq มีสองนิพจน์ที่ต้องได้รับการประเมิน ดังนั้น a จึงต้องมีสองคู่

(_eval '(eq x y) '((x a) (y a)))
; returns t
(_eval '(cons x y) '((x a) (y b)))
; returns (a . b)

cond ใช้ฟังก์ชันใหม่ _evcon ซึ่งรับรายการคู่ที่มีรูปแบบ (condition expression) เมื่อพบเงื่อนไขที่แท้จริง นิพจน์นั้นจะถูกประเมิน

(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

นี่คือนิพจน์เดียวกันโดยใช้ _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

การตีความฟังก์ชัน label และ lambda

ถ้า e เป็นฟังก์ชันอะตอมมิกแต่ไม่ใช่ฟังก์ชันพื้นฐาน ฟังก์ชันนั้นจะต้องเป็นฟังก์ชัน label หรือ lambda ที่ผู้ใช้กำหนด

นิพจน์ lambda มีรูปแบบ (lambda (param) (expression) arg) โดยที่ arg จะถูกส่งผ่านไปยัง expression ถึง param

(_eval '((lambda (param)
           (cond ((atom param) (quote is_atom))
                 ((quote t)    (quote not_atom))))
          arg)
       '((arg (a b))))
; returns not_atom

โปรดทราบว่า (quote t) ถูกใช้ที่นี่เป็นเงื่อนไข else ที่ชัดเจน Arc จัดการกรณีเหล่านี้อย่างสวยงาม แต่เนื่องจากเราผูกพันกับกฎของล่าม เราจึงต้องใช้ไวยากรณ์นี้

ในระหว่างการประเมิน นิพจน์ lambda ข้างต้นจะกลายเป็น

(_eval '(cond ((atom param) (quote is_atom))
              ((quote t)    (quote not_atom)))
       '((param (a b)) (arg (a b))))

โปรดสังเกตว่าอาร์กิวเมนต์ถูกขยายให้มีคู่สำหรับ param อย่างไร ซึ่งใช้ฟังก์ชันเสริม _evlis ซึ่งสร้างรายการคู่แบบวนซ้ำจาก arg สำหรับแต่ละ param ใน lambda ซึ่งอนุญาตให้ lambda จัดการรายการพารามิเตอร์ใดๆ ได้

((lambda (p1...pn) e) a1...an) เป็นคำจำกัดความที่เป็นทางการ .

label อนุญาตให้เรียกใช้ฟังก์ชันตามชื่อ ซึ่งเป็นคุณลักษณะที่สำคัญที่สุดของภาษาการเขียนโปรแกรมใดๆ

ที่นี่ McCarthy กำหนด ff ว่าเป็นฟังก์ชันเพื่อส่งคืนอะตอมแรกในรายการ มันใช้การเรียกซ้ำที่มีป้ายกำกับ

(_eval '((label ff (lambda (x)
                     (cond ((atom x) x)
                           ((quote t) (ff (car x))))))
         y)
       '((y ((a b) c))))
; returns a

เมื่อ _eval พบ label มันจะเก็บฟังก์ชันนั้นไว้ใน a เพื่อนำไปใช้ในภายหลัง นอกจากนี้ยังจะเริ่มประเมินฟังก์ชัน lambda ที่กำหนดโดย label ด้วย ในระหว่างการประเมิน นิพจน์ข้างต้นจะกลายเป็น

(_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))))

ดังที่ McCarthy กล่าวไว้ การประเมินแบบเต็มคือ “กิจกรรมที่เหมาะกับคอมพิวเตอร์อิเล็กทรอนิกส์มากกว่าผู้คน” ฉันเห็นด้วยและจะไม่แสดงรายการการประเมินทุกขั้นตอน

ลดความซับซ้อน _eval

การใช้ _eval ในรูปแบบดิบค่อนข้างละเอียด ดังนั้น McCarthy จึงกำหนด _apply เป็น wrapper เป็น _eval ซึ่งช่วยให้สำนวนสั้นลงและเข้าใจง่ายขึ้น

นี่จะใช้พารามิเตอร์สำหรับ _eval และล้อมไว้เช่น (quote (param)) นอกจากนี้ยังใช้อาร์กิวเมนต์กับฟังก์ชันโดยตรงอีกด้วย

(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))

เมื่อใช้ฟังก์ชันนี้ ฟังก์ชัน ff สามารถเขียนเป็นได้

(_apply '(label ff (lambda (x)
                     (cond ((atom x) x)
                           ((quote t) (ff (car x))))))
        '(a b))

ซึ่งเรียก _eval เป็น

(_eval '((label ff (lambda (x)
                     (cond ((atom x) x)
                           ((quote t) (ff (car x))))))
          (quote a) (quote b))
       'nil)

_apply ใช้ได้กับทุกสิ่งที่คุณเขียนโดยใช้ _eval แต่จะมีประโยชน์ที่จะทำความเข้าใจ _eval ก่อน ก่อนที่จะเพิ่มเลเยอร์ของนามธรรมนี้

ซื้อกลับบ้าน

ความสามารถในการกำหนดภาษาใหม่และการตรวจสอบสถานะภายในทำให้ LISP เป็นภาษาที่ยอดเยี่ยมสำหรับการสำรวจและการทดลอง

ความมหัศจรรย์ของการรวบรวมและปฏิบัติการหายไปแล้ว คุณสามารถดูการประเมินทุกขั้นตอนได้ด้วยตัวเอง นั่นทำให้การฝึกสะดุดผ่านไวยากรณ์ที่เก่าแก่สมหวัง

ฉันไม่เห็นตัวเองใช้ LISP ในการผลิต อย่างไรก็ตาม ฉันจะใช้มันเป็นเครื่องมือในการขยายความเข้าใจเกี่ยวกับการเขียนโปรแกรมระดับต่ำต่อไป

ขั้นตอนต่อไปสำหรับฉันคือการทำความเข้าใจวิธีการใช้คอมไพเลอร์ที่จะแปลงสิ่งนี้เป็นรหัสเครื่อง ฉันวางแผนที่จะอ่าน "โครงสร้างและการตีความโปรแกรมคอมพิวเตอร์" เพื่ออ่าน

นอกจากนี้ ฉันต้องการปรับปรุงล่ามนี้ให้ทันสมัย ดังที่ Paul Graham เขียนว่า “ภาษาที่เขา [John McCarthy] เขียนในปี 1960 ขาดหายไปมาก ไม่มีผลข้างเคียง ไม่มีการดำเนินการตามลำดับ ไม่มีตัวเลขที่ใช้งานได้จริง และมีขอบเขตแบบไดนามิก” แต่สิ่งนี้สามารถแก้ไขได้

Paul Graham กล่าวถึงบทความของ Steele และ Sussman เรื่อง "The Art of the Interpreter" โดยไม่ได้เจาะจงเจาะจง บางทีฉันจะพูดถึงสิ่งเหล่านี้ในบทความอื่น

เมื่อเจาะลึกประวัติความเป็นมาของการเขียนโปรแกรม คุณจะพบอิทธิพลของ LISP ทุกที่ การฝึกปรับให้เข้ากับรูปแบบไวยากรณ์เป็นสิ่งที่ควรค่าแก่การแสวงหาในตัวมันเอง แต่การพัฒนาความเข้าใจที่แท้จริงนั้นจะเปิดหน้าต่างสู่การทำงานภายในของทุกภาษา นั่นคือจุดประสงค์ของการทำความเข้าใจ LISP

เผยแพร่ครั้งแรกที่ https://joshbradley.me เมื่อวันที่ 4 เมษายน 2020