Erlang的遞迴與迴圈

昨天我寫九九乘法表,是因為寫氣泡排序法的時候,感覺到某一種陣列與迴圈表達的樣子。(天哪!如果我有寫一本書名叫Patterns in Erlang Programming,一定要把這個點子寫進去。)是一種很微妙的感覺,覺得好像抓到函數語言與一般語言之間的銜接點。

然後,從九九乘法表開始:

for(I, Fe, Fi, Fc) ->
    case Fe(I) of
	true ->
	    Fc(I),
	    I1 = Fi(I),
	    for(I1, Fe, Fi, Fc);
	false ->
	    ok
    end.

fe(I) -> I =< 9.

fi(I) -> I = I+1.

fc(I) -> for(1, fun fe/1, fun fi/1, fc1(I)).

fc1(I) ->
    fun(J) ->
	    io:format("~w x ~w = ~w~n", [I,J,I*J])
    end.

multiple() -> for(2, fun fe/1, fun fi/1, fun fc/1).

程式從multiple/0開始,執行for/4,而fun fc/1函數內容雖然是遞迴,但此時它只是一個函數而已,還沒有執行,內容物不佔記憶體。multiple/0執行遞迴for/4,從 I = 2 執行到 I = 9 ,由for/4的函數定義來看,for(2, …) 呼叫 for(3, …),for(3, …)呼叫for(4, …),依序到for(9, …)。假設這些呼叫都累積在堆疊中。另外看,for(2, …)內容呼叫到fc(2),fc(2)內容是遞迴,不過,執行完了之後,fc(2)內容所佔用的記憶體會放掉,對嗎?然後,後面的for(3, …)、for(4, …)、…等等,各自執行的fc(3)、fc(4)、… 等等執行之後也會釋放掉記憶體。

觀察到此,不曉得我可以不可以寫下一個結論,說,「雖然因為Erlang程式有時處理資料量相當多,造成大量的遞迴及堆疊累積,但是,我們可以藉由函數的分割,將遞迴數量減少」?甚至,我可不可以說,「在記憶體有限的平台上,Erlang程式寫成扁扁平平,將很深的遞迴函數分解成好幾個淺的遞迴函數,就可以避開遞迴堆疊限制」?

不曉得誰能回答我?

廣告

About 黃耀賢 (Yau-Hsien Huang)

熱愛 Erlang ,並且有相關工作經驗。喜歡程式語言。喜歡邏輯。目前用 Python 工作。
本篇發表於 Erlang, Problem。將永久鏈結加入書籤。

3 Responses to Erlang的遞迴與迴圈

  1. 路人甲 說道:

    隔了2年才看到這篇文章,忍不住想回應。
    其實你用的算tail-recursion,erlang的compiler有對tail-recursion做處置過,所以其實不用擔心堆疊累積的問題。
    當然,你若打破tail-recursion的使用原則,一般的recursion,那才要擔心堆疊過多的問題。

    就題目而言99乘法其實可以用單純一點的做法,不見得要用recursion
    既然erlang有List Comprehension,可以改成這樣
    F=fun({A,B})->io:format(“~wx~w=~w~n",[A,B,A*B]) end.
    lists:map(F , [{X,Y}||X<-lists:seq(1,9) , Y<-lists:seq(1,9)] ).
    % 輸出結果最後跑出一堆ok,我就不處置了

    題外話~
    我必須承認,接觸過FP(erlang , haskell)之後,才知道以前學的離散數學是作甚麼用的。

    • 黃耀賢 (Yau-Hsien Huang) 說道:

      你好。我目前正在以 Erlang 工作的辦公室中漸漸熟悉。歡迎你常常來聯絡、討論。

    • 黃耀賢 (Yau-Hsien Huang) 說道:

      這篇文章在 2011 年的時候寫,應該是想要呈現在比較一般的情況下,例如大學一年級學生看過幾本程式書籍,按照他們所看得懂的九九乘法表程式,以 Erlang 呈現。明確地說,應該是 C-ish Erlang 。

      kipper 您所說的沒錯,不過,實際上不管是用遞迴寫,還是用 lists:map/2 寫,兩種計算過程應該是相同的。因為學過函數語言的人都知道 map 的程式長什麼樣子。

      至於目前,我覺得有一種 Erlang-ish 方式的程式寫作方式,因為 Erlang 的重點是訊息分佈式處理,以及 actor model ,所以善用分佈或非分佈計算,是重點。

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s