Erlang裏頭怎麼掌控Laziness呢?

[黃耀賢 (Yau-Hsien Huang)]

嗨，大家好。

我一直著迷於一種稱為Parser Combinator的技巧。

讀的是Graham Hutton的文章 "Higher Order Functions For Parsing"

然後覺得似乎都要有lazy evaluation才玩得起來。

聽人說過Erlang要弄lazy evaluation是要自己做的。

所以我想可能用以下二個裝置可以很簡單做惰式計算的雙向處理：

   lazy(Func) -> fun()-> Func end.

   eval(LazyFunc) -> LazyFunc().

第一個說拿到什麼函數都可以戴上一個 fun()-> ... end 包裝，就會是 lazy ，

第二個則是拿到惰式函數就做一次 applying 把它解成普通函數。

結果仍然卡在 Hutton 文章中的 many/1 那一題。

因為是開始走遞迴了， many/1 若加上 Erlang 的普通函數，在測試parsing時

都會進入停不注的遞迴過程。不知道要怎樣才能有效地做成順暢的parser combinator。

我的半程式附在文末，請指教，謝謝。

=================== parsec.erl =============================

-module(parsec).

-compile(export_all).

lazy(Func) -> fun() -> Func end.

eval(LazyFunc) -> LazyFunc().

cons({X,Y}) ->

    if is_atom(Y) -> [X|[Y]];

       true -> [X|Y]

    end.

succeed(V) ->

    eval(lazySucceed(V)).

fail() ->

    eval(lazyFail()).

lazySucceed(V) ->

    lazy(fun(Inp) -> [{V, Inp}] end).

lazyFail() ->

    lazy(fun(_Inp) -> [] end).

satisfy(P) ->

    eval(lazySatisfy(P)).

   

lazySatisfy(P) ->

    lazy(fun(Inp) ->

case Inp of

    [] -> (fail())([]);

    [X|Xs] -> case P(X) of

  true -> (succeed(X))(Xs);

  false -> (fail())(Xs)

      end

end

end).

literal(X) ->

    lazySatisfy(fun(Y)-> Y == X end).

lazyLiteral(X) ->

    lazy(lazySatisfy(fun(Y)-> Y == X end)).

alt(Parser1, Parser2) ->

    fun(Inp) -> Parser1(Inp) ++ Parser2(Inp) end.

lazyAlt(LazyParser1, LazyParser2) ->

    lazy(fun(Inp) -> (eval(LazyParser1))(Inp) ++ (eval(LazyParser2))(Inp) end).

then(Parser1, Parser2) ->

    fun(Inp) ->

   [ {{V1,V2},Out2} || {V1,Out1} <- Parser1(Inp),

{V2,Out2} <- Parser2(Out1) ]

    end.

lazyThen(LazyParser1, LazyParser2) ->

    lazy(fun(Inp) ->

[ {{V1,V2},Out2} || {V1,Out1} <- (eval(LazyParser1))(Inp),

    {V2,Out2} <- (eval(LazyParser2))(Out1) ]

end).

using(Parser, Func) ->

    fun(Inp) -> [ {Func(V),Out} || {V,Out} <- Parser(Inp) ] end.

lazyUsing(LazyParser, Func) ->

    lazy(fun(Inp) -> [ {Func(V),Out} || {V,Out} <- (eval(LazyParser))(Inp) ] end).

many(LazyParser) ->

    lazyAlt(lazyUsing(lazyThen(LazyParser, lazy(many(LazyParser))), fun cons/1), lazySucceed([])).

=========================================================

[黃耀賢 (Yau-Hsien Huang)]

嗨，大家好。

抱歉上次突然丟這個訊息但沒有解釋得足夠多，可能人們覺得比較陌生。

我想介紹所謂 Parser Combinators 這種程式技巧，並且介紹我在Erlang語言上

給自己找到的解答。

On Tue, Jun 5, 2012 at 5:57 AM, 黃耀賢 (Yau-Hsien Huang) <g9414002.p...@gmail.com> wrote:

嗨，大家好。

我一直著迷於一種稱為Parser Combinator的技巧。

讀的是Graham Hutton的文章 "Higher Order Functions For Parsing"

然後覺得似乎都要有lazy evaluation才玩得起來。

Parser是根據一串文字的格式，將這串文字拆解成好幾個段落。為了符合

所處理的文字內容，通常會預設文字內容都會符合一套文法。而文法，

通常用BNF定義。在BNF中，我們會看到像 | 這個符號代表提供二種 parsing

rules 的選擇，另外有先parse某個符號然後忽略這個符號、之後要parse

譬如說一串浮點數這樣的文字內容。

Parser Combinators 是認為可以將幾個最基本的parsing運算定義為基本

單元，然後幾個parsing運算之間可以做類似shell command的pipe-line

串連。前文所提 Graham Hutton 的文章 "Higher Order Functions For Parsing"

即介紹這一種程式技巧。

用Erlang語言來想，假設有個parser可以解一段文字 "1+2-3" 此數學算式，

當parser成功解掉那段文字，我們可得到輸出值為：

    [ {"(1+2)-3", []}, {"1+(2-3)", []} ]

然而若讓這個parser解 "1+2-" 這段文字，因為不符合文法，所以輸出值為：

    []

Hutton之文章是以函數語言為討論基礎，語言預設有 lazy evaluation 策略，

像Haskell語言那樣。但以Erlang語言來看，Erlang預設為 eager evaluation 策略，

意思是如果有以下的式子：

    f(g(), h())

g, h二個函數一定先執行，然後執行 f 函數。不過雖然如此，仍可以用語言

技巧將 lazy evaluation 明確地指定出來。我認為有二種方式算是 lazy evaluation，

一種是把函數名稱當做參數使用：例如以下一行，

    fun g/0

它只是一個函數、不接收任何參數，並且函數還沒執行，而是要等到你給足

參數之後才會執行。第二種方式是將函數多加套一層lambda expression格式：

    fun() -> ... end

就讓各種函數變成 lazy ：例如，本來有個函數求二數相加，

    f(X, Y) -> X + Y.

改成 lazy 版本為

    f(X, Y) ->

        fun() -> X + Y end.

同樣呼叫 f(5, 3) 的時候，後一個版本變成是一個函數，要到呼叫寫成 (f(5,3))()

的時候才會計算 5 + 3 。

Lazy evaluation 對 parser combinators 很重要，因為很多文法定義都是遞迴定義。

如果走 eager evaluation 會把文法規則程式卡死。 Lazy evaluation 也是我自己用

Erlang實作這個時，時常卡到的問題。

====================================

那麼，可以開始介紹Parser Combinators的實作過程。

先定義parsing輸出資料為以下格式：

    [ { parse出來的值, 剩下未parse的文字 }, ... ]

首先可以定義幾個基本parsing單元。 fun succeed/1 是無條件parsing成功，

fun fail/0 是無條件parsing無效， fun satisfy/1 是根據一個邏輯判斷決定是否

parsing成功。

    succeed(V) ->

        fun(Input) -> [{V, Input}] end.

    fail() ->

        fun(_Input) -> [] end.

    satisfy(Predicate) ->

        fun(Input) -> case Input of

                                [] -> (fail())();

                                [X|Xs] -> case Predicate(X) of

                                                  true -> (succeed(X))(Xs);

                                                  false -> (fail())([X|Xs])

                                              end

                             end

         end.

在此每個函數都先接收基本必要的參數，然後要等待一段文字當作 Input 參數。

我覺得 fun(Input) -> 就代表了有 lazy evaluation 效果的等待。

那就可以定義解一個字母的parser為 fun literal/1 ：

    literal(A) ->

        satisfy(fun(X)-> X == A end).

這樣，像 (literal(a))([a,b,c]) 就可以解出為 [{a, [b,c]}] 。而假如解不出來，

像 (literal(a))([b,c,d]) ，輸出值則是 [] 。 Parsing 成功或失敗的定義很明確。

四則運算的BNF定義，開頭可能像

    Expr ::= Factor '*' Expr | Factor '/' Expr | Term

是說算式可能是乘法式子或除法式子、或一個普通式子。這裏的「或」是一個

parser combinator ，定義為 fun alt/2 ：

    alt(Parser1, Parser2) ->

        fun(Input) -> Parser1(Input) ++ Parser2(Input) end.

fun alt/2 是指二個parsers各自解同一段輸入文字，各自產生輸出值，二份輸出值

合起來算是整個完成的結果。

fun then/2 同樣拿二個 parsers ，先用一個解文字，解出來剩下的未parsing文字

再給另一個parser解。所以程式是：

    then(Parser1, Parser2) ->

        fun(Input) ->

             [ { {V1, V2}, Out2 } || {V1, Out1} <- Parser1(Input),

                                     {V2, Out2} <- Parser2(Out1) ]

        end.

如果多次使用 fun then/2 ，看使用的結構如何，輸出值也符合相同結構。像是

(then(literal(a), then(literal(b), literal(c)))([a,b,c]) 產生 [{{a,{b,c}}, []}] ，而

(then(then(literal(a), literal(b)), literal(c)))([a,b,c]) 產生 [{{{a,b},c}, []}] 。輸出值

基本收在tuple中，而因為tuple是有限元素的ordered pair，特性不如 list 好用，

所以會有 fun using/2 和 fun cons/1 來幫忙讓 {V1, V2} 變成 [V1, V2] 。

    using(Parser, Func) ->

          fun(Input) ->

                [ { Func(V), Out } || {V, Out} <- Parser(Input) ]

          end.

    cons({X,Y}) ->

          if is_list(Y) -> [X|Y];

             true        -> [X|[Y]]

          end.

所以，像有些BNF要定義 S ::= T * 表示有連續0個或多個 T ，可以定義為

fun many/1 ：

    many(Parser) ->

           fun(Input) ->

                 (alt(using(then(Parser, many(Parser)),

                                 fun cons/1),

                       succeed([])))(Input)

           end.

用起來像 (many(literal(a)))([a,a,b]) 會解出 [{[a,a], [b]}, {[a], [a, b]}, {[], [a,a,b]}]

這樣，把所有連續任意多個 a 的解出結果都拿出來。

在這裏提一下之前我卡到的 lazy evaluation 不成功的心得。我發現如果 fun many/1

寫成像以下錯誤的寫法：

    many(Parser) ->

          alt(using(then(Parser, many(Parser)),

                         fun cons/1),

               succeed([])).

雖然按照函數語言的用法感覺很對，但是執行 many(literal(a)) 就啟動一個無窮

遞迴過程。 而寫成前面那個版本，因為多了 fun(Input) -> ...(Input) end ，讓它

遞迴呼叫多了一些舒緩 laziness 的過程，就可以執行了。我不知道要如何解釋

它那樣可以、這樣卻不行的具體理由。

接著以 fun some/1 做結尾。BNF會定義 T+ 代表至少有一個或者更多個 T 。

fun some/1 定義這個文法：

    some(Parser) ->

         fun(Input) ->

               (using(then(Parser, many(Parser))

                          fun cons/1))(Input)

         end.

Best Regards,

Y.-H. Huang

[omusico]

請問一下 你講的類似 匿名函式的惰性求值嗎？

--
您已訂閱「Google 網上論壇」的「Erlang_Taiwan」群組，因此我們特別傳送這封郵件通知您。
如要在此群組張貼留言，請傳送電子郵件至 erlang...@googlegroups.com。
如要取消訂閱此群組，請傳送電子郵件至 erlang_taiwa...@googlegroups.com。
如需更多選項，請造訪此群組：http://groups.google.com/group/erlang_taiwan?hl=zh-TW。

[黃耀賢 (Yau-Hsien Huang)]

我講的就是匿名函式和惰性求值。不過，要將二者分別澄清。

匿名函式 (lambda expression) 和惰性求值 (lazy evaluation) 是二種不同語言特徵。

前者是已經發明了80年的一種表達方式，用來定義任何函數，後者是指一種程式

執行策略。

匿名函式不一定會搭配著惰性求值。以Haskell來說，執行策略都是惰性，即使

具名函式也是惰性。但以Erlang來說，執行策略是即性的 (eager) 。但我需要讓

一個Erlang函數可以稍微停一停，稍微lazy一點，而使用惰性求值的特徵讓一個

Erlang函數等待它的參數，如果沒有給參數就停著，讓同一式子的其他部份可以

執行。這或許是一種技巧上的惰性求值。

2012/6/9 omusico <omu...@gmail.com>