About
RSS

Bit Focus


移花接木 - 编译同步代码为异步代码 [数据结构篇]

Posted at 2013-03-11 12:48:16 | Updated at 2024-03-29 01:44:03

目标

    我说 JS 代码的表达能力是一流的, 可能一票 Python 党 (作为高级黑, 我不得不说我自己也是个 Python 党) 要笑了. 我是说真的, Python 的 Lambda 基本上就是半残废, 所以, 要用 Python 写异步代码那就像是用挂面上吊一样不来劲了.
    然而任何写 JS 代码遇到三层以上的异步代码套在一起的时候手撕键盘的心都有了, 蔽博先前也介绍了一个工具 (确切地说是玩具) 用来使用类似同步的代码生成异步代码. 而现在则有更明确的目标, 如把这样一段代码
fs: require('fs')
content: fs.readFile('/etc/passwd', %%)
console.log(content)
变成这样一段 Javascript
var fs, content;
fs = require('fs');
fs.readFile('etc/passwd', function(err, result) {
    content = result;
    console.log(content);
});
    为什么是这样? 首先 JS 中很多异步调用的回调函数都遵循 function(error, result) 这个形式, 这俨然成为了 Javascript 中的一种约定, 因此在接下来的分析中把这样的回调函数参数称为正规异步回调 (regular asynchronous callback). 既然它们都是这么个形式, 那么写代码的时候完全可以不这么罗嗦写个回调声明, 而是用 %% 这个符号来替代它.
    而包含正规异步回调的函数调用称之为正规异步调用 (regular asynchronous call).

    更详细地说, fs.readFile('/etc/passwd', %%) 这个表达式的意思是
    那么下面要做的事请是, 如果在一次编译过程中, 语法分析已经完成, 对应的同步代码的语法树已经建起来, 怎么根据上述规则去生成异步代码.

    比如上面的例子, 源语法树形式是

 +-----------------+
 | definition (fs) |
 +-----------------+
            |
         +------+
         | call |---------. (arugments)
         +------+          \
(callee) /              +---------------------+
+---------------------+ | string literal (fs) |
| reference (require) | +---------------------+
+---------------------+


 +----------------------+
 | definition (content) |
 +----------------------+
            |
         +---------------------------+      (arugments)
         | regular asynchronous call |------------------.
         +---------------------------+   \               \
    (callee) /                 +----------------+ +--------------+
       +---------------+       | string literal | | regular      |
       | member access |       | (/etc/passwd)  | | asynchronous |
       +---------------+       +----------------+ | callback     |
  (object)  /         \                           +--------------+
+----------------+ +----------+
| reference (fs) | | readFile |
+----------------+ +----------+


 +-------------+
 | arithmetics |
 +-------------+
           `-----------.
                    +------+ (arugments)
                    | call |----------.
                    +------+           \
            (callee) /            +---------------------+
               +---------------+  | reference (content) |
               | member access |  +---------------------+
               +---------------+
       (object)  /         \
+---------------------+ +-----+
| reference (console) | | log |
+---------------------+ +-----+

    而目标语法树形式则是

 +-----------------+
 | definition (fs) |
 +-----------------+
            |
         +------+
         | call |---------. (arugments)
         +------+          \
(callee) /              +---------------------+
+---------------------+ | string literal (fs) |
| reference (require) | +---------------------+
+---------------------+


 +-------------+ (#0)
 | arithmetics |
 +-------------+
            |
         +------+      (arugments)
         | call |------------------------------------.
         +------+                     \               \
    (callee) /                 +----------------+ +--------+  (#1)
       +---------------+       | string literal | | lambda +---------+
       | member access |       | (/etc/passwd)  | |  ` param: error  |
       +---------------+       +----------------+ |  ` param: result |
  (object)  /         \                           +------------------+
+----------------+ +----------+                       |
| reference (fs) | | readFile |                       | statements
+----------------+ +----------+                       | in
                                                      | function
                ______________________________________| body
               |
               |
               |    +----------------------+ (#2)
               |----| definition (content) |
               |    +----------------------+
               |               |
               |     +--------------------+
               |     | reference (result) |
               |     +--------------------+
               |
               |    +-------------+
               '----| arithmetics |
                    +-------------+
                              `-----------.
                                       +------+ (arugments)
                                       | call |----------.
                                       +------+           \
                               (callee) /            +---------------------+
                                  +---------------+  | reference (content) |
                                  | member access |  +---------------------+
                                  +---------------+
                          (object)  /         \
                   +---------------------+ +-----+
                   | reference (console) | | log |
                   +---------------------+ +-----+

    根据上面语法树的差异, 落实下来有这么几个要做的 (在下面具体代码给出来之后, 会进一步分析)

同步向异步的变换

代码生成类

    为了彰显一个 Python 党的风范, 接下来的所有工作都以 Python2 代码完成. 如下先来认识认识用来生成源代码的各路节点类型
class Expression:
    pass

class NumericLiteral(Expression):
    def __init__(self, value):
        self.value = value

    def str(self):
        return str(self.value)

class StringLiteral(Expression):
    def __init__(self, value):
        self.value = value

    def str(self):
        return `self.value`

class Reference(Expression):
    def __init__(self, name):
        self.name = name

    def str(self):
        return self.name

class Binary(Expression):
    def __init__(self, op, left, right):
        self.op = op
        self.left = left
        self.right = right

    def str(self):
        return '({left} {op} {right})'.format(
                left=self.left.str(), op=self.op, right=self.right.str())

class Call(Expression):
    def __init__(self, callee, arguments):
        self.callee = callee
        self.arguments = arguments

    def str(self):
        return '({callee}({arguments}))'.format(
                callee=self.callee.str(),
                arguments=','.join([ arg.str() for arg in self.arguments ]))

class Lambda(Expression):
    def __init__(self, parameters, body):
        self.parameters = parameters
        self.body = body

    def str(self):
        return 'function ({parameters}) {body}'.format(
                    parameters=','.join(self.parameters), body=self.body.str())

class Statement:
    pass

class Block(Statement):
    def __init__(self, statements):
        self.statements = statements

    def str(self):
        return '{' + ''.join([ st.str() for st in self.statements ]) + '}'

class Arithmetics(Statement):
    def __init__(self, expression):
        self.expression = expression

    def str(self):
        return self.expression.str() + ';'

class Branch(Statement):
    def __init__(self, predicate, consequence, alternative):
        self.predicate = predicate
        self.consequence = consequence
        self.alternative = alternative

    def str(self):
        return 'if ({pred}) {consq} else {alter}'.format(
                    pred=self.predicate.str(),
                    consq=self.consequence.str(),
                    alter=self.alternative.str())
    称这些节点类型为输出 (output) 节点类型, 以上代码保存在源文件 output.py 中.
    输出节点类型的设计思路是, 首先类型分为两种: 表达式 (expression) 跟语句 (statement). 无论哪种, 都能把自己变成一坨 Javascript 代码 (即成员函数 str(self) 干的事情). 这类节点直接对应于 Javascript 中存在的概念, 因此生成源代码轻松愉快, str 函数都很简洁明了. 上面这些东西虽然没有完全覆盖 Javascript 语言中的每个元素, 但是用来演示开始时提到的那些问题足够了.
    下面这些代码有助于理解该如何构造这些节点, 并用它们来生成代码
def main():
    print '/* a binary operation in a single statement */'
    print Arithmetics(Binary(
            '+',
            NumericLiteral(10),
            Reference('x')
        )).str()
    # result: (10 + x);

    print '/* a call in a statement, as a member of a block */'
    print Block([
            Arithmetics(Call(Binary('.',
                                    Reference('console'),
                                    Reference('log')),
                             [ StringLiteral('something') ]))
        ]).str()
    # result: {((console . log)('something'));}

    print '/* a more complex case */'
    print Block([
            Arithmetics(NumericLiteral('10.24')),
            Arithmetics(Call(Reference('setTimeout'), [
                    Lambda([], Block([
                            Branch(Reference('condition'), Block([
                                Arithmetics(Call(Reference('doSomething'), []))
                            ]), Block([]))
                        ])),
                    NumericLiteral(1000)
                ])),
        ]).str()
    # result: {10.24;(setTimeout(function () {if (condition) {(doSomething());} else {}},1000));}

if __name__ == '__main__':
    main()

语义语法节点类型设计

    相对于输出节点, 还有一类语义 (semantic) 节点. 大部分情况, 语义节点类型跟输出节点类型是一一对应的, 如
import output

class Expression:
    pass

class NumericLiteral(Expression):
    def __init__(self, value):
        self.value = value

    def compile(self):
        return output.NumericLiteral(self.value)

class StringLiteral(Expression):
    def __init__(self, value):
        self.value = value

    def compile(self):
        return output.StringLiteral(self.value)

class Reference(Expression):
    def __init__(self, name):
        self.name = name

    def compile(self):
        return output.Reference(self.name)

class Binary(Expression):
    def __init__(self, op, left, right):
        self.op = op
        self.left = left
        self.right = right

    def compile(self):
        return output.Binary(self.op, self.left.compile(), self.right.compile())

class Call(Expression):
    def __init__(self, callee, arguments):
        self.callee = callee
        self.arguments = arguments

    def compile(self):
        return output.Call(self.callee.compile(),
                           [ arg.compile() for arg in self.arguments ])

class Lambda(Expression):
    def __init__(self, parameters, body):
        self.parameters = parameters
        self.body = body

    def compile(self):
        return output.Lambda(self.parameters, self.body.compile())

class Statement:
    pass

class Block(Statement):
    def __init__(self, statements):
        self.statements = statements

    def compile(self):
        return output.Block([ stmt.compile() for stmt in self.statements ])

class Arithmetics(Statement):
    def __init__(self, expression):
        self.expression = expression

    def compile(self):
        return output.Arithmetics(self.expression.compile())

class Branch(Statement):
    def __init__(self, predicate, consequence, alternative):
        self.predicate = predicate
        self.consequence = consequence
        self.alternative = alternative

    def compile(self):
        return output.Branch(self.predicate.compile(),
                             self.consequence.compile(),
                             self.alternative.compile())
    每个语义节点对象在编译时应当产生一个对应的输出节点对象. 不过, 如果仅仅是这样, 那么就完全没必要区分语义节点与输出节点了. 回到最开始的需求上来, 如果现在要实现正规异步调用, 如
class RegularAsyncCall(Expression):
    def __init__(self, callee, arguments):
        self.callee = callee
        self.arguments = arguments

    def compile(self):
        pass
    是几乎不可能的事情. 现在任何语义节点的 compile 函数都是无参数, 而返回一个对应的输出节点. 任何节点都不知道自己在什么环境下被编译, 也不知道返回的节点会交给谁, 而正规异步调用的编译过程至少要做这样几件事情 (参照上节说的那些 #0 #1 #2 要做的事情)
    从这里看出来, 至少需要一个上下文语句流的概念. 当然, 它作为参数传入是最理想的设计. 因此现在就简单地设计这货.

上下文语句流

class ContextFlow:
    def __init__(self):
        self.block = output.Block([])
    没看错, 这东西简单起来就这么简单, 里面就放个语句块对象. 不过这对象的魔力很大, 而且可以随时替换语句块. 现在修改语义节点类型的编译方法实现, 方法如下
class Reference(Expression):
    def compile(self, context):
        return output.Reference(self.name)

class Binary(Expression):
    def compile(self, context):
        return output.Binary(self.op,
                             self.left.compile(context),
                             self.right.compile(context))

class Lambda(Expression):
    def compile(self, context):
        body_context = ContextFlow()
        body_flow = body_context.block
        self.body.compile(body_context)
        return output.Lambda(self.parameters, body_flow)
# semantic.py

class Block(Statement):
    def __init__(self, statements):
        self.statements = statements

    def compile(self, context):
        for s in self.statements: s.compile(context)

class Arithmetics(Statement):
    def __init__(self, expression):
        self.expression = expression

    def compile(self, context):
        compl_arith = output.Arithmetics(self.expression.compile(context))
        context.block.add(compl_arith)

class Branch(Statement):
    def __init__(self, predicate, consequence, alternative):
        self.predicate = predicate
        self.consequence = consequence
        self.alternative = alternative

    def compile(self, context):
        consq_context = ContextFlow()
        consq_flow = consq_context.block
        self.consequence.compile(consq_context)

        alter_context = ContextFlow()
        alter_flow = alter_context.block
        self.alternative.compile(consq_context)

        compl_branch = output.Branch(self.predicate.compile(context),
                                     consq_flow, alter_flow)
        context.block.add(compl_branch)
# output.py

class Block(Statement):
    def add(self, statement):
        self.statements.append(statement)
    下面这段小例子有助于理解语义节点的编译机制
def main():
    root_context = ContextFlow()
    root_flow = root_context.block
    Block([
            Arithmetics(NumericLiteral('10.24')),
            Arithmetics(Call(Reference('setTimeout'), [
                    Lambda([], Block([
                            Branch(Reference('condition'), Block([
                                Arithmetics(Call(Reference('doSomething'), []))
                            ]), Block([]))
                        ])),
                    NumericLiteral(1000)
                ])),
        ]).compile(root_context)
    print root_flow.str()

if __name__ == '__main__':
    main()

正规异步调用的编译实现

    把这些东西数据结构准备好之后, 正规异步调用实现起来如绘成竹
class RegularAsyncCall(Expression):
    def __init__(self, callee, arguments):
        self.callee = callee
        self.arguments = arguments

    def compile(self, context):
        compl_callee = self.callee.compile(context)

        # 编译参数, 并在参数中追加一个匿名函数作为回调
        compl_args = [ arg.compile(context) for arg in self.arguments ]

        callback_body_context = ContextFlow()
        cb_body_flow = callback_body_context.block
        # 如之前所说的正规异步回调, 它接受两个参数, 第一个参数表示错误, 第二个表示结果
        compl_args.append(output.Lambda([ 'error', 'result' ], cb_body_flow))

        # 在上下文语句流中插入一个算术节点, 算术节点中是个普通的函数调用
        context.block.add(output.Arithmetics(
                                    output.Call(compl_callee, compl_args)))

        # 调换上下文语句流, 以便让之后出现的语句被生成到某个匿名函数的函数体中
        context.block = cb_body_flow

        # 正规异步调用需要返回的则是名为 'result' 的引用
        # 因为这个调用要表示异步函数 "返回的结果"
        return output.Reference('result')
    最后, 藉由下面这个小例子来验证一下成果
def main():
    root_context = ContextFlow()
    root_flow = root_context.block
    Block([
            Arithmetics(
                    Binary(
                        '=',
                        Reference('content'),
                        RegularAsyncCall(
                            Binary('.', Reference('fs'), Reference('readFile')),
                            [ StringLiteral('/etc/passwd') ]))),
            Arithmetics(Call(Binary('.',
                                    Reference('console'),
                                    Reference('log')),
                        [ Reference('context') ]))
        ]).compile(root_context)
    print root_flow.str()

if __name__ == '__main__':
    main()
结果会是
{((fs . readFile)('/etc/passwd',function (error,result) {(content = result);((console . log)(context));}));}
格式化之后得
{
    ((fs.readFile)('/etc/passwd', function (error, result) {
        (content = result);
        ((console.log)(context));
    }));
}

查看完成代码请猛击这里. 更多实现思路, 请移步补述篇.

Post tags:   Compiler Construction  Python  Javascript  Asynchronous Expression

Leave a comment:




Creative Commons License Your comment will be licensed under
CC-NC-ND 3.0


. Back to Bit Focus
NijiPress - Copyright (C) Neuron Teckid @ Bit Focus
About this site