Translating a declarative DSL into nested function calls

I have a python library which builds special iterators (a behavior tree) out of nested function calls. While the API has a fairly nice and light-weight syntax (due to it being python), it could really use a declarative DSL.

Here's a rough sketch of what I'm envisioning:

The DSL (using YAML):

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

would result in the following nested function calls:

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

I'm having trouble visualizing exactly how to do this. Because the DSL must represent a tree, a simple depth-first traversal seems appropriate. But in order to build the nested function calls, I have to turn this inside out somehow. It probably involves something clever with an intermediary stack or some-such, but I can't quite grasp it. What's the correct way to perform this transformation?

Solution

I think you could let python keep track of the function calls and parameters instead of doing it yourself with a stack.

Suppose you have a YAML parse tree in which each node represents a function call and each child of this node is a parameter (which is also a function call, so it could potentially have its own parameters).

Then define the function evaluate, which evaluates a node of this tree, as follows (pseudocode):

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)

Finally, call evaluate passing the root of the YAML tree as the parameter and you should get the desired behaviour.

A slightly different eval-apply structure

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)