在具備一級函式的語言中常談到,函式就是值,或者一級函式代表著lambda表示式(或運算式),而lambda表示式的概念來自於lambda演算,是一種表示運算的方式,具有構造語言的能力。

那麼,到底什麼是lambda演算?

從ES6箭號函式開始

看到lambda演算這名詞別太驚恐!若開發者曾在具備一級函式特性的語言中,使用過匿名函式,那麼,就運用過lambda表示式,實現過某種程度的lambda演算了!

例如,ES6箭號函式x => x,相當於lambda表示式λx.x,也就是,一個對映到本身的(identity)函式,恭喜!此時,你已經成功使用x => x來表示一個「值」!別懷疑,不是常說一級函式就是值、一級公民嗎?

如果有個函式function addOne(x) { return x + 1; },addOne(0)執行結果會是1,addOne也可以定義為let addOne = x => x + 1,因此,addOne(0)就是(x => x + 1)(0),也就是說,可以使用(x => x + 1)(0)來表示1這個結果了,2的話就是(x => x + 1)(1),也就是(x => x + 1)((x => x + 1)(0))。依此類推,就可以得到更多的數字了。

仔細想想,我們如果不展開addOne的話,1是addOne(0),2是addOne((addOne)(0)),3就是addOne(addOne((addOne)(0))),也就是說,數看看有幾個addOne,就是代表哪個數字。

如果不限於加法操作,而可以是某個f操作,並使用x變數來作為0的箭號函式表示,那麼,就可以使用箭號函式,來定義1為f => x => f(x),2為f => x => f(f(x)),3為f => x => f(f(f(x))),而如此持續下去,就可以定義出想要的正整數了。簡單來說,看到n個f,數字n就會得出,那麼,一個f都沒有的f => x => x就可以當成0了!

n(f)(x)表示f套用在x上n次,f(n(f)(x))表示f套用在x上n + 1次,因此,為了便於得到n的下個數,可以定義succ為n => f => x => f(n(f)(x))。如果定義$1為f => x => f(x),那麼,addOne就可以定義為n => $1(succ)(n),全部展開的話,就是n => (f => x => f(x))(n => f => x => f(n(f)(x)))(n)。

現在,已經能用箭號函式來表達addOne函式,以及正整數了,這就是lambda演算。每個值都可以用lambda表示式來代表,addOne($1)執行結果也是(可以試著自行展開它)。

也就是說,就算程式再複雜,最後,都可以化為lambda表示式,即便是true、false、if等也不例外,當這裡連if等都構造出來,就已經有了高階程式語言的感覺了。

Y Combinator

若開發者先前撰寫過匿名函式,多少就是在進行lambda演算,理由在於像x => x + 1這樣的函式,就是以匿名函式表示一個值,其中隱含地假設x會接受另一個匿名函式值,而+與1都各自有著已定義的匿名函式。

如果不滿足,想要嘗試更純綷的lambda演算,不用包山包海地定義出語言中全部元素的匿名函式表示,就像方才定義出addOne的過程就足夠了。若有其他的值,想用匿名函式表示,先寫下熟悉的語法,例如,x => x - 1,檢視其中尚未以匿名函式定義的值,例如方才的減號,然後想辦法使用匿名函式來表示它。

然而,可能馬上會有開發者發現到,表示遞迴函式時,會遇到困難。例如,階乘函式let fact = n => n < 2 ? 1 : n * fact(n - 1),匿名的部份為n => n < 2 ? 1 : n * fact(n - 1),若拿掉let fact =,那麼,fact就是個未定義的變數了,那就令fact為參數?也就是fact => n => n < 2 ? 1 : n * fact(n - 1)。

然而,問題在於,fact可以接受的函式,又是從何而來?

如果能定義出一個y函式,產生出fact可以接受的函式,那麼,y(fact => n => n < 2 ? 1 : n * fact(n - 1))就會階乘函式,想要知道這個y如何推導出來,可以參考〈Y Combinator〉(https://goo.gl/yXNViU),y當然必須能用匿名函式表示,而結果就是f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n)))。

搞Y Combinator做什麼?就現代程式語言來說,搞Y Combinator不太能有實際的作用,然而,如果想用箭號函式來表達程式意圖,在遇上遞迴函式時,Y Combinator會是必要的元素之一!

let語法糖

為了可讀性,在實現lambda演算的過程中,我們此時可以放寬限制,使用let來代表每個匿名函式,例如:

let $0 = f => x => x;

let succ = n => f => x => f(n(f)(x));

let add = m => n => n(succ)(m);

console.log(add($0)(succ($1)));

雖然最後可以將add($0)(succ($1))全部展開為匿名函式,藉此驗證lambda演算是否正確,然而展開後的結果,完全就像是加密文字一樣;就沒有更好的方式,可以符合lambda演算,又稍微兼顧點可讀性嗎?

來看看let f = x => x + 1; f(1);好了,其實也可以表示為(f => f(1))(x => x + 1),從這個角度來看,在實現lambda演算的過程中使用的let,就像是個語法糖了,因此,上面的程式碼,實際可以表示為:

console.log(($0 =>

(succ =>

(add =>

add($0)(succ($1))

)(m => n => n(succ)(m))

)(n => f => x => f(n(f)(x)))

)(f => x => x));

這裡所採用的格式縮排與換行並非必要,只是為了方便閱讀,每個參數的實際定義,就是同一層括號中的匿名函式,如果去掉全部的縮排與換行,還是個lambda表示式。

與數學運算正面交峰

匿名函式是一種lambda表示式,而一個lambda表示式,相當於一個數學函數匿名表示。例如,x => x + 1,相當於f(x) = x + 1的匿名表示,也就是說,既然程式碼可以全部轉換為匿名函式,就表示程式碼可以全部轉換為數學函數,而程式碼執行結果,就是數學函數運算後的結果,因此,使用ES6箭號函式來表示全部的程式碼時,JavaScript執行環境只是個正好能識別它,接著按照匿名函式定義進行計算的機器而已。

將lambda表示式寫在一個字條上,方才程式中的console.log()看成是機器接受字條輸入的入口,不正是這種隱喻嗎?數學式就是程式碼,程式碼就是數學式。

如果願意,我們可以設計其他機器來讀取同樣的字條,運算其中的數學式(在沒有電腦的年代,執行此任務的就是人了)。

既然數學式就是程式碼,那麼,構成數學式規則的lambda演算,就是程式語言了。

它就只有變數、函式定義與呼叫這三條語法規則,使用lamdbda演算撰寫程式,就必須直接與數學運算正面交峰。

也許這麼做,接下來,就不會有「什麼是運算思維?」這樣的問題產生,更不會有那些虛無縹緲的答案了!

作者簡介


Advertisement

更多 iThome相關內容