Tail Call Optimization คืออะไร? มารู้จักวิธีประหยัดหน่วยความจำใน ES2015 กัน

Tail call optimization (ต่อไปนี้ผมขอเรียกแค่ TCO นะครับ) เป็นสิ่งใหม่ใน ES2015 ที่จะช่วยให้คุณประหยัดหน่วยความจำมากขึ้น แต่ใช่ว่าทุกคำสั่งจะได้รับอานิสงค์นี้ TCO นั้นมีผลแค่กับ tail call เท่านั้น แล้วอะไรหละคือ tail call? บทความนี้จะนำเพื่อนๆไปรู้จักกับ TCO และประโยชน์ที่ได้รับเมื่อปรับโค๊ดให้รองรับกับความสามารถนี้

ลำดับการทำงานกับ stack ในหน่วยความจำ

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

1function foo(x) {
2  return x
3}
4
5function bar(y) {
6  return foo(y + 1)
7}
8
9console.log(bar(1))

เมื่อโค๊ดข้างต้นเริ่มทำงาน JavaScript ต้องลงทะเบียนชื่อฟังก์ชันไว้ในหน่วยความจำก่อน เพื่อให้ทราบว่าเมื่อมีการอ้างถึงชื่อนี้ ต้องเรียกโค๊ดส่วนไหนมาทำงาน

จากนั้นโค๊ดบรรทัดที่9ก็จะทำงาน เป็นผลให้ปลุกฟังก์ชัน bar ในบรรทัดที่5ให้ขึ้นมาทำงาน ในฟังก์ชันนี้มีตัวแปรเพียงตัวเดียวคือ y JavaScript จึงจับ bar โยนลงใน stack พร้อมค่าของตัวแปร y ที่มีค่าเป็น1ส่งมาจากบรรทัดที่9 ดังนี้

จากนั้นในบรรทัดที่6 เราเรียกฟังก์ชัน foo อีกทีพร้อมส่งค่า y + 1 ให้ไปเป็นค่า x ของฟังก์ชัน foo จึงเกิดการซ้อนทับของ stack ขึ้นไปอีกชั้นแบบนี้

และแล้วโค๊ดของเราก็ไปสุดปลายทางที่บรรทัดที่2 เป็นผลให้สิ้นสุดฟังก์ชัน foo ทำให้ stack ของเราโดนกระซวกหายไปหนึ่งชั้น ผลลัพธ์ที่ได้จากการถอน foo ออกจาก stack จะไปอยู่ในชั้นของ bar ดังนี้

เมื่อจบการทำงานของ bar จะคืนค่ากลับไปสู่ main เป็นผลให้ bar หายไปจาก stack เช่นกัน ผลลัพธ์ที่ได้จากการทำงานทั้งหมดจึงเป็น2

ประหยัดหน่วยความจำด้วยการอย่าให้ Stack โต

สังเกตไหมครับบรรทัดที่9เราบอกว่าให้พิมพ์ bar(1) ซึ่งจริงๆแล้วมันคือการเรียก foo(1 + 1) นั่นเอง หรือพูดอีกนัยนึงได้ว่า bar ของเราเป็นเพียงฟังก์ชันคั่นกลางเฉยๆ คำถามคือถ้าเรามีฟังก์ชันคั่นกลางแบบนี้ซัก100สิ่ง Stack ของเราก็จะโตไปร้อยชั้นแบบนั้นหรอ? อย่ากระนั้่นเลย ในเมื่อเป็นแค่ของใช้ชั่วคราวเราก็ทำมันเป็นแค่ทางผ่านก็พอ เสียใจด้วยคุณยังไม่มีค่าเพียงพอให้ผมจดจำ :(

กลับมาตั้งต้นกันใหม่อีกรอบที่ stack ตั้งต้นของ main

เมื่อเราเรียก bar ในบรรทัดที่5 Stack ของเราจะโตขึ้นหนึ่งชั้นแบบนี้

บรรทัดที่6เราเรียก foo แต่เนื่องจากเรารู้แล้วว่าค่าที่ bar จะส่งออกไปจากฟังกชันนั้นคือค่าของ foo(y + 1) นั่นเอง ฉะนั้นแล้วเราจะเก็บชั้นของ bar ไว้ทำไมหละมันเป็นแค่ทางผ่านเองนะ ด้วยเหตุนี้เราจึงเอา foo(y + 1) ทับซะเลยแบบนี้

เมื่อเราดึงชิ้นส่วนบนสุดออกจาก stack เราก็จะได้คำตอบของผลลัพธ์คือ 2 ง่ายใช่ไหมหละกับ stack หนึ่งชั้น

Tail Call Optimization

เพื่อนๆสังเกตกันไหมครับ การที่เราจะบอกได้ว่าฟังก์ชันไหนเป็นแค่ตัวกลาง เราจะรู้ได้ก็ต่อเมื่อเจอประโยค return

1function foo(x) {
2  return x
3}
4
5function bar(y) {
6  // foo ตรงนี้ไม่สามารถแทนที่ stack ของ bar ได้
7  // เพราะไม่ได้อยู่ในประโยค return
8  foo(y)
9  // แบบนี้เรารู้เลยว่า bar ไม่สามารถโดนแทนที่ใน stack ด้วย foo ได้
10  // เพราะในประโยค return ไม่มีอะไรสัมพันธ์กับ foo แต่สัมพันธ์กับ 1 ต่างหาก
11  return 1
12}

แล้วถ้าเป็นแบบนี้หละ

1function foo(x) {
2  return x
3}
4
5function bar(x) {
6  return x
7}
8
9function print(x) {
10  // แบบนี้เราสามารถลดชั้นของ stack ได้
11  // เพราะประโยค return สัมพันธ์กับ foo หรือ bar ที่เป็นฟังก์ชัน
12  // ถ้า x > 0 แล้ว foo จะแทนที่ print ใน stack
13  // ถ้า x <= 0 แล้ว bar จะแทนที่ print ใน stack
14  return x > 0 ? foo(x) : bar(x)
15}
16
17console.log(print(1))

มีสิ่งหนึ่งที่ต้องให้ความสำคัญคือฟังก์ชันที่จะลดชั้นของ Stack ได้ต้องมีประโยค return ทำไมหนะหรือ? เพราะถ้าไม่มีประโยค return มันจะกลายเป็น return undefined หนะซิ ซึ่งมันไม่ได้สัมพันธ์กับฟังก์ชันไหนอีกเลย

1function foo(x) {
2  x
3}
4
5// มีค่าเท่ากับ
6function foo(x) {
7  x
8  return undefined
9}

สิ่งสำคัญอีกอย่างที่วิธีการนี้จะช่วยประหยัดหน่วยความจำคือต้องเป็นการเรียกในประโยค return สุดท้ายด้วยครับ ด้วยเหตุนี้เราจึงเรียกขั้นตอนวิธีนี้ว่า Tail Call Optimization นั่นเอง

TCO นั้นเป็นขึ้นตอนวิธีแบบใหม่ที่ผุดขึ้นใน ES2015 มีส่วนช่วยในการประหยัดหน่วยความจำในขั้นตอนการสร้าง Stack ES2015 ไม่ใช่กลุ่มภาษาแรกที่ใช้วิธีการนี้เพราะ TCO นั้นแพร่หลายในหมู่ภาษาโปรแกรมกลุ่ม Functional Programming อยู่แล้ว โดยวิธีการนี้มีประโยชน์มากโดยเฉพาะการทำงานแบบเรียกตนเอง (recursive function)

ตัวอย่างการลดการใช้หน่วยความจำด้วย Tail Call Optimization

ลองพิจารณาฟังก์ชันเรียกตัวเองต่อไปนี้ครับ

1function factorial(x) {
2  if (x <= 0) return 1
3  else return x * factorial(x - 1)
4}

จากฟังก์ชันหา factorial ข้างบน stack จะโตขึ้นเรื่อยๆเพราะภายใต้ฟังก์ชัน factorial เองก็เรียกตัวมันเองซ้ำไปซ้ำมา สาเหตุที่โค๊ดนี้ไม่สามารถใช้ TCO ได้เป็นเพราะบรรทัดที่3ไม่ใช่ tail call เพราะไม่ได้ return ฟังก์ชันออกมาเฉยๆ แต่ไปอ้างอิงถึงค่าของ x ด้วย

เพื่อให้บรรทัดที่3เป็น tail call เราจึงต้องทำการปรับเปลี่ยนโค๊ดดังกล่าวเล็กน้อยดังนี้

1function factorial(n, acc = 1) {
2  if (n <= 1) return acc
3  return factorial(n - 1, n * acc)
4}

รูปแบบโค๊ดที่จะได้รับอานิสงค์ของ Tail Call Optimization

ผมขอยกซักสองตัวอย่างการเขียนโค๊ดที่ได้รับผลของ TCO ครับ อย่างแรกคือโค๊ดที่มีการใช้ comma operator เรียกฟังก์ชันในตำแหน่งสุดท้าย เช่น

1// แบบนี้ได้รับผลของ TCO
2const foo = () => (f(), g())
3
4// มีค่าเท่ากับ
5const foo = () => {
6  // ยังคงเกิดชั้นของ stack สำหรับ f
7  f()
8
9  // แต่ไม่เกิดชั้นของ stack สำหรับ g เพราะสามารถแทนที่ได้
10  // บรรทัดนี้เป็น Tail Call
11  return g()
12}

อีกตัวอย่างคือประโยคเงื่อนไขคลาสสิกนี้

1const foo = (x) => {
2  return x > 0 ? foo() : bar()
3}

สนุกกันใช่ไหมครับกับ Tail Call Optimization บทความนี้ถือว่าเป็นสรุปจากหนังสือ Exploring ES6: Upgrade to the next version of JavaScript ของปรมาจารย์ Dr. Axel Rauschmayer เพื่อนๆคนไหนสนใจหาอ่านกันได้ครับ แนะนำให้อ่านเสร็จแล้วบูชากราบเช้ากราบเย็น ก่อนนอนก็ไว้ใต้หมอนครับ รับรองจะได้ฝันเห็น ES2015 ลอยไปลอยมาหลับง่ายยิ่งกว่านับแกะอีก (ความจริงคือเปิดอ่านแค่สารบัญก็หลับละ เห้อ :sleeping:)