PLT：說說Evaluation strategy - fsjohnhuang－IT工程師數位筆記本

文章出處

Brief　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

在學習方法/函數時，我們總會接觸到按值傳值和引用傳值兩個概念。像C#是按值傳值，但參數列表添加了ref/out后則是引用傳值，但奇怪的事出現了

namespace Foo{
  class Bar{
    public String Msg{get;set;}
  }
  class Program{
    public static void main(String[] args){
      Bar bar1 = new Bar();
      bar1.Msg = "Hey, man!";
      UpdateProp(bar1);
      Console.WriteLine(bar1.Msg); // Bye!
    }
    static void UpdateProp(Bar bar){
      bar.Msg = "Bye!";
    }
  }
}

Q:UpdateProp明明是按值傳值，對bar的修改怎么會影響到main中的bar1呢？

延伸Q:到底什么是按值傳值、引用傳值？

為了解答上述疑問，我們就需要理解求值策略了！

What is evaluation strategy?　　　　　　　　　　　　　　　　

Evaluation Strategy其實就是定義函數/方法的實參應該在何時被計算，并且以什么類型的值作為實參傳入到函數/方法內部。

A programming language uses an evaluation strategy to determine when to evaluate the argument(s) of a function call (for function, also read: operation, method, or relation) and what kind of value to pass to the function.

那么僅僅是函數調用如 function(a){console.log(a)}({name: 'fsjohnhuang'}) 才關聯到Evaluation Strategy嗎？Assignment Expression就不涉及到嗎？答案是否定的。

// Assigment Expression in C
int* pVal;
int val = 1;
pVal = &val;

// 轉換為Lisp的形式
(= pVal &val)

可以發現Assignment Expression絕對可以轉換為我們熟知的函數調用的形式（前綴表達式），所以各種運算均與Evaluation Strategy有關聯。

以時間為維度，那么就有以下三種類別的求值策略：

1. Strict/Eager Evaluation，在執行函數前對實參求值（實質上是在構建函數執行上下文前）。

2. Non-strict Evaluation(Lazy Evaluation)，在執行函數時才對實參求值。

3. Non-deterministic，實參求值時機飄忽。

另外注意的是，大部分編程語言采用不止一種求值策略。

Strict/Eager evaluation　　　　　　　　　　　　　　　　　　　　

現在絕大部分語言均支持這類求值策略，而我們也習以為常，因此當如Linq、Lambda Expression等延遲計算出現時我們才如此興奮不已。

但Strict/Eager Evaluation下還包括很多具體的定義，下面我們來逐個了解。

Applicative Order (Evaluation)

Applicative Order又名leftmost innermost，中文翻譯為“應用序列”，實際運算過程和Post-order樹遍歷算法類似，必須先計算完葉子節點再計算根節點，因此下面示例將導致在計算實參時就發生內存溢出的bug。

// function definitions
function foo(){
  return false || foo()
}
function test(a, f){
  console.log(a + f)
}
// main thread,陷入foo函數無盡的遞歸調用中
test(1, foo())

Call-by-value或Scalar

按值傳值也就是我們接觸最多的一種求值策略，實際運算過程是對實參進行克隆，然后將副本賦值到參數變量中。

function foo(val){
  val = 3
}
var bar = 1
foo(bar)
console.log(bar) // 顯示1
// 函數作用域中對實參進行賦值操作，并不會影響全局作用域的變量bar的值。

那如Brief中C#那種情況到底是啥回事呢？其實問題在于到底要克隆哪里的“值”了，對于Bar bar = new Bar()而言，bar對應的內存空間存放的是指向 new Bar()內存空間的指針，而因此克隆的就是指針而不是 new Bar()這個對象，也就是說克隆的是實參對應的內存空間存放的“值”。假如我們將Bar定義為Struct而不是Class，則明白C#確實遵循Call-by-value策略。

namespace Foo{
  struct Bar{
    public String Msg{get;set;}
  }
  class Program{
    public static void main(String[] args){
      Bar bar1 = new Bar();
      bar1.Msg = "Hey, man!";
      UpdateProp(bar1);
      Console.WriteLine(bar1.Msg); // Hey,man!
    }
    static void UpdateProp(Bar bar){
      bar.Msg = "Bye!";
    }
  }
}

稍微總結一下，Call-by-value有如下特點：

1. 若克隆的“值”為值類型則為值本身，并且在函數內的任何修改將不影響外部對應變量的值；

2. 若克隆的“值”為引用類型則為內存地址，并且在函數內的修改將影響外部對應變量的值，但賦值操作則不影響外部對應變量的值。

注意：由于第2個特點與Call-by-sharing的特點是一樣的，因此雖然Java應該屬于采用Call-by-sharing策略，但社區還是聲稱Java采用的是Call-by-value策略。

Call/Pass-by-reference

其實Call-by-reference和Call-by-value一樣那么容易被人誤會，以為把內存地址作為實參傳遞就是Call-by-reference，其實不然。關鍵是這個“內存地址”是實參對應的內存地址，而不是實參對應的內存中所存放的地址。C語言木有天然地支持Call-by-reference策略，但可以通過指針來模擬，反而能讓我們更好地理解整個求值過程。

int i = 1;
int *pI = &i; // &i會獲取i對應內存空間的地址，并存放到pI對應的內存空間中

void foo(int *);
void foo(int *pI){
  pI = 2; // 直接操作i對應的內存空間，等同于i = 2
}
int main(){
  foo(pI);
  printf("%s", i); // 返回2
  return 0;
}

內存結構：

而C#可通過在形參上添加ref或out來設置采用Call-by-reference策略，Java和JavaScript就天生不支持也沒有提供模擬的方式。

Call-by-sharing/object/object-sharing

采用該策略的語言暗示該語言主要基于引用類型而不是值類型。

Call by sharing implies that values in the language are based on objects rather than primitive types, i.e. that all values are "boxed".

明顯Java和受Java影響甚深的JavaScript就是采用這種策略的。

該策略特點和Call-by-value的個特點一致。

Call-by-copy-restore(copy in copy out, call-by-value-result, call-by-value-return)

暫時我還沒接觸到哪種語言采用了Call-by-copy-restore這種求值策略，它的運算過程主要分為兩步：

1. 如Call-by-value的特點1那樣，對實參進行拷貝操作，然后將副本傳遞到函數體內。重點是，即使實參為引用類型，也對引用所指向的對象進行拷貝，而不是僅拷貝指針而已。

效果：在函數體內對實參的任何操作（PutValue和Assignment）均不影響外部對應的變量。

2. 當退出函數執行上下文后，將實參值賦值到外部對應的變量。

/*** pseudo code ***/
var a = {}
function foo(a){
  a.name = 'fsjohnhuang'
  console.log('within foo:' + a.name)
  // 線程掛起1000ms
  var sd = +new Date()
  while(+new Date - sd < 1000);
}
// 異步執行foo
var promise = foo.async(a)
while(+new Date - sd < 100);

// 未退出foo的執行上下文時，訪問a.name，返回undefined
console.log(a.name)
if (promise.done){
  // 退出foo的執行上下文時，返回a.name，返回'fsjohnhuang'
  console.log(a.name)
}

Partial evaluation

即是部分實參在進入函數執行上下文前將不參與求值操作。示例如下：

var freeVar = {type: 'freeVar'}
function getName(){
  return freeVar
}
function print(msg, fn){
  console.log(msg + fn())
}

// 調用print時getName將不會被馬上求值
print('Hi,', getName)

可以看到上述print函數調用時不會馬上對getName實參求值，但會馬上對'Hi,'進行求值操作。而需要注意的地方是，由于getName是延遲計算，若函數體內存在自由變量（如freeVar）,那么后續的每次計算結果均有可能不同（也就是side effect）。

Non-strict evaluation(lazy-evaluation/calculation)　　　　

Non-strict Evaluation是指在執行函數體的過程中，需要用到該實參才進行運算的策略。還記得邏輯運算符(||,&&)的短路運算(short-circuit evaluation)嗎？這個就是延遲計算其中一個實例。

下面我們一起來了解4種延遲計算策略吧！

Normal Order (Evaluation)

Normal Order又名leftmost outermost，中文翻譯為“正常序列”，一般通過與Applicative Order作對比來理解效果較好。還記得Applicative Order可能會引起內存溢出的問題嗎？那是因為Applicative Order會不斷地對AST中層數最深的可規約表達式節點優先求值的緣故，而Normal Order則采用計算完AST中層數最淺的可規約表達式節點即可。

/ function definitions
function foo(){
  return false || foo()
}
function test(a, f){
  console.log(a + f)
}
// main thread, 顯示 "1false"
test(1, foo())

Call-by-name

這種延遲計算策略十分容易明白，計算過程就是在執行函數體時，遇到需計算實參表達式時才執行運算。注意點：

1. 每次在執行實參表達式時均會執行運算;

2. 若實參的運算過程為計算密集型或阻塞性操作時，則會阻塞函數體后續命令的執行。（這時會可通過Thunk對Call-by-name進行優化）

Call-by-need

其實就是Call-by-name + Memoized，就是第一計算實參表達式時，在返回計算結果的同時內部自動保存該結果，當下次執行實參表達式計算時直接返回首次計算的結果。注意點：

1. 該策略僅適用于pure function的實參，存在free variable則會導致無法確保每次的求值結果都一樣。

Call-by-macro-expansion

在Clojure中使用macro時則就是采用Call-by-macro-expansion策略，會執行expansion階段對函數體內的實參表達式替換為macro所定義的表達式，然后在進行運算。

Non-deterministic strategies　　　　　　　　　　　　　　　　

另外由于實參的運算時機具有不確定性，因此下面的策略不能歸入Strict和Non-strict求值策略中。

Call-by-future

這是一個并發求值策略，就是將求值操作委托給future，并由后續的promise去完成求值操作，然后調用者則通過future獲取求值結果。注意點：

1. 求值操作可能發生在future剛創建時，也有可能調用future獲取結果時才求值。

Conclusion

上述是查閱各資料后，對幾類求值策略的理解，若有紕漏請大家指正，謝謝！

尊重原創，轉載請注明來自：http://www.cnblogs.com/fsjohnhuang/p/4700102.html 肥仔John^_^

Thanks　　　　　　　　　　　　　　　　　　　　　　　　　　　　

https://en.wikipedia.org/wiki/Evaluation_strategy

http://stackoverflow.com/questions/8848402/whats-the-difference-between-call-by-reference-and-copy-restore

https://en.wikipedia.org/wiki/Thunk#Call_by_name

http://blog.csdn.net/institute/article/details/23750307

http://www.cnblogs.com/leowanta/articles/2958581.html

http://blog.csdn.net/sk__________________/article/details/12848597

http://dmitrysoshnikov.com/ecmascript/chapter-8-evaluation-strategy/

文章列表

Avast 防毒軟體已檢查此封電子郵件的病毒。
www.avast.com

大師兄

IT工程師數位筆記本

大師兄發表在痞客邦留言(0) 人氣()

E-mail轉寄

IT工程師數位筆記本

If you give someone a program , you will frustrate them for a day; if you teach them how to program, you will frustrate them for a lifetime.IT 這段話的意思是，如果你交給某人一隻程式，你將折磨他一整天;如果你教會某人如何寫程式，你將折磨他一輩子。

BloggerAds

PLT：說說Evaluation strategy - fsjohnhuang

歷史上的今天

留言列表

參觀人氣

文章搜尋

最新文章

文章精選

誰來我家

熱門文章

文章分類

最新留言

QR Code

POWERED BY