什麼是更新不可變AST的最簡單方法？

在使用宏時，我已經達到了這個要求（我一直在努力避免它），在那裏我需要更新AST中保持一定條件的那些節點。舉例來說，假設我想更新的每個節點：什麼是更新不可變AST的最簡單方法？

Literal(Constant(1))

與價值：

Literal(Constant(2))

那些AST節點可能是表達式樹中的任何地方，所以我不能使用的ad-hoc模式匹配器。顯然，我想要做的最後一件事是編寫一個完整的模式匹配器，它能夠覆蓋所有的編譯器原語。我一直在尋找API，但我有一個印象，收集和可穿越家庭不夠好，以滿足我的需要，因爲他們把樹看作線性的東西，我希望整個更新樹作爲結果。那麼，是否有可能以智能的方式更新不可變表達式樹？爲什麼在標準API中不存在這樣的'更新'操作？

來源

2012-07-09 jeslg

對於插件有一個TreeTransformer。我想，宏必須有一個類似的，可能甚至是相同的。 – pedrofurla 2012-07-09 15:17:40

也許你會想看看[拉鍊]（http://anti-xml.org/zippers.html） – 2012-07-09 15:21:21

@NikitaVolkov，我想說，如果他沒有問宏的上下文。 – pedrofurla 2012-07-09 15:39:41

下面是一個宏觀的Scala使用AST變壓器的例子：

https://github.com/retronym/macrocosm/blob/171be7e/src/main/scala/com/github/retronym/macrocosm/Macrocosm.scala#L129

來源

2012-07-09 18:57:14 retronym

我真的必須查找Transformer的源代碼。它看起來像XML轉換庫，並且該庫在樹的深度上具有指數性能。 – 2012-07-09 20:21:43

這個問題的答案是：這是關於自頂向下還是自下而上的遍歷？在自頂向下的遍歷中，更改葉子意味着重建上面的樹。在上面的鏈接中，traceImpl的實現表明，新樹是從下至上構建的（至少在那裏）。但是，一般來說，這取決於你如何調用'super.transform'。 – Blaisorblade 2012-07-27 01:33:05

通常修改數據結構中的多類型節點是數據類型泛型的一個經典情況（通過類型構造函數對代碼進行參數化）。

這些操作存在幾種方法，如定義數據類型泛型遍歷函數的"Scrap Your Boilerplate"方法。

在Haskell，節點更新功能是在兩個維度參數：由數據類型和代碼 - 這樣你就可以應用不同的更新功能，以不同的類型，在任何地方的結構：

-- | Apply a transformation everywhere in bottom-up manner 
everywhere :: (forall a. Data a => a -> a) 
      -> (forall a. Data a => a -> a)

這樣做的Haskell嚴重依賴於類型類。在Scala中，有幾個ported examples

來源

2012-07-09 15:19:30

什麼是更新不可變AST的最簡單方法？

回答

相關問題