勵志

勵志人生知識庫

λ演算

λ演算(英語:lambda calculus,λ-calculus)是一種用於研究函式如何抽象化定義、函式如何被套用以及遞歸的形式系統,它從數學邏輯中發展而來,以變數綁定和替換的規則為核心。λ演算由數學家阿隆佐·邱奇在20世紀30年代首次發表,是一種廣泛用途的計算模型,可以清晰地定義什麼是一個可計算函式,而任何可計算函式都能以這種形式表達和求值。

λ演算強調的是變換規則的運用,而非實現它們的具體機器,它可以模擬單一磁帶圖靈機的計算過程,因此與圖靈機等價。λ演算包括了建構lambda項,和對lambda項運行歸約的操作,其核心概念是「expression」表達式,包括變數、函式定義和套用等。

例如,identity函式的定義為:λx.x,函式可以套用於表達式,比如(λx.x)y,其求值過程是將實際參數在函式體中進行替換。

λ演算對函式式程式語言造成了很大影響,例如LispML語言Haskell語言。在λ演算中,每個表達式都代表一個函式,這個函式有一個參數,並且會返回一個值,無論是參數和返回值,也都是一個單參的函式。可以這麼說,λ演算中只有一個"類型",那就是這種單參函式。