Self Source Printing Program

เห็นเรื่อง Obfuscated C จาก blog คุณพูลลาภ แล้ว ทำให้นึกถึง brain teaser ข้อหนึ่งที่เคยเล่นกันสมัยเรียนตรี คือโปรแกรมที่ print source code ตัวเอง

เริ่มจาก พี่ปริญญาโทยกเอา Russel’s paradox มาเกริ่นก่อน ว่า logic ใดๆ ที่ย้อนเข้าหาตัวเองแบบนิเสธ จะกลายเป็น paradox (เรียกว่าเป็นความไม่สมบูรณ์ของระบบ) เช่น บอกว่า “ช่างตัดผมคนเดียวในหมู่บ้าน จะไม่โกนหนวดให้กับคนที่โกนหนวดเอง” เมื่อย้อนถามว่า “ถ้าเช่นนั้น ช่างตัดผมคนนี้ จะโกนหนวดตัวเองหรือเปล่า?” ก็จะหาคำตอบไม่ได้ทันที หรืออีกตัวอย่างหนึ่งคือ คำพูดที่ว่า “ผมโกหกเสมอ” เป็นจริงหรือเท็จ? เรื่องนี้ พอเข้าเนคเทค ก็มีน้องคนหนึ่งมาชวนคุยอีก คราวนี้โยงไปถึง Gödel ด้วย สนุกดีเหมือนกัน

สิ่งที่ Bertrand Russel เสนอคือ “ถ้า A เป็นเซ็ตของเซ็ตที่ไม่รวมตัวเอง ถามว่า จริงๆ แล้ว A รวมตัวเองหรือไม่?” หรือเขียนเป็นทางการหน่อยก็ “ถ้า A = { x | x ∉ x } ถามว่า จริงๆ แล้ว A ∈ A หรือไม่” ซึ่งตอบลำบาก เพราะถ้า A ∉ A ก็แปลว่า A สอดคล้องกับเงื่อนไขของเซ็ต และได้ว่า A ∈ A ในทางกลับกัน ถ้า A ∈ A ก็ขัดกับเงื่อนไขของเซ็ต ซึ่งหมายความว่า A ∉ A)

เกริ่นมาจนงงขนาดนี้ (เหมือนนักเล่นกล ต้องอ้างสิ่งลึกลับไว้ก่อน) แล้วก็ถามว่า “ถ้าเช่นนั้น โปรแกรมที่พิมพ์ซอร์สโค้ดตัวเองมีอยู่จริงหรือไม่?” กล่าวคือ สมมุติโปรแกรมที่ว่าคือ self.c มันควรทำเช่นนี้ได้ โดยห้ามอ่าน external input ใดๆ :

$ cc -o self self.c
$ ./self | diff -u - self.c
$ ./self > clone.c
$ cc -o clone clone.c
$ ./clone | diff -u - clone.c
$ ...

เขียนกันไปเขียนกันมา จะพบปัญหาไก่กับไข่อย่างแท้จริง แต่ก็มี trick บางอย่างทำให้ดิ้นออกมาได้ เรียกว่าได้แบบแฮ็กๆ โปรแกรมไม่ portable อะไร ใครอยากลองเขียนก็ลองดูได้ แต่ถ้าเขียน C program ที่ portable ได้ ช่วยบอกผมด้วย