Occurrences notation in “Compiling Pattern Matching to Good Decision Trees”

Question

From Compiling Pattern Matching to Good Decision Trees (Luc Maranget, Proceedings of ML '08, pp. 35–46. ACM, 2008.)

We also consider the usual occurrences. Occurrences are sequences of integers that describe the positions of subterms. More precisely an occurrence is either empty, written $\Lambda$, or is an integer $k$ followed by an occurrence $o$, written $k\cdot o$. Occurrences are paths to subterms, in the following sense: $$\begin{align*} v/\Lambda &= v\\ c(c_1, \dots, v_a)/k\cdot o &= v_k/o \quad(1\leq k\leq a) \end{align*}$$

Could anyone explain the occurrences notation a bit?

Answer 1

I will try to illustrate the concept more intuitively and informally by representing terms as trees.

A term can be represented as a rooted tree, where the leafs are atomic operands (literals, or variables) and the other nodes are operators. Typically abstract syntax trees can be built on that model as this example (taken in another answer), for which I am giving both the textual syntax and the tree representation.

if (x > y) {
   if (y < a) { 
     x:= a
     y:= b
   } else {
    x:= b;
   }
 }
              if
     ________/|\________
    /         |         \
   >          if        :=
  / \    ____/|\____   /  \
 x   y  /     |     \ x    b
       <     :=     :=
      / \   /  \   /  \
     y   a x    a y    b

But the concept is used in a lot of different contexts, with different kinds of operators. The example term above could also be written as in the text of your question in function call style:

if(>(x,y),if(<(y,a),:=(x,a),:=(y,b)),:=(x,b))

where the operators are if, >, <, and :=.

Whatever the kind of term you are interested in, an occurrence is a position in the tree (to which we can associate corresponding positions in any of the strings representation).

A subterm corresponds to a subtree, and an occurrence is the location of the main operator of a subterm, i.e. its root.

A simple way to designate unambiguously an occurrence is to give the path to access that occurrence from the root of the tree. The path is simply a string of integers that tell you at each node which of the daughter you should consider.

So the empty word $\Lambda$ correspond to the root itself (the top if in my example), since there is no path to be followed.

The string $2\;1\;2$ tell you to go to the second daughter, then to the first, then the second again. So it is an occurrence corresponding to the position of the leftmost a.

That in particular is useful to distinguish the two occurrences of a, the other one being $2\;2\;2$.

An the occurrence of the term :=(y,b) is $2\;3$.

Of course, an occurrence is meaningful only with respect to a term, and that is why your document systematically associate the reference term with the path, i.e. string, denoting an occurrence in that term.

Actually, the notation used in your document is a bit abusive, though it is common, because an occurrence is really a position in the term, where some subterm occurs, but it is not that subterm (though it is sometimes taken as such if the context makes it unambiguous).

To get the subterm, you should normally explicitly apply a function that takes an occurrence as argument and returns whatever subterm is found there.

Answer 2

An occurrence is a sequence of indices (separated by $\cdot$; $\Lambda$ is the empty sequence), which is used to index a vertex in an expression tree. For an expression $e$ and an occurrence $\sigma$, $e/\sigma$ is the vertex at address $\sigma$ in $e$. For example: $$ a(b(x_1,x_2),c(y_1,y_2)) / 1 = b(x_1,x_2), \\ a(b(x_1,x_2),c(y_1,y_2)) / 1 \cdot 2 = b(x_1,x_2) / 2 = x_2. $$ The definition that you quote is an inductive definition of $e/\sigma$. If $\sigma$ is the empty sequence $\Lambda$, then $e/\sigma = e$. Otherwise, you separate $\sigma$ into the first index $i$ and the rest of the list $\tau$ (which could be empty). If $e_i$ is the $i$th item in $e$, then $e/i\cdot \tau = e_i/\tau$, that is, we first go to the $i$th item, and then follow the rest of the address $\tau$ (see the example above).