2008/04/21

Inherited Attributes

Dragon book 進入第五章 syntax-directed translation。本來我以為基本上應該就是 parse tree 上面的 fold,可是與這個概念最直接的對應只是 "S-attributed translations" (S for "synthesised"),另外還有一種 "inherited attributes"。一個 production rule 左側 symbol 的

  • synthesised attributes 是從 production rule body 裡面各個成份的 attributes 合成出來的,而
  • inherited attributes 則是由「該 symbol 在 parse tree 裡面的 parent」所給的值。
Dragon book 在 p.308 給了第一個使用 inherited attribute 的例子,正好就是〈Parser Combinators in Haskell〉最後提到的狀況 ─ non-left-recursive grammars 的形狀和 abstract syntax tree 不一樣。pExpr' 傳回的是個 function ExprTree -> ExprTree,它的 parameter 其實就是 dragon book 所謂的 inherited attribute。Dragon book 接下來就談怎麼判斷 attributes 的求值順序(dependency graphs and topological sort, naturally),因為必須先算好 inherited attribute 的值才能算 Expr' 的 attribute 值。不過在 functional programming 似乎完全不用麻煩,ExprTree -> ExprTree 的解法把求值順序打回最基本的 fold 了。某種層面來看,synthesised attributes 所蘊含的 dependency edges 藏在 fold 的結構裡面,inherited attributes 所帶來的額外 dependency edges 則由 function arrows 表示。求值的時候,電腦就會神奇地根據隱含的 dependency graph 自己找出一個求值順序。

--
這一段和 FP 這邊兩相對照會很有意思 XD。


另外 "acyclic graphs ==> exists topological order" 的證明也很有意思,結構和 foundationalism 對 Agrippan scepticism 的回應一模一樣。我們宣稱這樣的圖裡面必存在一個點,沒有任何入射邊。若不然,Agrippan scepticism 的前提「任何信念都必須由另一個信念證成」(任何點都有入射邊)就滿足了,現在有三種可能:

  • 無窮後退:沿著一條一條的入射邊往回走,無窮下去,但 |V| = finite number,矛盾;
  • 拒絕舉證:到某個信念的時候拒絕提供證成,但這就和前提「任何點都有入射邊」矛盾;
  • 循環論證:沿著入射邊走回某個先前遇過的點,但這就形成 cycle 而與 acyclic graph 的前提矛盾。
我們於是得到一個 fatal trilemma。為了迴避這個 trilemma,foundationalism 宣稱有所謂的 basic beliefs,即「非由其他信念證成的信念」。在 graphs 的情況,就是存在「沒有任何入射邊的點」(然後 by induction on number of nodes 完成證明)。

--
我就直接把兩邊的詞彙混在一起用了 XD。

Labels: , ,

<< 回到主頁