[☭脑瘫党群☭][5686] 关于惰性求值与优化

DoDo理解到了惰性求值(延时求值)的绝对优势了。.net 3.x 里面加入的 Linq 为什么被我们如此看中了(事实上，准确的说C#对于Lazy Evaluation的支持来自于.net 2.0加入的关键字 yield return，只是在.net 3.x中由于lambda、Linq、Type Inference、Common Generic Delegates等一系列Feature的加入，使得这个东东变使用更加方便)。

为了解释这个问题，我写两个C#的版本：

实时求值 1：

var Double = (double xs)=> 2*xs;

var list =  new double[] { 1, 2, 3, 4, 5 };

foreach ( var fo in list)

    Console.WriteLine(Double(Double(Double(fo))));

这个版本只遍历，一次求值一次～但是处理的是元素，而不是列表。

因此修改一下：

实时求值2：

/*

 * Func<T,TResult> represents a functions like this: TResult foo(T arg).

 * So Func<IEnumerable<double>,.IEnumerable<double>> represents IEnumerable<double> foo(IEnumerable<double> arg)

 * 

 * Func<double,double> Double = delegate(IEnumerable<double> xs)  is a declaration of an anonymous method that introduced in .net 2.0.

 * It somehow made C# support LUA style function declaration that make assign a function to a variable, also it is just a syntactic sugar. 

 */ 

Func<IEnumerable<double>,IEnumerable<double>> Double = delegate(IEnumerable<double> xs) 

{

    var result = new List<double>();

    foreach(var fo in xs)

        result.Add(2*fo);

    return result;
}

var list =  new double[] { 1, 2, 3, 4, 5 };

var resultList = Double(Double(Double(list))));

foreach( var fo in resultList)

    Console.WriteLine(fo);

这个版本虽然处理了列表，但是却生成了3个临时的List。而且最重要的resultList的类型事实上是List<double>，是一个真实存在的集合，及时我们最后不打印resultList的值，他也会存在。

接着我们引入yield return，去实现一个延时求值的版本

延时求值1：

Func<IEnumerable<double>,IEnumerable<double>> Double = delegate(IEnumerable<double> xs) 

{

    foreach(var fo in xs)

        yield return 2 * fo;

}

var list =  new double[] { 1, 2, 3, 4, 5 };

var resultList = Double(Double(Double(list))));

foreach( var fo in resultList)

    Console.WriteLine(fo);

这段实现明显已经没有中间列表的产生了～而且由于yield return的出现，已经引入了延时求值。resultList的类型不再是一个List<double> 而是 Func<IEnumerable<double>,IEnumerable<double>>，如果不遍历它(就是不执行最后的那个 foreach 块)，它就不会被求值。

从之类看来，已经和haskell非常近似了～但是还不够～由于Anonymous  Method的语法的复杂性，明显 Haskell 的语法要比 C# 简洁得多，于是我们引入LINQ

延时求值2：

我们重写 Double为

var Double = from fo in list

                   select 2*fo;

这个是个不完全的版本，为什么，因为LINQ语句的原因，Double的类型变为了IEnumerable<double>，变成了一个确定的值，而不再是一个函数，因此我们不能使用函数调用这种模式了。因此我们再改改

延时求值3：

var Double =  

           (IEnumerable<double> xs) => 

                  from fo in xs

                  select 2*fo;

var list =  new double[] { 1, 2, 3, 4, 5 };

var resultList = Double(Double(Double(list))));

foreach( var fo in resultList)

    Console.WriteLine(fo);

于是这个版本也变得非常简洁了，稍微比Haskell、LUA等动态脚本语言稍微复杂了一点，不过对于强类型的OO语言来说已经很不错了。

观察一下这个最终版本，我们在里面运用了yield return(其实就是根据方法，自动生成一个枚举器类)、Linq(那个from * select * )、Lambda Expression( 那个(*)=> * )、还有Type Inference(var * =*)以及Common Generic Delgates(隐性的使用了Func<T,TReslt>，即Lambda的类型和Type Inference的结果，也就是 Double的类型)

由此看来C#其实是具有很多函数编程的特性的，所以有人说 C# 其实是一个半函数编程的语言。

不过个人觉得把惰性求值理解为一个理念，一个Pattern，要比把它当作一个语言特性强。从C#看来～虽然最后这个版本是一个延时求值的版本，但是其实我们可以把编译器帮我们做的所有工作完全展开（就像展开Macro那样展开），我们可以得到一个有C#基本特性而实现的延时求值代码（最简单的方法就是编译为MSIL，然后反编译回来）。

不仅仅是C#，我有信心在C语言里也实现同样的东西。

TimNew
------------
Release you passion
To Realize you potential
---------------------------------
Tip Of the Day:

Thomas A. Edison  - "Discontent is the first necessity of progress."

2009/4/16 米良 <timnew.wti@gmail.com>

一看那个"[==[ ]==]"风格的字符串的括弧就知道DODO 现在LUA中毒中～

TimNew
------------
Release you passion
To Realize you potential
---------------------------------
Tip Of the Day:

Maya Angelou  - "Nothing will work unless you do."

2009/4/15 Ning Yu <yuningdodo@gmail.com>

今天看到某篇文章中关于惰性求值的一段有趣说明. 先看例子.

[=haskell=[
list = [1 .. 4]

double x:xs = x * 2 : double xs
double [] = []

result = double $ double $ double list

print result
]=haskell=]

上面这段 haskell 代码的含义大体与下面的 lua / python 代码等效, 可以参照着理解

[=lua=[
function double(xs)
    res = {}
    for i = 1, #xs do
        x = xs[i]
        table.insert(res, x * 2)
    end
    return res
end

list = {1, 2, 3, 4}
result = double(double(double(list)))
]=lua=]

[=python=[
def double(xs):
    res = []
    for x in xs: res.append(x * 2)
    return res

list = range(1, 5)
result = double(double(double(list)))
]=python=]

我们知道, double 函数的作用是将一个列表中的所有值 x2, 并返回一个新的列表. 那么问题来了, 在 haskell 版本中, 究竟生成了几次新列表呢? 或者说程序运行过程中经过了几次对列表的 "遍历" 操作呢?

对于 lua 或者 python 的这两个版本, 不用说, 每调用一次 double() 进行一次遍历, 再生成一个新的列表. 对于 haskell 这样的纯 FP 来说, 由于惰性求值的存在, 为了保证 result 一定被调用, 后面我特意写了一句 print result, 就是假定我们至少执行过一次了, 否则根本就不会产生任何动作. 那么当打印 result 的第一个元素时, 这时 result 向第一层 double 请求第一个结果, 这个请求又被传至第二个 double, 直至传到 list, 它的第一个元素被返回, 并依次进行 3 次 x2 操作, 得到 8; 对于 print 导致的对 result 后面每个元素的请求都是这样. 因此结果就是, 遍历只发生了一次. 不过究竟这过程中生成了几个列表我还没有想明白. 但是总之就是理论上 FP 的优化能力要高于命令式语言, 虽然实际情况上至少 haskell 很慢.

以前虽然知道惰性求值这个概念, 也有意无意地使用过它, 不过还真就没有从计算流程的角度仔细考虑过这个问题.

--~--~---------~--~----~------------~-------~--~----~
脑瘫党内部密信
邮件列表地址：NTParty@googlegroups.com
草稿模式发布：NTParty+unsubscribe@googlegroups.com
英文Web主页：http://groups.google.com/group/NTParty
中文Web主页：http://groups.google.com/group/NTParty?hl=zh-CN
-~----------~----~----~----~------~----~------~--~---

Posted via email from timnew's posterous