recursively expanding $references in dictionaries

[Alia Khouri]

Oops, I left some redundant cruft in the function... here it is
slightly cleaner:

def expand(dikt):
    names = {}
    output = {}
    def _search(_, sourceDict):
        for key, value in sourceDict.items():
            if isinstance(value, dict):
                _search({}, value)
            if not '$' in value:
                names[key] = value
    _search({}, dikt)
    def _substitute(targetDict, sourceDict):
        for key, value in sourceDict.items():
            if isinstance(value, dict):
                new_target = targetDict.setdefault(key, {})
                _substitute(new_target, value)
            else:
                targetDict[key] =
Template(value).substitute(names)
    _substitute(output, dikt)
    return output

print expand(d2)