Functional Programming #2 : ฟังก์ชันพิสุทธิ์และการเรียกตัวเอง

เกริ่นนำ

บทนี้เราจะมาเรียนรู้ถึงนิยามของฟังก์ชันในมุมมองของ FP กัน แนวคิดของการสร้างฟังก์ชันพิสุทธิ์ (Pure Function) กลไกฟังก์ชันการเรียกตัวเอง (Recursive Function) รวมถึงการปรับปรุงประสิทธิภาพการเรียกตัวเองอีกด้วย ก่อนจะเข้าเนื้อหา ผมขอปรับความเข้าใจให้ตรงกันสองประการก่อนครับ ข้อแรกเรื่องการแปลศัพท์ทางเทคนิคจากภาษาอังกฤษมาเป็นภาษาไทย ผมจะยึดตามราชบัณฑิตเฉพาะคำที่รู้จักกันอย่างแพร่หลายแล้วเท่านั้น นอกนั้นผมขอบัญญัติคำขึ้นมาเอง เอาให้รื่นหูโดยมีแม่แบบมาจากท่าน ว.ณ เมืองลุง ผู้เขียนหนังสือกำลังภายในจีนที่ผมชอบมาก อย่างฟังก์ชันพิสุทธิ์ นี่ผมก็ตั้งเองนะครับ ตั้งชื่อเอาไว้เพื่อสื่อความเข้าใจเท่านั้น กรุณาอย่านำเอาไปใช้ต่อนะครับ

ส่วนเรื่องที่สองเป็นเรื่องที่ผมทำใจค่อนข้างลำบาก แต่ก็ต้องตัดสินใจ คือการอธิบายเรื่อง FP นั้น จำเป็นต้องใช้เลือกใช้ภาษาใดภาษาหนึ่งมาเป็นตัวขับเคลื่อน ถ้าตามใจคนใช้ Python C# Java หรืออื่นใดก็ตา  คนใช้ภาษาอื่นอาจไม่สบอารมณ์ ไม่ว่าเลือกภาษาใด ก็จะไม่สามารถเป็นที่ถูกใจทุกท่านได้หมด ดังนั้นผมขอไม่เอาใจใครเลยครับ เลือกเอาภาษา FP แท้ๆ ดีกว่า จะได้เห็นก็อย่างชัดเจนเลยว่า FP ทำงานอย่างไรแน่ แม้จะฟันธงแล้วว่าเป็นภาษา FP แท้ ๆ มันก็ยังมีหลายภาษาอยู่ดี ผมตัดสินใจแล้วครับ เลือกเอา Haskell ดีกว่า สั้นกะทัดรัดไม่เวิ่นเว้อ ยิงตรงจุด อ่านเข้าใจง่าย และที่สำคัญที่สุด การออกแบบภาษาทำได้ดีมากครับ ที่ควรเป็น มันเป็น ที่ไม่ควรเป็น มันไม่ทำ ชอบครับ ท่านไม่ต้องกังวลนะครับว่าจะไม่รู้เรื่อง รับรองได้ว่าไม่ยากครับ เข้าใจง่ายครับ ผมเอามาแค่ส่วนเล็ก ๆ ของภาษาเอง และผมจะอธิบายให้ท่านฟังตลอดทาง เปิดใจกว้าง ๆ ตามผมมาครับ

ฟังก์ชันพิสุทธิ์ (Pure Function)

ขอถามว่าฟังก์ชันคืออะไร เชื่อว่าท่านผู้อ่านเมื่อเห็นว่าผมถามอย่างนี้คงส่ายหน้าไปตาม ๆ กัน คงบ่นผมว่ามัวแต่รำมวยอยู่นั่นแหละไม่ชกซักที ใจเย็น ๆ ก่อนครับ ฟังก์ชันที่ผมพูดถึงไม่ได้หมายความซ้อนทับ 100% กับฟังก์ชันในภาษา C หรือภาษาอื่นๆที่ท่านรู้จักมา แต่หากเป็นฟังก์ชันที่เราเรียนกันมาตั้งแต่สมัยเด็ก ๆ ตอนมัธยม จำกันได้ไหมครับก็พวก sin() cos() tan() หรือฟังก์ชันที่เรานิยามเอง ท่านก็คงสงสัยอีกมันก็เรื่องเดียวกันกับในภาษา C นี่แหละ เรื่องเดียวกันชัด ๆ ไม่เห็นต่างกันตรงไหน เอาอย่างนี้ดีกว่าผมเปลี่ยนคำถามดีกว่า ลองดูข้างรูปข้างล่างนะครับ รูป A และรูป B ซึ่งแกน X เป็นค่าเรียงที่เราป้อนเข้าสู่ฟังก์ชันภาษาทางคณิตศาสตร์เรียกว่า domain และแกน Y เป็นผลลัพธ์ที่ได้จากฟังก์ชันซึ่งก็คือ range ท่านบอกได้ไหมว่ารูปได้เป็นหรือไม่เป็นฟังก์ชันตามที่เคยเรียนมา

is_function

รูปใดเป็นฟังก์ชัน จำได้ไหมครับว่าท่านมีวิธีพิสูจน์อย่างไร ถ้าจำไม่ได้ไม่เป็นไร  ผมขอเอาวิธีที่ครูเคยสอนผมตอนเด็ก ให้เราลากเส้นตรงผ่าลงมาในแนวดิ่งตำแหน่งใด ๆ ก็ได้บนกราฟ ถ้ามันตัดกราฟได้อย่างมากแค่ครั้งเดียวนั่นแหละคือฟังก์ชัน แต่ถ้าลากลงมาเกิดตัดเส้นกราฟมากกว่าหนึ่งจุด เพียงแต่ที่เดียว ก็ถือว่าไม่ใช่ฟังก์ชันในทางคณิตศาสตร์ ทีนี้ท่านบอกผมได้รึยังครับรูปใดเป็นหรือไม่เป็นฟังก์ชัน  ใช่แล้วครับ รูป A เป็นฟังก์ชัน ส่วนรูป B ไม่เป็นฟังก์ชัน ฟังก์ชันในจักรวาลของ FP  ก็ใช้นิยามนี้ในการกำหนดครับ  ถ้าเรามาลองย้อนกลับดูนะครับถึงฟังก์ชันในภาษาโปรแกรมที่เราเขียน ผมถามว่าเป็นฟังก์ชันตามนิยามข้างต้นหรือไม่ คุณว่าอย่างไรครับ ฟังก์ชันในจักรวาล Imperative บางตัวก็ไม่ใช่ฟังก์ชันตามนิยามนี้ใช่ไหมครับ การที่จะให้ตรงตามนิยาม เมื่อใส่ค่าพารามิเตอร์ให้แก่ฟังก์ชันค่าใดก็ตามมันจะให้ผลลัพธ์ออกมาค่าหนึ่งและถ้ามันยังให้ค่านั้นออกมาเสมอจนโลกแหลกสลายเช่น sqrt(2.0) จะได้ 1.414213452  เสมอรันโปรแกรมกี่ทีก็ยังได้ค่านี้ไม่อาจเป็นค่าอื่นไปได้แบบนี้สรุปได้เลยว่าเป็นฟังก์ชันตามนิยามทางคณิตศาสตร์ แต่ลองดูตัวอย่างนี้ครับ

ข้างบนไม่รู้ว่าเป็นภาษาอะไรนะครับ ผมมั่วขึ้นมา แต่มันเป็นการสร้างฟังก์ชัน  f() ลองใช้งานดูครับ  ถ้าเราใส่ f(10) จะได้ 15  ว่าแต่ว่ามันได้ 15 ตลอดกาลหรือไม่ ไม่เสมอไปใช่ไหมครับ ถ้าเราเปลี่ยนค่า a จาก 5 เป็นค่าอื่น  f(10) ก็จะเปลี่ยนค่า ดังนั้นผลลัพธ์ที่ได้จาก f() นั้นไม่ได้ขึ้นอยู่กับพารามิเตอร์แต่อย่างเดียว แต่หากอยู่กับค่า a ซึ่งเป็นตัวแปรภายนอกด้วย แบบนี้ไม่นับว่าเป็นฟังก์ชันทางคณิตศาสตร์ครับ

เรามามองดูกันครับปัญหาของเรื่องนี้เกิดจากอ้างถึงตัวแปรภายนอกเราเรียกว่ามันเป็น side effect ซึ่งภาษาที่เป็น FP แท้ ๆ จะไม่ยอมให้เราเข้าถึงตัวแปรข้างนอกฟังก์ชันเลยไม่ว่าอ่านหรือเขียนก็ตาม แต่เราอาจจะหย่อนกฎลงมาหน่อย ก็คือเราไม่เขียนค่าตัวแปรข้างนอกฟังก์ชันส่วนอ่านจะอ่านเฉพาะค่าที่เป็นค่าคงที่เท่านั้น ถ้าเป็นแบบนี้ก็ยังคงรักษากฎที่ว่าตัดเส้นแนวดิ่งได้อย่างมากจุดเดียวได้ฟังก์ชันตามแนวคณิตศาสตร์นี่แหละครับ เราเรียกมันว่าฟังก์ชันพิสุทธิ์ FP เท่านั้นยังไม่พอนะครับ ฟังก์ชันพิสุทธิ์จะต้องไม่ไปแก้ค่าใดๆ นอกฟังก์ชันตัวเอง แม้แต่การแสดงผล ก็ถือว่าเป็นการเปลี่ยนแปลงหน้าจอ ซึ่งขัดกับทฤษฏีของฟังก์ชันพิสุทธิ์ครับ ผมเคยให้โจทย์รับสมัครงาน ให้เขียนฟังก์ชันบวกเลข 1 ถึง 100 มีคนหนึ่งเขียนเป็น Visual Basic ประมาณนี้ครับ

เห็นปัญหาของฟังก์ชันนี้ไหมครับ ผลลัพธ์ไม่ใช่ปัญหาครับ คำตอบถูกต้อง แต่ปัญหาอยู่ตรงบรรทัด MessageBox ครับ บรรทัดนี้มันเปลี่ยนแปลงหน้าจอข้างนอก ให้เราเห็นคำตอบเลย ดูเหมือนจะดีครับ แต่มันทำให้การนำเอาไปใช้ใหม่ (reuse) มีปัญหาเวลาเอาไปใช้กับงานอื่น มันก็จะ MessageBox แสดงมาตลอด ซึ่งไม่น่าจะตรงกับความต้องการ เรียกว่าฟังก์ชัน SubForm1To กับ MessageBox มีเวรมีกรรมต่อกัน (Coupling) ถ้าเรายึดตามหลักฟังก์ชันพิสุทธิ์ ปัญหานี้จะไม่เกิดครับ เพราะ MessageBox มีการเปลี่ยนแปลงภายนอก คำสั่งนี้จึงใช้งานในฟังก์ชันพิสุทธิ์ไม่ได้ครับ   เมื่อฟังก์ชันพิสุทธิ์ไม่มีการเปลี่ยนแปลงสถานะใดๆ ภายนอกฟังก์ชัน ย่อมทำให้ลำดับในการทำงานก่อนหลังจึงไม่มีผล ดังนั้นถ้ามีการเรียกใช้ฟังก์ชันพิสุทธิ์ 100 หน ครั้งใดจะทำก่อนหรือหลังก็ได้ ทำให้สามารถประยุกต์ใช้กับการประมวลผลแบบขนานโดยใช้หลายแกนประมวลผล เพื่อช่วยกันทำงานให้ได้ผลลัพธ์ที่เร็วขึ้นได้ครับ ดังนั้นจึงไม่น่าแปลกใจว่าทำไมภาษาคอมพิวเตอร์ในจักรวาล FP นั้น มีข้อเด่นในเรื่องการประมวลผลแบบขนาน

ฟังก์ชันพิสุทธิ์ไม่มี sequence และ iteration

ถ้าใครก็ตามเรียนสาขาทางคอมพิวเตอร์โดยตรง จะทราบเป็นอย่างดีว่า Imperative นั้นมีนิยามในการทำงานหลักอยู่สี่ประการ บางครั้งเรียกว่า Control Flow บ้าง Structured Programming บ้าง ดังนี้

  • Sequence   คำสั่งมีลำดับการทำงาน คำสั่งต่อคำสั่งทำงานเรียงลงมา
  • Selection  คำสั่งมีเงื่อนไข มีทางแยกเช่นพวกคำสั่ง if,  case, switch นั่นเอง
  • Iteration คือการวนรอบที่รู้จักกันพวก  repeat, for, while นั่นเอง
  • Subroutine ก็คือ function หรือ procedure นั่นเอง

คำว่าโปรแกรมก็คือนำเอาวัตถุดิบทั้งสี่มาผัดรวมกัน ก็ตรงไปตรงมาเข้าใจได้ แต่ถ้าท่านลองอ่านหัวเรื่องนี้ให้ดี ท่านอ่าจจะงง ไม่ให้ใช้ Sequence กับ Iteration แล้วมันจะกลายเป็นโปรแกรมได้อย่างไรถ้าต้องการทำงานหลายๆขั้นตอนหรือทำงาน-วนซัก 100 รอบไม่ให้ใช้ Iteration แล้วจะเขียนได้อย่างไร การคุยกันเรื่องนี้คงต้องย้อนกลับไปที่ Lambda Expression สมัยที่ Church นิยามนั้น Imperative ยังไม่เกิด Sequence / Iteration ยังไม่เป็นที่รู้จัก รู้จักแต่ Selection และ Function เท่านั้นท่านคงสงสัยแล้วว่าแล้วขาด ๆ ด้วน ๆ แบบนี้มันจะทำงานได้หรือ ได้สิครับ ผมขอยกตัวอย่างการหาแฟคทอเรียลให้ดูกันครับเชื่อว่าทุกท่านน่าจะรู้จักกันดีอยู่แล้ว

\Large n!=\displaystyle\prod_{i=1}^n k

จากรูปนี้ถ้าใครอ่านภาษาทางคณิตศาสตร์ออกจะสามารถแปลเป็นโปรแกรมได้เลยครับ ซึ่งตัวมีเสาสองข้างและมีคานข้างบนคือตัวอักษรกรีกตัว pi ตัวใหญ่นั่นเอง ความหมายคือการคูณกำหนดให้ k=1 ไปถึง n จากนั้นคูณค่า k แต่ละค่าเข้าด้วยกันเป็นคำตอบ ดังนั้นสามารถแปลตรง ๆ เป็นภาษา C ได้เลย ดังนี้ครับ

คงคุ้นเคยกันดีอยู่แล้วนะครับสำหรับฟังก์ชันนี้ซึ่งใช้ loop for ถามว่าถ้าไม่ใช้ มีวิธีอื่นไหม มีครับแต่เราต้องเปลี่ยนนิยามมาเป็น

$latex n! = \left\{\begin{matrix} 1 & \text{if n = 0,}\\ (n-1)! \times n & \text{if n \textgreater 0} \end{matrix}\right.$

ซึ่งอยู่ในรูปของการเรียกตัวเองนั่นเอง ซึ่งเมื่อแปลงเป็นภาษา C จะได้ดังนี้

หรือถ้าเขียนเป็น Haskell จะได้สั้นๆ ดังนี้ครับ

เห็นไหมครับว่าโปรแกรมที่ได้นี่แทบจะลอกออกมาจากสูตรทางคณิตศาสตร์เลยทีเดียว โดยเฉพาะอย่างยิ่งภาษา Haskell คงอ่านเข้าใจได้โดยไม่ยากนะครับ ฟังก์ชันที่ใช้ loop for เป็นแบบ Imperative เน้นวิธีการทำ ทำอะไร และทำได้อย่างไร กรุณาแสดงวิธีทำ  ส่วนฟังก์ชันในการใช้การเรียกตัวเองจะเป็นแบบ FP ซึ่งแทบจะลอกนิยามมาเป็นโปรแกรมเลย  จึงเป็นการระบุว่า ต้องการอะไร มากกว่าทำได้อย่างไร ถ้าเทียบกันเฉพาะภาษา C ท่านว่าฟังก์ชันทั้งสองตัวนี้ตัวไหนสั้นกว่า แน่นอนครับแบบเรียกตัวเอง ซึ่งใช้แนวคิด FP จะสั้นกว่าแต่ถ้าถามว่าฟังก์ชันใดอ่านรู้เรื่องมากกว่ากันคนส่วนมากคงบอกว่า Imperative ไม่แปลกครับคนไทยพูดภาษาไทยตั้งแต่เกิด ย่อมต้องบอกว่าอ่านนิยายไทยเข้าใจและกินใจมากกว่าอ่านนิยายฝรั่งแน่นอนครับ  แต่แน่ ๆ ฝรั่งคงไม่คิดเหมือนเรา เฉกเช่นเดียวกันนักคณิตศาสตร์ส่วนมากจะบอกว่าฟังก์ชันเรียกตัวเองอ่านรู้เรื่องมากกว่าดังนั้นถ้าอยากเข้าใจ FP ก็ต้องทำตัวตัวเหมือนการไปคาเนกี้ฮอลล์ของวาทยกรชื่อดัง ก็ต้องซ้อม ๆ ๆ เท่านั้นครับ

มีข้อน่าสังเกตอยู่เล็กน้อยครับ ฟังก์ชันพิสุทธิ์จะไม่สร้างตัวแปรขึ้นมาในฟังก์ชันนะครับ โดยเฉพาะอย่างยิ่งตัวแปรที่สะสมค่า จากตัวอย่างข้างบนจะเห็นว่า นอกจาก n ที่เป็นพารามิเตอร์แล้ว จะไม่มีตัวแปรตัวอื่นอีกครับ ผิดกับ Imperative ที่อย่างน้อยต้องมีตัวแปรสะสมค่า sum อยู่หนึ่งตัว ซึ่งการไม่มีตัวแปรทำให้โอกาสที่จะผิดพลาดก็น้อยลง  แต่จะว่าไปแล้วถ้าพูดว่าฟังก์ชันพิสุทธิ์จะไม่สร้างตัวแปรในฟังก์ชันก็อาจจะไม่จริงนัก สร้างได้ครับ แต่จุดประสงค์ของการสร้าง ก็เพียงเพื่อลดการเขียนที่ซ้ำซ้อน เช่นในฟังก์ชันมีการใช้ pi * r ^2 หลายที่ การต้องเขียนสูตรนี้หลายครั้งจะซ้ำซ้อน อ่านยาก ยากต่อการแก้ไข ดังนั้นจึงสร้างตัวแปร area ขึ้นมาสำหรับการนี้ แต่เอาให้ชัดเจนนะครับ เมื่อกำหนดค่าตัวแปร area เป็นค่าใดแล้ว จะไม่มีการเปลี่ยนแปลงค่านั้นตลอดทั้งฟังก์ชันครับ วนรอบเปลี่ยนค่าอย่างตัวแปร i, sum เป็นสิ่งต้องห้ามสำหรับฟังก์ชันพิสุทธิ์ การที่ไม่มี Sequence และ Iteration ไม่ใช่ปัญหามากมายอย่างที่คิดว่าจะเป็น เพียงแค่จะต้องกระจายฟังก์ชันออกไปหลาย ๆ ตัวเพื่อสอดประสานการทำงานกันก็แค่นั้น ซึ่งผมจะมีตัวอย่างหลายตัวให้เห็นในบทต่อ ๆ ไป คุณจะได้เห็นว่า FP ไม่ยุ่งยากอย่างที่คิดครับ

การเรียกตัวเองทำงานได้อย่างไร

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

ram structure

จากรูปเป็นโมเดลการจัดหน่วยความจำของโปรแกรมที่ทำงานบนเครื่องคอมพิวเตอร์ทั่วไปที่ OS จัดสรรหน่วยความจำแรมมาให้แต่ละโปรแกรม เราจะเห็นได้ว่าหน่วยความจำแบ่งเป็น 4 ส่วนในส่วนแรกเป็นตัวโปรแกรมภาาษาเครื่อง ตามด้วยที่เก็บตัวแปรภายนอก ต่อด้วย  heap และ stack พอบอกได้ไหมครับว่าตัวแปรต่าง ๆ ที่เราสร้างเมื่อไหร่มันจะไปอยู่ในส่วนตัวแปรภายนอก  heap หรือ stack อย่างไร ลองพิจารณาตัวอย่างนี้ภาษา C นี้ครับ

ก่อนรันโปรแกรม โปรแกรมจะถูกโหลดจากหน่วยความจำสำรองเช่น harddisk เข้าสู่หน่วยความจำหลักคือแรม ตัวโปรแกรมภาษาเครื่องจะอยู่ในส่วนของโปรแกรมตามแผนผัง ซึ่งการถ่ายโอนจากสื่อสำรองมายังหน่วยความจำหลักเรียกว่าการโหลด ตัวแปร g จะถูกเก็บในส่วนตัวแปรภายนอก เมื่อเริ่มรันโปรแกรมใน main() จะเกิดตัวแปร a, b, c ขึ้น พอบอกได้ไหมครับตัวแปรทั้งสามเกิดขึ้นที่ไหน คำตอบคือ stack ครับ จริง ๆ แล้วไม่ใช่แค่ 3 ค่าที่เป็นตัวแปรท้องถิ่น (local) นะครับ แต่รวมถึงพารามิเตอร์ทุกตัวที่ส่งเข้ามาฟังก์ชัน (ถ้ามี) และ ค่าส่งกลับออกไป และที่สำคัญที่สุดคือตำแหน่งที่จะกลับไป ซึ่งจะมีรายละเอียดต่อไป ทั้งหมดรวมแล้วเรียกว่า stack frame ซึ่งมีหน้าตาดังนี้

one_stackframe

การเรียกฟังก์ชันหนึ่งครั้งจะเกิด stack frame หนึ่งชุดล องดูโปรแกรมข้างบนตามนะครับ เมื่อใน main() เรียกฟังก์ชัน f1() ไปทำงานก็จะเกิด stack frame ชุดที่สองซ้อนอยู่ข้างบน   ซึ่งประกอบด้วยตัวแปร x, y, a, b และ c  (ซึ่ง a, b และ c เป็นคนละตัวกับ stack frame ตัวแรกของ main()) และกำหนดให้ stack frame นี้มีสถานะ active นั่นคืออ่านเขียนค่าได้ส่วน stack frame ของ main() จะเข้าถึงไม่ได้ครับ ในหนึ่งช่วงเวลาใด ๆ เราสามารถใช้งาน stack frame ได้ตัวเดียวครับ (มีกรณียกเว้นแต่ขอไม่กล่าวในที่นี้ครับ) ซึ่งจะทำให้ผลลัพธ์จะได้ดังภาพนี้ครับ

f1_stackframe

จากนั้นใน f1() มีการเรียกใช้ f2()  ซึ่งจะเกิด stack frame ดังรูปนี้ครับ

f2_stackframe

ซึ่งเมื่อ f2() ทำงานเสร็จถามว่าโปรแกรมจะรู้ได้อย่างไรว่าจะกลับไปทำงานที่ใด ในงานจริงแต่ละฟังก์ชันอาจถูกเรียกมาจากหลายภาคส่วนของโปรแกรม แล้วฟังก์ชันนั้นจะรู้ได้ว่าใครเรียก แล้วจะกลับไปถูกยังผู้เรียกได้อย่างไร คำตอบอยู่ที่ stack frame นั่นเอง ก่อนที่จะเรียกใช้ฟังก์ชันใด ๆ ก็ตาม ผู้เรียกจะใส่ตำแหน่งต่อไปหลังจากเรียกใช้ฟังก์ชันนี้แล้วลงบน stack frame ตัวใหม่ เมื่อฟังก์ชันทำงานเสร็จก็จากดึงเอาตำแหน่งนั้นออกมาจาก stack frame แล้วกระโดดกลับไปที่นั่นในกรณีนี้ก็เช่นกัน f2() สามารถกลับไป f1() และในทำนองเดียวกันเมื่อ f1() ทำงานเสร็จก็สามารถกลับไปที่ main() ได้โดยวิธีเดียวกัน

ย้อนกลับโปรแกรมหา factorial แบบ recursive ข้างบนที่สงสัยว่าตัวแปร n แต่ละรอบที่วนกลับมาจะทับกันไหม ถ้าเราไม่มองว่าฟังก์ชันที่เราเรียกใช้คือตัวเราเอง แต่มองว่าฟังก์ชันนั้นเป็นอีกฟังก์ชันหนึ่งที่แค่มีชื่อเหมือนกันเท่านั้น จะเข้าใจได้ง่ายขึ้นครับ เมื่อมันวนเรียกตัวเองมันก็เกิด stack frame คนละชุดตัวแปรคนละชุดกันเลย ไม่ได้ทับกัน ฟังก์ชัน factorial จะวิ่งลงไปเรื่อย ๆ จนถึงท้ายสุดไปต่อไม่ได้จะเกิดส่งค่ากลับขึ้นตรงจุดสุดท้าย เราเรียกว่าหาง (tail) จากหางก็จะส่งค่าย้อนกลับมาเป็นชั้น ๆ จนถึงหัว (head) ในแต่ละชั้นที่กลับมา จะเกิดการคูณกับค่า n ที่เก็บไว้ใน stack frame แต่ละชุด คูณย้อน และส่งค่าครับ  เมื่อถึงหัวแล้วก็จะย้อนกลับไปไปสู่ฟังก์ชันผู้เรียก  สังเกตนะครับเราใช้ศัพท์ว่าหัวและหางนี่แทนการเรียกฟังก์ชันตัวเดียวกันแต่ต่างกันตรงที่เป็นทางเข้าหรือปลายสุด

ในมุมมองของประสิทธิภาพผมให้ไม่ผ่านครับ

จากความรู้ที่ผ่านมาทำให้เรารู้ว่าการหา factorial โดยใช้การเรียกตัวเองนั้นเป็นวิธีที่ไร้ประสิทธิภาพอย่างร้ายแรงเพราะถ้าต้องการหา 100! ก็ต้องมีการเรียกใช้ฟังก์ชันถึง 100 ครั้งมี stack frame เกิดขึ้นซ้อนกัน 100 ชุดและมีการย้อนกลับขึ้นมาถึง 100 ครั้งอีกด้วยการซ้อนกันของ stack หลายๆชั้นขนาดนี้ทำให้กินพื้นที่ลามขึ้นมาเมื่อใดก็ตามมันลามขึ้นไปหา heap ซึ่งลามลงมาเรื่อยๆอยู่เช่นกันชนกันเมื่อใดโปรแกรมก็จะหยุดทำงานแล้วฟ้องว่า stack overflow ซึ่งถ้าเทียบกับฟังก์ชัน factorial แบบการใช้ loop for แล้วการทำงานวน 100 รอบไม่มีการเรียกฟังก์ชันไม่เกิดstack frame ซ้อนเป็นชั้นๆเร็วกว่าหายห่วงเลยครับ แต่โชคร้ายครับที่การเรียนการสอนเรื่องการเรียกตัวเองเบื้องต้นสำหรับ Imperative นั้นมักหยิบยกเอา factorial มาเป็นตัวอย่างซึ่งไม่เหมาะสมเป็นอย่างมากทำให้โปรแกรมเมอร์ไม่น้อยมองการเรียกตัวเองเป็นศัตรูไปทั้งๆที่การเรียกตัวเองมันก็มีจุดยืนของมันถ้าถามผมว่ามีโจทย์ปัญหาข้อใดที่จำเป็นต้องใช้การเรียกตัวเองไม่ใช้แล้วเขียนไม่ได้ สำหรับ ผมบอกได้เลยว่าไม่มี ทุกอย่างที่เขียนเป็นแบบเรียกตัวเองได้ ย่อมสามารถเขียนเป็นแบบไม่ใช้การเรียกตัวเองได้เสมอ เพียงแค่ถ้าใช้การเรียกตัวเองแล้วบางกรณีเขียนง่ายกว่าและอ่านรู้เรื่องมากกว่ามันก็แค่นั้น

Tail call Optimization

เมื่ออ่านมาถึงบรรทัดนี้เชื่อว่าหลายท่านคงสงสัยว่าภาษาในจักรวาลของ FP คงมีประสิทธิภาพที่แย่น่าดูไม่ต้องดูอื่นไกลโจทย์ factorial ถ้าเป็น Imperative สามารถหนีไปใช้ loop for ได้แต่ FP ไม่น่าจะมี loop for น่าจะถูกบังครับให้ใช้การเรียกตัวเองอย่างนี้ stack frame ไม่บานเบอะหรือ เอาอย่างนี้ครับ FP มีวิธีอื่นในการแก้ไขปัญหาข้อนี้แต่ในบทความนี้ผมมุ่งเน้นไปยังการเรียกตัวเองเท่านั้นบอกได้เลยว่าถ้าเขียนแบบนี้ก็เจอกองทัพ stack frame แน่ แต่มันมีเทคนิคครับเทคนิคในการปรับโปรแกรมเล็กน้อย แล้วทำให้จากหลังเท้ากลายเป็นหน้ามือได้ เทคนิคนั้นเรียกว่า Tail call Optimization ตามหัวเรื่องเลยครับ เทคนิคนี้เราต้องปรับ code ของเราให้เป็น tail call ครับคำว่า tail call ยังคงเป็นการเรียกตัวเองอยู่นะครับ แต่แตกต่างกันตรงที่บรรทัดที่เรียก recursive นั้นต้องเป็นบรรทัดสุดท้ายไม่มี code อะไรต่อ และการส่งกลับนั้นต้องส่งกลับทันที ตรง ๆ ไม่มีการคำนวณใด ๆ อีก ลองดูตัวอย่าง

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

การนำเอา n – 1 อยู่ในการเรียกตัวเอง ไม่มีปัญหาครับ แต่เมื่อเรียกตัวเองแล้วต้องส่งกลับทันที ในกรณีข้างบนนี้มีการนำเอาไปคุณกับ n แบบนี้แหกกฎ tail call ครับ ลองดูตัวอย่างต่อไป

แบบนี้ก็แหกกฎ tail call ครับ เพราะหลังจากเรียกตัวเองแล้วต้องส่งกลับทันทีครับ จะมาอ้อยอิ่งทำอย่างอื่นก่อน แล้วค่อยส่งครับในบรรทัดข้างล่าง แบบนี้ก็ไม่ได้ครับ

ถ้าวิเคราะห์ดี ๆ ถึงนิยามของ tail call จะเห็นว่ากฎของ tail call มีเพื่อการบังคับให้โปรแกรมเมื่อเรียกตัวเองลงไปถึงหางแล้ว มีการมีการส่งค่ากลับขึ้นมาเป็นชั้นๆ ตาม stack frame โดยที่ค่านั้นจะมีความพิเศษอยู่อย่างหนึ่งคือ จะไม่มีการเปลี่ยนแปลงค่านั้นจากหางไปสู่หัว หรืออาจกล่าวได้ว่า tail call จะบังคับให้หางกับหัวส่งค่ากลับตัวเดียวกัน เราสามารถปรับโปรแกรม factorial ให้สอดคล้องกับ tail call ได้ดังนี้

หรือเขียนเป็น Haskell ได้ดังนี้ครับ

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

ท่านผู้อ่านอาจจะงงว่า มันก็ไม่เห็นต่างกับ factorial แบบแรก เพียงแค่ย้ายที่การคูณจากที่เคยทำตอนขาขึ้นมาทำเอาตอนขาลงเท่านั้น ถ้าท่านคิดว่ามันไม่ต่างก็ขอแสดงความยินดีด้วยครับแสดงว่าท่านเข้าใจการทำงานของการเรียกตัวเองเป็นอย่างดีแล้วครับ คนที่ทำให้ต่างไม่ใช่ท่านครับ มันอยู่ที่คอมไพเลอร์แต่ละตัว เคล็ดมันอยู่ตรงนี้ครับ ในเมื่อค่าที่ส่งกลับจากหางมาสู่หัวเป็นค่าเดียวกันเสมอแล้วนั้น ความจำเป็นที่ต้องสร้าง stack frame มากมายเพื่อย้อนกลับขึ้นมาก็ไม่มี ตัด stack frame ที่ซ้อนกันทิ้งไปให้หมดได้เลย  คอมไพเลอร์ที่เก่ง ๆ จะสามารถยุบโปรแกรมนี้กลายเป็น loop ปกติ ซึ่งอาจะได้ผลลัพธ์ที่เป็นภาษาเครื่องเดียวกันกับ loop for เลยก็เป็นได้ ซึ่งเร็วขึ้นมากแต่ยังคงการเขียนแบบการเรียกตัวเองไว้ได้

ถ้าจะใช้คอมไพเลอร์ตัวไหนภาษาอะไร ต้องดูว่าคอมไพเลอร์ตัวนั้นสามารถทำ tail call optimization ได้หรือไม่ อย่างภาษา C/C++ เราต้องระบุเวลาคอมไพล์ให้มันทำTail Call Optimization มันถึงจะยุบ tail call ให้กลายเป็น loop ได้  ส่วนภาษา Scala ต้องระบุ @tailrec ไว้บนหัวฟังก์ชันที่ต้องการ optimize ส่วนภาษาที่เป็น FP แท้ ๆอย่าง Haskell หรือ F# ไม่ต้องระบุอะไร เพราะมันจะ optimize อัตโนมัติเสมอ ถ้าเป็นภาษาแบบ Interpreter อย่าง Ruby หรือ Python การทำ tail call optimization เป็นเรื่องค่อนข้างยากแม้แต่ VB.NET C# Java ปัจจุบันก็ยังทำไม่ได้เลย

ถ้าต้องการพิสูจน์ว่า tail call optimization นั้นทำงานอยู่หรือไม่ วิธีทดสอบที่ง่ายที่สุดคือ ใช้ IDE ที่มากับคอมไพเลอร์ เขียนโปรแกรมและลองดีบั๊กโปรแกรมดูครับ ขอดูหน้าต่าง stack frame  ถ้าในระหว่างการดีบั๊กในส่วนการเรียกตัวเอง ถ้ามีการสร้าง stack frame ตัวใหม่ขึ้นเรื่อยๆ แสดงว่า tail call optimization ไม่ได้ทำงาน แต่ในทางกลับกัน ถ้าไล่ดีบั๊กวนไปเรื่อยๆ แต่ stack frame ยังคงที่ แสดงว่าทุกอย่างเป็นไปตามที่คาดไว้ครับ

แปลงร่างฟังก์ชันซ้อนมันซะ

จาก tail call ฟังก์ชันข้างบนสิ่งที่เราจะเห็นว่าการเรียกฟังก์ชันแบบเรียกตัวเองนั้นมันต้องมีพารามิเตอร์เพิ่มขึ้นอีกตัวเพื่อส่งค่า prodีct ซึ่งแน่นอนไม่ควรให้ผู้ใช้งานเห็น เพราะเขาจะงงว่าพารามิเตอร์ของ _factorial ว่า ตัวแปร product คืออะไรและทำไมต้องใส่เป็น 1 ในตอนเริ่มต้น  เพื่อแก้ไขปัญหานี้ผมจึงรักษารูปการเรียกใช้ฟังก์ชันแบบเดิม คือมีพารามิเตอร์ n เพียงตัวเดียว แต่ใช้ให้มันไปเรียกฟังก์ชันที่เรียกตัวเองอีกที ซึ่งจะยุ่งยากเพิ่มขึ้นกลายเป็นต้องมีสองฟังก์ชัน ภาษาบางภาษาจะแก้ไขปัญหานี้โดยการยอมให้มีการนิยามฟังก์ชันซ้อนฟังก์ชัน (nested functions) ซึ่งผมขอยกตัวอย่าง Scala ดังนี้

จะเห็นได้ว่าผู้ใช้ไม่จำเป็นต้องรับรู้ถึงการมีอยู่ของ _factorial() ซึ่งการใช้งานจะสะดวกขึ้นดูไม่รกรุงรัง ภาษาที่เป็น Interpreter อย่าง Python, Ruby ทำได้สบายมาก

ลองฝึกฝีมือหาค่าผลรวมจาก list ดู

หวังท่านเข้าใจในการเขียนโปรแกรมแบบการเรียกตัวเองแล้วนะครับเพื่อทดสอบว่าท่านเข้าใจเป็นอย่างดีแล้ว ผมขอให้โจทย์ซักข้อซ้อมมือสมมุติว่าเรามี list อยู่ตัวหนึ่งหรือ array ก็ได้ภายในมีแต่ตัวเลขจำนวนเต็มนะครับ อยากให้ลองเขียนโปรแกรมหาผลรวมของค่าทั้งหมดตั้งชื่อฟังก์ชันว่า sum ใช้ภาษาที่ท่านถนัดครับ  ไม่ต้องเอาถึงขนาดตัด Sequence ทิ้งก็ได้ครับ ขอให้ไม่มี Iteration ก็ขอให้ใช้การเรียกตัวเองแทนครับ

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























ถนนสายนี้มุ่งสู่ Haskell

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

เพื่อความเข้าใจ มาทำความรู้จัก Haskell สักหน่อย ก่อนเกิด Haskell มีภาษาหนึ่งครับที่เจ๋งมากชื่อว่า Miranda เกิดมาก่อน แต่น่าเสียดายที่ไม่ใช่ Open Source ดังนั้นในงานประชุมวิชาการด้าน FP ในปี 87 ที่อเมริกา ที่เป็นที่พบปะกันของสาวก FP ทั้งหลาย ในงานมีการพูดคุยตกลงกันถึงความร่วมมือในการสร้างภาษาใหม่ที่เป็น Open Source ให้เจ๋งกว่า Miranda นั่นแหละครับ ผลลัพธ์คือ Haskell ซึ่งเป็นผลงานของคนออกแบบในทีมที่รวมตัวกันเฉพาะกันหลายคนทีเดียว แต่ Haskell เป็นเพียงนิยามของภาษานะครับ ไม่ใช่คอมไพเลอร์ อิสระครับ ใครก็สร้างคอมไพเลอร์ขึ้นมาได้ ดังนั้นคอมไพเลอร์จึงมีหลายตัว แต่ที่มีชื่อเสียงที่สุดคือ Glasgow Haskell Compiler (GHC) ที่รองรับมาตรฐานของภาษาใหม่ล่าสุดคือ Haskell 2010 ผมขอใช้ตัวนี้เป็นหลัก ไป download ได้จาก http://www.haskell.org/ghc/ รองรับ OS ยอดนิยมได้ครบครับ download แล้ว install เลยครับ

จากนั้นเขียนโปรแกรม

สามบรรทัดแรกเป็นสิ่งที่เราเรียนมา ส่วน บรรทัดที่ 5 นั้นเป็นการสร้างฟังก์ชันทางเข้าที่ชื่อว่า main ซึ่ง main นั้นไม่ใช่ฟังก์ชันพิสุทธิ์นะครับ  Haskell แยกฟังก์ชันออกเป็นสองแบบครับคือ พิสุทธ์และ IO  ซึ่งถ้าไม่แยกก็แสดงผลไม่ได้นะครับ เพราะฟังก์ชันพิสุทธิ์จะเปลี่ยนแปลงหน้าจอไม่ได้ IO เป็น Monad ชนิดหนึ่งช่างมันว่าคืออะไร จำชื่อไว้ก็พอครับ  IO นอกจากแสดงผลได้แล้ว ยังทำงานเรียงบรรทัดแบบ Sequence ได้ครับ เป็นการผสม Imperative เข้ามา ภาษาจะได้ยืดหยุ่น  เราจะสังเกตได้ว่าฟังก์ชัน main ต่างจากฟังก์ชันที่เราเรียนมาคือ มีคำว่า do นั่นแหละครับเป็น IO   บรรทัดที่ 5 เขียนตามนี้ก็แล้วกัน

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

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

ก็จะได้เป็น executable file ถ้าเป็น Windows จะได้ factorial.exe  เอาไปรันได้เลยครับ ถ้าท่านอยากได้ IDE จะได้เขียนโปรแกรมสะดวกหน่อย ก็แนะนำสองตัวครับ คือ Leksah หรือใช้ Eclipse โดยเพิ่ม plugin ชื่อ EclipseFP เข้าไป ลองทดลองด้วยตัวท่านเองนะครับ ทำงานบน OS หลักๆ ได้ทั้งหมดเช่นกัน

พบกันใหม่ครั้งหน้า

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

[Total: 19    Average: 3.7/5]

You may also like...

2 Responses

  1. Kai says:

    ขอบคุณครับ

  2. kulrapat says:

    ขอบคุณมากครับ ที่เขียนบทความที่ดีเช่นนี้ให้ได้อ่าน

Leave a Reply

Your email address will not be published. Required fields are marked *