บทความที่เปลี่ยนวิธีคิดของผมเกี่ยวกับภาษาโปรแกรม

• แนะนำบทความ งานวิจัย และวิดีโอต่าง ๆ ที่เปลี่ยนมุมมองของผมต่อ ภาษาโปรแกรม และ คอมไพเลอร์ ไปอย่างสิ้นเชิง
• แหล่งข้อมูลที่ช่วยขยายความเข้าใจอย่างมากในเรื่อง การทำ GC, การออกแบบออปติไมเซอร์, การจัดสรรรีจิสเตอร์, เอนจิน regular expression ในเชิงปฏิบัติ
• อธิบายอัลกอริทึมและโครงสร้างที่ใช้จริงอย่าง Z3, abstract domain, รูปแบบ SSA, E-Graphs ได้เข้าใจง่าย พร้อมตัวอย่างโค้ดจริง
• แต่ละชิ้นอธิบายแนวคิดที่ซับซ้อนอย่างกระชับ ทั้งยัง ขยายต่อได้ และทำความเข้าใจได้ไม่ยาก

---

แนะนำบทความที่เปลี่ยนมุมมองเกี่ยวกับภาษาโปรแกรมและคอมไพเลอร์

• บางครั้งผมก็เจองานวิจัย บล็อกโพสต์ หรือวิดีโอเกี่ยวกับภาษาโปรแกรมและคอมไพเลอร์ที่เปลี่ยนความคิดของผมไปโดยสิ้นเชิง
• บางชิ้นส่งอิทธิพลแรงมากจนผมแทบจำไม่ได้ด้วยซ้ำว่าก่อนอ่านนั้นเคยคิดอย่างไร
• ด้านล่างคือแหล่งข้อมูลลักษณะนั้นที่อยากแนะนำ (ไม่เรียงลำดับ)

เกี่ยวกับ GC, ออปติไมเซอร์, abstract domain, การจัดสรรรีจิสเตอร์

• บทความ a simple semi-space collector ของ Andy Wingo แสดงให้เห็นอย่างชัดเจนว่าจะแปลงแนวคิด Cheney/copying/compacting garbage collector จากทฤษฎีไปสู่การใช้งานจริงได้อย่างไร
  • แกนหลักของการติดตั้ง GC ในบทความนั้นกระชับมาก ขยายต่อได้ และใช้เวลาเพียงครึ่งวันก็พอจะเข้าใจได้
• บทความ Implementing a Toy Optimizer ของ CF Bolz-Tereick ช่วยเปลี่ยนมุมมองเรื่องวิธี rewrite instruction ในออปติไมเซอร์
  • เน้นการใช้ forwarding pointer แทนการค้นหาแล้วแทนที่แบบง่าย ๆ พร้อมแนะนำแนวคิด union-find
  • ซีรีส์ toy optimizer ทั้งชุดมีเนื้อหาใหม่และน่าสนใจในทุกตอน
• บทความ A Knownbits Abstract Domain for the Toy Optimizer, Correctly แนะนำทั้ง abstract domain แบบใหม่และวิธีใช้ Z3 ไปพร้อมกัน
  • ไม่ได้แค่แสดงให้เห็นว่า Z3 ถูกใช้พิสูจน์ การคำนวณเชิงตัวเลข หลายแบบอย่างไร แต่ยังมีตัวอย่างการใช้เป็นเอนจินตรวจสอบโค้ด Python ด้วย
  • นำเสนอแนวคิดว่าถ้า Z3 หา counterexample ไม่เจอ ก็ถือเป็น หลักประกันความถูกต้อง ของโค้ดได้
• ใน Cranelift, Part 3: Correctness in Register Allocation ของ Chris Fallin มีการอธิบายวิธี พิสูจน์โดยตรงว่าการจัดสรรรีจิสเตอร์ถูกต้องสำหรับทุกอินพุต
  • ในสภาพแวดล้อมโปรดักชัน ผลลัพธ์ที่ได้จะเป็นการจัดสรรที่ถูกต้อง หรือไม่ก็ crash ที่มีความหมายอย่างใดอย่างหนึ่ง
  • ยังนำแนวทาง fuzzing มาใช้สำรวจ state space และตรวจจับบั๊กด้วย

เกี่ยวกับ parsing, interpreter, JIT, โครงสร้างเชิงนามธรรม

• Regular Expression Matching: the Virtual Machine Approach ของ Russ Cox นำเสนอการสร้างเอนจิน regular expression ด้วย โค้ดอ่านง่าย ราว 50 บรรทัด
  • ระหว่างนั้นยังอธิบายหลักการของ coroutine, fiber, scheduler และสิ่งที่เกี่ยวข้องได้อย่างเข้าใจง่าย
• micrograd ของ Andrej Karpathy เป็นตัวอย่างการติดตั้งใช้งานขนาดจิ๋วที่ทำให้ โครงข่ายประสาทเทียม ทำงานได้โดยไม่พึ่งไลบรารีภายนอก ช่วยให้เข้าใจโครงสร้างและหลักการพื้นฐานของแมชชีนเลิร์นนิง
• How I implement SSA form ของ Fil Pizlo แนะนำวิธีใหม่ในการปรับปรุงโครงสร้าง union-find
  • เป็นแนวทางที่จัดการพอยน์เตอร์เพิ่มเติมในการแปลง SSA ผ่าน Identity tag ภายในอ็อบเจ็กต์
  • นอกจากนี้ยังชวนให้คิดต่อเรื่อง Phi/Upsilon form, heap effect แบบ TBAA และประเด็นอื่น ๆ
• Speculation in JavaScriptCore ของ Fil Pizlo ลงรายละเอียดวิธี ติดตั้งใช้งานออปติไมเซอร์ หลากหลายรูปแบบใน JavaScriptCore
  • อ่านซ้ำกี่ครั้งก็มักได้อินไซต์ใหม่เสมอ

การออกแบบคอมไพเลอร์, parser, โครงสร้าง IR, E-Graphs

• ในบรรยาย Modernizing Compiler Design for Carbon Toolchain ของ Chandler Carruth (ช่วงนาทีที่ 29 โดยประมาณ) มีการอธิบายการตั้งเป้า เวลา compile ที่เร็วอย่างมากและกระบวนการออกแบบสถาปัตยกรรมโดยรวม
  • ตั้งแต่นาทีที่ 40 เป็นต้นไปจะค่อย ๆ แกะอธิบายโครงสร้างในแต่ละชั้น
• A Python Interpreter Written in Python ของ Allison Kaptur ช่วยให้เข้าใจการทำงานของ bytecode interpreter ภายใน CPython ได้ง่ายขึ้น
• Parsing expressions by precedence climbing ของ Eli Bendersky แนะนำวิธี parsing แบบ Precedence Climbing ที่เข้าใจง่ายกว่าพาร์เซอร์แบบ recursive descent ดั้งเดิม และมีภาระในการพัฒนาน้อยกว่า
• Ruby JIT Challenge ของ Takashi Kokubun แสดงให้เห็นการสร้างโค้ดและ วิธีจัดสรรรีจิสเตอร์แบบใหม่ (stack folding at compile-time)
• An Incremental Approach to Compiler Construction (PDF) ของ Abdulaziz Ghuloum อธิบาย แนวทางติดตั้งใช้งานแบบ single-pass ที่ช่วยให้เข้าใจการออกแบบคอมไพเลอร์หลายขั้นแบบดั้งเดิมได้ในคราวเดียว
  • ใช้วิธีเพิ่มความสามารถแต่ละส่วนแบบ end-to-end ทีละขั้น
• Lessons from Writing a Compiler ของ Fernando Borretti อธิบายกลยุทธ์การสร้างคอมไพเลอร์ด้วยถ้อยคำที่ ชัดเจนเป็นระบบ
• งานวิจัย egg: Fast and extensible equality saturation เปลี่ยนวิธีมองออปติไมเซอร์และลำดับของ pass ไปอย่างถึงราก
  • เสนอแนวคิดให้เก็บทุกเวอร์ชันที่เป็นไปได้ของนิพจน์ไว้ในรูป ไฮเปอร์กราฟแบบบีบอัด แล้วค่อยเลือกเวอร์ชันที่ดีที่สุด
• Cranelift: Using E-Graphs for Verified, Cooperating Middle-End Optimizations ของ Chris Fallin พิสูจน์ว่า e-graphs สามารถทำงานได้อย่างมีประสิทธิภาพแม้ในคอมไพเลอร์เชิงพาณิชย์จริง
• Acyclic Egraphs and Smart Constructors ของ Phil Zucker สำรวจโครงสร้าง acyclic e-graph และการใช้ smart constructor
  • ตอนแรกเป็นบทความที่เข้าใจยาก แต่เมื่อเวลาผ่านไปก็ยิ่งเข้าใจลึกขึ้นเรื่อย ๆ

การเก็บ AST, การวิเคราะห์เชิงไดนามิกแบบขนานขนาดใหญ่ และอื่น ๆ

• คอมเมนต์นี้บน Reddit ของ Bob Nystrom และ Flattening ASTs ของ Adrian Sampson
  • อธิบายวิธีเก็บ AST ให้กะทัดรัดแทบเหมือนไบต์โค้ด
  • และชี้ให้เห็นว่าถ้าเก็บโหนด IR ในลักษณะนี้ ก็อาจทำการวิเคราะห์แบบขนานขนาดใหญ่โดยไม่ต้องใช้ล็อกได้ด้วย
  • ข้อสังเกตของ Cliff Click เกี่ยวกับ ความเร็วในการจัดสรรบัฟเฟอร์ ก็มีอิทธิพลต่อแนวคิดลักษณะนี้เช่นกัน

[GN⁺]

ความคิดเห็นบน Hacker News

• ฉันชอบโพสต์นี้มาก ช่วงหลังอ่านงานวิจัยด้านวิทยาการคอมพิวเตอร์เยอะพอสมควร แต่ในนี้ก็ยังมีบางอย่างที่ฉันยังไม่เคยเจอ อยากแนะนำงานที่ฉันชอบแต่ไม่มีอยู่ในรายการนี้สักหน่อย: “Open, Extensible Object Models” ของ Ian Piumarta ว่าด้วยระบบ metaobject เชิงวัตถุแบบมินิมัลที่ให้อิสระกับโปรแกรมเมอร์สูงสุด โดยพื้นฐานกำหนดไว้แค่การส่งข้อความเท่านั้น ที่เหลือทั้งหมดเปลี่ยนได้ตอนรันไทม์ ให้ความรู้สึกเหมือนเวอร์ชันใช้งานจริงของ “Art of the Metaobject Protocol”, “Scripting: Higher-Level Programming for the 21st Century” ของ John Ousterhout ว่าด้วยแนวแบ่งขั้วระหว่างภาษาสำหรับ system programming กับ scripting language เรามักอยากได้ภาษาสมบูรณ์แบบแบบหลายพาราไดม์ที่ทั้งเร็วและทำงานได้อย่างมีประสิทธิผลในทุกอย่าง แต่หลายครั้งภาษาระบบที่คอมไพล์ได้ เร็ว และซับซ้อน ก็ทำงานได้ดีกว่าเมื่อจับคู่กับฟรอนต์เอนด์แบบ interpreter ที่สะดวกและยืดหยุ่น จริง ๆ แค่ใช้ C กับ Tcl ร่วมกันก็มักเพียงพอแล้ว เป็นบทความที่ใครทำภาษาโปรแกรมควรอ่าน, Project Oberon ของ Niklaus Wirth เป็นตัวอย่างของการสร้างระบบคอมพิวเตอร์ทั้งระบบตั้งแต่ UI ระดับสูงไปจนถึงเคอร์เนล คอมไพเลอร์ และสถาปัตยกรรม CPU คล้าย RISC เขาเรียกร้องเรื่อง “lean software” อย่างหนักแน่นและลงมือทำจริง ในยุคนี้ที่เต็มไปด้วย dependency hell และ abstraction ที่เกินจำเป็น มันคือฝีมือเชิงช่างที่สูญหายไปแล้ว

  • ฉันไม่เห็นด้วยกับแนวแบ่งขั้วและข้อสรุปของ Ousterhout ประเด็นของเขาคือภาษามีได้แค่เป็นภาษาระบบ (C) หรือไม่ก็ภาษา script (Tcl, Python) อย่างใดอย่างหนึ่ง ภาษาระบบมี type ที่เข้มงวดและใช้กับ data structure/algorithm ส่วนภาษา script ไม่มี type เลยจึงเหมาะกับงาน “กาวเชื่อม” เขาอ้างว่าภาษาที่ “ไม่มี type” ทำให้เขียนได้กระชับและพัฒนาได้เร็วกว่า แต่ฉันคิดว่านี่ไม่ใช่คำอธิบายที่สมจริง เขายกตัวอย่างเปรียบเทียบโค้ด Tcl กับ C++/MFC แล้วบอกว่า Tcl ดีกว่า แต่จริง ๆ แล้วมันแค่ชอบเพราะ syntax ดีกว่าเท่านั้นเอง คำกล่าวว่าภาษาที่ไม่มี type จะเร็วกว่าไม่เป็นความจริง มันแค่ต่างกันตรงว่าจะไปชนข้อจำกัดเมื่อไร การตรวจ type error ทั้งหมดก่อนรันย่อมดีกว่า และทุกภาษาก็วิเคราะห์ static type ได้ แต่ที่ไม่ทำเพราะมันซับซ้อนและยาก ในฐานะผู้ออกแบบ PL การตรวจ type เฉพาะตอนรันไทม์เป็นการตัดสินใจที่สมเหตุสมผลเพราะทำให้สร้างภาษาได้ง่ายขึ้น แต่ไม่ได้แปลว่ามันเป็นตัวเลือกที่ดีกว่า

• ฉันชอบโพสต์นี้มาก บทความเรื่องภาษาโปรแกรมทำให้วิธีที่ฉันมองการเขียนโปรแกรมเปลี่ยนไปเลย ฉันมักนึกถึงคำอ้างเรื่อง “ความปลอดภัย” จาก TAPL(Types and Programming Languages) อยู่บ่อย ๆ ภาษาที่ปลอดภัยคือภาษาที่กันไม่ให้โปรแกรมเมอร์ยิงเท้าตัวเอง และช่วยปกป้อง abstraction ของตัวเอง กล่าวคือความสามารถของภาษาที่จะรับประกันความสมบูรณ์ของทั้ง abstraction ที่ภาษามีให้และ abstraction ระดับสูงที่โปรแกรมเมอร์สร้างขึ้นมา ตัวอย่างเช่น ถ้ามี abstraction อย่าง array มันก็ควรถูกเปลี่ยนได้เฉพาะตอนอัปเดตอย่างชัดเจนเท่านั้น และไม่ควรไปเผลอแตะ data structure อื่นผิด ๆ ได้

• พูดถึงนิสัยการพัฒนาที่น่าสนใจ... Aaron Hsu ที่ดังจาก APL จะเขียนโค้ดด้วยปากกาหมึกซึมในสไตล์คัลลิกราฟีเวลาเรียบเรียงความคิด ส่วนฉันก็คล้าย ๆ กัน คือใช้ปากกาลูกลื่นราคาถูกวาดอะไรประมาณ flowchart ของ Python object เพื่อจัดระเบียบความคิด เป็น UML แบบประหยัด

  • ฉันเองพอเจอปัญหาที่ยากที่สุดก็มักจะหยิบปากกาหมึกซึมมาใช้เหมือนกัน การใช้ปากกาหมึกซึมเหมือนพาตัวเองเข้าสู่พื้นที่การคิดอีกแบบหนึ่ง มันมีข้อจำกัดในการแก้ไข เลยบังคับให้คิดอย่างสอดคล้องและเป็นเส้นตรงมากขึ้น แต่ก็เปิดพื้นที่สร้างสรรค์เพราะสลับไปมาระหว่างภาษาอังกฤษ โค้ด คณิตศาสตร์ ไดอะแกรม ฯลฯ ได้อย่างอิสระ

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

• อยากแนะนำอย่างยิ่งให้ไปดูบรรยายของ Rich Hickey โดยเฉพาะช่วงแรก ๆ สำหรับฉัน การได้ดูบรรยายแบบนั้นทำให้มุมมองต่อการเขียนโปรแกรมเปลี่ยนไปอย่างสิ้นเชิง

  • สำหรับฉัน บรรยายของ Rich Hickey มีอิทธิพลมากที่สุดพอ ๆ กับ “Programming Perl” ของ Larry Wall

  • ฉันแทบอยากจะแซวว่าให้ข้ามบรรยาย “Simple made easy” ไปได้เลย เพราะตลอด 10 ปีที่ผ่านมา วิทยากรตามงานคอนเฟอเรนซ์แทบทุกคนยกมาพูดกันจนกลายเป็นคำคมซ้ำ ๆ ไปแล้ว ส่วนตัวฉันชอบ “Hammock driven development” มากกว่า แต่ก็ยังไม่ถึงขั้นจะแนะนำในบริษัทได้

• เสียดายที่ Abdulaziz เงียบหายไปหลังกลับคูเวต เขาเป็นอินเทิร์น Maxine VM ในปี 2009 และเป็นคนที่ดีมาก บทความนั้นเป็นของล้ำค่าจริง ๆ

  • ฉันก็เสียดายเหมือนกัน แต่ดูเหมือนว่าเมื่อไม่นานมานี้เขาเปิดร้านเบเกอรีและธุรกิจกำลังไปได้ดี ถ้ามองแบบนั้นก็ถือว่ากำลังทำตามความฝันอยู่

• ไม่นานมานี้มี บทความดี ๆ เรื่อง interpreter แบบอิง closure เพื่อเร่งความเร็ว interpreter ฉันลองใช้เทคนิคนี้ทำ interpreter ของ brainfuck แบบง่าย ๆ ดู แล้วมันก็เร็วใช้ได้ คงไม่ได้มีโอกาสเอาไปใช้อย่างอื่น แต่การลองทำเป็นการทดลองก็มีประโยชน์มาก

  • ฉันสงสัยว่าระหว่าง array ของ closure กับ array ที่สลับกันระหว่าง function pointer กับ data มันต่างกันอย่างไร แบบหลังดูไม่ค่อยเป็นธรรมชาติในภาษาส่วนใหญ่และเหมาะกับภาษาอย่าง C มากกว่า อย่างไรก็ตาม ฉันคิดว่าถ้าเก็บ static function กับ data ไว้ใน array เดียวกัน มันน่าจะเป็นมิตรกับ cache มากกว่า

• อยากให้มีบทความแนวนี้สำหรับภาษาในระดับสูงกว่าอย่าง JavaScript หรือ .NET ผู้เขียนคนนี้ฉลาดมาก แต่เขาทำงานอยู่ในระดับที่ต่ำกว่า (หรือสูงกว่า?) ผู้ใช้ส่วนใหญ่มาก

• บทความอื่น ๆ ในบล็อกของเขาก็ยอดเยี่ยมมากเหมือนกัน

• เรื่อง micrograd: สงสัยว่ามีเอกสารเพิ่มเติมนอกจากซอร์สโค้ดใน GitHub repository หรือไม่

  • มี ซีรีส์ YouTube ของ Andrej Karpathy ที่พูดถึงกระบวนการพัฒนา micrograd

• พูดแบบคนที่ชอบเขานะ แต่บทความที่อยู่ตรงนี้ไม่ได้เกี่ยวกับ PL (ภาษาโปรแกรม) เองเลย และเกือบทั้งหมดเกี่ยวกับคอมไพเลอร์ (ยกเว้น garbage collector) แน่นอนว่าฉันก็ชอบคอมไพเลอร์ แต่ประเด็นนี้คนละเรื่องกับหัวข้อ PL

  • หรือเขาอาจหมายถึง programming language ในความหมายของการ implementation ก็ได้?