อย่ากังวลให้มากไป กับสแตกในฟังก์ชันเวียนเกิด

TECHJAM 2018 — Code Incubation #1

โดย monte-carlo

หนึ่งในไม่กี่เหตุผลที่โปรแกรมเมอร์หลายคนหลบเลี่ยงการเขียนฟังก์ชันเวียนเกิด (recursive function) คงหนีไม่พ้นความกังวลว่าจะไปทำให้สแตกล้น (stack overflow) เพราะโปรแกรมเรียกใช้งานฟังก์ชันซ้อนกันเป็นจำนวนมากเสียเกินกว่าที่ สแตกการเรียกฟังก์ชัน (call stack) จะรับไหว จนได้ผลลัพธ์อันน่ารำคาญใจออกมาเป็น Segmentation Fault ในที่สุด

แต่ความกังวลดังกล่าวก็ดูจะทุเลาลงไป เมื่อตัวแปลภาษา (compiler) ฉลาดขึ้นและสามารถรีดประสิทธิภาพของการเรียกฟังก์ชันสุดท้าย (tail call optimization, TCO) ให้กับฟังก์ชันเวียนเกิดที่เขียนมาอย่างเหมาะสม ซึ่งก็คือ ฟังก์ชันที่คืนค่าเป็นการเรียกฟังก์ชันซ้ำไปเรื่อยๆ โดยไม่มีการคำนวณอื่นใดมารบกวน นี่ทำให้ตัวแปลภาษาไม่จำเป็นต้องจองสแตกเพิ่มแต่อย่างใด หน้าที่ของโปรแกรมเมอร์ก็เหลือเพียงแค่การปรับปรุงโค้ดให้รองรับความสามารถดังกล่าวเท่านั้น

ตัวอย่างเช่นโค้ดต่อไปนี้ ที่จะคำนวณ f(n) = 1 + 2 + 3 + … + n โดยนำเทคนิค TCO เข้ามาช่วย

หากวาดภาพการทำงานของฟังก์ชันดังกล่าว เปรียบเทียบกันระหว่างก่อนและหลังทำ TCO ก็คงได้แผนภาพผลลัพธ์ประมาณนี้

จะเห็นว่า ก่อนการทำ TCO นั้น ฟังก์ชันดังกล่าวจะใช้สแตกขนาด O(n) และหลังจากทำ TCO ไปแล้วก็จะลดการใช้สแตกเหลือเพียง O(1) เท่านั้น ❤️

ข้อจำกัดสำคัญของเทคนิค TCO คือ ฟังก์ชันเวียนเกิดจะสามารถเรียกตัวเองได้เพียงครั้งเดียวตอนคืนค่าเท่านั้น แต่อัลกอริทึมในโลกจริงอาจถูกเขียนด้วยฟังก์ชันเวียนเกิดที่เรียกตัวเองซ้ำมากกว่าหนึ่งรอบ เช่น อัลกอริทึมการเรียงแบบเร็ว (quicksort) ที่มีหน้าตาเช่นนี้

นั่นหมายความว่าเราไม่สามารถทำ TCO กับฟังก์ชันเหล่านี้ได้ …

…

ซะที่ไหนกันหละ! เพราะเราสามารถออกแบบให้ฟังก์ชันเวียนเกิดใดๆ คืนค่าเป็นการเรียกตัวเองซ้ำได้เสมอ โดยฟังก์ชันที่เป็นเป้าหมายของเรานี้ จะรับตัวแปรแรกเป็นข้อมูลเพียงครึ่งเดียวของสิ่งที่ต้องทำ พร้อมห่อหุ้ม (closure) ข้อมูลครึ่งหลังไว้เป็นตัวแปรที่สอง ซึ่งถูกส่งต่อให้ตัวเองในอนาคตหยิบมาทำเมื่อพร้อมนั่นเอง

เทคนิคดังกล่าวเรียกว่า การส่งผ่านอย่างต่อเนื่อง (continuation-passing style, CPS) ซึ่งเราสามารถนำมาใช้ปรับโค้ด quicksort ให้อยู่ในรูปแบบดังกล่าวได้ดังนี้

เมื่อไล่การทำงานของมันก็จะได้ภาพประมาณ

แม้ฟังก์ชันดังกล่าวจะเป็น CPS และได้รับประโยชน์จาก TCO ที่คอยควบคุมขนาดของสแตกให้เป็น O(1) ก็ตาม แต่ถ้าสังเกตตัวแปร c ให้ดี จะพบว่ามันถูกห่อหุ้มซ้อนกันมากขึ้นเรื่อยๆ เหมือนงานที่ดองไว้ จนมีขนาดโตเป็น O(log n) ในที่สุด (คิดจากความซับซ้อนเฉลี่ยของ quicksort ที่ต้องเวียนเกิดลงไปลึก O(log n) ชั้น)

พูดง่ายๆ ก็คือ เราย้ายสแตกการเรียก (ที่ถูกซ่อนด้วยตัวภาษา) ออกมาให้เห็นกันชัดๆ ในระดับตัวแปรนั่นเอง!

ดังนั้น แม้เราจะสามารถทำ TCO บนฟังก์ชันเวียนเกิดใดๆ ได้ก็จริง แต่ไม่ใช่ทุกการทำ TCO จะเป็นประโยชน์

เช่นนี้แล้ว ในสายตาของโปรแกรมเมอร์จำนวนหนึ่ง ฟังก์ชันเวียนเกิดคงไม่มีวันเซ็กซี่ เพราะยังไงมันก็สู้การวน while ลูปแบบเดิมๆ ไม่ได้อยู่ดีใช่หรือเปล่า?

… ก็ไม่แน่ ลองย้อนกลับไปเขียน quicksort แบบไม่ง้อการเวียนเกิดดู

ไม่ว่าอย่างไร เราก็ต้องใช้สแตกเพื่อเก็บสถานะของฟังก์ชันอยู่ดี (แค่เราจะเปลี่ยนจากสแตกการเรียกเป็นสแตกตัวแปร) ซึ่งก็กินพื้นที่เป็น O(log n) ไม่ต่างจากเดิม เพิ่มเติมคือเราต้องเป็นคนจัดการสแตกด้วยตนเอง … ทั้งที่งานส่วนนี้สามารถโยนไปให้ตัวแปลภาษาทำแทนเราได้

ความน่ากลัวของฟังก์ชันเวียนเกิดจึงไม่ได้อยู่ที่สแตก แต่เป็นการวิเคราะห์ และออกแบบอัลกอริทึมให้ใช้พื้นที่อย่างมีประสิทธิภาพมากกว่า เพราะท้ายที่สุดแล้ว ถ้าอัลกอริทึมที่เขียนด้วยฟังก์ชันเวียนเกิดอย่างดีที่สุดยังใช้สแตกจนล้น การเปลี่ยนไปเขียนอัลกอริทึมดังกล่าวด้วยลูปก็ไม่ได้รักษาปัญหานี้ให้หายขาดแต่อย่างใด