怎樣理解 Partial Evaluation？

01-06

或者也叫程序特化.

把函數輸入(參數)分成兩部分, 一部分是編譯期已經知道的輸入 input_c (例如調用這函數的時候, 把常量傳給了它), 另一部分是編譯期還不知道的輸入 input_g . 把已知輸入 input_c 代入函數做優化就叫做 partial evaluation. 做這個優化的東西就是 partial evaluator 或者 specializer.

optimized_program specializer(program, input_c);

pure function 在 partial evaluation 的優化中有很重要的作用. C++ 的 constexpr 和 GCC 的 __attribute__((pure)) 也是幫助做 partial evaluation 的. 一般編譯器名詞中 inlining + constant folding + loop unrolling 可以達到相似的效果.

但是 partial evaluation 還有更重大的理論意義, 就是二村映射 (Futamura Projection (扶他就是這個 futa (逃... 見 Compilers for Free

第三種二村映射: 我們把一個 specializer 作為待優化的代碼, 和一個 specializer 做為固定輸入, 扔給一個 specializer, 那就生成一個 compiler compiler, s.t. 這個 compiler compiler 可以接受一個 interpreter 作為輸入, 生成一個 compiler...

這個 compiler compiler 可解決這些問題: 怎麼讓 JRuby 跑得更快, 怎麼優化光線追蹤, 怎麼優化套了好多層的 Monad Transformer ...

然後問題來了, 存在第四種二村映射么? Is there a fourth Futamura projection?

站在解釋器的角度來看，Partial Evaluation概念其實很好理解。

拿最簡單的解釋器舉例子，一般來說解釋器會有兩個參數：一個是要解釋的Expr，以及當前的環境Env。比如Peter Norvig教你怎麼用Python寫的Lisp解釋器，還有Lisp in Small Pieces前兩章的解釋器都是這個結構。
這時候解釋器是從Expr到Value的一個映射，將表達式化簡到不能再進一步化簡的Value。
而Env中包含了變數名到值的Bindings，通過變數名我們可以查找到所對應的Value。如果找不到，那就是有一個Unbound variable，這個時候解釋器應該報錯並停止解釋。

但是對於一個Partial Evaluator來說，則是一個Expr到Expr的映射。解釋器的返回結果仍然是一個表達式，而不是值，這個表達式就叫做Residual program。
但這個時候你去Env中查找變數名所對應的值的時候，如果找不到並不報錯，而是返回literal的Expr本身。與此同時，解釋器變成了non-deterministic的，比如如果if表達式的條件是一個non-Value，那就需要對then和else兩個分支都繼續做PE。
簡單來說，PE是對於能解釋的Expr那就解釋一下變成Value然後inline到程序里，對於不能解釋的Expr那就還是原樣放在那。

對於Function application要稍微複雜一點，簡單來說是區分已知的static argument和在編譯時未知的dynamic argument，把已知的static argument直接inline到function中同時生成出一個特化後的函數。有空再詳細說。上一個簡單的Partial Evaluator代碼可能會更清晰一點。

#lang racket


(struct FDef (args body) #:transparent)

(struct None () #:transparent)
(define (lookup key env)

  (cond [(null? env) (None)]

        [(equal? key (first (first env))) (second (first env))]

        [else (lookup key (rest env))]))
(define (update key val env)

  (cond [(null? env) (list key val)]

        [(equal? key (first (first env)))

         (cons (list key val) (rest env))]

        [else (cons (first env) (update key val (rest env)))]))
(define (op? op)

  (or (symbol=? op "==) (symbol=? op "+)

      (symbol=? op "-)  (symbol=? op "*)))
(define (is-value? v) (or (number? v) (boolean? v)))
(define (aexp op l r)

  (match op

    ["+ (+ l r)]

    ["* (* l r)]

    ["- (- l r)]

    ["== (eq? l r)]))
(define (new-function-name old-name args)

  (string-&>symbol (string-append (symbol-&>string old-name)

                                 (number-&>string (equal-hash-code args)))))
; peval: [(symbol, FDef)] SExpr -&> ([(symbol, FDef)], SExpr)

(define (peval fdefs expr)

  (define (pe expr env)

    (match expr

      [(or (? number?) (? boolean?)) expr]

      [(? symbol?)

       (define val (lookup expr env))

       (if (None? val) expr val)]

      [`(,(? op? op) ,l ,r)

       (define lv (pe l env))

       (define rv (pe r env))

       (if (and (is-value? lv) (is-value? rv))

           (aexp op lv rv)

           `(,op ,lv ,rv))]

      [`(if ,cnd ,thn ,els)

       (define cnd-v (pe cnd env))

       (if (is-value? cnd-v)

           (if cnd-v (pe thn env) (pe els env))

           `(if ,cnd ,(pe thn env) ,(pe els env)))]

      [`(,fname ,args ...)

       (define fun (lookup fname fdefs))

       (define args-v (map (λ (v) (pe v env)) args))

       (define new-env (map list (FDef-args fun) args-v))

       (define-values (statics dyns) (partition (compose is-value? second) new-env))

       (if (empty? dyns)

           (pe (FDef-body fun) statics)

           (let ([new-fname (new-function-name fname statics)])

             (when (None? (lookup new-fname fdefs))

               (set! fdefs `((,new-fname "placeholder) ,@fdefs))

               (set! fdefs (update new-fname (FDef (map first dyns) (pe (FDef-body fun) statics)) fdefs)))

             `(,new-fname ,@(map second dyns))))]))

  (reverse `(,(pe expr "()) ,fdefs)))

(module* test #f (define add (list "add (FDef "(x y) "(+ x y)))) ; (add 1 2) 直接被解釋為3 (check-equal? (second (peval (list add) "(add 1 2))) 3) ; (add 1 a) 則解釋為(add467865875966180528 a) ; 同時生成了一個特化的函數 "add467865875966180528, 也就是(λ (y) (+ 1 y)) (check-equal? (peval (list add) "(add 1 a)) (list (list (list "add467865875966180528 (FDef "(y) "(+ 1 y))) (list "add (FDef "(x y) "(+ x y)))) "(add467865875966180528 a))))

接這個回答：怎樣理解 Supercompilation ？ - 函數式編程

Partial evaluation和Supercompilation一樣，都是試圖在編譯期化簡能化簡的東西。區別在於，Partial evaluation通常使用一套預先準備好的規則特例來化簡，而Supercompilation通常直接基於源語言的語義規則來化簡。

前者的好處是：容易調節優化效果與演算法複雜度的平衡，在某些領域可以根據領域專有知識寫很多根據源語言語義無法直接導出的複雜規則。

後者的好處是：演算法簡單，框架統一，以及（也許）可以給我們一些優化之外的insight。

還有這個問題，我正好在做，而且我能提供一個大家基本不可能想到的關於分散式數據管理的角度。

Partial Evaluation，這個概念自2006年愛丁堡大學ACM Fellow樊文飛老師開始被使用在了分散式XML數據管理方面。

之後，樊老師以及他的學生（Ma Shuai、Cong Gao等人）先後發表了一系列論文討論了如何利用Partial Evaluation在分散式XML數據上處理XQuery、在分散式Graph上處理Reachability Query和Graph Simulation等等問題。

我在2016年VLDB Journal上發表了一個如何利用Partial Evaluation處理分散式RDF數據上的SPARQL查詢的工作。

當前，關於利用Partial Evaluation進行在樊老師這一系列的工作下，已經有了很多理論上的成果。

（當然，這角度過於小眾，除了樊老師，就只有我在這上面做了。而樊老師應該沒時間來知乎上給大家介紹這方面的工作。）

在Partial Evaluation中，一個計算問題被抽象出一個函數f，而用戶的輸入被分成兩部分：已知的部分s和未知的部分d。函數處理階段，局部計算框架首先根據已知的輸入部分s得出部分解，也就是圖上的f』(s)。此時，整個函數也變化成f』』。然後，當未知部分的輸入d被輸入到之後，系統利用f』』根據已知部分輸入的部分解f』(s)與未知部分d一起計算出最終結果。

對於分散式數據管理而言，在有些實際應用中，有些數據因為數據管理以及安全性的考量，會可能會被預先劃分好。比如，有些應用中，系統會希望將相同主題下的實體放在一個分片中，或者有些系統會要求部分敏感的數據放在一個分片中以單獨管理。對於這樣的預劃分好的分散式RDF數據圖，傳統的分散式數據管理方法就不再適用。為此，人們需要提出一個獨立於數據劃分的分散式數據處理方案。而Partial Evaluation就是一個很好的框架。

基於Partial Evaluation的分散式數據管理中，每個機器將存儲在自身的數據視為已知的部分s，而存儲在其他機器上的數據視為未知的部分d。然後，每個機器利用已知部分對查詢求出部分解。最後，這些局部匹配被收集起來並通過連接操作拼成最終解。

在利用Partial Evaluation進行分散式數據管理的過程中，有一個問題至關重要，就是根據每個機器自身存儲的數據找出的局部解應該如何定義。具體而言，對於分散式XML數據上的Boolean XQuery而言，樊文飛老師定義了一種長度為XQuery中點數的位串做為局部解；在分散式Graph數據上的Reachability Query中，樊老師定義了一種長度為邊界點數的位串做為局部解；我的關於分散式RDF數據上的SPARQL查詢處理工作中，我定義了一種本地局部匹配做為局部解。

基於Partial Evaluation的分散式數據管理，在理論上有三個很好的保證。第一個，這個框架能保證對於每個機器只會被訪問一次，也即遠程訪問次數少；第二，如果查詢的是布爾查詢，這個框架能保證通信代價只與跨界數據和查詢相關；第三，如果查詢的是布爾查詢，這個框架能保證計算代價只與跨界數據、查詢和最慢的機器相關。

相關參考文熙如下：

（樊老師與他的學生的文章）

Wenfei Fan, Xin Wang, Yinghui Wu:

Performance Guarantees for Distributed Reachability Queries. PVLDB 5(11): 1304-1315 (2012)

Gao Cong, Wenfei Fan, Anastasios Kementsietsidis, Jianzhong Li, Xianmin Liu:

Partial Evaluation for Distributed XPath Query Processing and Beyond. ACM Trans. Database Syst. 37(4): 32 (2012)

Gao Cong, Wenfei Fan, Anastasios Kementsietsidis:

Distributed query evaluation with performance guarantees. SIGMOD Conference 2007: 509-520

Peter Buneman, Gao Cong, Wenfei Fan, Anastasios Kementsietsidis:

Using Partial Evaluation in Distributed Query Evaluation. VLDB 2006: 211-222

Shuai Ma, Yang Cao, Jinpeng Huai, Tianyu Wo:

Distributed graph pattern matching. WWW 2012: 949-958

（我的文章）

Peng Peng, Lei Zou, M. Tamer ?zsu, Lei Chen, Dongyan Zhao:

Processing SPARQL queries over distributed RDF graphs. VLDB J. 25(2): 243-268 (2016)