ภาษา Python แบบโฮโมไอคอนิก (Homoiconic)

 (aljamal.substack.com)
2 คะแนน โดย GN⁺ 2024-05-13 | 2 ความคิดเห็น | แชร์ทาง WhatsApp
  • ความเป็นโฮโมไอคอนิก ของ Lisp คือคุณสมบัติที่ปฏิบัติต่อโค้ดและข้อมูลในรูปแบบเดียวกัน และเมื่อนำ “Lisp in Lisp” แบบคลาสสิกมาย้ายเป็น Python แนวคิดนี้ก็ปรากฏให้เห็นในไวยากรณ์ที่คุ้นเคยกว่า
  • เดิมที Lisp มีทั้ง M-expression ซึ่งเป็นการแทนโค้ด และ S-expression ซึ่งเป็นการแทนข้อมูล ส่วน “Lisp in Lisp” คือการใช้ M-expression เพื่อ implement S-expression Lisp
  • เวอร์ชัน Python แทน S-expression ด้วย ลิสต์ของ Python และย้าย M-expression ไปเป็นการเรียกฟังก์ชันกับคำสั่งเงื่อนไข จึงสร้าง interpreter ได้โดยไม่ต้องมี parser แยกต่างหาก
  • interpreter ตัวแรกตั้งอยู่บน primitive operation สำหรับลิสต์ เช่น atom, eq, car, cdr, cons, append และเพื่อรองรับ lambda จึงเพิ่ม assoc, pairlis และลิสต์สภาพแวดล้อมเข้ามา
  • eval รับทั้ง expression และสภาพแวดล้อมเพื่อจัดการ variable binding และเชื่อมอาร์กิวเมนต์กับค่าตามแนวทาง dynamic scope ผ่าน pairlis และ assoc

การผสานโค้ดและข้อมูลที่ Lisp แสดงให้เห็น

  • Lisp ทิ้งแนวคิดหลายอย่างที่ยังใช้ได้แม้ผ่านไปหลายสิบปี ผ่าน บทความ Lisp ของ John McCarthy ในช่วงต้นทศวรรษ 1960 และ คู่มือ Lisp 1.5
  • แก่นสำคัญอย่างหนึ่งในนั้นคือ ความเป็นโฮโมไอคอนิก
    • ในภาษาทั่วไป โค้ดมักถูกเข้าใจว่าเป็นลำดับของ operation ที่กระทำต่อข้อมูล
    • Lisp ปฏิบัติต่อโค้ดและข้อมูลในรูปแบบเดียวกัน ทำให้เส้นแบ่งระหว่าง operator กับ operand พร่าเลือนลง
  • Alan Kay เรียกโค้ด “Lisp in Lisp” ที่อยู่ท้ายหน้า 13 ของคู่มือ Lisp 1.5 ว่า “Maxwell's Equations of Software”
    • มีการอ้างถึงแนวคิดว่า นี่เป็นการตระหนักรู้ครั้งใหญ่ เพราะโค้ดเพียงไม่กี่บรรทัดบรรจุโลกทั้งใบของการเขียนโปรแกรมไว้ได้

วิธีนำ “Lisp in Lisp” มาย้ายเป็น Python

  • เป้าหมายคือการเขียนโค้ด “Lisp in Lisp” แบบคลาสสิกขึ้นใหม่ด้วย Python โดยรักษาจิตวิญญาณของโค้ดดั้งเดิมไว้ให้มากที่สุด
  • Lisp มีรูปแบบไวยากรณ์สองแบบ
    • M-expression: การแทนโค้ด ย่อมาจาก meta
    • S-expression: การแทนข้อมูล ย่อมาจาก symbolic
    • ทั้งสองรูปแบบเทียบเท่ากันในเชิงความหมาย
  • โค้ด “Lisp in Lisp” เดิมเขียนด้วย M-expression เพื่อ implement S-expression Lisp
  • ใน implementation แบบ Python จะใช้ ลิสต์ของ Python แทน Lisp S-expression
    • Lisp ย่อมาจาก “List Processing” และทำงานโดยมีโครงสร้างข้อมูลเดียวคือ list เป็นศูนย์กลาง
    • ลิสต์ของ Python ถูกใช้เป็นรูปแบบที่เหมาะสำหรับจำลอง Lisp S-expression
  • M-expression ถูกแปลเป็นโครงสร้างโค้ดอย่างการเรียกฟังก์ชันและคำสั่งเงื่อนไขของ Python
    • mapping นี้ทำให้สร้าง interpreter ได้โดยไม่ต้องจัดการสตริงหรือ implement parser แยกต่างหาก

interpreter ตัวแรกที่สร้างจาก primitive operation ของลิสต์

  • การ implement Lisp ต้องมี ฟังก์ชันพื้นฐาน บางอย่างที่ภายนอกภาษาเป็นผู้จัดเตรียมให้
  • primitive operation ของลิสต์ที่ใช้ใน implementation แบบ Python มีดังนี้
    • atom(x): ตรวจสอบว่า x เป็นลิสต์หรือไม่
    • eq(x,y): ตรวจสอบว่า x กับ y เหมือนกันหรือไม่
    • car(x): องค์ประกอบแรกของลิสต์
    • cdr(x): ส่วนที่เหลือของลิสต์
    • cons(x,y): นำ atom ไปต่อเข้ากับลิสต์
    • append(x,y): ต่อสองลิสต์เข้าด้วยกัน
  • นอกจาก primitive operation แบบ recursive บางตัวแล้ว สามารถใช้ Llama3-70b บน Groq เพื่อสร้าง interpreter ที่รัน subset ของโค้ด “Lisp in Lisp” ได้อย่างรวดเร็ว
  • ในตัวอย่าง ลิสต์ของ Python ทำงานเหมือน S-expression
  • โค้ดทั้งหมดมีให้ดูที่ github gists

การขยายเพื่อรองรับ lambda และ recursion

  • implementation แรกยังขาดฟีเจอร์สำคัญอย่าง lambda
    • lambda เป็นวิธีหลักใน Lisp สำหรับนิยามและเรียก anonymous function
    • ใน Lisp หากไม่มี lambda ก็ไม่สามารถ implement recursion ได้
    • หากไม่มี recursion ก็ไม่ถึงเกณฑ์ขั้นต่ำของ Turing completeness ซึ่งหมายถึงความสามารถในการคำนวณทุกสิ่งที่คำนวณได้
  • เพื่อใส่ lambda จึงเพิ่ม assoc(x,y) และ pairlis(x,y) เข้ามา
    • assoc(x,y) คือการ lookup key/value ที่ implement ด้วยลิสต์ โดยใช้ association list
    • pairlis(x,y) จับคู่สองลิสต์เข้าด้วยกันเหมือน zip(x,y) ของ Python
  • Lisp ดั้งเดิมต้องจัดการแม้แต่ linear scan ง่าย ๆ ด้วย recursion
    • เพราะ Lisp ดั้งเดิมไม่มี loop
    • ในคำแปลเป็น Python สามารถเขียน assoc และ pairlis ให้กระชับขึ้นด้วย list comprehension
  • ในการจัดการ COND จะถอด evcon ของ Lisp ดั้งเดิมเป็น loop และในการจัดการ LAMBDA ก็ใช้แนวทางเดียวกันกับ evlis

ลิสต์สภาพแวดล้อมและ dynamic scope

  • ฟังก์ชัน eval ของ Lisp ดั้งเดิมรับอาร์กิวเมนต์สองตัว
    • อาร์กิวเมนต์แรกคือ S-expression ที่จะประเมินค่า
    • อาร์กิวเมนต์ที่สองคือลิสต์สภาพแวดล้อมในรูปแบบรายการ key/value
  • สภาพแวดล้อมรักษา variable binding ไว้ในการจัดการ LAMBDA
    • หากฟังก์ชันมีตัวแปร x และมีการใส่ข้อมูลเข้าไป pairlis จะจับคู่สัญลักษณ์ x กับข้อมูล
    • ค่าที่จับคู่แล้วจะถูกบันทึกหรือเพิ่มลงในลิสต์สภาพแวดล้อม
    • เมื่อต้องใช้ x assoc จะค้นหาจากสภาพแวดล้อมแล้วนำกลับไปแทนใน expression
  • วิธี binding นี้เรียกว่า dynamic scope
  • implementation สุดท้ายคือรูปแบบที่ย้าย “Lisp in Lisp” ดั้งเดิมมาเป็น Python และในตัวอย่างสุดท้ายรวมถึงการรัน lambda ด้วย

บทความที่เกี่ยวข้อง

2 ความคิดเห็น

 
GN⁺ 2024-05-13
ความคิดเห็นบน Hacker News

  • ถ้าสนใจ Lisp สำหรับสคริปต์ที่เรียบง่ายและเร็วในสไตล์ Python ก็น่าดูภาษาแนว Clojure อย่าง Hy และ Janet

    1. Hy(https://hylang.org/): คอมไพล์เป็นไบต์โค้ดของ Python และโดยทั่วไปช้ากว่า Python แต่เข้ากันได้กับไลบรารี Python ทั้งหมด
    2. Janet(https://janet-lang.org/): มี VM แบบฝังตัวที่เบามากสไตล์ Lua ขนาดประมาณ 1MB เร็วกว่า Python ราว 2 เท่าในการคำนวณคล้ายกัน และทำงานร่วมกับ C ได้ง่ายมาก
    • ถ้าพูดถึงสคริปต์เร็ว ๆ สไตล์ Python ก็มี Common Lisp แบบแบตเตอรี่ครบในตัวอย่าง https://github.com/ciel-lang/ciel ด้วย
      มีให้ใช้เป็นไบนารีที่เริ่มทำงานได้เร็ว และรวมไลบรารีสำหรับงานประจำวันไว้ด้วย
      ฝั่ง CL↔Python ก็น่าดู https://github.com/CodyReichert/awesome-cl?tab=readme-ov-fil... เช่นกัน
    • Hy ช้ากว่า Python เหรอ? อย่างน้อยก็ไม่ควรเป็นแบบนั้นในเวลาเรียกใช้งาน
      ผมเป็น ผู้ดูแล Hy ถ้าเห็นความต่างด้านประสิทธิภาพที่มีนัยสำคัญ นั่นคือบั๊ก
      1. Basilisp(https://github.com/basilisp-lang/basilisp): “ภาษา Lisp สายย่อยที่เข้ากันได้กับ Clojure แบบ -ish โดยมุ่งเป้าไปที่ Python 3.8+”
    • อาจดูเหมือนเป็นความชอบส่วนตัว แต่ Lisp ให้ความรู้สึกเสมอว่าเป็น ภาษาที่ชวนให้ถูกโต้แย้ง เพราะวงเล็บครอบที่จำเป็น
      M-expression เลี่ยงกับดักนี้ได้ เลยสงสัยว่าเคยมีภาษาจริงที่ไม่ต้องใช้วงเล็บแบบนี้ แต่ยังคงความเป็น homoiconicity และความสง่างามเชิงแนวคิดของ Lisp ไว้หรือไม่
    • https://github.com/yaml/yamlscript
      นี่แหละ สิ่งที่คิดอยู่พอดี คำอธิบายก็ตรงไปตรงมามาก: “Program in YAML”
      แทบไม่ต้องพูดอะไรเพิ่มแล้ว

  • เดี๋ยวนะ นี่ก็แค่ Lisp ที่เขียนด้วย Python ไม่ใช่เหรอ?
    ดูไม่เหมือน Python แบบ homoiconic ตามที่ชื่อสื่อไว้ ผมพลาดอะไรไปหรือเปล่า?

    • ตามกฎข้อที่สิบของ Greenspun ก็ใช่: https://en.m.wikipedia.org/wiki/Greenspun's_tenth_rule
    • ผมเองก็ตื่นเต้นอยู่ไม่น้อย นึกว่าเป็น Python แบบ homoiconic ที่จะทำให้เพื่อนร่วมงานใช้ Lisp ได้โดยไม่ต้องกล่อมให้ยอมรับ Lisp แต่ไม่ใช่ มันก็แค่ Lisp
    • ดูเหมือนจะเป็นแบบนั้น ผมสงสัยเพราะอยากเห็น Python แบบ homoiconic นี้ แต่ก็ไม่แน่ใจว่าเป็นไปได้ไหม
      ถ้าจะทำแบบนั้น ไวยากรณ์ของ Python คงต้องประกอบจากทูเพิล ลิสต์ และดิกชันนารี แล้วอินเทอร์พรีเตอร์ต้องประเมินสิ่งเหล่านั้นโดยตรง
    • ต่างกันตรงไหน?

  • อีกภาษาฟังก์ชันนัลที่สามารถอิมพลีเมนต์ได้อย่างกระชับด้วย Python คือ Binary Lambda Calculus
    โค้ดส่วนใหญ่จัดการกับโมเดลอินพุต/เอาต์พุตบริสุทธิ์ของ BLC และสำหรับการค้นหาตัวแปร จะใช้ de Bruijn index เพื่ออินเด็กซ์อาร์เรย์สภาพแวดล้อมแทนการใช้ association list
    ในหน้าเดียวกันยังมีอิมพลีเมนต์ภาษาอื่นอีก 9 ภาษา และ self-interpreter ของ BLC กระชับที่สุดที่ 232 บิต (29 ไบต์) รวมทั้งพาร์เซอร์และโทเคนไนเซอร์แล้ว
    [1] https://rosettacode.org/wiki/Universal_Lambda_Machine#Python

  • วิชาพื้นฐานการเขียนโปรแกรมของ MIT ให้ผู้เรียนทุกคนเขียน อินเทอร์พรีเตอร์ Lisp ด้วย Python
    เป็นร่องรอยจากสมัยก่อนที่วิชานั้นสอนด้วย Lisp จริง ๆ
    https://py.mit.edu/spring24

    • คล้ายกัน วิชาที่ผมเคยเรียนในมหาวิทยาลัยก็ให้สร้าง อินเทอร์พรีเตอร์ Lisp ขั้นพื้นฐานด้วย Lisp

  • ผมเคยลองทำอะไรคล้าย ๆ กันด้วยลิสต์ของ JS: https://github.com/andrelaszlo/js-lisp

  • เป็นเรื่องทั้งตลกและประชดที่ภาษา Store definition file ในยุคใหม่ ๆ ค้นพบฟีเจอร์น่าทึ่งของ Lisp อีกครั้งหลังผ่านไปหลายสิบปี
    ไม่กี่วันก่อน โปรแกรม Python ที่เรียก API โฮมเซิร์ฟเวอร์ของผมมา 9 ชั่วโมงหยุดทำงาน เลยโมโหมาก เป็นการเรียก API คล้าย ๆ กัน และกำลังเรียก LLM ด้วยเทมเพลตพรอมป์ต์ที่กำหนดไว้ล่วงหน้ากับข้อจำกัดทางไวยากรณ์
    ก่อนจะรันลูปที่เหลือแยกต่างหาก ผมอยากบันทึกสถานะของโปรแกรมแล้วปิด แต่หาวิธีแก้โค้ด Python ที่กำลังรันอยู่หรือส่องดูตัวแปรไม่ได้ สุดท้ายเลยเสีย งาน 9 ชั่วโมง ไป
    ไม่กี่วันต่อมาผมเห็น https://malisper.me/debugging-lisp-part-1-recompilation/ แล้วก็ทึ่งที่ Common Lisp มีฟีเจอร์แบบนี้ฝังอยู่ในภาษามาหลายสิบปีแล้ว ฟีเจอร์อื่น ๆ อย่างระบบมาโครที่ทรงพลังที่สุดก็เช่นกัน

    • ไม่น่าแปลกที่ภาษาสมัยใหม่ค้นพบฟีเจอร์ของ Lisp อีกครั้งหลังผ่านไปหลายสิบปี เพราะตระกูล Lisp เป็นกลุ่มภาษาที่มีความยืดหยุ่นและพลังในการสื่อความหมายมากที่สุด
      แต่นั่นก็เป็นปัญหาด้วย คือ พลังในการสื่อความหมายสูงเกินไป
      Lisp ทำให้ผมนึกถึงทัศนศิลป์สื่อผสมอยู่เสมอ อิสระในการแสดงออกดูดี แต่สุดท้ายผลงานมักออกมาด้อยกว่างานศิลป์แบบสื่อเดี่ยวที่ดั้งเดิมกว่าโดยรวม จึงเห็นได้ว่าข้อจำกัดของสื่อก็สำคัญพอ ๆ กับพลังในการสื่อความหมาย
    • ถ้าต้องการส่องสถานะได้ในระดับหนึ่ง ใช้ Py-spy หรือ Pystack ได้
      หรือมี https://github.com/malor/cpython-lldb ด้วย
      วิธีเพิ่มเติมดูได้ที่ https://github.com/albertz/pydbattach/
    • ถ้าเป็นโปรเซสที่รันหลายชั่วโมง ก็ควรบันทึกงานลงดิสก์ และเตรียมให้พร้อมเริ่มต่อจากจุดที่หยุดไปได้
    • ไม่มี exception ถูกโยนออกมาเหรอ?

  • การทำแบบนี้เป็น Python แบบ homoiconic อย่างไร?

  • มี Lisp ที่มี ระบบชนิดข้อมูล ซึ่งช่วยควบคุมแนวโน้มที่ Lisp จะอ่านยากขึ้นเมื่อโปรแกรมใหญ่ขึ้นได้บ้างไหม?
    ถึงไม่ใช่ระบบชนิดข้อมูล ผมก็สงสัยว่ามีองค์ประกอบอื่นที่ช่วยจัดการคุณสมบัติแบบนั้นได้หรือเปล่า
    เมตาโปรแกรมมิงเจ๋งมากจริง ๆ แต่บางครั้งมันอ่านเหมือน Haskell ที่เป็นนามธรรมชวนงงที่สุดเท่าที่เคยเห็น แถมไม่มีแม้แต่ type signature ให้เป็นเข็มทิศ
    ผมมองว่าระบบชนิดข้อมูลกับลินเตอร์เป็นเครื่องมือที่ดีที่สุดในการทำให้โค้ดเชื่องโดยอัตโนมัติ แต่ยังนึกไม่ออกว่าจะยับยั้งแนวโน้มของโปรเจกต์ Lisp ได้อย่างไร โดยไม่ไปจำกัดเหตุผลหลักที่เลือกใช้ Lisp เอง

    • ถ้าพูดถึง Lisp ที่มีระบบชนิดข้อมูล ผมนึกถึง Common Lisp
      SBCL ซึ่งแทบจะใกล้เคียงมาตรฐานที่สุด ก็มีการตรวจชนิดตอนคอมไพล์ที่ค่อนข้างดี
      เช่น ถ้าเขียน (declare (type String a b)) แล้วตามด้วย (+ a b) มันจะเตือนว่าชนิดอนุมานของ A คือ STRING แต่ควรเป็น NUMBER
      เหตุผลใหญ่ที่สุดที่ผมย้ายจาก Scheme มา CL ก็คือการตรวจชนิดนี้ และหลังจากนั้นก็อยู่ต่อเพราะฟีเจอร์เล็ก ๆ ดี ๆ อย่าง restarts กับ continuable asserts
    • ฝั่งที่เป็นมิตรและเข้าถึงง่ายคือ Typed Racket ส่วนฝั่งที่ทรงพลังแต่ซับซ้อนคือ Shen
    • https://en.wikipedia.org/wiki/Dylan_(programming_language)

  • ถ้ามี Python ที่เน้น expression คงดีกว่า Python ตอนนี้มาก
    บทความนี้ไม่ได้เป็นอย่างที่ชื่อชวนให้คิด แต่ในฐานะคำอธิบาย Lisp ถือว่าดี

    • Python ที่เน้น expression ก็คงไม่ใช่ Python แล้ว
      ถึงอย่างนั้นก็ไม่เป็นไร แต่ “การวาง expression ไว้เป็นไวยากรณ์ชั้นสอง” เป็นการเลือกที่ค่อนข้างพื้นฐานและตั้งใจมาก อีกทั้งยังเป็นการออกแบบให้ยากสำหรับนักพัฒนาที่อยากเขียนซุปวงเล็บด้วย
      ดังนั้น lambda: และ := จึงถูกทำให้เทอะทะโดยเจตนาเพื่อกดไม่ให้ใช้ และก็เขียนฟังก์ชันนิรนามไม่ได้ด้วย
      Python เป็นภาษาที่บอกว่าถ้าอยากทำอะไรฉลาด ๆ ให้ทำด้วย iterator ไม่ใช่วัตถุที่เรียกได้

  • อยากให้ทุกอย่างมี ความไร้ไวยากรณ์แบบ Lisp
    สำหรับผม แบบนั้นดีกว่า และโชคดีที่ใน CL ทำแบบนั้นได้ง่าย
 
kayws426 2024-05-13

ภาษาถิ่นของ Lisp ที่ฝังอยู่ใน Python
https://hylang.org/