2.0. Lời tựa

Giả sử ta cần implement vòng lặp, hay loop, thì ý tưởng cực hay đó là:

$(\lambda x.x\;x)(\lambda x.x\;x)$

Sử dụng $\beta$-reduction lên vế đầu:

$=(\lambda x.x\;x)(\lambda x.x\;x) [x:=\lambda x.x\;x]$

Ta thu được chính biểu thức ban đầu, hay biểu diễn ngắn gọn hơn:

$\text{loop}=\text{loop}$

Đây là một hàm quy về chính nó (tự ánh xạ), và chính là bản chất nguyên thủy của tất cả các cú pháp mang tính lặp (iterative) trong lập trình như for, do-while, …

2.1. Đệ quy (recursion)

Từ đây, chúng ta định nghĩa các khái niệm khác như đệ quy, bản chất đệ quy cũng chính là một hàm nhận một hàm khác và lặp lại chính hàm đó:

$\text{rec}\;f = f (\text{rec}\;f)=f(f…(\text{rec}))$

Đây chính là nguyên mẫu nguyên thủy của đệ quy, từ đây chính ta có thể định nghĩa những variant của đệ quy như tương hỗ, phi tuyến, …

Mối liên hệ giữa đệ quy và loop đó là:

$\text{rec}=\text{Y}=\lambda f. (\lambda x.f(x\;x))(\lambda x.f(x\;x))$

Khi chúng ta ánh xạ $\text{Y}-$combinator lên một hàm $g$ nào đó:

$\text{Y}\;g=(\lambda x.g(x\;x))(\lambda x.g(x\;x))$

$=g\left((\lambda x.g(x\;x)) (\lambda x.g(x\;x))\right)=g(\text{Y}\;g)$

Đây chính là $\text{Y}-$combinator trong huyền thoại, ý tưởng một hàm có thể gọi các hàm khác.

2.3. Factorial

Để minh họa sự ảo diệu của $\text{Y}-$combinator, ta sẽ đi qua một ví dụ kinh điển về đệ quy - tính giai thừa bằng hàm factorial (fac), chúng ta đều biết rằng theo định nghĩa thông thường:

` fac (x) = if x = 1 then 1 else x * fac(x-1) `

Khi toán hóa:

$\text{fac} = \lambda r. \lambda n. (\text{if}\;n = 1\;\text{then}\;1 \;\text{else}\;n * r (n - 1))$

Ánh xạ $\text{Y}-$combinator lên hàm $\text{fac}\;2$ để tính 2!.

$ (\text{Y}\;\text{fac})\;2 = \text{fac}\;(\text{Y}\;\text{fac})\;2 $

$ =2*(\text{Y}\;\text{fac})\;1 [r:=(\text{Y}\;\text{fac}); n:=2] $

$ =2*\text{fac}(\text{Y}\;\text{fac}) 1 $

$ =2*1[r:=(\text{Y}\;\text{fac}); n:=1]=2 $

Kết thúc bài 2