Hello World
Spiga

趣味编程:在JavaScript中实现简单的yield功能(2 - 循环支持及解释执行)

2010-06-11 20:41 by 老赵, 2096 visits

上一篇文章里,我们构造了$yield和$yieldSeq两个基础编程组件,于是我们可以“在一定程度上”使用C#中的yield功能来构造一个迭代器。从表面上看来似乎不错,不过它的实际价值还是有值得推敲的。例如,我们目前还必须使用递归来代替循环,那么我们有办法改变这种变成方式吗?此外,在评论中有朋友谈到,这样写代码其实不是一个格式化就混乱了吗?至少,您是否觉得这种编程方法的function和括号实在多了些呢?这次我们就来探索这些问题的解决办法。

想法来源

为此,还是先谈一下我这种想法的来源吧——这便是F#里的“序列”:

// F#
let fibSeq() = seq {
    let rec fibSeq' a b = seq {
        let next = a + b
        yield next
        yield! fibSeq' b next
    }

    yield 0
    yield 1
    yield! fibSeq' 0 1
}

瞧,这个无限的斐波那契序列实现方式,和之前的JavaScript做法是否几乎完全一致?其实在F#中,seq本身(从理念上讲)并不是个语言特性,而是基于一种更为抽象的语言特性“(计算表达式)Computation Expressions”而实现的功能。换句话说,seq只是一个“类库”,和我以前经常强调的async一样,都不是语言特性而是类库功能。我们基于这个语言特性也可以写出我们自己的实现,这样我们也可以用上xyz { ... }等等,而不仅仅是seq { ... }或async { ... }等“内置”的功能了。

Computation Expressions其实是一种“语法糖”,如刚才的fibSeq在“解糖”之后就变成了:

// F#
let fibSeq() = seq {
    let rec fibSeq' a b =
        let next = a + b
        seq.Combine(
            seq.Yield(next),
            seq.Delay(fun () -> 
                seq.YieldFrom(fibSeq' next b)))

    seq.Combine(
        seq.Yield(0),
        seq.Delay(fun () ->
            seq.Combine(
                seq.Yield(1),
                seq.Delay(fun () ->
                    seq.YieldFrom(fibSeq' 0 1)))))
}

总体来说,它们都是把顺序的语法拆成了一段一段,再通过回调函数进行连接的结果。事实上,“计算表达式”便是定义了一系列的“基础控制元素”,然后将一系列的表达式“解糖”为这些基础控制元素的调用。有些朋友可能发现这其实便是Monad(类似的东西),这话一点没错,F#的设计者Don Syme便曾经写道

... Likewise the kinds of operations used under the hood are much like the operations used in both LINQ and Haskell monads. Indeed, computation expressions can be seen as a general monadic syntax for F#.

如果不看实际的代码样式,只看“感觉”,您是否发现这和前文的做法十分接近?其实刚才我之前的JS其实也是利用了这种思路,只是直接写出了“解糖”后语法(且解糖的具体方式有所不同),于是会显得比较丑陋——因此,谁说语法糖不重要?

while循环

其实F#的计算表达式中也提供了对于while循环的基础构造元素,这对我们现在要做的事情来说像是一个指导。那么我们来看看F#是如何“解糖”while语句的吧。假如我们有这样一个计算表达式:

// F#
foo {
    let i = ref 0;
    while (i.Value < 10) do
        i.Value <- i.Value + 1
    ...
}

那么它解糖后的结果便是:

// F#
let i = ref 0;
bar.While(
    (fun () -> i.Value < 10),
    (fun ()  -> i.Value <- i.Value + 1))

换句话说,当我们使用这样的表达式时:

// F#
while (cond-expr) do
    loop-body

实际上我们执行的是:

// F#
// member While: (unit -> bool) * Result<unit> –> Result<unit>
foo.While(
    (fun () -> cond-expr),
    (fun () -> loop-body))

看到了没?我们不妨也这么做吧。例如当我们在C#里写这样的代码时:

// C#
public static IEnumerable<int> Infinite(int start)
{
    while (true) yield return start++;
}

它所对应的JavaScript便是:

// JavaScript
function infinite(start) {
    return $while(
        function () { return true; },
        function () { return $yield(start++); });
}

其中$while方法的实现是:

// JavaScript
function $while(cond, body, rest) {
    if (cond()) {
        var iter = body();
        if (iter) {
            return $yieldSeq(iter, function () {
                return $while(cond, body, rest);
            });
        } else {
            return $while(cond, body, rest);
        }
    } else if (rest) {
        return rest();
    } else {
        return null;
    }
}

$while本身也是返回一个迭代器,不过它并不会像$yield或$yieldSeq那样“构造”出一个迭代器,而更像是在做一个“协调”的工作。例如,当cond为false时,它将直接返回后续的迭代器;否则,便会从body生成一个迭代器对象,并将下一个$while,也就是需要重新执行的内容使用$yieldSeq函数“拼接”在最后。由此我们可以看出(至少我感觉如此),使用无副作用的编程方式,在业务逻辑的表现上会比“状态改变”更为清晰一些。

先解析,后执行

现在,我们就试着使用刚才定义的$while函数来重写原来的rangeSeq函数吧:

// JavaScript
function rangeWhileSeq(minInclusive, maxExclusive) {
    var i = minInclusive;
    return $while(
        function () { return i < maxExclusive; },
        function () {
            return $yield(i, function () {
                i++;
            });
        });
}

额,您看明白这段代码的含义了没?总之我是看的够呛,光有yield还好说,一旦加上$while就容易让人神智不清了。更重要的是,我这里真不知道怎么格式化才能显得清晰一些。因此,$while的可用性远不如$yield和$yieldSeq来的好。那么,我们该怎么办才好?先不谈这个,先想想我们究竟希望怎么样的编程方式吧……这样如何?

// JavaScript
function rangeWhile(minInclusive, maxExclusive) {
    var i = minInclusive;
    while (i < maxExclusive) {
        return $yield(i);
        i++;
    }
}

这完全就是一种最为理想的方式,不是么?易于编写,语意良好,格式美观,几乎没有缺点。那么,您有办法将这个rangeWhile方法“改写”成上面rangeWhileSeq的形式吗?还有,您能把这样的代码:

// JavaScript
function fibSeq() {
    function fibSeq$(a, b) {
        var next = a + b;
        return $yield(next);
        return $yieldSeq(fibSeq$(b, next));
    }

    return $yield(0);
    return $yield(1);
    return $yieldSeq(fibSeq$(0, 1));
}

改写成如下形式吗?

// JavaScript
function fibSeq() {
    function fibSeq$(a, b) {
        var next = a + b;
        return $yield(next, function () {
        return $yieldSeq(fibSeq$(b, next));

        });
    }

    return $yield(0, function () {
    return $yield(1, function () {
    return $yieldSeq(fibSeq$(0, 1));

    });
    });
}

我相信这实现起来不会过于困难。

事实上,我认为这可以说是JavaScript语言最终极的黑魔法。由于JavaScript的语言特性,我们完全可以调用一个函数的toString方法,再进行“改造”,最后再eval回去。利用这种方式,JavaScript可以说拥有了几乎无限的语法糖能力。事实上,类似的事情一直有人在做。例如,已经有人用JavaScript写出Flash播放器以及PostScript解释器。因此,我们为什么不把这种方式直接用在JavaScript自身呢?

提高JavaScript的开发效率

再次回到F#吧。刚才我们提到,计算表达式的试用性很广,除了seq以外,F#的核心库还实现了“异步工作流(Asynchronous Workflows)”。例如下面的代码:

// F#
async {
    let req = WebRequest.Create("http://blog.zhaojie.me/")
    let! resp = req.GetResponseAsync()
    use stream = resp.GetResponseStream()
    let reader = new StreamReader(stream)
    let! html = reader.ReadToEndAsync()
    return html
}

便会被“解糖”为:

// F#
async.Delay(fun () ->
    let req = WebRequest.Create("http://blog.zhaojie.me/")
    async.Bind(req.GetResponseAsync(), (fun resp –>
        async.Using(resp.GetResponseStream(), (fun stream –>
            let reader = new StreamReader(stream)
            async.Bind(reader.ReadToEndAsync(), (fun html ->
                async.Return(html))))))))

这里let!会被视作一次Bind函数的调用,F#在此会发起一个异步操作(如一个基于IOCP的异步操作),并会在操作结束后执行回调函数。这样,我们便可以使用异步工作流轻松地编写异步程序,而不需要在纷繁的回调函数中纠缠不清。循环也好,递归也罢,异步工作流都会帮我们保留各式上下文,按照我们的需要进行逻辑控制。

这就是了。刚才我们提出在JavaScript中解析“迭代器”的生成代码,那么我们能用同样的方式实现一个完整的“计算表达式”特性吗?事实上,这样JavaScript就几乎获得了完整的,与F#一样强大且优雅的特性。更重要的是,“异步操作”是JavaScript的应用领域中最为常见的使用场景(没有之一),如果JavaScript拥有了F#中的“异步工作流”,那么JavaScript的开发体验一定会大大增强。

我认为,首先于语言特性,JavaScript本身的生产力似乎已经遇到了瓶颈,必须借助“外力”才能带来更好的开发效率。例如GWTScript#,都是通过编写服务器端的代码(如Java和C#)再编译成JavaScript以获得更好的开发效率(虽然Anders Hejlsberg认为并不认为这是正途)。在这方面,我认为走的更远的是莫过于WebSharper,它是一个基于F#构建的Web开发平台,使用F#构造从前到后的一整套内容。其中利用到F#中许多高级的开发特性,并可以将F#代码直接转化JavaScript,这样服务器端和客户端的通信也变得透明起来。事实上我很看好这种方式,尤其是在HTML 5出现之后,越来越多的东西可以使用JavaScript编写,我认为这是增强Web平台开发效率的方向之一。

当然,如WebSharper这类与平台(.NET,F#)密切相关的产品,其实适用性会受到限制。不过,如我上面说的那样,如果可以用JavaScript开发出一套“解释器”,或是一种可以大大提高生产力的语法糖,其通用性一定会更高,且更容易被前端开发人员所接受。

相关文章

Creative Commons License

本文基于署名 2.5 中国大陆许可协议发布,欢迎转载,演绎或用于商业目的,但是必须保留本文的署名赵劼(包含链接),具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言

Add your comment

24 条回复

  1. 老赵
    admin
    链接

    老赵 2010-06-11 20:45:03

    其实每种语言都可以使用这种方式,例如在Pre-Build里改造代码,然后再进行编译,呵呵。

  2. infinte
    60.166.104.*
    链接

    infinte 2010-06-11 21:20:51

    @老赵:

    我正在做的一个叫lofn的语言就是“Lofn-JS翻译器”。到我的博客上看一下细节。

  3. zzfff
    113.141.29.*
    链接

    zzfff 2010-06-11 22:35:59

    Anders同学大概会这么做:LINQ to JS

    Expression<Func<IEnumerable<int>>> e = () => 
    {
        yield return 1;
        yield return 2;
    };
    

    诸多原因,编译不过。我认为“LINQ to XX”就是(初级)元编程。

  4. 老赵
    admin
    链接

    老赵 2010-06-11 22:44:11

    @zzfff

    其实这和LINQ关系不大,只是Expression Tree吧。这已经不是“Expression”,而是“Statement”了,现在的确不会支持。当然……就算支持了,能不能支持yield也是个问题,呵呵。

  5. zzfff
    113.141.29.*
    链接

    zzfff 2010-06-11 22:59:39

    @老赵

    嗯,本质是ET,用LINQ只为迎合习俗。statement在ET v2中被看作是值为void的expression。lambda expression及anonymous delegate不支持yield确实(在理论上)有些奇怪,没去深究。

  6. 链接

    Tianium 2010-06-11 23:02:15

    其实 jQuery 中就已经实现了 “异步工作流(Asynchronous Workflows)”, 而其写法并不需要很难看的 N 级函数递归调用,只要利用一个队列,一点点封装就能实现了。

  7. 老赵
    admin
    链接

    老赵 2010-06-11 23:40:52

    @zzfff

    理论上都是可以实现的,但实际上总归有所考量,就好比C#的类型推断完整可以做的更好,不是么,呵呵。

  8. 老赵
    admin
    链接

    老赵 2010-06-11 23:41:31

    @Tianium

    能不能具体谈一下,或是给一些参考资料呢?

  9. 链接

    Ivony 2010-06-12 00:00:14

    同问,未在jQuery API中发现此功能。

  10. 老赵
    admin
    链接

    老赵 2010-06-12 00:02:41

    @Ivony

    即使有,其实我也很怀疑它的形式啊,毕竟JavaScript语言特性是个限制……

  11. 链接

    Tianium 2010-06-12 00:13:37

    这个不是 jQuery 的核心部分,但是 jQuery 在实现 UI 效果时,使用了这一特性,在 http://api.jquery.com/queue/ 中有其队列的演示。 里面的每个动画效果都是异步的,而队列将其串行起来了。

    BTW, @老赵,我在你前一篇的帖子里贴了一个 yield 实现,不知道是否能满足你的题意。

  12. 链接

    Ivony 2010-06-12 00:15:43

    JavaScript不能阻塞

    我能想出的最好的语法也仅限于:

    async
    ( function() { ... } )
    ( function() { ... } )
    ( function() { ... } )
    ();
    

    其实我之前说打算在C#中实现async的语法也是这种形式,可惜C#总是遇到类型之殇。。。。

  13. 链接

    Ivony 2010-06-12 00:37:25

    奥特曼了,,,,原来动画效果是异步执行的,一直以为是同步的。。。

  14. 老赵
    admin
    链接

    老赵 2010-06-12 09:37:20

    @Ivony

    差别还是很大的,jQuery只是把一堆异步任务统统堆进去,然后一个一个执行。异步工作流的一个特点便是“交互式”的,例如,等待一个异步操作结束,根据结果再进行下一步操作。当然,jQuery再添加点功能也可以实现这些,但是就又难以避免JavaScript的语言限制了,因为要表示“延迟”等,不可避免会出现function等关键字。

  15. 链接

    装配脑袋 2010-06-12 11:26:28

    我就是想弄一种语言,让这种可以自己改造编译过程的特性成为语言的内置特性……

  16. Dexter.Yy
    116.232.245.*
    链接

    Dexter.Yy 2010-06-12 13:04:45

    在javascript里链式调用来实现阻塞和异步操作是很容易很直观的,比如:

    request(url).callback(function(data) { })
    animate(action).wait(1000).stop()
    require(module).use(function(main) { })
    getCanvas().draw(rule).draw(rule)
    

    不同语言社区之间的借鉴很有必要,JS社区一直在借鉴其他语言的成功之处,比如CommonJS推崇的很多组件和API都来自Ruby,但是这些都不能超出语言本身的元编程能力,而且要因地制宜的做“本地化”取舍,一味的用其他语言的思考方式来写JS,是不会有好下场的,曾经有人用ruby的方式来写JS(prototype),也有人以java的方式来写JS,他们最后都转向去学习jquery的style了……

  17. 老赵
    admin
    链接

    老赵 2010-06-12 13:35:38

    @Dexter.Yy

    链式调用几乎各种语言都可以,它拯救不了异步编程,还是需要更好的异步编程模型,呵呵。

    我的看法是,如果直接使用JavaScript编程,那代码就要是JavaScript的样子,就像我设想的那样:

    // JavaScript
    function fibSeq() {
        function fibSeq$(a, b) {
            var next = a + b;
            return $yield(next);
            return $yieldSeq(fibSeq$(b, next));
        }
    
        return $yield(0);
        return $yield(1);
        return $yieldSeq(fibSeq$(0, 1));
    }
    

    你可以发现这是完全标准的JavaScript风格,只是在执行之前被一个解释器“修改”了。而我说的写C#,Java,F#最终变成JavaScript,那也是在写那些语言本身。它们都不是“用JavaScript模仿其他语言的编程风格”。

  18. 链接

    Tianium 2010-06-13 07:58:32

    在js执行前做预编译(预解释),已经涉及到语言特性修改的范畴了,等于你创造了一种新的语言(javascript+ :)。JS 本身其实是一种支持父对象特性扩展的语言,充分利用这点,参考其它语言的特性实现,来模拟这些特性,我觉得才是正徒。

    具体来说,如果我们猜测 C# 的实现 yield 的方式是异步工作流(虽然应该不是,我只是假设),那利用 JS 本身的特性实现异步工作流就是最好的,参考函数式语言的实现方式,大致思路这样:

    1. 请求入口异步函数,在函数返回时触发结束事件(连同结果,由异步工作流的实现框架响应);
    2. 工作流框架根据事件结果,做模式匹配,匹配到下一个符合条件的异步函数后,重复步骤 1。

    这里的关键是利用事件机制,而不是回调函数触发下一流程。提到这个, 准确的说, jQuery 实现的的确不是异步工作流,而是异步队列,但是这个讨论的核心不正是异步请求的顺序实现么?是工作流还是队列并不是问题的关键(就像 @老赵 你说的,“再添加点功能也可以实现这些”)。回到问题本质,jQuery 的实现是解决这一问题的一个很好借鉴。

  19. 老赵
    admin
    链接

    老赵 2010-06-13 09:31:34

    @Tianium

    我可没改造JavaScript语法,与F#的异步工作流一样,用的完全是F#语法,我这里用的也完全是JavaScript语法,呵呵。

    就像我说的那样,其实jQuery没有什么特别的,链式调用在哪个语言里都可以实现,但是它解决不了异步问题,这就是“生产力受语言特性限制”的典型示例。JavaScript是很灵活,但事实上也很死板,我说的死板是在于它的语法框架很多,如function,return,括号等都无法省去,这样很难写出漂亮的代码,代码不漂亮就没人用了。

    当然“漂亮”可能是个主观因素,我觉得你可以根据你的设想写一段JavaScript出来,这样也容易让我理解你的意思,我现在实在无法理解JavaScript如何可以写出漂亮的代码。我的观点就是:jQuery的API只是一套简单的,用其他语言来也同样可以实现出来的API,甚至可以实现的更优雅,比如这段JavaScript:

    request(url).callback(function(data) { })
    animate(action).wait(1000).stop()
    require(module).use(function(main) { })
    getCanvas().draw(rule).draw(rule)
    

    C#不也一样吗?省下了function关键字还更优雅呢:

    Request(url).Callback(data => { });
    Animate(action).Wait(1000).Stop();
    Require(module).Use(main => { });
    GetCanvas().Draw(rule).Draw(rule);
    

    说实话,这充其量只能算是fluent interface,jQuery的异步队列实现和F#的异步工作流相比,无论是功能还是灵活性都是不能相提并论的。事件机制就是回调机制,用到的就是回调函数。还有,这里不仅仅是异步任务的顺序实现,F#异步工作流里面实现的是整套控制流程,递归、if、while、for、try...catch,任意组合任意使用……

  20. 链接

    Tianium 2010-06-14 01:09:23

    呵呵,说的没错,事件机制的确就是回调机制,只是实现的更巧妙,能够被封装而已。 我拿 jQuery 举例子,也仅仅就“异步任务的顺序实现”而言就事论事,并没有想说他和 F# 的异步工作流有任何可比性,何况我对 F# 也并不了解。 如果有必要把这个讨论延伸到工作流的范畴,我相信 JS 作为程序语言的完整性,既然能写出 JS 编译器,实现异步工作流也应该是可以的,我很愿意在空下来的时候,提供一份实现来这里讨论。

  21. 老赵
    admin
    链接

    老赵 2010-06-14 02:52:14

    @Tianium

    实现异步工作流自然是可以的,用JavaScript写编译器重新修改一下某个函数就可以了嘛。不过这不是因为JavaScript“程序语言的完整性”,而是它有些变态的能力:“可以在运行时修改自身”。其实我文章里和刚才的评论都是这个意思,总之还是要突破JavaScript原有语言限制才行,否则很难得到真正优雅高效的异步编程模型……

  22. 链接

    Ivony 2010-06-14 13:39:04

    其实啊,jQuery那个queue功能,看起来就是个委托链。。。。

  23. 老赵
    admin
    链接

    老赵 2010-06-14 19:46:13

    @Ivony

    其实现在大部分框架类库看了api之后,我们大都可以猜测出里面的实现是什么样的,并没有太神秘的东西。而且一个框架类库太神秘的反而不一定是好事,说明设计便写的不够透明直观。

  24. Taobao
    221.238.73.*
    链接

    Taobao 2010-06-16 14:45:16

    这个功能很强大啊!只是用Jquery能不能做呢?

发表回复

登录 / 登录并记住我 ,登陆后便可删除或修改已发表的评论 (请注意保留评论内容)

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

评论内容(大于5个字符):

  1. Your Name yyyy-MM-dd HH:mm:ss

使用Live Messenger联系我