อะไรคือ Y Combinator?
ถึงตอนนี้เราคงเรียกตัวเองบนแลมบ์ดาเป็นกันแล้ว (ถ้ายังไม่เป็น แนะนำให้อ่านตอนก่อน)
กลับไปดูอีกรอบ จะเห็นว่าตอนเรียกตัวเอง เราจะต้องใส่ชื่อฟังก์ชันตัวเองลงไปเป็นตัวแปรหนึ่งเสมอ
lambda f, x: 1 if x == 0 else x * f(f, x-1)
แล้วถ้าเราไม่อยากทำอะไรอย่างนี้หละ อยากจะเขียนแค่ f(x-1) เหมือนกับการเรียกใช้งานฟังก์ชันตามปรกติทั่วไป จะทำได้มั้ย?
ถอยหนึ่งก้าว กลับไปเขียนแฟคทอเรียลแบบธรรมดาๆ ก่อน
f = lambda x: 1 if x == 0 else x * f(x-1)
ฟังก์ชันนี้ยังคงสามารถเรียกใช้ได้ เนื่องจากว่าเราจองชื่อ f ไว้ให้มันแล้ว (ซึ่งไม่ใช่สิ่งที่เราต้องการ) นั่นหมายความว่าชื่อ f ต้องมีปรากฏอยู่ในขอบเขตนี้จึงจะเรียกตัวเองได้ และมันมีอีกวิธีนึงที่จะทำให้ f ปรากฏอยู่ภายในขอบเขตนี้ได้โดยไม่ต้องจองชื่อหรือส่งผ่านเป็นตัวแปรในขอบเขตเดียวกัน คือ
lambda f: lambda x: 1 if x == 0 else x * f(x-1)
แต่การประกาศเช่นนี้จะทำให้เราไม่สามารถใช้ฟังก์ชันได้ทันที เพราะเราต้องเอาฟังก์ชั่นนี้ส่งไปเป็นตัวแปรให้ตัวมันเองเรื่อยๆ เช่น ถ้าเราต้องการหา $5!$ เราต้องเขียนออกมาอย่างนี้
(lambda f: lambda x: 1 if x == 0 else x * f(x-1))(
(lambda f: lambda x: 1 if x == 0 else x * f(x-1))(
(lambda f: lambda x: 1 if x == 0 else x * f(x-1))(
(lambda f: lambda x: 1 if x == 0 else x * f(x-1))(
(lambda f: lambda x: 1 if x == 0 else x * f(x-1))(
(lambda f: lambda x: 1 if x == 0 else x * f(x-1))(
(lambda whatever: 42)
)
)
)
)
)
)(5) # i know, its a sin writing lisp-sy code with c style indentation
ซึ่งก็คือเราต้องซ้อนการเขียน lambda f: ... ด้วยตนเอง ในกรณีของ $5!$ นั้นเราต้องซ้อนไปอย่างน้อยๆ ห้า(บวกหนึ่ง)ครั้ง และยิ่งต้องการหาค่าแฟคทอเรียลสูงๆ เราก็ยิ่งต้องซ้อนมันมากขึ้นเป็นเงาตามตัว
นั่นหมายความว่าเราต้องการอะไรซักอย่างที่จะทำหน้าที่ส่งผ่านฟังก์ชันที่นิยามการเรียกตัวเองต่อไปเรื่อยๆ เป็นอนันต์ครั้งโดยอัตโนมัติ นี่คือแนวคิดของคอมบิเนเตอร์จุดตรึง (fixed-point combinator) โดยมีตัวหนึ่ง (เสียดายที่ไล่เองไม่ออก1) ที่เป็นมีชื่อเสียงเป็นที่รู้จักกันมากคือ Y combinator ซึ่งเขียนเป็นโค้ด Python2 ได้ดังนี้
Y = lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v)))
หรือนิยามทางคณิตศาสตร์ว่า $Y = \lambda f.(\lambda x.f(x\;x))(\lambda x.f(x\;x))$ ที่ไม่ต้องเขียนตัวแปร $v$ ห้อยท้าย
และเมื่อเราสำรวจการทำงานของมัน จะเห็นได้ว่า
\[\begin{align} Y\;g &= \Big( {\color{blue}\lambda f}.\big(\lambda x.{\color{blue}f}(x\;x)\big) \; \big(\lambda x.{\color{blue}f}(x\;x)\big) \Big) \; {\color{red}g} \\ &= \big(\lambda x.{\color{green}g}(x\;x)\big) \; \big(\lambda x.{\color{green}g}(x\;x)\big) \\ &= \big({\color{blue}\lambda x}.g({\color{blue}x}\;{\color{blue}x})\big) \; {\color{red}\big(\lambda x.g(x\;x)\big)} \\ &= g\Big( {\color{green}\big(\lambda x.g(x\;x)\big)}\;{\color{green}\big(\lambda x.g(x\;x)\big)} \Big) \\ &= g\Big( \big(\lambda x.{\color{green}g}(x\;x)\big)\;\big(\lambda x.{\color{green}g}(x\;x)\big) \Big) \\ &= g\Big( \Big( {\color{blue}\lambda f}. \big(\lambda x.{\color{blue}f}(x\;x)\big)\;\big(\lambda x.{\color{blue}f}(x\;x)\big) \Big) \; {\color{red}g} \Big) \\ &= g \big( Y\;g \big) \\ &= g \big( g \big( Y\;g \big) \big) = g \big( g \big( g \big( Y\;g \big) \big) \big) = g \big( g \big( g \big( g \big( \cdots \big) \big) \big) \big) \end{align}\]วิธีเอามาใช้งานก็ไม่ยุ่งยาก เพียง
(lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v))))( # Y
lambda factorial: # function name
lambda n: 1 if n == 0 else n * factorial(n-1) # function definition
)(5) # applying argument
ลองเปลี่ยนมาหาเลขฟีโบนัชชีบ้าง ก็แค่เปลี่ยนเป็น
(lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v))))(
lambda fib:
lambda n: n if n <= 1 else fib(n-1) + fib(n-2)
)(5)
ง่ายจริงป่ะ?
-
ถ้าใครติดใจว่าเราได้ฟังก์ชันหน้าตานี้มายังไง แนะนำให้อ่านบทความของสรวีย์ที่จะพาเราไปค่อยๆ ไล่แกะการเรียกตัวเองจนได้พจน์ Y combinator ออกมาในที่สุด ↩
-
จริงๆ แล้วส่วนโค้ดนั้นคือ Z combinator ซึ่งมีจุดแตกต่างตรงที่ต้องส่งค่า
x(x)(v)ในทันที ↩
Revision notes:
- December 12, 2022:
เพิ่มลิงก์ไปยังเว็บของสรวีย์
author