将声明性DSL翻译为嵌套函数调用

Question

我有一个Python库，可以通过嵌套函数调用来构建特殊的迭代器（行为树）。虽然这个库的接口语法相对简单易懂（因为是用Python写的），但我觉得它真的需要一个声明式的领域特定语言（DSL）。

以下是我想象中的一个粗略草图：

这个DSL（使用YAML格式）：

tree:
  - sequence:
    - do_action1
    - do_action2
    - select:
      - do_action3
      - sequence:
        - do_action4
        - do_action5
      - do_action6

将会生成以下的嵌套函数调用：

visit(
    sequence(
        do_action1(),
        do_action2(),
        select(
            do_action3(),
            sequence(
                do_action4(),
                do_action5(),
                ),
            do_action6(),
            )
        )
    )

我在想象具体该怎么做时遇到了困难。因为这个DSL必须表示一个树结构，所以简单的深度优先遍历似乎是合适的。但是为了构建嵌套的函数调用，我必须以某种方式把这个过程反转过来。这可能涉及到一些聪明的中间栈之类的东西，但我还没完全理解。请问，正确的转换方法是什么呢？

Answer 1

我觉得你可以让Python自己跟踪函数调用和参数，而不是自己用栈来管理。

假设你有一个YAML解析树，每个节点代表一个函数调用，而这个节点的每个子节点就是一个参数（这个参数也可以是一个函数调用，所以它也可能有自己的参数）。

然后定义一个叫做evaluate的函数，用来评估这个树的一个节点，具体可以这样写（伪代码）：

def evaluate(node):
    # evaluate parameters of the call
    params = []
    for child in node:
        params.append(evaluate(child))

    # now make the call to whatever function this node represents,
    # passing the parameters
    return node.function.call(*params)

最后，调用evaluate，把YAML树的根节点作为参数传进去，这样你就能得到想要的效果。

---

这是一个稍微不同的评估-应用结构

def evaluate(node):
    # evaluate parameters of the call
    params = [ evaluate(child) for child in node ]

    # apply whatever function this node represents
    return node.function.call(*params)