iT邦幫忙

2018 iT 邦幫忙鐵人賽
DAY 5
1
Software Development

函數式編程: 從 Elixir & Phoenix 入門。系列 第 5

親愛的,遞迴把記憶體塞爆了

那個很有名的英文程式問答網站

記得當我們昨天在一步步執行遞迴時,在加總前的最後一步是 (1 + (2 + (3 + 0))) 嗎?在遞迴的每一步想要回傳,但仍然有沒辦法處理的部份時,就會先把目前手上的東西,放到記憶體裡一個叫做 stack (堆棧) 的地方,等到知道怎麼解決時再拿回來算。而在我們範例的執行過程中,stack 的狀態有點像是這樣:

*1 (1 + 等第二行)
*2 (2 + 等第三行)
*3 (3 + 等第四行)
*4 0

一直到要第四行回傳了可運算的值,上面那些在等待的部份才會一個個清上去。只有四行當然沒什麼問題,但若在呼叫這個函式時,有人傳了上億個元素的串列進來,stack 就會被塞爆了,情況比較好就是跑很慢,情況差的時候,就會噴那個著名的 stack overflow 錯誤出來。所以你看一下那個同名的英文程式問答網站 logo,相當傳神的展示了這種情況。

https://ithelp.ithome.com.tw/upload/images/20171224/201033909YRNFSiYVI.png

尾呼叫最佳化 (tail call optimization)

想解決這個問題,要符合兩個條件,第一個條件就是該語言的 VM 要實作 tail call optimization,尾呼叫最佳化。聽起來很厲害,但是其實就是一條規則:

如果函式執行的最後一行,是另一個單純的函式呼叫時,那就直接把這個 stack 替換成新的函式呼叫。

試想有下面這樣一段程式碼:

def foo(x) do
  # 做些什麼事,產生 y
  bar(y) # 沒有計算跟其它有的沒的,就是個單純的函式呼叫
end

剛呼叫時,stack 長這樣:

*1 foo(x)

而算完中間的部份,運行到最後一行回傳時,stack 會被替換成這樣:

*1 bar(y)

既然 stack 完全沒有往下堆,也就不存在被塞爆的煩惱了。大多數的函數式編程語言都會在 VM 上實作 tail call optimization,elixir/erlang 當然也不例外。值得一提的是,之前的版本沒有硬性規定,但 JavaScript 從 ES6 開始,規範要實作 tail call optimization,且會在程式宣告嚴格模式的時候生效。

尾遞迴版本的 Math.sum

剛剛提到了解決問題的兩個條件。除了 VM 的實作之外,我們要調整一下程式碼,使其符合回傳時是一個單純的函式呼叫這條件。在遞迴裡用了尾呼叫,就稱為尾遞迴。實際的做法,就是把目前已求得的值當做另一個參數,往下傳

def sum([], total), do: total
def sum([h | t], total), do: sum(t, h + total)

# 呼叫時
sum([1, 2, 3], 0)

我們新版的 sum 需要兩個參數,除了原先要加總的串列之外,多放一個 0 當做 total 的起始值 (其實就是我們之前遇到空串列時的那個回傳值)。接下來在遞迴的過程中,每一步我們都用首值跟 total 相加,再用剩下的串列,以及這個新加好的 total 當做參數,遞迴的呼叫自己。最後遇到空串列時,直接回傳 total。

再模擬一下我們的 stack,因為永遠只有一層,所以用箭號 => 來表示每個呼叫的歷程:

#1 sum([1,2,3], 0) => sum([2, 3], 1) => sum([3], 3) => sum([], 6) => 6

但是這個函式比較醜…

問題解決了,但是我們的函式從只要一個參數,變成需要兩個參數。呼叫時都要把對我們沒意義的起始值一起傳進去。在 elixir 裡要解決這個問題,有兩個方式:

方案 A: 繼續利用 pattern matching

我們可以用 pattern matching 來定義同名,不同參數個數的函式。像這樣:

def sum(x), do: sum(x, 0)

defp sum([], total), do: total
defp sum([h|t], total), do: sum(t, h + total)

這裡我們把接收兩個參數的 sum 改用 defp 來定義,這是 elixir 裡宣告私有函式 (private function) 的方式。只有在同一個模組裡的程式才能呼叫它。但這不是必須的,用原先的 def 也能正常運作。但這樣的目的是為了不對外界曝露兩個變數的呼叫方式,絕對不是單純只是為了展示語法所編造的例子

方案 B: 參數預設值

如果你希望對外界同時提供一個參數及兩個參數的呼叫方式時,就可以使用參數預設值來解決這個問題。參數預設值的語法如下:

def foo(x \\ 1) do
  ## blah
end

在參數後方加上兩個反斜線 \\ , 並在後面寫上預設值。所以我們的程式可以改成這樣:

def sum([], total), do: total
def sum([h|t], total \\ 0), do: sum(t, h + total)

試著執行看看,會發現雖然可以印出正確的值,但是 elixir 噴了個警告給我們:warning: definitions with multiple clauses and default values require a header. 這段是說因為我們的函式有多個相同參數個數的區塊 (clause),所以要把預設值放在 header 裡。正確的寫法如下:

def sum(list, total \\ 0)
def sum([], total), do: total
def sum([h|t], total), do: sum(t, h + total)

所謂的 head ,就是沒有函式本體 do...end 或是 do: 的函式宣告。

重點回顧

  • 遞迴的函式可能會造成 stack overflow
  • 若 VM 實作了 tail call optimization,且函式呼叫回傳的那一步是一個單純的函式呼叫,不會在 stack 上疊東西
  • 多放一個參數來實作尾遞迴版本的函式
  • 可以用 pattern matching 或參數預設值來解決多一個參數的問題
  • defp 用來宣告私有函式
  • \\ 用來宣告參數預設值
  • 有多個同參數個數的函式版本時,參數預設值要提出來,寫在最上方的 header 裡。

下一篇將討論 guards 及著名的 Pipe operator。

Happy hacking! 明天見。


上一篇
函式、模組,還有那些會跳針的。
下一篇
Guards 與 Pipe operator
系列文
函數式編程: 從 Elixir & Phoenix 入門。31
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言