การเขียนโปรแกรม: เขียนโปรแกรมด้วยสิ่งที่น้อยกว่าความว่างเปล่า

• บทความนี้เป็นเรื่องเล่าเชิงเสียดสีในสถานการณ์สัมภาษณ์งาน ที่ผู้สมัครพยายามแก้โจทย์ FizzBuzz แบบง่าย ๆ ด้วยคอมบิเนเตอร์ฟังก์ชันบริสุทธิ์ที่อิงแคลคูลัสแลมบ์ดา
• ตัวเอกเริ่มต้นด้วย JavaScript แต่ค่อย ๆ นิยามคอมบิเนเตอร์ S, K, I และสร้างโครงสร้างพื้นฐานของภาษาใหม่ขึ้นมาด้วยตนเอง
• จากนั้นยังแทนค่าบูลีน ตัวเลข ลิสต์ และสตริงทั้งหมดด้วยคอมบิเนเตอร์ล้วน ๆ และใช้Y combinator เพื่อทำรีเคอร์ชัน
• ท้ายที่สุดเขาสร้าง FizzBuzz แบบ point-free ได้สำเร็จอย่างสมบูรณ์ แต่โค้ดก็ขยายตัวจนอยู่ในระดับที่มนุษย์แทบไม่อาจเข้าใจได้
• บทความนี้สำรวจแก่นแท้ของภาษาโปรแกรมและความสุดขั้วของการนามธรรมอย่างมีอารมณ์ขัน พร้อมสะท้อนการเสียดสีตัวเองในวัฒนธรรมนักพัฒนา

---

การเริ่มต้นของการสัมภาษณ์: FizzBuzz และคอมบิเนเตอร์

• เรื่องเริ่มจากฉากที่ผู้สัมภาษณ์ Dana ขอให้ผู้สมัครแก้โจทย์ FizzBuzz
  • แต่แทนที่จะใช้ลูปทั่วไป ผู้สมัครกลับเริ่มจากการนิยามคอมบิเนเตอร์ S และ K เพื่อแก้ปัญหา
  • Dana รู้สึกงุนงง แต่ผู้สมัครก็พูดว่า “ขออีกนิดเดียว” แล้วเดินหน้าต่อ
• ผู้สมัครนิยามคอมบิเนเตอร์หลากหลายตัว เช่น I, B, C, W, T และใช้สิ่งเหล่านี้เป็นองค์ประกอบพื้นฐานของภาษาใหม่
  • คอมบิเนเตอร์แต่ละตัวทำหน้าที่แทนแนวคิดหลักของแคลคูลัสแลมบ์ดา เช่น การประกอบฟังก์ชัน การสลับอาร์กิวเมนต์ และการประยุกต์ใช้กับตัวเอง
  • ในคอมเมนต์ของโค้ดยังมีชื่อเล่นของคอมบิเนเตอร์อย่าง “Bluebird, Cardinal, Warbler, Thrush” ปรากฏอยู่

การนิยามบูลีนและตัวเลข

• ผู้สมัครนิยาม TRUE, FALSE, NOT ด้วยคอมบิเนเตอร์ล้วน ๆ เพื่อสร้างตรรกะบูลีนขึ้นมา
  • Dana ถามว่า “นี่แคลคูลัสแลมบ์ดาหรือเปล่า” แต่ผู้สมัครตอบว่า “แคลคูลัสแลมบ์ดามันเทอะทะเกินไป”
• จากนั้นจึงนิยาม ZERO, SUCC, PRED, IS_ZERO เพื่อประกอบเป็นระบบตัวเลข (Church numeral)
  • SUCC คือฟังก์ชันตัวถัดไป, PRED คือฟังก์ชันตัวก่อนหน้า และ DECREMENT คือการลดค่าที่จะไม่ลดต่ำกว่า 0
  • มีการนิยามตัวเลขตั้งแต่ ONE ถึง TEN ไล่ตามลำดับ

รีเคอร์ชันและ Y combinator

• ผู้สมัครนิยามฟังก์ชัน ADD แล้วค่อย ๆ แปลงมันให้อยู่ในรูปแบบ point-free
  • เขานิยาม ADD_MAKER แล้วห่อมันด้วยY combinator เพื่อให้เกิดรีเคอร์ชันได้
  • Dana ทักว่า “ใน JavaScript ก็ทำรีเคอร์ชันได้อยู่แล้ว” แต่ผู้สมัครตอบว่า “อีกเดี๋ยวมันก็จะไม่ใช่ JavaScript แล้ว”
• เมื่อเกิด stack overflow จากการประเมินผลแบบ eager ของ JavaScript ผู้สมัครจึงนำโค้ดไปรันบนอินเทอร์พรีเตอร์ JS แบบ “lazy” ชื่อ Skoobert
  • ผลลัพธ์คือสามารถพิมพ์ 3 ออกมาได้สำเร็จ

เลขคณิต ลิสต์ และสตริง

• ผู้สมัครอิมพลีเมนต์การคำนวณอย่าง SUBTRACT, MULTIPLY, MOD, DIVIDE ทั้งหมดบนฐานคอมบิเนเตอร์
  • แต่ละการดำเนินการถูกประกอบขึ้นจากการเชื่อม IS_ZERO, PRED, SUCC และส่วนอื่น ๆ แบบรีเคอร์ซีฟ
• ต่อมาเขานิยาม CONS, FIRST, REST, EMPTY เพื่อสร้างโครงสร้างลิสต์
  • รวมถึงอิมพลีเมนต์โอเปอเรชันเชิงฟังก์ชันระดับสูงอย่าง MAP, FOLD, RANGE, CONCAT ทั้งหมดในรูปคอมบิเนเตอร์
• เพื่อแสดงลิสต์ออกมาเป็นสตริง เขาเขียนฟังก์ชัน renderList และ showLines
  • ส่วน Dana ดูเหมือนจะยอมแพ้ไปแล้วและไม่ตอบสนองอะไรอีก

การประกอบอักขระและสตริง

• ผู้สมัครนิยามรหัสอักขระตั้งแต่ 1 ถึง 9 และต่อยอดเป็นหลักสิบ โดยใช้คอมบิเนเตอร์
  • ตั้งแต่ CHAR_A ถึง CHAR_Z และ CHAR_0 ถึง CHAR_9 ล้วนถูกแทนด้วยการประกอบเชิงตัวเลข
• ผ่านฟังก์ชัน ARRAY เขาแปลงสตริงเป็นลิสต์ แล้วสร้าง FIZZ, BUZZ, FIZZBUZZ
  • จากนั้นใช้ฟังก์ชัน extractString เพื่อแปลงลิสต์กลับเป็นสตริงจริง
  • ผลลัพธ์ที่แสดงบนคอนโซลคือ "fizzbuzz"

การแปลงจากตัวเลขเป็นสตริง

• มีการนิยาม NUMBER_TO_DIGIT_LIST สำหรับแปลงตัวเลขเป็นลิสต์ของหลัก และ NUMBER_TO_STRING สำหรับแปลงลิสต์นั้นเป็นสตริง
  • ใช้ DIVIDE, MOD, TEN และองค์ประกอบอื่น ๆ เพื่อแยกแต่ละหลักออกมา
  • จากนั้นแมปอักขระตัวเลขผ่านลิสต์ DIGITS_NUMERAL
• กระบวนการนี้ทำให้การแปลง ตัวเลข → อักขระ → สตริง เป็นไปได้อย่างสมบูรณ์ภายในระบบคอมบิเนเตอร์เดียวกัน

การทำ FizzBuzz ให้สมบูรณ์

• มีการนิยาม FIFTEEN และ ONE_HUNDRED แล้วใช้ MAP กับ RANGE เพื่อสร้างลิสต์ตั้งแต่ 1 ถึง 100
  • สำหรับแต่ละตัวเลข จะตรวจสอบว่าเป็นพหุคูณของ 3, 5 หรือ 15 เพื่อพิมพ์ "Fizz", "Buzz", "FizzBuzz" หรือสตริงของตัวเลขนั้น
  • จากนั้นแสดงผลลัพธ์สุดท้ายด้วย showLines(extractString)(FIZZBUZZ_RESULT)
• Dana ถามว่า “ตอนนี้พอใจหรือยัง” แต่ผู้สมัครกลับลบนิยามตัวแปรทั้งหมดออก แล้วเขียนโค้ดใหม่ด้วยคอมบิเนเตอร์บริสุทธิ์เพียงอย่างเดียว
  • ผลที่ได้คือนิพจน์ขนาดมหึมาที่ประกอบด้วย S และ K เท่านั้น ยาวหลายพันบรรทัด

บทสรุปและความหมาย

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

[GN⁺]

ความเห็นจาก Hacker News

• ดูเหมือนหลายคนจะคิดว่า “นี่มันอะไรกันแน่?” เลยขอลองอธิบายใจความของ combinator
  combinator คือฟังก์ชันที่ไม่เปลี่ยนแปลงสถานะส่วนกลางและไม่ capture ตัวแปรภายนอก ถ้าให้พารามิเตอร์เดิมก็จะได้ผลลัพธ์เดิมเสมอ และไม่ส่งผลใด ๆ กับส่วนอื่นของระบบ
  เมื่อนำฟังก์ชันบริสุทธิ์แบบนี้มาประกอบกัน ก็จะได้ combinator ตัวใหม่ กล่าวคือ การ compose ฟังก์ชันบริสุทธิ์ก็ยังคงเป็นฟังก์ชันบริสุทธิ์อยู่
  ฟังก์ชันพวกนี้เขียนด้วย assembly หรือ C ก็ได้ไม่ยาก ตัวอย่างเช่น ถ้า implement S และ K ตรง ๆ บน x64 แล้วคอมไพล์ Common Lisp แบบอิง combinator ลงไป ข้างล่างสุดก็เท่ากับว่า Lisp รันอยู่บนฟังก์ชัน assembly แค่สองตัว
  ประสิทธิภาพอาจไม่ดีนัก แต่ถ้าสร้าง inline combinator สำหรับแพตเทิร์นที่ใช้บ่อยสักไม่กี่ร้อยแบบแล้วตั้งชื่อให้ มันก็จะกลายเป็น “เครื่องจักร” ที่ใช้งานได้จริงพอสมควร
  โครงสร้างแบบนี้ยังคล้ายกับ Forth ที่หวาดกลัว mutation, bytecode VM, หรือ CPU ที่เรียก combinator ว่า “คำสั่ง”
  ท้ายที่สุด combinator อาจเรียกได้ว่าเป็น การแสดงออกของวิทยาการคอมพิวเตอร์ประยุกต์ ที่พยายามไม่สนใจรายละเอียดการ implement ให้มากที่สุด เพราะอย่างนั้นจึงอาจบอกได้ว่ามันเรียบง่ายกว่า lambda calculus
  ถ้า implement lambda calculus ด้วย combinator ไม่กี่ตัว แล้ววาง Lisp ไว้ข้างบน งานที่ผูกกับเครื่องซึ่งต้องทำอยู่ก้นสแตกก็จะลดลงอย่างมาก

  • รู้สึกเหมือนต้องมีฟังก์ชันสักตัวที่เรียกตัวเองจากที่ไหนสักแห่งแล้วได้รับ seed round มา
  • ตอนเป็นนักเรียนผมเคยทำอะไรคล้าย ๆ กันมาแล้ว (ไม่ใช่ Lisp แต่เป็นภาษาง่าย ๆ ที่ macro expand ไปเป็น lambda calculus) การที่สร้างทุกอย่างได้ด้วยแค่ S กับ K นั้น ช็อก มาก แต่ก็ทำให้ประหลาดใจพอ ๆ กันว่ามันไม่มีประสิทธิภาพขนาดไหน อย่างไรก็ดี พอชุดคำสั่งใหญ่ขึ้น สถานการณ์ก็ดีขึ้นมาก
  • ในทางทฤษฎีทำได้ทั้งหมดนั่นแหละ แต่ในทางปฏิบัติควรเลือก รากฐานการคำนวณที่ใช้งานได้จริง มากกว่าการ rewrite กราฟ เว้นแต่ว่าคุณกำลังทดลองขอบเขตของความสามารถในการคำนวณ ไม่อย่างนั้นมันก็แทบจะเป็นแค่ลูกเล่นในงานปาร์ตี้ แถมการแทนค่าตัวเลขก็เป็นปัญหาด้วย อย่างน้อยต้องใช้จำนวนเต็มแบบ two’s complement กับตัวทำลายที่มีประสิทธิภาพถึงจะน่าทึ่งจริง
  • สงสัยว่ามี Lisp ที่ implement อยู่บน combinator แบบนี้จริงไหม ถ้ามีก็น่าจะพอร์ตสนุกทีเดียว

• let A = (x) => (y) => (z) => x(z)(y((w) => z))
  

  แค่เอาสิ่งนี้ไปประกอบกันไม่กี่ครั้งก็พอ

  let K = A(A(A))(A(A(A))(A)(A)(A)(A)(A);
  let S = A(A(A(A)(A(A)(A(A)))(A(A(A(A)((A(A)))))))(A)(A);
  

  “ฉันไม่มีวันใช้ lambda calculus หรอก มันเป็น ภาษาที่พองเกินเหตุ”
  แต่จริง ๆ แล้ว combinatory logic พองกว่าอีก ต้องใช้บิตมากกว่าเพื่อแทนโปรแกรมเดียวกัน
  ตรงกันข้าม lambda calculus กลับเป็นหนึ่งใน ภาษาที่กระชับที่สุด
  แม้แต่ในภาษา eager อย่าง JavaScript ก็ทำให้เป็น lazy ได้ด้วยการห่ออาร์กิวเมนต์ด้วย lambda หลอก ๆ ดูตัวอย่างได้ที่ JS BLC interpreter นี้
  งานวิจัยที่เกี่ยวข้องดูได้ใน PDF นี้ และ ตัวอย่าง IOCCC

  • จุดที่น่าสนใจคือ interpreter ของ lambda calculus ที่เร็วที่สุดบางตัว (เช่น uni.c) ลงท้ายก็แปลง lambda expression ไปเป็น combinatory logic เพื่อคำนวณอยู่ดี เพียงแต่ใช้ basis ที่ใหญ่กว่า S, K
  • “bloated language” หมายถึงภาษาที่มีฟีเจอร์เกินจำเป็นมากมาย เช่น C++ อาจเขียนโค้ดสั้นกว่า C ได้ แต่ก็เป็น ภาษาที่ซับซ้อนกว่า มาก
  • พอมองโค้ดบล็อกนั้นแล้ว เสียงที่หลุดออกจากปากผมแทบจะตรงกับรายการอาร์กิวเมนต์เลย
  • ดูเหมือนนิยามของ K กับ S จะมีวงเล็บผิด เวอร์ชันที่แก้แล้วคือ

    let K = A(A(A))(A(A(A))(A)(A)(A)(A)(A));
    let S = A(A(A(A)(A(A)(A(A)))(A(A(A(A)(A(A)))))))(A)(A);
    

    และการทำให้ภาษา eager กลายเป็น lazy ก็ทำได้ประมาณนี้

    let A = x => y => z => () => x()(z())(y()(w => z()));
    

  • เกิดคำถามว่า “w คืออะไรนะ?”

• “รู้จัก FizzBuzz ไหม?”
  “แน่นอนสิ เอาแบบ code golf 10 ตัวอักษร, แบบ 12 บรรทัดที่จูเนียร์ก็เข้าใจได้, หรือแบบเพี้ยนสุด ๆ เอาไว้ โชว์ความรู้ประหลาด ดีล่ะ?”

  • เห็นแล้วผมเลยลองทำ FizzBuzz ที่เร็วที่สุด บน C64 BASIC ดู เสียเวลาช่วงเช้าอย่างสนุกสนาน
    ลิงก์ผลลัพธ์

• คำอธิบาย combinator logic นี่เท่มาก สไตล์การเขียนทำให้นึกถึงซีรีส์นี้

  • จะว่าเป็นคำอธิบายก็คงไม่เชิง มันใกล้กับ การแสดงโชว์ให้ดู มากกว่า ถึงอย่างนั้นก็ยังน่าประทับใจทีเดียว
  • ดูเหมือนว่าจะได้แรงบันดาลใจจากซีรีส์นั้นแน่ ๆ น่าจะดีกว่านี้ถ้ามีการเอ่ยถึงชื่อผู้เขียน
  • น่าเสียดายที่ในสหราชอาณาจักรถูกบล็อกการเข้าถึงเพราะ Online Safety Act

• ทำให้นึกถึงบทความ “FizzBuzz in TensorFlow” ที่เคยอ่านมาก่อน
  ลิงก์

  • อย่างน้อยบทความนี้ก็ยังพอตามทัน ซึ่งดีมาก

• กรอบแบบ การสัมภาษณ์เขียนโปรแกรม นี้ดูจะผิด ๆ ไปหน่อย
  จุดประสงค์ของการสัมภาษณ์คือ (1) ตรวจสอบความรู้ด้านการเขียนโปรแกรมของผู้สมัคร และ (2) ดูความเข้ากันได้กับ วัฒนธรรมการเขียนโปรแกรมของบริษัท
  ตัวอย่างเช่น ถ้ากำลังรับตำแหน่ง JavaScript แต่ผู้สมัครหมกมุ่นกับ combinatory logic อย่างลึกมาก ก็มีโอกาสสูงว่าจะไม่เข้ากับวัฒนธรรม ดังนั้นจะไม่ผ่านก็คงไม่แปลก

  • น่าจะอ้างอิงซีรีส์นี้ แต่ในต้นฉบับไม่ได้ระบุชัดเจน
  • บางครั้งก็รู้สึกว่าคนคอมเมนต์ใน HN เป็นพวก คนที่ลืมความสนุกไปแล้ว
  • การเน้นความหลากหลายของการเขียนโปรแกรมนั้นถูกต้อง แต่ก็เป็นเพียงรูปแบบหนึ่งของการคัดหาความเชี่ยวชาญใน ecosystem เฉพาะทางเท่านั้น ส่วนใหญ่แล้วเป็นการเลือกเพื่อรับมือกับ legacy code หรือใช้ ecosystem ที่มีอยู่เดิม
  • คำพูดอย่าง “IQ ต่ำก็ตก” ฟังดูตลก แต่สุดท้ายถ้าได้เงินมากพอ คุณก็ปรับตัวเข้ากับสไตล์แบบ OOP/FP/FRP ไหนก็ได้
  • ในโลกความจริงแทบไม่มีการสัมภาษณ์ในอุดมคติแบบนี้ ส่วนใหญ่คือ คนสัมภาษณ์ที่ผิดหวัง พยายามยัดเยียดโลกทัศน์ของตัวเอง และงานจริงก็แทบไม่เกี่ยวอะไรกับสิ่งที่ถามในสัมภาษณ์เลย

• ถึงเวลาต้องจดจำ Moses Schönfinkel แล้ว
  เขาเป็นคนคิดค้น combinatory logic ตอนเป็นศิษย์ของ Hilbert ในปี 1920 หลังจากกลับรัสเซียเขาป่วยทางจิต และเสียชีวิตอย่างยากจนในมอสโก ตาม Wikipedia บอกว่าต้นฉบับงานวิจัยของเขาถูกเพื่อนบ้านเอาไปเผาเป็นเชื้อเพลิงทำความร้อน

• โค้ดบล็อกสุดท้ายใหญ่จนต้องมีสกรอลล์ (166KB)
  S กับ K เป็น ฟังก์ชันแบบเคอร์รี ที่รับอาร์กิวเมนต์ครั้งละหนึ่งตัว
  รายละเอียดดูได้ในคำตอบบน StackOverflow นี้

  • ตอนเลื่อนลงมาแล้วเห็น syntax highlighting ยอมแพ้ไปกลางทาง นั่นแหละที่ขำที่สุด

• ชอบชื่อแบบนกอย่าง “Bluebird, cardinal, warbler, thrush” มาก อยากเอามาใช้เป็น ธรรมเนียมการตั้งชื่อ ใหม่
  “Barendregt ไง Church มันแมสเกินไปแล้ว”
  “เดี๋ยวมันก็จะไม่ใช่ JavaScript อีกต่อไป”
  ให้ความรู้สึกเหมือน Douglas Adams มาสอน SICP

  • ชื่อนกพวกนั้นมาจาก 『To Mock a Mockingbird』 ของ Smullyan ในนั้นยังมีนกอีกเยอะมาก

• “นั่นคือ... Y combinator เหรอ?”
  “ใช่แล้ว ต้องใช้ถ้าจะทำ recursion”
  เกร็ดน่าสนุก: fixed-point combinator มีอยู่ไม่จำกัดจำนวน กล่าวคือ คุณสามารถทำ recursion ได้อีกนับไม่ถ้วนโดยไม่ต้องใช้ Y combinator