Friday, February 01, 2008

วันโชคร้ายของจักรยาน

ช่วงนี้หลังจากย้ายบ้านไปอยู่แถวเกษตร-นวมินทร์แล้ว
ผมก็ขี่จักรยานไปทำงานทุกวัน
ระยะทางกำลังดี ก็คือประมาณ 5 โล
ทำให้เหงื่อออกไม่เยอะ


View Larger Map

ขาไปทำงาน ส่วนใหญ่จะขี่แบบเรื่อยๆเฉื่อยๆ เพราะพึ่งกินอิ่ม
ส่วนขากลับนี่ ทางมันตรง ก็เลยใส่เต็มที่ ลมออกหูทุกวัน (เหนื่อย)

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

หลังจากปะเสร็จก็ออกมาอีกครั้ง
ปั่นมาถึงแถววังหิน
คราวนี้ โซ่ขาด
โชคดีได้ร้านซ่อมมอเตอร์ไซด์แถวนั้น จัดต่อโซ่ให้

ปล. เมื่อต้นอาทิตย์ ขี่จักรยานไปเจอเจ้าปั้นเหน่งกำลังข้ามถนน
สอบถามได้ความว่า codegent ตั้งอยู่แถวนี้ด้วย
เห็นชุดทำงานมันแล้ว ต้องอิจฉา บริษัทอะไรใส่เสื้อกล้ามโชว์รักแร้ไปทำงานได้ด้วย

Related link from Roti

Monday, January 28, 2008

Y combinator in BarcampBangkok

คำเตือน
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 แล้ว

Related link from Roti