Given a dictionary of format strings,
I want to do cascading/recursive string interpolation.

```
FOLDERS = dict(home="/home/user",
               workspace="{home}/workspace",
               app_project="{workspace}/{app_name}",
               app_name="my_app")

```

I started with this implementation:

```
def interpolate(attrs):
    remain = [k for k, v in attrs.items() if "{" in v]
    while remain:
        for k in remain:
            attrs[k] = attrs[k].format(**attrs)
        remain = [k for k in remain if "{" in attrs[k]]

```

The `interpolate()` function first select the format strings.
Then, it substitute the strings until no more format strings remain.

When I call this function with the following Python dictionary, I get:

```
>>> import pprint
>>> pprint.pprint(FOLDERS)
{'app_name': 'my_app',
 'app_project': '/home/user/workspace/my_app',
 'home': '/home/user',
 'workspace': '/home/user/workspace'}

```

The result is OK but this implementation doesn't detect reference cycles.

For instance, the following call results in Infinite loop!

```
>>> interpolate({'home': '{home}'})

```

Could anyone give me a better implementation?

**EDIT: solution**

I think Leon's solution is good and simple, the one of Serge Bellesta too.

I'll implement it that way:

```
def interpolate(attrs):
    remain = [k for k, v in attrs.items() if "{" in v]
    while remain:
        for k in remain:
            attrs[k] = attrs[k].format(**attrs)
            fmt = '{' + k + '}'
            if fmt in attrs[k]: # check for reference cycles
                raise ValueError("Reference cycle found for '{k}'!".format(k=k))
        remain = [k for k in remain if "{" in attrs[k]]

```