Y combinator ดูเหมือนจะเป็นเวทมนตร์มหัศจรรย์ที่ทำให้เราสามารถเขียนฟังก์ชันเวียนเกิด (recursive function) ในแคลคูลัสแลมบ์ดา (lambda calculus) ได้ เนื่องจากความมหัศจรรย์ของมัน หลาย ๆ คนจึงพยายามที่จะอธิบายว่ามันคืออะไรและทำงานได้อย่างไร แต่เรารู้สึกว่าคำอธิบายส่วนใหญ่นั้นน่าผิดหวัง เพราะมักจะกำหนด Y combinator ขึ้นมาตั้งแต่แรกและเพียงแค่แสดงให้เห็นว่ามันทำงานถูกต้อง ซึ่งไม่ได้แสดงให้เห็นว่าเราจะสามารถคิดหา Y combinator ขึ้นมาเองได้อย่างไร คำอธิบายอีกจำพวกพยายามที่จะตอบโจทย์นี้ แต่ก็มักจะมีประโยคเช่น “เราไม่รู้ว่าเราควรจะใส่อะไรเข้าไปเป็นพารามิเตอร์ของฟังก์ชันนี้ ทำไมถึงไม่ลองใส่ตัวเองเข้าไปดูล่ะ! และเห็นไหมว่ามันทำงานได้อย่างที่เราต้องการ!” ซึ่งเรารู้สึกว่ามันควรจะมีวิธีอธิบายที่ไม่ต้องใช้การทดลองมั่วแบบนี้ได้ จึงเป็นที่มาของบทความนี้

บทนำ #

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

ถึงแม้ว่าบทความนี้จะเกี่ยวกับแคลคูลัสแลมบ์ดา แต่เราจะใช้ภาษาโปรแกรมจริง ๆ ในการอธิบายเพื่อให้เข้าใจง่ายขึ้น ในที่นี้ เราจะใช้ภาษา Racket
เราเลือกที่จะใช้ภาษา Racket เพราะว่า
  • Racket ไม่มีการตรวจสอบชนิดข้อมูลล่วงหน้า (static type checking) ซึ่งส่วนมากแล้วมักจะเคร่งครัดมากเกินไปและตัดสินว่าโปรแกรมที่ใช้ Y combinator มีข้อผิดพลาดทางชนิดข้อมูล
  • Racket มีกฎเกี่ยวกับขอบเขตตัวแปรที่เรียบง่ายและใกล้เคียงกับแคลคูลัสแลมบ์ดา ไม่เหมือนภาษาเช่น Python และ JavaScript ซึ่งมีกฎเกี่ยวกับการยกตัวแปรขึ้น (variable hoisting) ที่ซับซ้อน และทำให้โปรแกรมเช่น const f = () => f(); ที่ดูเหมือนไม่น่าจะมีการเรียกซ้ำ มีการเรียกซ้ำเกิดขึ้น
แต่ภาษาอื่นก็อาจจะใช้ได้เหมือนกัน

สำหรับบทความนี้ ผู้อ่านควรจะมีความคุ้นเคยกับทฤษฎีภาษาโปรแกรมเบื้องต้น แต่เราจะพยายามลิงก์ไปยังบทความต่าง ๆ เพื่อให้ผู้อ่านที่ไม่มีพื้นฐานสามารถตามได้

เพิ่มการเรียกซ้ำ #

ใน Racket เราสามารถเขียนโค้ดเพื่อคำนวณหาค่า $3! + 4!$ ได้อย่างง่ายดาย
ภาษา Racket มีภาษาย่อยอยู่มากมาย ในบทความนี้เราจะใช้ภาษา Racket มาตรฐาน (#lang racket) เป็นหลัก ดังนั้นเราจะไม่เขียนบรรทัดระบุภาษาดังกล่าวนับจากโค้ดนี้เป็นต้นไป เว้นเสียแต่ตอนที่เราจะใช้ภาษาย่อยอื่น ๆ

1
2
3
4
5
6
7
#lang racket

(letrec ([fact (λ (n)
                 (case n
                   [(0) 1]
                   [else (* n (fact (- n 1)))]))])
  (+ (fact 3) (fact 4)))
30

เราสามารถนิยามฟังก์ชันเวียนเกิด fact นี้ได้ เพราะว่า letrec
อ่าน (letrec ([‹x› ‹v›]) ‹e›) ว่า “ให้ ‹x› เป็นฟังก์ชันเวียนเกิด ‹v› และคืนค่า ‹e›
อนุญาตให้เราสามารถอ้างถึง fact ข้างในฟังก์ชันแลมบ์ดาซึ่งจะกลายมาเป็น fact เองในอนาคต

แต่ปัญหาคือแคลคูลัสแลมบ์ดาไม่มี letrec! อันที่จริงแล้ว Racket สร้างคำสั่ง letrec โดยใช้การเปลี่ยนข้อมูล (mutation)
ตัวอย่างเช่น:
1
2
3
4
5
6
7
(let ([fact "dummy-value"])
  (begin
    (set! fact (λ (n)
                 (case n
                   [(0) 1]
                   [else (* n (fact (- n 1)))])))
    (+ (fact 3) (fact 4))))
ซึ่งก็ไม่มีในแคลคูลัสแลมบ์ดาเช่นเดียวกัน ฉะนั้นแล้วเป้าหมายของเราคือการเขียนฟังก์ชัน fact ใน Racket โดยไม่ใช้คำสั่ง letrec และการเปลี่ยนข้อมูล

เราจะลองแก้โค้ดแบบง่าย ๆ ตรงไปตรงมากันก่อน

1
2
3
4
5
(let ([fact (λ (n)
              (case n
                [(0) 1]
                [else (* n (fact (- n 1)))]))])
  (+ (fact 3) (fact 4)))
fact: unbound identifier in: fact

เราเพียงแค่เปลี่ยน letrec ให้กลายเป็น let
อ่าน (let ([‹x› ‹v›]) ‹e›) ว่า “ให้ ‹x› เป็นค่า ‹v› และคืนค่า ‹e›
ในขณะที่ letrec และ let ดูคล้าย ๆ กัน let ไม่มีความสามารถที่จะอนุญาตให้เราอ้างถึง fact ข้างในฟังก์ชันแลมบ์ดาที่จะกลายมาเป็น fact เองในอนาคต อันที่จริงแล้ว (let ([‹x› ‹v›]) ‹e›) ไม่ได้เพิ่มพลัง (expressive power) ใด ๆ ให้กับแคลคูลัสแลมบ์ดาทั้งสิ้น เนื่องจากความหมายของมันเทียบเท่าทุกประการกับ ((λ (‹x›) ‹e›) ‹v›) ซึ่งเป็นพจน์ในแคลคูลัสแลมบ์ดา บางภาษาโปรแกรมนับให้ let เป็นเพียง syntactic sugar และคอมไพล์ (let ([‹x› ‹v›]) ‹e›) ให้กลายเป็น ((λ (‹x›) ‹e›) ‹v›) ก่อนที่จะเริ่มรันโปรแกรม

โค้ดข้างต้นมีข้อผิดพลาดเนื่องจากตัวแปร fact ที่เราไฮไลท์ไว้ไม่ได้ถูกนิยามในขอบเขตที่เหมาะสม (unbound) เราควรจะแก้ไขข้อผิดพลาดนี้อย่างไรดี? ลองมาดูตัวอย่างอีกอันหนึ่งที่เรียบง่ายมากกว่ากันดู

1
2
3
(let ([f (λ (n) (+ n c))])
  (let ([c 1])
    (f 99)))
c: unbound identifier in: c

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

1
2
3
(let ([f (λ (c n) (+ n c))])
  (let ([c 1])
    (f c 99)))
100

เราจะแก้ไขปัญหาเกี่ยวกับตัวแปร fact ที่ไม่ได้ถูกนิยามในขอบเขตที่เหมาะสมด้วยวิธีเดียวกัน สังเกตว่าตัวแปร fact ถูกนิยามอย่างอย่างถูกต้องข้างใน let ฉะนั้นเราสามารถที่จะส่ง fact เข้าไปข้างในฟังก์ชันแลมบ์ดาได้!

1
2
3
4
5
(let ([fact (λ (fact n)
              (case n
                [(0) 1]
                [else (* n (fact (- n 1)))]))])
  (+ (fact fact 3) (fact fact 4)))
fact: arity mismatch;
the expected number of arguments does not match the given number
 expected: 2
 given: 1
 arguments...:

แต่ปรากฏว่าโค้ดข้างต้นก็ยังมีปัญหาอยู่ดี: fact ตอนนี้เป็นฟังก์ชันที่มี 2 พารามิเตอร์ ฉะนั้นแล้วการเรียกฟังก์ชันที่เราไฮไลท์ไว้ ซึ่งส่งพารามิเตอร์เข้าไปเพียงแค่ตัวเดียว จึงส่งผลให้เกิดข้อผิดพลาด ฟังก์ชั่น fact ต้องการอะไรเป็นพารามิเตอร์แรก? คำตอบคือฟังก์ชัน fact!

1
2
3
4
5
(let ([fact (λ (fact n)
              (case n
                [(0) 1]
                [else (* n (fact fact (- n 1)))]))])
  (+ (fact fact 3) (fact fact 4)))
30

ด้วยทริคข้างบนนี้ ดูเหมือนว่าเราจะสามารถเขียนฟังก์ชันเวียนเกิดใด ๆ ในภาษาที่ไม่มี letrec ได้ด้วยวิธีการ ก. ดังต่อไปนี้

  1. เริ่มต้นด้วยการเขียนฟังก์ชันเวียนเกิด $f$ โดยใช้ letrec
  2. เปลี่ยน letrec ไปเป็น let
  3. ในทุก ๆ จุดที่เราเรียก $f$ ให้เพิ่ม $f$ เข้าไปเป็นพารามิเตอร์แรก
  4. ในฟังก์ชันแลมบ์ดา $f$ ให้รับ $f$ เพิ่มเข้ามาเป็นพารามิเตอร์แรก
วิธีการ ก.

แต่วิธีการ ก. ถูกต้องเสมอไปหรือเปล่า? ลองพิจารณาโค้ดต่อไปนี้ดู

1
2
3
4
5
6
(letrec ([fact (λ (n)
                 (case n
                   [(0) 1]
                   [else (* n (fact (- n 1)))]))])
  (let ([fact2 fact])
    (+ (fact2 3) (fact2 4))))
30

แปลงกลายเป็น

1
2
3
4
5
6
(let ([fact (λ (fact n)
              (case n
                [(0) 1]
                [else (* n (fact fact (- n 1)))]))])
  (let ([fact2 fact])
    (+ (fact2 3) (fact2 4))))
fact: arity mismatch;
 the expected number of arguments does not match the given number
  expected: 2
  given: 1
  arguments...:

อย่างที่เราได้เห็น วิธีการ ก. นี้ไม่ถูกต้องเสมอไปซะทีเดียว เพราะถ้า $f$ อยู่ในตำแหน่งที่ไม่ใช่ฟังก์ชัน จะไม่มีการเปลี่ยนแปลงโค้ดที่เหมาะสมเกิดขึ้น แต่โชคยังดีเพราะเราสามารถบังคับให้ทุก ๆ $f$ ที่ปรากฏในโปรแกรมอยู่ในตำแหน่งฟังก์ชันเสมอ! ถ้า $f$ เป็นฟังก์ชันที่รับ $n$ พารามิเตอร์ จะได้ว่า $f$ มีความหมายเทียบเท่า (observationally equivalent) กับ $\lam{x_1 x_2 \dots x_n}{f x_1 x_2 \dots x_n}$ (เมื่อ $f$ ไม่ได้เป็นหนึ่งใน $x_1, x_2, \dots, x_n$)
ความเท่าเทียมกันระหว่าง $f$ กับ $\lam{x_1 x_2 \dots x_n}{f x_1 x_2 \dots x_n}$ เป็นกรณีพิเศษของ $\eta$-equivalence โดยในแคลคูลัสแลมบ์ดา เราสามารถใช้ $\eta$-conversion ที่ไหนก็ได้ เพราะทุก ๆ พจน์มีความหมายเป็นฟังก์ชันแลมบ์ดาหนึ่ง ๆ เสมอ แต่เนื่องจาก Racket มีข้อมูลประเภทอื่นเช่นตัวเลข เราจึงสามารถใช้ $\eta$-conversion ได้อย่างจำกัดเท่านั้น
ดังนั้น หากเราแทรกขั้นตอนเพิ่มระหว่างขั้นที่ 2 กับขั้นที่ 3 ของวิธีการ ก. เพื่อเปลี่ยนทุก ๆ ตัวแปร $f$ ให้กลายเป็น $\lam{x_1 x_2 \dots x_n}{f x_1 x_2 \dots x_n}$ เราจะได้วิธีการ ข. ซึ่งทำงานถูกต้องกับทุก ๆ โปรแกรม

  1. เริ่มต้นด้วยการเขียนฟังก์ชันเวียนเกิด $f$ โดยใช้ letrec
  2. เปลี่ยน letrec ไปเป็น let
  3. เปลี่ยนทุก ๆ ตัวแปร $f$ ให้กลายเป็น $\lam{x_1 x_2 \dots x_n}{f x_1 x_2 \dots x_n}$
  4. ในทุก ๆ จุดที่เราเรียก $f$ ให้เพิ่ม $f$ เข้าไปเป็นพารามิเตอร์แรก
  5. ในฟังก์ชันแลมบ์ดา $f$ ให้รับ $f$ เพิ่มเข้ามาเป็นพารามิเตอร์แรก
วิธีการ ข.

ลองมาใช้วิธีการ ข. ดูกัน!

1
2
3
4
5
6
(letrec ([fact (λ (n)
                 (case n
                   [(0) 1]
                   [else (* n (fact (- n 1)))]))])
  (let ([fact2 fact])
    (+ (fact2 3) (fact2 4))))

แปลงกลายเป็น

1
2
3
4
5
6
(let ([fact (λ (fact n)
              (case n
                [(0) 1]
                [else (* n ((λ (v) (fact fact v)) (- n 1)))]))])
  (let ([fact2 (λ (v) (fact fact v))])
    (+ (fact2 3) (fact2 4))))
30

เยี่ยม!

โอเมกา #

เราจะออกทะเลกันเล็กน้อย จะเกิดอะไรขึ้นถ้าเราใช้การเปลี่ยนแปลงโปรแกรมที่ได้กล่าวไว้ข้างต้นกับฟังก์ชันที่เรียกตัวเองไปเรื่อย ๆ เป็นวงวนไม่รู้จบ?

1
2
(letrec ([diverge (λ () (diverge))])
  (diverge))

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

1
2
(let ([diverge (λ (diverge) (diverge diverge))])
  (diverge diverge))

แคลคูลัสแลมบ์ดาไม่มี let แต่เราสามารถเปลี่ยน let ไปเป็นพจน์ในแคลคูลัสแลมบ์ดาตามที่ได้เคยกล่าวไว้

1
2
((λ (diverge) (diverge diverge))
 (λ (diverge) (diverge diverge)))

พจน์ข้างบนนี้รู้จักกันในชื่อ $\Omega$-combinator ซึ่งเป็นตัวอย่างมาตรฐานในตำราเรียนว่าเป็นพจน์ในแคลคูลัสแลมบ์ดาที่เมื่อรันแล้ว ในแต่ละขั้นจะได้ตัวเองไปเรื่อย ๆ ไม่ได้มีผลลัพธ์ออกมาเป็นค่าข้อมูล

ตามล่าหาครอบครัวของ Y combinator #

ในขณะที่เรารู้วิธีในการเขียนฟังก์ชันเวียนเกิดในแคลคูลัสแลมบ์ดาแล้ว โปรแกรมที่เราเขียนมีรูปร่างไม่คล้ายคลึงกับโปรแกรมดั้งเดิมที่ใช้ letrec มันคงจะดีไม่น้อยถ้าหากมีพจน์ ‹make-recursion› ซึ่งทำให้

1
2
3
4
5
(‹make-recursion›
  (λ (n)
    (case n
      [(0) 1]
      [else (* n (fact (- n 1)))])))

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

1
2
3
4
5
6
(‹make-recursion›
  (λ (fact)
    (λ (n)
      (case n
        [(0) 1]
        [else (* n (fact (- n 1)))]))))

เราจะเรียกฟังก์ชันแลมบ์ดาซึ่งเป็นพารามิเตอร์ของ ‹make-recursion› ว่าตัวสร้างฟังก์ชันเวียนเกิด และสิ่งที่เราอยากได้คือ สำหรับตัวสร้างฟังก์ชันเวียนเกิด ‹recursion-maker› ใด ๆ (‹make-recursion› ‹recursion-maker›) ควรจะกลายมาเป็นฟังก์ชันเวียนเกิดที่เราสามารถใช้งานได้ตามปกติ

เราควรจะเริ่มต้นอย่างไรดี? ถึงแม้ว่าเราจะไม่รู้ว่า ‹make-recursion› มีรูปร่างเป็นอย่างไร แต่เรารู้ว่า ‹fact-maker› มีรูปร่างเป็นอย่างไร ฉะนั้น เราจะพยายามจัดรูปโค้ดที่มีการใช้วิธีการ ข. เพื่อเขียนฟังก์ชันแฟกทอเรียล:

1
2
3
4
5
(let ([fact (λ (fact n)
              (case n
                [(0) 1]
                [else (* n ((λ (v) (fact fact v)) (- n 1)))]))])
  (+ ((λ (v) (fact fact v)) 3) ((λ (v) (fact fact v)) 4)))

ให้กลายเป็นโค้ดที่มีการใช้ ‹fact-maker›:

1
2
3
4
5
6
7
(let ([fact-maker (λ (fact)
                    (λ (n)
                      (case n
                        [(0) 1]
                        [else (* n (fact (- n 1)))])))])
  (let ([fact (‹???› fact-maker)])
    (+ (fact 3) (fact 4))))

ถ้าหากเราสามารถแปลงโค้ดได้สำเร็จ ก็จะได้ว่าช่องว่าง ‹???› คือ ‹make-recursion› ที่เรากำลังตามหา

สำหรับขั้นตอนแรก สังเกตว่าทั้ง fact และ n เป็นพารามิเตอร์ของฟังก์ชันแลมบ์ดาในโค้ดที่เรามี แต่ใน ‹fact-maker› มีฟังก์ชันแลมบ์ดาสองอันแยกกัน ฉะนั้นแล้ว เราสามารถใช้ currying ในการแยกพารามิเตอร์ออกจากกันได้ แน่นอนว่าเราต้องเปลี่ยนการเรียกฟังก์ชันตามให้ถูกต้องด้วยเช่นกัน นั่นคือเราจะเปลี่ยน

1
2
3
4
5
(let ([fact (λ (fact n)
              (case n
                [(0) 1]
                [else (* n ((λ (v) (fact fact v)) (- n 1)))]))])
  (+ ((λ (v) (fact fact v)) 3) ((λ (v) (fact fact v)) 4)))

ไปเป็น

1
2
3
4
5
6
(let ([fact (λ (fact)
              (λ (n)
                (case n
                  [(0) 1]
                  [else (* n ((λ (v) ((fact fact) v)) (- n 1)))])))])
  (+ ((λ (v) ((fact fact) v)) 3) ((λ (v) ((fact fact) v)) 4)))

สำหรับขั้นตอนถัดไป สังเกตว่าในโค้ดปัจจุบันของเรา มี (λ (v) ((fact fact) v)) ปรากฏไปทั่วในตำแหน่งที่จริง ๆ แล้วเราควรจะสามารถใช้ fact ได้ ดังนั้น เราจะบัง (shadow) fact ด้วย (λ (v) ((fact fact) v)) เพื่อจัดรูปให้โค้ดปัจจุบันของเราเหมือน ‹fact-maker› มากขึ้นไปอีก

1
2
3
4
5
6
7
8
(let ([fact (λ (fact)
              (let ([fact (λ (v) ((fact fact) v))])
                (λ (n)
                  (case n
                    [(0) 1]
                    [else (* n (fact (- n 1)))]))))])
  (let ([fact (λ (v) ((fact fact) v))])
    (+ (fact 3) (fact 4))))

ในโค้ดข้างบน ไฮไลท์อันแรกดูคล้ายกับ ‹fact-maker› เป็นอย่างมาก และไฮไลท์อันที่สองก็ดูเหมือนโค้ดที่เราควรจะเขียนเพื่อคำนวณ $3! + 4!$ ทุกประการ สิ่งที่เราควรจะทำเป็นลำดับถัดไปคือเปลี่ยน (let ([fact (λ (v) ((fact fact) v))]) ‹body›) ให้กลายมาเป็น (λ (fact) ‹body›) (โดย ‹body› คือไฮไลท์อันแรก) แล้วก็ย้าย (λ (v) ((fact fact) v)) ออกไปที่อื่น ซึ่งเราสามารถทำได้อย่างง่ายดายด้วยการคอมไพล์ let ให้กลายเป็นพจน์ในแคลคูลัสแลมบ์ดา

1
2
3
4
5
6
7
8
9
(let ([fact (λ (fact)
              ((λ (fact)
                 (λ (n)
                   (case n
                     [(0) 1]
                     [else (* n (fact (- n 1)))])))
               (λ (v) ((fact fact) v))))])
  (let ([fact (λ (v) ((fact fact) v))])
    (+ (fact 3) (fact 4))))

เราทำให้ ‹fact-maker› ปรากฏตัวออกมาสำเร็จ! อันดับถัดไป เราสามารถที่จะดึง ‹fact-maker› ออกมาเป็นตัวแปรชื่อ fact-maker ได้

1
2
3
4
5
6
7
8
(let ([fact-maker (λ (fact)
                    (λ (n)
                      (case n
                        [(0) 1]
                        [else (* n (fact (- n 1)))])))])
  (let ([fact (λ (fact) (fact-maker (λ (v) ((fact fact) v))))])
    (let ([fact (λ (v) ((fact fact) v))])
      (+ (fact 3) (fact 4)))))

เนื่องจากสุดท้ายแล้ว เราอยากให้ ‹make-recursion› เป็นพจน์ในแคลคูลัสแลมบ์ดา แต่ แคลคูลัสแลมบ์ดา ไม่มี let เราจึงจะพยายามรวม (let ([fact ...]) ...) ที่ซ้อนกันสองอันเข้าด้วยกันด้วยการแทนที่แบบตรงไปตรงมา

1
2
3
4
5
6
7
8
9
(let ([fact-maker (λ (fact)
                    (λ (n)
                      (case n
                        [(0) 1]
                        [else (* n (fact (- n 1)))])))])
  (let ([fact (λ (v)
                (((λ (fact) (fact-maker (λ (v) ((fact fact) v))))
                  (λ (fact) (fact-maker (λ (v) ((fact fact) v))))) v))])
    (+ (fact 3) (fact 4))))

สำหรับขั้นตอนสุดท้าย สังเกตว่า ‹make-recursion› ควรจะเป็นฟังก์ชันที่รับ fact-maker เป็นพารามิเตอร์ ฉะนั้น เราจะดึงตัวแปร fact-maker ออกมา

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
(let ([fact-maker (λ (fact)
                    (λ (n)
                      (case n
                        [(0) 1]
                        [else (* n (fact (- n 1)))])))])
  (let ([fact ((λ (fact-maker)
                 (λ (v)
                   (((λ (fact) (fact-maker (λ (v) ((fact fact) v))))
                     (λ (fact) (fact-maker (λ (v) ((fact fact) v))))) v)))
               fact-maker)])
    (+ (fact 3) (fact 4))))
30

ในที่สุดเราก็ทำสำเร็จ! เราค้นพบว่า ‹make-recursion› คือโค้ดที่เราไฮไลท์ไว้

ขั้นตอนที่เราปฏิบัติเพื่อหา ‹make-recursion› จริง ๆ แล้วไม่ได้เฉพาะเจาะจงกับฟังก์ชันแฟกทอเรียลเลย ต่อให้เราใช้ฟังก์ชันเวียนเกิดใด ๆ เป็นจุดเริ่มต้น เราก็จะได้พจน์ที่ $\alpha$-equivalent กับ ‹make-recursion› ที่เรามี ฉะนั้นแล้ว เพื่อที่จะเน้นว่า ‹make-recursion› ไม่ได้เฉพาะเจาะจงกับฟังก์ชันแฟกทอเรียล เราจะเปลี่ยนชื่อตัวแปร ($\alpha$-convert) เพื่อลบการอ้างอิงถึงฟังก์ชันแฟกทอเรียล

1
2
3
4
(λ (f)
  (λ (k)
    (((λ (x) (f (λ (v) ((x x) v))))
      (λ (x) (f (λ (v) ((x x) v))))) k)))

อันที่จริงแล้ว เราสามารถย่อรูป ‹make-recursion› ให้เล็กลงได้ด้วย โดยใช้หลักการเดียวกันที่เราเคยใช้ในเพิ่มการเรียกซ้ำ ว่าถ้าเรารันนิพจน์ $e$ แล้วได้ค่าออกมาเป็นฟังก์ชันที่รับพารามิเตอร์หนึ่งตัว จะได้ว่า $e$ มีความหมายเทียบเท่ากับ $\lam{x}{e x}$ (โดยที่ $e$ ห้ามมีตัวแปร $x$ ที่ไม่ได้ถูกนิยามในขอบเขตที่เหมาะสม) การเปลี่ยนรูปไปมาระหว่าง $e$ กับ $\lam{x}{e x}$ นั้นเป็นที่รู้จักกันในชื่อ $\eta$-conversion และเราสามารถใช้ $\eta$-conversion ในการสร้างพจน์ต่อไปนี้จาก ‹make-recursion› ได้

  • เริ่มจาก ‹make-recursion› หากเราใช้ $\eta$-conversion กับพจน์ที่เราไฮไลท์

    1
    2
    3
    4
    (λ (f)
      (λ (k)
        (((λ (x) (f (λ (v) ((x x) v))))
          (λ (x) (f (λ (v) ((x x) v))))) k)))
    

    เราจะได้

    1
    2
    3
    (λ (f)
      ((λ (x) (f (λ (v) ((x x) v))))
       (λ (x) (f (λ (v) ((x x) v))))))
    

    เป็นผลลัพธ์ ซึ่งเป็นที่รู้จักกันในชื่อ Z combinator ($Z$)

  • เริ่มจาก $Z$ หากเราใช้ $\eta$-conversion กับพจน์ที่เราไฮไลท์

    1
    2
    3
    (λ (f)
      ((λ (x) (f (λ (v) ((x x) v))))
       (λ (x) (f (λ (v) ((x x) v))))))
    

    เราจะได้

    1
    2
    3
    (λ (f)
      ((λ (x) (f (x x)))
       (λ (x) (f (x x)))))
    

    เป็นผลลัพธ์ ซึ่งเป็นที่รู้จักกันในชื่อ Y combinator ($Y$)

‹make-recursion›, $Z$ และ $Y$ เป็น fixed-point combinator โดยคำว่า combinator หมายความว่าพจน์ในแคลคูลัสแลมบ์ดาเหล่านี้ ไม่มีตัวแปรที่ไม่ได้ถูกนิยามในขอบเขตที่เหมาะสม ส่วนคำว่า จุดตรึง (fixed-point) หมายความว่าผลการเรียกฟังก์ชันของ fixed-point combinator บน $f$ นั้น เป็นคำตอบของสมการ $x = f(x)$ ถ้าเราใช้ $Z$ เป็นตัวอย่าง จะได้ว่า $Z(f) = f(Z(f))$ อัตลักษณ์จุดตรึงนี้มีความสำคัญอย่างไร? และ ‹make-recursion›, $Z$ กับ $Y$ แตกต่างกันอย่างไร? เราจะตอบคำถามเหล่านี้ในส่วนถัดไปของบทความนี้

จุดตรึง #

ทำไมเอกลักษณ์จุดตรึง เช่น $Z(f) = f(Z(f))$ ถึงเป็นจริง และเอกลักษณ์นี้มีความสำคัญอย่างไร? เราจะตอบคำถามเหล่านี้ในส่วนนี้ของบทความ โดยเราจะใช้ Z combinator เป็นตัวอย่างหลัก

อันดับแรก เราจะพิจารณาตัวสร้างฟังก์ชันเวียนเกิดจากมุมมองใหม่ ในตามล่าหาครอบครัวของ Y combinator เราได้เห็นตัวสร้างฟังก์ชันเวียนเกิด แต่เรารู้เพียงแค่ว่าสำหรับ ตัวสร้างฟังก์ชันเวียนเกิด ‹recursion-maker› ใด ๆ จะได้ว่า (Z ‹recursion-maker›) จะกลายเป็นฟังก์ชันเวียนเกิด เราสามารถใช้ ‹recursion-maker› ทำอย่างอื่นได้หรือไม่? เราจะพิจารณา ‹fact-maker› เป็นตัวอย่าง

1
2
3
4
5
(λ (fact)
  (λ (n)
    (case n
      [(0) 1]
      [else (* n (fact (- n 1)))])))

What can we pass into $\text{fact-maker}$? It obviously consumes the factorial function! But provided that we don’t have the real factorial function already, the best we can do is to provide any other value instead. Say, we pass in a non-sensible value $42$. This results in:

1
2
3
4
(λ (n)
  (case n
    [(0) 1]
    [else (* n (42 (- n 1)))]))

What we have here is the factorial function that only works on $n = 0$. For $n > 0$, the highlighted $42$ will be used as a function value which results in an error. We will call this function $\text{fact}_0$.

What else can we pass into $\text{fact-maker}$? We just obtained $\text{fact}_0 = \text{fact-maker}(42)$, so we can use it. This results in:

1
2
3
4
(λ (n)
  (case n
    [(0) 1]
    [else (* n (‹fact0› (- n 1)))]))

Again, what we have here is the factorial function that works on $n \le 1$. Let’s call it $\text{fact}_1$. Next, we can pass $\text{fact}_1 = \text{fact-maker}(\text{fact-maker}(42))$ into $\text{fact-maker}$ to get $\text{fact}_2$. We can clearly see the trend here. $\text{fact-maker}^k(42) = \text{fact}_{k-1}$, the factorial function that works on $n \le k - 1$.

In general, any recursion maker $f$ propels the computation one more level deeper.

To get the actual factorial function, which should work for any natural number $n$, we evidently need an infinitely high tower of $\text{fact-maker}$. That is, $\text{fact} = \text{fact}_\infty = \text{fact-maker}(\text{fact-maker}(\text{fact-maker}(\dots)))$.

Note that:

$$\begin{align*}
\text{fact} &= \text{fact-maker}(\text{fact-maker}(\dots))\\
\text{fact-maker}(\text{fact}) &= \text{fact-maker}(\text{fact-maker}(\text{fact-maker}(\dots))) & \text{applying fact-maker}\\
&= \text{fact}\\
\end{align*}$$

which agrees with our definition of $\text{fact-maker}$: applying $\text{fact}$ to $\text{fact-maker}$ produces the actual $\text{fact}$ function.

1
2
3
4
5
(λ (fact)
  (λ (n)
    (case n
      [(0) 1]
      [else (* n (fact (- n 1)))])))

Recall that the Z combinator makes the recursion possible: $\text{fact} = Z(\text{fact-maker})$. Substituting this in the above equation, we obtain that $\text{fact-maker}(Z(\text{fact-maker})) = Z(\text{fact-maker})$.

In general, for any recursion maker $f$, $Z(f) = f(Z(f))$. The importance of this identity is that $Z(f) = f(Z(f)) = f(f(Z(f))) = f(f(f(Z(f)))) = \dots$ which creates an infinite tower of the recursion maker $f$, making recursion possible.

Yet another proof

We can also show that $Z(f) = f(Z(f))$ directly using the definition of $Z$:

$$\begin{align*}
Z &= \lam{f}{(\lam{x}{f (\lam{v}{(x x) v})})(\lam{x}{f (\lam{v}{(x x) v})})} & \\
Z(f) &= (\lam{\color{red}{x}}{f (\lam{v}{(\color{red}{x x}) v})})(\lam{x}{f (\lam{v}{(x x) v})}) & \\
&= f (\lam{\color{blue}{v}}{((\lam{x}{f (\lam{v}{(x x) v})}) (\lam{x}{f (\lam{v}{(x x) v})})) \color{blue}{v}}) & \beta \text{-reduction}\\
&= f ((\lam{x}{f (\lam{v}{(x x) v})}) (\lam{x}{f (\lam{v}{(x x) v})})) & \eta \text{-conversion}\\
&= f (Z(f)) & \\
\end{align*}$$

Y vs. Z #

How are ‹make-recursion›, $Z$, and $Y$ different? We can empirically test them:

  • The original ‹make-recursion›:

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    (let ([make-recursion
           (λ (f)
             (λ (k) (((λ (x) (f (λ (v) ((x x) v))))
                      (λ (x) (f (λ (v) ((x x) v))))) k)))])
      (let ([fact-maker (λ (fact)
                          (λ (n)
                            (case n
                              [(0) 1]
                              [else (* n (fact (- n 1)))])))])
        (let ([fact (make-recursion fact-maker)])
          (+ (fact 3) (fact 4)))))
    
    30
  • The Z combinator:

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    (let ([Z (λ (f)
               ((λ (x) (f (λ (v) ((x x) v))))
                (λ (x) (f (λ (v) ((x x) v))))))])
      (let ([fact-maker (λ (fact)
                          (λ (n)
                            (case n
                              [(0) 1]
                              [else (* n (fact (- n 1)))])))])
        (let ([fact (Z fact-maker)])
          (+ (fact 3) (fact 4)))))
    
    30
  • The Y combinator:

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    (let ([Y (λ (f)
               ((λ (x) (f (x x)))
                (λ (x) (f (x x)))))])
      (let ([fact-maker (λ (fact)
                          (λ (n)
                            (case n
                              [(0) 1]
                              [else (* n (fact (- n 1)))])))])
        (let ([fact (Y fact-maker)])
          (+ (fact 3) (fact 4)))))
    
    Non-terminating

Uh oh.

We derive the Y combinator from the Z combinator via $\eta$-conversion, which intuitively should preserve semantics. Yet something clearly went wrong when we try to use the Y combinator for computing factorials, since the computation doesn’t terminate (while the Z combinator works as expected). In fact, the problem is much worse: any attempt to use Y will always result in an infinite loop in Racket!

Recall the following:

if $e$ evaluates to a function of one argument, then $e$ is มีความหมายเทียบเท่า to $\lam{x}{e x}$ (provided that $x$ does not freely occur in $e$).

and how we convert $Z$:

1
2
3
(λ (f)
  ((λ (x) (f (λ (v) ((x x) v))))
   (λ (x) (f (λ (v) ((x x) v))))))

to $Y$:

1
2
3
(λ (f)
  ((λ (x) (f (x x)))
   (λ (x) (f (x x)))))

In Racket, when we evaluate, say, (Y fact-maker), does (x x) evaluate to a function of one argument? We can manually step through the evaluation to see what’s going on:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
1.  (Y fact-maker)
==> ((λ (f) ((λ (x) (f (x x))) (λ (x) (f (x x))))) fact-maker)

2.  ((λ (f) ((λ (x) (f (x x))) (λ (x) (f (x x))))) fact-maker)
==> ((λ (f) ((λ (x) (f (x x))) (λ (x) (f (x x))))) (λ (fact) ...))

3.  ((λ (f) ((λ (x) (f (x x))) (λ (x) (f (x x))))) (λ (fact) ...))
==> ((λ (x) ((λ (fact) ...) (x x))) (λ (x) ((λ (fact) ...) (x x))))

4.  ((λ (x) ((λ (fact) ...) (x x))) (λ (x) ((λ (fact) ...) (x x))))
==> ((λ (fact) ...)
     ((λ (x) ((λ (fact) ...) (x x))) (λ (x) ((λ (fact) ...) (x x)))))

5.  ((λ (fact) ...)
     ((λ (x) ((λ (fact) ...) (x x))) (λ (x) ((λ (fact) ...) (x x)))))
==> ((λ (fact) ...)
     ((λ (fact) ...)
      ((λ (x) ((λ (fact) ...) (x x))) (λ (x) ((λ (fact) ...) (x x))))))

6.  ((λ (fact) ...)
     ((λ (fact) ...)
      ((λ (x) ((λ (fact) ...) (x x))) (λ (x) ((λ (fact) ...) (x x))))))
==> ((λ (fact) ...)
     ((λ (fact) ...)
      ((λ (fact) ...)
       ((λ (x) ((λ (fact) ...) (x x))) (λ (x) ((λ (fact) ...) (x x)))))))

...

The answer is no! Hence, in Racket, our $\eta$-conversion to turn $Z$ to $Y$ is unsound!

While Racket evaluates the term (Y fact-maker) exactly as described above, we can imagine another way to evaluate the term:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
1.  (Y fact-maker)
==> ((λ (f) ((λ (x) (f (x x))) (λ (x) (f (x x))))) fact-maker)

2.  ((λ (f) ((λ (x) (f (x x))) (λ (x) (f (x x))))) fact-maker)
==> ((λ (x) (fact-maker (x x))) (λ (x) (fact-maker (x x))))

3.  ((λ (x) (fact-maker (x x))) (λ (x) (fact-maker (x x))))
==> (fact-maker ((λ (x) (fact-maker (x x))) (λ (x) (fact-maker (x x)))))

4.  (fact-maker ((λ (x) (fact-maker (x x))) (λ (x) (fact-maker (x x)))))
==> ((λ (fact) ...) ((λ (x) (fact-maker (x x))) (λ (x) (fact-maker (x x)))))

5.  ((λ (fact) ...) ((λ (x) (fact-maker (x x))) (λ (x) (fact-maker (x x)))))
==> (λ (n)
      (case
        [(0) 1]
        [1 (* n (((λ (x) (fact-maker (x x))) (λ (x) (fact-maker (x x))))
                 (- n 1)))]))

In this evaluation trace, (Y fact-maker) successfully evaluates to the factorial function! The difference of these two evaluation traces is due to evaluation strategies, which describes what reducible expression (redex) should be $\beta$-reduced.

Most programming languages including Racket employ the first evaluation strategy presented above, which always evaluates arguments of a function application before the application itself. This strategy is known as call-by-value
The call-by-value strategy in fact is a family of strategies. It still leaves some room for flexibility. For example, the strategy does not specify which one between ((λ (x) x) 1) and ((λ (x) x) 2) should be reduced first when evaluating (+ ((λ (x) x) 1) ((λ (x) x) 2)). Racket particularly always evaluates the leftmost-innermost redex (outside of lambda functions) first.
. As another example for how this strategy works, it would evaluate (double (double 1)) where double is defined as (λ (x) (+ x x)) in the following way:

1
2
3
4
(double (double 1)) ==> (double (+ 1 1))
(double (+ 1 1))    ==> (double 2)
(double 2)          ==> (+ 2 2)
(+ 2 2)             ==> 4

On the other hand, the second strategy presented above calls the function application without waiting for arguments to be evaluated first. This strategy is known as call-by-name. It would evaluate (double (double 1)) in the following way:

1
2
3
4
5
6
(double (double 1))       ==> (+ (double 1) (double 1))
(+ (double 1) (double 1)) ==> (+ (+ 1 1) (double 1))
(+ (+ 1 1) (double 1))    ==> (+ 2 (double 1))
(+ 2 (double 1))          ==> (+ 2 (+ 1 1))
(+ 2 (+ 1 1))             ==> (+ 2 2)
(+ 2 2)                   ==> 4

We have seen that different evaluation stategies might not evaluate a term to the same result. This is disconcerting. Fortunately, the Church-Rosser theorem guarantees that given a term $t$, if two strategies successfully evaluate $t$ to values, then the two values from both strategies are equal, as we can see from the (double (double 1)) example. The only case that two evaluation strategies would evaluate a term to different results is when one of them doesn’t terminate, which is exactly what happens with the Y combinator in the call-by-value strategy.

There are advantages and disadvantages for each evaluation strategies. For instance, the call-by-name strategy has a beautiful property that if a term could be evaluated to a value by some evaluation strategy, then it will be able to evaluate the term to the value as well. This is the reason why the strategy successfully evaluate (Y fact-maker). The disadvantages are (1) it’s not really efficient, taking 6 steps to evaluate (double (double 1)) while the call-by-value strategy can evaluate the term in only 4 steps, and (2) it doesn’t interact well with mutation, which is a feature that most programming languages have. This is the reason why most programming languages use call-by-value instead.

Due to the call-by-value strategy, we can’t run the Y combinator in the standard Racket language. One cool feature of Racket however is its ability to create and use a new programming language via the hash lang line. In fact, the creators of Racket even call Racket a Programmable Programming Language. It is very easy to create a call-by-name language with Racket. Even better, someone did that already and we can just use it!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
#lang lazy

(let ([Y (λ (f)
           ((λ (x) (f (x x)))
            (λ (x) (f (x x)))))])
  (let ([fact-maker (λ (fact)
                      (λ (n)
                        (case n
                          [(0) 1]
                          [else (* n (fact (- n 1)))])))])
    (let ([fact (Y fact-maker)])
      (! (+ (fact 3) (fact 4)))))) ;; we need to ! to force value for printing
30

The final remark in this section is that, the Z combinator is also known as the call-by-value Y combinator since it’s the Y combinator for call-by-value languages.

Y and me #

I learned the Y combinator two years ago from the PL class taught by Shriram Krishnamurthi. One great explanation (which Shriram pointed us to) is Matthias Felleisen’s A Lecture of the Why of Y, which similarly attempts to derive the Y combinator. However, the explanation that corresponds to the “Enabling recursion” section goes in a much slower pace and implicitly contains some elements from the “Fixed point” section. The strength of this approach in my opinion is that it crucially uses the fixed-point identity $Y(f) = f(Y(f))$ to justify the “self-application trick” in the derivation right away, so it motivates really well why $Y(f) = f(Y(f))$ is important. The approach that I use, on the other hand, simply focuses on where things are bound and how can we direct values to appropriate places, which results in a simpler explanation in my opinion. I also make use of let a lot, which I think helps with readability. The weakness is that I also need to talk about desugaring.

I didn’t discover this approach myself. The core insight of this approach is from a student’s homework that I graded in the current iteration of the PL class. A part of the homework asks students to write random programs in a language that is very similar to Racket without letrec and mutation. I didn’t expect that students will be able to write a really meaningful program unless they know a fixed-point combinator already, ... or so I thought. It turns out that one student wrote a program to calculate 1 + 2 + ... + n for arbitrary n without knowing a fixed-point combinator! Here’s the program in Racket:

1
2
3
4
5
(let ([triangle (λ (triangle n)
                  (case n
                    [(0) 0]
                    [else (+ n (triangle triangle (- n 1)))]))])
  (triangle triangle 10))
55

Granted, this is simply a rewrite of one of Matthias’s slides into the let form with uncurrying, but it really opened up my eyes.

Acknowledgements #

Since our grading policy dictates that we can’t look at students’ name, I don’t know who this student is. Regardless, I would like to thank them for this incredible insight. I also would like to thank Shriram and Matthias for their teaching. Lastly, I thank James Wilcox for his various suggestions for this post.