Valerie's mark-up method

The girl (whose name was Valerie) possessed a power of mental abstraction that went beyond anything her older brother, let alone her father, could do. Her first achievement was to come up with a description of the 'structure' of any possible tree-pattern. Her father, the woodcutter, never did understand what she meant by 'structure'. Heaven knows where she got her ideas from!

Oddly, she started referring to tree-patterns as 'expressions', and one of her first moves was to define a 'prime expression'. She said that a prime expression was one that consisted of a single circle, together with an expression inside that circle. So in the figure

the expression on the left is prime, while the one on the right is not.

The dotted lines indicate how the expression on the right could be 'split up' into prime expressions, or conceived as a 'product' of 'prime factors'. The process by which one passes from an expression to its prime factors she called 'factorization'.

Now, a prime expression consists (let me remind you) of a single circle, together with an expression inside that circle. The girl taught us to call that interior expression the 'content' of the prime expression. Expressions in general do not have 'content', but a prime expression does.

Starting from a given expression, one can factorize it, then inspect the contents of each of the prime factors in turn. Indeed, one can take any of these content-expressions and factorize it in turn. And factorize the contents of each of its prime factors. And so on!

Are you lost? Perhaps you are beginning to see what I meant about that girl's astonishing mental powers. Her way of talking seemed complicated and moreover had the character of a 'net of words'. Any concrete-minded person found it terribly difficult to understand what she was saying. She certainly wasn't talking about anything one could see or touch, but instead was talking about 'definitions' (whatever that might mean) and the strange powers of coercion which these 'definitions' seemed to exert on one another - and even on us! They talk of limits on what we can write down, in the way of tree-patterns. How strange that a mere 'net of words' can have power over our actions!

Back to what the girl worked out. The expression that consists of a simple mark (an empty circle, O) is clearly prime. Its content is the empty expression,    . (To make it clear that we haven't made a typing error, we will usually write the blank space as _ .) The empty expression, on the other hand, has no content and is not prime, has no prime factors, and cannot be factorized. When one analyzes an expression by means of factorization-and-content (repeatedly), one reaches the end of the road when the content of a prime is the empty expression. So the analysis of a finite expression (consisting of finitely many circles) is a finite process, as one would expect. It's time for an example.

Suppose we are given the expression e

which factorizes into two prime factors, p1 and p2. The first of these is an empty mark (whose content e1 is the empty expression), the content of the second is the following expression, which we will call e2:

Clearly, e2 splits into two prime factors (p21 and p22). The second of these has for content the empty expression (e22), the content of the first (e21) splits into three (called p211,p212,p213). Of these prime factors, two have for content _ , the third (p213) has for content a single mark (e213). This O is already prime, and has for content e2131 = _ .

It sounds complicated in words, but the analysis can be represented succinctly by a family tree

In the tree, general expressions (from e downwards) are represented by filled dots, prime expressions by unfilled ones. Notice that from each unfilled dot descends just one filled dot (the content of the prime expression); while from each filled dot, a number (which may be zero) of unfilled dots descend (the prime factors of the expression).

Note also that the original expression can be reconstituted out of its dot-diagram (without the labels). Starting at the top, draw a circle for each unfilled dot (if any) descending from the top (filled) dot. At the next level down, again draw a circle for each unfilled dot, placing it inside the circle corresponding to its 'parent dot'. And so on, down to the lowest level.

To analyse a given pattern, the procedure could be summarized as: factorize, inspect content of each factor, factorize, inspect content of each factor, factorize,... and so on. The procedure for synthesizing a new pattern is similar: create factors (i.e. circles, side by side), give content to each factor by creating factors, give content to each factor... and so on, for as long as required.

After returning from university, the girl announced that the essence of the structure was 'recursion'. Sometimes she said, alternatively, that the essence of 'recursion' was to be found in the theory of the tree-patterns. Recursion, she would explain if asked, is a concept beloved of computer-programmers and linguists (especially of the Chomskyan persuasion). In the computer sphere, computer languages are usually defined in such a way that 'procedures can call themselves' - a feature that is sometimes useful to programmers, and enables them to write programs that have a very 'natural' feel. That is to say, that many of the tasks which computers are called upon to perform have an essentially recursive character. Which is no doubt connected, in turn, with the recursive structure of many (or all?) human languages.

Taking the English sentence 'Fred decided that he would buy a lottery ticket if the man with a goatee beard lifted his right eyebrow' as an example, we notice that the part of the sentence consisting of the words 'the man with a goatee beard lifted his right eyebrow' is itself a complete, grammatical English sentence. One sentence can be 'embedded' in another - and this is what is meant by 'recursion' in grammar. Here the word 'if' can be taken as a signal that recursion is about to happen. The word 'that' often plays a similar role, as in the sentence: 'I thought that the man with a goatee beard lifted his right eyebrow'.

The fact that such constructions are allowed in English, and many other languages, makes those languages far more versatile than they would otherwise be. One could draw an analogy, perhaps, with the 'if statements' and other conditional statements in computer programming, which effectively open the door to unlimited complexity.

In an interview, Chomsky has suggested:

... there had to be a point in time when a rewiring of the human brain that allowed people to use recursion took place. Perhaps sixty to seventy thousand years ago in a small hominid group in East Africa, a single individual was born with a genetic mutation. This mutation would have caused a restructuring of the brain and instantly bequeathed the affected person with the capacity for unbounded thought. Linguistic communication would not have begun at this moment, because the individual with the mutation was the only one with the capacity for it. But even a slight advantage spreads quickly throughout a population, and after this new rewiring was passed on to his or her offspring, the entire group would eventually become language-ready. [Christine Kenneally, The First Word (London: Viking, 2007)]

Golly! Was it really a question of brain rewiring? If it was, it seems likely that the very same mutation would have allowed our ancestors to appreciate the subtleties of the tree-marks, had they encountered them. The girl took it further, of course: she could not only understand the tree-marks, but talk about tree-mark-structure. She was commonly regarded as 'brainy'. Was that a question of a newly re-wired brain, or did she just have plenty of it?

One's brain is supposed to be 'rewired' as one develops through adolescence. One's capacity for abstract thought increases at the same time. I have noticed (for example) that it is very difficult to get even bright, mathematically-minded children to understand and use algebra (as opposed to arithmetic) under the age of 11 or 12. A few years later, and it seems to come naturally. (Not to everyone, of course - some of us never get what all those x's and y's were about until our dying day.)

Having mastered the logical specification of tree-mark-structure, we are in a position to move onto tree-mark-value. Before we begin, it will be useful to adopt the following convention. The two values are m and n: here m stands for mark, n for no-mark. In other words, m stands for 'Cut this tree down!', n stands for 'Spare it!'. Now, any expression can be evaluated by applying two rules:

1. (Factors) The value of an expression is m if the value of any of its prime factors is m; otherwise (i.e. if none of the prime factors has value m - or if it has no factors) it is n.

2. (Content) The value of a prime expression is the opposite of the value of its content (i.e. if the content has value m then the prime expression has value n; and vice-versa).

Unless the expression is very shallow, the rules will have to be applied 'recursively'. That is to say, on the way to evaluating the given expression, you will have to evaluate its parts, and the parts of the parts, and so on. But in any given expression the parts do not have parts, and so on, ad infinitum. Therefore, the process of evaluation, although it may be complicated, does not go on for ever.

To make the process quite clear, we can replace the expression by its dot-diagram, and evaluate it from the bottom up. Before we do that, we need to recognize two easy consequences of the rules.

1. The value of the empty expression is n. Because the expression has no prime factors, it is impossible for any of them to have the value m.

2. The value of a single mark O is m. Because its content _ has value n, the value of the mark must be the opposite, namely m.

So the rules are not complete nonsense! Now, each branch of the dot-diagram terminates in a filled dot with no descendants, representing an expression with no factors, in other words, the empty expression: with value n. So we write n beside each of the terminator-dots.

Each terminator-dot descends from an unfilled dot: the prime expression of which it is the content. Given that the filled dot is marked n, we mark the unfilled dot m. We then work our way up the diagram, always marking an unfilled dot with the opposite value to the value of the filled dot descended from it (its content); and marking a filled dot with m if and only if any of its factors (unfilled dots descending from it) already has an m.

If we like, we can dispense with the dot-diagram and do our value-marking on the original expression. The dot-diagram just teaches us how to think about its structure: once we have learnt that, we can dispense with the prop. We do the marking as follows:

The space inside each empty circle O we mark with n (the value of the content). Then, just outside the circle we write m. This is the value of the prime expression. At higher levels, we look at all the prime factors of an expression, and if any of them has an m written just outside them, we mark the expression itself by writing m just inside its bounding circle. If none of its factors has value m then we write n just inside its boundary.

What if the expression is the whole expression, and has no bounding circle? Then it is convenient to draw in a fictitious 'parent circle', drawn with a dotted line, and to write the value of the whole expression just inside the dotted circle. If you liked, you could write down the opposite value just outside the dotted circle — but that would be rather pointless.

The figure shows the result of this marking operation on our usual expression.

If you like, you can dispense with the content-values (the ones written just inside the circles) and do it all with the factor-values. Here the rule is: write m outside a circle if every factor of the content of the circle is already marked n. If any factor is marked m, then write n.

Alternatively, one could dispense with the factor-values, and do it with the content-values. A content-expression is to be marked n if and only if the content of each factor is already marked m. If any is marked n, then the expression is to be marked m.

I think you should be convinced by now that every regular expression (no circles allowed to cross, or touch, or anything like that) has an absolutely unambiguous value.


It is time to reconsider Valerie's older brother's method for evaluating any given expression. Recall what he did. Most expressions he would 'reduce' by selecting an empty circle and rubbing out its parent circle; but if the chosen empty circle was at the top level, and had no parent, then he would know that the value of the whole expression was m; if, on the other hand, the expression was reduced to nothing, he would know that its value was n.

We can now explain why his method always worked. We are done if we can prove that the reduction step has no effect on value: in other words, that the value of the reduced expression is always equal to the value of the unreduced expression.

On the left we have the situation before the reduction step:

Here x, y, z and a (and so on) each stand for 'any expression'; the figure shows how the expression of interest (the one that is about to be cancelled) is 'embedded' within a larger expression. The whole expression has been 'marked up', so far as is possible without knowing the values of x, y, z... But observe that an m can be written just inside the 'parent circle', even without evaluating x: because one factor with value m is enough to endow a whole expression with that same value. Just outside the parent circle, we are entitled to write the value n: this means that the value of the parent circle (together with its contents), considered as a prime expression, is n. As such, it makes no contribution to the value of the expression of which the parent circle is a factor (maybe, the only factor, if y happens to be the empty expression). Only an m would make any difference. Therefore, replacing the parent circle (and contents) by the empty expression - in other words, cancelling it - will make no difference, so far as value is concerned.

In case our selected empty circle has no 'parent circle', we employ the 'mundane shell' (the fictitious bounding circle of the whole expression). We write m just inside the dotted circle, which informs us that the value of the whole expression is m.


The new play area has three check-boxes in the top right hand corner. The program does the work of evaluating any expression that you care to create. When you tick the box labelled 'show interior values' all the factor-values are shown. 'Show levels' colours all the spaces in such a way that spaces that lie at the same level in the family tree are all the same colour. 'Show value of sign' just shows the final value of the whole expression that you have created.