## 你所不知道的<br>Functional programming:<br><br> lambda calculus
---
## 簡報
---
## 參考資料
- https://www.ics.uci.edu/~lopes/teaching/inf212W12/readings/church.pdf
- https://en.wikipedia.org/wiki/Alonzo_Church
- https://en.m.wikipedia.org/wiki/Lambda_calculus
- https://www.slideshare.net/ccckmit/calculus-253542231
- https://github.com/gtramontina/lambda/blob/master/lambda.js
- https://gitlab.com/cccnqu111/alg/-/tree/master/09c-lambdaCalculus
---
## 程式碼
- https://colab.research.google.com/drive/1s6BpB3P5-Xe1kY6cqIttEgGsic8ZwaEy
---
## Alonzo Church
- Alonzo Church在20世紀30年代提出<br>**lambda calculus**
---
## python的lambda語法
```python
f = lambda x: x+1
f(10)
```
和下面的寫法等價
```python
def f(x):
return x+1
f(10)
```
---
## lambda calculus 語法
- 變數
- $x\ y\ z$
<br>
- 函數定義
- $\lambda\ x.x$
<br>
- 函數呼叫
- $M\ N$
---
## 柯里化
```python
def f(a, b):
return a + b
f(2, 3)
```
```python
def f(a):
def g(b):
return a + b
return g
f(2)(3)
```
---
## 述詞邏輯
- $TRUE=λx.λy.x$
```python
def true_(x, y):
return x
```
- $FALSE=λx.λy.y$
```python
def false_(x, y):
return y
```
- $IF=λc.λx.λy.c\;\;x\;\;y$
```python
def if_(c, x, y):
return c(x, y)
```
---
- $AND=λp.λq.p\;\;q\;\;FALSE$
```python
def and_(p, q):
return p(q, false_)
```
- $OR=λp.λq.p\;\;TRUE\;\;q$
```python
def or_(p, q):
return p(true_, q)
```
- $NOT=λp.p\;\;FALSE\;\;TRUE$
```python
def not_(p):
return p(false_, true_)
```
---
### 邱奇數
- $0=λf.λx.x$
- $1=λf.λx.f\ x$
- $2=λf.λx.f(f\ x)$
- $3=λf.λx.f(f(f\ x))$
```python
def _0(f, x):
return x
def _1(f, x):
return f(x)
def _2(f, x):
return f(f(x))
def _3(f, x):
return f(f(f(x)))
```
---
- $SUCC=\lambda n.\lambda f.\lambda x.f(n\ f\ x)$
```python
def succ(n):
def g(f, x):
return f(n(f, x))
return g
```
- $PLUS=\lambda m.\lambda n.m\ SUCC\ n$
```python
def plus(m):
def _plus(n):
return m(succ, n)
return _plus
```
- $MULT=\lambda m.\lambda n.m\ PLUS\ n \ 0$
```python
def mult(m, n):
return m(plus, n) _0
```
---
$$PRED=\lambda n.\lambda f.\lambda x.n\\ (\lambda g.\lambda h.h\ (g\ f))\\ (\lambda u.x)\ (\lambda u.u)$$
- $\lambda u.x$
- $\lambda u.u\ x$
- $\lambda u.u\ (f\ x)$
- $\lambda u.u\ (f\ (f\ x))$
- $\lambda u.u\ (f\ (f\ (f\ x)))$
- $...$
- $SUB=\lambda m.\lambda n.n\ PRED\ m$
```python
def sub(m, n):
return n(pred, m)
```
---
```python
ISZERO = lambda n: n(lambda u: FALSE)(TRUE)
LESS_THAN_EQUAL = lambda m: lambda n: ISZERO(SUB(m)(n))
LESS_THAN = lambda m: lambda n: NOT(LESS_THAN_EQUAL(n)(m))
EQUAL = lambda m: lambda n: AND(LESS_THAN_EQUAL(m)(n))\
(LESS_THAN_EQUAL(n)(m))
GREATER_THAN_EQUAL = lambda m: lambda n:\
LESS_THAN_EQUAL(n)(m)
GREATER_THAN = lambda m: lambda n:\
NOT(GREATER_THAN_EQUAL(n)(m))
```
---
## 資料結構
- $PAIR=\lambda x.\lambda y.\lambda f.f\ x\ y$
```python
def pair(x, y):
def g(f):
return f(x, y)
return g
```
---
## 遞迴
- $(\lambda f.\lambda x.f\ f\ x)\ (\lambda f.\lambda x.f\ f\ x)$
```python
def g(a, b):
return a(a, b)
g(g, x)
```
---
## 計算費氏數列
一開始的想法...
```python
def fib(n):
def f(a, b):
if_(
b <= 2,
1,
a(a, b-1) + a(a, b-2))
return f(f, n)
```
- if_(b<=2) 沒辦法讓a(a, b-1)停止遞迴
---
- 把a(a, b-1)改成lambda g: g(g, b-1)，最後才把a帶入，這樣就不會進入無窮遞迴了
```python
def fib(n):
def f(a, b):
if_(b <= 2,
lambda g: 1,
lambda g: g(g, b-1) + g(g, b-2)) (a)
return f(f, n)
```
---
- 最後程式碼長這樣
```python
U = lambda g: g(g)
FIBONACCI = U(lambda f: lambda x:\
IF(LESS_THAN_EQUAL(x)(_2))\
(lambda g: _1)\
(lambda g: PLUS (U(g)(PRED(x)))
(U(g)(PRED(PRED(x))) )) (f))
```
---
# 謝謝大家！
{"description":"","contributors":"[{\"id\":\"ddebcf0f-9f97-4dc4-8203-d32939bebe28\",\"add\":5644,\"del\":1689}]","title":"你所不知道的Functional programming: lambda calculus"}