Expressions.Rmd

# Expressions

```{r setup, include = FALSE}
source("common.R")
library(rlang)
```

To compute on the language, we first need to understand its structure. That requires some new vocabulary, some new tools, and some new ways of thinking about R code. \index{expressions}

The first thing you'll need to understand is the distinction between an operation and its result. Take this code, which takes a variable `x` multiplies it by 10 and saves the result to a new variable called `y`. It doesn't work because we haven't defined a variable called `x`:

```{r, error = TRUE}
y <- x * 10
```

It would be nice if we could capture the intent of the code, without executing the code. In other words, how can we separate our description of the action from performing it? One way is to use `base::quote()`: it captures an expression without evaluating it: \indexc{quote()}

```{r}
z <- quote(y <- x * 10)
z
```

`quote()` returns a quoted __expression__: an object that contains R code. In this chapter, you'll learn about the structure of those expressions, which will also help you understand how R executes code. Later, we'll learn about `eval()` which allows you to take such an expression and perform, or __evaluate__, it:

```{r}
x <- 4
eval(z)
y
```

## Abstract syntax trees

Quoted expressions are also called abstract syntax trees (AST) because the structure of code is fundamentally hierarchical and can be naturally represented as a tree. To make that more obvious we're going to introduce some graphical conventions, illustrated with the very simple call `f(x, "y", 1)`. \index{abstract syntax tree}

```{r, echo = FALSE, out.width = NULL}
knitr::include_graphics("diagrams/expression-simple.png", dpi = 450)
```
  
*   Function __calls__ define the hierarchy of the tree. Calls are shown
    with an orange square. The first child is the function that gets called,
    here `f`. The second and subsequent children are the arguments. 
  
    NB:Unlike many tree diagrams the order of the children is important: 
    `f(x, 1)` is not the same as `f(1, x)`.
    
*   The leaves of the tree are either __symbols__, like `f` and `x`, or 
    __constants__ like `1` or `"y"`. Symbols have a purple border and rounded 
    corners. Constants, which are atomic vectors of length one, have black 
    borders and square corners. Strings are always surrounded in quotes so
    you can more easily distinguish from symbols --- more on that important
    difference later.

Every call in R can be written in this form, even if it doesn't look like it at first glance. Take `y <- x * 10` again: what function is being called? It not as easy to spot as `f(x, 1)` because this expression uses __infix__ form. Infix functions come **in**between their arguments (so an infix function can only have two arguments). Most functions in R are __prefix__ functions where the name of the function comes first. 

(Some programming languages use __postfix__ functions where the name of the function comes last. If you ever used an old HP calculator, you might have fallen in love with reverse Polish notation, postfix notation for algebra. There is also a family of "stack"-based programming languages descending from Forth which takes this idea as far as it might possibly go.)

### Infix vs. prefix

In R, any infix call can be converted to a prefix call if you you escape the function name with backticks. That means that these two lines of code are equivalent:

```{r}
y <- x * 10
`<-`(y, `*`(x, 10))
```

And their AST looks like this:

```{r, echo = FALSE, out.width = NULL}
knitr::include_graphics("diagrams/expression-prefix.png", dpi = 450)
```

Drawing these diagrams by hand takes me some time, and obviously you can't rely on me to draw diagrams for your own code. So to supplement the hand-drawn trees, we'll also use some computer-drawn trees made by `lobstr::ast()`. `ast()` tries to make trees as similar as possible to my hand-drawn trees, while respecting the limitations of the console. I don't think they're quite as easy to visually parse, but they're not too bad. If you're running in an interactive terminal, you'll see calls in orange and names in purple.

```{r}
lobstr::ast(y <- x * 10)
```

`ast()` also prints the argument names when they're used:

```{r}
lobstr::ast(mean(x = mtcars$cyl, na.rm = TRUE))
```

We can use `ast()` to peek into even more complex calls. In this call, note the special forms used by `function`, `if`, and `{}` are just regular nodes in the tree.

```{r}
lobstr::ast(function(x, y, z) {
  if (x > y) {
    z - x
  } else {
    z + y
  }
})
```

For more complex code, you can also use RStudio's tree viewer to explore the AST interactively. Activate with `View(quote(y <- x * 10))`.

### Constants

__constants__ include the length one atomic vectors, like `"a"` or `10`,
They have the interesting property that quoting is idempotent:

```{r}
identical(1, quote(1))
identical("test", quote("test"))
```

Note that you can't directly create longer vectors because there's no way to do that without calling a function:

```{r}
lobstr::ast(c(1, 2, 3))
lobstr::ast(1:3)
```

### Symbols {#names}

Symbols, represent the name of an object rather than its value. `ast()` prefixes names with a backtick. \index{names} \index{symbols|see{names}}

```{r}
lobstr::ast(x)
lobstr::ast(mean)
lobstr::ast(`an unusual name`)
```

Names that would otherwise be invalid are automatically surrounded by backticks
\index{non-syntactic names}.

There's one special name that needs a little extra discussion: the empty name. It is used to represent missing arguments. This object behaves strangely. You can't bind it to a variable. If you do, it triggers an error about missing arguments. It's only useful if you want to programmatically create a function with missing arguments. \index{names|empty}

```{r, error = TRUE}
f <- function(x) 10

formals(f)$x
is.name(formals(f)$x)
as.character(formals(f)$x)

missing_arg <- formals(f)$x
# Doesn't work!
is.name(missing_arg)
```

To explicitly create it when needed, call `quote()` with a named argument:

```{r}
quote(expr = )
```

### Unquoting

Note that `ast()` supports "unquoting" with `!!` (pronounced bang-bang). We'll talk about this in detail later; for now notice that this is useful if you've already used `quote` to captured the expression in a variable.

```{r}
lobstr::ast(z)
lobstr::ast(!!z)
```

### Base R naming conventions

Before we go much further, you need a word of caution about the naming conventions we've used here. Unfortunately, base R does not have a consistent set of conventions that are used throughout functions and documentation, and this book introduces another set of mild variations (which at least we do use consistently).

* Language object is used in two senses in base R. `is.language()` defines
  as the union of symbols, calls, and expressions; `str()` uses as synonoym
  for call.

* Symbol and name used interchangeably in base R. `as.name()` and `is.name()` 
  are identical to `as.symbol()` and `is.symbol()`. We prefer symbol because 
  name is too overloaded (i.e. the name of a variable).

* `expression()` and `parse()` create expression objects, which are basically a 
  list of calls. This is not very useful since you can just put calls in a list.
  There is no reason to ever use `expression()`.

### Exercises

1.  Use `ast()` and experimentation to figure out the three arguments in an
    `if()` call. Which components are required? What are the arguments to
    the `for()` and `while()` calls?

1.  What does the call tree of an `if` statement with multiple `else` 
    conditions look like?

1.  Why can't an expression contain an atomic vector of length greater than one?
    Which two of the six types of atomic vector can't appear in an expression?
    Why?

## Understanding R's grammar

The set of rules used to go from a sequence of tokens (like `x`, `y`, `+`) to a tree is known as a grammar. In this section, we'll explore some of the details of R's grammar, learning more about how a potentially ambiguous string is turned into a tree.

### Operator precedence and associativity

The AST has to resolve two sources of ambiguity when parsing infix operators. First, what does `1 + 2 * 3` yield? Do you get 7 (i.e. `(1 + 2) * 3`), or 9 (i.e. `1 + (2 * 3)`).  Which of the two possible parse trees below does R use?

```{r, echo = FALSE, out.width = NULL}
knitr::include_graphics("diagrams/expression-ambig-order.png", dpi = 450)
```

Infix functions introduce an ambiguity in the parser in a way that prefix functions do not. Programming langauges resolve this using a set of conventions known as __operator precedence__. We can reveal the answer using `ast()`: 

```{r}
lobstr::ast(1 + 2 * 3)
```

Second, is `1 + 2 + 3` parsed as `(1 + 2) + 3` or `1 + (2 + 3)`? 

```{r}
lobstr::ast(1 + 2 + 3)
```

This is called __left-associativity__ because the the operations on the left are evaluated first. The order of arithmetic doesn't usually matter because `x + y == y + x`. However, some S3 classes define `+` in a non-associative way. For example, in ggplot2 the order of arithmetic does matter.

(These two sources of ambiguity do not exist in postfix languages which is one reason that people like them. They also don't exist in prefix languages, but you have to type a bunch of extra parentheses. For example, in LISP you'd write `(+ (+ 1 2) 3))`. In a postfix language you write `1 2 + 3 +`)

You override the default precendence rules by using parentheses. These also appear in the AST:

```{r}
lobstr::ast((1 + 2) + 3)
```

### Whitespace

R, in general, is not very sensitive to white space. Most white space is not signficiant and is not recorded in the AST. `x+y` yields exactly the same AST as `x +        y`. There's is only one place where whitespace is quite important:

```{r}
lobstr::ast(y <- x)
lobstr::ast(y < -x)
```

### The function component

The first component of the call is usually a symbol that resolves to a function:

```{r}
lobstr::ast(f(a, 1))
```

But it might also be a function factory, a function that when called returns another function:

```{r}
lobstr::ast(f()(a, 1))
```

And of course that function might also take arguments:

```{r}
lobstr::ast(f(a, 1)())
```

And finally, there might be arguments at multiple levels:

```{r}
lobstr::ast(f(a, b)(1, 2))
```

These forms are relatively rare, but it's good to be able to recognise them when they crop up. 

### Exercises

1.  Which arithmetic operation is right associative?

1.  Why does `x1 <- x2 <- x3 <- 0` work? There are two reasons.

1.  Compare `x + y %+% z` to `x ^ y %+% z`. What does that tell you about 
    the precedence of custom infix functions?

## Extracting, modifying, and creating calls {#calls}

A call behaves similarly to a list. It has a `length()` and you can extract elements with  `[[`, `[`, and `$`. Like lists, calls are recursive, because a call can contain other calls. The main difference is that the first element of a call is special: it's the function that will get called. \index{calls}

Let's explore these ideas with a simple example:

```{r}
x <- quote(read.table("important.csv", row = FALSE))
lobstr::ast(!!x)
```

The length of a call minus one gives the number of arguments:

```{r}
length(x) - 1
```

The names of a call are always empty for the first element and for unnamed arguments. 

```{r}
names(x)
```

### Subsetting

You can extract the leaves of the call by position and by name using `[[` and `$` in the usual way:

```{r}
x[[1]]
x[[2]]

x$row
```

You can use `[` to extract multiple components, but if you drop the the first element, you're usually going to end up with a weird call:

```{r}
x[2:3]
```

If you do want to extract multiple elements in this way, it's good practice to coerce the results to a list:

```{r}
as.list(x[2:3])
```

Note that if you want to extract a specific argument from a function call, it's going to be challenge because it could potentially be in any location, with the full name, with an abreviated name, or with no name. To work around this problem, you can use `rlang::lang_standardise()` which standardises all arguments to use the full name: \indexc{standardise\_call()}

```{r}
rlang::lang_standardise(x)
```

(Note that if the function uses `...` it's not possible to standardise all arguments.)

It's also possible to modify calls:

```{r}
x$header <- TRUE
x
```

But there are some important caveats which we'll come back to after we discuss how to construct a call from scratch.

## Parsing and deparsing {#parsing-and-deparsing}

Sometimes code is represented as a string, rather than as an expression. You can convert a string to an expression with `parse()`. `parse()` is the opposite of `deparse()`: it takes a character vector and returns an expression object. The primary use of `parse()` is parsing files of code to disk, so the first argument is a file path. Note that if you have code in a character vector, you need to use the `text` argument: \indexc{parse()}

```{r}
z <- quote(y <- x * 10)
deparse(z)

parse(text = deparse(z))
```

Because there might be many top-level calls in a file, `parse()` doesn't return just a single expression. Instead, it returns an expression object, which is essentially a list of expressions: \index{expression object} 

```{r}
exp <- parse(text = c("
  x <- 4
  x
  5
"))
length(exp)
typeof(exp)

exp[[1]]
exp[[2]]
```

You can create expression objects by hand with `expression()`, but I wouldn't recommend it. There's no need to learn about this esoteric data structure if you already know how to use expressions. \indexc{expression()}

With `parse()` and `eval()`, it's possible to write a simple version of `source()`. We read in the file from disk, `parse()` it and then `eval()` each component in a specified environment. This version defaults to a new environment, so it doesn't affect existing objects. `source()` invisibly returns the result of the last expression in the file, so `simple_source()` does the same. \index{source()}

```{r}
simple_source <- function(file, envir = new.env()) {
  stopifnot(file.exists(file))
  stopifnot(is.environment(envir))

  lines <- readLines(file, warn = FALSE)
  exprs <- parse(text = lines)

  n <- length(exprs)
  if (n == 0L) return(invisible())

  for (i in seq_len(n - 1)) {
    eval(exprs[i], envir)
  }
  invisible(eval(exprs[n], envir))
}
```

The real `source()` is considerably more complicated because it can `echo` input and output, and also has many additional settings to control behaviour.

`_label()`, `_name()`, `_text()`.

### Exercises

1.  What are the differences between `quote()` and `expression()`?

1.  Read the help for `deparse()` and construct a call that `deparse()`
    and `parse()` do not operate symmetrically on.

1.  Compare and contrast `source()` and `sys.source()`.

1.  Modify `simple_source()` so it returns the result of _every_ expression,
    not just the last one.

1.  The code generated by `simple_source()` lacks source references. Read
    the source code for `sys.source()` and the help for `srcfilecopy()`,
    then modify `simple_source()` to preserve source references. You can
    test your code by sourcing a function that contains a comment. If
    successful, when you look at the function, you'll see the comment and
    not just the source code.

1.  One important feature of `deparse()` to be aware of when programming is that 
    it can return multiple strings if the input is too long. For example, the 
    following call produces a vector of length two:

    ```{r, eval = FALSE}
    g(a + b + c + d + e + f + g + h + i + j + k + l + m +
      n + o + p + q + r + s + t + u + v + w + x + y + z)
    ```

    Why does this happen? Carefully read the documentation for `?deparse`. Can you write a
    wrapper around `deparse()` so that it always returns a single string?

## Exercises that need a home

1.  You can use `formals()` to both get and set the arguments of a function.
    Use `formals()` to modify the following function so that the default value
    of `x` is missing and `y` is 10.

    ```{r}
    g <- function(x = 20, y) {
      x + y
    }
    ```

1.  Write an equivalent to `get()` using `as.name()` and `eval()`. Write an
    equivalent to `assign()` using `as.name()`, `substitute()`, and `eval()`.
    (Don't worry about the multiple ways of choosing an environment; assume
    that the user supplies it explicitly.)

1.  Implement a pure R version of `do.call()`.

1.  Concatenating a call and an expression with `c()` creates a list. Implement
    `concat()` so that the following code works to combine a call and
    an additional argument.

    ```{r, eval = FALSE}
    c(quote(f()), list(a = 1, b = quote(mean(a)))
    concat(quote(f), a = 1, b = quote(mean(a)))
    #> f(a = 1, b = mean(a))
    ```