Lambda Calculus เขาว่าเป็นพ่อทุกสถาบันแห่งการคำนวณ EP.01: นิยาม และองค์ประกอบพื้นฐานของ Lambda Calculus
Disclaimer !!
ตัวผมเองนั้นจัดตัวเองอยู่ในผู้ที่มีความสนใจในคณิตศาสตร์ ไม่ใช่ผู้เชี่ยวชาญ และ ผมอยากจะเขียน Blog นี้ออกมาให้ตัวเอง (และคนอื่น ?) อ่านแล้วเข้าใจได้ไม่ยากให้มากที่สุด ดังนั้นผมจึงไม่สามารถรับประกันในรายละเอียด หรือ ความถูกต้องอย่างถี่ถ้วนภายในบทความได้ วิธีที่ดีที่สุดในการที่คุณจะทำความเข้าใจมันคือ ให้คุณลองเอา Keyword หรือบางอย่างที่ผมเขียนใน Blog นี้ไปค้นหา ศึกษาต่อ หรือ ถ้าใครที่พอมีความรู้ ความเข้าใจมาอ่าน หากมีตรงไหนที่ขาดตกบกพร่อง หรือ อยากเสริม ก็สามารถเข้ามาคอมเมนต์ใน Blog นี้ได้อย่างสะดวก ขออย่างเดียวคือขอให้เราแลกเปลี่ยนกันอย่างเป็นมิตรที่ดีต่อกันก็พอ และผมแนะนำคนที่มาอ่านว่าถ้าหากคุณอ่าน Blog นี้แล้วเจอว่ามันมีคอมเมนต์ ก็แนะนำให้ลองไปอ่านในคอมเมนต์ด้วยเผื่อจะมีคนมาเมนต์ตามที่บอกไปข้างต้น จะได้ทำให้พวกท่านได้รับข้อมูล ความรู้ที่หลากหลาย ครอบคลุมมากขึ้นนะครับ :)
เกริ่น
เนื่องจากว่าผมได้มีโอกาสมาศึกษา Functional Programming อย่างจริงจังด้วยความเนิร์ดส่วนตัวที่เห็นว่ามันเป็นศาสตร์คอมพิวเตอร์ที่มีการหยิบยืมคอนเซปต์ของ Pure Mathematics มาใช้อย่างจัดเต็มประมาณนึง บวกกับเห็นโอกาสหลายๆอย่างในแวดวง Software Developer / Computer Science ในยุคปัจจุบัน ถ้าหากมีความเข้าใจ Functional Programming หรือ Functional Programming Language เลยคิดว่าศึกษามันอย่างจริงจังไปเลยดีกว่า
หลังจากที่ได้ศึกษาด้วยตัวเองมาสักพัก ผมพบว่ามันมีเนื้อหาทางคณิตศาสตร์น่าสนใจ ที่เกี่ยวข้องกับ Functional Programming อยู่หลายอย่าง แต่ผมจะแตกออกมาหลักๆก็คือ Lambda Calculus, Abstract Algebra, Category Theory, Type Theory (อาจจะมี Homotopy Theory กับ Homotopy Type Theory ด้วยถ้าไหว แต่ขอดูอีกทีดีกว่า) แล้วก็ตัว Concept ของ Functional Programming เอง ซึ่งถ้าผมเข้าใจในเนื้อหามันได้ประมาณนึง และมีเวลา ไม่ขี้เกียจ ก็อยากจะเขียนสรุปทุกๆหัวข้อพวกนี้ไว้เท่าที่ตัวเองตามเนื้อหาของมันไหวเลยครับ :)
Lambda Calculus ?
เห็นคำว่า Calculus โดยสามัญสำนึกของเด็กไทย ที่ผ่านการศึกษาระดับมัธยมปลายเป็นขั้นต่ำมา ผมว่าหลายคนน่าจะนึกถึง Limit, Differentiate, Integral ถั่วงอก dx/dy อะไรแบบนี้แน่ๆเลยใช่ไหมล่ะ! ผมรู้นะ!
แต่จริงๆแล้วในหัวข้อทางคณิตศาสตร์เองก็มีส่วนที่ไม่ได้พูดถึงประเด็นข้างต้นที่กล่าวมาขนาดนั้น แต่ก็ใช้คำว่า Calculus เหมือนกัน หนึ่งในนั้นก็คือ Lambda Calculus ไงล่ะ
แล้ว Lambda Calculus จริงๆแล้วมันคืออะไรล่ะ ?
Lambda Calculus คือโมเดลทางคณิตศาสตร์รูปแบบหนึ่งที่พูดถึง 3 ส่วนนี้ครับ
- ) Variable หรือ ตัวแปร
- ) Abstraction หรือ Lambda Abstraction ก็คือการเขียนให้อยู่ในรูปคล้ายๆกับฟังก์ชัน
- ) Application หรือ การประยุกต์ตัวแปร หรือ Expression เข้ากับ Abstraction
นักคณิตศาสตร์ท่านหนึ่งที่ชื่อ Alonzo Church (คนมักจะรู้จักท่านนี้ในฐานะ Supervisor ของบิดาแห่งคอมพิวเตอร์อย่าง Alan Turing) ได้คิดค้นหลักการนี้ขึ้นมา ซึ่งมีหัวใจสำคัญคือการคำนวณด้วยการแทนค่า Variable ลงใน Abstraction ผ่าน Application ซึ่งเราจะลงรายละเอียดคำเหล่านี้ในหัวข้อถัดไป
ที่ผมขึ้นชื่อบทความว่าเป็นพ่อทุกสถาบันแห่งการคำนวณ เพราะมันเคยมีประโยคที่พูดถึง Lambda Calculus ประมาณว่า
ทุกอย่างที่คำนวณได้ สามารถเขียนรูปแบบการคำนวณให้อยู่ใน Form ของ Lambda Calculus ได้เสมอ หรือก็คือ ทุกอย่างที่คำนวณได้ สามารถคำนวณได้ด้วย Lambda Calculus ได้เสมอนั่นแหละ
ซึ่งเราจะขยายความถึงการนำรูปแบบของ Lambda Calculus ไปใช้ในการคำนวณในหัวข้อต่างๆทางคณิตศาสตร์ได้อย่างไร ในบทความถัดๆไป
Variable
Variable หรือ ตัวแปร ในที่นี้เราพูดถึงตัวแปรปกติที่เราเข้าใจกันเลยอย่างเช่น X, Y หรือ ในหัวข้ออาจจะมีการพูดถึง True, False (Boolean) ซึ่งพวกนี้ก็นับว่าเป็น Variable ได้เช่นกัน เนื่องจากมีการแทนค่าตัวแปรเหล่านี้ได้ด้วย Expression หรืออยู่ในรูป Abstraction ซึ่งเราจะพูดถึงกันต่อไป
Abstraction
การเขียนในรูปแบบ Abstraction ในบริบทหัวข้อ Lamda Calculus จะมีรูปร่างประมาณนี้ครับ
λ<Parameter 1>.λ<Parameter 2>.<ไล่ประมาณนี้ไปเรื่อยๆ>.λ<Parameter n>.<Return Expression>
ยกตัวอย่างเช่น
- λx.x เทียบเท่ากับ f(x) = x
- λx.λy.x (สามารถเขียนในรูปย่อได้ว่า λxy.x) เทียบเท่ากับ f(x)(y) = x (ไม่ใช่ f(x, y) = x เดี๋ยวจะลงรายละเอียดเพิ่มเติมในหัวข้อ Currying)
ใช่ครับ การเขียน Lambda Abstraction มันจะมีลักษณะคล้ายๆกับการเขียนฟังก์ชันในหัวข้อเรื่องความสัมพันธ์ และฟังก์ชันนั่นแหละครับ
Application
การนำตัวแปร หรือ Expression ไปประยุกต์ใช้กับ Abstraction (หรือ Function)
ยกตัวอย่างเช่น
- (λx.x 2) มีความหมายว่าให้เอาตัวแปร 2 (2 ใน Lambda Calculus ให้เรานับว่าเป็นตัวแปรตัวหนึ่ง เพราะ Lambda Calculus จะพูดถึงตัวแปร และ การดำเนินการเป็นหลักเท่านั้น) ไปแทนที่ตัวแปร x ใน Abstraction λx.x ก็จะได้ผลลัพธ์มาเป็น 2 (เพราะว่าเราเอา 2 ไปแทน x แล้วใน Abstraction มันรับ parameter เป็น x จากนั้นก็ return x ออกมาเลย เราแทน x เป็น 2 แปลว่า Abstraction ดังกล่าวก็ Return ค่าออกมาเป็น 2 นั่นเอง ผมอธิบายชวนงงไปไหมหว่า ?) อารมณ์ประมาณว่า f(x) = x เราแทน x = 2 ก็ได้ว่า f(2) = 2 ก็คือผลลัพธ์ของ f(2) ก็คือ 2 นั่นแหละ
- (λx.λy.xy 2 3) => เอา 2 ไปแทนค่าใน x (แทนค่าตามลำดับ) ได้เป็น (λ2.λy.2y 3) => (λy.2y 3) เอา 3 ไปแทนค่า y ได้เป็น (λ3.23) => 23 (ให้มองว่าเราเอา 2 กับ 3 มาประกบกันเฉยๆ ไม่ใช่ตัวเลข 23 ที่อ่านว่า ยี่สิบสาม นะ)
อธิบายให้เข้าใจ (หรือเปล่า ?) ก็คือ Application จะประกอบไปด้วย Expression ฝั่งซ้าย ซึ่งจะเป็น Abstraction หรือไม่ก็ Variable ที่แทนค่าเป็น Abstraction ได้ และ Expression ฝั่งขวา (Expression แต่ละฝั่งถูกคั่นผ่าน Whitespace นะ) เราก็แค่เอา Expression ทางขวา ไปแทนเป็นค่าใน Parameter ใน Abstraction แล้วก็เอาไปแทนตัวแปรเดียวกันใน Return Expression ของตัว Abstraction ก็จะได้ผลลัพธ์ของ Abstraction นั้นออกมาเป็น Return Expression ที่ได้รับการแทนค่าเรียบร้อยแล้ว เช่น
Currying (แถม)
เมื่อกี้เราติดค้างกันไปว่าทำไม λx.λy.x เวลามองเป็นฟังก์ชันทางคณิตศาสตร์ว่าเป็น f(x)(y) = x (อ่านว่า ฟังก์ชันที่รับพารามิเตอร์เป็น x แล้วได้ผลลัพธ์เป็นฟังก์ชันที่รับพารามิเตอร์เป็น y แล้วได้ผลลัพธ์เป็น x) แทนที่จะเป็น f(x, y) = x (อ่านว่า ฟังก์ชันที่รับพารามิเตอร์สองตัว เป็น x, y แล้วได้ผลลัพธ์เป็น x)
คอนเซปต์ของการสร้างฟังก์ชันซ้อนกันโดยแต่ละฟังก์ชันจะรับพารามิเตอร์แค่ตัวเดียว เราเรียกมันว่า Currying
สิ่งที่แตกต่างกันระหว่าง Currying Function กับ ฟังก์ชันแบบทั่วไปคืออะไร ?
สมมติว่าเรามีฟังก์ชัน f(x)(y) = x + y ถ้าหากเราแทนค่า x เป็น 5 ฟังก์ชันจะอยู่ในรูป f(5)(y) = 5 + yใช่ไหมครับ
เราสามารถแทนค่า f(5) ในตัวแปรตัวอื่นได้ครับ เช่น plus5 = f(5) ก็จะได้เป็นว่า
f(5)(y) = plus5(y) = 5 + y เราสามารถทำแบบนี้กับ Currying Function แต่เราไม่สามารถทำแบบนี้กับฟังก์ชันอย่าง f(x, y) = x + y (ถ้าเราแทนค่า x เป็น 5 ในฟังก์ชัน ฟังก์ชันนี้ก็จะเป็นแค่ฟังก์ชันที่ยังไม่สามารถหาผลลัพธ์ได้อย่างสมบูรณ์)
และการมองฟังก์ชันเป็น Currying Function ก็จะถูกนำมาใช้ในการตีความ Lambda Abstraction อย่างเช่น
λx.λy.x ก็จะมองว่ามันเป็น Lamda Abstraction ที่รับ x แล้ว return เป็น Lambda Abstraction ที่รับ y แล้ว return เป็น x
เปรียบเทียบ Lambda Calculus Form กับ Javascript Syntax
หัวข้อนี้เป็นส่วนที่ผมขออนุญาตเพิ่มเติมจากเวอร์ชันที่ Publish ไปก่อนแล้ว เพราะเนื้อหาหลายส่วนของบทความนี้ผมอ้างอิงความเข้าใจมาจากวิดีโอ Lambda Calculus — Fundamentals of Lambda Calculus & Functional Programming in JavaScript — YouTube
แล้วส่วนตัวผมรู้สึกชอบที่คุณ Gabriel Lebec (ผู้สอนในวิดิโอ) เปรียบเทียบ Lambda Abstraction กับ Javascript’s Arrow Function แล้วก็เปรียบเทียบ Application กับการใช้งาน Function ใน Javascript ทำให้ผมเข้าใจการทำงานของ Abstraction กับ Application มากขึ้น เลยอาจจะเอาตารางเปรียบเทียบในวิดิโอมาแปะในบทความให้ผู้อ่านได้ทำความเข้าใจกันด้วยครับ
Variable
Application
Abstraction
สรุป
หลักๆแล้ว Lambda Calculus จะพูดถึง Expression ที่อยู่ในรูป Variable, Lambda Abstraction และ Application ตามที่ได้พูดถึงไป ใน Blog ถัดไปเราจะพูดถึงเรื่องของการดำเนินการภายใน Lambda Calculus อย่างลงรายละเอียดให้เห็นจริงๆ ว่าเราจะใช้องค์ประกอบที่กล่าวมาข้างต้น ในการคำนวณออกมาเป็นผลลัพธ์ สำหรับโจทย์การคำนวณต่างๆได้อย่างไร เนื่องจากบทความนี้เราต้องการแค่จะอธิบายถึงนิยาม และ รูปแบบพื้นฐานของ Lambda Calculus ก่อน ขอบคุณครับ
