[Inquiry] Re: Theme One Program

[Jon Awbrey]

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

TOP.  Expository Note 4

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

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

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.

Jon Awbrey

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