Quickly add a free MyWikiBiz directory listing!

# Theme One Program : Exposition

Jump to: navigation, search

Author: Jon Awbrey

## Expository Note 1

Theme One Program Exposition

Jon Awbrey, Spring 2003, Winter 2005

1.  Invitation

Theme One is a program for building and transforming a particular species
of graph-theoretical data structures in memory, structures that have been
designed to support a variety of fundamental learning and reasoning tasks.

The program was developed as a part of an exploration into the
implementation and integration of different types of learning
and reasoning procedures, concerned especially with the types
of algorithms and data structures that might work in support
of inquiry.  In its current state, Theme One integrates over
a common data structure fundamental algorithms for one type
of inductive learning and one type of deductive reasoning.

The first order of business is to describe the general class of
graph-theoretical data structures that are used by the program,
as they are determined in their local and their global aspects.

It will be the usual practice to shift around and to view these
graphs at many different levels of detail, from their abstract
definition to their concrete implementation, and many points
in between.

The main work of the Theme One program is achieved by building and
transforming a single species of graph-theoretical data structures.
In their abstract form these structures are most closely related to
the graphs that are called "cacti" and "conifers" in graph theory,
and so I will generally refer to them under those names.

The graph-theoretical data structures used by the program are
built up from a basic data structure called an "idea-form flag".
This structure is defined as a pair of Pascal data types by means
of the following specifications:

type    idea = ^form;
form = record
sign: char;
as, up, on, by: idea;
code: numb
end;

An 'idea' is a pointer to a 'form'.

A 'form' is a record consisting of:

1.  A 'sign' of type char;

2.  Four pointers, 'as', 'up', 'on', 'by', of type idea;

3.  A 'code' of type numb, that is, an integer in [0, max integer].

Represented in terms of 'digraphs', or directed graphs,
the combination of an 'idea' pointer and a 'form' record
is most easily pictured as an 'arc', or a directed edge,
leading to a 'node' that is labeled with the other data,
in this case, a letter and a number.

At the roughest but quickest level of detail,
an 'idea' of a 'form' can be drawn like this:

o a 1
^
|
@

When it is necessary to fill in more detail,
the following schematic pattern can be used:

^ ^     ^
as\|up on|
o-----o by
| a 1 |--->
o-----o
^
|
@

The idea-form type definition determines the local structure of
the whole host of graphs that are used by the Theme One program,
including a motley array of ephemeral buffers, temporary scratch
lists, and other graph-theoretical data structures that are used
for their transient utilities at specific points in the program.

I will put off discussing these more incidental graph structures
until the points where they actually arise, focusing here on the
particular varieties and the specific variants of cactoid graphs
that constitute the main formal media of the program's operation.

## Expository Note 2

2.  Painted And Rooted Cacti And Conifers

Figure 1 depicts a typical example of a "painted and rooted cactus" (PARCA).

o
a   |       d
o---o       o
\ /  b c   |
o----o----o b e
\       /
\     /
\   /
\ /
@ a c e

Figure 1.  Painted And Rooted Cactus

The graph itself is a mathematical object and does not inhabit
the page before our eyes, nor must it be confused with any one
picture of it, any more than you would wish someone to confuse
you with a picture of yourself, but it's a fair enough picture,
once you understand the conventions of representation involved.

Let V(G) be the set of nodes in a graph G and let L be a set of identifiers.
We very often find ourselves in situations where we have to consider many
different ways of associating the nodes of G with the identifiers in L.
Various manners of associating nodes with identifiers have been given
conventional names by different schools of graph theorists.  I will
give here one way of describing a few of the most common patterns
of association.

A graph is "painted" if there is a relation between the
set of its nodes and a set of identifiers, in which case
the relation is called a "painting" and the identifiers
are called "paints".

A graph is "colored" if there is a function from the set
of its nodes to a set of identifiers, in which case the
function is called a "coloring" and the identifiers are
called "colors".

A graph is "labeled" if there is a one-to-one mapping
between the set of its nodes and a set of identifiers,
in which case the mapping is called a "labeling" and
the identifiers are called "labels".

A graph is "rooted" if it has a uniquely distinguished node,
in which case the distinguished node is referred to as the
"root" of the graph.  The root node of the above graph is
represented by the "at" sign or the "amphora" symbol "@".

The graph in Figure 1 has eight nodes plus the five paints in
the set {a, b, c, d, e}.  The painting of nodes is depicted by
drawing the paints of each node next to the node that they paint.
Observe that some nodes may be painted with an empty set of paints.

The structure of a "painted and rooted cactus" (PARC)
can be encoded in the form of character string that is
called a "painted and rooted cactus expression" (PARCE).
To facilitate the rest of this discussion let's agree that
the terms "cactus" and "cactus expression" will be used to
mean the painted and rooted varieties.  A cactus expression
is formed on the alphabet that consists of the relevant set
of identifiers, the "paints", plus three punctuation marks,
the left parenthesis, the comma, and the right parenthesis.

## Expository Note 3

2.  Painted And Rooted Cacti And Conifers (cont.)

Figure 2 illustrates one way to visualize the correspondence between
cactus graphs and cactus strings, exemplified in the instance of the
cactus from Figure 1.  The polygons of the cactus graph are referred
to as its "lobes".  An edge not a part of a larger polygon counts as
a "bi-gon", and when it is terminal it forms a specialized lobe that
is known as a "spike".

o
a  (|)        d
o---o         o
(\ /)  b c   (|)
o--,--o--,--o b e
\         /
\       /
(  \     /  )
\   /
\ /
@ a c e

( ( a , ( ) ) , b c , ( d ) b e ) a c e

Figure 2.  Cactus Graph and Cactus Expression

One traverses a cactus by beginning at the left hand side of the root node,
reading off the list of paints that one encounters at that point, climbing
up the left hand side of the leftmost lobe, marking that ascent by means
of a left parenthesis, traversing whatever cactus one happens to reach
at the first node above the root, that done, proceeding from left to
right along the top side of the lobe, marking each interlobal span
by means of a comma, traversing each cactus in turn that one meets
along the way, on completing the last of them climbing down the
right hand side of the lobe, marking that descent by means of
a right parenthesis, and then traversing each cactus in turn,
in left to right order, that is incident with the root node.

For the time being I will continue with the informal presentation
of the subject, and merely mention that additional discussion and
formal definitions of cactus graphs, cactus expressions, and the
relationships between them can be found at the following sites:

LOC.  http://stderr.org/pipermail/inquiry/2004-December/thread.html#2135
LOC.  http://forum.wolframscience.com/showthread.php?threadid=649

PERS.  http://stderr.org/pipermail/inquiry/2004-April/thread.html#1341
PERS.  http://stderr.org/pipermail/inquiry/2004-May/thread.html#1391
PERS.  http://forum.wolframscience.com/showthread.php?threadid=297

## Expository Note 4

2.  Painted And Rooted Cacti And Conifers (concl.)

It is possible to write a program that parses cactus expressions into
fairly close facsimiles of cactus graphs as pointer graph structures
in computer memory, in such a way that edges correspond to addresses
and nodes correspond to records.  That is exactly what I did in some
of the early forerunners of the present program, but it turns out to
be a somewhat more robust strategy in the long run, in spite of what
may appear to be an exorbitant amount of extra overhead with respect
to the nodes that have to be invested at the beginning, to implement
a more articulate but more indirect type of parsing algorithm, one
in which the punctuation marks are not just tacitly converted to
addresses in passing, but instead recorded as nodes in roughly
the same way as the ordinary identifiers, or paints.

Figure 3 illustrates this type of parsing paradigm, showing the
shape of the pointer graph structure that results from parsing
the cactus expression in Figure 2.  A traversal of this graph
naturally reconstructs the cactus string that parses into it.

o-----o
o------|--o  |
|  o---o  |  |
o->| ) |--o  |
o---o     |
^   o-----o
|  /   o-----o                o-----o
o--------------------|-/----|--o  |  o-------------|--o  |
|  o---o  o---o  o---o< o---o  |  |  |  o---o  o---o  |  |
o->| a |->| , |->| ( |->| ) |--o  |  o->| d |->| ) |--o  |
o---o  o---o  o---o  o---o     |     o---o  o---o     |
^   o--------------------------o     ^   o------------o
|  /                                 |  /                 o-----o
o------|-/----------------------------------|-/------------------|--o  |
|  o---o< o---o  o---o  o---o   o---o   o---o< o---o  o---o  o---o  |  |
o->| ( |->| , |->| b |->| c |-->| , |-->| ( |->| b |->| e |->| ) |--o  |
o---o  o---o  o---o  o---o   o---o   o---o  o---o  o---o  o---o     |
^   o---------------------------------------------------------------o
|  /
o------|-/---------------------o
|  o---o< o---o  o---o  o---o  |
o->| ( |->| a |->| c |->| e |--o
o---o  o---o  o---o  o---o
^
|
@

( ( a , ( ) ) , b c , ( d ) b e ) a c e

Figure 3.  Parse Graph and Traverse String

The variety of pointer graph that we saw in Figure 3, specifically,
the parse graph of a cactus expression, is something that we shall
probably not be able to resist calling a "cactus graph", against
the obvious ambiguities involved in doing so, but with regard to
its level of abstraction we should at least notice that it lies
a step further in the direction of a concrete implementation
than the last thing we called by that name.  Indeed, there
are several other distinctive features of these graphs
that we probably ought to notice before moving on.

In terms of idea-form structures, a cactus parse graph begins
with a root idea that points into a 'by'-cycle of forms, each
of whose 'sign' fields bears either a "paint", in other words,
a direct or an indirect identifier reference, or an opening
left parenthesis that indicates a link to a subtended lobe
of the cactus.

A lobe springs from a form whose 'sign' field bears a left parenthesis.
This stem form has an 'on' idea that points into a 'by'-cycle of forms,
exactly one of which has a 'sign' field that bears a right parenthesis.
This last form has an 'on' idea that points back to the form that bore
the initial left parenthesis.

In the case of a lobe, aside from the single form that bears the closing
right parenthesis, the 'by'-cycle of a lobe may list any number of forms,
each of whose 'sign' fields bears either a comma, a paint, or an opening
left parenthesis that indicates a link to a more deeply subtended lobe.

Just to draw out one of the implications of this characterization and to
stress the point of it, the root node can be painted and bear many lobes,
but it cannot be segmented, that is, the 'by'-cycle corresponding to the
root node can bear no commas.

## Expository Note 5

3.  Lexical, Literal, Logical

Theme One puts cactus graphs to work in three distinct but related ways,
what we shall call the "lexical", the "literal", and the "logical" uses,
and these applications make use of three distinct but overlapping subsets
of the broader species of cacti.  Thus, we shall find ourselves speaking
of graphs, files, and expressions of lexical, literal, and logical types,
depending on our point of view and on our focus at the moment in question.

The logical class of cacti is the broadest, encompassing the whole species
that was described above, and so we have already seen a typical example of
a logical cactus, in its avatars as an abstract graph, a pointer structure,
and a string of characters suitable for storage in an external text file.

But being a logical cactus is not just a matter of syntactic form --
it means being subject to meaningful interpretations as a sign of
a logical proposition.  From a logical perspective, we expect our
cactus expressions to 'express' something, a proposition that can
be true or false of something.

Still, before we can get to this logical, interpretive, semantic aspect
of cactus graphs we have a bit more to do in the way of detailing their
syntactic utilities.  So those are the matters that I will turn to next.

## Expository Note 6

3.1.  Lexical Cacti

The Index section of Theme One embodies an algorithm that "learns"
finite sequences of finite sequences of characters.  In this context,
from now on, I will use the word "sequence" to mean a finite sequence.

A set of sequences of sequences of whatever signs one happens to have
in an alphabet !A! is called a "two-level formal language" over !A!.
So I can say that the program's Index function "learns" a two-level
formal language over a particular alphabet !A!, the characters of
which you can probably guess, more or less.

It is usual to introduce a collection of notations that
comes along with the language of formal language theory:

An "alphabet" !A! is a finite set.

The "kleene-star" !A!* of an alphabet !A! is the set
of all finite sequences over !A!, that is, the set
of all finite sequences that can be formed from
the elements of !A!.

The "sur-plus" !A!^+ of an alphabet !A! is the set
of all finite sequences over !A! of length greater
than zero.

A "formal language" L over !A! is a subset of !A!*.
Employing the symbol "c" for "subset of", L c !A!*.

A "two-level formal language" L over !A! is a subset L c !A!**
that is specified by giving the first-level language L_1 c !A!*
and the second-level language L = L_2 c L_1* c !A!**.

The elements of L_1 are called "words" or "distinguished strings".
The elements of L_2 are called "phrases" or "distinguished strands".

We refer to L_1 as the "lexical" level and
we refer to L_2 as the "literal" level of
the two-level formal language in question.

For the rest of this discussion, pick an alphabet !A! that contains
all of the usual alphanumerics, plus a finite number of other signs
that may be found convenient, but excluding the blank, the comma,
the left and right parentheses, and the period, as these latter
marks are reserved to special purposes by the Theme One program.

## Expository Note 7

3.1.  Lexical Cacti (cont.)

Example 2.  Two-Level Formal Language:  am

Consider a very small example of a 2-level formal language,
whose only word is the character sequence <"a", "m">, and
whose only phrase is the singleton sequence <"am">, where
we observe the convention that "am" = <"a", "m">.

Formally speaking, we have the following data:

L_1 = {<"a", "m">} c !A!*.

L_2 = {<"am">} = {<<"a", "m">>} c !A!**.

Theme One stores its data about the lexical level of a 2-level
formal language in the form of a "lexical cactus".  As always,
one may choose to view this information as an abstract graph,
as a concrete pointer graph, or as a text file consisting of
the characters that encode a traversal string for the graph.

Example 2.  Lexical Level:  am

Figure 4 shows the abstract lexical cactus
for the lexical level L_1 = {<"a", "m">}.

o
|
mo-o o
|/ /
ao-o
|/
@

( a ( m , ( ) ) , ( ) )

Figure 4.  Abstract Lexical Cactus:  am

Figure 5 shows the concrete lexical cactus
for the lexical level L_1 = {<"a", "m">}.

o-----o
o-------|--o  |
|  o----o  |  |
o->| )0 |--o  |
o----o     |
^   o------o
|  /    o-----o          o-----o
o-----------------------|-/-----|--o  |  o-------|--o  |
|  o----o  o----o  o----o< o----o  |  |  |  o----o  |  |
o->| m1 |->| ,1 |->| (0 |->| )0 |--o  |  o->| )0 |--o  |
o----o  o----o  o----o  o----o     |     o----o     |
^   o------------------------------o     ^   o------o
|  /                                     |  /    o-----o
o---------------|-/--------------------------------------|-/-----|--o  |
|  o----o  o----o<              o----o              o----o< o----o  |  |
o->| a1 |->| (1 |-------------->| ,0 |------------->| (0 |->| )0 |--o  |
o----o  o----o               o----o              o----o  o----o     |
^  o----------------------------------------------------------------o
| /
o----o<
| (1 |
o----o
^
|
@

(1 a1 (1 m1 ,1 (0 )0 )0 ,0 (0 )0 )0

Figure 5.  Concrete Lexical Cactus:  am

## Expository Note 8

3.1.  Lexical Cacti (cont.)

Theme One gets its information about a two-level formal language L
from a data stream that consists of a sequence -- indefinitely long
in principle but always finite in practice -- of characters from the
alphabet !A!, interspersed with blanks that tell it when an accepted,
distinguished, established, or "received" word or phrase has passed.

For example, the picture of the data structure shown in Figure 5
depicts the state of the relevant portion of computer memory just
after the Indexer, starting from scratch, has taken up the initial
segment of a data stream that begins "a", "m", " ", " ".  The first
space tells it that a sequence of characters constituting a word has
just passed, and the second space tells it that a sequence of words
constituting a phrase has just passed.

More Examples of Lexical Cacti

At this point I think that it would be a good idea to look at
a developmental series of lexical cacti, ordered according to
their increasing complication, designed to illustrate various
features of their typical organization.  The lexical level of
Example 2 ("am") has already pushed the limits of the present
format as far as being able to delineate the concrete pointer
structures, but it will be possible to squeeze in just a few
more of the abstract cacti for the following set of examples.

Example 3.  Lexical Level:  all bees buzz

Figure 6 shows the abstract lexical cactus
and two forms of lexical files for the
character stream "all bees buzz ".

all bees buzz

o      o
|      |
so-o o zo-o o
|/ /   |/ /
eo-o   zo-o o
|/     |/ /
eo-----uo-o
|       /
|      /
o   |     /
|   |    /
lo-o o |   /
|/ /  |  /
lo-o   | / o
|/    |/ /
ao----bo-o
|      /
|     /
|    /
|   /
|  /
| /
|/
@

( a ( l ( l
, ( )
)
, ( )
)
, b ( e ( e ( s
, ( )
)
, ( )
)
, u ( z ( z
, ( )
)
, ( )
)
, ( )
)
, ( )
)

(3 a1 (1 l1 (1 l1
,1 (0 )0
)0
,0 (0 )0
)0
,0 b2 (2 e1 (1 e1 (1 s1
,1 (0 )0
)0
,0 (0 )0
)0
,0 u1 (1 z1 (1 z1
,1 (0 )0
)0
,0 (0 )0
)0
,0 (0 )0
)0
,0 (0 )0
)0

Figure 6.  Lexical Cactus:  all bees buzz

## Expository Note 9

3.1.  Lexical Cacti (cont.)

Example 4.  Lexical Level:  all apes are bold

Figure 7 shows the abstract lexical cactus
and two forms of lexical files for the
character stream "all apes are bold ".

all apes are bold

o
|
o so-o o  o
|  |/ /   |
lo-o eo-o eo-o o
|/   |/   |/ /  o
lo---po---ro-o   |
|          / do-o o
|        /    |/ /
|      /     lo-o o
|    /        |/ /
|  /         oo-o o
|/            |/ /
ao------------bo-o
|              /
|            /
|          /
|        /
|      /
|    /
|  /
|/
@

( a ( l ( l
, ( )
)
, p ( e ( s
, ( )
)
, ( )
)
, r ( e
, ( )
)
, ( )
)
, b ( o ( l ( d
, ( )
)
, ( )
)
, ( )
)
, ( )
)

(4 a3 (3 l1 (1 l1
,1 (0 )0
)0
,0 p1 (1 e1 (1 s1
,1 (0 )0
)0
,0 (0 )0
)0
,0 r1 (1 e1
,1 (0 )0
)0
,0 (0 )0
)0
,0 b1 (1 o1 (1 l1 (1 d1
,1 (0 )0
)0
,0 (0 )0
)0
,0 (0 )0
)0
,0 (0 )0
)0

Figure 7.  Lexical Cactus:  all apes are bold

At this point, all that we need to take away from the above examples
of lexical cacti is the prefix-sharing pattern of the data structure,
which apart from the cactus rather than tree forms would probably be
called "radix coding".  If one has noticed the extra "spikes" at the
right hand extremes of the cactus lobes, it would not be misleading
to view these for now as a form of "parity checks", or a built-in
redundancy for controlling potential errors in coding the data.

## Expository Note 10

3.1.  Lexical Cacti (concl.)

Example 5.  Lexical Level:  an angry ape ate a big bug

Figure 8 shows the abstract lexical cactus and
two forms of lexical files for the character
stream "an angry ape ate a big bug ".

an angry ape ate a big bug

o
|
yo-o o
|/ /
ro-o o  o    o
|/ /   |    |
go-O eo-o eo-o o
|/   |/   |/ /
no---po---to-O
|          /  o    o
|         /   |    |
|        / go-o go-o o
|       /   |/   |/ /
|      /   io---uo-o
|     /     |     /
|    /      |    /
|   /       |   /
|  /        |  /
| /         | / o
|/          |/ /
ao----------bo-o
|            /
|           /
|          /
|         /
|        /
|       /
|      /
|     /
|    /
|   /
|  /
| /
|/
@

( a ( n ( g ( r ( y
, ( )
)
, ( )
)
, ( )
) +
, p ( e
, ( )
)
, t ( e
, ( )
)
, ( )
) +
, b ( i ( g
, ( )
)
, u ( g
, ( )
)
, ( )
)
, ( )
)

(7 a5 (5 n2 (2 g1 (1 r1 (1 y1
,1 (0 )0
)0
,0 (0 )0
)0
,0 (0 )0
)1
,0 p1 (1 e1
,1 (0 )0
)0
,0 t1 (1 e1
,1 (0 )0
)0
,0 (0 )0
)1
,0 b2 (2 i1 (1 g1
,1 (0 )0
)0
,0 u1 (1 g1
,1 (0 )0
)0
,0 (0 )0
)0
,0 (0 )0
)0

Figure 8.  Lexical Cactus:  an angry ape ate a big bug

What we want to be on the lookout for in this last example of
a lexical cactus is the way that the prefix-sharing strategy
codes embedded words, the way that the lexical spelling of
the word "a" is initial to "an", "angry", "ape", and "ate",
and the way that the characters of the word "an" are also
preficial to "angry".

It is only the concrete versions of the lexical cactus
and the corresponding traversal string that contain the
real information about whether a prefix of a word in the
"lexicon" or lexical level L_1 is a word in its own right
within L_1.  This information is coded in the 'code' field
of the idea-form flag, and represents a frequency count of
just how many times a character in a particular position
has appeared as a part of a word in the data stream.

For instance, the following fragment of the above lexical file
illustrates how the word "an" is recorded as an element of L_1.

(7 a5 (5 n2 (2 g1 (1 r1 (1 y1
,1 (0 )0
)0
,0 (0 )0
)0
,0 (0 )0
)1
^
|
This frequency count being greater than zero
indicates that "an" is a word in the lexicon.

For convenience on those occasions when we do not care
about the exact frequency counts on the nodes, but only
about whether they are zero or not, we can transfer this
information about "prefixes of words that are also words"
to the abstract cactus string by marking the corresponding
right parenthesis with an extra plus sign, "+", in this way:

( a ( n ( g ( r ( y
, ( )
)
, ( )
)
, ( )
) +
^
|
This plus sign reminds us that
"an" is a word in the lexicon.

As a way of marking the information about prefix words
on the abstract lexical cactus, let us use the device
of a big node "O" for the node just before the lobal
descent to the stem in question.  Thus we have this:

o
|
yo-o o
|/ /
ro-o  o
|/  /
go--O <----------------- This big node means "an" is a word.
| /           o
|/  ...  ... /
no---po---to-O <-------- This big node means "a" is a word.
|          /  o    o
|         /   |    |
|        / go-o go-o o
|       /   |/   |/ /
|      /   io---uo-o
|     /     |     /
|    /      |    /
|   /       |   /
|  /        |  /
| /         | / o
|/          |/ /
ao----------bo-o
|            /
|           /
|          /
|         /
|        /
|       /
|      /
|     /
|    /
|   /
|  /
| /
|/
@

Figure 9.  Making a Big Point of a Prefix Word

## Expository Note 11

3.2.  Literal Cacti

| There are no strings,
| There are no strings,
| There are no strings on me!

Let us return to our littlest example
of a two-level formal language, and
pick up on the way that Theme One
stores information about the
literal level L_2.

Example 2.  Two-Level Formal Language:  am

Recall the two-level formal language L = (L_1, L_2)
whose only word, or member of L_1, is the sequence
of characters <"a", "m">, and whose only phrase, or
member of L_2, is the singleton word sequence <"am">.

Formally speaking, we have the following data:

L_1 = {<"a", "m">} c !A!*.

L_2 = {<"am">} = {<<"a", "m">>} c !A!**.

Example 2.  Literal Level:  am

Theme One stores its data about the literal level of a 2-level
formal language in the form of a "literal cactus".  As always,
one may choose to view this information as an abstract graph,
as a concrete pointer graph, or as a text file consisting of
the characters that encode a traversal string for the graph.

Things begin to get a little bit complicated at this point.
Just as the lexical cactus that stores the data for L_1 is
painted with single characters from the alphabet !A!, the
literal cactus that stores the data for L_2 needs to be
painted with words from L_1.  This is achieved, not by
recording the words themselves as character strings in
the literal cactus, but by storing just their "ideas",
that is, pointers to forms in the lexical cactus that
serve as a type of "hash codes" for the words in L_1.
These indirect identifier references are recorded in
the "alias" or the 'as' fields of the paint-bearing
forms in the literal cactus.

In order to see how these "hash nodes" work, we shall need
to drive a stratum deeper into the concrete data structure
that supports both the lexical and the literal data bases.

The display below shows a memory dump of the index structure
that is formed in the relevant piece of computer memory when
the Indexer, starting from scratch, has taken up the initial
segment of a data stream that begins "a", "m", " ", " ".

( dump index (
1003407    (         0   1003510   1003407       0
1003201    (         0   1005513   1004006       1
1005513    a         0         0   1005700       1    a
1005700    (         0   1005803   1006112       1
1005803    m         0         0   1005906       1    m
1005906    ,         0         0   1006215       1
1006215    (         0   1006402   1006009       0
1006402    )         0   1006215   1006402       0
1006009    )         0   1005700   1005803       0
1006112    ,         0         0   1002911       0
1002911    (         0   1003014   1003304       0
1003014    )         0   1002911   1003014       0
1003304    )         0   1003201   1005513       0
1004006    (         0   1007001   1003510       1
1007001        1005906         0   1007104       1    am
1007104    ,         0         0   1003800       1
1003800    (         0   1003903   1004109       0
1003903    )         0   1003800   1003903       0
1004109    )         0   1004006   1007001       0
1003510    )         0   1003407   1003201       0
))

The first column of the index dump shows the address of the form.
The second column shows the character in the form's 'sign' field.
The third, fourth, and fifth columns list the addresses in the
form's 'as' field, 'on' field, and 'by' field, respectively.
The sixth column shows the number in the form's 'code' field.
The last column highlights the identifier, if any, that is
associated with a paint-bearing lexical or literal form.

Figure 10 plots the data of the index dump as a graph,
showing the shape and some of the concrete details of
the graph-theoretical data structure that is built up
in memory when the Indexer has taken up the incept of
a data stream that begins "a", "m", " ", " ".

o-----o
o-------|--o  |
|  o----o  |  |
o->| )0 |--o  |
|6402|     |
o----o     |
^   o------o
|  /    o-----o          o-----o
o-----------------------|-/-----|--o  |  o-------|--o  |
|  o----o  o----o  o----o< o----o  |  |  |  o----o  |  |
o->| m1 |->| ,1 |->| (0 |->| )0 |--o  |  o->| )0 |--o  |
|5803|  |5906|  |6215|  |6009|     |     |3014|     |
o----o  o----o  o----o  o----o     |     o----o     |
^       ^                          |     ^   o------o
|  o----|--------------------------o     |  /    o-----o
o---------------|-/-----|--------------------------------|-/-----|--o  |
|  o----o  o----o<      |       o----o              o----o< o----o  |  |
o->| a1 |->| (1 |-------|------>| ,0 |------------->| (0 |->| )0 |--o  |
|5513|  |5700|       |       |6112|              |2911|  |3304|     |
o----o  o----o       o       o----o              o----o  o----o     |
^                   o-\---------------------------------------------o
|                  /   \
|                 /     \                                  o-----o
|                /       \                         o-------|--o  |
|               /         \                        |  o----o  |  |
|              /           \                       o->| )0 |--o  |
|             /             \                         |3903|     |
|            /               \                        o----o     |
|           /                 \                       ^   o------o
|          /                   \                      |  /    o-----o
|         /                   o-\---------------------|-/-----|--o  |
|        /                    |  o----o  o----o  o----o< o----o  |  |
|       /                     o->|  1 |->| ,1 |->| (0 |->| )0 |--o  |
|      /                         |7001|  |7104|  |3800|  |4109|     |
|     /                          o----o  o----o  o----o  o----o     |
|    /                           ^    o-----------------------------o
|   /                            |   /
|  /                             |  /                      o-----o
o-------|-/------------------------------|-/-----------------------|--o  |
|  o----o<                          o----o<                   o----o  |  |
o->| (1 |-------------------------->| (1 |------------------->| )0 |--o  |
|3201|                           |4006|                    |3510|     |
o----o                           o----o                    o----o     |
^                                ^                         ^   o------o
|                                |                         |  /
@                                @                o--------|-/-o
lex                              lit               |   o----o<  |
o-->| (0 |---o
|3407|
o----o
^
|
@

Figure 10.  Index Graph:  am

In Figure 10, the pointer marked "lex" points to the root form of
the lexical cactus for L_1, while the pointer marked "lit" points
to the root form of the literal cactus for L_2.  The lex and lit
root forms are lodged in a piece of utility data structure that
serves as a convenient dopstick or palette for keeping them
together during processing.

The thing to notice in Figure 10 is the "alias" (or is it "alibi"?)
pointer that extends from the literal cactus to the lexical cactus.
In this particular case, the literal form # 7001 has an 'as' field
that points to the lexical form # 5906.  The latter form serves in
effect as the environmentally unique "hash code" for the word "am".

Figure 11 demonstrates, in the case of our present example, a quick way to
sketch the abstract versions of the lexical and literal cacti, and it also
gives the text file representations of the corresponding traversal strings.

o
|
mo-o o                  o
|/ /              am   |
ao-o                 o-o
|/                   |/
@                    @
lex                  lit

am.lex  =  (1 a1 (1 m1 ,1 (0 )0 )0 ,0 (0 )0 )0
am.lit  =  (1 am 1 ,1 (0 )0 )0

Figure 11.  Lexical Cactus + Literal Cactus:  am

## Expository Note 12

3.2.  Literal Cacti (concl.)

The text file representations of lexical and literal cacti give Theme One
a "long-term memory", a more permanent way of storing up the "experience"
of a given stream of characterness and putting it away for future revival.

Moreover, when Theme One reloads a previously saved pair
of lex and lit files, it has the luxury of being able to
do a little more pre-processing that it otherwise had in
the midst of an ongoing character stream, and so we next
look to an illustration of that.

The display below shows a memory dump of the index structure
that is formed in the relevant piece of computer memory when
the Indexer has loaded the lex and lit files that were shown
in the legend of Figure 11.  For reasons that shall be clear
in time, let's call this reloaded version the "tabbed index".

( dump index (
1004315    (         0   1004502   1004315       0
1002911    (         0   1003201   1004708       1
1003201    a         0         0   1003304       1    a
1003304    (         0   1003510   1004006       1
1003510    m         0         0   1003613       1    m
1003613    ,   1004914         0   1003800       1    am
1003800    (         0   1003903   1003407       0
1003903    )         0   1003800   1003903       0
1003407    )         0   1003304   1003510       0
1004006    ,         0         0   1004109       0
1004109    (         0   1004212   1003014       0
1004212    )         0   1004109   1004212       0
1003014    )         0   1002911   1003201       0
1004708    (         0   1004914   1004502       1
1004914        1003613   1004914   1005101       1    am
1005101    ,         0         0   1005204       1
1005204    (         0   1005307   1004811       0
1005307    )         0   1005204   1005307       0
1004811    )         0   1004708   1004914       0
1004502    )         0   1004315   1002911       0
))

Figure 12 plots the data of the "tabbed index" dump as a graph,
showing the graph-theoretical data structure that is formed in
memory when the Indexer has loaded the lex and lit files shown
once more in the legend of the Figure.

o-----o
o-------|--o  |
|  o----o  |  |
o->| )0 |--o  |
|3903|     |
o----o     |
o--------------------o               ^   o------o
/                      \              |  /    o-----o          o-----o
/              o---------\-------------|-/-----|--o  |  o-------|--o  |
o               |  o----o  o----o  o----o< o----o  |  |  |  o----o  |  |
|               o->| m1 |->| ,1 |->| (0 |->| )0 |--o  |  o->| )0 |--o  |
|                  |3510|  |3613|  |3800|  |3407|     |     |4212|     |
|                  o----o  o----o  o----o  o----o     |     o----o     |
|                  ^       ^                          |     ^   o------o
|                  |  o----|--------------------------o     |  /    o-----o
|  o---------------|-/-----|--------------------------------|-/-----|--o  |
|  |  o----o  o----o<      |       o----o              o----o< o----o  |  |
|  o->| a1 |->| (1 |-------|------>| ,0 |------------->| (0 |->| )0 |--o  |
|     |3201|  |3304|       |       |4006|              |4109|  |3014|     |
o     o----o  o----o       o       o----o              o----o  o----o     |
\    ^                   o-\---------------------------------------------o
\   |                  /   \
\  |                 /     \                                  o-----o
\ |                /       \                         o-------|--o  |
\|               /         \                        |  o----o  |  |
\              /           \                       o->| )0 |--o  |
|\            /             \                         |5307|     |
| \          /               \                        o----o     |
|  \        /                 \       o---o           ^   o------o
|   \      /                   \      |  /            |  /    o-----o
|    \    /                   o-\-----|-/-------------|-/-----|--o  |
|     \  /                    |  o----o< o----o  o----o< o----o  |  |
|      \/                     o->|  1 |->| ,1 |->| (0 |->| )0 |--o  |
|      /\                        |4914|  |5101|  |5204|  |4811|     |
|     /  o---------------------->o----o  o----o  o----o  o----o     |
|    /                           ^    o-----------------------------o
|   /                            |   /
|  /                             |  /                      o-----o
o-------|-/------------------------------|-/-----------------------|--o  |
|  o----o<                          o----o<                   o----o  |  |
o->| (1 |-------------------------->| (1 |------------------->| )0 |--o  |
|2911|                           |4708|                    |4502|     |
o----o                           o----o                    o----o     |
^                                ^                         ^   o------o
|                                |                         |  /
@                                @                o--------|-/-o
lex                              lit               |   o----o<  |
o-->| (0 |---o
|4315|
o----o
^
|
@

am.lex  =  (1 a1 (1 m1 ,1 (0 )0 )0 ,0 (0 )0 )0
am.lit  =  (1 am 1 ,1 (0 )0 )0

Figure 12.  Tabbed Index Graph:  am

Except for one sling and one arrow, the tabbed index graph in Figure 12
is isomorphic to the untabbed index graph in Figure 10.  Of course, the
actual addresses of the forms are different, but that is to be expected
whenever the lex and lit files are reloaded in a different environment.

Comparing the tabbed index graph of Figure 12 with the index graph
of Figure 10, we can see that the extra arrow is the arc from the
lex form # 3613 to the lit form # 4914, and the extra sling is
the 'on'-loop at the lit form # 4914.  I will refer to these
as the "tab link" and the "tab loop", respectively, because
they are accessed by using the tab key on the keyboard.
In general, the tab loop is extended to a "tab cycle"
whenever there is more than one appearance of the
same lexical item in the same literal cactus.

The tab link in Figure 12 points from the "hash form" of the
lexical item "am" to the site of its first invocation in the
literal cactus.  The tab loop in this particular case merely
constitutes a self-reference at this initial site, but would
more generally expand into a tab cycle as the literal cactus
grows, to encompass all of the occurrences of a lexical item.

The preceding discussion provides a first glance at the structural anatomy of
lexical and literal cacti.  There is quite a bit more to say on this score,
and then we would have barely yet scratched the surface when it comes to
their functional roles in adaptive indexing and experiential learning.
All in the fullness of time.  But now we have the minimal background
that we need to get back to logical cacti, and that amounts to such
a compelling subject that I cannot resist returning to it at once.

## Expository Note 13

3.3. Logical Cacti

Up till now we've been working to hammer out a two-edged sword of syntax, honing the syntax of painted and rooted cacti and expressions (PARCAE), and turning it to use in taming the syntax of two-level formal languages.

But the purpose of a logical syntax is to support a logical semantics, which means, for starters, to bear interpretation as sentential signs that can denote objective propositions about some universe of objects.

One of the difficulties that we face in this discussion is that the words interpretation, meaning, semantics, and so on will have so many different meanings from one moment to the next of their use. A dedicated neologician might be able to think up distinctive names for all of the aspects of meaning and all of the approaches to them that will concern us here, but I will just have to do the best that I can with the common lot of ambiguous terms, leaving it to context and the intelligent interpreter to sort it out as much as possible.

As it happens, the language of cacti is so abstract that it can bear at least two different interpretations as logical sentences denoting logical propositions. The two interpretations that I know about are descended from the ones that C.S. Peirce called the entitative and the existential interpretations of his systems of graphical logics. For our present aims, I shall briefly introduce the alternatives and then quickly move to the existential interpretation of logical cacti.

Table 13 illustrates the existential interpretation of cactus graphs and cactus expressions by providing English translations for a few of the most basic and commonly occurring forms.

 $$\text{Cactus Graph}\!$$ $$\text{Cactus Expression}\!$$ $$\text{Interpretation}\!$$ $${}^{\backprime\backprime}\texttt{~}{}^{\prime\prime}$$ $$\operatorname{true}.$$ $$\texttt{(~)}$$ $$\operatorname{false}.$$ $$a\!$$ $$a.\!$$ $$\texttt{(} a \texttt{)}$$ $$\begin{matrix} \tilde{a} \\[2pt] a^\prime \\[2pt] \lnot a \\[2pt] \operatorname{not}~ a. \end{matrix}$$ $$a~b~c$$ $$\begin{matrix} a \land b \land c \\[6pt] a ~\operatorname{and}~ b ~\operatorname{and}~ c. \end{matrix}$$ $$\texttt{((} a \texttt{)(} b \texttt{)(} c \texttt{))}$$ $$\begin{matrix} a \lor b \lor c \\[6pt] a ~\operatorname{or}~ b ~\operatorname{or}~ c. \end{matrix}$$ $$\texttt{(} a \texttt{(} b \texttt{))}$$ $$\begin{matrix} a \Rightarrow b \\[2pt] a ~\operatorname{implies}~ b. \\[2pt] \operatorname{if}~ a ~\operatorname{then}~ b. \\[2pt] \operatorname{not}~ a ~\operatorname{without}~ b. \end{matrix}$$ $$\texttt{(} a, b \texttt{)}$$ $$\begin{matrix} a + b \\[2pt] a \neq b \\[2pt] a ~\operatorname{exclusive-or}~ b. \\[2pt] a ~\operatorname{not~equal~to}~ b. \end{matrix}$$ $$\texttt{((} a, b \texttt{))}$$ $$\begin{matrix} a = b \\[2pt] a \iff b \\[2pt] a ~\operatorname{equals}~ b. \\[2pt] a ~\operatorname{if~and~only~if}~ b. \end{matrix}$$ $$\texttt{(} a, b, c \texttt{)}$$ $$\begin{matrix} \operatorname{just~one~of} \\ a, b, c \\ \operatorname{is~false}. \end{matrix}$$ $$\texttt{((} a \texttt{)}, \texttt{(} b \texttt{)}, \texttt{(} c \texttt{))}$$ $$\begin{matrix} \operatorname{just~one~of} \\ a, b, c \\ \operatorname{is~true}. \end{matrix}$$ $$\texttt{(} a, \texttt{(} b \texttt{)}, \texttt{(} c \texttt{))}$$ $$\begin{matrix} \operatorname{genus}~ a ~\operatorname{of~species}~ b, c. \\[6pt] \operatorname{partition}~ a ~\operatorname{into}~ b, c. \\[6pt] \operatorname{pie}~ a ~\operatorname{of~slices}~ b, c. \end{matrix}$$

Table 14 illustrates the entitative interpretation of cactus graphs and cactus expressions by providing English translations for a few of the most basic and commonly occurring forms.

 $$\text{Cactus Graph}\!$$ $$\text{Cactus Expression}\!$$ $$\text{Interpretation}\!$$ $${}^{\backprime\backprime}\texttt{~}{}^{\prime\prime}$$ $$\operatorname{false}.$$ $$\texttt{(~)}$$ $$\operatorname{true}.$$ $$a\!$$ $$a.\!$$ $$\texttt{(} a \texttt{)}$$ $$\begin{matrix} \tilde{a} \\[2pt] a^\prime \\[2pt] \lnot a \\[2pt] \operatorname{not}~ a. \end{matrix}$$ $$a~b~c$$ $$\begin{matrix} a \lor b \lor c \\[6pt] a ~\operatorname{or}~ b ~\operatorname{or}~ c. \end{matrix}$$ $$\texttt{((} a \texttt{)(} b \texttt{)(} c \texttt{))}$$ $$\begin{matrix} a \land b \land c \\[6pt] a ~\operatorname{and}~ b ~\operatorname{and}~ c. \end{matrix}$$ $$\texttt{(} a \texttt{)} b$$ $$\begin{matrix} a \Rightarrow b \\[2pt] a ~\operatorname{implies}~ b. \\[2pt] \operatorname{if}~ a ~\operatorname{then}~ b. \\[2pt] \operatorname{not}~ a, ~\operatorname{or}~ b. \end{matrix}$$ $$\texttt{(} a, b \texttt{)}$$ $$\begin{matrix} a = b \\[2pt] a \iff b \\[2pt] a ~\operatorname{equals}~ b. \\[2pt] a ~\operatorname{if~and~only~if}~ b. \end{matrix}$$ $$\texttt{((} a, b \texttt{))}$$ $$\begin{matrix} a + b \\[2pt] a \neq b \\[2pt] a ~\operatorname{exclusive-or}~ b. \\[2pt] a ~\operatorname{not~equal~to}~ b. \end{matrix}$$ $$\texttt{(} a, b, c \texttt{)}$$ $$\begin{matrix} \operatorname{not~just~one~of} \\ a, b, c \\ \operatorname{is~true}. \end{matrix}$$ $$\texttt{((} a, b, c \texttt{))}$$ $$\begin{matrix} \operatorname{just~one~of} \\ a, b, c \\ \operatorname{is~true}. \end{matrix}$$ $$\texttt{(((} a \texttt{)}, b, c \texttt{))}$$ $$\begin{matrix} \operatorname{genus}~ a ~\operatorname{of~species}~ b, c. \\[6pt] \operatorname{partition}~ a ~\operatorname{into}~ b, c. \\[6pt] \operatorname{pie}~ a ~\operatorname{of~slices}~ b, c. \end{matrix}$$

## Expository Note 14

3.3.  Logical Cacti (cont.)

For the time being, the main things to take away from Tables 13 and 14 are
the ideas that the compositional structure of cactus graphs and expressions
can be articulated in terms of two different kinds of connective operations,
and that there are two distinct ways of mapping this compositional structure
into the compositional structure of propositional sentences, say, in English:

1.  The "node connective" joins a number of
component cacti C_1, ..., C_k at a node:

C_1 ... C_k
@

2.  The "lobe connective" joins a number of
component cacti C_1, ..., C_k to a lobe:

C_1 C_2   C_k
o---o-...-o
\       /
\     /
\   /
\ /
@

Table 15 summarizes the existential and entitative
interpretations of the primitive cactus structures,
in effect, the graphical constants and connectives.

Table 15.  Existential & Entitative Interpretations of Cactus Structures
o-----------------o-----------------o-----------------o-----------------o
|  Cactus Graph   |  Cactus String  |  Existential    |   Entitative    |
|                 |                 | Interpretation  | Interpretation  |
o-----------------o-----------------o-----------------o-----------------o
|                 |                 |                 |                 |
|        @        |       " "       |      true       |      false      |
|                 |                 |                 |                 |
o-----------------o-----------------o-----------------o-----------------o
|                 |                 |                 |                 |
|        o        |                 |                 |                 |
|        |        |                 |                 |                 |
|        @        |       ( )       |      false      |      true       |
|                 |                 |                 |                 |
o-----------------o-----------------o-----------------o-----------------o
|                 |                 |                 |                 |
|   C_1 ... C_k   |                 |                 |                 |
|        @        |   C_1 ... C_k   | C_1 & ... & C_k | C_1 v ... v C_k |
|                 |                 |                 |                 |
o-----------------o-----------------o-----------------o-----------------o
|                 |                 |                 |                 |
|  C_1 C_2   C_k  |                 |  Just one       |  Not just one   |
|   o---o-...-o   |                 |                 |                 |
|    \       /    |                 |  of the C_j,    |  of the C_j,    |
|     \     /     |                 |                 |                 |
|      \   /      |                 |  j = 1 to k,    |  j = 1 to k,    |
|       \ /       |                 |                 |                 |
|        @        | (C_1, ..., C_k) |  is not true.   |  is true.       |
|                 |                 |                 |                 |
o-----------------o-----------------o-----------------o-----------------o

It is possible to specify "abstract rules of equivalence" (AROE's)
between cacti, rules for transforming one cactus into another that
are "formal" in the sense of being indifferent to the above choices
for logical or semantic interpretations, and that partition the set
of cacti into formal equivalence classes.

A "reduction" is an equivalence transformation
that is applied in the direction of decreasing
graphical complexity.

A "basic reduction" is a reduction that applies
to one of the two families of basic connectives.

Table 16 schematizes the two types of basic reductions
in a purely formal, interpretation-independent fashion.

Table 16.  Basic Reductions
o---------------------------------------o
|                                       |
|    C_1 ... C_k                        |
|         @         =         @         |
|                                       |
|    if and only if                     |
|                                       |
|    C_j = @ for all j = 1 to k         |
|                                       |
o---------------------------------------o
|                                       |
|   C_1 C_2   C_k                       |
|    o---o-...-o                        |
|     \       /                         |
|      \     /                          |
|       \   /                           |
|        \ /                            |
|         @         =         @         |
|                                       |
|   if and only if                      |
|                                       |
|         o                             |
|         |                             |
|   C_j = @ for exactly one j in [1, k] |
|                                       |
o---------------------------------------o

The careful reader will have noticed that we have begun to use
graphical paints like "a", "b", "c" and schematic proxies like
"C_1", "C_j", "C_k" in a variety of novel and unjustified ways.

The careful writer would have already introduced a whole bevy of
technical concepts and proved a whole crew of formal theorems to
justify their use before contemplating this stage of development,
but I have been hurrying to proceed with the informal exposition,
and this expedition must leave steps to the reader's imagination.

Of course I mean the "active imagination".
So let me assist the prospective exercise
with a few hints of what it would take to
guarantee that these practices make sense.

## Expository Note 15

3.3.  Logical Cacti (cont.)

The foregoing discussion has given a fairly thorough description of
the abstract graphs and the concrete data structures that fall under
the name of "painted and rooted cacti".  As far as their applications
to organizing lexical and literal data, the function of the "paints"
is fairly clear:  They are more or less straightforward references
to the characters and the phrases of a two-level formal language.
This all appears to be about as concrete as anything can be and
quite free of any degree of interpretive play or flexibility.

But there is an aspect of the prefix-sharing strategy that gives
each word in a lexical cactus and each phrase in a literal cactus
a double meaning.  For one thing, it stands for itself, as always;
For another thing, it stands for the family of words or the family
of phrases, respectively, in the two-level formal language that has
that sequence of characters or that sequence of words as its prefix.

For example, consider the two-level language that is given as follows:

L_1 = {"a", "all", "an", "angry", "ape", "apes", "are", "ate",
"bees", "big", "bold", "bug", "buzz"}

L_2 = {"all bees buzz",
"all apes are bold",
"an angry ape ate a big bug"}

We make the following observations about this example:

1.  The prefix class of "a" in L_1, written "[a]L_1",
or simply "[a]" if the context is understood, is
the set of all words in L_1 that begin with "a".

2.  The prefix class of "bu" in L_1, written "[bu]L_1",
or simply "[bu]" if the context is understood, is
the set of all words in L_1 that begin with "bu",
namely, the set {"bug", "buzz"}.

3.  The prefix class of "all" in L_2, written "[all]L_2",
or simply "[all]" when the context is understood, is
the set of all phrases in L_2 that begin with "all",
namely, the set {"all bees buzz", "all apes are bold"}.

In general terms, a prefix, whether it belongs to the language or not,
can be used to "stand for", that is, as a proxy, a representative, or
a symbol for, the associated prefix class, which constitutes a subset
of the language in question.

In graphical terms, the path up to a point in a lexical or literal
cactus can be used, under the proper alternative interpretation,
to stand for the whole class of paths in the cactus that run
from the root, through that point, to a syntactic terminus,
in so many ways extending the initial path in question.

The situation that we have just now been looking at
is only a very special case of a much more general
phenomenon, falling under a principle that I will
describe this way:

Information is form before matter.

That is not a definition -- it is only an emphasis.
I am often tempted to express the idea by saying that
information is form, not matter, but the more I reflect
on it the less certain I become that form and matter are
not all one in the end, so the best that I can do for now
is to emphasize what seems fair to stress in the meantime.

One of the consequences of this principle is that all codes are
abstract, formal, and symbolic to some degree, which means that
no code has the power to determine its interpretation perfectly.

I will not attempt to prove this principle -- not knowing how long the
line between form and matter will hold, it would probably be pointless
to try -- I will merely call attention to examples of it as they arise.

The most pressing pertinent example
arises in the case of logical cacti,
so let us now turn to consider that.

## Expository Note 16

3.3.1.  Bare Cacti and Their Arithmetic

I will now elaborate a strategy that I use whenever I get worried about
the "meaning" or the "ontology" of "variables".  The problematic status
of the variable can be seen to become especially acute in light of the
principle just stated, concerning the interpretive relativity of form
and matter in the signs that bear information, that is, in light of
the circumstance that the distinction between their form and their
content is relative to interpretation.

The acuteness is due to the circumstance that the very distinction between
constant and variable now becomes relative to interpretation in this light.
In order to approach this issue from a slightly different perspective than
is usually taken up, I will not speak of constants and variables, whatever
those are, but return to the description of cacti in the media of "paints".

I introduce a few bits of informal language that will speed the discussion:

Generally speaking, one often finds that a particular formal language under
view will contain an "arithmetic" sub-language, all of whose expressions are
composed solely of symbols called "constant symbols", and as such singled out
from the "algebraic" language as a whole, whose expressions may also contain
symbols called "variable symbols".  For the moment, I will keep the colorful
terms "arithmetic" and "algebraic", but try to avoid especially the use of
the word "variable", with all its accretions of mystifying connotations.

By definition, an "impression" is an expression in the arithmetic sub-language.

Back in realm of cacti and cactus expressions, I make the following definitions:

A "bare cactus" is one devoid of paint, or what is the same thing,
a cactus that has every node painted with the empty set of paints.

Bare cacti and bare cactus expressions are also known as "impressions",
as in "impressions of value", and these are regarded as limiting cases
of the more general cacti and cactus expressions that we shall come to
apprize as "expressions of value".

What brings the question of "value" into this realm of abstract expressions
and special impressions is that there is a set of rules that can be used to
equate every impression with one or the other of these two cacti:  @ or |,
where I use the vertical bar "|" as an in-line picture of the rooted edge.

I now present a set of "abstract rules of equivalence" (AROE's) that
divide the space of impressions into exactly two equivalence classes.

Rather than trying to come up with the most elegant set of rules
from the axiomatic standpoint, I will merely give the rules that
seem to be the most frequently useful in practice, and that will
serve to rationalize the algorithm used in the Theme One program.

o-----------------------------------------------------------o
|                              |
|         o  o         o          |
|         \ /         |          |
|          @     =     @          |
|                              |
o-----------------------------------------------------------o
|                              |
|        ( ) ( )   =    ( )         |
|                              |
o-----------------------------------------------------------o
| Axiom I_1.  Distract <--- | ---> Condense        |
o-----------------------------------------------------------o

o-----------------------------------------------------------o
|                              |
|          o                    |
|          |                    |
|          o                    |
|          |                    |
|          @     =     @          |
|                              |
o-----------------------------------------------------------o
|                              |
|         (( ))    =               |
|                              |
o-----------------------------------------------------------o
| Axiom I_2.   Unfold <--- | ---> Refold         |
o-----------------------------------------------------------o

o-----------------------------------------------------------o
|                              |
|   x_1 x_2 ... x_k                  |
|   o----o-...-o----o                  |
|    \       /                   |
|    \     /                   |
|     \     /                    |
|     \   /                    |
|      \   /                     |
|      \ /                     |
|       \ /                      |
|       @       =       @       |
|                              |
|                              |
|  ( x_1, x_2, ..., x_k )  =      <blank>      |
|                              |
|                              |
|            IF AND ONLY IF           |
|                              |
|                      o       |
|  Just one of the x_1, x_2, ..., x_k = | = ( )  |
|                      @       |
|                              |
o-----------------------------------------------------------o
| Lobe Evaluation Rule                   |
o-----------------------------------------------------------o

Two special cases of the Lobe Evaluation Rule are as follows:

o-----------------------------------------------------------o
|                              |
|       x                      |
|   o-...-o-o-o-...-o                  |
|    \       /                   |
|    \     /                   |
|     \     /                    |
|     \   /                    |
|      \   /             x       |
|      \ /             o       |
|       \ /              |       |
|       @       =       @       |
|                              |
o-----------------------------------------------------------o
|                              |
|   ( , , , x , , , )   =       (x)       |
|                              |
o-----------------------------------------------------------o
| Rule I_3                         |
o-----------------------------------------------------------o

o-----------------------------------------------------------o
|                              |
|       o                      |
|   a  m|n  z                  |
|   o-...-o-o-o-...-o                  |
|    \       /                   |
|    \     /                   |
|     \     /                    |
|     \   /                    |
|      \   /                     |
|      \ /                     |
|       \ /            a...m n...z     |
|       @       =       @       |
|                              |
o-----------------------------------------------------------o
|                              |
| (a, ..., m, ( ), n, ..., z) =     a...m n...z     |
|                              |
o-----------------------------------------------------------o
| Rule I_4                         |
o-----------------------------------------------------------o

## Expository Note 17

3.3.1.  Bare Cacti and Their Arithmetic (cont.)

## Work Area

Example 1.  Painted And Rooted Cactus.

parc1.log

( ( a , ( ) ) , b c , ( d ) b e ) a c e

o
a   |       d
o---o       o
\ /  b c   |
o----o----o b e
\       /
\     /
\   /
\ /
@ a c e

o-----o
o------|--o  |
|  o---o  |  |
o->| ) |--o  |
o---o     |
^   o-----o
|  /   o-----o                o-----o
o--------------------|-/----|--o  |  o-------------|--o  |
|  o---o  o---o  o---o< o---o  |  |  |  o---o  o---o  |  |
o->| a |->| , |->| ( |->| ) |--o  |  o->| d |->| ) |--o  |
o---o  o---o  o---o  o---o     |     o---o  o---o     |
^   o--------------------------o     ^   o------------o
|  /                                 |  /                 o-----o
o------|-/----------------------------------|-/------------------|--o  |
|  o---o< o---o  o---o  o---o   o---o   o---o< o---o  o---o  o---o  |  |
o->| ( |->| , |->| b |->| c |-->| , |-->| ( |->| b |->| e |->| ) |--o  |
o---o  o---o  o---o  o---o   o---o   o---o  o---o  o---o  o---o     |
^   o---------------------------------------------------------------o
|  /
o------|-/---------------------o
|  o---o< o---o  o---o  o---o  |
o->| ( |->| a |->| c |->| e |--o
o---o  o---o  o---o  o---o
^
|
@

parc1.mod

( a ( c ( e ( b ( d ,
( d ) ( ) ) ,
( b ) ( ) ) ,
( e ) ( ) ) ,
( c ) ( ) ) ,
( a ) ( ) )

o
|
d o-------o--o d
\     /
\   /     o
\ /      |
b o-------o--o b
\     /
\   /     o
\ /      |
e o-------o--o e
\     /
\   /     o
\ /      |
c o-------o--o c
\     /
\   /     o
\ /      |
a o-------o--o a
\     /
\   /
\ /
@

parc1.ten

( a ( c ( e ( b ( d ,
( ) ) ,
( ) ) ,
( ) ) ,
( ) ) ,
( ) )

o
|
d o-------o
\     /
\   /     o
\ /      |
b o-------o
\     /
\   /     o
\ /      |
e o-------o
\     /
\   /     o
\ /      |
c o-------o
\     /
\   /     o
\ /      |
a o-------o
\     /
\   /
\ /
@

parc1.sen

a c e b d

a c e b d @

o-------------------------------------o
|  o---o  o---o  o---o  o---o  o---o  |
o->| a |->| c |->| e |->| b |->| d |--o
o---o  o---o  o---o  o---o  o---o
^
|
@

( log  (
1000103    (         0   1000206   1002106       0
1000309    (         0   1000412   1001011       0
1000515         985109   1002106   1000702       0    a
1000702    ,         0         0   1000805       0
1000805    (         0   1000908   1000412       0
1000908    )         0   1000805   1000908       0
1000412    )         0   1000309   1000515       0
1001011    ,         0         0   1001114       0
1001114         985315   1001900   1001301       0    b
1001301         985605   1002209   1001404       0    c
1001404    ,         0         0   1001507       0
1001507    (         0   1001610   1001900       0
1001713         985811   1001713   1001610       0    d
1001610    )         0   1001507   1001713       0
1001900         985315   1001114   1002003       0    b
1002003         986101   1002312   1000206       0    e
1000206    )         0   1000103   1000309       0
1002106         985109   1000515   1002209       0    a
1002209         985605   1001301   1002312       0    c
1002312         986101   1002003   1000103       0    e

(0 (0 a 0 ,0 (0 )0 )0 ,0 b 0 c 0 ,0 (0 d 0 )0 b 0 e 0 )0 a 0 c 0 e 0

( dupe (
1002911    (         0   1003014   1004914       0
1003201    (         0   1003304   1003903       0
1003407         985109   1004914   1003510       0    a
1003510    ,         0         0   1003613       0
1003613    (         0   1003800   1003304       0
1003800    )         0   1003613   1003800       0
1003304    )         0   1003201   1003407       0
1003903    ,         0         0   1004006       0
1004006         985315   1004708   1004109       0    b
1004109         985605   1005101   1004212       0    c
1004212    ,         0         0   1004315       0
1004315    (         0   1004502   1004708       0
1004605         985811   1001713   1004502       0    d
1004502    )         0   1004315   1004605       0
1004708         985315   1001114   1004811       0    b
1004811         986101   1005204   1003014       0    e
1003014    )         0   1002911   1003201       0
1004914         985109   1000515   1005101       0    a
1005101         985605   1001301   1005204       0    c
1005204         986101   1002003   1002911       0    e

(0 (0 a 0 ,0 (0 )0 )0 ,0 b 0 c 0 ,0 (0 d 0 )0 b 0 e 0 )0 a 0 c 0 e 0

( fake (
1007207    (         0   1007310   1007413       0
1005906    (         0   1006009   1006112       0
1005410         985109         0   1005513       0    a
1005513    ,         0         0   1005700       0
1005700    (         0   1005803   1006009       0
1005803    )         0   1005700   1005803       0
1006009    )         0   1005906   1005410       0
1006112    ,         0         0   1006215       0
1006215         985315         0   1006402       0    b
1006402         985605         0   1006505       0    c
1006505    ,         0         0   1006711       0
1006711    (         0   1006814   1007001       0
1006608         985811         0   1006814       0    d
1006814    )         0   1006711   1006608       0
1007001         985315         0   1007104       0    b
1007104         986101         0   1007310       0    e
1007310    )         0   1007207   1005906       0
1007413         985109         0   1007600       0    a
1007600         985605         0   1007703       0    c
1007703         986101         0   1007207       0    e

(0 (0 a 0 ,0 (0 )0 )0 ,0 b 0 c 0 ,0 (0 d 0 )0 b 0 e 0 )0 a 0 c 0 e 0

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o

Example 2.  Lexical Graph.

am

o
|
mo-o o
|/ /
ao-o
|/
@

( a ( m , ( ) ) , ( ) )

o-----o
o-------|--o  |
|  o----o  |  |
o->| )0 |--o  |
o----o     |
^   o------o
|  /    o-----o          o-----o
o-----------------------|-/-----|--o  |  o-------|--o  |
|  o----o  o----o  o----o< o----o  |  |  |  o----o  |  |
o->| m1 |->| ,1 |->| (0 |->| )0 |--o  |  o->| )0 |--o  |
o----o  o----o  o----o  o----o     |     o----o     |
^   o------------------------------o     ^   o------o
|  /                                     |  /    o-----o
o---------------|-/--------------------------------------|-/-----|--o  |
|  o----o  o----o<              o----o              o----o< o----o  |  |
o->| a1 |->| (1 |-------------->| ,0 |------------->| (0 |->| )0 |--o  |
o----o  o----o               o----o              o----o  o----o     |
^  o----------------------------------------------------------------o
| /
o----o<
| (1 |
o----o
^
|
@

(1 a1 (1 m1 ,1 (0 )0 )0 ,0 (0 )0 )0

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o

Example 3.  Lexical Graph

all bees buzz

o      o
|      |
so-o o zo-o o
|/ /   |/ /
eo-o   zo-o o
|/     |/ /
eo-----uo-o
|       /
|      /
o   |     /
|   |    /
lo-o o |   /
|/ /  |  /
lo-o   | / o
|/    |/ /
ao----bo-o
|      /
|     /
|    /
|   /
|  /
| /
|/
@

( a ( l ( l
, ( )
)
, ( )
)
, b ( e ( e ( s
, ( )
)
, ( )
)
, u ( z ( z
, ( )
)
, ( )
)
, ( )
)
, ( )
)

(3 a1 (1 l1 (1 l1
,1 (0 )0
)0
,0 (0 )0
)0
,0 b2 (2 e1 (1 e1 (1 s1
,1 (0 )0
)0
,0 (0 )0
)0
,0 u1 (1 z1 (1 z1
,1 (0 )0
)0
,0 (0 )0
)0
,0 (0 )0
)0
,0 (0 )0
)0

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o

Example 4.  Lexical Graph

all apes are bold

o
|
o so-o o  o
|  |/ /   |
lo-o eo-o eo-o o
|/   |/   |/ /  o
lo---po---ro-o   |
|          / do-o o
|        /    |/ /
|      /     lo-o o
|    /        |/ /
|  /         oo-o o
|/            |/ /
ao------------bo-o
|              /
|            /
|          /
|        /
|      /
|    /
|  /
|/
@

( a ( l ( l
, ( )
)
, p ( e ( s
, ( )
)
, ( )
)
, r ( e
, ( )
)
, ( )
)
, b ( o ( l ( d
, ( )
)
, ( )
)
, ( )
)
, ( )
)

(4 a3 (3 l1 (1 l1
,1 (0 )0
)0
,0 p1 (1 e1 (1 s1
,1 (0 )0
)0
,0 (0 )0
)0
,0 r1 (1 e1
,1 (0 )0
)0
,0 (0 )0
)0
,0 b1 (1 o1 (1 l1 (1 d1
,1 (0 )0
)0
,0 (0 )0
)0
,0 (0 )0
)0
,0 (0 )0
)0

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o

Example 5.  Lexical Graph.

an angry ape ate a big bug

o
|
yo-o o
|/ /
ro-o o  o    o
|/ /   |    |
go-O eo-o eo-o o
|/   |/   |/ /
no---po---to-O
|          /  o    o
|         /   |    |
|        / go-o go-o o
|       /   |/   |/ /
|      /   io---uo-o
|     /     |     /
|    /      |    /
|   /       |   /
|  /        |  /
| /         | / o
|/          |/ /
ao----------bo-o
|            /
|           /
|          /
|         /
|        /
|       /
|      /
|     /
|    /
|   /
|  /
| /
|/
@

( a ( n ( g ( r ( y
, ( )
)
, ( )
)
, ( )
) +
, p ( e
, ( )
)
, t ( e
, ( )
)
, ( )
) +
, b ( i ( g
, ( )
)
, u ( g
, ( )
)
, ( )
)
, ( )
)

(7 a5 (5 n2 (2 g1 (1 r1 (1 y1
,1 (0 )0
)0
,0 (0 )0
)0
,0 (0 )0
)1
,0 p1 (1 e1
,1 (0 )0
)0
,0 t1 (1 e1
,1 (0 )0
)0
,0 (0 )0
)1
,0 b2 (2 i1 (1 g1
,1 (0 )0
)0
,0 u1 (1 g1
,1 (0 )0
)0
,0 (0 )0
)0
,0 (0 )0
)0

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o

Example 6.  Lexical Graph + Literal Graph.

am

( dump index (
1003407    (         0   1003510   1003407       0
1003201    (         0   1005513   1004006       1
1005513    a         0         0   1005700       1    a
1005700    (         0   1005803   1006112       1
1005803    m         0         0   1005906       1    m
1005906    ,         0         0   1006215       1
1006215    (         0   1006402   1006009       0
1006402    )         0   1006215   1006402       0
1006009    )         0   1005700   1005803       0
1006112    ,         0         0   1002911       0
1002911    (         0   1003014   1003304       0
1003014    )         0   1002911   1003014       0
1003304    )         0   1003201   1005513       0
1004006    (         0   1007001   1003510       1
1007001        1005906         0   1007104       1    am
1007104    ,         0         0   1003800       1
1003800    (         0   1003903   1004109       0
1003903    )         0   1003800   1003903       0
1004109    )         0   1004006   1007001       0
1003510    )         0   1003407   1003201       0
))

o-----o
o-------|--o  |
|  o----o  |  |
o->| )0 |--o  |
|6402|     |
o----o     |
^   o------o
|  /    o-----o          o-----o
o-----------------------|-/-----|--o  |  o-------|--o  |
|  o----o  o----o  o----o< o----o  |  |  |  o----o  |  |
o->| m1 |->| ,1 |->| (0 |->| )0 |--o  |  o->| )0 |--o  |
|5803|  |5906|  |6215|  |6009|     |     |3014|     |
o----o  o----o  o----o  o----o     |     o----o     |
^       ^                          |     ^   o------o
|  o----|--------------------------o     |  /    o-----o
o---------------|-/-----|--------------------------------|-/-----|--o  |
|  o----o  o----o<      |       o----o              o----o< o----o  |  |
o->| a1 |->| (1 |-------|------>| ,0 |------------->| (0 |->| )0 |--o  |
|5513|  |5700|       |       |6112|              |2911|  |3304|     |
o----o  o----o       o       o----o              o----o  o----o     |
^                   o-\---------------------------------------------o
|                  /   \
|                 /     \                                  o-----o
|                /       \                         o-------|--o  |
|               /         \                        |  o----o  |  |
|              /           \                       o->| )0 |--o  |
|             /             \                         |3903|     |
|            /               \                        o----o     |
|           /                 \                       ^   o------o
|          /                   \                      |  /    o-----o
|         /                   o-\---------------------|-/-----|--o  |
|        /                    |  o----o  o----o  o----o< o----o  |  |
|       /                     o->|  1 |->| ,1 |->| (0 |->| )0 |--o  |
|      /                         |7001|  |7104|  |3800|  |4109|     |
|     /                          o----o  o----o  o----o  o----o     |
|    /                           ^    o-----------------------------o
|   /                            |   /
|  /                             |  /                      o-----o
o-------|-/------------------------------|-/-----------------------|--o  |
|  o----o<                          o----o<                   o----o  |  |
o->| (1 |-------------------------->| (1 |------------------->| )0 |--o  |
|3201|                           |4006|                    |3510|     |
o----o                           o----o                    o----o     |
^                                ^                         ^   o------o
|                                |                         |  /
@                                @                o--------|-/-o
lex                              lit               |   o----o<  |
o-->| (0 |---o
|3407|
o----o
^
|
@

o
|
mo-o o              o
|/ /          am   |
ao-o             `o-o
|/               |/
@                @
lex              lit

am.lex  =  (1 a1 (1 m1 ,1 (0 )0 )0 ,0 (0 )0 )0

am.lit  =  (1 am 1 ,1 (0 )0 )0

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o

Example A.  Painted And Rooted Cactus.

parca.log

( ( a ) , b c , ( ( ) , d ) a c e )

o
a       |   d
o       o---o
|   b c  \ /
o----o----o a c e
\       /
\     /
\   /
\ /
@

o-----o
o------|--o  |
|  o---o  |  |
o->| ) |--o  |
o---o     |
^   o-----o
o-----o                     |  /                 o-----o
o-------------|--o  |              o------|-/------------------|--o  |
|  o---o  o---o  |  |              |  o---o< o---o  o---o  o---o  |  |
o->| a |->| ) |--o  |              o->| ( |->| , |->| d |->| ) |--o  |
o---o  o---o     |                 o---o  o---o  o---o  o---o     |
^   o------------o                 ^   o--------------------------o
|  /                               |  /                        o-----o
o------|-/--------------------------------|-/-------------------------|--o  |
|  o---o< o---o  o---o  o---o  o---o  o---o< o---o  o---o  o---o  o---o  |  |
o->| ( |->| , |->| b |->| c |->| , |->| ( |->| a |->| c |->| e |->| ) |--o  |
o---o  o---o  o---o  o---o  o---o  o---o  o---o  o---o  o---o  o---o     |
^   o--------------------------------------------------------------------o
|  /
| /
o---o<
| ( |
o---o
^
|
@

parca.mod

( b ( c ( d ( a ( e ,
( e ) ( ) ) ,
( a ) ) ,
( d ) ( a  ( ) ,
( a ) ) ) ,
( c ) ( ) ) ,
( b ) ( d ( a ( ) ,
( a ) ( ) ) ,
( d ) ( ) ) )

o
|
e o---o-o e       o
\ /            |
a o---o-o a   a o---o-o a
\ /           \ /
d o-------------o-o d
\           /
\         /
\       /             o   o
\     /              |   |
\   /       o     a o---o-o a   o
\ /        |        \ /        |
c o---------o-o c   d o---------o-o d
\       /           \       /
\     /             \     /
\   /               \   /
\ /                 \ /
b o-------------------o-o b
\                 /
\               /
\             /
\           /
\         /
\       /
\     /
\   /
\ /
@

parca.ten

( b ( c ( d ( a ( e ,
( ) ) ,
( a ) ) ,
( d ) ( ( ) ,
( a ) ) ) ,
( ) ) ,
( b ) ( d ( ( ) ,
( ) ) ,
( ) ) )

o
|
e o---o           o
\ /            |
a o---o-o a     o---o-o a
\ /           \ /
d o-------------o-o d
\           /
\         /
\       /             o   o
\     /              |   |
\   /       o       o---o       o
\ /        |        \ /        |
c o---------o       d o---------o
\       /           \       /
\     /             \     /
\   /               \   /
\ /                 \ /
b o-------------------o-o b
\                 /
\               /
\             /
\           /
\         /
\       /
\     /
\   /
\ /
@

( log  (
1000103    (         0   1000206   1000103       0
1000309    (         0   1000412   1000702       0
1000515         985109   1001900   1000412       0    a
1000412    )         0   1000309   1000515       0
1000702    ,         0         0   1000805       0
1000805         985315   1000805   1000908       0    b
1000908         985605   1002003   1001011       0    c
1001011    ,         0         0   1001114       0
1001114    (         0   1001301   1001900       0
1001404    (         0   1001507   1001610       0
1001507    )         0   1001404   1001507       0
1001610    ,         0         0   1001713       0
1001713         985811   1001713   1001301       0    d
1001301    )         0   1001114   1001404       0
1001900         985109   1000515   1002003       0    a
1002003         985605   1000908   1002106       0    c
1002106         986101   1002106   1000206       0    e
1000206    )         0   1000103   1000309       0

(0 (0 a 0 )0 ,0 b 0 c 0 ,0 (0 (0 )0 ,0 d 0 )0 a 0 c 0 e 0 )0

( dupe (
1002808    (         0   1002911   1002808       0
1003014    (         0   1003201   1003407       0
1003304         985109   1004605   1003201       0    a
1003201    )         0   1003014   1003304       0
1003407    ,         0         0   1003510       0
1003510         985315   1000805   1003613       0    b
1003613         985605   1004708   1003800       0    c
1003800    ,         0         0   1003903       0
1003903    (         0   1004006   1004605       0
1004109    (         0   1004212   1004315       0
1004212    )         0   1004109   1004212       0
1004315    ,         0         0   1004502       0
1004502         985811   1001713   1004006       0    d
1004006    )         0   1003903   1004109       0
1004605         985109   1000515   1004708       0    a
1004708         985605   1000908   1004811       0    c
1004811         986101   1002106   1002911       0    e
1002911    )         0   1002808   1003014       0

(0 (0 a 0 )0 ,0 b 0 c 0 ,0 (0 (0 )0 ,0 d 0 )0 a 0 c 0 e 0 )0

( fake (
1007001    (         0   1007104   1007001       0
1005204    (         0   1005307   1005410       0
1005101         985109         0   1005307       0    a
1005307    )         0   1005204   1005101       0
1005410    ,         0         0   1005513       0
1005513         985315         0   1005700       0    b
1005700         985605         0   1005803       0    c
1005803    ,         0         0   1006402       0
1006402    (         0   1006505   1006608       0
1005906    (         0   1006009   1006112       0
1006009    )         0   1005906   1006009       0
1006112    ,         0         0   1006215       0
1006215         985811         0   1006505       0    d
1006505    )         0   1006402   1005906       0
1006608         985109         0   1006711       0    a
1006711         985605         0   1006814       0    c
1006814         986101         0   1007104       0    e
1007104    )         0   1007001   1005204       0

(0 (0 a 0 )0 ,0 b 0 c 0 ,0 (0 (0 )0 ,0 d 0 )0 a 0 c 0 e 0 )0

The formal rule of evaluation for a k-operator is:

| ( x1, x2, ..., xk )  =  [blank]
|
| iff
|
| Just one of the arguments x1, x2, ..., xk  =  ()

The interpretation of these operators, read as assertions
about the values of their listed arguments, is as follows:

1.  Existential Interpretation:   "Just one of the k argument is false."
2.  Entitative  Interpretation:   "Not just one of the k arguments is true."

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o