<commit_before>---
layout: post
title: Y-combinator：lambda function's recursion
description: How to create a automate iterator via lambda calculation
keywords: "lambda calculus, combinator, recursion, closet, Lisp"
category: lambda_calculus
tags: [lambda_calculus, recursion, combinator]
---
{% include JB/setup %}

> 緣起 - 還是要從最近玩的一個比較有意思的Toy說起，[『DrRacket』](http://docs.racket-lang.org/drracket/), 涉及到兩個叠代的繪圖 `procedure`,
	而我希望做的工作就是對這兩個叠代split `procedure` 函數做一個 high-order abstraction。其實對於瞭解Y-combinator的來說，一拉到底爺就可以了，最後有個關於lambda recursion基於Y-combinator的實現。

<!-- more -->

首先，我得到四種遞歸畫圖的`procudure`, 他們分別被命名為：`right-split`,	 `up-split`, 	`left-split`,	`down-split`, 代表圖像叠代的方向是identity picture的上，下，左，右四個方位。下面我寫出具體的代碼和示意圖來作為演示。[後面我們會明白之所以使用這種繪圖函數來作為這個問題的引子，是因為其本身具有的閉包(closure)屬性]

```lisp
(require (planet "sicp.ss" ("soegaard" "sicp.plt" 2 1)))
(define (right-split painter n)
	(if (= n 0)
	     painter
	     (let ((smaller (right-split painter (- n 1))))
	     	 (beside painter (below smaller smaller)))))
```

結果如下圖：

 ![right-split einstein](/assets/images/2014/07/right-split.png) 

 原諒我使用偉大的 Einstein 來做這個例子的說明，只是因為好像Library作者們似乎比較喜歡這位？ 

 同理，我們也可以用類似的叠代思想來表示 `up-split` 過程：

```lisp
 (define (up-split painter n)
 	(if (= n 0)
 	     painter
 	     (let ((smaller (up-split painter (- n 1))))
 	     	(below painter (beside smaller smaller)))))
```

 Usage:

```lisp
 (paint (up-split einstein 4))
```

 結果是這樣的：

 ![up-split einstein](/assets/images/2014/07/up-split.png) 

 從Einstein分裂的走時來看，我們已經可以發現 `below`, `beside` 的組合先後順序似乎決定了painter的組合方式的所有。

 從上面兩個例子我們就可以看出來，實際上，這個 `[direction]-split` procedure 本質上都是split 叠代的向 identity picture 上面組合疊加的函數，所以，我們受到上面的 `right-split`,	 `up-split` 的影響，進一步希望製作抽象procedure歸納出所有方向上的`split`函數。

 正如上面的[up-split einstein] 圖所說的，我們實際上這兩個函數只是 `below` 和 `beside` 這兩個過程的嵌套位置顛倒而已，如此的話，實際上就是說我們也應該可以抽象出過程滿足如下方式生成`up-split` 和 `right-split`

```lisp
	(define left-split (split beside below))
	(define up-split (split below beside))
```

顯然，split是這四個方位split函數的函數抽象，所以，實際上，從上面這個定義抽象上來看，至少還有  painter 和 n 兩個參數實際上是被構建的 Abstraction Barrier 給個離開了。

如此的話，我們至少可以猜測出 `split` 過程返回的應該是一個lambda 函數，他的形式如下  *(lambda (painter n) (...))* 的形式。 於是，我們的問題就此出現了。

* This question is related to the form of Procedure  `split` 's output -- *(lambda (painter n) (...))* ：

	+ 首先，我瞭解到，這個返回的 `(lambda (painter n)`  實際上肯定是等價於 `up-split` 和 `right-split` 的。

	+ 所以，我們確定  `(lambda (painter n)`  對應的是一個遞歸函數，類似於 `factorial`,  `(up-split painter n)` 的值來自於 `(up-split painter (- n 1))` 的定義。

	+ 所以這個問題就進一步可以被泛華做，我們應該如何是使用 lambda 函數來表示一個關於滋生的recursion 過程？

	+ 這裏顯然不同於普通定義法的地方就在於，實際上我們不可能像普通定義中使用 (up-split painter (- n 1)) 的方法來顯式的調用函數本身來完成遞歸了。因為這裏的lambda函數是匿名的，他們有一個名稱來給我進行引用。

所以，今天我寫下這篇post的目的，就是希望能基於lambda 函數的由來 lambda calculus 來分析究竟該如何在 匿名函數的情況下，來完成遞歸函數的定義。lambda函數具有的強大的表達能力，所以我們希望在其自身找到如何基於其定義完成遞歸的方法。

>  基石 - $\lambda \ Calculus$: 

*  我們首先從函數開始說起，函數是一個數學中非常基本的概念，例如，如果我們希望能夠使用從變量到值的mapping的時候，我們一般把他寫成 $f：x \mapsto x - y$ 的形式，但是，這裏我們給函數賦予的「函數名」f 是必須的嗎？ 顯然，過多的特殊標註會導致我們在使用高階函數的時候帶來混亂，這也就是Church的標註發的好處了。我們ignore每一個函數的函數名稱，取而代之的是輔助符號$\lambda$, 因為本身函數表達的從變量到值的映射按理來說其實本身就代表了自己，根本不需要使用函數名來做annotation。這也可以說我們是把 $x \mapsto x - y$ 整體當作是函數名字了。如此，我們就可以吧上面的這個f 和 g分別定義做：

$$
	f = \lambda x. x-y    \qquad \qquad g = \lambda y. x - y \\\
	\equiv  \\\
	f(0) = 0-y   \qquad \qquad  g(0) = x-0 \\\
	我們再lambda \ notation 裏面寫作：\\\
	((\lambda x.x-y) 0)   \qquad \qquad  ((\lambda y.x-y) 0) \\\
$$

使用lambda表達最大的好處主要在於描述高階函數，例如上面的 f , g 實際上可以看作是來自於 $h(x, y) = x - y$ 函數的marginal function，所以，如果我們使用lambda notation 的話，一切都會變得簡單起來。

* 首先， 映射被表示做了 $(x,y) \mapsto x - y$, 我們使用lambda symbol之後，寫作: $$\lambda xy. x - y$$，那麽再問，單參數函數和多參數函數的區分是有必要的嗎？ 如果我們使用 $\lambda xy$ 的形式的話，我們要輸入的參數就不是單變量了而是pairs，這顯然不是必要的，我們完全可以把二元（多元）函數看作是一個參數是函數的函數，於是我們把上面的函數改寫做：

$$
	x \mapsto (y \mapsto x - y)   \Rightarrow \lambda x.(\lambda y. x - y) 
$$

如果我們給這個匿名函數一個名字叫$$h^*$$, 的話，我們發現原來的 $h(x, y) \rightarrow (h^*(x))(y) $。 換句話說，我們把一個以數的函數映射成一個函數的函數，也就是我們常常說的「高階函數」（high-order function）。

我們把這種將多參數函數轉化成單參數的高階函數的過程，叫做Currying(柯裏化)。寫作 $$((\lambda xy. x - y) x y) \equiv (((\lambda x. (\lambda y. x - y)) a) b)$$.

* &lambda; Calculus 的形式化

> ($\lambda$ Terms): 

* 我們有一個無窮的字符串集合，我們叫他『變量』，同時還有一個字符串結合叫做『原子常量』，原子常量可能是有限集合，無限集合或者空集合。 但是Atomic constant只針對applied lambda calculus討論，我們目前主要考慮pure lambda calculus的話，$$Atomic\ Constant \equiv \oslash $$。So，$\lambda \ term$ 定義如下：

	+ 所有的變量 $v\_0, v\_{000}$, ... 都是lambda 項；
	+ 如果M和N是lambda 項的話，那麽（MN）也是lambda 項 （Called Application）；
	+ 如果M是lambda 項，x是任意變量，那麽 $\lambda x. M$ 也是一個lambda 項。

* 符號約定：

	+ Lambda 項是左結合的，f, x, y 都是 lambda term的話，那麽 f x y = （f x）y
	+ 如 $\lambda x. M$ 我們稱之為函數抽象，因為這個形式如果M是一個實際上對應函數的函數體，例如x+2
	+ 我們使用 小寫字母來表示lambda term中的`變量`，同時使用大寫字母（M，N，P，Q ...）來表示對應的lambda term。
	+ lambda 項都是左結合的：例如，$((((MN))P)Q)$ 我們就可以寫作 MNPQ, 此時parentheses 可以被忽略。同時，$\lambda x.$ 作為一個聲明，是不能單獨存在的。
	+ 幾個例子：

	$$
		\lambda x.\lambda y. yxab = (\lambda x. (\lambda y. (((yx)a)b))) \\\
		(\lambda x.\lambda y.yx)ab = (((\lambda x.(\lambda y.(yx)))a)b) \\\
		\lambda x.\lambda y.ab\lambda z.z = (\lambda x. (\lambda y. ((ab)\lambda z.z))) \\\
	$$

	+ 再來個Currying 定義： $\lambda x_1x_2...x_n. M = (\lambda x_1. (\lambda x_2. (... (\lambda x_n. M))))$。

* 語法全等：
	+ lambda terms的語法全等寫作： $M \equiv N$ 
	+ 表示的是M和N有完全相同的`結構`.  $\Rightarrow$
	+ MN  $\equiv$ PQ $\Rightarrow$ M $\equiv$ P 且 N $\equiv Q$ 
	+ 如果是function abstraction的話，那麽  $\lambda x. M \equiv \lambda y. N \Rightarrow x \equiv y  \ \& \ M \equiv N $

* 替換 &bull; preparation：
	+ lgh(M) := 所有原子在M中出現的次數。
		- lgh(a) = 1; 
		- lgh(MN) = lgh(M)+lgh(N); 
		- lgh($\lambda x. M$) = 1+lgh(M).
		- E.g $M \equiv x(\lambda y. yux) \Rightarrow lgh(M)=1+(1+3)=5$
	+ 出現(occurance):
		- P 出現於P中；
		- P 出現在M或者N中，則P出現在(MN)中；
		- P 出現在M中或者P $\equiv$ x, 那麽P出現在$\lambda x. M$中。
	+ Scope: 對於 function abstraction 來說： $\lambda x. M$ 中 $\lambda x$ 的scope 是 M
	+ 自由變量：對一個lambda term P來說，我們可以定義<commit_msg>add lambda calculus's new post<commit_after>---
layout: post
title: Y-combinator：lambda function's recursion
description: How to create a automate iterator via lambda calculation
keywords: "lambda calculus, combinator, recursion, closet, Lisp"
category: lambda_calculus
tags: [lambda_calculus, recursion, combinator]
---
{% include JB/setup %}

> 緣起 - 還是要從最近玩的一個比較有意思的Toy說起，[『DrRacket』](http://docs.racket-lang.org/drracket/), 涉及到兩個叠代的繪圖 `procedure`,
	而我希望做的工作就是對這兩個叠代split `procedure` 函數做一個 high-order abstraction。其實對於瞭解Y-combinator的來說，一拉到底爺就可以了，最後有個關於lambda recursion基於Y-combinator的實現。

<!-- more -->

首先，我得到四種遞歸畫圖的`procudure`, 他們分別被命名為：`right-split`,	 `up-split`, 	`left-split`,	`down-split`, 代表圖像叠代的方向是identity picture的上，下，左，右四個方位。下面我寫出具體的代碼和示意圖來作為演示。[後面我們會明白之所以使用這種繪圖函數來作為這個問題的引子，是因為其本身具有的閉包(closure)屬性]

```lisp
(require (planet "sicp.ss" ("soegaard" "sicp.plt" 2 1)))
(define (right-split painter n)
	(if (= n 0)
	     painter
	     (let ((smaller (right-split painter (- n 1))))
	     	 (beside painter (below smaller smaller)))))
```

結果如下圖：

 ![right-split einstein](/assets/images/2014/07/right-split.png) 

 原諒我使用偉大的 Einstein 來做這個例子的說明，只是因為好像Library作者們似乎比較喜歡這位？ 

 同理，我們也可以用類似的叠代思想來表示 `up-split` 過程：

```lisp
 (define (up-split painter n)
 	(if (= n 0)
 	     painter
 	     (let ((smaller (up-split painter (- n 1))))
 	     	(below painter (beside smaller smaller)))))
```

 Usage:

```lisp
 (paint (up-split einstein 4))
```

 結果是這樣的：

 ![up-split einstein](/assets/images/2014/07/up-split.png) 

 從Einstein分裂的走時來看，我們已經可以發現 `below`, `beside` 的組合先後順序似乎決定了painter的組合方式的所有。

 從上面兩個例子我們就可以看出來，實際上，這個 `[direction]-split` procedure 本質上都是split 叠代的向 identity picture 上面組合疊加的函數，所以，我們受到上面的 `right-split`,	 `up-split` 的影響，進一步希望製作抽象procedure歸納出所有方向上的`split`函數。

 正如上面的[up-split einstein] 圖所說的，我們實際上這兩個函數只是 `below` 和 `beside` 這兩個過程的嵌套位置顛倒而已，如此的話，實際上就是說我們也應該可以抽象出過程滿足如下方式生成`up-split` 和 `right-split`

```lisp
	(define left-split (split beside below))
	(define up-split (split below beside))
```

顯然，split是這四個方位split函數的函數抽象，所以，實際上，從上面這個定義抽象上來看，至少還有  painter 和 n 兩個參數實際上是被構建的 Abstraction Barrier 給個離開了。

如此的話，我們至少可以猜測出 `split` 過程返回的應該是一個lambda 函數，他的形式如下  *(lambda (painter n) (...))* 的形式。 於是，我們的問題就此出現了。

* This question is related to the form of Procedure  `split` 's output -- *(lambda (painter n) (...))* ：

	+ 首先，我瞭解到，這個返回的 `(lambda (painter n)`  實際上肯定是等價於 `up-split` 和 `right-split` 的。

	+ 所以，我們確定  `(lambda (painter n)`  對應的是一個遞歸函數，類似於 `factorial`,  `(up-split painter n)` 的值來自於 `(up-split painter (- n 1))` 的定義。

	+ 所以這個問題就進一步可以被泛華做，我們應該如何是使用 lambda 函數來表示一個關於滋生的recursion 過程？

	+ 這裏顯然不同於普通定義法的地方就在於，實際上我們不可能像普通定義中使用 (up-split painter (- n 1)) 的方法來顯式的調用函數本身來完成遞歸了。因為這裏的lambda函數是匿名的，他們有一個名稱來給我進行引用。

所以，今天我寫下這篇post的目的，就是希望能基於lambda 函數的由來 lambda calculus 來分析究竟該如何在 匿名函數的情況下，來完成遞歸函數的定義。lambda函數具有的強大的表達能力，所以我們希望在其自身找到如何基於其定義完成遞歸的方法。

>  基石 - $\lambda \ Calculus$: 

*  我們首先從函數開始說起，函數是一個數學中非常基本的概念，例如，如果我們希望能夠使用從變量到值的mapping的時候，我們一般把他寫成 $f：x \mapsto x - y$ 的形式，但是，這裏我們給函數賦予的「函數名」f 是必須的嗎？ 顯然，過多的特殊標註會導致我們在使用高階函數的時候帶來混亂，這也就是Church的標註發的好處了。我們ignore每一個函數的函數名稱，取而代之的是輔助符號$\lambda$, 因為本身函數表達的從變量到值的映射按理來說其實本身就代表了自己，根本不需要使用函數名來做annotation。這也可以說我們是把 $x \mapsto x - y$ 整體當作是函數名字了。如此，我們就可以吧上面的這個f 和 g分別定義做：

$$
	f = \lambda x. x-y    \qquad \qquad g = \lambda y. x - y \\\
	\equiv  \\\
	f(0) = 0-y   \qquad \qquad  g(0) = x-0 \\\
	我們再lambda \ notation 裏面寫作：\\\
	((\lambda x.x-y) 0)   \qquad \qquad  ((\lambda y.x-y) 0) \\\
$$

使用lambda表達最大的好處主要在於描述高階函數，例如上面的 f , g 實際上可以看作是來自於 $h(x, y) = x - y$ 函數的marginal function，所以，如果我們使用lambda notation 的話，一切都會變得簡單起來。

* 首先， 映射被表示做了 $(x,y) \mapsto x - y$, 我們使用lambda symbol之後，寫作: $$\lambda xy. x - y$$，那麽再問，單參數函數和多參數函數的區分是有必要的嗎？ 如果我們使用 $\lambda xy$ 的形式的話，我們要輸入的參數就不是單變量了而是pairs，這顯然不是必要的，我們完全可以把二元（多元）函數看作是一個參數是函數的函數，於是我們把上面的函數改寫做：

$$
	x \mapsto (y \mapsto x - y)   \Rightarrow \lambda x.(\lambda y. x - y) 
$$

如果我們給這個匿名函數一個名字叫$$h^*$$, 的話，我們發現原來的 $h(x, y) \rightarrow (h^*(x))(y) $。 換句話說，我們把一個以數的函數映射成一個函數的函數，也就是我們常常說的「高階函數」（high-order function）。

我們把這種將多參數函數轉化成單參數的高階函數的過程，叫做Currying(柯裏化)。寫作 $$((\lambda xy. x - y) x y) \equiv (((\lambda x. (\lambda y. x - y)) a) b)$$.

* &lambda; Calculus 的形式化

> ($\lambda$ Terms): 

* 我們有一個無窮的字符串集合，我們叫他『變量』，同時還有一個字符串結合叫做『原子常量』，原子常量可能是有限集合，無限集合或者空集合。 但是Atomic constant只針對applied lambda calculus討論，我們目前主要考慮pure lambda calculus的話，$$Atomic\ Constant \equiv \oslash $$。So，$\lambda \ term$ 定義如下：

	+ 所有的變量 $v\_0, v\_{000}$, ... 都是lambda 項；
	+ 如果M和N是lambda 項的話，那麽（MN）也是lambda 項 （Called Application）；
	+ 如果M是lambda 項，x是任意變量，那麽 $\lambda x. M$ 也是一個lambda 項。

* 符號約定：

	+ Lambda 項是左結合的，f, x, y 都是 lambda term的話，那麽 f x y = （f x）y
	+ 如 $\lambda x. M$ 我們稱之為函數抽象，因為這個形式如果M是一個實際上對應函數的函數體，例如x+2
	+ 我們使用 小寫字母來表示lambda term中的`變量`，同時使用大寫字母（M，N，P，Q ...）來表示對應的lambda term。
	+ lambda 項都是左結合的：例如，$((((MN))P)Q)$ 我們就可以寫作 MNPQ, 此時parentheses 可以被忽略。同時，$\lambda x.$ 作為一個聲明，是不能單獨存在的。
	+ 幾個例子：

	$$
		\lambda x.\lambda y. yxab = (\lambda x. (\lambda y. (((yx)a)b))) \\\
		(\lambda x.\lambda y.yx)ab = (((\lambda x.(\lambda y.(yx)))a)b) \\\
		\lambda x.\lambda y.ab\lambda z.z = (\lambda x. (\lambda y. ((ab)\lambda z.z))) \\\
	$$

	+ 再來個Currying 定義： $\lambda x\_1x\_2...x\_n. M = (\lambda x\_1. (\lambda x\_2. (... (\lambda x\_n. M))))$。

* 語法全等：
	+ lambda terms的語法全等寫作： $M \equiv N$ 
	+ 表示的是M和N有完全相同的`結構`.  $\Rightarrow$
	+ MN  $\equiv$ PQ $\Rightarrow$ M $\equiv$ P 且 N $\equiv Q$ 
	+ 如果是function abstraction的話，那麽  $\lambda x. M \equiv \lambda y. N \Rightarrow x \equiv y  \ & \ M \equiv N $

* 替換 &bull; preparation：
	+ lgh(M) := 所有原子在M中出現的次數。
		- lgh(a) = 1; 
		- lgh(MN) = lgh(M)+lgh(N); 
		- lgh($\lambda x. M$) = 1+lgh(M).
		- E.g $M \equiv x(\lambda y. yux) \Rightarrow lgh(M)=1+(1+3)=5$
	+ 出現(occurance):
		- P 出現於P中；
		- P 出現在M或者N中，則P出現在(MN)中；
		- P 出現在M中或者P $\equiv$ x, 那麽P出現在$\lambda x. M$中。
	+ Scope: 對於 function abstraction 來說： $\lambda x. M$ 中 $\lambda x$ 的scope 是 M
	+ 自由變量：對一個lambda term P來說，我們可以定義
{'fraction_non_alphanumeric': 0.16484080794248546, 'fraction_numerical': 0.00718931872646354, 'mean_word_length': 4.394736842105263, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '371702', 'n_tokens_mistral': 7495, 'n_tokens_neox': 8050, 'n_words': 1051}