06 · ภาษาและคอมไพเลอร์
ชั้นนี้คือจุดที่คำสั่งเลิกพูดกับเครื่องจักรและหันมาพูดกับคน — โปรแกรมถูกเขียนขึ้นเพื่อให้คนอ่าน
อะไรทำให้ข้อความมีความหมายต่อเครื่องจักร?
งานที่ประเมินไว้หกเดือนใช้เวลาจริงกว่าสองปี ทีมของ John Backus ที่ IBM เริ่มทำ FORTRAN ด้วยตัวเลขนั้น และในบันทึกประวัติโครงการของเขาเอง Backus เล่าว่าหกเดือน "ยังคงเป็นระยะเวลาที่คาดไว้จนกว่างานจะเสร็จจริง ซึ่งเกิดขึ้นอีกกว่าสองปีให้หลัง ในเดือนเมษายน 1957" (remained the interval-to-completion until it actually was completed over two years later, in April 1957) ความล่าช้าไม่ใช่ส่วนที่น่าสนใจ ส่วนที่น่าสนใจคือสิ่งที่ทุกคนคาดว่าผลลัพธ์จะเป็น Backus เล่าว่า "ยากที่จะสื่อ ... ถึงความแรงของความคลางแคลงใจต่อ 'automatic programming'" (it is difficult to convey ... the strength of the skepticism about 'automatic programming') และต่อ "ความสามารถของมันในการผลิตโปรแกรมที่มีประสิทธิภาพ" (its ability to produce efficient programs) เป้าหมายที่ทีมของเขาประกาศไว้มีแค่ "ผลิตโปรแกรมที่มีประสิทธิภาพเกือบเท่าโค้ดที่เขียนด้วยมือ" (produce programs almost as efficient as hand coded ones) (Backus, The History of FORTRAN I, II, and III) เกือบ. ข้อสมมติของวงการตอนนั้นคือเครื่องจักรอ่านสัญกรณ์ของมนุษย์แล้วผลิตโค้ดที่ดีไม่ได้ และข้อสมมตินั้นไม่โง่เลย ไม่มีอะไรในเรื่องความหมายที่ดูเป็นกลไก
สิ่งที่ทำให้เรื่องนี้กลายเป็นกลไกได้ คือการผ่าความหมายออกเป็นสองท่อน ไวยากรณ์ (syntax) ถามว่าข้อความมีรูปถูกต้องหรือไม่ ความหมาย (semantics) ถามว่ามันทำอะไร สองคำถามนี้ไม่ใช่คำถามคนละคำตอบ แต่คนละชนิด Backus บรรยาย syntax ของภาษาพีชคณิตสากลที่เสนอกันในปี 1959 ด้วยสัญกรณ์ของกฎและทางเลือก Peter Naur ดัดแปลงมันไปใช้ในรายงาน ALGOL 60 และจดหมายของ Donald Knuth ถึง CACM ในปี 1964 เสนอชื่อที่มันแบกมาจนถึงวันนี้ คือ Backus–Naur Form (Knuth, 1964) พอมีไวยากรณ์รูปนัย คำถามว่า "โปรแกรมนี้ถูกต้องหรือไม่" ก็พ้นจากดุลพินิจ กลายเป็นข้อตัดสินที่โปรแกรมทำเองได้ ALGOL 60 คือบทพิสูจน์ และคำตัดสินของ Tony Hoare คือประโยคที่ถูกอ้างมากที่สุดในวงการออกแบบภาษา "นี่คือภาษาที่ล้ำยุคของมันมากจนไม่ใช่แค่ก้าวหน้ากว่ารุ่นก่อนหน้า แต่ยังก้าวหน้ากว่ารุ่นต่อๆ มาเกือบทั้งหมดด้วย" (Here is a language so far ahead of its time, that it was not only an improvement on its predecessors, but also on nearly all its successors) — มาจากปาฐกถาปี 1973 เรื่อง "Hints on Programming Language Design" ไม่ใช่ปาฐกถา Turing อย่างที่มักอ้างกันผิด
ความหมายไม่ยอมให้จัดการแบบเดียวกัน คอมไพเลอร์จึงไม่ไขมัน แต่พามันลงบันไดทีละขั้นเล็กๆ ที่แม่นยำ คอมไพเลอร์คือหอคอยซ้อนอยู่ในหอคอย การวิเคราะห์คำศัพท์ (lexical analysis) แปลงตัวอักษรเป็นคำ parsing แปลงคำเป็นต้นไม้ที่สะท้อนไวยากรณ์ การวิเคราะห์ความหมาย (semantic analysis) เติมลงบนต้นไม้นั้นว่าแต่ละชื่ออ้างถึงอะไร และการดำเนินการใดได้รับอนุญาต ต้นไม้กลายเป็นตัวแทนกลาง (intermediate representation) ที่ไม่ผูกกับภาษาใดหรือเครื่องใด การเพิ่มประสิทธิภาพ (optimization) เขียนมันใหม่ให้ถูกลงโดยความหมายไม่เปลี่ยน และการสร้างโค้ด (code generation) ปล่อยชุดคำสั่งของบทที่ 04 ออกมา ทุกขั้นมีอยู่เพราะมันยื่นตัวแทนที่ทำให้งานของขั้นถัดไปง่าย — นั่นคือวิทยานิพนธ์ทั้งเล่มของหนังสือนี้ แสดงย่อส่วนอยู่ในโปรแกรมเดียว ตัวแทนกลางคุ้มค่าตัวด้วยเลขคณิตล้วนๆ ไม่มีมัน การรองรับ n ภาษาบน m เครื่องต้องใช้คอมไพเลอร์ n × m ตัว มีมัน ใช้ n + m
ภาษาที่สร้างบนกลไกนั้นให้ชุดวิธีตั้งชื่อแก่สิ่งต่างๆ — ฟังก์ชัน, ชนิดข้อมูล (type), มอดูล (module), อ็อบเจกต์ (object) — แต่ละอย่างมีไว้ให้ผู้อ่านเพิกเฉยต่อบางอย่างได้ ตัวอย่างที่กระชับที่สุดคือ LISP เดือนเมษายน 1960 John McCarthy ตีพิมพ์เปเปอร์ที่นิยามการคำนวณบนนิพจน์เชิงสัญลักษณ์ (symbolic expressions) รวมถึงฟังก์ชันชื่อ eval ที่อธิบายว่าการประเมินนิพจน์ใดๆ ในภาษานี้หมายความว่าอย่างไร (Recursive Functions of Symbolic Expressions, CACM 3, no. 4) มันคือคณิตศาสตร์ ตั้งใจให้อ่าน Steve Russell เอา eval ไปคอมไพล์ด้วยมือลงเป็นโค้ดเครื่อง IBM 704 (McCarthy, History of Lisp) และนิยามของภาษาก็กลายเป็นอินเทอร์พรีเตอร์ (interpreter) ของภาษานั้นเอง นั่นคือไอเดียโปรแกรมที่เก็บในหน่วยความจำ (stored program) จากบทที่ 04 ถึงกำหนดจ่ายคืน เพราะโปรแกรมคือข้อมูล คำอธิบายของภาษาจึงเป็นโปรแกรมที่รันภาษานั้นได้
Type คือกลไกตั้งชื่อที่คมที่สุด เพราะ type คือคำสัญญาที่เครื่องจักรตรวจได้ ประกาศว่าฟังก์ชันหนึ่งรับจำนวนเต็มและคืนสตริง คือข้อกล่าวอ้างครอบคลุมการรันทุกครั้งที่เป็นไปได้ ตรวจสอบเสร็จก่อนการรันครั้งแรกจะเกิดขึ้นด้วยซ้ำ — เป็นส่วนเดียวของการเขียนโปรแกรมที่คุณได้การรับประกัน (guarantee) ไม่ใช่ผลการเทสต์ การรับประกันนี้แคบแต่จริง Gao, Bird และ Barr หยิบบั๊ก JavaScript ที่เปิดเผยต่อสาธารณะ เช็คเอาต์โค้ดช่วงก่อนแก้บั๊กแต่ละตัว ใส่ type annotation ด้วยมือ แล้วถามว่าตัวตรวจชนิด (type checker) จะโวยไหม ทั้ง Flow และ TypeScript จับได้ 15 เปอร์เซ็นต์ (To Type or Not to Type, ICSE 2017) อ่านให้ละเอียด นี่ไม่ใช่ "15 เปอร์เซ็นต์ของบั๊กเป็นข้อผิดพลาดเรื่อง type" แต่คือ 15 เปอร์เซ็นต์ของบั๊กที่รอดการเทสต์ การรีวิว และการปล่อยใช้งานจริงมาแล้ว ดันไอเดียนี้ไปไกลพอ มันเลิกเป็นเรื่องบั๊ก Curry–Howard correspondence ที่ Haskell Curry สังเกตเห็นในทศวรรษ 1930 และ William Howard ระบุไว้ในต้นฉบับปี 1969 ชื่อ "The Formulae-as-Types Notion of Construction" บอกว่า type คือ ข้อเสนอ (proposition) และโปรแกรม คือ บทพิสูจน์ของมัน type checker คือเครื่องพิสูจน์ทฤษฎีบทอัตโนมัติตัวจิ๋วที่โปรแกรมเมอร์ส่วนใหญ่ใช้ทุกวันโดยไม่ทันสังเกต
แล้วทำไมถึงมีภาษามากมายขนาดนี้ ฐานข้อมูล HOPL ที่ดูแลมาตั้งแต่ปี 1995 นับได้ 8,945 ภาษา ณ เดือนสิงหาคม 2026 การแตกแขนงนี้ไม่ใช่ความสูญเปล่า ภาษาหนึ่งคือการเดิมพันว่าความผิดพลาดแบบไหนคุ้มที่จะป้องกัน และการทำซ้ำแบบไหนคุ้มที่จะตั้งชื่อ การเดิมพันนั้นต่างกันจริงระหว่างเคอร์เนลของระบบปฏิบัติการ โมเดลเชิงสถิติ และหน้าเว็บ Alan Perlis วางบททดสอบที่ใช้ได้จริงไว้ใน Epigrams on Programming ปี 1982 "ภาษาที่ไม่กระทบวิธีคิดของคุณเกี่ยวกับการเขียนโปรแกรม ก็ไม่คุ้มที่จะรู้จัก" (A language that doesn't affect the way you think about programming, is not worth knowing) สิ่งที่ไม่รอดมาคือความกลัวของปี 1957 คอมไพเลอร์เอาชนะแอสเซมบลีฝีมือดีที่เขียนด้วยมือเป็นเรื่องปกติไปแล้ว และตอนนี้ superoptimizer ก็เอาชนะคอมไพเลอร์อีกที: STOKE ค้นแบบสุ่มจากโค้ดที่ยังไม่ถูกเพิ่มประสิทธิภาพ หารูปแบบเขียนใหม่ที่ความหมายเท่ากัน แล้วให้ผลเทียบเท่าหรือดีกว่าผลลัพธ์ที่ดีที่สุดของคอมไพเลอร์ระดับโปรดักชัน (Schkufza, Sharma & Aiken, ASPLOS 2013) ทีมของ Backus ขอแค่ เกือบ ดีเท่าโค้ดมือ และแพ้เดิมพันนั้นในทิศทางที่น่ายินดีที่สุด
คนบนชั้นนี้มีนิสัยหันกลับมาโจมตีงานของตัวเอง Backus รับ Turing Award ในปี 1977 แล้วใช้ปาฐกถานั้นถล่มโมเดลที่ FORTRAN ปักหลักไว้ ตั้งชื่อว่า "Can Programming Be Liberated from the von Neumann Style?" — ลงใน CACM เดือนสิงหาคมปีถัดมา ระบบ A-0 ของ Grace Hopper ปี 1951–52 มักถูกเรียกว่าคอมไพเลอร์ตัวแรก จริงๆ มันทำงานใกล้เคียงตัวโหลด (loader) มากกว่า งานที่ส่งผลกว่าคือ FLOW-MATIC คำกริยาคล้ายภาษาอังกฤษของมันผ่านเข้าไปใน COBOL แทบทั้งดุ้น และวางข้อความที่คนอ่านออกไว้ในการเขียนโปรแกรมเชิงพาณิชย์อย่างถาวร เธอเกษียณจากกองทัพเรือสหรัฐฯ ในปี 1986 ด้วยยศพลเรือตรี ติดนิสัยยื่นเส้นลวดยาวเกือบหนึ่งฟุตให้แขกที่มาเยี่ยม — ระยะทางที่แสงเดินทางได้ในหนึ่งนาโนวินาที — เพื่อให้เลิกคิดว่าเวลาที่เสียไปไม่มีต้นทุน
เชื่อมโยง
ชั้นล่างของบทนี้ บทที่ 04 มอบชุดคำสั่งที่ back end ปล่อยโค้ดออกไปหา และบทที่ 05 มอบ abstraction ของ process ที่โปรแกรมคอมไพล์แล้วถูกโหลดเข้าไปอยู่ บทที่ 01 กำหนดเพดาน เพราะปัญหาการหยุด (halting problem) ตัดสินไม่ได้ คอมไพเลอร์จึงตัดสินในกรณีทั่วไปไม่ได้ว่าการเพิ่มประสิทธิภาพหนึ่งๆ ปลอดภัยทุกกรณีหรือไม่ optimizer ตัวจริงจึงถูกออกแบบมาให้ระมัดระวังไว้ก่อน ชั้นบน บทที่ 07 ถามว่ากลไกตั้งชื่อเหล่านี้ตัวไหนทำให้ระบบใหญ่เปลี่ยนแปลงได้ตลอดหลายปี และบทที่ 12 เปิดความเป็นไปได้ว่าสัญกรณ์ถัดไปที่คนใช้เขียนอาจไม่ใช่ภาษาโปรแกรมเลย
คำถามที่ยังเปิดอยู่
ถ้าโมเดลผลิตโค้ดที่ทำงานได้จากคำอธิบายภาษาอังกฤษ ภาษาโปรแกรมมีไว้ทำอะไร — ทำสเปก (specification) พิสูจน์ความถูกต้อง (verification) หรือแค่รีวิว? Type จับข้อบกพร่องจริงได้อย่างพิสูจน์แล้ว แล้วทำไมอุตสาหกรรมส่วนใหญ่ยังปฏิเสธมัน คำตอบที่ตรงไปตรงมาคือเรื่องหลักฐานหรือเรื่องต้นทุน? และภาษาที่ออกแบบมาให้โปรแกรมอ่านมากกว่าให้คนเขียน จะหน้าตาแบบไหน?
อ่านต่อ
- Alfred V. Aho, Monica S. Lam, Ravi Sethi & Jeffrey D. Ullman, Compilers: Principles, Techniques, and Tools, 2nd ed., Addison-Wesley, 2006 — หรือที่รู้จักกันในชื่อ "dragon book" ยังคงเป็นตำราอ้างอิงมาตรฐานสำหรับ pipeline ของคอมไพเลอร์
- John Backus, "The History of FORTRAN I, II, and III," ACM SIGPLAN Notices 13, no. 8 (1978) — เรื่องเล่าของผู้ก่อตั้งวงการที่พิสูจน์ให้คนที่ไม่เชื่อเห็นว่าตัวเองคิดผิด
- John McCarthy, "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I," Communications of the ACM 3, no. 4 (1960): 184–195 — ภาษาที่ถูกนิยามไว้ ไม่ได้ถูกทำให้ใช้งานได้จริง แต่สุดท้ายก็มีคนทำให้ใช้งานได้จริงอยู่ดี