之前學defunctionalization時只知道是把高階函數去了變成一階的，掃了一些文章，Olive的但還是不能理解這樣做的初衷與意義。又看到有人在Haskell類型的層面上這樣做，於是想問問。

@閱千人而惜知己 看了一下wiki，好像有點概念，與您探討，求點評！

-- 對以下函數做defunctionalization變換

data Tree a = Leaf a | Node (Tree a) (Tree a) deriving (Show)

tree1 = Node (Node (Leaf 1) (Leaf 2)) (Node (Leaf 3) (Leaf 4))

cons :: a -&> [a] -&> [a]

cons x xs = x : xs

-- 函數做參數的高階函數

o :: (b -&> c) -&> (a -&> b) -&> a -&> co f g x = f (g x)

-- 函數作為返回值的高階函數

walk :: Tree t -&> ([t] -&> [t])walk (Leaf x) = cons xwalk (Node t1 t2) = o (walk t1) (walk t2)

flatten :: Tree t -&> [t]

flatten t = walk t []

ftt1 = flatten tree1

-- [1,2,3,4]

---- 以下是上面函數的defunctionalization變換 ----

-- 用數據結構Lam來表示原來高階函數應用，

-- LamCons 對應 cons-- LamO 對應 o

-- PS：在實踐當中，這個數據結構用彙編語言來表示

data Lam a = LamCons a | LamO (Lam a) (Lam a) deriving (Show)

-- apply類似解釋器，解釋上面那個數據結構Lam

-- PS：在實踐中，apply可能就是cpu本身……

apply :: Lam a -&> [a] -&> [a]apply (LamCons x) xs = x : xsapply (LamO f1 f2) xs = apply f1 (apply f2 xs)

-- 構造LamCons

cons_def :: a -&> Lam acons_def x = LamCons x

-- 構造LamO

o_def :: Lam a -&> Lam a -&> Lam a

o_def f1 f2 = LamO f1 f2

-- 構造一個與Tree對應的apply數據結構

-- 原來返回函數，現在返回Lam t數據結構

walk_def :: Tree t -&> Lam t

walk_def (Leaf x) = cons_def xwalk_def (Node t1 t2) = o_def (walk_def t1) (walk_def t2)

walk_deft1 = walk_def tree1

-- LamO (LamO (LamCons 1) (LamCons 2)) (LamO (LamCons 3) (LamCons 4))

--

flatten_def :: Tree t -&> [t]

flatten_def t = apply (walk_def t) []

總結：

把高階函數變換成（編譯）一個數據結構，然後用一個apply函數來解釋此數據結構

目的是讓有高階函數抽象的語言用無高階函數抽象或者模擬起來很難的語言（比如C或者彙編）來執行

1. Data flow analysis for HOL

Application
  • Flow-analysis optimization ：common-subexpression elimination, redundant-assignment detection, code hoisting等等 ；
  • Type analysis：類型推導/預測，類型錯誤檢查...（此處單獨列出，當然type analysi可以用在optimization中）
  • Verification and so on..

Problem

CFGs(and SSA) are tricky to build for higher-order programs!

關於Function as first-class的問題，看一個例子

(let ((f (foo 7 g k))
(h (aref a7 i j)))
(if (&< i j (h 30) (f h)))

我們要構造if表達式的CFG，但是h和f的值是動態確定的。

要構造靜態的CFG來做flow analysis，必須分析f和h可能綁定的任意lambda表達式。 而這本身也是個flow analysis問題。

引申一下：為什麼指針分析對flow analysis那麼重要？如果沒有指針，那麼CFG、SSA的構造是非常簡單的。為了構造CFG，要做指針分析，而指針分析本身也是個flow analysis問題。所以目前工業實踐中的指針分析往往限於過程內、上下文和流不敏感。扯遠了。。但是和hol的道理是類似的。。

Attempt
  • Build CFG after CPS transformation
  • Closure conversion, defunctionalization and other transformation
  • ...

既然function as first-class value不利於分析，那麼該怎麼做呢？「Defunctionalization is a program

transformation that aims to turn a higher-order functional program into a first-order one, that is, to eliminate the use of functions as first-class value」。

2. Defunctionalization in MLton

本節直接摘錄http://www.mlton.org/References.attachments/060916-mlton.pdf

Goal
  • eliminate higher-order functions, producing a first-order IL
  • make direct top-level calls, which are easy to optimize
  • make control-flow info available to rest of optimizer
  • optimize closures just like other data structures

Approaches

  • moves nested functions to top level
  • function = tagged record of free variables
  • call = dispatch on tag followed by top-level call
  • control-flow analysis to minimize dispatches

3. Related and Future work

Closure conversion，CPS and SSA

Defunctionalization和closure conversion非常相似。一個是對tag做case analysis，一個是用code pointer做跳轉，瞭解closure conversion的可以將二者做對比。。（詳細區別不再展開。。）

CPS和SSA都是IL（中間語言），可以在轉換成CPS/SSA形式後做def..變換，或者在轉換的過程中做變換。 在這個過程中就可以做一些優化。也有些優化是在變換後進行的。

IL design for program analysis

程序分析非要構造複雜的CFG/SSA（或其他「複雜」的中間表示）麼？有些應用其實並不需要。 比如在用abstraction interpretation做類型分析時，只需要利用AST（抽象語法樹），維護幾個hash形式的env。。王垠的pysonar正式這種思想的體現。

Whole program optimization

Fortran/C編譯器做全局分析、優化的代價很大，更何況ML、Haskell等引入了很多其他的難題（當然，immutable等特性也使某些優化更方便）。

MLton項目是一個積極的嘗試，並且它還有很多優化空間。

Other application and algorithm

formal vefication，security analysis什麼的。。發揮想像力，能做的還有很多。。

closure conversion演算法有這麼多花樣，defunctionzlization也可以再做些文章的（尤其是加入Polymorphic、impressive等特性後）

。。

參考文獻：

Compiling with continuationDefunctionalization at WorkPolymorphic Typed DefunctionalizationControl-Flow Analysis of Higher-Order Language （細節有待補充）

主要就是類型檢查時很容易在closure這裡沒法檢查只能做成例外，即便你類型檢查能做對，去掉的好處是你後面的pass就不需要能處理高階函數了嘛，省點事有啥不好的。

比如，有

f: X -&> Y -&> Z

g: (Y-&>Z) -&> ???

我們只關心 X Y Z 無視 ??? 就是了

檢查 g (f x) 時，我們檢查 x 類型是否為X，是的話，f x類型就是 Y -&> Z，符合 g 的要求。

這樣看似就沒有問題了。但是你繼續往下編譯

假如用一種naive的實現，(f x)的類型就變成了類似

struct {
function *f
X *var_1
}

而 g 裏要調用 (f x) ，假設第一個參數名是 arg1

((function *)arg1)(arg1, y)

實際上，就是在類型上開了個後門，我們不管closure裡面裝的是啥，只要用起來是一樣的，我們就認為他們都是一樣的。

比如又有 h: X -&> Y - &> Y -&> Z (h x y) 就變成

struct {
function *f
X *var_1
Y *var_2
}

這麼做的問題是後面的優化就約等於沒法做了。無論如何要分析這裡面的類型，一定是要找出所有可能傳入這裡的closure的。所以，我認為MLton的做法很好，也不用什麼高難度的技巧，到這一步就是直接做一次whole-program分析把他們都找出來。

我是mlton腦殘粉 (逃
推薦閱讀：
查看原文 >>
相關文章