你所不知道的
Functional programming:

lambda calculus

簡報

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

參考資料

程式碼

Alonzo Church

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

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

謝謝大家！

Select a repo