大概是面向 \(\text{CSer}\) 的入門，雖然我覺得網上很多教程難懂的主要原因是不喜歡把所有括號都打出來，然后在描述的時候濫用柯里化（雖然這是對的）。

\(\lambda\) 演算可以理解成一種（好用？的）編程語言。\(\lambda\) 演算的思想就是設計一個可計算的函數，可以看成像 Haskell，Erlang 之類函數式編程的先祖。

這里還是描述一下函數式編程，在函數式編程中，所有東西都是函數，比如常量 \(1\)，被認為是一個總是返回 \(1\) 的常函數。同時，函數和數學上一樣是不可變的（畢竟就是數學家做出來的東西）。

語法

函數的定義

\(\lambda\) 演算作為一種很早的很基本的，而且更本沒有考慮可讀性的語言，其語法規則是簡單但幾乎不可讀的。

首先，標準的 \(\lambda\) 演算是沒有函數名的，這也是為什么 c++ 等語言用 \(\lambda\) 表達式來描述匿名函數。當你想調用一個函數的時候，你必須把其重新定義一遍。不過這樣實在有點愚蠢，這里我們還是定義函數名，可以理解成語法糖。這里記錄一下最簡單的 \(\lambda\) 函數：\(I(x)=\lambda x.x\)，返回自身的恒等函數。

\(\lambda\) 演算中定義函數非常簡單：\(\lambda \text{參數}.\text{函數體}\)。最開始的 \(\lambda\) 是一個標識符，相當于告訴你我要定義一個函數了。在 \(\lambda\) 演算中，為了可讀性，我們允許用 \(()\) 標記運算優先級。

最標準的 \(\lambda\) 演算同樣只允許單元函數，比如我們計算 \(a+b\) 就應該寫，\((\lambda x.(\lambda y.x+y)b)a\)。當然，加法可以有更基本的定義，不過我們暫時不考慮這個問題。

理解一下這個函數的運行邏輯，就是先讀入 \(a\)，然后作為第一個參數，把 \(x=a\) 當作常量參數傳入 \(\lambda y.x+y\) 中，再讀入 \(y=b\)。

這樣寫起來會多寫很多函數，為了簡便，我們可以簡寫為 \((\lambda xy.x+y)ab\)，約定先讀入最左側的參數。有時候，為了區分到底是 \(a(b)\) 作為輸入，還是 \(a\) 和 \(b\) 作為兩個參數輸入，我們還使用 \(,\) 分隔，也就是 \((\lambda xy.x+y)(a,b)\) 用于計算 \(a+b\)。

變量

剛剛的演示中我們已經看到了 \(\lambda\) 演算中的所有變量類型：自由變量和約束變量。

自由變量就是上文的 \(ab\) 這樣的變量，它本身不是一個函數的參數，想取什么都可以，這樣的變量應該被理解成一般編程語言中的輸入。（代碼中的常量本質上也是輸入，你可以理解成現代的語言給了語法糖，讓你不用每次調用都輸入）

約束變量就是 \(\lambda x.x\) 這樣的函數中的參數，就是形參。

\(\#\) 作為一種古老的語言，沒有語法安全檢測是正常的，你需要自己保證自己的代碼不會 \(\color{yellow}\text{CE}\)。

選擇結構

實現選擇，其實很簡單，比如一段很簡單的 python 代碼

if condition:
	F
else:
	G

那我們一下子就知道了，如果 condition 為真，就運行 F，否則就運行 G。這個其實在 \(\lambda\) 演算中也很好實現。一個容易出現的錯誤想法是我們的函數接受 \(3\) 個參數，一個布爾變量和兩個函數，但是這樣你選擇不了，會陷入循環論證。

此時正確的做法是回憶一下開頭所說：\(\lambda\) 演算中所有東西都是函數。那么布爾變量也應該是函數，這下就容易了：

此時就很好定義 if 了：\(if(a,b,c)=\big(\lambda(a,b,c).a(b,c)\big)\)，自然地可以理解成 if a then b else c。當然，這就是什么都沒有做，重點是上面對布爾變量的定義。

邏輯運算

都會 if 了，邏輯運算就很簡單了，這里只是寫一下定義（進行了一定的化簡，你用一堆 if 拼出來自然也是可以的），方便后面使用。

函數迭代與自然數

在 \(\lambda\) 演算中，函數迭代是不簡單的，因為我們還沒有定義自然數，自然也不能寫循環，事實上，函數式編程中沒有循環，只有遞歸（也就是函數迭代）。

那么，為了解決這個問題，像之前說的一樣，自然數也是函數，那我們把函數迭代的迭代次數本身當成自然數不就好了。

具體一點：

這里的 \(=\) 應該理解成宏替換，實際上用 \(\equiv\) 會更數學一點。（一個有意思的點是 \(0=F\) 在 \(\lambda\) 演算中是自然成立的）

需要理解的一點是，既然我們用函數定義了自然數，那最后我們就不一定要填滿所有的參數，知道這個函數表示什么數就可以了。

比如 \(\lambda\) 演算編寫的程序：\(\lambda fx.f(f(f(x)))\)，我們并不需要真的輸入 \(f\) 和 \(x\)，我們已經知道這就是一個常函數，返回值為 \(3\) 了。

另外需要注意的一點是，我們目前還沒有定義數組或數對，所以你寫 \(\lambda\) 演算式 \(33\)，我們的理解應該是復合函數，直接復合的結果就是 \(3^3\)，于是乘方就不用寫了。

是否為 0

考慮之前對布爾值的定義，我們可以觀察到一個性質：\(F=\lambda xy.y\)，這時我們要記住，這其實是一個縮寫，本質是 \(F=\lambda x.(\lambda y.y)\)，那么如果只給一個參數，就有 \(F(a)=\lambda y.y=I\)，同時這也告訴我們，\(FF=I\)。

這是一個很好的性質，可以被類比成一種開關，于是我們可以寫下一個函數判斷一個量是否為 \(0\)。

這里的 \(\neg\) 本質上也是一個函數，我們寫 \(x(F)\) 的意思是，如果 \(x>1\)，那么就會迭代出 \(I\)，如果 \(x=1\)，那么 \(F(\neg)\) 也等于 \(I\)，然后 \(I(F)=F\)，但是如果 \(x=0\)，那么 \(x(F)=I\)，于是結果就是 \(\neg F=T\)。

后繼與加法

如果你看了分析基礎 I，就應該知道比加法更基本一點的運算是后繼運算，也就是 \(suc(x)=x+1\)。（這里的 \(suc\) 沒有使用正體 \(\text{suc}\)，是因為想強調在 \(\lambda\) 演算中數和函數沒有本質區別，所有東西都是函數）

其實有了后繼就有加法了，因為我們可以定義 \(add(x,y)=\lambda xy.\big(x(suc)\big)(y)\)，因為 \(suc\) 是自加 \(1\)，那迭代 \(x\) 次就是自加 \(x\)。

然后我們知道數字本質是用 \(f\) 重復的次數定義，那求后繼多套一個不就完了，再想一下細節，為了 \(f\) 表示同一個函數，\(suc\) 其實應該接受 \(3\) 個參數，也就是

就像定義自然數時一樣，雖然我們有 \(3\) 個參數，但是后 \(2\) 個大多數時候根本不需要，我們只是形式上保留了這樣的內容。

后面我們就可以開心得寫 \(x+y\) 這樣的內容了。

數對，前驅與減法

\(\lambda\) 演算天然支持存儲單個元素，但這樣就像只有一個寄存器的電腦一樣讓人難受。

那最簡單的構造數對的方法就是把兩個數放在一起，于是我們可以想到和之前構造自然數一樣，我們保留一個形式化的參數，就有了

這樣帶來的一個額外好處是，對于數對 \(p\)，\(p(T)\) 相當于 p.first，\(p(F)\) 相當于 p.second。

然后你發現其實 \(b\) 是個什么東西都可以，于是一個 \(\text{naive}\) 的想法就是可以這樣定義數組，然后還真行~。這樣得到的列表大概是 \((a,(b,(c,\ldots)))\)。然后數組還有一些實現細節，之后再說。

現在我們回歸之前的目標，推導出基本的二元運算，現在我們推導減法，首先還是推導前驅。

我們知道，前驅運算很簡單，就是 \(pre(x)=x-1\)。

但是減法的定義是有點困難的，這里有一個妙妙做法就是考慮每次存數對 \((n+1,n)\)，然后當 \(n+1=x\) 的時候，取 pair 中的另外一個元素就得到了 \(n\)。（畢竟是數學模型，能做就行，至少暫時不要考慮復雜度）

定義數對的后繼是很容易的，\(psuc(p)=mp\Big(suc\big(p(T)\big),p(T)\Big)\)。然后和加法一樣，我們直接迭代 \(n\) 次就好了，于是可以有

可以注意到，此時有 \(pre(0)=0\)，這個當成 \(\text{ub}\) 就好了，但是有時候很好用。

然后，\(\lambda xy.\big(y(pre)\big)(x)\) 是可以當成無符號整數的 \(x-y\) 用的，但是如果 \(y>x\) 得到的結果還是 \(0\)。

乘法

在之前乘方的基礎上稍微改改就行了，直接放結果：

比較算符

首先，我們可以定義 \(x\le y\)，這個很簡單，就是

然后別的幾個都可以拼出來，比如 \(x=y\Leftrightarrow x\le y\land y\le x\)。

Recursion

Combinator

沒有循環的高（nan）貴（xie）語言。

最 \(\text{naive}\) 的想法肯定是，我直接寫不就完了，比如 \(f(a,b,x)=if(a,b,f(a,b,x))\)。

但問題就在于，這是不能通過編譯的。因為 \(f\) 本身是個 \(\lambda\) 函數，然后你展開的話就會發現有無窮多層。

所以常用的做法是把 \(f\) 也當成參數，從外面傳入進來。

那外面這個輔助函數最簡單地，至少要可以生成無限次的遞歸，至于怎么終止則要看內部的函數，這個任務不應該被交給輔助函數。形式化地，記外面的輔助函數為 \(H\)，那么應該有

然后你展開就會發現這意味著

求解這樣的 \(H\) 目前看上去有點困難，但是我們可以考慮簡單一點的情況，只調用自己一次，那這樣的函數是很簡單的（也就是想得到 \(g(f(x))=f(f(x))\)），只需要考慮 \(\omega(x)=\lambda x.x(x)\) 即可。

這個時候，聰明的同學可以注意到一件事，如果我考慮 \(\omega(\omega)\) 會發生什么事呢，代入之后就會發現兩個 \(x\) 都會被替換成 \(\omega\)，于是 \(\omega\omega=\omega\omega\)，這個東西有個名字叫 \(\Omega\) 組合子，因為是兩個 \(\omega\) 組合起來的算子。

然后 \(\Omega\) 稍微改造一下其實就可以實現遞歸了。怎么想到的呢？就是 \(\omega\) 每次嵌套什么都沒有做，但是如果我傳入一個函數 \(f\)，每次 \(\omega\) 嵌套的時候都在外面套一層 \(f\)，就可以實現無窮層的遞歸了。后面填一點細節就是這樣：

外面傳入兩個參數，一個是遞歸函數的核 \(f\)（我也不知道是不是叫這個名字），一個是 \(x\)（也就是原本 \(\omega\) 用來遞歸的東西），具體就是

之前說過，這里的參數就是函數

這樣的函數定義無疑是合理的，而且外面會發現如果記 \(x=\omega(f,\omega)\)，就有 \(f(x)=x\)。于是 \(\omega(f,\omega)\) 又叫做 \(f\) 的不動點。

你會發現上面我們做的，其實就是提出了一種構造任意函數不動點的機械方法，這樣的方法（中用到的輔助函數）就被稱為組合子。

用 \(\lambda\) 演算寫下來 \(\omega\) 的定義：

這時我們想要一個更好的封裝，也就是 \(C(r)=\omega(r,\omega)=\omega r\omega\)。這樣的 \(C\) 是容易得到的：

通過交換 \(x,r\) 的位置我們可以得到更簡單的格式（我一開始出了點問題，沒有想到這里，看了后面就知道是什么問題了）：

其實相當于把 \(\omega(f,\omega)\) 換成了 \(\omega(\omega,f)\)，同時稍微修改一下 \(\omega\) 的定義變為 \(\omega(x,f)=f(x(f,x))\) 就可以了。

這個組合子可以參考John Tromp 的一篇論文（第 10 頁中的 \(\mathbf{Y}^{\prime\prime}\)），我沒細看論文，不知道推法一不一樣。

An Example of Combinator

比如一個典中典的問題是求解自然數的階乘，那在 \(\lambda\) 演算中我們是沒有循環的，只能寫遞歸了。

首先，我們考慮簡單的遞歸函數：

def fact(n):
	if n == 0:
		return 1
	else:
		return n * fact(n - 1)

為了便于理解，我們首先在代碼層面把這個函數拆分為遞歸部分 fact 和計算部分 calc：

def fact1(n, calc):
	if n == 0:
		return 1
	else:
		return n * calc(n - 1, calc)

我們發現 fact1 本身就可以作為計算階乘的函數，于是就有 \(n!\) 等于 fact1(n, fact1)。（這里很多網上的資料會化成 fact1=f=>n=>f(f)(n)，雖然是對的，但是我還是不習慣柯里化的寫法，感覺有點毒瘤）

那轉化成 \(\lambda\) 演算就應該是 \(fact1(n,x)=if\big(Zero(n),1,n*x(n-1,x)\big)\)。然后 \(fact1(n, fact1)\) 就是我們想求的，可以發現這就是 \(\omega f\omega\) 的形式，于是 \(C(fact1)\) 就是 \(fact\)，\(\big(C(fact1)\big)(n)=n!\)。

A Way to Find Combinators

記 \(f^\infty=f(f^\infty)\)，也就是 \(f\) 的無窮層嵌套得到的函數。只要我們有辦法表示出 \(f^\infty\) 就可以了，或者說，\(f\) 的任意不動點就是 \(f^\infty\)。

從之前的方法，我們可以意識到，直接求解 \(f^\infty\) 是困難的，但是我們可以用一個輔助函數 \(g\) 的有限次嵌套來構造出無限循環。

比如我們假設 \(f^\infty=g(g)=gg\)，那么就有 \(f(gg)=gg\)，這樣我們可以立馬知道 \(g(x)=\lambda x.f(xx)\)。然后我們想要得到這樣的算子 \(Y\)，于是 \(Y(f)=g(g)\)。（當然，嚴謹一點，我們應該把 \(f\) 也當成參數傳給 \(g\)）

這樣得到的組合子就是 \(Y=\lambda g.\big(\lambda x.g(xx)\big)\big(\lambda x.g(xx)\big)\)，即著名的 \(Y\) 組合子。（本來也想一開始就講這個的，但是不知道為什么我推了個別的出來）

就算是同樣的設法也可以得到不同的組合子，比如和上面同樣的設法，但是你交換一下 \(g\) 里面的參數，也就是定義為 \(g(x,f)\)，那么不動點就是 \(g(g,f)\)，可以得到 \(g=\lambda x.(\lambda f.f(xxf))\)。

這時得到的組合子被稱為 \(\text{Turing Combinator}\)，即 \(T(f)=g(g,f)=\big(\lambda x.x(x)\big)\Big(\lambda y.\big(\lambda f.f(yyf)\big)\Big)\)。

實際上因為我們總是至少要兩個參數，一個函數體 \(f\)，一個輔助函數 \(g\)，所以交換 \(g\) 中的參數再手動加一層總是可以得到一個新的遞歸函數，實際上，我們可以定義一個函數 \(S=\lambda x.\lambda y.y(xy)\) 。比如 \(T\) 就是 \(Y S\)。所以其實之前我只是得到了 \(C S\)，而不是 \(C\)。

之前我們得到的組合子的構造方法是 \(f^\infty=g(f(g))\)，實際上什么構造方法都可以，比如 \(f^\infty=g(f(g(g)))\) 也可以，當然，這里你就會覺得柯里化是合理的，因為每次嵌套，你都需要給 \(g\) 增加一個參數，更詳細的內容可以參考Y組合子的一個啟發式推導中的第五部分。

Array

要是我們可以用 \(\lambda\) 演算定義數列了，那么我們就有足夠的信心相信它不弱于圖靈機了。

定義數列（列表）可以用極其粗暴的方式，每次要在 \(L\) 末位插入一個元素 \(x\) 時，直接返回 \(mp(L, x)\) 就行了。

然后，出于習慣，我們約定空列表 \(nil=F\)。

這時我們想一想，可以用 \(Head(L)=L(T)\) 得到 \(L\) 中的第一個元素，用 \(Tail(L)=L(F)\) 得到 \(L\) 中的第二個元素，也就是刪去了第一個元素的列表。

Is Empty

判斷一個列表是不是空是很常用的功能，然后我們發現之前說過（或者你可以回去看定義）：

在 \(\lambda\) 演算中，\(0\) 和 \(F\) 天然是一個東西。

于是之前的函數 \(Zero\) 就是 \(Null\)。

Length

我們想要做的另外一個事情是判定給定列表的長度。首先容易寫出正常的代碼：

def len(lst, calc):
	if Null(lst):
		return 0
	else:
		return 1+calc(Tail(lst), calc)

用 \(\lambda\) 演算寫就是 \(len=\lambda lst.\lambda f.If\big(Null(lst),0,suc\text{ }calc(Tail(lst),calc)\big)\)，然后 \(Len=Y(len)\)，其中 \(Y\) 你隨便選個喜歡的組合子都可以。

Kth Element

一個列表，我們當然想取出其中第 \(k\) 個元素，其實差不多，存一個計數器，到 \(0\) 的時候就返回就可以了。

然后用 \(Get=Y(get)\) 就行了。

后記

咕咕，咕咕咕，咕——