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.