Meta-Programming Parsing

Using an explicit function such as m to bootstrap us into the matrix expression language is the simplest way to use R’s own parser for our benefits, but it is not the only way. In R, we can manipulate expressions as if they were data, a feature known as meta-programming and something we return to in Chapter 5. For now, it suffices to know that an expression can be explored recursively. We can use the predicate is.name to check whether the expression refers to a variable, and we can use the predicate is.call to check whether it is a function call—and all operators are function calls. So, given an expression that does not use the m function and thus does not enter our DSL, we can transform it into one that goes like this:

build_matrix_expr <- function(expr) {
  if (is.name(expr)) {
      return(substitute(m(name), list(name = expr)))
  }

  if (is.call(expr)) {
      if (expr[[1]] == as.name("("))
        return(build_matrix_expr(expr[[2]]))
      if (expr[[1]] == as.name("*") ||
          expr[[1]] == as.name("%*%")) {
          return(call('*',
                      build_matrix_expr(expr[[2]]),
                      build_matrix_expr(expr[[3]])))
      }
      if (expr[[1]] == as.name("+")) {
          return(call('+',
                      build_matrix_expr(expr[[2]]),
                      build_matrix_expr(expr[[3]])))
      }
  }
  stop(paste("Parse error for", expr))
}

In this implementation, we consider both * and %*% matrix multiplication so that we would consider an R expression that uses matrix multiplication as such. Notice also that we consider calls that are parentheses. Parentheses are also function calls in R, and if we want to allow our language to use parentheses, we have to deal with them—like here, where we just continue the recursion. We did not have to worry about that when we explicitly wrote expressions using m and operator overloading because there R already took care of giving parentheses the right semantics.

For this function to work, it needs a so-called quoted expression. If we write a raw expression in R, then R will try to evaluate it before we can manipulate it. We will get an error before we even get to rewrite the expression.

build_matrix_expr(A * B)

## Error in A * B: non-conformable arrays

To avoid this, we need to quote the expression.

build_matrix_expr(quote(A * B))

## m(A) * m(B)

We can avoid having to explicitly quote expressions every time we call the function by wrapping it in another function that does this for us. If we call the function substitute on a function parameter, we get the expression it contains so that we can write a function like this:

parse_matrix_expr <- function(expr) {
  expr <- substitute(expr)
  build_matrix_expr(expr)
}

Now, we do not need to quote expressions to do the rewriting.

parse_matrix_expr(A * B)

## m(A) * m(B)

This isn’t a perfect solution, and there are some pitfalls, among which is that you cannot use this function from other functions directly. The substitute function can be difficult to work with. The further problem is that we are creating a new expression, but it’s an R expression and not the data structure we want in our matrix expression language. You can think of the R expression as a literate piece of code; it is not yet evaluated to become the result we want. For that, we need the eval function, and we need to evaluate the expression in the right context. Working with expressions, especially evaluating expressions in different environments, is among the more advanced aspects of R programming, so if it looks complicated right now, do not despair. We cover it in detail in Chapter 7. For now, we will just use this function:

parse_matrix_expr <- function(expr) {
  expr <- substitute(expr)
  modified_expr <- build_matrix_expr(expr)
  eval(modified_expr, parent.frame())
}

It gets the (quoted) expression, builds the corresponding matrix expression, and then evaluates that expression in the “parent frame,” which is the environment where we call the function. With this function, we can get a data structure in our matrix language from an otherwise ordinary R expression.

parse_matrix_expr(A * B)

## ([A] * [B])

The approach we take here involves translating one R expression into another to use our m function to move us from R to matrix expressions. This involves parsing the expression twice, once when we transform it and again when we ask R to evaluate the result. The approach is also less expressive than using the m function directly. We can call m with any expression that generates a matrix, but in the expression transformation, we only allow identifiers.

As an alternative, we can build the matrix expression directly using our constructor functions. We will use matrix_mult and matrix_sum when we have a call that is *, %*%, or +, and otherwise, we will call m. This way, any expression we do not recognize as multiplication or addition will be interpreted as a value we should consider a matrix. This approach, however, adds one complication. When we call function m, we need to call it with a value, but what we have when traversing the expression is quoted expressions. We need to evaluate such expressions, and we need to do so in the right environment. We will need to pass an environment along with the traversal for this to work.

build_matrix_expr <- function(expr, env) {
  if (is.call(expr)) {
    if (expr[[1]] == as.name("("))
      return(build_matrix_expr(expr[[2]], env))
    if (expr[[1]] == as.name("*") || expr[[1]] == as.name("%*%"))
      return(matrix_mult(build_matrix_expr(expr[[2]], env),
                         build_matrix_expr(expr[[3]], env)))
    if (expr[[1]] == as.name("+"))
      return(matrix_sum(build_matrix_expr(expr[[2]], env),
                        build_matrix_expr(expr[[3]], env)))
  }
  data_matrix <- m(eval(expr, env))
  attr(data_matrix, "def_expr") <- deparse(expr)
  data_matrix
}

Most of this function should be self-explanatory, except for where we explicitly set the def_expr attribute of a data matrix. This is the attribute to be used for pretty printing, and when we call the m function, it is set to the literate expression we called m with. This would be eval(expr, env) for all matrices we create with this function. To avoid that, we explicitly set it to the expression we use in the evaluation.

Once again, we can wrap the function in another that gets us the quoted expression and provide the environment in which we should evaluate expressions.

parse_matrix_expr <- function(expr) {
  expr <- substitute(expr)
  build_matrix_expr(expr, parent.frame())
}

parse_matrix_expr(A * B + matrix(1, nrow = 10, ncol = 10))

## (([A] * [B]) + [matrix(1, nrow = 10, ncol = 10)])

There is more to know about manipulating expressions, especially about how they are evaluated, but we will return to that in later chapters.

Optimizing Multiplication

Before we start rewriting multiplication expressions, though, we should figure out how to find the optimal order of multiplication. Let’s assume that we have this matrix multiplication: A₁ × A₂ × … × A _n . We need to set parentheses somewhere, say (A₁ × A₂ × …A _i ) × (A_i+1…× A _n ), to select the last matrix multiplication. If we first multiply together, in some order, the first i and the last n – i matrices, the last multiplication we have to do is the product of those two. If the dimensions of (A₁ × …A _i ) are n × k and the dimensions of (A_i+1…× A _n ) are k × m, then this approach will involve n × k × m operations plus how long it takes to produce the two matrices. Assuming that the best possible way of multiplying the first i matrices involves N_1,i operations and assuming the best possible way of multiplying the last n – i matrices together involves N_i+1,n operations, then the best possible solution that involves setting the parentheses where we just did involves N_1,i + N_i+1,n +n × k × m operations. Obviously, to get the best performance, we must pick the best i for setting the parentheses at the top level, so we must minimize this expression for i. Recursively, we can then solve for the sequences 1 to i and i + 1 to n to get the best performance.

Put another way, the minimum number of operations we need to multiply matrices A _i ,A_i+1,…,A _j can be computed recursively as N_i,j = 0 when i = j and

otherwise. Actually computing this recursively would involve recomputing the same values many times, but using dynamic programming we can compute the N_i,j table efficiently, and from that table we can backtrack and find the optimal way of setting parentheses as well.

In the following implementation, we assume that we have such a list of matrices as input. We then collect their dimensions in a table, dims, for easy access. Then, we simply create a table to represent the N_i,j values and fill it using the previous equation. Once we have filled the table, we backtrack through it to work out the optimal way of multiplying together the matrices from 1 to n, given the dimensions, table, and matrices.

arrange_optimal_matrix_mult <- function(matrices) {
  n <- length(matrices)
  dims <- matrix(0, nrow = n, ncol = 2)
  for (i in seq_along(matrices)) {
    dims[i,] <- dim(matrices[[i]])
  }

  N <- matrix(0, nrow = n, ncol = n)
  for (len in 2:n) {
    for (i in 1:(n - len + 1)) {
      j <- i + len - 1
      k <- i:(j - 1)
      N[i,j] <- min(dims[i,1]*dims[k,2]*dims[j,2] + N[i,k] + N[k + 1,j])
    }
  }

  # Backtrack through the table. This function will
  # be defined shortly.
  backtrack_matrix_mult(1, n, dims, N, matrices)
}

We use a table of matrix dimensions because it allows us to compute the minimum of the expression using a vector expression over k, something we could not do using the A list quite as easily. We loop over the length of intervals rather than just i and j because we need to compute the N[i,j] values in order of increasing lengths for the dynamic programming algorithm to work. If we did not do it in this order, we would not be guaranteed that the N values we use in the expression are filled out yet. Otherwise, though, we just implement the computation sketched earlier.

The backtracking function is equally simple. We want to find the optimal way of multiplying matrices i to j, and we have the table that tells us what N_i,j is. So, we should find a split point where we can get that value from the recursion. That is where we should set the parentheses and then solve to the left and right, recursively, until we get to the base case of a single matrix, which of course is already the result we should return.

backtrack_matrix_mult <- function(i, j, dims, N, matrices) {
  if (i == j) {
    matrices[[i]]
  } else {
    k <- i:(j - 1)
    candidates <- dims[i,1]*dims[k,2]*dims[j,2] + N[i,k] + N[k + 1,j]
    split <- k[which(N[i,j] == candidates)][1]
    left <- backtrack_matrix_mult(i, split, dims, N, matrices)
    right <- backtrack_matrix_mult(split + 1, j, dims, N, matrices)
    matrix_mult(left, right)
  }
}

At each step in the backtracking function, we construct a multiplication object using matrix_mult, so we rearrange the original expression in this way.

Expression Rewriting

With the dynamic programming algorithm in place, we know how to arrange multiplications in optimal order. We need to have them in a list, however, to access them by index in constant time in the backtracking function, but what we have as input is an expression that gives us a tree of mixed multiplications, addition, and data objects. So, the first step we must perform in the rearrangement is to collect the components of the multiplication in a list.

It is simple enough to visit all the relevant values in an expression. We recurse on all matrix_mult objects but not data or matrix_sum objects since it is these that we want to collect. It is inefficient to traverse the tree and grow an actual list object one element at a time; whenever you extend the length of a list object by one element, you need to copy all the old elements. Instead, we can implement a linked list—that we can prepend elements to in constant time—and translate that into a list object later.

To see this in action, we can consider a simpler tree first.

leaf <- function(x) structure(x, class = c("leaf", "tree"))
inner <- function(left, right)
  structure(list(left = left, right = right),
            class = c("inner", "tree"))

Let’s say we have such a tree as shown here (and we do not a priori know that it has four leaves):

tree <- inner(leaf(1), inner(inner(leaf(2), leaf(3)), leaf(4)))

And say we want to construct a list containing the values in the leaves.

One way to implement linked lists is as a list object containing two values, which are the head of the list (an actual value) and the tail of the list (another list, or potentially NULL representing the empty list).

Since head and tail are useful built-in functions in R, we will call these two elements car and cdr instead. These are the names they have in the Lisp programming language and many other functional programming languages. We can construct a list from a car and cdr element like this:

cons <- function(car, cdr) list(car = car, cdr = cdr)

To traverse a tree, we use recursion, but we don’t want to test the class of subtrees explicitly. Here is what we would usually do: have a test for the base case of having a leaf and another case for when we have an inner node. This approach would be sensible on this simple tree. However, once we start working with expressions where we can have many different node types, it might not be obvious what should be considered a base case or a recursive case. For any particular traversal, it is better to use generic functions.

collect_leaves_rec <- function(tree, lst)
  UseMethod("collect_leaves_rec")

collect_leaves_rec.leaf <- function(tree, lst) {
  cons(tree, lst)
}
collect_leaves_rec.inner <- function(tree, lst) {
  collect_leaves_rec(tree$left, collect_leaves_rec(tree$right, lst))
}

Using a generic function like this is certainly overkill for this simple example, but it illustrates the idea, which will be useful for more complex trees. Each node type is responsible for handling itself and potentially recursing further if this is needed. Here, the leaf handler prepends the tree to the list that is passed down the recursion. The tree is just the leaf, so this is the value we want to collect. The result is an updated list that we return from the recursion. For inner nodes, we first call recursively toward the right, passing along the lst object. This will prepend the elements in the right subtree to create a new list that we then pass along to a recursion on the left subtree.

The result of this traversal is a linked list containing all the leaves. To create a list object out of this, we need to run through the list and compute its length, allocate a list of that length, and then run through the linked list again to insert the elements in the list. This is one of the few tasks in R that is easier done with a loop than a functional solution, so that is what we will use.

lst_length <- function(lst) {
  len <- 0
  while (!is.null(lst)) {
    lst <- lst$cdr
    len <- len + 1
  }
  Len
}
lst_to_list <- function(lst) {
  v <- vector(mode = "list", length = lst_length(lst))
  index <- 1
  while (!is.null(lst)) {
    v[[index]] <- lst$car
    lst <- lst$cdr
    index <- index + 1
  }
  v
}

To improve the readability of the example, we will just add a function that gives us a vector instead of a list.

lst_to_vec <- function(lst) unlist(lst_to_list(lst))

Now we can use the combination of the traversal and transformation from the linked list to implement the function we want.

collect_leaves <- function(tree) {
  lst_to_vec(collect_leaves_rec(tree, NULL))
}
collect_leaves(tree)

## [1] 1 2 3 4

We can use the same approach to implement a better version of the rearrange_matrix_expr.matrix_mult function from earlier—one that rearranges the multiplication instead of just returning the original expression. We need it to collect the components of the multiplication—those would be data and sum objects—and then rearrange them using the dynamic programming algorithm.

rearrange_matrix_expr.matrix_mult <- function(expr) {
  matrices <- collect_mult_components(expr)
  arrange_optimal_matrix_mult(matrices)
}

The collect_mult_components function can be implemented using a traversal with a generic function like this:

collect_mult_components_rec <- function(expr, lst)
  UseMethod("collect_mult_components_rec")
collect_mult_components_rec.default <- function(expr, lst)
  cons(rearrange_matrix_expr(expr), lst)

collect_mult_components_rec.matrix_mult <- function(expr, lst)
    collect_mult_components_rec(expr$left,
              collect_mult_components_rec(expr$right, lst))

collect_mult_components <- function(expr)
    lst_to_list(collect_mult_components_rec(expr, NULL))

We use the default implementation to prepend expressions that are not multiplications to the list we are building, while we call recursively on the multiplication objects. Once we have collected all the components we need in a linked list, we translate it into a list object that lets us look up elements by index, as we need in the dynamic programming algorithm.

To see the rearranging in action, we can create the expression we used in the previous chapter. We have four matrices that we multiply together without setting any parentheses.

A <- matrix(1, nrow = 400, ncol = 300)
B <- matrix(1, nrow = 300, ncol = 30)
C <- matrix(1, nrow = 30, ncol = 500)
D <- matrix(1, nrow = 500, ncol = 400)

expr <- m(A) * m(B) * m(C) * m(D)

This implicitly sets parentheses such that the expression will be evaluated by multiplying from left to right.

expr

## ((([A] * [B]) * [C]) * [D])

This, however, is not the optimal order. Instead, it is better to first multiply A with B and C with D and then multiply the results.

rearrange_matrix_expr(expr)

## (([A] * [B]) * ([C] * [D]))