นักพัฒนาคนหนึ่งสามารถสร้าง C compiler ที่ใช้งานได้จริงด้วยโค้ด Python เพียง 500 บรรทัดเท่านั้น โดยมี WebAssembly เป็นรูปแบบเอาต์พุต ความสำเร็จที่น่าประทับใจนี้ได้จุดประกายการอภิปรายในชุมชนโปรแกรมเมอร์เกี่ยวกับปรัชญาการออกแบบ compiler และการแลกเปลี่ยนระหว่างความเรียบง่ายของโค้ดกับฟังก์ชันการทำงาน
โปรเจกต์นี้แสดงถึงแนวทางมินิมัลลิสต์ในการสร้าง compiler โดยตัดฟีเจอร์ดั้งเดิมของ C หลายอย่างออกไปเพื่อมุ่งเน้นไปที่ฟังก์ชันหลัก compiler นี้รองรับเฉพาะชนิดข้อมูลจำนวนเต็มและการดำเนินการพื้นฐาน โดยจงใจตัดฟีเจอร์ที่ซับซ้อนออกไป เช่น pointers, structs, ขนาดข้อมูลแบบต่างๆ และการจัดการข้อผิดพลาดที่เหมาะสม เพื่อให้อยู่ในขีดจำกัดของจำนวนบรรทัดที่เข้มงวด
คุณสมบัติที่รองรับ
- รองรับเฉพาะประเภทข้อมูลจำนวนเต็ม
- การดำเนินการทางคณิตศาสตร์พื้นฐาน
- การเรียกใช้ฟังก์ชันและ stack frames
- ค่าคงที่สตริงผ่าน StringPool
- ตัวแปรท้องถิ่นและการควบคุมการทำงานพื้นฐาน
Single-Pass เทียบกับการออกแบบแบบหลายขั้นตอนแบบดั้งเดิม
การถกเถียงในชุมชนมุ่งเน้นไปที่การเลือกใช้แนวทาง single-pass compilation แทนที่จะเป็น pipeline แบบ lexer-parser-AST-emitter ที่เป็นแบบดั้งเดิม นักพัฒนาบางคนตั้งคำถามว่าแนวทางนี้เรียบง่ายกว่าจริงหรือไม่ โดยโต้แย้งว่าการสร้าง Abstract Syntax Tree (AST) อาจจะง่ายกว่าในการใช้งานจริงและจะช่วยให้สามารถทำการปรับปรุงประสิทธิภาพพื้นฐานผ่าน pattern matching ได้ อย่างไรก็ตาม คนอื่นๆ ชี้ให้เห็นว่าโค้ดที่มีบรรทัดน้อยกว่าไม่ได้หมายความว่าจะง่ายกว่าในการใช้งาน และแนวทาง single-pass ก็ช่วยลดความซับซ้อนในการจัดการ intermediate representations
การตัดสินใจทางเทคนิคที่สำคัญ
- สถาปัตยกรรมคอมพิวเตอร์แบบ stack-based (หลีกเลี่ยงความซับซ้อนของการจัดสรร register)
- รูปแบบเอาต์พุตเป้าหมายเป็น WebAssembly
- แนวทางการคอมไพล์แบบ single-pass
- การใช้งาน Python เพื่อลดโค้ดส่วนเสริมที่ซ้ำซาก
WebAssembly เป็นเป้าหมายที่ไม่ธรรมดา
การตัดสินใจเลือก WebAssembly แทนที่จะเป็น native machine code หรือ custom runtime ได้ดึงดูดความสนใจ ผู้เขียนยอมรับว่าการเลือกนี้เป็นเพื่อความสนุกสนานส่วนหนึ่ง แม้ว่าจะสร้างความท้าทายที่น่าสนใจก็ตาม instruction set แบบ stack-based ของ WebAssembly เข้ากันได้ดีกับการออกแบบแบบ stack-based ของ compiler แต่การขาด registers แบบดั้งเดิมและความซับซ้อนในการแบ่ง control flow ก็สร้างอุปสรรคในการใช้งานที่เป็นเอกลักษณ์
เทคนิคทางวิศวกรรมที่ชาญฉลาดและการแลกเปลี่ยน
compiler นี้ใช้เทคนิคประหยัดพื้นที่หลายอย่างที่เสียสละแนวปฏิบัติที่ดีแบบดั้งเดิมเพื่อความกระชับ ระบบ StringPool จัดการค่าคงที่แบบสตริงอย่างมีประสิทธิภาพ ในขณะที่การใช้ dataclasses ของ Python ช่วยลดโค้ดที่ซ้ำซากได้อย่างมาก ผู้เขียนจงใจเลือกที่จะคัดลอก intermediate representations แทนที่จะแก้ไข structures โดยแลกเปลี่ยนประสิทธิภาพหน่วยความจำกับความเรียบง่ายของโค้ด
dictionaries ของผมจะเป็น linked-list การค้นหา key จะกลายเป็น linear search... 500 บรรทัดถือว่าเข้มงวดมาก แต่ IOCCC ให้เทคนิคมากมายที่จะช่วยลดจำนวนบรรทัดลงได้
โครงสร้างข้อมูลหลัก
ValueRef: ตำแหน่งสำหรับจัดเก็บ/เรียกใช้ค่าต่างๆConst: ค่าคงที่เป็นตัวเลขจำนวนเต็มGlobalRef: ตำแหน่งส่วนกลางสำหรับค่าคงที่แบบสตริงNameRef: ชื่อที่มีค่า offset (สามารถซ้อนกันได้อย่างไม่จำกัด)TypeRef: ข้อมูลประเภทสำหรับค่าต่างๆAlloc/Free: การจัดการพื้นที่ stack
คุณค่าทางการศึกษาและความเชื่อมโยงทางภาษาศาสตร์
โปรเจกต์นี้ได้จุดประกายความสนใจในหมู่นักพัฒนาที่เพิ่งเริ่มต้นศึกษาการสร้าง compiler โดยบางคนสังเกตเห็นความเชื่อมโยงที่น่าประหลาดใจระหว่างการออกแบบ compiler และภาษาศาสตร์ ความสัมพันธ์นี้มาจากงานของ Noam Chomsky เกี่ยวกับ formal grammars สำหรับภาษาธรรมชาติ ซึ่งนักวิทยาศาสตร์คอมพิวเตอร์ได้นำมาปรับใช้สำหรับการออกแบบภาษาโปรแกรมในภายหลัง ทฤษฎี formal grammar ที่อธิบายโครงสร้างของภาษามนุษย์ให้รากฐานทางคณิตศาสตร์สำหรับการแยกวิเคราะห์ภาษาโปรแกรม
ความท้าทายและการตอบสนองของชุมชน
โปรเจกต์นี้ได้สร้างแรงบันดาลใจให้เกิดความท้าทายที่สนุกสนานในชุมชน รวมถึงข้อเสนอในการเขียน Python compiler ด้วย C เพียง 500 บรรทัด แม้ว่าจะเป็นไปได้ในทางเทคนิค แต่การใช้งานดังกล่าวจะต้องมีการประนีประนอมอย่างมาก รวมถึงการใช้ linear search algorithms แทน hash tables ที่มีประสิทธิภาพ และการจัดการข้อผิดพลาดที่น้อยที่สุด ความเห็นพ้องต้องกันคือแม้ว่าจะทำได้ แต่ compiler ที่ได้จะไม่สามารถใช้งานได้จริงสำหรับแอปพลิเคชันในโลกจริง
C compiler 500 บรรทัดนี้แสดงให้เห็นว่าผลลัพธ์ที่น่าประทับใจสามารถทำได้ด้วยข้อจำกัดที่เข้มงวด แม้ว่าผลิตภัณฑ์สุดท้ายจะเสียสละฟีเจอร์หลายอย่างที่ production compilers ต้องการก็ตาม มันทำหน้าที่เป็นแบบฝึกหัดทางการศึกษาที่ยอดเยี่ยมและเป็นการพิสูจน์แนวคิด แสดงให้เห็นว่าหลักการพื้นฐานของ compiler สามารถกลั่นให้เป็นโค้ดที่กะทัดรัดได้อย่างน่าประหลาดใจ