post นี้อาจทำให้เกิด stack overflow ในสมองคนอ่านได้ (เหมือนที่เกิดกับคนเขียนไปแล้ว)
กลับจาก BarcampBangkok ด้้วยสมองอันหนักอื้ง
สิ่งหนึ่งที่ยังติดใจไม่หายก็คือ source code ของ Haskell หน้าตาแบบนี้
(จาก presentation เรื่อง Yoda in Haskell ของ Ben)
fix f = let x = f x in x
โชคดีที่เหลือบมองเห็น comment ที่ Ben เขาเขียนเหนือ function นี้ มันมีคำว่า Y combinator อยู่ด้วย
เรื่อง Y combinator เคยผ่านตามาหลายครั้งแล้ว แต่ไม่เคยทำความเข้าใจได้สักที
วันนี้เลยได้ฤกษ์การพยายามครั้งใหม่
จากการ search google ก็พบว่า code ข้างบนนั้น มันมีชื่อเรียกว่า
Fixed point combinator
หลักการมันประมาณนี้
เริ่มที่คำว่า Fixed point ก่อน
fix point ก็คือ ค่าที่ทำให้ผลลัพท์ของ function มีคุณสมบัติแบบนี้
f(x) = x
ในทางคณิตศาสตร์ สมมติเรามี function อยู่อันหนึ่งซึ่งมี definition ดังนี้
f(x) = x^2
ค่า fixed point คือ function นี้ก็คือ 0 และ 1
เพราะ 0^2 == 0 และ 1^2 = 1
ใน functional language ทุกอย่างเป็น function
ดังนั้น เมื่อมี function ก็แสดงว่า มันก็ต้องมี fixed point ได้เหมือนกัน
ลองนึกถึง higher-order function f ที่รับ parameter เป็น function
มันก็ควรจะมี fixed point function p ซึ่ง
f(p) = p
Y combinator ก็คือ function g ซึ่งรับ parameter เป็น function f
ผลลัพท์ที่ได้ ก็คือ function p ซึ่งเป็น fixed point ของ function f
p = g(f), f(p) = p
ลองอ่านคำอธิบาย contract ของ Y combinator เทียบกับ function ข้างบน
Give me myself and a higher order function f, and I’ll return to you a function that is a fixed point of f.
ถ้าลองแทน function ข้างบนไปมา ก็จะได้
f(g(f)) = g(f)
อ้าจ้องไปจ้องมา แล้วมันก็คือ let x = f x in x นั่นเอง
ประเด็นหลักๆของไอ้ Fix ก็คงจะอยู่ที่เรื่อง Lambda expression
เนื่องจากเราไม่สามารถเขียน recursive function ในรูป lambda expression ได้
ใครอยากรู้ลองอ่านไอ้นี่เอาแล้วกัน
http://en.wikipedia.org/wiki/Lambda_abstraction#Recursion
ลองดูตัวอย่าง่ factorial บ้าง
ปกติเราเขียน factorial อย่างนี้
fact n = if n == 0 then 1 else n * fact (n-1)
ลองปรับ form ให้เป็น lambda expression โดยสร้าง function genfact ขึ้นมา
genfact f n = if n == 0 then 1 else n * f(n-1)
ลอง apply fix เข้าไป
fix genfact 3 = fact (fix genfact) 3
= 3 * ((fix genfact) 2)
= 3 * (genfact (fix genfact) 2)
= 3 * 2 * ((fix genfact) 1)
= 3 * 2 * 1 * ((fix genfact) 0)
= 3 * 2 * 1 * 1
= 6
พอแล้ว stack ผม overflow แล้ว
9 comments:
โพสนี้เล่นเอาสมองหยักจนหงิกเลย - -"
โอ้เบน โอ้เบน
หลังจากกลับมาผมก็นั่งหาข้อมูลเรื่อง Y combinator ก็ได้อ่านที่เดียวกับ link ของ พี่นั่นแหละครับ ก็พอจะเข้าใจว่าทำให้เขียน lambda expression แบบ recursive ได้ แต่ว่า
ที่ยังสงสัยตอนนี้ก็คือมันต่างกันอย่างไรบ้างกับการที่เราเขียน recursive แบบธรรมดาที่มันอ่านได้ง่ายกว่า ตัวอย่างเช่น
fact 0 = 1
fact n = n * fact(n-1)
แบบนี้หนะครับ
por: มีอีกประเด็นหนึ่งก็คือ ตัว combinator เหมาะกับพวก anonymous function มากกว่า (anonymous function มันอยู่ใน form ของ lambda expression)
ผมเห็นในหนังสือพวก little scheme เขาพยายามสอนให้เรา ลดรูป helper function ให้อยู่ในแบบ anonymous
คงเป็นประเด็นเรื่อง namespace ที่ถ้าทุกอย่างประกาศเป็น name function หมด มันก็จะ รก และจัดการยากขึ้น (name มันจะอยู่ใน global space)
ใน reddit มีคนพูดถึง
I've used a custom Y-like combinator a couple of times. I have a parser combinator library in Ocaml, which uses a custom recursion operator to detect infinite loops arising from left-recursion and breaks out of them. I have also written a pickling/unpickling library in ML based on Andrew Kennedy's pickling combinators paper that uses a custom recursion operator also. I've also done the memoization trick that doliorules describes, as well.
อ่านแล้วตัว memoization ค่อนข้างจะไกล้เคียงกับชีวิตจริงเราหน่อย ลองอ่านอันนี้ดู (อ่านแล้วปวดกบาลมาก)
http://okmij.org/ftp/Computation/overriding-selfapplication.html
เอกสารนี้ ก็อ่านแล้วดูเข้าใจมากขึ้น(อีกหน่อยหนึ่ง)
http://www.dreamsongs.com/Files/WhyOfY.pdf
อันนี้ก็เขียนดี
http://www.seas.upenn.edu/~sweirich/cse340/04/why_of_y.ps
ทุกครั้งที่สอน lambda calculus ก็จะข้ามเรื่องนี้ตลอด (อิอิ) เพราะว่าตัวเองก็ยังมึน ๆ อยู่เหมือนกัน
ขนาด John McCarthy ตอนที่ design LISP ก็ยังนึกไม่ถึงว่า lambda expression สามารถเขียน recursive function ได้ โดยไม่ต้องพึ่งพาอะไรอย่างอื่น (ก็ด้วย Y-Combinator นี่แหล่ะ) เขาเลยต้องมี letrec อยู่
ผมว่าสำหรับผม (ที่พิจารณาเชิงทฤษฎี) แล้วประเด็นว่า lambda calculus นิยาม recursive function ได้ ค่อนข้างสำคัญ เพราะว่าเป็นการบอก "พลัง" ของภาษา
อิอิ เดี๋ยวขอเก็บลิงก์พี่ป๊อกเรื่องนี้ไว้ด้วยเลย ขอบคุณคร้าบ
โห ชอบมากๆ แบบว่ากำลังสนใจอย่างแรง
ผมจำได้ว่าอ่านบล็อกอันนี้ห่างกันปีกว่าๆ เพิ่งเข้าใจเมื่อตะกี้ สุดยอด
เพิ่งอ่าน haskell จบ แล้วก็สงสัยเรื่อง recursive ของ lambda เอง ... หาไปหามาโผล่ที่นี่ได้ไงไม่รู้ ขอบคุณนะฮะ -/\-
Post a Comment