簡報

參考資料

• 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年代提出
  lambda calculus

python的lambda語法

f = lambda x: x+1
f(10)

和下面的寫法等價

def f(x):
    return x+1
f(10)

lambda calculus 語法

• 變數
  • \(x\ y\ z\)
    
    
• 函數定義
  • \(\lambda\ x.x\)
    
    
• 函數呼叫
  • \(M\ N\)

柯里化

def f(a, b):
    return a + b

f(2, 3)

def f(a):
    def g(b):
        return a + b
    return g

f(2)(3)

述詞邏輯

• \(TRUE=λx.λy.x\)

def true_(x, y):
    return x

• \(FALSE=λx.λy.y\)

def false_(x, y):
    return y

• \(IF=λc.λx.λy.c\;\;x\;\;y\)

def if_(c, x, y):
    return c(x, y)

• \(AND=λp.λq.p\;\;q\;\;FALSE\)

def and_(p, q):
    return p(q, false_)

• \(OR=λp.λq.p\;\;TRUE\;\;q\)

def or_(p, q):
    return p(true_, q)

• \(NOT=λp.p\;\;FALSE\;\;TRUE\)

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))\)

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)\)

def succ(n):
    def g(f, x):
        return f(n(f, x)) 
    return g

• \(PLUS=\lambda m.\lambda n.m\ SUCC\ n\)

def plus(m):
    def _plus(n):
        return m(succ, n)
    return _plus

• \(MULT=\lambda m.\lambda n.m\ PLUS\ n \ 0\)

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\)

def sub(m, n):
    return n(pred, m)

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\)

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)\)

def g(a, b):
    return a(a, b)
g(g, x)

計算費氏數列

一開始的想法…

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帶入，這樣就不會進入無窮遞迴了

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)

• 最後程式碼長這樣

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))

謝謝大家！