7.3 Recursing over environments

If you want to operate on every ancestor of an environment, it’s often convenient to write a recursive function. This section shows you how, applying your new knowledge of environments to write a function that given a name, finds the environment where() that name is defined, using R’s regular scoping rules.

The definition of where() is straightforward. It has two arguments: the name to look for (as a string), and the environment in which to start the search. (We’ll learn why caller_env() is a good default in Section 7.5.)

where <- function(name, env = caller_env()) {
  if (identical(env, empty_env())) {
    # Base case
    stop("Can't find ", name, call. = FALSE)
  } else if (env_has(env, name)) {
    # Success case
    env
  } else {
    # Recursive case
    where(name, env_parent(env))
  }
}

There are three cases:

The base case: we’ve reached the empty environment and haven’t found the binding. We can’t go any further, so we throw an error.
The successful case: the name exists in this environment, so we return the environment.
The recursive case: the name was not found in this environment, so try the parent.

These three cases are illustrated with these three examples:

where("yyy")
#> Error: Can't find yyy

x <- 5
where("x")
#> <environment: R_GlobalEnv>

where("mean")
#> <environment: base>

It might help to see a picture. Imagine you have two environments, as in the following code and diagram:

e4a <- env(empty_env(), a = 1, b = 2)
e4b <- env(e4a, x = 10, a = 11)

where("a", e4b) will find a in e4b.
where("b", e4b) doesn’t find b in e4b, so it looks in its parent, e4a, and finds it there.
where("c", e4b) looks in e4b, then e4a, then hits the empty environment and throws an error.

It’s natural to work with environments recursively, so where() provides a useful template. Removing the specifics of where() shows the structure more clearly:

f <- function(..., env = caller_env()) {
  if (identical(env, empty_env())) {
    # base case
  } else if (success) {
    # success case
  } else {
    # recursive case
    f(..., env = env_parent(env))
  }
}

Iteration versus recursion

It’s possible to use a loop instead of recursion. I think it’s harder to understand than the recursive version, but I include it because you might find it easier to see what’s happening if you haven’t written many recursive functions.

f2 <- function(..., env = caller_env()) {
  while (!identical(env, empty_env())) {
    if (success) {
      # success case
      return()
    }
    # inspect parent
    env <- env_parent(env)
  }

  # base case
}

7.3.1 Exercises

Modify where() to return all environments that contain a binding for name. Carefully think through what type of object the function will need to return.
Write a function called fget() that finds only function objects. It should have two arguments, name and env, and should obey the regular scoping rules for functions: if there’s an object with a matching name that’s not a function, look in the parent. For an added challenge, also add an inherits argument which controls whether the function recurses up the parents or only looks in one environment.