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。