def rec_eval(expr, deepcopy_inputs=False, memo=None,
        max_program_len=None,
        memo_gc=True,
        print_trace=False,
        print_node_on_error=True,
        ):
    """
    expr - pyll Apply instance to be evaluated

    memo - optional dictionary of values to use for particular nodes

    deepcopy_inputs - deepcopy inputs to every node prior to calling that
        node's function on those inputs. If this leads to a different return
        value, then some function (XXX add more complete DebugMode
        functionality) in your graph is modifying its inputs and causing
        mis-calculation. XXX: This is not a fully-functional DebugMode because
        if the offender happens on account of the toposort order to be the last
        user of said input, then it will not be detected as a potential
        problem.

    """
    if max_program_len == None:
        max_program_len = DEFAULT_MAX_PROGRAM_LEN

    if deepcopy_inputs not in (0, 1, False, True):
        # -- I've been calling rec_eval(expr, memo) by accident a few times
        #    this error would have been appreciated.
        raise ValueError('deepcopy_inputs should be bool', deepcopy_inputs)

    node = as_apply(expr)
    topnode = node

    if memo is None:
        memo = {}
    else:
        memo = dict(memo)

    # -- hack for speed
    #    since the inputs are constant during rec_eval
    #    but not constant in general
    node_inputs = {}
    node_list = []
    dfs(node, node_list, seqset=node_inputs)

    # TODO: optimize dfs to not recurse past the items in memo
    #       this is especially important for evaluating Lambdas
    #       which cause rec_eval to recurse
    #
    # N.B. that Lambdas may expand the graph during the evaluation
    #      so that this iteration may be an incomplete
    if memo_gc:
        clients = {}
        for aa in node_list:
            clients.setdefault(aa, set())
            for ii in node_inputs[aa]:
                clients.setdefault(ii, set()).add(aa)
        def set_memo(k, v):
            assert v is not GarbageCollected
            memo[k] = v
            for ii in node_inputs[k]:
                # -- if all clients of ii are already in the memo
                #    then we can free memo[ii] by replacing it
                #    with a dummy symbol
                if all(iic in memo for iic in clients[ii]):
                    #print 'collecting', ii
                    memo[ii] = GarbageCollected
    else:
        def set_memo(k, v):
            memo[k] = v

    todo = deque([topnode])
    while todo:
        if len(todo) > max_program_len:
            raise RuntimeError('Probably infinite loop in document')
        node = todo.pop()
        if print_trace:
            print 'rec_eval:print_trace', len(todo), node.name

        if node in memo:
            # -- we've already computed this, move on.
            continue

        # -- different kinds of nodes are treated differently:
        if node.name == 'switch':
            # -- switch is the conditional evaluation node
            switch_i_var = node.pos_args[0]
            if switch_i_var in memo:
                switch_i = memo[switch_i_var]
                try:
                    int(switch_i)
                except:
                    raise TypeError('switch argument was', switch_i)
                if switch_i != int(switch_i) or switch_i < 0:
                    raise ValueError('switch pos must be positive int',
                            switch_i)
                rval_var = node.pos_args[switch_i + 1]
                if rval_var in memo:
                    set_memo(node, memo[rval_var])
                    continue
                else:
                    waiting_on = [rval_var]
            else:
                waiting_on = [switch_i_var]
        elif isinstance(node, Literal):
            # -- constants go straight into the memo
            set_memo(node, node.obj)
            continue
        else:
            # -- normal instruction-type nodes have inputs
            waiting_on = [v for v in node_inputs[node] if v not in memo]

        if waiting_on:
            # -- Necessary inputs have yet to be evaluated.
            #    push the node back in the queue, along with the
            #    inputs it still needs
            todo.append(node)
            todo.extend(waiting_on)
        else:
            # -- not waiting on anything;
            #    this instruction can be evaluated.
            args = _args = [memo[v] for v in node.pos_args]
            kwargs = _kwargs = dict([(k, memo[v])
                for (k, v) in node.named_args])

            if memo_gc:
                for aa in args + kwargs.values():
                    assert aa is not GarbageCollected

            if deepcopy_inputs:
                args = copy.deepcopy(_args)
                kwargs = copy.deepcopy(_kwargs)

            try:
                rval = scope._impls[node.name](*args, **kwargs)

            except Exception, e:
                if print_node_on_error:
                    print '=' * 80
                    print 'ERROR in rec_eval'
                    print 'EXCEPTION', type(e), str(e)
                    print 'NODE'
                    print node  # -- typically a multi-line string
                    print '=' * 80
                raise

            if isinstance(rval, Apply):
                # -- if an instruction returns a Pyll apply node
                # it means evaluate that too. Lambdas do this.
                #
                # XXX: consider if it is desirable, efficient, buggy
                #      etc. to keep using the same memo dictionary
                foo = rec_eval(rval, deepcopy_inputs, memo,
                        memo_gc=memo_gc)
                set_memo(node, foo)
            else:
                set_memo(node, rval)

    return memo[topnode]


############################################################################
############################################################################
dataset/ETHPy150Open hyperopt/hyperopt/hyperopt/pyll/base.py/rec_eval/original